A method for the Integration of Solutions of Ore Equations

Sergei A. Abramov

Computer Center of the Russian Academy of Science, Vavilova 40, Moscow 117967, Russia

                              abramov@ccas.ru
                            sabramov@cs.msu.su ^{∗}

Mark van Hoeij

Department of mathematics University of Nijmegen, 6525 ED Nijmegen The Netherlands

                                                                 hoeij@sci.kun.nl

Abstract

We introduce the notion of the adjoint Ore ring and give a definition of adjoint polynomial, operator and equation. We apply this for integrating solutions of Ore equations.

1 Introduction

The study of Ore rings [10, 4] is attractive because, first of all, it allows statement concerning operators of various kinds to be treated simultaneously. In addition, the use of this theory lets one create general purpose algorithms and corresponding programs adjustable to a specific form of operators and equations.

The goal of this paper is integration (in the difference case this is: summation) of solutions of Ore equations. For this purpose we first define an adjoint for an Ore ring, similar to the well known adjoint for differential operators, and also similar to ideas in [7].

For solving linear differential equations one often applies “reduction of order” in case one of the solutions was found. Reduction of order leads to the problem of integrating solutions of a differential equation. In this paper we give a simple and easy to implement method for this problem. Given an operator L, our algorithm computes an operator L̃ of minimal order such that all solutions of L are derivatives of solutions of L̃. In the case that the order of L̃ equals the order of L, this effectively removes, at low computational cost, one integration symbol from the symbolic solutions of the original differential equation. The use of Ore rings makes our algorithm more general, so that it can be applied for the case of difference and q-difference equations as well.

2 Integrating factors and adjoints

Let k be a field and let K be a ring that contains k. We consider Ore rings k[∇] and K[∇] for two different types of ∇:

• Case 1: ∇ is a derivation on K, i.e. ∇(ab) = b∇(a) + a∇(b) for all a, b ∈ K, and it is also a derivation on k (so ∇(a) ∈ k for a ∈ k).

• Case 2: ∇ = σ − 1 where σ is an automorphism of k and of K.

In both cases we will assume that the set of constants Const = {a ∈ K|∇(a) = 0} is a subfield of k. Let k[∇] be the ring of all operators ∑_{i=0}^{n} a_{i}∇^{i}. Similarly define K[∇]. An element L of K[∇] or k[∇] can be viewed as a Const-linear map from K to K, L(y) = ∑_{i=0}^{n} a_{i}∇^{i}(y) ∈ K. We will assume that ∑ a_{i}∇^{i} ∈ K[∇] acts as the zero map on K if and only if all a_{i} are zero. A common situation for such Ore rings is that one is given an equation L(y) = 0 for some L ∈ k[∇] and one is interested in finding solutions y of this equation in some (field or ring) extension K of k. By “rational solutions” of L we mean solutions y ∈ k.

Now k[∇] and K[∇] are rings. The multiplication in these ring corresponds to composition of operators. Using the relation

• Case 1: ∇ ∘ a = a∇ + ∇(a)

• Case 2: ∇ ∘ a = σ(a)∇ + ∇(a)

any product of elements in K[∇] can be written in a standard form ∑_{i=0}^{n} a_{i}∇^{i}. We define ∇^{∗} as follows:

• Case 1: ∇^{∗} = −∇

• Case 2: ∇^{∗} = σ^{−1} − 1

and we can define the adjoint ring of k[∇] as k[∇^{∗}]. Note that in case 1 we have k[∇] = k[∇^{∗}] but in case 2 k[∇] need not be equal to its adjoint ring. Now we can define the adjoint map

ad : k[∇] → k[∇^{∗}]

for an operator L = ∑_{i} a_{i}∇^{i} as follows:

ad L = ∑_{i}(∇^{∗})^{i} ∘ a_{i}.

This can be rewritten to the standard form ad L = ∑_{i} b_{i}(∇^{∗})^{i} for some b_{i} ∈ k. For brevity we will often write L^{∗} instead of ad L.

Now one can verify that the adjoint is a Const-linear bijective map and that

(L ∘ M)^{∗} = M^{∗} ∘ L^{∗}

for all L, M ∈ k[∇].

∗Work reported herein was supported in part by the RFBR and INTAS under Grant 95-IN-RU-412.

Proposition 1

∇(f) = 0 ⟺ f ∈ Const ⟺ ∇^{∗}(f) = 0.

Additionally for any L ∈ K[∇]

L(1) = 0 ⟺ ∃_{M} L = M ∘ ∇

