then L2 (h) = SL1 (f ) = S(b) as desired. To prove the other direction, suppose L2 (h) = S(b)

˜ ˜

for some h ∈ k. Let f = R(h) + L1 (b) ∈ k. Then

˜ ˜

L1 (f ) = L1 R(h) + L1 L1 (b)

˜ ˜

SL2 (h) + (1 ’ SS)(b)

=

˜ ˜

SS(b) + b ’ SS(b)

=

= b,

completing the proof.

Let k = C(x). Given a = ∈ k, p, q ∈ C[x] with (p, q) = 1, de¬ne deg a to be the

p

q

maximum of deg p and deg q. Given L = an Dn + an’1 Dn’1 + . . . + a0 ∈ D, de¬ne deg L =

max1¤i¤n (deg ai ). Given operators L and L2 , we will want to parameterize all pairs of

operators (L1 , S) satisfying:

1. L1 is a monic operator equivalent to L2 that divides L on the left, and

23

2. ord S ¤ ord L2 ’ 1 and L2 R = SL1 for some R ∈ D, GCRD(L1 , R) = 1.

Lemma 3.2.5 Let T1 and T2 be operators with coe¬cients in C(x) of orders n and m

and degrees N and M respectively. If T3 is an operator with coe¬cients in C(x) such that

T3 T2 = T1 , then deg T3 ¤ (n ’ m + 1)2 M + N.

Proof. See Lemma 2.5 of [BS99].

Lemma 3.2.6 Let k = C(x) and L, L2 be monic operators in D of orders n and m respec-

tively.

1. For any i, 0 ¤ i ¤ ord L, one can e¬ectively ¬nd an integer ni such that if L = L1 L0

with monic L1 , L0 ∈ D and ord L1 = i, then deg L0 ¤ ni .

˜ ˜ ˜˜

2. One can e¬ectively ¬nd an integer N such that if L2 R = SL for some R, S ∈ D with

˜ ˜ ˜

ord R < ord L and ord S < ord L2 , then deg S ¤ N.

3. One can e¬ectively ¬nd an integer M such that if L1 is a monic operator equiva-

lent to L2 , dividing L on the left, then there exist R and S in D such that L2 R =

SL1 , ord R < ord L1 , ord S < ord L2 and deg R, deg S ¤ M.

Proof. See Lemma 2.6 of [BS99].

The next lemma relies on the following notion. Consider the set Fn,m ⊆ C(x)[D] of

operators of order n and degree at most m. We de¬ne a bijection between Fn,m and a

n

subset of C 2(n+1)(m+1) as follows: Suppose L = ai Di ∈ Fn,m . Suppose moreover that,

i=0

for each i, we have

m j

j=0 bi,j x

, bi,j , ci,j ∈ C, ( bi,j xj , ci,l xl ) = 1.

ai = m j

j=0 ci,j x j l

Then identify L with the vector (b0,0 , b0,1 , . . . , cn’1,m ) ∈ C 2(n+1)(m+1) . De¬ne a set L ⊆ Fn,m

to be constructible if, under this identi¬cation, L corresponds to a constructible subset of

C 2(n+1)(m+1) .

Lemma 3.2.7 Let k, L and L2 be as in the hypotheses of Lemma 3.2.6.

24

1. The set of pairs of monic operators (L1 , L0 ), ord L1 = m, ord L0 = n ’ m such

that L = L1 L0 forms a constructible set whose de¬ning equations can be explicitly

computed.

2. Let nm be as in Lemma 3.2.6.1 and M be as in Lemma 3.2.6.3. The set PL2 of triples

of operators (L1 , R, S) where

(a) ord L1 = m; deg L1 ¤ nm ; ord R, S ¤ m ’ 1; deg R, S ¤ M,

(b) L1 divides L on the the left,

(c) GCRD(L1 , R) = 1,

(d) L2 R = SL1 (and so L1 is equivalent to L2 )

is constructible. Furthermore, one can e¬ectively calculate the de¬ning equations of

PL2 .

