Absolute Factorization of Differential Operators

Jacques-Arthur Weil

Université de Limoges

Algorithms Seminar

January 27, 1997

[summary by Frédéric Chyzak]

A properly typeset version of this document is available in postscript and in pdf.

If some fonts do not look right on your screen, this might be fixed by configuring your browser (see the documentation here).

1   The Problem

Consider the linear ODE y(n)(x)+an-1(x)y(n-1)(x)+...+a0(x)y(x)=0, where the coefficients ai are rational functions of k=C(x) for an algebraic closure C of the rational number field Q. Solving this equation is an easier task when the corresponding linear differential operator in =d/dx,
L=n+an-1(x)n-1+...+a0(x),
admits a factorization L=L2L1 where the product denotes composition. The Leibniz rule
· ay=(ay)'=a'y+ay'=(a+a')· y    (aÎ k)
defines a degree on the non-commutative ring A=k[], which makes it left and right Euclidean.

Consider the operator
L=4-
1
4
3+
3
4x2
2-x.
It can be proved to be irreducible in A, i.e., it admits no factorization L2L1 in A. However, L factorizes over the extension ring k((x)1/2)[]:
L= æ
ç
ç
è		 2-
1
x
+
3
4x2
-(x)1/2 ö
÷
÷
ø		 ( 2-(x)1/2 ) = æ
ç
ç
è		 2-
1
x
+
3
4x2
+(x)1/2 ö
÷
÷
ø		 ( 2+(x)1/2 ) .
Note that since (x)1/2 and -(x)1/2 are algebraically and differentially indiscernable, the conjugates of a right factor of L are other right factors of L. In the example above, L is the least common left multiple of both conjugate right factors.

More generally, an operator LÎA is called absolutely reducible when there exists an algebraic extension kext of k such that L is reducible in A ext=kext[] (for a suitable extension of the action of  on kext). For an absolutely reducible operator L with a right factor L1ÎA ext, let L~ be the least common left multiple of the algebraic conjugates of L1. As a simple result of differential Galois theory, L~ is stable under the action of the differential Galois group of the extension A ext over A (to be defined in the next section). This entails that L~ÎA. Since L~ divides L, we have that L is irreducible but absolutely reducible in A if and only if L is the least common left multiple of the conjugates of a right factor L1ÎA ext.

The example above motivates the following problems, sorted by increasing complexity:
  1. find an algorithm to decide absolute reducibility;
  2. find an algorithm to compute a factorization on an algebraic extension;
  3. find an algorithm to compute a factorization on an algebraic extension with absolutely irreducible factors.
The algorithms to solve these problems, reduce to solving ODE's for solutions in special classes. A solution y such that yÎ k is called a rational solution, while a solution y such that y'/yÎ k is called an exponential solution1 and a solution y such that y'/y is algebraic over k is called a Liouvillian solution. An early study on this topic dates back to Liouville [6, 7]. The first algorithm to solve for rational solutions was developed in [1]. It relies on the resolution for polynomial solutions, for which an optimized algorithm is presented in [2]. Next, algorithms for factorization as well as algorithms to solve for Liouvillian solutions rely on the resolution for rational or exponential solutions. Algorithms for factorization are given in [3, 4, 9, 12]. The first algorithm to solve for Liouvillian solutions of second-order ODE's is due to Kovacic [5] and was later elaborated in [11], again in the second-order case. A prototypical algorithm for higher-order equations is to be found in [8] and was highly improved on in [10] in the third order case.

In the remainder of this summary, we comment on an algorithm to solve the second problem.

2   Differential Galois Theory

In the suitable analytical framework, the solution space V of the equation L· y=0 is the C-vector space generated by n linearly independent solutions yi. However, these solutions satisfy algebraic differential relations
Pi ( y1,y'1,...,y1(n-1),...,yn,y'n,...,yn(n-1) ) =0
for polynomials Pi in n2 variables and with coefficients in k. As an example, any solution y1 of the equation y''+y=0 satisfies an algebraic equation y12+y'12=cÎ C. For a given L, we would like to describe the ideal  I generated by all algebraic differential relations. A description is obtained by differential Galois theory.

