J. Symbolic Computation (1998) 11, 1–22

Computing Galois Groups of Completely Reducible Differential Equations

ELIE COMPOINT§^{†} AND MICHAEL F. SINGER^{⋆}^{‡}

§Mathématiques, Université de Paris VI, T. 46, Case 247, 4, Place Jussieu, 75 230 Paris Cédex 05 ⋆Department of Mathematics, North Carolina State University, Raleigh, NC 27695-8205

(Received April 25, 1997)

We give an algorithm to calculate a presentation of the Picard-Vessiot extension associated to a completely reducible linear differential equation (i.e., an equation whose Galois group is reductive). Using this, we show how to compute the Galois group of such an equation as well as properties of the Galois groups of general equations.

1. Introduction

At present we do not know a general algorithm that will compute the Galois group of a linear differential equation with coefficients in a differential field k, even when k = ℚ̄(x), where ℚ̄ is the algebraic closure of the rational numbers. In contrast, algorithms for calculating the Galois group of a polynomial with coefficients in ℚ or ℚ̄(x) have been known for a long time (Cohen, 1993; van der Waerden, 1953; Pohst and Zassenhaus, 1989). The key idea behind these methods is to represent the splitting field of a polynomial in terms of generators and relations. The Galois group is then the set of permutations of the generators that preserve the relations. In the differential case, the analogue of the splitting field is called the Picard-Vessiot extension and the Galois group is defined as the group of differential automorphisms leaving elements of the base field fixed. The obstruction to mimicking the ideas from the Galois theory of polynomials is that, at present, we do not know how to effectively present a general Picard-Vessiot extension in terms of generators and relations. In this paper, we will show that for differential equations whose Galois group is reductive, one can effectively present the corresponding Picard-Vessiot extension and from this presentation compute the Galois group.

In (Compoint, 1996a; Compoint, 1996b), the first author showed that if a Picard-Vessiot extension has a reductive unimodular Galois group then the relations defining this extension come from the invariants of the Galois group. To be more specific, let k be a differential field of characteristic zero with algebraically closed field C of constants and let Y′ = AY be a differential equation where A is an n × n matrix with entries in k. Let G ⊂ SL(n) be the Galois group and let its action on the polynomial ring C[Y_{1,1}, …, Y_{n,n}]

  † E-mail: compoint@riemann.math.jussieu.fr

‡ E-mail: singer@math.ncsu.edu . Research partially supported by NSF Grant CCR-93222422

0747–7171/90/000000 + 00 $03.00/0 \begin{matrix}c \\ ◯ \end{matrix} 1998 Academic Press Limited

be defined by letting each element of G act on the n×n matrix [Y_{i,j}] by multiplication on the left. Since G is reductive, the ring C[Y_{1,1}, …, Y_{n,n}]^{G} of invariants is finitely generated. Compoint showed that if this ring is generated by polynomials of degree at most m, then the Picard-Vessiot extension is the quotient field of the ring k[Y_{1,1}, …, Y_{n,n}]/I, where I is an ideal generated by polynomials of degree at most m as well. It is known that given m, one can calculate these generators directly from the equation Y′ = AY, without a priori knowledge of the Galois group (van Hoeij and Weil, 1996). Therefore the question of determining the Galois group of an equation Y′ = AY with reductive unimodular group is reduced to the question of finding a bound on the degrees of the generators of the ring of invariants. The main result of this paper is that there is an effective method to find such a bound.

The rest of the paper is organized as follows. In Section 2 we review some material concerning the relationship between connections, differential equations and D-modules, discuss the concept of completely reducible operators in these settings and prove some ancillary results concerning exponential extentions of differential fields. In Section 3, we show how to bound the degree of generators of the invariants of the Galois group of a completely reducible operator. In Section 4 we show how one can use these bounds together with the results of (Compoint, 1996a; Compoint, 1996b) to give an effective presentation of the Picard-Vessiot extension of an algebraic extension of C(x) associated to a completely reducible differential operator and show how this can be used to compute the Galois group of this extension. We also show how to apply this result to arbitrary operators to deduce properties (e.g. , connectedness) of their Galois groups. We have included an appendix where we give algorithms to factor linear operators over algebraic extensions of C(x) as well as algorithms to decide if operators over these fields are completely reducible.

We would like to thank Dimitri Chmelkine for Lemma 3.1 in Section 3.2.

All fields in this paper will be assumed to be of characteristic zero. We shall use the term computable field to denote a field in which the field operations are recursive functions and over which we can factor polynomials. We shall also assume that the reader is familiar with the basics of the Picard-Vessiot theory, (Kaplansky, 1976; Kolchin, 1976; Magid, 1994).

2. Connections, Equations and D-Modules

In this section we start by giving a quick review of the definitions and basic facts concerning these topics. We then characterize linear differential equations whose Galois groups are reductive groups and give procedures to determine if an equation has a reductive Galois group as well as constructions that will be used later in this paper. Throughout this section k is a differential field with algebraically closed field of constants C.

2.1. Connections

A connection is a finite dimensional k-space M with an operator ∇ : M → M satisfying

∇(u + v) = ∇(u) + ∇(v)
∇(fu) = f′u + f∇(u)

for all u, v ∈ M and f ∈ k (c.f., (Haefliger, 1987)). We shall refer to the k-dimension of M as the dimension of the connection. If e_{1}, …, e_{n} is a k-basis of M, we may write

∇e_{i} = − ∑_{j} a_{j,i}e_{j}  (2.1)

where A = (a_{i,j}) ∈ HOM_{k}(M, M). If u = ∑_{i} u_{i}e_{i}, then ∇(u) = ∑_{i}(u′_{i} − ∑_{j} a_{i,j}u_{j})e_{i}. Therefore, once a basis of M has been selected and the identification M ≃ k^{n} has been made, we have that u ∈ k^{n} satisfies u′ = Au if and only if ∇u = 0. Conversely, given a system Y′ = AY, A ∈ HOM(k^{n}, k^{n}) one can use equation 2.1 to define a connection ∇_{A} on k^{n}. A connection (N , ∇_{N}) is a subconnection of (M, ∇) if N ⊂ M and ∇_{N} = ∇|_{N}. Given a connection and a subconnection one can define a quotient connection and if (M_{1}, ∇_{1}) and (M_{2}, ∇_{2}) are two connections one can form the direct sum (M_{1} ⊕ M_{2}, ∇_{1} ⊕ ∇_{2}) and the tensor product (M_{1} ⊗ M_{2}, ∇_{1} ⊗ 1 + 1 ⊗ ∇_{2}) in the obvious ways. A morphism ϕ : (M_{1}, ∇_{1}) → (M_{2}, ∇_{2}) is a k-linear map ϕ : M_{1} → M_{2} such that ϕ ∘ ∇_{1} = ∇_{2} ∘ ϕ. If {e_{1}, …, e_{n}} is a basis of M_{1} (resp. {f_{1}, …, f_{m}} is a basis of M_{2}) and Y′ = A_{1}Y (resp. Y′ = A_{2}Y) is the equation associated with (M_{1}, ∇_{1}) (resp. (M_{2}, ∇_{2})) then U ∈ HOM_{k}(M_{1}, M_{2}) defines a morphism if and only if U′ = A_{2}U−UA_{1}. One can define a connection (HOM_{k}(M_{1}, M_{2}), ∇_{HOM}) by the equation ∇_{HOM}ϕ(u) = ∇_{2}(ϕ(u)) − ϕ(∇_{1}u). One sees that ϕ ∈ HOM_{k}(M_{1}, M_{2}) defines a morphism if and only if ∇_{HOM}ϕ = 0. When M_{2} = k and ∇_{2} is the trivial connection, then we say that (HOM_{k}(M_{1}, M_{2}), ∇_{HOM}) is the dual connection (M_{1}^{∗}, ∇_{1}^{∗}). The differential equation associated with (M_{1}^{∗}, ∇_{1}^{∗}) is Y′ = −A^{T} Y. If M_{1} = M_{2} and U defines an isomorphism, we then have

A_{2} = U′U^{−1} + UA_{1}U^{−1}  (2.2)

We therefore define the systems Y′ = A_{1}Y and Y′ = A_{2}Y to be equivalent if there exists a matrix U ∈ GL(n, k) such that equation 2.2 holds.

Let K be a Picard-Vessiot extension of k containing the full solution spaces V_{1} and V_{2} of Y′ = A_{1}Y and Y′ = A_{2}Y and let G = Gal(K/k) be the Galois group of K over k. The spaces V_{1} and V_{2} are G-modules. If they are isomorphic as G-modules, then there exist fundamental solution matrices† Z_{1} and Z_{2} of Y′ = A_{1}Y and Y′ = A_{2}Y respectively such that for each g ∈ G, there is a matrix [g] ∈ GL(n, C) such that g(Z_{1}) = Z_{1}[g] and g(Z_{2}) = Z_{2}[g]. Therefore the matrix U = Z_{1}Z_{2}^{−1} is left fixed by G and so must lie in GL(n, k). The matrix U then defines an isomorphism between (k^{n}, ∇_{A_{1}}) and (k^{n}, ∇_{A_{2}}). Conversely, if the two systems Y′ = A_{1}Y and Y′ = A_{2}Y are equivalent one sees that the map Z_{1} = UZ_{2} defines a G-isomorphism between the two solution spaces V_{1} and V_{2}. In fact, this argument shows that if Y′ = A_{1}Y and Y′ = A_{2}Y are equivalent differential systems and K is a Picard-Vessiot extension containing the full solution space of Y′ = A_{1}Y, then it will contain the full solution space of Y′ = A_{2}Y.

2.2. D-modules