and

L^{∗}(1) = 0 ⟺ ∃_{M} L = ∇ ∘ M.

Proof: The first statement follows from the definitions. Write L = ∑_{i} a_{i}∇^{i} for some a_{i} ∈ K. Now L = M ∘ ∇ for some M if and only if a_{0} = 0. Now the second statement followings because a_{0} = L(1). For the third statement, write L^{∗} ∈ K[∇^{∗}] (note that in general L^{∗} need not be an element of K[∇]) as L^{∗} = ∑_{i} a_{i}(∇^{∗})^{i} for some a_{i} ∈ K. Now L = ∑_{i} ∇^{i} ∘ a_{i} and L = ∇ ∘ M for some M iff a_{0} = L^{∗}(1) = 0. □

An element l ∈ K is an integrating factor for L ∈ K[∇] if lL = ∇ ∘ M, where M ∈ K[∇].

The following Proposition shows that in the general case the adjoint operator has an important feature which is well known in the differential case.

Proposition 2 l ∈ K is an integrating factor for L iff L^{∗}(l) = 0.

Proof: By Proposition 1 we have lL = ∇ ∘ M for some M iff (lL)^{∗}(1) = 0. Since l ∈ K we have l^{∗}(1) = l(1) = l and so (lL)^{∗}(1) = L^{∗}(l). □

3 Accurate integration

An element g ∈ K is a primitive of f ∈ K if ∇(g) = f. Consider the following problem:

Let f ∈ K and the minimal annihilating operator L ∈ k[∇] for f be given. So n = ord L is minimal with the property that L ∈ k[∇] and L(f) = 0. Decide whether there exists a primitive g of f such that the minimal annihilating operator L̃ for g has order n. If so, then construct all such g together with their minimal annihilating operators. We show that this problem (the problem of the accurate integration) can be solved with the help of finding integrating factors.

Let g be any primitive of f and L̃ ∈ k[∇] be the minimal annihilating operator for g. Now L ∘ ∇(g) = L(f) = 0 hence by the minimality of L̃ (and by the fact that k[∇] is a Euclidean ring, c.f. [10]) it follows that L̃ is a right-hand factor of L ∘ ∇. Hence

ord L̃ ≤ ord L ∘ ∇ = n+1 and if ord L̃ = n+1 then L̃ = L∘∇.

Consider the least common left multiple (LCLM) of L̃ and ∇ presented in the form

LCLM(L̃, ∇) = L_{1} ∘ ∇,  (1)

L_{1} ∈ k[∇], ord L_{1} ≤ ord L̃. We have L̃(g) = 0, so L_{1}∘∇(g) = 0, hence L_{1}(f) = 0 and so ord L_{1} ≥ n by the minimality of L. So ord LCLM(L̃, ∇) ≥ n + 1 and hence

ord L̃ ≥ n and if ord L̃ = n then GCRD(L̃, ∇) = 1 (2)

where GCRD stands for greatest common right divisor.

Thus there are two possibilities for ord L̃: n and n + 1. The questions are: when is ord L̃ = n and what is L̃ in this case.

If ord L̃ = n then from equation (2) it follows that

r ∘ ∇ + l̃∘ L̃ = 1  (3)

for some l̃, r ∈ k[∇] with ord r < ord L̃ = n and ord l̃ < ord ∇ = 1. Applying equation (3) on g results in

r(f) = g.

Applying ∇ on this equation yields ∇ ∘ r(f) = f so (1 − ∇ ∘ r)(f) = 0. By the minimality of L it follows that 1−∇∘r = l ∘ L for some operator l hence

∇ ∘ r + l ∘ L = 1.  (4)

Conversely, if equations (3),(4), ord r < n and ord l̃ < 1 hold then one can easily verify that ord L̃ = n, that L̃ is the minimal annihilating operator for r(f) and that ∇(r(f)) = f. Hence equations (3),(4) with the conditions on ord r and ord l̃are equivalent with the problem of accurate integration. The inequality ord l̃ < 1 implies ord l = ord l̃ = 0, i.e. l, l̃ ∈ k. Both sides of (4) are operators and if we take the adjoints we get

r^{∗} ∘ ∇^{∗} + L^{∗} ∘ l^{∗} = 1.  (5)

Applying the left- and the right-hand side of (5) to 1 we obtain

L^{∗}(l) = 1.  (6)

