Absolute Factorization of Differential Operators
JacquesArthur 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)+a_{n1}(x)y^{(n1)}(x)+...+a_{0}(x)y(x)=0, where the
coefficients a_{i} 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}+a_{n1}(x)¶^{n1}+...+a_{0}(x),
admits a factorization L=L_{2}L_{1} where the product denotes
composition. The Leibniz rule
¶· ay=(ay)'=a'y+ay'=(a¶+a')· y (aÎ k)
defines a degree on the noncommutative ring A=k[¶],
which makes it left and right Euclidean.
Consider the operator
It can be proved to be irreducible in A, i.e., it
admits no factorization L_{2}L_{1} in A. However, L factorizes
over the extension ring k((x)^{1/2})[¶]:
L= 
æ ç ç è 
¶^{2} 

¶+ 

(x)^{1/2} 
ö ÷ ÷ ø 
( 
¶^{2}(x)^{1/2} 
) 
= 
æ ç ç è 
¶^{2} 

¶+ 

+(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 k_{ext}
of k such that L is reducible in A_{ ext}=k_{ext}[¶] (for a suitable extension of the action of ¶
on k_{ext}). For an absolutely reducible operator L with a
right factor L_{1}ÎA_{ ext}, let L^{~} be the least
common left multiple of the algebraic conjugates of L_{1}. 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 L_{1}ÎA_{ ext}.
The example above motivates the following problems, sorted by
increasing complexity:

find an algorithm to decide absolute reducibility;
 find an algorithm to compute a factorization on an
algebraic extension;
 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
solution^{1} 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 secondorder ODE's is due to
Kovacic [5] and was later elaborated in [11],
again in the secondorder case. A prototypical algorithm for
higherorder 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 Cvector space generated by n linearly independent
solutions y_{i}. However, these solutions satisfy algebraic
differential relations
P_{i} 
( 
y_{1},y'_{1},...,y_{1}^{(n1)},...,y_{n},y'_{n},...,y_{n}^{(n1)}

) 
=0 
for polynomials P_{i} in n^{2} variables and with coefficients in k.
As an example, any solution y_{1} of the equation y''+y=0 satisfies
an algebraic equation y_{1}^{2}+y'_{1}^{2}=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(y_{1},...,y_{1}^{(n1)},...,y_{n},...,y_{n}^{(n1)}),
i.e., the smallest differential field extension of k which contains
the y_{i}'s and does not extend the field of constants C. This
field is called the PicardVessiot extension of L. The
group Gal(K/k) is called the differential Galois
group of L and denoted Gal_{k}(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 Ccombination of the y_{i}'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 L_{1} with solution space V_{1}Ì V. For any v_{1}Î V_{1}
and any automorphism sÎ G,
L_{1}·s(v_{1})=s(L_{1}· v_{1})=0, so that V_{1} is stable
under G. We want to prove a converse property.
For an rtuple (v_{1},...,v_{r})Î K^{r}, the
Wronskian Wr(v_{1},...,v_{r}) is classically defined as
the matrix [v_{i}^{(j)}]. The corresponding determinant
induces an application from K^{r} to K. This application is an
alternate rlinear form and satisfies
s(det(Wr(v_{1},...,v_{r})))
=det(Wr(s(v_{1}),...,s(v_{r})))
for any sÎ G. Below, we more intrinsically use rexterior
products, i.e., formal alternate rlinear
symbols v_{1}Ù...Ù v_{r} that
satisfy s(v_{1}Ù...Ù
v_{r})=s(v_{1})Ù...Ùs(v_{r}) for any sÎ G.
Let us assume V_{1} to be a 2dimensional Cvector subspace of V
with basis (f_{1},f_{2}) and stable under the action of G. More
specifically, for each sÎ G there
exist c_{i,j}^{(s)}Î C\{0} such that
s(f_{i})=c 

f_{1}+c 

f_{2}. 
Then in the exterior power L^{2}(V_{1}) where f_{1}Ù
f_{1}=f_{2}Ù f_{2}=0,
s(f_{1}Ù f_{2})=s(f_{1})Ùs(f_{2})
=(c_{1,1}c_{2,2}c_{1,2}c_{2,1})(f_{1}Ù f_{2}).
More generally, assume that V_{1} is a Csubspace of V stable
under G and with dimension dim V_{1}=r<n=dim V. Then, the
exterior rpower Ù^{r}(V_{1}) is a 1dimensional vector space
with basis w=f_{1}Ù...Ù f_{r}. For each sÎ G,
there exists a nonzero c_{s}Î C such
that s(w)=c_{s}w. In fact, c_{s}=dets
when s is viewed as a Clinear automorphism of V_{1}. Now,
for yÎ V, write
L_{1}· y= 
det(Wr(y,f_{1},...,f_{r})) 

det(Wr(f_{1},...,f_{r})) 

. 
This makes L_{1} a linear operator of order r. For any sÎ
G,
s(L_{1}· y)
= 
s(det(Wr(y,f_{1},...,f_{r}))) 

s(det(Wr(f_{1},...,f_{r}))) 

= 
c 

s(det(Wr(y,f_{1},...,f_{r}))) 


c 

s(det(Wr(f_{1},...,f_{r}))) 


=L_{1}· y. 
The coefficients of L_{1} are therefore left fixed by all elements
of G, and L_{1}Î k[¶].
Lemma 1
An operator L with solution space V admits a right factor L_{1}
such that the solution space V_{1} of L_{1} is a subspace of V if
and only if there exists a nonzero proper subspace of V which is
stable under G.
3 The BekeBronstein Algorithm
Wronskians relate the
solutions of an ODE to its coefficients. In particular, the
Wronskian w=det(Wr(y_{1},...,y_{n}))
=det[Y,Y',...,Y^{(n1)}] where Y is the column vector
of the y_{i}'s satisfies
w' 
= 

det 
[ 
Y,...,Y^{(i1)},Y^{(i+1)},Y^{(i+1)},...,Y^{(n1)} 
] 
+det 
[ 
Y,...,Y^{(n2)},Y^{(n)} 
] 


= 

a_{i}(x)det 
[ 
Y,...,Y^{(n2)},Y^{(i)} 
] 
=a_{n1}(x)det 
[ 
Y,Y',...,Y^{(n1)} 
] 
=a_{n1}(x)w. 

In short w'+a_{n1}(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:

solve L· y=0 for exponential solutions; if solutions are
found, they yield firstorder right factors of L;
 similarly, find firstorder lefthand factors by the method of
adjoint operators [4]; if solutions are found, they yield
right factors of L of order n1;
 if no solution was found, look for right factors of order r
(2£ r£ n2) as follows:

build an equation whose solution space is spanned by all
Wronskians of order r;
 solve for exponential solutions;
 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/4¶^{3}+3/4x^{2}¶^{2}x.
Both first steps of the algorithm above fail, so that the only
possible factorizations are of the form L=L_{2}L_{1} with factors of
order 2. Write w=y_{1}y_{2}'y_{1}'y_{2} for any two solutions of L. By
computing its first derivatives, reducing them by L on the
basis (y_{1}^{(i)}y_{2}^{(j)})_{i,j=0,...,3}, and looking
for linear dependencies by Gaussian elimination, we obtain that w is
annihilated by
P=¶^{5} 

¶^{4}+ 

¶^{3}
 

¶^{2}+ 

¶. 
The only exponential solutions are the constants lÎ C. This
entails that L_{1}=¶^{2}l¶+r(x) for an algebraic
function r. By identification, one finds
L_{2}=¶^{2}+ 
æ ç ç è 
l 

ö ÷ ÷ ø 
¶
+ 
æ ç ç è 
l^{2} 

+ 

r(x) 
ö ÷ ÷ ø 
, 
where r(x)=1/4x^{2}(2l^{2}x^{2}l x±
(4l^{4}x^{4}8l^{3}x^{3}+13l^{2}x^{2}15l
x+16x^{5})^{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. 16111620. 
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. 290296. 
New York, 1995.
 [3]

Beke (E.). 
Die Irreducibilität des homogenen linearen
Differentialgleichungen. Mathematische Annalen, vol. 45,
1884, pp. 278294.
 [4]

Bronstein (M.) and Petkovsek (M.). 
On Ore rings, linear operators and factorisation. Programmirovanie, n°1, 1994, pp. 2744. 
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. 343.
 [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. 124148.
 [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. 149193.
 [8]

Singer (Michael F.). 
Liouvillian solutions of nth order homogeneous linear differential
equations. American Journal of Mathematics, vol. 103, n°4,
1981, pp. 661682.
 [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. 77104.
 [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. 122.
 [11]

Ulmer (Felix) and Weil (JacquesArthur). 
Note on Kovacic's algorithm. 
Prépublication n°9413, 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. 130.
 1
 Such a solution is also frequently referred to as a
hyperexponential solution.
This document was translated from L^{A}T_{E}X by
H^{E}V^{E}A.