Linear differential equations are frequently given by n^{th} order scalar equations L(y) = y^{(n)} + a_{n−1}y^{(n−1)} + … a_{0}y = 0, a_{i} ∈ k. It is useful to associate with such an equation the operator L = D^{n} + a_{n−1}D^{n−1} + … + a_{0} in the ring D = k[D] of linear differential operators (c.f., Singer (1996)). This ring is the ring of noncommutative polynomials in

† A fundamental solution matrix is a matrix whose columns form a basis of the solution space

D where D satisfies Df = fD + f′ for all f ∈ k. The ring D has a right and left division algorithm and one can calculate right and left least common multiples. A D-module is a finite dimensional k-space M on which D acts on the left. A connection (M, ∇) can be considered a D-module by defining Du = ∇u for u ∈ M. Conversely, to any Dmodule M one can associate the connection (M, ∇) where ∇u = Du. Given an operator L = D^{n} + a_{n−1}D^{n−1} + … + a_{0} ∈ D one can associate to it the system Y′ = A_{L}Y where

A_{L} = ( \begin{matrix}0 & 1 & 0 & … & 0 \\ 0 & 0 & 1 & … & 0 \\ … & … & … & … & … \\ −a_{0} & −a_{1} & … & … & −a_{n−1} \end{matrix} )  (2.3)

We denote the associated connection (k^{n}, ∇_{L}). One can easily check that this D-module is isomorphic to (D/D·L)^{∗}. It is well known (Katz, 1987) that if k contains a non-constant element then any connection (M, ∇) is cyclic, that is, there exists an element u ∈ M such that the elements u, ∇u, ∇^{2}u, …, ∇^{n−1}u form a k-basis of M. Applying this fact to the dual (M^{∗}, ∇^{∗}), we see that with respect to a basis of the form v, ∇^{∗}v, …, (∇^{∗})^{n−1}v, the connection will have a matrix of the form

( \begin{matrix}0 & 0 & 0 & … & −a_{0} \\ 1 & 0 & 0 & … & −a_{1} \\ 0 & 1 & 0 & … & −a_{2} \\ … & … & … & … & … \\ 0 & 0 & … & 1 & −a_{n−1} \end{matrix} )

Therefore (M^{∗∗}, ∇^{∗∗}) ≃ (M, ∇) is associated with the equation Y′ = −B^{T} Y where −B^{T} = A_{L} for the operator L = D^{n} +a_{n−1}D^{n−1} +…+a_{0}. Let Y′ = AY be a differential equation and (k^{n}, ∇_{A}) the associated connection. We shall refer to an operator L so that (k^{n}, ∇_{A}) ≃ (k^{n}, ∇_{L}) as an operator equivalent to the system Y′ = AY or equivalent to the connection ∇_{A}.

2.3. Completely Reducible Operators

An operator L ∈ D is said to be reducible over k if it can be written as the product L = L_{1}L_{2} of operators of smaller order. The following gives several equivalent properties. We will call an equation Y′ = AY (or its connection) reducible over k or simply reducible, if k is clear from the context, if any of these equivalent conditions holds. An equation that is not reducible is said to be irreducible. Recall that a module is reducible if it has a proper, nonzero submodule.

Proposition 2.1. Let Y′ = AY be a linear differential equation with coefficients in k and let K be its Picard-Vessiot extension with Galois group G. Let L be an operator equivalent to this system. The following are equivalent:

1 The connection (k^{n}, ∇_{A}) contains a proper nonzero subconnection.

2 The D-module M_{A} is reducible.

3 Y′ = AY is equivalent to a system Y′ = BY where B has the form

B = ( \begin{matrix}B_{1} & 0 \\ B_{2} & B_{3} \end{matrix} )

4 The D-module D/DL is reducible.

5 L is a reducible over k.

6 The solution space V of Y′ = AY in K is a reducible G-module.

Proof. Since K contains the full solution space of Y′ = AY, it will contain the full solution space of any equivalent operator. Furthermore, these spaces will be G−isomorphic. The equivalence of 5. and 6. is given by Corollary 2.3 of (Singer, 1996). The equivalence of 3. and 6. is given in (Grigoriev, 1990). Since D/DL is the dual of M_{A}, the equivalence of 2. and 4. is clear. The equivalence of 1., 2. and 3 is by definition. □

An operator L is said to be completely reducible if it is the least common left multiple of irreducible operators. A module is completely reducible if it is the direct sum of irreducible modules. Finally, a linear algebraic group G is reductive if its unipotent radical is trivial (see (Humphreys, 1975) for the definition of this and related notions). The following proposition relates these notions.

Proposition 2.2. Let Y′ = AY be a linear differential equation with coefficients in k and let K be its Picard-Vessiot extension with Galois group G. Let L be an operator equivalent to this system. The following are equivalent:

1 The connection (k^{n}, ∇_{A}) is the direct sum of irreducible subconnections.

2 The D-module M_{A} is completely reducible.

3 Y′ = AY is equivalent to a system Y′ = BY where B has the form

B = ( \begin{matrix}B_{1} & 0 & … & 0 \\ 0 & B_{2} & … & 0 \\ 0 & 0 & … & B_{t} \end{matrix} )

and where each equation Y′ = B_{i}Y is irreducible over k. 4 The D-module D/DL is completely reducible. 5 L is a completely reducible over k. 6 The solution space V of Y′ = AY in K is a completely reducible G-module. 7 G is a reductive group.

Proof. The equivalence of 5., 6. and 7. is given by Lemma 2.13 of (Singer, 1996). The equivalence of 1., 2. and 3. is by definition. A module is completely reducible if and only if its dual is and so 2. is equivalent to 4. We now show that 4. is equivalent to 5.

Assume 4. holds and write D/DL = M_{1} ⊕ … ⊕ M_{t} where each M_{i} is irreducible. Let ¯1 be the coset of 1 ∈ D. We may write ¯1 = v_{1} + … + v_{t} where each v_{i} ∈ M_{i}. Let L_{i} ∈ D be the monic operator of smallest degree such that L_{i}(v_{i}) = 0. Since each M_{i} is irreducible, each L_{i} is irreducible. Furthermore, 0 = L(¯1) = L(v_{1}) + … + L(v_{t}) so each L(v_{i}) = 0. Therefore each L_{i} divides L on the right. If each L_{i} divides an operator L_{0} on the right, then L_{0}(¯1) = L_{0}(v_{1}) + … + L_{0}(v_{t}) = 0 + … + 0 = 0. Therefore, L divides L_{0} on the right and so L is the least common left multiple of th L_{i}.

Assume 5. holds and let L be the least common multiple of the distinct monic irreducible operators L_{1}, …, L_{t}. One easily sees that this implies that the map ϕ : D → D/DL_{1} ⊕ … ⊕ D/DL_{t} taking L ∈ D to the sum of cosets has kernel DL. Since the L_{i} are distinct, the sum of their orders equals the order of L. Therefore the k-dimensions of D/DL and D/DL_{1} ⊕ … ⊕ D/DL_{t} are the same and so these modules are isomorphic. □

In (Singer, 1996), an algorithm is described that decides if a given operator L ∈ k[D] is completely reducible when k = C(x), C a computable algebraically closed field. This algorithm is extended in Section 5.2 to fields k that are algebraic extensions of C(x).

Finally, let k_{2} be an algebraic extension of k_{1} both fields having the same algebraically closed field of constants and let L ∈ k_{1}[D]. We then have that L_{1} is completely reducible over k_{1} if and only if it is completely reducible over k_{2}. This is because the Galois groups of L over k_{1} and k_{2} share a common connected component and a group is reductive if and only if its identity component is reductive.

2.4. Decomposition Fields

Let k be a differential field with algebraically closed field of constants C. A connection (M, ∇) defined over k is said to be absolutely irreducible over k if for any algebraic extension K of k, the connection (M⊗K, ∇) is irreducible over K. Let M be a completely reducible k[D]-module. We say that k_{1} ⊃ k is a decomposition field for M if

1 k_{1} is an algebraic extension of k, and

2 M⊗k_{1} = M_{1} ⊕…⊕M_{t} where each M_{i} is an absolutely irreducible k_{1}[D]-module.

In terms of equations, we can state this as follows. An algebraic extension k_{1} of k is a decomposition field of Y′ = AY if this equation is equivalent (over k_{1}) to an equation in block diagonal form where the equation corresponding to each block remains irreducible over any algebraic extension of k_{1}. Clearly, the algebraic closure of k is a decomposition field for any completely reducible equation.

Now assume that for any equation Y′ = AY over k one can effectively find an algebraic extension k_{1} of k and elements Y_{1}, …, Y_{r} ∈ k_{1}^{n} such that any solution of Y′ = AY algebraic over k is a C-linear combination of the Y_{i}. Examples of such fields are C(x), where C is a computable algebraically closed field, any finitely generated algebraic or elementary extension of C(x), and certain liouvillian extensions of C(x) (Singer, 1979; Singer, 1991). The following result shows that for such fields one can compute a decomposition field.

Proposition 2.3. Let (M, ∇) be a completely reducible connection defined over the field k and let k̄ be the algebraic closure of k. Let (HOM_{k}(M, M), ∇_{HOM}) be the connection associated with the endomorphisms of M.

1 Let k_{1} ⊂ k̄ be a computable differential field containing k. If we can effectively find a C-basis of all elements U of HOM_{k_{1}}(M ⊗ k_{1}, M ⊗ k_{1}) such that ∇_{HOM}(U) = 0, then we can effectively decompose (M ⊗ k_{1}, ∇) as a sum of irreducible connections over k_{1}. If k_{1} is furthermore a decomposition field of (M, ∇), then we can effectively decompose (M ⊗ k_{1}, ∇) as a sum of absolutely irreducible connections.

2 Let k_{1} be an algebraic extension of k such that any U ∈ HOM_{k}(M, M) ⊗ k̄ with ∇_{HOM}(U) = 0 is already in HOM_{k}(M, M) ⊗ k_{1}, then k_{1} is a decomposition field of (M, ∇).