For each solution l ∈ k of (6) we have (1 − lL)^{∗}(1) = 1 − L^{∗}(l) = 0 and so by Proposition 1 it follows that equation (4) allows a unique solution r. The minimal annihilating operator of g is defined up to a left-hand factor in k. Therefore we can take l̃= 1 and

L̃ = 1 − r ∘ ∇.  (7)

This operator annihilates one-unique primitive r(f) of f. If operators r_{0} and r_{1} correspond to different solutions l_{0} and l_{1} of (6) then the primitives r_{0}(f) and r_{1}(f) of f are also different (otherwise the operator r_{0} − r_{1} of order < n would annihilate f). Since primitives are determined up to constants it follows that (r_{0} − r_{1})(f) must be a constant.

L̃ maps the primitive r(f) of f to 0. Furthermore it maps any constant to itself. Hence it maps any primitive of f to a constant.

The preceding can be formulated as the following

Proposition 3 Let L ∈ k[∇] be the minimal annihilating operator for f ∈ K and L^{∗}(l) = 1, l ∈ k. Then the equality ∇ ∘ r + l ∘ L = 1 uniquely determines r. In turns r lets find the operator L̃ ∈ k[∇] (up to a factor in k) annihilating the primitive

g = r(f)  (8)

of f. If formula (7) is used to construct L̃ then L̃(g_{1}) ∈ Const for any primitive g_{1} of f. □

If (6) has no solution in k then no primitive of f has a minimal annihilating operator over k of order n. If (6) has a unique solution in k then a primitive and its minimal annihilating operator can be defined uniquely by (8),(7).

Proposition 4 Let M be the set of all solutions of (6) in k. Then M either is empty, or M has only one element, or M has the form

l_{0} + Ch,  (9)

where l_{0}, h ∈ k, h ≠ 0, C runs through Const. In the last case any primitive of f has a minimal annihilating operator of order n.

Proof: Suppose there exists a solution l_{0} of (6). Then the solution space of (6) is of the form l_{0} + V where V is the solution space of L^{∗}(l) = 0. The map l ↦ r(f) (r depends on l by (4)) is an injective (here we use that L is minimal) linear map from l_{0} + V to the set of primitives of f. Since the set of primitives is an affine space of dimension 1, V must have dimension ≤ 1. □

Note that if the solution space of L^{∗}(l) = 0 has dimension > 1 then the map l ↦ r(f) can not be injective because the image of this map has dimension ≤ 1. The fact that the map is not injective means that there exists an r, ord r < ord L, with r(f) = 0 which contradicts our assumption that L is minimal.

Let now M have the form (9). Denote by l_{C} the solution l_{0} + Ch of (6) and by r_{C} and L̃_{C} the operators which are found starting with l_{C}. Since h is an integrating factor for L we have hL = ∇ ∘ M, ord M = n − 1. Now from (4) and (7) we obtain

r_{C} = r_{0} − CM  (10)
L̃_{C} = L̃_{0} + CM ∘ ∇  (11)

where r_{0} and L̃_{0} correspond to the solution l_{0} of (6). The operator L̃_{C} is the minimal annihilating operator for the primitive

g_{C} = r_{C}(f)  (12)

of f.

Let g be a primitive of f and C ∈ Const. Then L̃_{C}(g) = L̃_{0}(g)+CM(∇(g)) = L̃_{0}(g)+CM(f) and M(∇(g)) ∈ Const because L̃_{C}(g), L̃_{0}(g) ∈ Const. Additionally M(f) ≠ 0 because ord M < ord L. Taking

C = − \frac{L̃_{0}(g)}{M(f)}  (13)

we obtain the value of C such that g = r_{C}(f).

The price which we pay for solving the problem of the accurate integration is finding solutions in k of the equation L^{∗}(y) = 1. If k is a rational function field, then the last problem can be solved effectively in all the cases mentioned in the examples below (c.f. [1, 2, 3]).

Examples Let k = C(x), ∇ = D = \frac{d}{dx}. Applying the described approach to f = ln x,

L = xD^{2} + D  (14)

gives L^{∗} = xD^{2} +D, and the general rational solution of the equation L^{∗}(y) = 1 is l_{C} = x + C. Therefore l_{0} = x, h = 1. So any primitive of ln x is annihilated by a second order operator. We obtain

L̃_{C} = (x^{2} + Cx)D^{2} − xD + 1, r_{C} = (−x^{2} − Cx)D + x.

The algorithm proposed above lets in some cases integrate special functions. The minimal annihilating operator for Bessel function J_{1} is x^{2}D^{2} + xD + (x^{2} − 1). Applying the algorithm we get L^{∗} = x^{2}D^{2} + 3xD + x^{2}, and L^{∗}(y) = 1 has one-unique rational solution \frac{1}{x^{2}} . We obtain

