<<

. 6
( 33 .)



>>

To prove one direction of the lemma, suppose L1 (f ) = b for some f ∈ k. If h = R(f ) ∈ k,
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)

<<

. 6
( 33 .)



>>