In more pedestrian terms, Proposition 2.3 says the following. If Y′ = AY is the equation associated with the connection and if we can find all solutions in k_{1} of U′ = AU − UA, then 1. says that we can find an equation equivalent to Y′ = AY whose matrix is in block diagonal form where the blocks along the diagonal correspond to irreducible equations. Furthermore, if k_{1} is a decomposition field, we can do this in such a way that the equations corresponding to the blocks are absolutely irreducible. Part 2. says that if k_{1} is an algebraic extension of k such that k_{1} contains the entries of any matrix U ∈ HOM(k̄^{n}, k̄^{n}) satisfying U′ = AU − UA, then k_{1} is a decomposition field for Y′ = AY. Therefore to construct a decomposition field, we need only find a field containing the entries of all algebraic solutions of U′ = AU − UA.

Proof. 1. As we have already noted at the end of the last section, (M ⊗ k_{1}, ∇) remains completely reducible over k_{1}. Select a k_{1}-basis of (M ⊗ k_{1}, ∇) and let Y′ = AY be the associated equation with respect to this basis. Let U_{1}, …, U_{t} be a basis of the solution space of ∇_{HOM}(U) = U′ − (AU − UA) = 0. Note that the solution space of this latter equation forms a matrix algebra that contains the identity. Fix an integer s. Let {a_{i,j}}_{1≤i≤s}^{1≤j≤t} be a set of indeterminates and let P_{i} = ∑_{j} a_{i,j}U_{j} for i = 1, …, s. Consider the following conditions:

1 For all pairs i ≠ l, 1 ≤ i, l ≤ s, P_{i}P_{l} = P_{l}P_{i} = 0.

2 For all i, P_{i}^{2} = P_{i}.

3 For all i, P_{i} ≠ 0.

Expanding these equalities and inequalities in terms of a C-basis of k_{1} we see that there is a C-constructible set T_{s} ⊂ C^{ts} such that (a_{i,j}) ∈ T_{s} if and only if the above conditions hold. These conditions are equivalent to the statement that the P_{i} are disjoint projections in the category of connections. Note that when s = 1, the identity matrix P_{1} = I satisfies the above conditions. Therefore T_{1} is not empty. Since M is finite dimensional we have that for large s, the T_{s} are empty. Let m be the smallest integer such that T_{m+1} is empty. Then for (a_{i,j}) ∈ T_{m}, the projections P_{i} form a maximal set of disjoint nonzero projections. Therefore the image of each of these must be an irreducible subconnection. Again by maximality, the sum of these images must be the entire space M. If we therefore take a maximal linearly independent set of columns from the P_{i}, we will have a basis of M with respect to which the connection is block diagonal with irreducible blocks.

If k_{1} is furthermore a decomposition field, then there will be no further projections P_{i} in an algebraic extension of k_{1}. Therefore, the images of the P_{i} will be absolutely irreducible.

2. For k_{1} as described, the above procedure will produce a decomposition into irreducible subconnections. If one of these subconnections is not absolutely irreducible, then the associated projection could be written as a sum of projections in some algebraic extension k_{2}. By assumption, these new projections must already be defined over k_{1}, contradicting the irreducibility of the subconnection. □

2.5. Exponential Extension Fields

Let k ⊂ E be differential fields and 0 ≠ u ∈ E. We say that u is exponential over k if u′/u ∈ k. We say that a differential field E is an exponential extension of a differential field k if they have a common field of constants and E = k(u_{1}, …, u_{m}) where each u_{i} is exponential over k. If the constants are algebraically closed, then one sees that E is a Picard-Vessiot extension of k whose Galois group is a finite extension of a torus. We shall show that, given an algebraic extension k of C(x), C algebraically closed, and elements v_{1}, …, v_{m} ∈ k, one can explicitly describe the structure of the exponential extension E that is the Picard-Vessiot extension for the equation Y′ = diag(v_{1}, …, v_{m})Y. We recall the following weak version of the Kolchin-Ostrowski Theorem (Kolchin, 1968): Let k ⊂ E be differential fields with the same constants and let u_{1}, …, u_{n} be elements of E exponential over k. If u_{1}, …, u_{n} are algebraically dependent over k then there exist integers, e_{1}, …, e_{n}, not all zero, such that ∏ u_{i}^{e_{i}} ∈ k.

Proposition 2.4. Let E = k(u_{1}, …, u_{m}) be an exponential extension of k, a finitely generated algebraic extension of C(x). Assume that one is given elements v_{1}, …, v_{m} ∈ k such that u′_{i}/u_{i} = v_{i}. Then one can effectively find a (possibly empty) set of elements S = {u_{i_{1}}, …, u_{i_{r}}} ⊂ {u_{1}, …, u_{m}} and an integer M such that

1 {u_{i_{1}}, …, u_{i_{r}}} is a transcendence basis of E over k.

2 If k_{1} is the algebraic closure of k in E, then [k_{1} : k] ≤ M.

Furthermore, for each j ∈ {1, …, m} one can effectively find an element f_{j} ∈ k and integers n_{j}, n_{i,j}, n_{j} ≠ 0 such that

u_{j}^{n_{j}} = f_{j} ∏_{t=1}^{r} u_{i_{t}}^{n_{t,j}}  (2.4)

if S is nonempty, or u_{j}^{n_{j}} = f_{j} if S is empty.

Proof. We shall proceed by induction on m. We may assume that u_{1}, …, u_{s} form a transcendence basis of K = k(u_{1}, …, u_{m−1}) over k. Given v ∈ k and u ∈ E with u′ = vu we will first show how to decide if u is algebraic over K and if it is find integers n, n_{j}, n ≠ 0 and an element f ∈ k such that

u^{n} = f ∏_{j=1}^{s} u_{j}^{n_{j}} .

The Kolchin-Ostrowski Theorem implies that such integers will exist if and only if u is algebraic over K. This is furthermore equivalent to deciding if there exist integers n, n_{j}, n ≠ 0 such that

n\frac{u′}{u} − ∑_{j=1}^{s} n_{j} \frac{u′_{j}}{u_{j}} = nv − ∑_{j=1}^{s} n_{j}v_{j}  (2.5)

is the logarithmic derivative of an element of k. Let C be the curve associated with the function field k and define the following divisors:

D = ∑_{P ∈C} res_{P} (vdx) P
D_{i} = ∑_{P ∈C} res_{P} (v_{i}dx) P

One sees that if 2.5 is the logarithmic derivative of a function f ∈ k then nD + ∑ n_{i}D_{i} is the divisor of a function in k.

Conversely, the set of (n, n_{1}, …, n_{s}) ∈ ℤ^{s+1} such that nD+∑ n_{i}D_{i} is the divisor of an element of k forms a ℤ-module T . In (Bertrand, 1995; Masser, 1988) techniques are given to find a set of generators of T and therefore we can find a basis {(e_{i}, e_{i,1}, …, e_{i,s})}_{i=1}^{l} of this free module. Furthermore, for each i one can find an element f_{i} ∈ k such that e_{i}D + ∑ e_{i,j}D_{j} is the divisor of f_{i}, (Baldassarri and Dwork, 1979; Coates, 1970; Trager, 1984). Each of the differential forms

ω_{i} = (\frac{f′_{i}}{f_{i}} − e_{i}v − ∑_{j} e_{i,j}v_{j})dx

is a holomorphic 1-form. We claim that 2.5 is the logarithmic derivative of an element in k for some choice of n, n_{i}, n ≠ 0 if and only if the ω_{i} are linearly dependent over ℤ (this can also be decided using methods of (Coates, 1970; Trager, 1984)). If ∑_{j} N_{j}ω_{j} = 0, then

\frac{(∏ f_{j}^{N_{j}})′}{∏ f_{j}^{N_{j}}} = (∑_{j} N_{j}e_{j})v + ∑_{i}(∑_{j} N_{j}e_{i,j})v_{i}

Note that if ∑_{j} N_{j}e_{j} = 0, then for each i, ∑_{j} N_{j}e_{i,j} = 0 or else the u_{1}, …, u_{s} would be algebraically dependent. Therefore ∑_{j} N_{j}e_{j} ≠ 0, since the (e_{i}, e_{i,1}, …, e_{i,s}) are independent.

Now assume that

\frac{f′}{f} = nv + ∑_{j=1}^{s} n_{j}v_{j}

Then (n, n_{1}, …, n_{s}) ∈ T so there exist N_{i} ∈ ℤ such that

(n, n_{1}, …, n_{s}) = ∑_{i} N_{i}(e_{i}, e_{i,1}, …, e_{i,s}) .

This implies that