3. The set ML2 of pairs (L1 , S) such that for some R ∈ D, (L1 , R, S) ∈ PL2 is a

constructible set. Furthermore, one can e¬ectively calculate the de¬ning equations of

ML2 .

Proof. See Lemma 2.7 of [BS99].

Lemma 3.2.8 Let k = C(x), N an integer and L = y (n) + . . . + a0 y ∈ D. The set V of

(c0 , . . . , cN , d0 , . . . , dN ) ∈ C 2N +2 such that

cN xN + . . . + c0

L(y) = (3.14)

dN xN + . . . + d0

has a solution in k, is constructible. Furthermore, one can e¬ectively ¬nd the de¬ning

equations of V.

Proof. See Lemma 2.8 of [BS99].

It is a fact that Lemma 3.2.8 holds in the case where k is an algebraic extension of C(x)

and the parameterized rational function given in the right-hand side of (3.14) is replaced

by a parameterized member of k. [BS99] restricts attention to the case where k = C(x) for

convenience. Also remark that the above lemmas represent an extension of known methods

25

for expressing the set of factorizations of a given operator as a constructible set; see [Gri90]

and [Tsa96].

The above lemmas now provide su¬cient machinery for a decision procedure to calcu-

late the Galois group of L(y) = b. Here is the algorithm, as stated in [BS99] with slight

modi¬cations:

Algorithm I

Input: A completely reducible nth order operator L ∈ C(x)[D] and an element b ∈ C(x).

Output: A set of equations in n2 variables de¬ning the Galois group GL of L(y) = 0, an

integer t and a rational homomorphism ¦ : GL ’ GLt (C) such that the Galois group G of

L(y) = b is C t GL where the action of GL on C t by conjugation is given by ¦.

1. Write L as a least common left multiple of a set T = {T1 , . . . , Ts } of irreducible

operators (using, for example, the algorithms in the Appendix of [CS99]).

2. If L = L1 L0 then complete reducibility implies that L1 is equivalent to the least

common left multiple of some subset of T . Fix some subset of T and let L2 be the

least common left multiple of its elements. For this operator, apply Lemma 3.2.7.3 to

construct the set ML2 .

3. Let (L1 , S) ∈ ML2 . Lemma 3.2.4 implies that L1 (y) = b has a solution in C(x) if and

only if the equation

L2 (y) = S(b) (3.15)

has a solution y ∈ C(x). Apply Lemma 3.2.8 to equation (3.15) to determine the set

of (L1 , S) for which this equation has a rational solution.

4. Repeat steps 2. and 3. until one ¬nds an L2 of maximal order so that the set RL2 of

(L1 , S) ∈ ML2 for which the equation (3.15) has a rational solution is nonempty. In

this case, Proposition 3.2.1 implies that there exists a unique L1 such that (L1 , S) ∈

RL2 for some S.

5. We write L = L1 L0 and let t be the order of L0 . Find de¬ning equations of the Galois

group GL of L with respect to a basis of the solution space that includes a basis of

the solution space of L0 (y) = 0 (the results of [CS99] allow one to do this). In this

®

AB

basis, an automorphism σ ∈ G will have the form ° » , where A represents the

0C

26

C t (i.e., selecting A from σ)

action of σ on W = VL0 . Restriction to the space W

yields the desired rational map ¦ : GL ’ GLt (C) that gives the action of GL on C t in

Ct GL .

We make the following additional remarks:

1. The calculations of Example 3.2.2 can be viewed as an application of the above al-

gorithm. In that example, we have L = (D ’ 2x) —¦ (D ’ 2x), so that all ¬rst-order

left (resp., right) factors of L are equivalent to D ’ 2x. The set of ¬rst-order left fac-

L1,(c,d) = D ’ (2x ’ d

tors is c+dx ) : (c, d) = (0, 0) . The algorithm calls for deciding

whether L1,(c,d) (y) = b admits a k-rational solution for some suitable (c, d). A calcu-

lation using Lemma 3.2.4 as in Step 3 of the algorithm shows that the above problem