For a differential field extension K of k, the group of automorphisms s of K that induce the identity on k and such that s(f')=s(f)' for fÎ K is called the differential Galois group of K over k and is denoted Gal(K/k). Let K be k(y1,...,y1(n-1),...,yn,...,yn(n-1)), i.e., the smallest differential field extension of k which contains the yi's and does not extend the field of constants C. This field is called the Picard-Vessiot extension of L. The group Gal(K/k) is called the differential Galois group of L and denoted Galk(L). A computational representation of G is obtained as follows. Assume y to satisfy L· y=0, then for any automorphism sÎ G, L·s(y)=s(L· y)=0. In other words, each automorphism moves a solution of L to another solution. Consequently, s(y) is a linear C-combination of the yi's with coefficients that are independent from y. This yields a matrix representation of G. Thus G is linear algebraic and the ideal  I is stable under the action of G.

We now proceed to introduce a lemma which is crucial to the algorithm discussed in the next section. Assume that L admits a right factor L1 with solution space V1Ì V. For any v1Î V1 and any automorphism sÎ G, L1·s(v1)=s(L1· v1)=0, so that V1 is stable under G. We want to prove a converse property.

For an r-tuple (v1,...,vr)Î Kr, the Wronskian Wr(v1,...,vr) is classically defined as the matrix [vi(j)]. The corresponding determinant induces an application from Kr to K. This application is an alternate r-linear form and satisfies
s(det(Wr(v1,...,vr))) =det(Wr(s(v1),...,s(vr)))
for any sÎ G. Below, we more intrinsically use r-exterior products, i.e., formal alternate r-linear symbols v1Ù...Ù vr that satisfy s(v1Ù...Ù vr)=s(v1)Ù...Ùs(vr) for any sÎ G.

Let us assume V1 to be a 2-dimensional C-vector subspace of V with basis (f1,f2) and stable under the action of G. More specifically, for each sÎ G there exist ci,j(s)Î C\{0} such that
s(fi)=c
(s)
 
i,1
f1+c
(s)
 
i,2
f2.
Then in the exterior power L2(V1) where f1Ù f1=f2Ù f2=0,
s(f1Ù f2)=s(f1)Ùs(f2) =(c1,1c2,2-c1,2c2,1)(f1Ù f2).

More generally, assume that V1 is a C-subspace of V stable under G and with dimension dim V1=r<n=dim V. Then, the exterior r-power Ùr(V1) is a 1-dimensional vector space with basis w=f1Ù...Ù fr. For each sÎ G, there exists a non-zero csÎ C such that s(w)=csw. In fact, cs=dets when s is viewed as a C-linear automorphism of V1. Now, for yÎ V, write
L1· y=
det(Wr(y,f1,...,fr))
det(Wr(f1,...,fr))
.
This makes L1 a linear operator of order r. For any sÎ G,
s(L1· y) =
s(det(Wr(y,f1,...,fr)))
s(det(Wr(f1,...,fr)))
=
c
 
s
s(det(Wr(y,f1,...,fr)))
c
 
s
s(det(Wr(f1,...,fr)))
=L1· y.
The coefficients of L1 are therefore left fixed by all elements of G, and L1Î k[].
Lemma 1   An operator L with solution space V admits a right factor L1 such that the solution space V1 of L1 is a subspace of V if and only if there exists a non-zero proper subspace of V which is stable under G.

3   The Beke-Bronstein Algorithm

Wronskians relate the solutions of an ODE to its coefficients. In particular, the Wronskian w=det(Wr(y1,...,yn)) =det[Y,Y',...,Y(n-1)] where Y is the column vector of the yi's satisfies
w'
=
n-1
å
i=1
det [ Y,...,Y(i-1),Y(i+1),Y(i+1),...,Y(n-1) ] +det [ Y,...,Y(n-2),Y(n) ]
 
=-
n-1
å
i=0
ai(x)det [ Y,...,Y(n-2),Y(i) ] =-an-1(x)det [ Y,Y',...,Y(n-1) ] =-an-1(x)w.
In short w'+an-1(x)w=0 (Liouville relation); the other coefficients of L satisfy similar relations.

The algorithm developed and implemented by Bronstein after Beke's work and described in [4] makes use of Wronskians in the following way. To obtain a right factor of the operator L:
  1. solve L· y=0 for exponential solutions; if solutions are found, they yield first-order right factors of L;
  2. similarly, find first-order left-hand factors by the method of adjoint operators [4]; if solutions are found, they yield right factors of L of order n-1;
  3. if no solution was found, look for right factors of order r (2£ r£ n-2) as follows:
    1. build an equation whose solution space is spanned by all Wronskians of order r;
    2. solve for exponential solutions;
    3. test which solutions are Wronskians, i.e., pure exterior products, and obtain a right factor.
As a comparison, Singer's method, which was implemented by Van Hoeij, relies on solving for rational solutions only.

4   An Example

Again, consider the operator L=4-1/43+3/4x22-x. Both first steps of the algorithm above fail, so that the only possible factorizations are of the form L=L2L1 with factors of order 2. Write w=y1y2'-y1'y2 for any two solutions of L. By computing its first derivatives, reducing them by L on the basis (y1(i)y2(j))i,j=0,...,3, and looking for linear dependencies by Gaussian elimination, we obtain that w is annihilated by
P=5-
5
2x
4+
21
4x2
3 -
69
8x3
2+
8x5+15
2x4
.
The only exponential solutions are the constants lÎ C. This entails that L1=2-l+r(x) for an algebraic function r. By identification, one finds
L2=2+ æ
ç
ç
è		 l-
1
x
ö
÷
÷
ø		 + æ
ç
ç
è		 l2-
l
x
+
3
4x2
-r(x) ö
÷
÷
ø		 ,
where r(x)=1/4x2(2l2x2-l x± (4l4x4-8l3x3+13l2x2-15l x+16x5)1/2). Realizing that l=0, we get r(x)=±(x)1/2 and the factorizations of the first section.

References

[1]
Abramov (S. A.). -- Rational solutions of linear differential and difference equations with polynomial coefficients. USSR Computational Mathematics and Mathematical Physics, vol. 29, n°11, 1989, pp. 1611--1620. -- Translation of the Zhurnal vychislitel'noi matematiki i matematichesckoi fiziki.

[2]
Abramov (Sergei A.), Bronstein (Manuel), and Petkovsek (Marko). -- On polynomial solutions of linear operator equations. In Levelt (A.) (editor), Symbolic and algebraic computation. pp. 290--296. -- New York, 1995.

[3]
Beke (E.). -- Die Irreducibilität des homogenen linearen Differentialgleichungen. Mathematische Annalen, vol. 45, 1884, pp. 278--294.

[4]
Bronstein (M.) and Petkovsek (M.). -- On Ore rings, linear operators and factorisation. Programmirovanie, n°1, 1994, pp. 27--44. -- Also available as Research Report 200, Informatik, ETH Zürich.

[5]
Kovacic (Jerald J.). -- An algorithm for solving second order linear homogeneous differential equations. Journal of Symbolic Computation, vol. 2, 1986, pp. 3--43.

[6]
Liouville (J.). -- Premier mémoire sur la détermination des intégrales dont la valeur est algébrique. Journal de l'École polytechnique, n°14, 1833, pp. 124--148.

[7]
Liouville (J.). -- Second mémoire sur la détermination des intégrales dont la valeur est algébrique. Journal de l'École polytechnique, n°14, 1833, pp. 149--193.

[8]
Singer (Michael F.). -- Liouvillian solutions of n-th order homogeneous linear differential equations. American Journal of Mathematics, vol. 103, n°4, 1981, pp. 661--682.

[9]
Singer (Michael F.). -- Testing reducibility of linear differential operators: A group theoretic perspective. Applicable Algebra in Engineering, Communication and Computing, vol. 7, n°2, 1996, pp. 77--104.

[10]
Singer (Michael F.) and Ulmer (Felix). -- Necessary conditions for Liouvillian solutions of (third order) linear differential equations. Applicable Algebra in Engineering, Communication and Computing, vol. 6, n°1, 1995, pp. 1--22.

[11]
Ulmer (Felix) and Weil (Jacques-Arthur). -- Note on Kovacic's algorithm. -- Prépublication n°94-13, Institut de recherche mathématique de Rennes, Université de Rennes 1, France, July 1994.

[12]
Van Hoeij (Mark). -- Formal solutions and factorization of differential operators with power series coefficients. Journal of Symbolic Computation, vol. 24, n°1, July 1997, pp. 1--30.
1
Such a solution is also frequently referred to as a hyperexponential solution.
This document was translated from LATEX by HEVEA.