∑_{i} N_{i}ω_{i} = ∑_{i} N_{i}ω_{i} + (\frac{f′}{f} − (nv + ∑_{j=1}^{s} n_{j}v_{j})dx

= ((∑_{i} N_{i} \frac{f′_{i}}{f_{i}}) + \frac{f′}{f})dx

= \frac{d(f ∏_{i} f_{i}^{N_{i}})}{f ∏_{i} f_{i}^{N_{i}}}

If d(f ∏_{i} f_{i}^{N_{i}}) ≠ 0 this last expression is a differential with simple poles. Since ∑_{i} N_{i}ω_{i} is holomorphic, we must have d(f ∏_{i} f_{i}^{N_{i}}) = ∑_{i} N_{i}ω_{i} = 0.

Therefore we can decide if u and the u_{i} are algebraically dependent and if so find integers n, n_{j}, n ≠ 0 and an element f ∈ k such that

u^{n} = f ∏_{t=1}^{s} u_{j}^{n_{j}} .

If the degree of the algebraic closure of k in k(u_{1}, …, u_{m−1}) is bounded by M_{1}, the degree of the algebraic closure k_{1} of k in E is bounded by M = nM_{1} □ Proposition 2.5. Using the notation of Proposition 2.4, the map

η : (t_{1}, …, t_{r}) ↦ (∏_{l=1}^{r} tl^{\frac{Nn_{l,1}}{n_{1}}} , ∏_{l=1}^{r} tl^{\frac{Nn_{l,2}}{n_{2}}} , …, ∏_{l=1}^{r} tl^{\frac{Nn_{l,m}}{nm}})  (2.6)

where N = LCM(n_{1}, …, n_{m}) is a surjective homomorphism of (C^{∗})^{r} onto the connected component Gal(E/k)^{o} of the Galois group of E over k. This homomorphism has finite kernel.

Proof. We first note that for j ∈ {i_{1}, …, i_{r}} the relation 2.4 is precisely u_{j}^{n_{j}} = u_{j}^{n_{j}} since the u_{j} with j ∈ {i_{1}, …, i_{r}} are algebraically independent. Therefore for i_{s} ∈ {i_{1}, …, i_{r}}, the i_{s}^{th} entry on the right hand side of 2.6 is just t_{i_{s}}^{N}. We identify the Galois group G of E over k with a closed subgroup of the group of diagonal matrices diag(a_{1}, … a_{m}) in GL(m, C). Since the u_{i} satisfy the relations 2.4, we have that an element (a_{1}, …, a_{m}) ∈ Gal(E/k) satisfies

a_{j}^{n_{j}} = ∏_{t=1}^{r} a_{i_{t}}^{n_{t,j}}

These equations define a subgroup H of the diagonal group and using the observation at the beginning of this proof we see that this group has dimension r. Since E has transcendence degree r over k the connected component of the Galois group has dimension r. Therefore Gal(E/k)^{o} = H^{o}. The map 2.6 defines a homomorphism of (C^{∗})^{r} into H as well and again, by dimension considerations, we see that the image of 2.6 must be H^{o}.

Comparing dimensions we see that the kernel has finite dimension. □

3. Invariant Theory

In the Introduction, we stated that to solve the problem of finding a presentation of the Picard-Vessiot extension of a linear differential equation Y′ = AY with reductive Galois group G, it is sufficient to find a bound for the degree of generators for the ring of polynomial invariants corresponding to the action of G on the n-fold sum of the solution space of Y′ = AY. In this section we will show how this bound may be calculated directly from Y′ = AY without a priori knowledge of G.

We begin by reviewing some facts from the constructive invariant theory of reductive groups, (Kempf, 1987). Let G be a reductive group defined over an algebraically closed field C acting faithfully on a finite dimensional vector space V. The group G then acts on the coordinate ring C[V]. Its ring of invariants C[V]^{G} is finitely generated and we denote by N_{G,V} a bound on the degree of a set of generators of this ring. Such a bound has been calculated in several cases:

1 If G is a finite group then E. Noether showed (Noether, 1916; Sturmfels, 1993) that,

independent of V, N_{G,V} = |G|. 2 If G is a torus, several authors (Kempf, 1987; Sturmfels, 1991; Wehlau, 1993) have

given expressions for N_{G,V}. We may identify G with an r-fold product (C^{∗})^{r}. Let χ be a weight of G acting on V. Then χ(t_{1}, …, t_{r}) = ∏_{i=1}^{r} t_{i}^{m_{i}} for some integers m_{i}. We define ||χ|| = max |m_{i}|, and let t = max ||χ|| where the χ run through all weights of G on V. Wehlau, for example, showed that N_{G,V} = (2t)^{2r−1} as well as N_{G,V} = (n − r − 1)r!vol(C), where n is the dimension of V and vol(C) is the volume of the convex hull of the exponents of the weights of G on V.

3 If G is a connected semisimple group, Popov showed in (Popov, 1981) that

N_{G,V} = nC(\frac{2^{r+s}n^{s+1}(n − 1)^{s−r}t^{r}(s + 1)!}{3^{s}((\frac{s−r}{2} )!)^{2}})

where C(M) denotes the least common multiple of all positive integers less than or equal to M, n = dim(V), s = dim(G), r = rank(G) and t is defined as above for a maximal torus T_{max} of G.

Hiss (Hiss, 1996) has given expressions for N_{G,V} for any connected reductive group but for our purposes it will be easier to deal with semisimple groups and tori separately.

To deal with reductive groups we will need to glue these results together. We will use the following result of Kempf (Kempf, 1987). Let G_{2} < G_{1} be a normal subgroup of the reductive group G_{1} and let V be a G_{1}-module. Since G_{2} is normal in G_{1} we have that G_{1} acts on the ring k[V]^{G_{2}}. Let W = k[V]^{G_{2}} ∩ k[V]_{1≤i≤N_{G_{2},V}} where k[V]_{1≤i≤N_{G_{2},V}} denotes the sum of homogeneous terms of degree between 1 and N_{G_{2},V}. Kempf shows that

N_{G_{1},V} = N_{G_{1}/G_{2},W} · N_{G_{2},V} .

An arbitary reductive group G has a tower of normal subroups (e) < T < G^{o} < G where G^{o} is the component of the identity in G and T is the component of the identity of the center of G^{o}. It is known that T is furthermore a torus and that G^{o}/T is semisimple. Therefore to find N_{G,V} it will be sufficient to

1 Calculate T together with its weights on V.

2 Bound N_{G^{o}/T,W}, where W = k[V]^{T} ∩ k[V]_{1≤i≤N_{T,V}}

3 Bound the order of G/G^{o}.

We will deal with each of these problems separately in the next three subsections. In what follows we will assume that k is a finitely generated algebraic extension of C(x) where C is a computable algebraically closed field.

3.1. T

Let Y′ = AY be a completely reducible differential equation with coefficients in k and let k_{0} be a decomposition field for Y′ = AY. Proposition 2.3 says that we can effectively construct such a field. Let K be the Picard-Vessiot extension of k_{0} corresponding to Y′ = AY and let G = Gal(K/k_{0}) be the Galois group of K over k_{0}. Since k_{0} is an algebraic extension of k the component of the identity of G is the same as the component of the identity of the Galois group of Y′ = AY over k. Over k_{0}, Y′ = AY is equivalent to a block diagonal equation Y′ = diag(A_{1}, …, A_{m}) where each equation Y′ = A_{i}Y is absolutely irreducible. In particular, each Y′ = A_{i}Y is irreducible over the fixed field of G^{o}. Therefore Schur’s Lemma implies that the center of G^{o} acts via scalar multiplication on the solution space of each Y′ = A_{i}Y.

Proposition 3.1. Let k_{0} be a differential field with algebraically closed field of constants and let Y′ = diag(A_{1}, …, A_{m})Y be a block diagonal differential equation with A_{i} ∈ HOM(k_{0}^{d_{i}}, k_{0}^{d_{i}}) where the equations Y′ = A_{i}Y are absolutely irreducible. Let K be the Picard-Vessiot extension of k_{0} corresponding to Y′ = AY and let G = Gal(K/k_{0}) be its Galois group. Let E = k_{0}(u_{1}, …, u_{m}) be the exponential extension of k_{0} where u′_{i} = tr(A_{i})u_{i} for i = 1, …, m and assume that Gal(E/k_{0}) has dimension r. If

η : (t_{1}, …, t_{r}) ↦ (χ_{1}(t_{1}, …, t_{r}), …, χ_{m}(t_{1}, …, t_{r}))

is a homomorphism of (C^{∗})^{r} onto the component of the identity of Gal(E/k_{0}), then

ϕ : (t_{1}, …, t_{r}) ↦ diag(\overbrace{χ1^{\frac{N}{d_{1}}} , …, χ1^{\frac{N}{d_{1}}}}^{d_{1}}, …, \overbrace{χm^{\frac{N}{dm}} , …, χm^{\frac{N}{dm}}}^{d_{m}})

where N = lcm(d_{1}, …, d_{m}), is a homomorphism of (C^{∗})^{r} onto T, the component of the identity of the center of G^{o}.

Proof. The remarks preceeding this proposition imply that T is a subgroup of

H = \{diag(\overbrace{a_{1}, …, a_{1}}^{d_{1}}, …, \overbrace{a_{m}, …, a_{m}}^{d_{m}}) | a_{i} ∈ C^{∗}\}

Since E is a Picard-Vessiot extension of k contained in K, the component G^{o} of the identity of the Galois group G leaves E invariant. This induces a surjective homomorphism ψ of G^{o} onto Gal(E/k_{0})^{o}. Explicitly, this map is given by

ψ(diag(g_{1}, …, g_{m})) = (det(g_{1}), …, det(g_{m})) .

Writing G^{o} = (G^{o}, G^{o}) · Z(G^{o}) where Z(G^{o}) is the center of G^{o} (Humphreys (1975), page 168) we see that (G^{o}, G^{o}) lies in the kernel of ψ. Therefore, ψ maps T onto the component of the identity of Gal(E/k_{o}). One sees that the kernel of ψ in T is finite so T has dimension r. Note that

ψ(diag(a_{1}, …, a_{1}, …, a_{m}, …, a_{m})) = (a_{1}^{d_{1}}, …, a_{m}^{d_{m}})

so we have ψ ∘ ϕ = η^{N}. Therefore, the image of ϕ is a connected group of dimension r that is mapped by ψ onto Gal(E/k_{0})^{o}. Therefore this image must coincide with T. □

We are now able to show how to calculate the action of T on the solution space of Y′ = AY. First calculate a decomposition field k_{0} as in Proposition 2.3. We then calculate the map η as in Proposition 2.5. Finally, Proposition 3.1 gives us the characters of the action of T on the solution space of Y′ = AY. As noted in the introduction to this section, this allows us to bound the degrees of generators for the invariants.

3.2. G^{o}/T

We shall use Popov’s formula to bound N_{G^{o}/T,W}. In practice, once the dimension of W is known we know that there are at most a finite number of semisimple groups having faithful representations of that dimension. For each of these groups we can calculate these representations and bound t as well as calculating the dimension and ranks of these groups.

Another approach is to give a priori bounds for the elements appearing in Popov’s formula. Let n = dim W. The dimension of the semisimple group G^{o}/T is then at most n^{2} − 1 and its rank is at most n − 1. The following lemma gives a bound for t.

Lemma 3.1. Let H be a connected semisimple group with maximal torus T_{max} and W an H-module of dimension n. We can fix an isomorphism T_{max} ≃ (C^{∗})^{r} such that for any weight χ(t_{1}, …, t_{r}) = ∏_{i} t_{i}^{n_{i}} of T_{max} on W, we have that each |n_{i}| ≤ n.

Proof. (c.f., Onishchik and Vinberg (1990), Ch. 4.6) Let 𝔥 be the Lie algebra of H and let 𝔥 = 𝔱 ⊕ ⨁ 𝔤_{α} be the root decomposition of 𝔥. For each positive root α we may select e_{α} ∈ 𝔤_{α}, e_{−α} ∈ 𝔤_{−α} such that h_{α} = [e_{α}, e_{−α}], e_{α}, e_{−α} span a Lie subalgebra 𝔤^{(α)} isomorphic to 𝔰l(2). Since SL(2) is simply connected, there exists a homomorphism ϕ_{α} : SL(2) → H such that dϕ_{α} maps the Lie algebra of SL(2) isomorphically onto 𝔤^{(α)}. Let T_{α} ≃ C^{∗} be the maximal torus of ϕ_{α}(SL(2)). If {h_{α_{1}}, …, h_{α_{r}}} are a basis of 𝔱. then T_{α_{1}} × … × T_{α_{r}} = T_{max}. We shall use the isomorphism ϕ_{α_{1}} × … × ϕ_{α_{r}} as our fixed isomorphism of (C^{∗})^{r} onto T_{max}. If we restrict χ to T_{α_{i}} ⊂ ϕ_{α_{i}}(SL(2)), we get the weight t_{i}^{n_{i}} of the action of the maximal torus T_{α_{i}} ⊂ ϕ_{α_{i}}(SL(2)) on W. As an SL(2)-module, W is the direct sum of irreducible SL(2)-modules. The weights t^{m} of an irreducible SL(2)-module of dimension d satisfy |m| ≤ d. Therefore we have that each |n_{i}| ≤ n.□

3.3. G/G^{o}

We shall show how one can bound the order of G/G^{o}. We begin with a group theoretic lemma.

Lemma 3.2. Let G be a connected reductive linear algebraic group defined over an algebraically closed field C. Let V be an irreducible G-module of dimension n and H a subgroup of SL(V) such that H normalizes G. Then |H/H ∩ G| < n · n!.

Proof. Let us first assume that G is semisimple. We shall show that |H · G/G| = |H/H ∩ G| < n · n!. The action of H · G on G by conjugation induces a homomorphism Φ : H · G/G → Aut(G)/Inn(G) where Aut(G) is the group of automorphisms of G and Inn(G) is the subgroup of inner automorphisms. The kernel Ker(Φ) of Φ consists of those cosets h · G where, for some g ∈ G, hg commutes with all elements of G. Since V is irreducible, Schur’s Lemma implies that hg is a constant matrix. Since H ⊂ SL(V) and G = (G, G) ⊂ SL(V), we have that the coset h · G has a representative that is a constant matrix in SL(V). Therefore |Ker(Φ)| ≤ n. Since G is semisimple, Aut(G) is the product of Inn(G) and the automorphism group of its Dynkin diagram ((Humphreys, 1975), p. 166). The automorphism group of the Dynkin diagram forms a subgroup of the symmetric group on r objects where r is the rank of G. Therefore |Aut(G)/Inn(G)| ≤ r! < n! and so |H · G/G| = |H/H ∩ G| < n · n!.

Now assume that G is an arbitrary connected reductive group. In this case we can write G = G′ · Z(G) where G′ = (G, G). Since V is irreducible, Z(G) consists of constant matrices. Therefore V is an irreducible G′-module. Furthermore H normalizes G′. Since |H/H ∩ G| ≤ |H/H ∩ G′|, the conclusion of the lemma follows from the result of the previous paragraph. □

Before continuing, we note that an equation Y′ = AY with coefficents in k has a Galois group over k that is conjugate to a unimodular group if and only if there exists a non-zero element u ∈ k such that u′ = tr(A)u. This follows from the facts that Y′ = AY has such a group if and only if it has a fundamental solution matrix Z with det(Z) ∈ k and that det(Z) satisfies det(Z)′ = tr(A)det(Z).

Let Y′ = AY, A ∈ HOM_{k}(k^{n}, k^{n}) be a completely reducible equation and let k_{0} be a decomposition field for this equation. Proposition 2.3 implies that we can find such a field when k is algebraic over C(x). Over k_{0} we may assume that A = diag(A_{1}, … A_{m}) where each A_{i} corresponds to an absolutely irreducible equation. For i = 1, …, m let u′_{i} = tr(A_{i})u_{i} and let E = k_{0}(u_{1}, …, u_{m}). Proposition 2.4 implies that one can explicitly bound [k_{1} : k_{0}], where k_{1} is the algebraic closure of k_{0} in E and so bound [k_{1} : k].

Proposition 3.2. Let Y′ = AY, k_{0}, E, and k_{1} as above. If G is the Galois group of Y′ = AY over k, then

|G/G^{o}| < [k_{1} : k]n^{n} · n!

Proof. Let K be the Picard-Vessiot extension of Y′ = AY over k_{0} and let G̃ be the Galois group of K over k_{0}. We shall first show that

|G̃/G̃^{o}| < [k_{1} : k_{0}]n^{n} · n!

Since K will contain a full set of solutions of each Y′ = A_{i}Y, it will contain the determinant of a fundamental solution matrix of each of these equations. We can therefore assume that E ⊂ K. Note that

|G̃/G̃^{o}| ≤ |Gal(E/k_{0})/Gal(E/k_{0})^{o}| · |Gal(K/E)/Gal(K/E)^{o}| .

This follows from the fact that the index of the component of the identity in a Galois group equals the degree of the maximal algebraic extension of the ground field. By definition, |Gal(E/k_{0})/Gal(E/k_{0})^{o}| = [k_{1} : k_{0}], so it remains to prove that

|Gal(K/E)/Gal(K/E)^{o}| < n^{n} · n! .

To do this we will describe the group Gal(K/E)^{o} and its action on the solution space of Y′ = AY in greater detail.

Let V = V_{1} ⊕ … ⊕ V_{m} be the solution space of Y′ = AY where each V_{i} corresponds to the solution space of Y′ = A_{i}Y. Let n_{i} be the dimension of V_{i}. Each V_{i} is an irreducible G̃^{0}-module. The group G̃^{0} can be written as (G̃^{o}, G̃^{o}) · Z where Z is the center of G̃^{o}. Schur’s Lemma implies that on each V_{i}, Z acts as scalar multiplication. Therefore each V_{i} is an irreducible (G̃^{o}, G̃^{o})-module. Note that u_{i} is the determinant of a fundamental solution matrix of Y′ = A_{i}Y. Since (G̃^{o}, G̃^{o}) must be unimodular on each V_{i}, we have that (G̃^{o}, G̃^{o}) leaves each u_{i} fixed and so is a subset of Gal(K/E). Therefore, each V_{i} is an irreducible Gal(K/E)-module. Furthermore Gal(K/E)|_{V_{i}} is unimodular since Gal(K/E) leaves each u_{i} fixed. We may write Gal(K/E) = Gal(K/E)^{o} ·H where H is a finite group (Wehrfritz (1973), page 142). Note that |Gal(K/E)/Gal(K/E)^{o}| = |H/H ∩Gal(K/E)^{o}|. Let G_{i} = Gal(K/E)|_{V_{i}} and H_{i} = H|_{V_{i}}. Note that Gal(K/E)^{o}|_{V_{i}} = (Gal(K/E)|_{V_{i}})^{o}. Lemma 3.2 implies that for each i, |H_{i}/H_{i} ∩ Gal(K/E)_{i}^{o}| < n_{i} · (n_{i})!. Therefore |H/H ∩ Gal(K/E)^{o}| ≤ ∏ |H_{i}/H_{i} ∩ G_{i}^{o}| < n^{n}n!.

To complete the proof of the proposition, let F be the Picard-Vessiot extension of Y′ = AY over k. We then have that F · k_{0} is the Picard-Vessiot extension of k_{0} for this equation and so can be identified with K. Proposition 6.6 of (Magid, 1994) implies that G̃ = Gal(K/k_{0}) = Gal(F ·k_{0}/k_{0}) may be identified with Gal(F/F ∩k_{0}). This implies that G̃ and G share a common component of the identity. Since the index of Gal(F/F ∩ k_{0}) in G is at most [k_{0} : k] we have that |G/G^{o}| ≤ |G̃/G̃^{o}| · [k_{0} : k] < [k_{1} : k_{0}]n^{n} · n![k_{0} : k] = [k_{1} : k]n^{n} · n!□

Note that no attempt was made to optimize the bound in this proposition. Once a decomposition of Y′ = AY is known, a better bound can be achieved.

4. Algorithms

4.1. Completely Reducible Equations

Let Y′ = AY be a differential equation with A an n × n matrix with coefficients in k = C(x), x′ = 1, C an computable algebraically closed field of characteristic zero. In this section we shall show how to compute the basis for a prime ideal I ⊂ k[Y_{11}, … Y_{nn}] such that the quotient field of k[Y_{11}, … Y_{nn}]/I is the Picard-Vessiot extension of k corresponding to Y′ = AY. Compoint (Compoint, 1996a; Compoint, 1996b) showed that such an ideal is generated by elements of the form Q(Y_{i,j}) − c where Q is a homogeneous invariant of the Galois group and f is a constant. In what follows, we shall show that the string of coefficients of the polynomial Q can be identified with a solution of an auxillary differential equation and that the element c can be determined from Q by evaluating Q at a power series solution (at a regular point) of Y′ = AY.

In order to define and calculate the auxillary operator mentioned above, we continue the discussion started in Section 2 concerning connections. We have defined subconnections, quotients, direct sums, tensor products and duals. Using these operations one can construct symmetric powers of connections. More concretely, let (M, ∇) be a connection of dimension N and let e_{1}, …, e_{N} be a basis of M. Let Y′ = BY be the associated equation with respect to this basis. The d^{th} symmetric power of this connection is defined on the space Sym^{d}(M). If we use the basis {e_{1}^{i_{1}}e_{2}^{i_{2}} ⋯ e_{N}^{i_{N}} | i_{1} + i_{2} + … + i_{N} = d}, the connection Sym^{d}(∇) is defined by the equation Z′ = Sym^{d}(B)Z where Sym^{d}(B)

is the ( \begin{matrix}N + d − 1 \\ d − 1 \end{matrix} ) × ( \begin{matrix}N + d − 1 \\ d − 1 \end{matrix} ) matrix whose entries are defined by expanding

the equations

(e_{1}^{i_{1}}e_{2}^{i_{2}} ⋯ e_{N}^{i_{N}})′ = i_{1}e_{1}^{i_{1}−1}e′_{1}e_{2}^{i_{2}} ⋯ e_{N}^{i_{N}} + i_{2}e_{1}^{i_{1}}e_{2}^{i_{2}−1}e′_{2} ⋯ e_{N}^{i_{N}} + … + i_{N}e_{1}^{i_{1}}e_{2}^{i_{2}} ⋯ e_{N}^{i_{N} −1}e′_{N}
= i_{1}e_{1}^{i_{1}−1}(Be_{1})e_{2}^{i_{2}} ⋯ e_{N}i_{N} + i_{2}e_{1}^{i_{1}}e_{2}^{i_{2}−1}(Be_{2}) ⋯ e_{N}^{i_{N}} + …
+i_{N}e_{1}^{i_{1}}e_{2}^{i_{2}} ⋯ e_{N}^{i_{N} −1}(Be_{N})

The dual (Sym^{d}(M)^{∗}, Sym^{d}(∇)^{∗}) of this connection corresponds to homogeneous polynomials of degree d on M with coefficients in k. To be explicit, let us order the basis s_{i_{i}i_{2}...i_{N}} = e_{1}^{i_{1}}e_{2}^{i_{2}} ⋯ e_{N}^{i_{N}} of Sym^{d}(M) in some way. If Φ = (…, f_{i_{1}i_{2}...i_{N}} , …) is a solution of Sym^{d}(∇)^{∗}(Φ) = 0, then we consider the associated polynomial

Q_{Φ} = ∑ \frac{d!}{i_{1}!...i_{N}!}f_{i_{1}i_{2}...i_{N}} Y_{1}^{i_{1}}...Y_{N}^{i_{N}}

with i_{1} + ... + i_{N} = d, and we have Q_{Φ}(y_{1}, ..., y_{N}) = Φ(S^{d}v), with v = y_{1}e_{1} + ... + y_{N}e_{N}.

Let K be the Picard-Vessiot extension of k corresponding to Y′ = BY, let G be its Galois group and V be the solution space of this equation in K with basis v_{1}, …, v_{N}. One can consider the symmetric power Sym^{d}(V), with basis {v_{1}^{i_{1}}v_{2}^{i_{2}} ⋯ v_{N}^{i_{N}} }, and its dual (Sym^{d}(V))^{∗} ≃ Sym^{d}(V^{∗}). One can show (Compoint, 1996a) that the two spaces Sym^{d}(M)^{∗}⊗K and Sym^{d}(V)⊗K are isomorphic as K-spaces. Note that if Sym^{d}(∇)^{∗}(Φ) = 0, then, for v = y_{1}v_{1} + … + y_{N}v_{N},

(Q_{Φ}(y_{1}, …, y_{N}))′ = Φ(S^{d}(v)))′