is equivalent to deciding whether y ’ 2xy = (c + dx) · b admits a k-rational solution

for some (c, d) = (0, 0). Lemma 3.2.8 can then be applied to solve that problem.

2. [CS99] presents an algorithm to compute KH /k, the Picard-Vessiot extension of L(y) =

0. This algorithm, together with Algorithm 1 above and Corollary 3.2.3, yields an

algorithm to compute KI /k, the Picard-Vessiot extension of L(y) = b.

Computing the group of L1 —¦ L2 , L1 , L2 completely

3.3

reducible

The problem of computing the group of L1 —¦L2 , L1 , L2 completely reducible, can be reduced

to that of computing the group of L(y) = b, L completely reducible. In [Ber90], D. Bertrand

accomplishes this in terms of D-modules. In [BS99], the process is made explicit in terms

of operators and systems, and a decision procedure is provided. We recapitulate the results

from [BS99] below.

First, consider the inhomogeneous ¬rst-order system

Y = AY + B, Y = (y1 , . . . , yn )T , A ∈ k n—n , B = (b1 , . . . , bn )T ∈ k n , (3.16)

where the yi are indeterminates. Let KH /k (resp., VH , GH ) be the Picard-Vessiot extension

(resp., the solution space; the group) of the associated homogeneous system Y = AY.

Before de¬ning the extension and the group of (3.16), we de¬ne a new homogeneous system

27

as follows: De¬ne a new variable yn+1 , and consider the following system of equations:

Y = AY + (b1 yn+1 , b2 yn+1 , . . . , bn yn+1 )T , yn+1 = 0.

˜

If we de¬ne Y = (y1 , . . . , yn , yn+1 )T , we obtain the following homogeneous ¬rst-order system:

®

AB

Y =° »Y .

˜ ˜ (3.17)

00

De¬ne the Picard-Vessiot extension KI (resp., the Galois group GI ) of (3.16) to be the

Picard-Vessiot extension (resp., the group) of (3.17).

Note that if Y = (y1 , . . . , yn ) ∈ VH , then (y1 , . . . , yn , 0) satis¬es (3.17). Thus, we may

write KH ⊆ KI . If · = (·1 , . . . , ·n , 1) is a solution of (3.17), then · = (·1 , . . . , ·n ) is a

˜

solution of (3.16). Any two solutions of (3.16) di¬er by a member of VH , so that the full

solution set of (3.16) is · + VH . Moreover, the full solution space of (3.17) over KI is spanned

by · and those solutions of the form (y1 , . . . , yn , 0), (y1 , . . . , yn ) ∈ VH . It follows that KI /k

is the minimal di¬erential ¬eld extension containing the full solution set of (3.16) and that

KI = KH ·1 , . . . , ·n .

We de¬ne equivalence for inhomogeneous systems as follows: We say that the systems

Y = A1 Y + B1 and Y = A2 Y + B2 are equivalent (over k) if they have the same dimen-

’ (k n , ’

sion n and there exist isomorphisms φ : (k n , and ψ : (k n+1 ,

A1 ) A2 ) A1 )

˜

(k n+1 , A2 ), where

®

˜

Ai Bi

Ai = ° »

˜

0 0

for i = 1, 2, such that ψ is identical to φ. We see that if Y = A1 Y + B1 and Y =

kn •0

A2 Y +B2 are equivalent systems, then a Picard-Vessiot extension associated with one system

is also a Picard-Vessiot extension for the other system and, moreover, that Y = A1 Y and

Y = A2 Y are equivalent.

We say that the inhomogeneous equation L(y) = b and the system Y = AY + B are

equivalent (over k) if the systems Y = AL Y +(0, . . . , 0, b)T and Y = AY +B are equivalent

(over k).

Given an inhomogeneous ¬rst-order system Y = AY +B. We may compute an equivalent

equation L(y) = b by the following method: Let E (resp., E — ) be the standard ordered basis

of k n (resp., of (k n )— ). Find a cyclic vector v of ((kn )— , —

A ), so that

— — n’1

Bv = v, A (v), . . . , ( A) (v)