L̃ = D^{2} + \frac{1}{x} D + 1, r = −D − \frac{1}{x} .

Thus we get a primitive of J_{1} in the form

r(J_{1}) = (−D − \frac{1}{x})(J_{1}),

with the minimal annihilating operator D^{2} + \frac{1}{x} D + 1. Other primitives can be annihilated by the operator L ∘ D of order 3. This result is in agreement with the Bessel function theory.

Let k = Q(n), ∇ = E − 1 where E(n) = n + 1. Let u_{0}, u_{1}, ... be Fibonacci numbers. Apply the described approach to u_{n}^{2}, L = E^{3} − 2E^{2} − 2E + 1. We obtain L^{∗} = E^{−3}−2E^{−2}−2E^{−1}+1, and the equation L^{∗}(y) = 1 has the unique rational solution − \frac{1}{2} . It shows that one-unique primitive of u_{n}^{2} can be annihilated by an operator the order 3: L̃ = − \frac{1}{2} L, while r = \frac{1}{2} (E^{2} − E − 3). This primitive is

\frac{1}{2} (u_{n+2}^{2} − u_{n+1}^{2} − 3u_{n}^{2})

and in particular

∑_{i=0}^{n} u_{i}^{2} = \frac{1}{2} (u_{n+3}^{2} − u_{n+2}^{2} − 3u_{n+1}^{2}).

□

The algorithm described in this Section, is a generalization of well known Gosper’s algorithm ([8]) which, given a first order (i.e. hyper-geometric) sequence over Q(n), lets recognize whether there exists another sequence of such a kind that is a primitive for the given sequence. The algorithm, proposed above, solves the analogous problem for a wide class of equations of any order n. Using (8) we can express the mentioned primitive explicitly.

Remark that from the results in this paper it follows that the following 3 problems are equivalent.

• Find the solutions l ∈ k of L^{∗}(l) = 1.

• Let f ∈ K. Let the minimal annihilating operator L ∈ k[∇] for f be given. Decide whether there exists r ∈ k[∇] such that r(f) is a primitive of f. If so, then construct such r.

• The problem of accurate integration.

• Computing solutions (r, l) of equation (4). Note that according to section 3.1 in [9] this is equivalent to computing a complement of Const in the solution space of L ∘ ∇.

Similar problems, but in a more general situation, are studied in [5, 6]. Our approach is less general but it has the advantage of simplicity, it only uses an adjoint and rational solutions, which are quite efficient.

Acknowledgment

We would like to thank the referees and Marko Petkovšek who provided us with useful comments on earlier draft.

References

[1] S. A. Abramov (1989): Rational solutions of linear difference and differential equations with polynomial coefficients, USSR Comput. Maths. Math. Phys. 29, 7 – 12. Transl. from Zl. Vychislit. matem. mat. fiz. 29, 1611 – 1620.

[2] S. A. Abramov, K. Yu. Kvashenko (1991): Fast algorithm to search for the rational solutions of linear differential equations, Proc. ISSAC’91, 267 – 270.

[3] S. A. Abramov (1995): Rational solutions of linear difference and q-difference equations with polynomial coefficients, Programming and Comput. Software 21, No 6, 273 – 278. Transl. from Programmirovanie, No 6, 3 – 11.

[4] M. Bronstein, M. Petkovšek (1995): An introduction to pseudo-linear algebra, Theoretical Computer Science 157, 3 – 33.

[5] F. Chyzak (1996): ∂-finite functions, INRIA. Algorithm seminar 1995–1996 , 43–46.

[6] F. Chyzak, B. Salvy (1996): Non-commutative elimination in Ore algebra proves multivariate holonomic identities, INRIA Research Report, No 2799.

[7] P. M. Cohn, Skew Fields (1995): Theory of General Division Rings, Encyclopedia of Mathematics and its Applications, Cambridge University Press, 57.

[8] R. W. Gosper, Jr. (1978): Decision procedure for indefinite hypergeometric summation, Proc. Natl. Acad. Sci. USA 75, 40 – 42.

[9] M. van Hoeij (1996): Rational Solutions of the Mixed Differential Equation and its Application to Factorization of Differential Operators, Proc. ISSAC’96, 219– 225.

[10] O. Ore (1933): The theory of non-commutative polynomials, Ann. Maths. 34, 480 – 508.