= Φ(Sym^{d}(∇)(S^{d}(v)))
= Φ(0)
= 0 .

Therefore the polynomial Q_{Φ} will take on constant values on solutions of Y′ = BY. Furthermore, the solutions of Sym^{d}(∇)^{∗}(Z) = 0 in Sym^{d}(M)^{∗}, that is the solutions of Sym^{d}(∇)^{∗}(Z) = 0 in Sym^{d}(M^{∗})⊗K with coefficients in k, correspond to the G-invariant elements of (Sym^{d}(V))^{∗} ⊗ K. A consequence of this is that a G-invariant homogeneous polynomial ϕ with constant coefficients (considered as an element of Sym^{d}(V^{∗})) corresponds to a vector Φ that is a solution of Φ′ = (Sym^{d}(B))^{∗}Φ with entries in k.Therefore, for ϕ as above we have a polynomial Q_{ϕ} − ϕ(S^{d}v) of degree d with coefficients in k that vanishes when evaluated at (y_{1}, ..., y_{N}). Let {y_{ij}} be a fundamental system of solutions of Y′ = BY, and consider the system Y′ = diag(B, ..., B)Y. The vector v whose coordinates are ^{t}(y_{11}, y_{21}, ..., y_{nn}) is a solution of this system. If ϕ is an element of Sym^{d}(V ⊕ ... ⊕ V) wich is G-invariant, then we obtain the polynomial P_{ϕ} = Q_{ϕ} − ϕ(S^{d}v). This polynomial clearly is in the ideal of polynomial relations among the {y_{ij}}. The main result of (Compoint, 1996a) is the following.

Proposition 4.1. Let k be a differential field with algebraically closed constants C and let Y′ = AY be a differential equation with A an n × n matrix with entries in k . Let (y_{i,j}) be a fundamental solution matrix of this equation in a Picard-Vessiot extension of k. Assume that the Galois group of this equation is reductive and unimodular and let {ϕ_{1}, …, ϕ_{t}} be homogeneous generators of the ring of invariants C[Y_{i,j}]^{G}. Then k[y_{i,j}] ≃ k[Y_{i,j}]/I where I = (P_{ϕ_{1}}, …, P_{ϕ_{t}}).

We can now state and prove the main result of this paper.

Theorem 4.1. Let k be an algebraic extension of C(x), C a computable algebraic closed field and let {Y_{i,j}}, {X_{i,j}} be two sets of n^{2} variables. Let Y′ = AY be a differential equation, with A an n × n matrix with entries in k, whose Galois group is reductive. Then one can compute in a finite number of steps a basis for a prime ideal I ⊂ k[Y_{i,j}] such that the quotient field K of k[Y_{i,j}] is a Picard-Vessiot extension of k corresponding to Y′ = AY. Furthermore, one can compute a basis for an ideal J ⊂ k[X_{i,j}] such that the Galois group of Y′ = AY is the set of zeroes of J in GL(n, C).

Proof. We will use Proposition 4.1 so our first task is to show that we may assume that the Galois group is unimodular. Consider the differential equation Y′ = ÃY where

Ã = ( \begin{matrix}A & 0 \\ 0 & −tr(A) \end{matrix} )

If Z is a fundamental solution matrix of Y′ = AY, then

( \begin{matrix}Z & 0 \\ 0 & (det(Z))^{−1} \end{matrix} )

is a fundamental solution matrix of Y′ = ÃY. The Picard-Vessiot extensions of these two equations are the same and so they have the same Galois groups. If g ∈ GL(n, C) is an element of the Galois group of Y′ = AY, then the map

g ↦ ( \begin{matrix}g & 0 \\ 0 & (det(g))^{−1} \end{matrix} )

is an isomorphism between the Galois group of Y′ = AY and that of Y′ = ÃY. Clearly the image of this map is unimodular. If we calculate the defining ideal I of a Picard-Vessiot extension for Y′ = ÃY then using Gröbner bases techniques, we can find the defining ideal of the solutions of Y′ = AY. We therefore will assume that the Galois group of Y′ = AY is unimodular.

In Section 3, we showed how one can calculate a bound for the degrees of a set of homogeneous generators of the invariants of a Galois group. We apply this to the equation Y′ = BY where B = diag(A, A, …, A). Assume that N is such a bound. Since k is an algebraic extension of C(x), Propositions 3.1 and 3.2 of (Singer, 1991) imply that we can, for each d ≤ N, calculate a C-basis B_{d} for the solutions Φ in k of Y′ = Sym^{d}(B)Y (see also (van Hoeij and Weil, 1996)). The entries of the Φ are in k and so can be considered functions on an algebraic curve. Let z_{0} be a C-point of this curve at which none of these functions have a pole. If we evaluate each of the coefficients of the polynomials Q_{ϕ}(Y_{1,1}, …, Y_{n,n}) at z_{0} and let Y_{i,j} = δ_{i,j}, we get a constant c_{Φ}. From the discussion preceeding Proposition 4.1, we see that P_{Φ} = Q_{Φ} − c_{Φ} vanishes on the solution {y_{i,j}} of Y′ = AY corresponding to the initial conditions y_{i,j}(z_{0}) = δ_{i,j}. Therefore we have found generators of the ideal I defining the Picard-Vessiot extension k({y_{i,j}}).

We now turn to calculating the Galois group. The Galois group of K = k(y_{i,j}) is the subgroup of GL(n, C) leaving the ideal I invariant. This is equivalent to leaving each polynomial P_{ϕ} invariant, ϕ ∈ B_{d}, 0 ≤ d ≤ N. Expanding each P_{Φ} in a C-basis of k, we see that this is equivalent to a system of polynomial equations with constant coefficients. These give the defining equations of the Galois group. □

Note that in the process of proving this result we have obtained polynomials that characterize the Galois group: The Galois group is precisely the set of matrices that fix the polynomials P_{Φ}. This gives an illustration of the theorem of Chevalley.

4.2. General Equations

In this section we shall show how Theorem 4.1 can be used to calculate properties of the Galois group of an arbitrary differential equation. The key to this is the following Proposition.

Proposition 4.2. Let k be a differential field with algebraically closed field of constants and let L ∈ k[D] be a differential operator. Let L = L_{m}L_{m−1} ⋯ L_{1} where each L_{i} is an irreducible operator and let L̃ = LCLM{L_{m}, …, L_{1}} where LCLM{…} denotes the least common left multiple. If G is the Galois group of L(y) = 0, then G/R_{u} is the Galois group of L̃, where R_{u} is the unipotent radical of G.

Proof. For simplicity we shall assume that m = 2; the general case can be proven in a similar manner. Let K be the Picard-Vessiot extension of k corresponding to L(y) = 0 and let n be the order of L and n_{i} be the order of L_{i}. Since L_{1} maps the solution space V of L(y) = 0 onto the solution space of L_{2}(y) = 0 there exists a basis {y_{1}, …, y_{n}} such that {y_{1}, …, y_{n_{1}}} is a basis of the solution space of L_{1}(y) = 0 and {L_{1}(y_{j})}_{j=n_{1}+1}^{n} is a basis of the solution space of L_{2}(y) = 0. Therefore {y_{1}, …, y_{n_{1}}, L_{1}(y_{n_{1}+1}), …, L_{1}(y_{n})} spans the solution space of LCLM{L_{1}, L_{2}} (note that these elements need not be linearly independent). Let K_{0} ⊂ K be the Picard-Vessiot extension generated by {y_{1}, …, y_{n_{1}}, L_{1}(y_{n_{1}+1}), …, L_{1}(y_{n})} and their derivatives, that is, the Picard-Vessiot extension corresponding to the equation LCLM{L_{1}, L_{2}}. We shall show that the subgroup H of G leaving K_{0} fixed is precisely R_{u}. First note that with respect to the basis {y_{1}, …, y_{n}} any element g ∈ G is in block diagonal form

g = ( \begin{matrix}g_{1} & ∗ \\ 0 & g_{2} \end{matrix} )

where g_{i} ∈ GL(n_{i}, C). Therefore, if g leaves the elements of K_{0} fixed, it must be of the form is in block diagonal form

g = ( \begin{matrix}I_{1} & ∗ \\ 0 & I_{2} \end{matrix} )

where I_{i} is the n_{i} × n_{i} identity matrix. Therefore H consists of unipotent matrices. Furthermore, H is the kernel of the map G → Gal(K_{0}/k) given by restriction. Since Gal(K_{0}/k) is the Galois group of a completely reducible operator, it is a reductive group. Therefore H is not properly contained in any normal unipotent subgroup and so it must be the radical of G. □

Theorem 4.2. Let k be an algebraic extension of C(x) and let L ∈ k[D]. Let G be the Galois group of L(y) = 0. Then one can

1 calculate G/R_{u} where R_{u} is the unipotent radical of G,

2 calculate G/G^{o}, and

3 decide if G^{o} is solvable and therefore decide if L(y) = 0 is solvable in terms of liouvillian functions.

Proof. One begins by factoring L into a product L_{1}L_{2} ⋯ L_{m} of irreducible factors (see Section 5.1) and then forming the operator L̃ = LCLM{L_{m}, …, L_{1}}. Proposition 4.2 implies that L̃ has Galois group isomorphic to G/R_{u} where G is the Galois group of L and R_{u} is its unipotent radical. If L̃ has order r then Theorem 4.1 implies that we can find polynomials {f_{i}} in r^{2} variables whose zero set in GL(r, C) is the Galois group G̃ of L̃. This proves 1.

The map G → G/G^{o} induces an isomorphism of G/G^{o} onto (G/R_{u})/(G/R_{u})^{o}. Therefore to prove 2., we shall show how to compute (G/R_{u})/(G/R_{u})^{o}. Compute G/R_{u} as in 1. Standard arguments (Gianni et al., 1988; Eisenbud et al., 1992) allow one to decompose the variety defined by {f_{i} = 0} into irreducible components. The number of these components will be |(G/R_{u})/G/R_{u})^{o}|. Selecting a distinct set of representatives {g_{j}} from these components and deciding to which component each g_{i}g_{j} belongs allows us to write down a multiplication table for (G/R_{u})/G/R_{u})^{o}. This proves 2.

Note that G^{o} is solvable if and only if G^{o}/R_{u} = (G/R_{u})^{o} is solvable. Using the decomposition of G/R_{u} into irreducible components, we can select the component of the identity of this latter group. Since (G/R_{u})^{o} is reductive, it is solvable if and only if it is conjugate to a subgroup of the diagonal group D. Using Gröbner bases techniques, one can decide if the set of h ∈ GL(r, C) such that h(G/R_{u})^{o}h^{−1} ⊂ D is nonempty and so decide if (G/R_{u})^{o} is semisimple. This proves 3. We note that decisions procedures for 3. also appear in (Singer, 1981; Singer, 1991; Singer and Ulmer, 1996). □

5. Appendix

Let C be an algebraically closed field and let k be an algebraic extension of C(x). In this section we shall show that there are algorithms to factor operators over k or decide if operators are completely reducible over k. Although it may be apparent to the experts that many of the algorithms to do these tasks over C(x) can be modified to work over k (see (van Hoeij, 1996; van Hoeij, 1997; Singer, 1996) for references to the known algorithms), this has not been explicitly presented in print. We do not claim that the algorithms we present here are the most efficient but rather are ones that are simple to describe.

5.1. Factoring

We begin by recalling some known procedures. Let K be a differential field. We say that we can effectively solve homogeneous linear differential equations over K if for any operator L ∈ K[D] we can effectively find a basis for the vector space of all y ∈ K such that L(y) = 0 (c.f., (Singer, 1991)). We say that we can effectively find all exponential solutions of homogeneous linear differential equations over K if for any operator L ∈ K[D]

we can effectively find u_{1}, …, u_{m} ∈ K such that if L(e^{∫ u}) = 0 for some u ∈ K, then for

some i, e^{∫ u}/e^{∫ u_{i}} ∈ K. It is clear that we can perform both of these tasks if K = C. Propositions 2.1 and 3.1 of (Singer, 1991) imply that we can then perform both of these tasks over k where k is an algebraic extension of C(x). Lemma 2.4 of (Singer, 1991) implies that we can refine the second task in the following way:

Given L ∈ k[D], one can effectively find u_{i} and v_{i,j}, 1 ≤ i ≤ m, 1 ≤ j ≤ n_{i} in k such that if u ∈ k and L(e^{∫ u}) = 0 then there exists an i and constants c_{i,j} such that e^{∫ u} = (∑_{j=1}^{n_{j}} c_{i,j}v_{i,j})e^{∫ u_{i}}.

Using the methods of Proposition 2.4 we can decide if e^{∫ u_{i}}/e^{∫ u_{j}} = f_{i,j} ∈ k for each pair i > j. If this is the case, we can replace v_{i,1}, …, v_{i,n_{i}} with v_{i,1}, …, v_{i,n_{i}},

f_{i,j}v_{j,1}, …, f_{i,j}v_{j,n_{j}}, delete u_{j} and assume that the new set of u_{i}’s satisfies e^{∫ u_{i}}/e^{∫ u_{j}} ∉ k for i ≠ j.

To factor operators over k we proceed as follows. Let L = L_{1}L_{2} where L_{1} has order n − r and L_{2} has order r. Since the solutions of L_{2}(y) = 0 are also solutions of L(y) = 0, we can write

L_{2}(y) = y^{(r)} + b_{r−1}y^{(r−1)} + … + b_{0}y  (5.1)

= \frac{det ( \begin{matrix}Y & y_{1} & … & y_{r} \\ Y′ & y′_{1} & … & y′_{r} \\ … & … & … & … \\ Y^{(r)} & y_{1}^{(r)} & … & y_{r}^{(r)} \end{matrix} )}{det ( \begin{matrix}y_{1} & … & y_{r} \\ y′_{1} & … & y′_{r} \\ … & … & … \\ y_{1}^{(r−1)} & … & y_{r}^{(r−1)} \end{matrix} )}  (5.2)

where y_{1}, …, y_{r} are solutions of L(y) = 0.

Note that the denominator of the right hand side of 5.2 is the wronskian of a fundamental set of solutions of L_{2}. Therefore it is exponential over k. Furthermore the coefficients of L_{2} are quotients of determinants of r × r submatrices of

( \begin{matrix}y_{1} & … & y_{r} \\ y′_{1} & … & y′_{r} \\ … & … & … \\ y_{1}^{(r)} & … & y_{r}^{(r)} \end{matrix} )  (5.3)

and this wronskian. Since the coefficients of L_{2} are in k, each determinant of an r × r submatrix of 5.3 is exponential over k.

One can calculate a differential equation L^{∧r} whose solution space is spanned by all such determinants as y_{1}, …, y_{r} varies over all subsets of r solutions of L(y) = 0 (c.f., Schlesinger (1887), Section 167 - 168). We use the algorithm alluded to in the displayed paragraph above to calculate u_{i}, v_{i,j} as described for the equation L^{∧r}. Since we are

assuming that for distinct i, j, e^{∫ u_{i}}/e^{∫ u_{j}} ∉ k, we see that for each coefficient b_{l} of L_{2} there is an index i and constants c_{i,j}, d_{i,j} such that

b_{l} = \frac{∑_{j=0}^{n_{j}} c_{i,j}v_{i,j}}{∑_{j=0}^{n_{j}} d_{i,j}v_{i,j}}  (5.4)

Therefore to decide if L has a factor of order r one selects a j ∈ {1, …, m} for each l, forms the expression 5.4 with indeterminate c_{i,j}, d_{i,j} for each possible coefficient b_{l} and formally divides the resulting operator into L. Setting the remainder equal to zero gives polynomial conditions on the c_{i,j}, d_{i,j} and one then decides if there are constants satisfying these conditions. If no factor is found in this way then L is irreducible. Otherwise one factors L and proceeds by induction until an irreducible factorization is found.

We note that this procedure can be modified to find an algebraic extension k_{1} of k and a factorization of L over k_{1} such that each factor is absolutely irreducible. To do this one can modify the algorithm displayed above to find a set of elements u_{i} and v_{i,j}, 1 ≤

i ≤ m, 1 ≤ j ≤ n_{j} algebraic over k such that if u is algebraic over k and L(e^{∫ u}) = 0

then there exists an i and constants c_{i,j} such that e^{∫ u} = (∑_{j=1}^{n_{j}} c_{i,j}v_{i,j})e^{∫ u_{i}}. One then proceeds to factor over k_{1} = k({u_{i}}, {v_{i,j}}) and continue this process until no further factorization is possible.

5.2. Testing Complete Reducibility

In (Singer, 1996), a test is given to decide if an element L ∈ C(x)[D] is completely reducible. One can extend this to a test for elements of k[D], k an algebraic extension of C(x) in the following way. We may assume that k is a Galois extension of C(x). Let G be its Galois group and let L^{σ} denote the operator gotten from L by applying σ ∈ G to all the coefficients of L. Let M be the least common left multiple of all the elements of {L^{σ} | σ ∈ G}. Since L divides M on the right, the Galois group of L will be a quotient of the Galois group of M. Proposition 2.2.6 implies that if M is completely reducible, then L is completely reducible. Conversely, if L is completely reducible then each L^{σ} is completely reducible and so M is completely reducible. Therefore to decide if L is completely reducible over k it suffices to decide if M is completely reducible over k. Note that the coefficients of M are invariant under the Galois group and so must lie in C(x).

As noted at the end of Section 2.3 M is completely reducible over k if and only if it is completely reducible over C(x). Therefore we can use the results of (Singer, 1996) to decide if M (and therefore L) is completely reducible.

The results of (Singer, 1996) allow one to decide if an equation is completely reducible without having to find a factorization. If a factorization is given, then one can proceed in a different manner. Let Y′ = AY be a differential equation with

A = ( \begin{matrix}A_{1} & 0 & 0 & … & 0 \\ ∗ & A_{2} & 0 & … & 0 \\ … & … & … & … & … \\ ∗ & ∗ & … & ∗ & A_{r} \end{matrix} )  (5.5)

where each equation Y′ = A_{i}Y is irreducible and let (M, ∇) be the associated connection. One sees that this connection has a filtration (M, ∇) = (M_{1}, ∇_{1}) ⊃ (M_{2}, ∇_{2}) ⊃ … ⊃ (M_{r}, ∇_{r}) where the quotient of the i and i + 1 elements is a connection having equation Y′ = A_{i}Y. From general properties of completely reducible modules, we see that (M, ∇) is isomorphic to ⊕_{i=1}^{r}(M_{i}/M_{i+1}, ∇_{M_{i}/M_{i+1}}). This latter connection has equation Y′ = ÃY where

Ã = ( \begin{matrix}A_{1} & 0 & 0 & … & 0 \\ 0 & A_{2} & 0 & … & 0 \\ … & … & … & … & … \\ 0 & 0 & … & 0 & A_{r} \end{matrix} )  (5.6)

Conversely, since each Y′ = A_{i}Y is irreducible, we see that if A and Ã are equivalent then Y′ = AY is completely reducible. Therefore to decide if Y′ = AY is completely reducible we must decide if there exists a U ∈ GL(n, k) such that U′ = AU − UÃ. To do this we find a basis U_{1}, … U_{s} of the solution space of U′ = UA − ÃU with entries in k and decide if there are constants c_{i} such that det(∑ c_{i}U_{i}) ≠ 0.

References

Baldassarri, F., Dwork, B. (1979). On second order linear differential equations with algebraic solutions.

American Journal of Mathematics, 101:42–76. Bertrand, D. (1995). Minimal heights and polarizations on group varieties. Duke Mathematics Journal,

80:1:223–250. Coates, J. (1970). Constructions of rational functions on a curve. Proceedings of the Cambridge Philo-

sophical Society, 68:105–123. Cohen, H. (1993). A Course in Computational Algebraic Number Theory. Graduate Texts in Mathe-

matics. Springer-Verlag, New York. Compoint, E. (1996a). Differential Equations and Algebraic Relations. Technical report, Université de

Paris VI. Compoint, E. (1996b). Équations Différentielles, Relations Algébriques et Invariants. PhD thesis,

Université de Paris VI. Eisenbud, D., Huneke, C., Vasconcelos, W. (1992). Direct methods for primary decomposition. Inven-

tiones Mathematicae, 110:207–236. Gianni, P., Trager, B., Zacharias, G. (1988). Gröbner bases and primary decomposition of polynomial

ideals. Journal of Symbolic Computation, 6:149–167. Grigoriev, D. Y. (1990). Complexity of irreducibility testing for a system of linear ordinary differen-

tial equations. In Proceedings of the 1990 International Symposium on Symbolic and Algebraic Computation, pages 225–230. ACM Press.

Haefliger, A. (1987). Local theory of meromorphic connections in dimension one (Fuchs theory). In

Algebraic D-Modules, Borel et al, chapter III., pages 129–149. Academic Press. Hiss, K. (1996). Constructive invariant theory for reductive groups. Technical report, Brandeis University. Humphreys, J. (1975). Linear Algebraic Groups. Graduate Texts in Mathematics. Springer-Verlag, New

York.

Kaplansky, I. (1976). An Introduction to Differential Algebra. Hermann, Paris, second edition. Katz, N. (1987). A simple algorithm for cyclic vectors. American Journal of Mathematics, 109:65–70. Kempf, G. (1987). Computing invariants. In Koh, S. S., editor, Invariant Theory, Lecture Notes in

Mathematics, 1278, pages 81–94. Springer-Verlag, Berlin, Heidelberg, New York. Kolchin, E. (1968). Algebraic groups and algebraic dependence. American Journal of Mathematics,

90:1151–1164. Kolchin, E. (1976). Differential Algebra and Algebraic Groups. Academic Press, New York. Magid, A. (1994). Lectures on Differential Galois Theory. University Lecture Series. American Mathe-

matical Society. Masser, D. (1988). Linear relations on algebraic groups. In Baker, A., editor, New Advances in Tran-

scendence Theory, pages 248–262. Cambride University Press, Cambridge. Noether, E. (1916). Der Endlichkeitsatz der Invarianten endlicher Gruppen. Mathematische Annalen,

77:89–92. Onishchik, A. L., Vinberg, E. B. (1990). Lie Groups and Algebraic Groups. Springer-Verlag, Berlin. Pohst, M., Zassenhaus, H. (1989). Algorithmic Algebraic Number Theory. Encyclopedia of Mathematics

and its Applications. Cambridge University Press, Cambridge. Popov, V. L. (1981). Constructive invariant theory. Astérisque, 87/88:303–334. Schlesinger, L. (1887). Handbuch der Theorie der Linearen Differentialgleichungen. Teubner, Leipzig. Singer, M. F. (1979). Algebraic solutions of n^{th} order linear differential equations. In Proceedings of the

1979 Queen’s Conference on Number Theory, pages 379–420. Queen’s Papers in Pure and Applied Mathematics, 59.

Singer, M. F. (1981). Liouvillian solutions of n^{th} order homogeneous linear differential equations. Amer-

ican Journal of Mathematics, 103:661–681. Singer, M. F. (1991). Liouvillian solutions of linear differential equations with liouvillian coefficients.

Journal of Symbolic Computation, 11:251–273. Singer, M. F. (1996). Testing reducibility of linear differential operators: a group theoretic perspective.

Applicable Algebra in Engineering, Communication and Computing, 7:77–104. Singer, M. F., Ulmer, F. (1996). Linear differential equations and products of linear forms. Journal of

Pure and Applied Algebra. to appear. Sturmfels, B. (1991). Gröbner bases for toric varieties. Tôhoku Mathematics Journal, 43:249–261. Sturmfels, B. (1993). Algorithms in Invariant Theory. Springer-Verlag, Vienna. Trager, B. (1984). Integration of Algebraic Functions. PhD thesis, MIT. van der Waerden, B. L. (1953). Modern Algebra. Frederick Ungar Publishing Co., New York, second

edition. van Hoeij, M. (1996). Rational solutions of the mixed differential equation and its applications to

factorization of differential operators. In Proceedings of the 1996 ISSAC Conference, pages 219 – 225. ACM Press.

van Hoeij, M. (1997). Factorization of differential operators with rational function coefficients. to appear

in the Journal of Symbolic Computation. van Hoeij, M., Weil, J.-A. (1996). An Algorithm for Computing Invariants of Differential Galois Groups.

Technical report, University of Groningen. Wehlau, D. (1993). Constructive invariant theory for tori. Annales de l’Institut Fourier, Grenoble,

43:1055–1066. Wehrfritz, B. A. F. (1973). Infinite Linear Groups. Ergebnisse der Mathematik. Springer-Verlag, Berlin.