Direct and Inverse Problems in Differential Galois Theory

Michael F. Singer

Abstract. This paper surveys recent work on the problems of calculating Galois groups of differential equations and of constructing differential equations with given groups as their Galois groups.

1. Introduction

In his address to the 1966 International Congress of Mathematicians [87], Ellis Kolchin described five problems with the hope that “my description of a few of the more challenging unsolved problems will lure some into accepting the challenge.” The fourth problem, concerning the Picard-Vessiot theory, was presented in the following way:

Now let 𝔉 be an ordinary differential field and denote its field of constants by ℭ; denote the field of constants of 𝔘^{1} by 𝔎. Consider a homogeneous linear differential polynomial L = Y^{(n)} + a_{1}Y^{(n−1)} + … + a_{n}Y with coefficients in 𝔉. If ℭ is algebraically closed then L has a fundamental system of zeros (η_{1}, …, η_{n}) such that the extension 𝔊 = 𝔉⟨η_{1}, … η_{n}⟩ of 𝔉 has the same field of constants ℭ, and then the set of all the isomorphisms over 𝔉 of 𝔊 onto an extension of 𝔉 in 𝔘 has a natural group structure; by means of the fundamental system of zeros (η_{1}, …, η_{n}) this group can be identified with an algebraic subgroup G of GL_{𝔎}(n) defined over ℭ. This G can be called the Galois group of L over 𝔉. Of course, a different choice of fundamental systems of zeros in general gives a different Galois group; G is determined up to conjugation in GL(n) by a matrix that is rational over ℭ. (This ambiguity can be removed by taking for G an algebraic subgroup of the group GL(V) of all automorphisms of the vector space V of zeros of L).

As in the ordinary Galois theory, there are two general problems:

1^{o} Given L, to determine G.

2^{o} Given G, to find an L of which G is the Galois group.

1991 Mathematics Subject Classification. Primary 12H05, 14E20; Secondary 12F12, 12Y05.

The author was supported in part by NSF Grant #CCR-93222422.

1Kolchin previously defined 𝔘 to be a universal differential field, that is, a field “so large that it contains enough elements for every purpose we can have.” Kolchin also assumes that this field is of characteristic zero and we shall make this assumption for all fields mentioned in this paper.

Of course, the nature of these problems depends on the differential field 𝔉 which is given. For example, when 𝔉 = ℭ then it is easy to see that, for every L, G is reducible to triangular form (and hence is solvable). A. Bialynicki-Birula [25] has shown that if 𝔉 has finite transcendence degree over ℭ and G is a connected and nilpotent algebraic subgroup of GL(n) defined over ℭ, then there exists a homogeneous linear differential polynomial L with coefficients in 𝔉 such that the Galois group of L over 𝔉 is isomorphic to G. Aside from this and some work in a slightly different direction by Lawrence Goldman [57], even when 𝔉 = ℂ(x) very little of a general nature is known. For the second problem this is not unexpected, in view of the history of the analogous problem in classical Galois theory. The obstinacy of the first problem is somewhat of a surprise, and it now appears that we should be grateful for almost any kind of information about G; the difficulty stems in part from the fact that a zero of L that is not a zero of any linear differential polynomial over ℂ(x) of lower order may very well be a zero of a nonlinear one.

We shall refer to problem 1^{o} as the direct problem and problem 2^{o} as the inverse problem. The aim of this paper is to describe some of the work that has been done on these problems since Kolchin’s talk and to give a guide to the literature. Excellent guides to the 19^{th} Century literature are [69], [131], [132] and [160] as well as [58] and [59] which give historical insight into this era. A good recent survey of work on linear meromorphic differential equations is [158] (see also [159]). We refer to Borel’s article [26] or any of [22], [53], [54], [77], [88], [95], [100] for the basic facts concerning differential Galois theory and [27] for the basic facts concerning linear algebraic groups.

2. The Direct Problem

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 [39], [117], [163]. 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 Picard-Vessiot extension is the analogue of the splitting field. 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. Nonetheless, there are many properties of the Galois group that can be computed and, in some cases, one can even determine this group (see [140] for an introduction to differential Galois theory with an emphasis on computational aspects).

Let k be a differential field with algebraically closed field of constants C. Let L(y) be a homogeneous linear differential polynomial of order n with coefficients in k, K = k⟨y_{1}, …, y_{n}⟩ the associated Picard-Vessiot extension, and G its Galois group. We will denote by V the solution space of L(y) = 0 in K. Note that V is a finite dimensional C-vector space and a G-module. We shall now consider algorithms to determine various properties of G, V and L. Throughout we shall assume that the field of constants C is a computable field with a factorization algorithm, that is, a field whose field theoretic operations +, −, ×,^{−1} are recursive functions and over which we can effectively factor polynomials. For example, the algebraic closure of a finitely generated extension of ℚ is such a field [163].

2.1. Triviality of G. The Galois group is trivial if and only if K = k, so we wish to consider algorithms to decide if L(y) = 0 has a full set of solutions in k. In fact algorithms exist to find the space W ⊂ V of solutions of L(y) = 0 in k for large classes of fields k. Consider first the simpler problem of finding solutions a ∈ ℚ of p(x) = a_{n}x^{n} +… a_{0} = 0, p(x) ∈ ℤ[x]. One way to proceed is to note that factors of the denominator of a must divide a_{n} and the factors of the numerator must divide a_{0} (assuming that a has relatively prime numerator and denominator). One could then try all possibilities. For differential equations L(y) = a_{n}y^{(n)} + … + a_{0}y = 0 with a_{i} ∈ C(x), x′ = 1 one can attempt a similar approach. One can see that any irreducible factor q of the denominator of a solution y ∈ C(x) must divide a_{n}, but the largest power q^{m} of q dividing the denominator of y may be greater than the largest power of q dividing a_{n}. For example, y = x^{m} is a solution of xy′−my = 0. To bound m in general, one expands q-adically each a_{i} = a_{i,n_{i}}q^{n_{i}} + a_{i,n_{1}+1}q^{n_{i}+1} + …, deg(a_{i,j}) < deg(q), substitutes y = A_{m}q^{m} + A_{m+1}q^{m+1} + … into L(y) = 0 and notices that in order for equality to hold the exponent m must satisfy a polynomial equation over C (the indicial equation at q). The smallest integer root m_{q} of this equation will bound the possible m. Substituting y = z ∏ q^{m_{q}} into L(y) = 0, reduces the problem to finding polynomial solutions of L̃(z) = L(z ∏ q^{m_{q}}) = 0. In order for equality to hold in L̃(z) = 0 after one substitutes z = α_{N}x^{N} + … + α_{0}, one again sees that N must satisfy a polynomial equation (the indicial equation of L̃ at infinity). If N is the largest integer root of this polynomial, we can substitute z = α_{N}x^{N} + … + α_{0} into L̃(z) = 0 to yield a system of linear equations for the α_{i}. A basis of the solution space of this system will yield a basis of the solution space of L(y) = 0 in C(x).

This naive algorithm can be improved in several ways. For example, one would like to work in the smallest field C_{0}(x) ⊂ C(x) containing the coefficients of L and one would like to find efficient algorithms to find polynomial solutions of linear differential equations. These and related issues are discussed in [1], [3], [4], [35]. Before turning to other fields, we note that in many situations one is given a system Y′ = AY of differential equations where A is an n × n matrix with coefficients in C(x) and asked to determine a basis for all solutions in (C(x))^{n}. In theory one can reduce this problem to finding all solutions of an associated scalar equation L(y) = 0 in C(x) (this is described in Section 2.4.1) but finding this associated equation can be costly. An algorithm to find rational solutions of the system Y′ = AY directly has been given by M. A. Barkatou [14].

Algorithms to find solutions of L(y) = 0 in a given differential field k when k is an algebraic extension of C(x), or more generally, certain types of liouvillian extensions (this term will be defined below) of C(x) are discussed in [141]. Finally algorithms to find solutions of inhomogeneous linear differential equations in various fields are discussed in [30], [31], [32], [33], [45].

2.2. Reducibility of V. The G-module V contains a proper nontrivial Gmodule W of dimension r if and only if one can write the differential polynomial L(y) = L_{n−r}(L_{r}(y)) as a composite of homogeneous linear differential polynomials L_{n−r} and L_{r} of orders n − r and r respectively with coefficients in k. To see this, let {y_{1}, …, y_{r}} be a basis of W and let L_{r}(y) = Wr(y, y_{1}, …, y_{r})/Wr(y_{1}, … y_{r}), where Wr(…) denotes the wronskian determinant. Assume that W is a G-invariant subspace of V. The coefficients of L_{r} are left invariant by G since applying g ∈ G to these wronskians multiplies each of these determinants by the determinant of the linear map induced by g on W. Writing L(y) = L_{n−r}(L_{r}(y))+R(y) where the order of R(y) is less than r (c.f., [118], Ch. III) we see that R(y) = 0 has r independent solutions in K and therefore must be 0. Conversely, if L(y) = L_{n−r}(L_{r}(y)), the solution space W of L_{r}(y) = 0 is a G-invariant subspace of V.

This characterization of reducibility leads naturally to considering the ring D = k[D] of linear operators. This is the ring of noncommutative polynomials in D with coefficients in k where D · a = a · D + a′. To each homogeneous linear differential polynomial L(y) = a_{n}y^{(n)} + … + a_{0}y we can associate the operator L = a_{n}D^{n} + … + a_{0} in D. We then have that V is reducible as a G-module if and only if L factors in D as a product of operators of smaller positive order. Furthermore, to any operator L ∈ D one can associate the left D-module D/D · L. The operator L factors as a product of operators of smaller positive order if and only if the D-module D/D · L contains a proper nontrivial D-submodule (see [143] for a discussion of this ring and historical comments on the work of Frobenius, Jordan, Beke, Loewy, Ore and Jacobson concerning D). Applying the Jordan-Hölder Theorem one sees that every operator L ∈ D can be written as a product of irreducible operators L = L_{1} · . . . · L_{r}. Furthermore, if L = L̃_{1} · . . . · L̃_{s} with the L̃_{i} irreducible, then r = s and (after a possible renumbering) the D-modules D/DL_{i} and D/DL̃_{i} are isomorphic or, in more pedestrian terms, the orders of L_{i} and L̃_{j} are equal and there exist nonzero operators R and S whose orders are less than the order of L_{i} satisfying L_{i}R = SL̃_{i}.

Before we discuss algorithms to determine if V is reducible we investigate the more restrictive question of whether V has a one dimensional G-submodule. As we have seen this is equivalent to L having a right factor of order one. If we write L = L_{n−1}L_{1} where L_{1} = D − r, then one sees that L has a first order right factor if and only if L(y) = 0 has a solution of the form y = exp(∫ r) with r ∈ k (y is then called an exponential over k). Algorithms to find such solutions when k = \overline{ℚ}(x) are classical ([131], Section 177) and rest on the fact that at any point x_{0} ∈ ℂ, one can formally find the solution space of L(y) = 0 (one can also consider the point at infinity by letting x = 1/z and d/dx = −z^{2}d/dz). If x_{0} is a nonsingular point (i.e., a point where a_{n}(x_{0}) ≠ 0), then all solutions are given by convergent power series. In general, if a linear differential equation has coefficients that are meromorphic at x_{0}, there exist n linearly independent solutions of the form

y_{i} = (x − x_{0})^{λ_{i}}e^{Q_{i}(t)}(ϕ_{i,0} + ϕ_{i,1}(t) log(x − x_{0}) + … ϕ_{i,s_{i}}(t)(log(x − x_{0}))^{s_{i}}) (2.1)

where λ_{i} ∈ ℂ, t = (x − x_{0})^{−1/q_{i}} for some positive integer q_{i}, Q_{i} is a polynomial in t^{−1} without constant term, and ϕ_{i,j} ∈ ℂ[[t]]. At each point x_{0} there are only a finite number of λ_{i} (called exponents) and Q_{i} (called determining factors) that can occur and these can be calculated directly from the operator L (or a system Y′ = AY) ([131], Section 110, [11], [13], [49], [68], [72], [94], [101], [148], [150]). If exp(∫ r) is a solution of L(y) = 0 and r = α_{m}(x − x_{0})^{−m} + … + α_{1}(x − x_{0})^{−1} + … is the Laurent expansion of r at x_{0}, then Q(x) = \frac{α_{m}}{−m+1}(x − x_{0})^{−m+1} − … − α_{2}(x − x_{0})^{−1} is a determining factor and λ = α_{1} is an exponent at x_{0}. In particular, if x_{0} is a nonsingular point, then m = 1 and α_{1} is an integer between 0 and n − 1. Therefore to find the possible r ∈ \overline{ℚ}(x) with L(exp(∫ r)) = 0, we write

r = p(x) + ∑_{α∈S}(∑_{i=1}^{n(α)} \frac{c_{α,i}}{(x − α)^{i}}) + ∑_{β∈N} \frac{m_{β}}{(x − β)}

where S is the set of finite singular points, N is the set of finite non-singular points, the c_{α,i} are constants, the m_{β} are integers between 0 and n − 1, and p(x) is a polynomial. For α ∈ S, the possible terms ∑_{i=1}^{n(α)} \frac{c_{α,i}}{(x−α)^{i}} can be found by examining the exponents and determining factors at α. The possibilities for the polynomial p(x) can be found by examining the determining factors at infinity. For each choice of these possibilities, we consider z = y exp(− ∫ r̃) where r = p(x) + ∑_{α∈S}(∑_{i=1}^{n(α)} \frac{c_{α,i}}{(x−α)^{i}}). The element z = exp(∫ ∑_{β∈N} \frac{m_{β}}{(x−β)}) = ∏(x − β)^{m_{β}} satisfies the linear differential equation L̃(z) = exp(− ∫ r̃)L(z exp(∫ r̃)) = 0. The original equation L(y) = 0 has an exponential solution if and only for some choice possibilities the equation L̃(y) = 0 has a polynomial solution. In the previous section we discussed how to decide this latter question. One can furthermore use this approach to find all such solutions. There are many places where this algorithm can be improved. For example, one would like to work in the coefficient field for as long as possible. One would like to efficiently find the exponents and determining factors. Also, it is not always necessary to try all possible combinations of the determining factors and exponents. These and other implementation issues as well as generalizations to other fields are discussed in [34], [45], [71], [141] . There are also algorithms to find exponential solutions of systems Y′ = AY, that is solutions Y = (y_{1}, …, y_{n})^{T} where each y_{i} is exponential over \overline{ℚ}(x) [115].

We now turn to the problem of deciding if V has invariant subspaces W of arbitrary dimension r. As noted in the beginning of this section, this is equivalent to finding a right factor of L of order r. Such an operator will be of the form L_{r} = Wr(y, y_{1}, …, y_{r})/Wr(y_{1}, … y_{r}) where y_{1}, … y_{r} forms a basis of W. The coefficients of L_{r} are quotients whose numerators are r × r subdeterminants of

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

and whose denominators are Wr(y_{1}, …, y_{r}). For example the coefficient of y^{(r−1)} in L_{r} is Wr(y_{1}, …, y_{r})′/Wr(y_{1}, …, y_{r}). Since each of these quotients is in k, one can show that each of these subdeterminants is an exponential over k. Furthermore, one can show ([131], Section 167) that there exists an operator L^{∧r} of order at

most ( \begin{matrix}n \\ r \end{matrix} ) with coefficients in k, such that for any basis y_{1}, …, y_{n} of V, all

r × r subdeterminants of Wr(y_{1}, …, y_{n}) satisfy L^{∧r}(y) = 0. We again restrict ourselves to operators whose coefficients lie in the field k = \overline{ℚ}(x) and outline an algorithm originally due to Beke [16]. To find a right factor of order r of L, one first finds a maximal set {z_{i}} of linearly independent solutions of L^{∧r}(y) = 0 that are exponential over k. One can then give a bound N on the degrees of the numerators and denominators of all elements of \overline{ℚ}(x) that equal a quotient (∑ c_{i}z_{i})/(∑ d_{i}z_{i}). One forms an operator L̃_{r} of order r whose coefficients are quotients of polynomials of degree N in x with indeterminate coefficients. Formally dividing L̃_{r} into L yields a remainder that is an operator R of order less than r. The coefficients of this remainder will be quotients of polynomials in x whose coefficients are polynomials in the indeterminates introduced above. The condition R = 0 is equivalent to systems of polynomial equalities and inequalities that the indeterminates must satisfy in order that L̃_{r} divides L. One then decides if these equalities and inequalities can be satisfied in C (details and refinements of this basic algorithm are given in [16], [36], [42] Appendix, [131] Section 176, [133]). One can refine this algorithm to give a factorization into irreducible factors. Furthermore, one can enumerate all possible factorizations [154].

There have been other improvements in this algorithm. In [63] Grigoriev gives several improvements in the algorithm together with a careful analysis of the running time and the size of the resulting factors. He also gives a polynomial time algorithm to find the greatest common right divisor of a family of operators.

Another improvement comes from the observation that not all exponential solutions of L^{∧r}(y) = 0 yield information about factors. Generically, the solution space of L^{∧r}(y) = 0 is G-isomorphic to ⋀^{r} V (although, there are situations when this solution space is isomorphic to a quotient of ⋀^{r} V). Not all G-invariant lines in ⋀^{r} V correspond to decomposable vectors, i.e., vectors of the form v_{1} ∧ … ∧ v_{r}; the Plücker relations define those that do. Therefore not all exponential solutions of L^{∧r}(y) = 0 must correspond to subdeterminants of 2.2. Tsarev [153] has shown how one can use the Plücker relations to narrow down the possible exponential solutions of L^{∧r}(y) = 0 that enter into the factorization problem.

Recent work of van Hoeij [71, 72] has led to good implementations of algorithms to factor linear operators. In [72] van Hoeij takes the methods of [101] and turns them into efficient algorithms for factoring in C((x))[D]. In [71] he uses the local methods of [72] to give good ways to find exponential solutions of linear differential operators with the aim of efficiently determining the coefficients in a factorization. In addition he minimizes the need to go beyond the smallest field containing the coefficients of L.

When one considers restricted classes of differential operators, the problem of factorization becomes more tractable. We say that a differential operator L is completely reducible if it is the least common left multiple of irreducible operators. This is equivalent to any of the following: a) D/DL is the sum of irreducible Dmodules; b) V is the sum of irreducible G-modules; c) G is a reductive group. In [143] algorithms are given to decide if an operator in C(x)[D] is completely reducible (this is generalized to algebraic extensions of C(x) in the appendix of [42]). Furthermore, once it is known that the operator is completely reducible, it can be factored by finding solutions in k of certain auxiliary systems; one does not need to search for elements that are exponential over k. Although this class seems to be restrictive, we shall see below that in other decision problems one is frequently given an operator that is known in advance to be completely reducible and for which one needs to determine a factorization. In [70], van Hoeij shows how his methods may be applied to this class of differential operators (as well as some more general classes).

For differential systems Y′ = AY, the solution space has an invariant Gsubmodule of dimension s if and only if there is an invertible matrix B ∈ GL(n, k) such that

B′B^{−1} + BAB^{−1} = ( \begin{matrix}A_{1,1} & 0 \\ A_{2,1} & A_{2,2} \end{matrix} )

where A_{2,2} is in M(s, k), [62]. In this latter paper, Grigoriev gives a procedure (with complexity analysis) for determining this property when k = C(x).

Finally, we note that although Gauss’s Lemma does not hold in D, an Eisensteinlike criterion for irreducibility was developed for this ring in [91].

2.3. Solvability of the Identity Component. One consequence of Kolchin’s work on the Galois theory of differential equations was to give a precise version of Vessiot’s theorem concerning equations solvable by quadratures (see [85] for a discussion of Vessiot’s original work). One says that an extension E = k(t_{1}, … t_{r}) of k is a liouvillian extension of k if for each i either:

1. t_{i} is primitive over k(t_{1}, … t_{i−1}), i.e. t′_{i} ∈ k(t_{1}, … t_{i−1}), or
2. t_{i} is exponential over k(t_{1}, … t_{i−1}), i.e. t′_{i}/t_{i} ∈ k(t_{1}, … t_{i−1}), or
3. t_{i} is algebraic over k(t_{1}, … t_{i−1}).

We say that an element u of an extension of k is liouvillian over k if it belongs to a liouvillian extension of k. Kolchin showed [85] that a linear homogeneous differential equation is solvable in terms of liouvillian functions (i.e., its Picard-Vessiot extension lies in a liouvillian extension of k) if and only if the component G^{0} of the identity of its Galois group G is solvable.

An algorithm to find a basis for the space of liouvillian solutions of a homogeneous linear differential equation L(y) = 0 with coefficients in an algebraic extension k of C(x) was presented in [136]. To get a taste of the ideas involved, we will describe an algorithm to decide if all solutions of L(y) = 0 are liouvillian. An effective version of the Lie-Kolchin Theorem asserts that in this case G will have a subgroup H such that the elements of H can be simultaneously put in upper triangular form and such that the index of H in G is bounded by a computable function I(n) of n, the order of L. If y is a common eigenvector of H, then σ(y′/y) = cy′/cy = y′/y so y′/y is left fixed by all elements σ of H. This implies that y′/y is algebraic over k of degree bounded by I(n) and so will be algebraic over C(x) of degree bounded by M = I(n)[k : C(x)]. Therefore, if L(y) = 0 is solvable in terms of liouvillian functions over k, L(y) = 0 has a solution y such that y′/y is algebraic over C(x) of degree bounded by M. To decide if L(y) = 0 has such a solution we will look for candidates for the minimal polynomial of u = y′/y. If p(u) = u^{N} + b_{N−1}(x)u^{N−1} + … + b_{0}(x), N ≤ M, is the minimal polynomial of such a u, then one can show that there exist solutions z_{1}, …, z_{N} of L(y) = 0 such that each b_{i} is the i^{th} symmetric function of the z′_{i}/z_{i}. From the exponents and determining factors at the singular points of L, we can bound the degrees of the numerators and denominators of the b_{i}. Therefore, if L(y) = 0 has only liouvillian solutions, it will have a solution y such that u = y′/y satisfies a polynomial over C(x) of degree at most M whose coefficients have numerators and denominators of effectively bounded degrees. Elimination theory then allows us to decide if such a solution exists and produces u. We then use the change of variables y = z exp(∫ u) to get a new equation L̃(z) = 0 of lower order and proceed by induction.

This algorithm is not a practical algorithm. For example when n = 2 and the equation has coefficients in ℚ(x), the bound for I(n) given in [136] is 384, 064 while it is known that a second order linear differential equation with a liouvillian solution will have a solution whose logarithmic derivative is algebraic of degree at most 12 (see the description of Kovacic’s algorithm below). In [155], Ulmer modified the algorithm in [136] by refining the group theoretic techniques involved. For second order equations, Ulmer’s algorithm yields the correct bound. He was not only able to get significantly improved bounds in all cases but he developed conditions to further narrow down the set of possible degrees of the logarithmic derivative of an exponential solution of L(y). Similar algorithms have been developed to find liouvillian solutions of inhomogeneous linear differential equations [45] and linear differential equations over more general fields [141]. A different approach to the general algorithm based on the fact that a linear differential equation has a liouvillian solution if and only if the Galois group has a semi-invariant linear form that factors into linear factors, is given in [147]. Finally, the substitution y = z exp(∫ u) and other order reducing substitutions are discussed in [2], [5], and [6].

In 1979, previous to [136], Kovacic [92] discovered an algorithm to decide if a second order linear differential equation L(y) = y′′ + ay′ + by = 0 with coefficients in C(x) has liouvillian solutions (see [51] or [119] for other expositions of this algorithm). With hindsight, this algorithm is also based on the idea that when such solutions exist, the equation will have a solution that is exponential over an algebraic extension of the base field. Yet Kovacic was able to produce an algorithm that is much more efficient than any general algorithm produced since because he also took advantage of knowledge of all the groups that can occur as Galois groups for second order equations. Kovacic’s first observation is that after the substitution y = exp(−\frac{1}{2} ∫ a)z one has a differential equation of the form z′′ − rz = 0 whose Galois group G is unimodular and has liouvillian solutions if and only if the original equation has solutions of this type. We will describe the rest of the algorithm using a trichotomy used by Ulmer in [155] to improve the results of [136]. If G is a group acting on a vector space V we say that G is reducible if V is reducible as a G-module. The group G is said to be imprimitive if G is not reducible and if there exist nontrivial, proper subspaces V_{1}, …, V_{r} of V such that V = V_{1} ⊕…⊕V_{r} and such that G permutes the V_{i}. We say G is primitive if it is not reducible and not imprimitive. If G ⊂ SL(2, C) is reducible then it must have an invariant onedimensional subspace (so the linear differential equation will have a solution that is exponential over C(x)) and Kovacic gives a very explicit algorithm to decide this. If G ⊂ SL(2, C) is imprimitive then G^{o} is diagonalizable and of index 2 in G. Kovacic shows that this implies that the equation will have linearly independent solutions y_{1}, y_{2} such that y_{1}y_{2} is exponential over a quadratic extension of C(x) and shows how one can decide this. Finally, if G ⊂ SL(2, C) is primitive, Kovacic shows that G is either SL(2) or a specific finite group of order 24, 48, or 120. Furthermore, in each of these latter three cases he shows that there are linearly independent solutions y_{1}, y_{2} and a homogeneous form f in y_{1}, y_{2} with constant coefficients, of degree 4, 6, and 12 respectively, such that f^{n} ∈ C(x) with n = 3, 2, or 1 respectively. In particular f will be exponential over C(x). Kovacic shows how one can decide each of these latter three cases. Since these are the only possibilities, we have that the equation has liouvillian solutions if and only if the Galois group is reducible, imprimitive or one of these three cases hold Furthermore, a decision procedure results from these considerations. Kovacic is able to construct a liouvillian solution when one exists and is also able to give very strong necessary conditions by looking at the possible exponents that can occur at singular points (these conditions are generalized to third order equations in [146]). We note that Kovacic’s algorithm finds a solution of the form exp(∫ u) where u is algebraic over C(x) when the equation has liouvillian solutions. When the equation has only algebraic solutions, the algorithm does not find the minimal polynomials of such solutions, even when the Galois group is one of the finite primitive groups. For these groups this task was begun in [55] and [56] and completed and generalized to third order equations in [144] and [145].

Several improvements have been made on Kovacic’s original algorithm. Duval and Loday-Richaud [51] have given a more uniform treatment of the considerations concerning singular points and have as well applied the algorithm to decide which parameters in the hypergeometric equations (as well as several other classes of second order equations) lead to liouvillian solutions. In [119], van der Put shows how the algorithm can be simplified if the equation has only one or two singular points. In [157], Ulmer and Weil improve the algorithm by using the observation that any homogeneous polynomial with constant coefficients of degree m in any number of solutions of the equation must satisfy an auxiliary equation L^{◯ s m}(y) = 0 called the m^{th} symmetric power of L (see also [37]). They then show that except in the reducible case, one can decide if there is a liouvillian solution (and find one) by looking for solutions of appropriate symmetric powers that lie in C(x). This eliminates some of the nonlinear considerations of Kovacic’s algorithm. A general necessary and sufficient condition for the existence of liouvillian solutions in terms of the existence of G-invariant homogeneous forms is given in [147]. If the equation has coefficients in C_{0}(x) where C_{0} is not algebraically closed, it is important to know in advance how large an algebraic extension of C_{0} is required. In [66] and [164] sharp results are given for Kovacic’s algorithm as well as a general framework for higher order equations. In [156], sharp results are given concerning what constant fields are needed for equations of all prime orders. Applications of the algorithm to questions concerning integrability of Hamiltonians are given in [9] and the references cited there. We finally note that it was recently discovered that an algorithm (with some mistakes) to find the minimal polynomial of an element u algebraic over C(x) with exp(∫ u) satisfying a given second order linear differential equation was found by Pepin [113] in 1881. The problem of deciding when an n^{th} order linear differential equation has a solution y with y′/y algebraic is also discussed by Marotte in [102] and concrete results are given when n = 2, 3, 4.

The question of deciding if a linear differential equation has only algebraic solutions (or even one nonzero algebraic solution) has a long history. In 1872, Schwarz [134] gave a list of those parameters for which the hypergeometric equation has only algebraic solutions (for higher hypergeometric functions this was done by Beukers and Heckman [24]). Using his algorithm, Pépin [113] was able to reproduce this list as well. Using invariant theory, Fuchs [55], [56] was able to find the minimal polynomial of an algebraic solution of a second order linear differential equation assuming that the Galois group is the finite imprimitive group of order 48 or 120 (this method is generalized in [145]). In [83], [84], Klein shows that any second order linear differential equation with only algebraic solutions comes from some hypergeometric equation via a rational change in the independent variable x = r(z). This approach was turned into an algorithm by Baldassarri and Dwork [10]. Jordan [76] considered the problem of deciding if a linear differential equation of order n has only algebraic solutions. He showed that a finite subgroup of GL(n) has an abelian normal subgroup of index bounded by a computable function f(n) of n (this fact and its generalizations are at the heart of the algorithms for finding liouvillian solutions in [136] and [155] described above). This implies that such an equation has a solution whose logarithmic derivative is algebraic of degree at most f(n). Jordan’s approach was made algorithmic in [135] (see also [28] and [112] for similar but incomplete algorithms due to Boulanger and Painlevé). It should be noted that the algorithms of Boulanger, Klein, Painlevé, and Pépin, are all incomplete in at least one regard. Each of these algorithms, at one point or another, is confronted with the following problem: Given an element u, algebraic over C(x), decide if exp(∫ u) is also algebraic over C(x). Boulanger refers to this as Abel’s Problem ([28], p. 93) and none of these authors gives an algorithm to answer this question. In 1970, Risch [130] showed that this problem could be solved if one could decide if a given divisor on a given algebraic curve is of finite order. Risch showed how one could solve this latter problem by reducing the jacobian variety of the curve modulo two distinct primes and bounding the torsion of the resulting finite groups. For other work concerning Abel’s Problem, see [10], [31] [44], [151], [161], [162]. The introduction to [102], the book [59] and the article [58] give historical accounts of work concerning algebraic solutions of linear differential equations.

Over the field C((x)) of formal power series, all linear differential equations are solvable in terms of liouvillian functions (see section 2.4.2). An algorithm to solve the direct problem for second order equations whose Galois group is a subgroup of SL(2) is given in [61].

The question of when a linear differential equation has liouvillian or algebraic solutions leads to the general question of when such an equation can be solved in terms of other special functions. An equivalent definition of liouvillian extension is the following; an extension E = k(t_{1}, … t_{r}) of k is a liouvillian extension of k if each t_{i} is either algebraic over k(t_{1}, … t_{i−1}) or satisfies a first order linear differential equation t′_{i} + at_{i} = b with a, b ∈ k(t_{1}, … t_{i−1}). We can generalize this to define a linear differential equation of order n to be solvable in terms of lower order equations if its Picard-Vessiot field lies in a field of the form k(t_{1}, … t_{r}) where each t_{i} is either algebraic over k(t_{1}, … t_{i−1}) or satisfies a linear differential equation of order less than n over k(t_{1}, … t_{i−1}). In [139] it is shown that a linear differential equation of order n is not solvable in terms of lower order linear differential equations if and only if the Lie algebra 𝔤 of G has the following two properties:

• 𝔤 is simple, and

• 𝔤 has no nontrivial representation of degree less than n.

An algorithm for third order equations is described in [137] (see also [138] for related material). An algorithm to solve linear differential equations in terms of hypergeometric functions is given in [114].

2.4. Calculating Galois Groups.

2.4.1. Algebraic Methods. The key to understanding modern algebraic techniques for calculating Galois groups comes from the formulation of the Galois theory in terms of Tannakian Categories [18], [19], [21], [46], [47], [48], [78]. Instead of a linear differential equation we consider a connection, that 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., [64]). If e_{1}, …, e_{n} is a k-basis of M, we may write

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

where A = (a_{i,j}) ∈ M(n, k). 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 ∈ M(n, k) one can use equation 2.3 to define a connection ∇_{A} on k^{n}.

All of the usual constructions of linear algebra can be carried out for connections. 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

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

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.4 holds. Finally we note that on any finite dimensional D-module M one can define a natural connection via the equation ∇u = Du.

The relationship with linear differential equations or, more specifically linear operators, is the following. 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

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

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 [7], [17], [20], [46], [75], [80], [123], 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}. Finding an equivalent linear operator allows one to reduce questions concerning systems (e.g., existence of rational or liouvillian solutions) to the corresponding questions for linear operators.

The Picard-Vessiot extension K associated to a system Y′ = AY is a field of the form k(z_{1,1}, … z_{n,n}) having no new constants where Z = (z_{i,j}) is an invertible matrix satisfying Z′ = AZ. The columns of Z span the solution space V of this equation. Equivalent equations have isomorphic Picard-Vessiot extensions and so we can define the Picard-Vessiot extension K corresponding to a connection. If (M̃, ˜∇) is a connection gotten from (M, ∇) via iteration of the operations of direct sums, tensor products and duals, we say that (M̃, ˜∇) is a construction of (M, ∇). If V is the solution space in K^{n} of the connection (M, ∇) we can also consider all iterations of the operations of direct sums, tensor products and duals on V and call a resulting vector space Ṽ a construction of V. One can show that if the same sequence of operations are applied to both (M, ∇) and V, resulting in (M̃, ˜∇) and Ṽ, then the solution space of (M̃, ˜∇) is Ṽ. Let M be the collection of all subconnections of all constructions of (M, ∇) and let V be the collection of all solutions spaces of elements of M. Clearly, V is a collection of certain subspaces of constructions of V. For any construction Ṽ of V there is a natural representation GL(V) ↪ GL(Ṽ). One can show [47], [48], [78], that the group

G = {g ∈ GL(V) | g(W) = W for all W ∈ V}

is the Galois group of K over k. In more pedestrian terms, reducibility properties of the solutions spaces of associated differential equations determine the Galois group of a given differential equation.

This idea is at the heart of many results determining the Galois groups of linear differential equations. One distinguishes a certain group from other groups by the manner in which constructions decompose into invariant subspaces. One then gives criteria (or uses the tests described in Section 2.2) for the associated connections to decompose into the subconnections in the same way. For example, Beukers, Brownawell and Heckman show in [23] that for a linear algebraic group G ⊂ GL(V), G modulo its center is infinite and the second symmetric power S^{2}V is irreducible under G if and only if G is an extension by scalars of SL(V) or Sp(V). Using this they were able to show that large classes of hypergeometric equations have Galois groups of this type (for related work see also [65]). Katz and Pink [82] give a sufficient condition for the Galois group of a linear differential equation to contain SL(n), Sp(n) or SO(n). The differential Galois groups of all irreducible confluent hypergeometric differential equations were determined by Katz and Gabber,[79], [81] using representation theoretic characterizations of semisimple Lie algebras. An algebraic study of the Galois groups of reducible hypergeometric equations was made by Boussel in [29]. We note that many of the calculations were motivated by questions in the theory of transcendental numbers where one needs to know if certain functions satisfying differential equations and their derivatives are algebraically independent. This can be translated into questions concerning the dimension of certain Galois groups. Kolchin also wrote on this question. In [86], Kolchin calculated the Galois groups of Picard-Vessiot extensions generated by sets of Bessel functions but he relied on simple group theoretic considerations rather than the representation theoretic approach described above.

Algorithms based on this philosophy for computing Galois groups and their properties are given in [144, 145, 146]. For example, it is shown that L(y) = y′′ + ry = 0 has liouvillian solutions if and only if L^{◯ s 6}(y) is reducible, where L^{◯ s 6}(y) = 0 is the seventh order equation whose solution space is the sixth symmetric power of the solution space of L(y) = 0. We note that if L is irreducible its Galois group is reductive. This implies that L^{◯ s 6} will be completely reducible and so its reducibility can be tested using the results of [143]. Similar criteria are given for properties of third order equations as well as criteria to determine if a particular group is the Galois group of such an equation. Fourth order equations have been treated by Hessinger in [67].

If one knows in advance that a linear differential equation has a reductive Galois group (that is, if the equation is completely reducible), then one can calculate a presentation of the associated Picard-Vessiot extension and its Galois group [43]. In [41, 40], Compoint showed that if a Picard-Vessiot extension has a reductive unimodular Galois group then the relations defining the Picard-Vessiot 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}] 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 a 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 furthermore is known that given such an m, one can calculate the generators of I directly from the equation Y′ = AY, without a priori knowledge of the Galois group [73]. 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 generators of the ring of invariants. The main result of [43] is that there is an effective method to find such a bound. It is also shown how this result can be extended to equations with arbitrary (not necessarily unimodular) reductive Galois groups as well as be used to calculate G/G^{o}, that is, the group of connected components of the Galois group of a linear differential equation with arbitrary Galois group.

Reduction modulo a prime can also be used to get information concerning the Galois group. Let L(y) = 0 be a linear differential equation with coefficients in k_{0}(x) where k_{0} is a number field. For almost all primes 𝔭 of k_{0}, it makes sense to reduce the coefficients of L modulo 𝔭 and get an operator L_{𝔭} with coefficients in k_{𝔭}(x), where k_{𝔭} is the residue field at 𝔭. A conjecture of Grothendieck states: All solutions of L(y) = 0 are algebraic over k_{0}(x) if and only if, for almost all 𝔭, the equation L_{𝔭}(y) = 0 has a full set of solutions in k_{𝔭}(x), [19], [38], [74], [78], [120]. In [122], van der Put uses the classification of differential equations in positive characteristic and ideas around the Grothendieck conjecture to factor differential operators and find symbolic solutions over ℚ(x).

2.4.2. Analytic Methods. Classically [59], analytic/topological techniques were used to associate a group with a differential equation Y′ = AY having coefficients in ℂ(x). This group is defined as follows [93]. Let {α_{1}, …, α_{m}} be the singular points of the equation on the Riemann sphere S^{2}, let α_{0} ∈ S^{2} − {α_{1}, …, α_{m}} and let {y_{1}, …, y_{n}} be a fundamental set of solutions, analytic in a neighborhood of α_{0}. If [γ] ∈ π_{1}(S^{2} − {α_{1}, …, α_{m}}, α_{0}), one can analytically continue each solution y_{i} along γ. The resulting function y_{i}^{γ} is independent of the homotopy class representative γ used and is again a solution of Y′ = AY. From this one sees that there is an invertible matrix A_{γ} such that (y_{1}^{γ}, …, y_{m}^{γ}) = (y_{1}, … y_{n})A_{γ}. Furthermore, the map [γ] ↦ A_{γ} is a group homomorphism of π_{1}(S^{2} − {α_{1}, …, α_{m}}, α_{0}) into GL(n, ℂ). Selecting a different fundamental set of solutions at α_{0} will give a conjugate homomorphism. The conjugacy class of this homomorphism is called the monodromy representation of the differential equation and the conjugacy class of the image is called the monodromy group [118]. The monodromy group is contained in the Galois group, but the Galois group can be strictly larger. For example the equation y′ − y = 0 has trivial monodromy group since π_{1}(S^{2} − ∞, 0) = 0 while its Galois group is ℂ^{∗}. We say that a singular point α of the operator L is a regular singular point if for any open sector Ω at α, all solutions y, analytic in Ω, satisfy lim_{x→α} x^{N}y = 0 for some N ≥ 0. An equation is called regular if all of its singular points are regular. Fuchs showed that for a differential operator, α ∈ ℂ is a regular singular point if and only if the coefficient of D^{n−i} has a pole of order at most i. For a system Y′ = AY, α ∈ ℂ is a regular singular pount if and only if there is a U ∈ GL(n, C((x − α))) such that U′U^{−1} + UAU^{−1} = (x − α)^{−1}A_{0} for some constant matrix A_{0} (this latter property is decidable [12]). It was known classically ([131], Section 160) that if all singular points are regular singular points then the monodromy group is Zariski dense in the Galois group. In general this is not true as the above example shows. For arbitrary singular points Ramis [103], [124], [126],

[125] was able to define analytically a subgroup of each local Galois group (defined below) that is dense in this latter group.

To understand Ramis’s results, we begin with some definitions (we shall follow the presentation in [107]; see also [121]). Let α ∈ S^{2} and let t_{α} be the local coordinate of S^{2} at α. Let ℂ({t_{α}}) be the field of fractions of the ring of convergent power series at α and let ℂ((t_{α})) be the field of fractions of the ring of formal power series. Any differential equation Y′ = AY with A ∈ M_{n}(ℂ(x)) can be thought of as a differential equation over ℂ({t_{α}}) or ℂ((t_{α})) as well. The Galois group of Y′ = AY over ℂ({t_{α}}) is called the local Galois group at α and the Galois group over ℂ((t_{α})) is called the formal Galois group at α. It is known [107] that the Zariski closure of the group generated by all local Galois groups is the Galois group of the equation over ℂ(x). For simplicity of notation, we shall restrict ourselves to the situation where α = 0.

A differential equation Y′ = AY with A ∈ ℂ({x}) admits a formal solution

Ŷ = Ĥ(x)x^{L}e^{Q(t)} (2.6)

where t = x^{1/r}, r a positive integer , L ∈ M_{n}(ℂ), Ĥ ∈ GL(n, ℂ((x))) and Q = diag(q_{1}, … q_{n}) where q_{i} ∈ t^{−1}ℂ[t^{−1}], i = 1, …, n (this is the matrix version of formula 2.1). Furthermore, one may assume that the polynomials q_{i} are permuted by the map t ↦ te^{2iπ/r}.

We now define two groups. The first is the formal monodromy group G_{M}. This is the group generated by the matrix M̂ defined Ŷ (te^{2iπ/r}) = Ŷ M̂. The second is the exponential torus T . This is the Galois group of ℂ((t))⟨e^{q_{1}}, …, e^{q_{n}}⟩ over ℂ((t)). Both of these groups may be identified with subgroups of the local Galois group of Y′ = AY at 0 and both of these groups may be calculated once one has the formal solution 2.6. It can be shown that the Zariski closure of the group generated by G_{M} and T is precisely the formal Galois group at 0 [19], [107]. Furthermore, when 0 is a regular singular point, the local and formal Galois groups coincide. For general singular points, this is not true and one needs additional elements to generate G topologically.

To define these elements, Ramis shows that one can canonically select open sectors S_{1}, …, S_{m} at 0 that fill out a neighborhood of 0 and canonically (in fact, functorially) select fundamental solution matrices Y_{i} of Y′ = AY, holomorphic in S_{i} (this latter process is called multisummation [97], [99], [121]). On the intersection S_{i} ∩ S_{i+1} the fundamental solution matrices must differ multiplicatively by a constant matrix S_{i}, Y_{i} = Y_{i+1}S_{i}. The matrices S_{i} are called the Stokes matrices. The fundamental result of Ramis is that the Zariski closure of the group generated by the formal monodromy, the exponential torus and the Stokes matrices is the local Galois group ([103] or [98] for a proof based on Tannakian considerations). When the differential equation has at most two singular points, at worst a regular one at 0 and a possibly irregular one at ∞, then one also knows that the Zariski closure of the local Galois group at infinity is the entire Galois group of the equation over ℂ(x).

In general, there is no effective procedure to compute the Stokes matrices. There are numerical schemes to approximate the canonically selected holomorphic functions on the sectors (and so approximate the Stokes matrices) [111] as well as to directly approximate the Stokes matrices for systems of dimension 2 [96]. For large classes of differential equations, one has integral representations of the solutions and this does allow one to calculate the Stokes matrices. This has been done by Duval and Mitschi [50], [52] and applied to calculate Galois groups of some confluent hypergeometric differential equations. This work has been extended and generalized by Mitschi [106, 107] to calculate the Galois groups (over ℂ(x)) of large classes of confluent hypergeometric differential equations. Toulouse [149] uses this approach to calculate Galois groups of classes of equations of the form Y′ = (A_{0} + xA_{1})Y where A_{i} ∈ M_{n}(ℂ) with n = 2 or 3.

3. The Inverse Problem

The inverse problem is: Given a differential field k, what groups are Galois groups of Picard-Vessiot extensions of k? As Kolchin already noted in the extract quoted at the beginning of this article, the answer depends both on k and G. Expanding on Kolchin’s comments, let k = ℂ and let Y′ = AY be a differential equation with A ∈ M_{n}(ℂ). Classically, it is known that by reducing the matrix A to rational normal form one can reduce the problem of finding solutions of this equation to the problem of finding solutions of constant coefficient linear differential equations L(y) = 0 of order possibly greater than one. All solutions of such equations are of the form y = ∑ p_{i}(x)e^{α_{i}x} where p_{i} ∈ ℂ(x) and the α_{i} ∈ ℂ.

Therefore the associated Picard-Vessiot extension K lies in a field of the form F = ℂ(x, e^{α_{1}x}, …, e^{α_{t}x}). One sees that F is a Picard-Vessiot extension of ℂ with Galois group G = ℂ × ℂ^{∗} × … × ℂ^{∗}. Therefore the Galois group of K over ℂ is a quotient of such a group, which can be shown to be of the form ℂ^{s} × ℂ^{∗t} where s and t are nonnegative integers and 0 ≤ s ≤ 1. Conversely, one can adjoin appropriate elements to ℂ and show that any such group is a Galois group. Group theoretically, one can characterize such groups as linear algebraic groups that are (i) connected, (ii) abelian and (iii) whose largest unipotent subgroup has dimension at most one (a linear group is unipotent if all of its elements are unipotent). These three properties therefore characterize the groups that can appear as Galois groups of Picard-Vessiot extensions of ℂ. Once again, one can approach the general problem using algebraic and analytic techniques.

3.1. Algebraic Methods. Preceding Kolchin’s 1966 talk, Bialynicki-Birula [25] had already shown that, for any differential field k of characteristic zero with algebraically closed field of constants C, if the transcendence degree of k over C is finite and nonzero then any connected nilpotent group is a Galois group of a Picard-Vessiot extension of k. Goldman [57] developed the notion of a generic differential equation with group G ⊂ GL(n), that is, a linear differential operator L with parameters such that any linear differential operator with Galois group contained in G is a specialization of L (this is analogous to the notion E. Noether developed for algebraic equations). In his thesis [105], Miller developed the notion of a differentially hilbertian differential field and gave a sufficient condition for the generic equation of a group to specialize over such a field to an equation having this group as a Galois group.

A breakthrough was made by Kovacic [89], [90] who proposed an ultimately successful program to solve the inverse problem for connected groups (over fields of finite, nonzero transcendence degree over their algebraically closed field of constants) and solved the problem for connected solvable groups. A key element of Kovacic’s program is an emphasis on the role of the Lie algebra of the Galois group. Let G be a connected linear algebraic group defined over the algebraically closed field of constants C of a differential field k and let 𝔤 be its Lie algebra. We denote by 𝔤_{k} the k-points in the Lie algebra, that is, 𝔤_{k} = 𝔤_{C} ⊗_{C} k. Kovacic shows that if A ∈ 𝔤_{k} then the Picard-Vessiot extension of k corresponding to Y′ = AY has Galois group H that is a subgroup of G. Furthermore, for k = C(x) (or any cohomologically trivial field), if the Galois group H ⊂ G of Y′ = AY with A ∈ 𝔤_{k} is connected, then there exists an invertible g ∈ G(k) such that g′g^{−1} + gAg^{−1} ∈ 𝔥_{k}, where 𝔥 is the Lie algebra of H. In particular, to construct a differential equation Y′ = AY with coefficients in C(x) having a given connected Galois group G one must find a matrix A ∈ 𝔤_{k} such that:

1. the Galois group of Y′ = AY is connected and

2. for any g ∈ G(k), g′g^{−1} + gAg^{−1} does not lie in the Lie algebra of a smaller

connected group. Let us consider an example. Let

G = \{( \begin{matrix}1 & c \\ 0 & 1 \end{matrix} ) | c ∈ C\}

G is isomorphic to the additive group C. The Lie algebra of this group is

𝔤 = \{( \begin{matrix}0 & c \\ 0 & 0 \end{matrix} ) | c ∈ C\}

If we start with a matrix

A = ( \begin{matrix}0 & f \\ 0 & 0 \end{matrix} )

with f ∈ C(x) then the equation Y′ = AY will have a Galois group that is an algebraic subgroup of the additive group C. The only such groups are the trivial group and C itself, so the Galois group will be connected. If the Galois group is trivial then there is an element

g = ( \begin{matrix}1 & h \\ 0 & 1 \end{matrix} ) ∈ G(C(x))

such that g′g^{−1} + gAg^{−1} is the zero matrix. This is equivalent to the existence of an element h ∈ C(x) such that h′ + f = 0, that is, f has an antiderivative in C(x). On can easily select an f so that this is not the case (e.g., f = 1/x) and so find a differential equation whose Galois group is the additive group C.

This criterion can be thought of in more geometric terms. Kolchin showed ([88] or the paper of Borel [26] in this volume) that a Picard-Vessiot extension of a differential field k with Galois group G is the function field of a principal homogeneous G-space. If k = C(x) or any other cohomologically trivial field, all principal homogeneous spaces for a connected group G are isomorphic to G. Therefore, a Picard-Vessiot extension K of C(x) can be thought of as the function field of a principal G-bundle over the projective line. The derivation on K gives a connection on this bundle and the condition that for any g ∈ GL(n, k), g′g^{−1} + gAg^{−1} does not lie in the Lie algebra of a smaller connected group is equivalent to the differential geometric condition that the connection is not reducible to a connection on an H-bundle for some connected subgroup H of G.

Another key element of Kovacic’s program was to give a procedure to inductively apply the above criterion to lift a solution of the inverse problem for G/R_{u} to a solution for the group G (R_{u} is the unipotent radical of G, that is, the largest normal subgroup of G all of whose elements are unipotent). Using this, Kovacic showed that to give a complete solution of the inverse problem for connected groups, one needed only to solve this problem for reductive groups (since G/R_{u} is reductive). He was able to solve the problem for tori and so could give a solution when G/R_{u} is a torus, that is, when G is a solvable group. He furthermore showed that one could reduce the problem to the case when G is the power of a simple connected linear algebraic group (see also [60] for extensions and modifications of Kovacic’s methods to partial differential fields).

The solution of the inverse problem for such groups (or more generally semisimple groups) is one of the main contributions of [108] (see [109] for a simplified exposition). In this paper, the authors use an idea of Kovacic to show that to solve the inverse problem for connected groups over a differential field k of finite transcendence degree over its algebraically closed field of constants C it is enough to solve this problem for connected groups over C(x). For this field and connected linear algebraic groups G, the authors show there are integers d(G) and e(G) depending only on G such that G is the Galois group of an equation of the form

Y′ = (\frac{A_{1}}{x − α_{1}} + … + \frac{A_{d(G)}}{x − α_{d(G)}} + A_{∞})Y

where A_{i}, i = 1, …, d(G) are constant matrices and A_{∞} is a matrix with polynomial entries of degree at most e(G). In particular, the only possible singularities of this system are d(G) regular singular points in the finite plane and a (possibly irregular) singular point at infinity. The integers d(G) and e(G) are defined as follows. Let G be a connected linear algebraic group and let R_{u} be its unipotent radical and P a Levi factor, that is, a reductive group P such that G = R_{u}⋊P. The group R_{u}/(R_{u}, R_{u}), where (R_{u}, R_{u}) is the commutator subgroup, is a commutative unipotent group and so isomorphic to a vector group C^{n}. The group P acts on R_{u} by conjugation and this action factors to an action on R_{u}/(R_{u}, R_{u}). Therefore we may write R_{u}/(R_{u}, R_{u}) = U_{1}^{n_{1}} ⊕ … ⊕ U_{s}^{n_{s}}, where each U_{i} is an irreducible P -module. We shall assume that U_{1} is the trivial one dimensional P -module (and so allow the possibility that n_{1} = 0). We may write P = T · H, where T is a torus and H is a semisimple group. Let m_{i} = n_{i} if the action of H on U_{i} is trivial and let m_{i} = n_{i} + 1 if the action of H on U_{i} is nontrivial. Let N = 0 if H is trivial and N = 1 if H is nontrivial. We define the defect d(G) of G to be the number n_{1} and the excess e(G) of G to be max{N, m_{2}, …, m_{s}}. We note that any two Levi factors are conjugate so that these numbers are independent of the choice of P. Furthermore, one can show that d(G) is the dimension of R_{u}/(G, R_{u})

For example, for any connected reductive group G, we have that R_{u}(G) = (0). Therefore d(G) = 0 and e(G) = 1 so there exists constant matrices A and B such that G is the Galois group of an equation of the form Y′ = (A + xB)Y. It is also shown in [108] that the bound on the number of singular points given by d(G) is sharp: there are examples of groups G that cannot be Galois groups of differential equations with fewer than d(G) + 1 singular points. Finally, the proof in [108] is constructive.

Kovacic also considered fields that are not finitely generated over their constant subfields. He showed that a solvable connected linear algebraic group G is a Galois over C((x)) if and only if it is commutative and its unipotent radical R_{u} is of dimension at most one. Equation 2.1 implies that the Picard-Vessiot extension of a linear differential equation over C((x)) lies in liouvillian extension of C((x)). Therefore, the identity component G^{o} of the Galois group G is solvable (in fact, G/G^{o} is cyclic so G is solvable). Therefore Kovacic’s result implies that a connected group is a Galois group over C((x)) if and only if it is commutative and its unipotent radical is of dimension at most 1. Kovacic also considers the field C({x}) of convergent power series and shows that a connected solvable linear algebraic group is a Galois group over this field if and only if the unipotent radical of the center of G/(R_{u}, R_{u}) has dimension at most one. Using the notation of the previous paragraphs, this is equivalent to the condition that d(G) ≤ 1. The complete characterization of Galois groups over C({x}) when C = ℂ rests on analytic techniques due to Ramis and will be described in the next section.

It should be noted also that Kovacic [89], [90] considered the inverse problem for arbitrary connected algebraic groups (not just linear groups), that is, classifying those groups that arise as Galois groups of strongly normal extensions. He showed that one can reduce this problem to the inverse problem for connected linear algebraic groups and for abelian varieties. In [89] he solved the problem for abelian varieties over fields of finite nonzero transcendence degree over their algebraically closed constant subfields. In [116], Pillay develops a Galois theory of differential fields where the Galois groups are differential algebraic groups. He also considers inverse problems in this context.

In the soon to be published second edition of [100], Magid uses geometric techniques to solve the inverse problem for several classes of groups. The proof given in the first edition of [100] to demonstrate that all connected groups having no subgroups of codimension one are Galois groups (Theorem 7.13) is flawed.

It should be finally noted that algebraic techniques have not yet been successful in attacking the inverse problem for groups that are not connected. At present, one must rely on analytic techniques.

3.2. Analytic Methods. Analogous to the inverse problem in differential Galois theory, there is an inverse problem in the analytic theory of linear differential equations. This is the Riemann-Hilbert Problem. In its weakest form the problem asks if, for any representation ρ : π_{1}(S^{2} − Σ) → GL(n, ℂ) of the Riemann Sphere S^{2} minus a finite set Σ of points, does there exist a differential equation Y′ = AY, A ∈ M_{n}(ℂ(x)) with regular singular points at the points of Σ whose monodromy representation is given by ρ. In this form, the answer is always yes. This positive answer can be used to show that there is an equivalence of categories between the category of connections having only regular singular points in some set Σ ⊂ S^{2} and the category of finite dimensional representations of π_{1}(S^{2} − Σ). This equivalence is called the Riemann-Hilbert Correspondence and, in this form, was established and generalized by Deligne [46]. A more restrictive form of the Riemann-Hilbert problem is to ask if there is a differential equation of the form

Y′ = ∑_{α∈Σ} \frac{A_{α}}{x − α}Y

(with A_{α} ∈ M(n, ℂ) and ∑ A_{α} = 0) having ρ as its monodromy representation. Bolibruch has shown that the answer to this question is no for certain representations (for a history of this problem and its solution, see [15] or [8]).

C. and M. Tretkoff [152] used the solution of the weak Riemann-Hilbert Problem to solve the inverse problem for all linear algebraic groups G over the field ℂ(x). They showed that any such G contains a Zariski - dense finitely generated subgroup H. One can select generators h_{1}, … h_{m} of H such that ∏_{i=1}^{m} h_{i} = 1 and therefore there exists a representation ρ of the fundamental group of the Riemann Sphere minus m points onto H. Using the solution of the weak Riemann-Hilbert Problem, there is a differential equation Y′ = AY with regular singular points whose monodromy representation is given by ρ. Since, for equations with regular singular points, the monodromy group is Zariski dense in the Galois group, the equation has Galois group G.

Ramis [103], [104] has shown how one can use analytic methods to completely solve the inverse problem over ℂ({x}). To do this he defined a wild monodromy group π_{1,S} and showed that it has the following two properties:

1. If Y′ = AY is a differential equation with A ∈ GL(n, ℂ({x}), there is a representation ρ : π_{1,S} → GL(n, ℂ) whose image is the group generated by the formal monodromy, exponential torus and Stokes matrices of this equation.

2. Any representation ρ : π_{1,S} → GL(n, ℂ) can be realized as in 1.

These two facts yield a Riemann-Hilbert Correspondence between the categories of local connections (i.e., connections over the field ℂ({x})) and finite dimensional representations of π_{1,S}. To define the wild monodromy group, one notes that the possible formal monodromy groups are all homomorphic images of ℤ. Furthermore, the possible exponential tori form an inverse system and we let T denote their inverse limit. There is a natural action of ℤ on T and so we can form their semi-direct product π_{1,Sf} = ℤ ⋉ T . The group π_{1,Sf} is called the wild formal fundamental group and any formal Galois group is a quotient of this group. One can furthermore define a group R such that any group generated by Stokes matrices is a homomorphic image of R and an action of π_{1,Sf} on R [104]. The group π_{1,S} is defined to be π_{1,Sf} ⋉ R.

We have already noted that the group generated by the formal monodromy, exponential torus and Stokes matrices is Zariski dense in the Galois group of the equation over ℂ({x}). Therefore to solve the inverse problem over this field it is enough to identify those linear algebraic groups G containing a Zariski dense homomorphic image of π_{1,S}. Ramis gave necessary and sufficient conditions on the Lie algebra of G for this to be true and equivalent group theoretic conditions were given in [110]. The final result is the following [128] (see also [127], [129]): a linear algebraic group G with identity component G^{o} and unipotent radical R_{u} is a Galois group of a Picard-Vessiot extension of ℂ({x}) if and only if

1. the finite group G/G^{o} is cyclic,

2. the dimension of R_{u}/(R_{u}, G^{o}) is at most one, and

3. the group G/G^{o} acts trivially on R_{u}/(R_{u}, G^{o}) Ramis is furthermore able to show that these three conditions are equivalent to the quotient G/L(G) being the Zariski closure of a cyclic group, where L(G) is the subgroup of G generated by all the tori of G. Ramis took this local result and combined it with a glueing technique to show that any linear algebraic group is the Galois group of a differential equation Y′ = AY over ℂ(x) (or even over an algebraic extension of ℂ(x)) . Furthermore he can bound the number and type of singular points in terms of the number of generators of any Zarisk-dense subgroup of G/L(G).

Analytic methods only work when the field of constants is ℂ. Nonetheless, some transfer techniques have been developed to allow one to draw conclusions about C(x) where C is any algebraically closed field. Let L(n, m) be the vector space of differential operators

L = ∑_{i=0}^{n} ∑_{j=0}^{m} a_{i,j}x^{j}D^{i}

of order at most n whose coefficients are polynomials of degree at most m with coefficients in ℂ. Let G be a linear algebraic group, V a finite dimensional Gmodule and let L(n, m, G, V) be the set of operators in L(m, n) with Galois group G and solution space G-isomorphic to V. In general, L(n, m, G, V) is not a Zariskiclosed subset (or even a constructible subset) of L(n, m). For example, an operator L_{c} = xD − c, c ∈ ℂ, has its solution space spanned by x^{c}. Therefore it has Galois group ℂ^{∗} if and only if c is not rational. This implies that L(n, m, ℂ^{∗}, ℂ) where ℂ^{∗} acts on ℂ by multiplication, cannot be constructible. Note that c is an exponent at the singular point 0. This suggests that one fix a certain amount of information at the singular points. Let S be a finite subset of k_{0}[x], k_{0} ⊂ ℂ and let L(n, m, S, G, V) be the set of L ∈ L(n, m, G, V) such that at any singular point the exponents and determining factors at that point lie in S (c.f., the discussion following equation 2.1). In [142], large classes of groups are determined for which this set is constructible. To be more precise, let G be a linear algebraic group with identity component G^{o}. Let Kerχ(G) be the intersection of the kernels of all characters χ : G^{o} → ℂ^{∗}. The group G^{o}/Kerχ(G^{o}) is abelian (in fact it is a torus) and so one can use the sequence

1 → G^{o}/Kerχ(G^{o}) → G/Kerχ(G^{o}) → G/G^{o} → 1

to define an action of G/G^{o} on G^{o}/Kerχ(G^{o}). The main result of [142] is: if the action of G/G^{o} on G^{o}/Kerχ(G^{o}) is trivial, then for any fixed G-module V and fixed n, m and S, the set L(n, m, S, G, V) is constructible and defined over k_{0}. For example, connected groups, finite groups, and groups where G^{o} is semisimple all satisfy these hypotheses. It is also shown in [142] that the assumption of triviality of the action is crucial; there is a family of second order differential operators with regular singular points and fixed exponents such that their Galois groups are all subgroups of ℂ^{∗} ⋊ ℤ/2ℤ and such that the set of parameters for which the Galois group is all of ℂ^{∗} ⋊ ℤ/2ℤ is not constructible.

If G is a group satisfying the hypothesis of this result, one can use the results of the Tretkoffs or Ramis to show that for any faithful G-module V and for some fixed n, m and S, the set L(n, m, S, G, V) contains a ℂ-point. The Hilbert Nullstellensatz then implies that it will contain a point in any algebraically closed field containing k_{0}. This allows one to solve the inverse problem for many classes of groups over C(x) where C is an arbitrary algebraically closed field of characteristic zero.

References

1. S. A. Abramov, Rational solutions of linear differential and difference equations with polynomial coefficients (in Russian), Journal of Computational Mathematics and Mathematical Physics 29 (1989), no. 11, 1611–1620.

2. S.A. Abramov, On D’Alembert substitution, Proceedings of the 1993 International Symposium on Symbolic and Algebraic Computation (ISSAC’93) (M. Bronstein, ed.), ACM Press, 1993, pp. 20–26.

3. S.A. Abramov, M. Bronstein, and M. Petkovšek, On polynomial solutions of linear operator equations, Proceedings of the 1995 International Symposium on Symbolic and Algebraic Computation (ISSAC’95) (A. H. M. Levelt, ed.), ACM Press, 1995, pp. 290–296.

4. S.A. Abramov and K. Yu. Kvansenko, Fast algorithms for rational solutions of linear differential equations with polynomial coefficients, Proceedings of the 1991 International Symposium on Symbolic and Algebraic Computation (ISSAC’91) (S. M. Watt, ed.), ACM Press, 1991, pp. 267–270.

5. S.A. Abramov and M. Petkovšek, D’Alembert solutions of linear differential and difference equations, Proceedings of the 1994 International Symposium on Symbolic and Algebraic Computation (ISSAC’94) (J. von zur Gathen, ed.), ACM Press, 1994, pp. 169–180.

6. S.A. Abramov and E. V. Zima, D’Alembert solutions of inhomogeneous linear equations (differential, difference and otherwise), Proceedings of the 1996 International Symposium on Symbolic and Algebraic Computation, ACM Press, 1996, pp. 232–239.

7. K. Adjamagbo, Sur l’effectivité du lemme du vecteur cyclique, Comptes Rendus de l’Académie des Sciences, Paris 306 (1988), 543 – 546.

8. D. V. Anosov and A. A. Bolibruch, The Riemann-Hilbert Problem, Vieweg, Braunschweig, Wiesbaden, 1994.

9. A. Baider, R. C. Churchill, D. L. Rod, and M. F. Singer, On the infinitesimal geometry of integrable systems, Mechanics Day (W. F. Shadwick, ed.), American Mathematical Society, 1996, pp. 5–56.

10. F. Baldassarri and B. Dwork, On second order linear differential equations with algebraic solutions, American Journal of Mathematics 101 (1979), 42–76.

11. M. A. Barkatou, Rational Newton algorithm for computing formal solutions of linear differential equations, Symbolic and Algebraic Computation - ISSAC’88 (P. Gianni, ed.), ACM Press, 1988, pp. 183–195.

12. , A rational version of Moser’s algorithm, Proceedings of the 1995 International Symposium on Symbolic and Algebraic Computation (ISSAC’95) (A. H. M. Levelt, ed.), ACM Press, 1995, pp. 290–296.

13. , An algorithm to compute the exponential part of a formal fundamental matrix solution of a linear differential system, Applicable Algebra in Engineering, Communication and Computing 8 (1997), no. 9, 1 – 24.

14. , An efficient algorithm for computing rational solutions of systems of linear differential equations, Tech. report, Université de Grenoble I, IMAG-LMC, 1997.

15. A. Beauville, Monodromie des systèmes différentieles à pôles simples sur la sphère de Riemann (d’après A. Bolibruch), Astérisque 216 (1993), 103–119, Séminaire Bourbaki, No. 765.

16. E. Beke, Die Irreducibilität der homogenen Differentialgleichungen, Mathematische Annalen 45 (1894), 278–294.

17. D. Bertrand, Constructions effectives de vecteurs cycliques pour un D-module, Publication du Groupe d’Étude d’Analyse Ultramétrique, 12e année, 1984/85, no. 11.

18. , Groupes algébriques linéaires et théorie de Galois différentielle, Cours de 3^{e} cycle à l’Université Pierre et Marie Curie (Paris 6); notes de cours rédigées par René Lardon, 1985-86.

19. , Groupes algébriques et équations différentielles linéaires, Astérisque 206 (1992), 183–204, Séminaire Bourbaki, Vol. 1991/92.

20. , Un analogue différentiel de la théorie de kummer, Approximations Diophantiennes et Nombres Transcendents, Luminy 1990 (P. Philippon, ed.), Walter de Gruyter and Co., Berlin, 1992, pp. 39–49.

21. , Review of Lectures on Differential Galois Theory by A. Magid, Bulletin (New Series) of the American Mathematical Society 33 (1996), no. 2, 289–294.

22. F. Beukers, Differential Galois Theory, From Number Theory to Physics (Les Houches, 1989) (Berline) (M. Waldschmidt et al, ed.), Springer-Verlag, 1992, pp. 413–439.

23. F. Beukers, D. Brownawell, and G. Heckman, Siegel normality, Annals of Mathematics 127 (1988), 279 – 308.

24. F. Beukers and G. Heckman, Monodromy for the hypergeometric function _{n}F_{n−1}, Inventiones Mathematicae 95 (1989), 325–354.

25. A. Bialynicki-Birula, On the inverse problem of Galois theory of differential fields, Bulletin of the American Mathematical Society 69 (1963), 960–964.

26. A. Borel, Algebraic groups in the work of Ellis R. Kolchin, this volume.

27. , Linear Algebraic Groups, Second Enlarged Edition, Springer-Verlag, New York, 1991.

28. A. Boulanger, Contribution à l’étude des équations linéaires homogènes intégrables algébriquement, Journal de l’École Polytechnique, Paris 4 (1898), 1 – 122.

29. K. Boussel, Groupes de Galois des équations hypergéométriques, Comptes Rendus de l’Académie des Sciences, Paris 309 (1989), 587–589.

30. M. Bronstein, Fast reduction of the Risch differential equation, Symbolic and Algebraic Computation - ISSAC’88 (P. Gianni, ed.), ACM Press, 1988, pp. 64–72.

31. , The Risch differential equation on an algebraic curve, Symbolic and Algebraic Computation - ISSAC’88 (P. Gianni, ed.), ACM Press, 1988, pp. 64–72.

32. , Integration of elementary functions, Journal of Symbolic Computation 9 (1990), no. 3, 117–174.

33. , The transcendental Risch equation, Journal of Symbolic Computation 9 (1990), no. 1, 49 – 60.

34. , Linear ordinary differential equations: breaking through the order 2 barrier, Proceedings of the International Symposium on Symbolic and Algebraic Computation- ISSAC’92 (P. Wang, ed.), ACM Press, 1992, pp. 42–48.

35. , On solutions of linear ordinary differential equations in their coefficient field, Journal of Symbolic Computation 13 (1992), no. 4, 413 – 440.

36. , An improved algorithm for factoring linear ordinary differential operators, Proceedings of the 1994 International Symposium on Symbolic and Algebraic Computation (ISSAC’94) (J. von zur Gathen, ed.), ACM Press, 1994, pp. 336–347.

37. M. Bronstein, T. Mulders, and J.-A. Weil, On symmetric powers of differential operators, To appear in Proceedings of the 1997 International Symposium on Symbolic and Algebraic Computation (ISSAC’97).

38. D. Chudnovsky and G. Chudnovsky, Application of Padé approximation to the Grothendieck conjecture on linear differential equations, Number Theory (New York, 1983-84), Springer-Verlag, 1985, Lecture Notes In Mathematics, v. 1135, pp. 52–100.

39. H. Cohen, A Course in Computational Algebraic Number Theory, Graduate Texts in Mathematics, Springer-Verlag, New York, 1993.

40. E. Compoint, Équations différentielles, relations algébriques et invariants, Thèse, Université de Paris VI, 1996.

41. , Differential equations and algebraic relations, Tech. report, Université de Paris VI, 1996.

42. E. Compoint and M. F. Singer, Calculating Galois groups of completely reducible linear operators, Manuscript, North Carolina State University, 1997.

43. , Linear relations among solutions of linear differential equations, Manuscript, North Carolina State University, September 1996.

44. J. Davenport, On the Integration of Algebraic Functions, Lecture Notes in Computer Science, vol. 102, Springer-Verlag, Heidelberg, 1981.

45. J. Davenport and M. F. Singer, Elementary and liouvillian solutions of linear differential equations, Journal of Symbolic Computation 2 (1986), no. 3, 237–260.

46. P. Deligne, Equations Différentielles à Points Singuliers Réguliers, Lecture Notes in Mathematics, vol. 163, Springer-Verlag, Heidelberg, 1970.

47. , Catégories tannakiennes, Grothendieck Festschrift, Vol. 2 (P. Cartier et al., ed.), Birkhäuser, 1990, Progress in Mathematics, Vol. 87, pp. 111–195.

48. P. Deligne and J. Milne, Tannakian categories, Hodge Cycles, Motives and Shimura Varieties (P. Deligne et al., ed.), 1982, Springer Lecture Notes in Mathematics, Vol. 900, pp. 101–228.

49. J. Della Dora, C. di Crescenzo, and E. Tournier, An algorithm to obtain formal solutions of a linear differential equation at an irregular singular point, Computer Algebra - EUROCAM ‘82 (Lecture Notes in Computer Science, 144 (J. Calmet, ed.), 1982, pp. 273–280.

50. A. Duval, Biconfluence et groupe de Galois, Publication IRMA, Lille, Vol 18, No. 1, 1989.

51. A. Duval and M. Loday-Richaud, Kovacic’s algorithm and its application to some families of special functions, Applicable Algebra in Engineering, Communication and Computing 3 (1992), no. 3, 211–246.

52. A. Duval and C. Mitschi, Matrices de Stokes et groupe de Galois des équations hypergéométriques confluentes généralisées, Pacific Journal of Mathematics 138 (1989), no. 1, 25–56.

53. A. Fahim, Extensions galoisiennes d’algèbres différentielles, Publication IRMA, Lille, 1993; to appear in the Pacific Journal of Mathematics.

54. , Extensions galoisiennes d’algèbres différentielles, Comptes Rendus de l’Académie des Sciences, Paris 314 (1992), 1–4.

55. L. Fuchs, Über die linearen Differentialgleichungen zweiter Ordnung, welche algebraische Integrale besitzen, und eine neue Anwendung der Invariantentheorie, Journal für die reine und angewandte Mathematik 81 (1875), 97–147.

56. , Über die linearen Differentialgleichungen zweiter Ordnung, welche algebraische Integrale besitzen, zweite Abhandlung, Journal für die reine und angewandte Mathematik 85 (1878), 1–25.

57. L. Goldman, Specialization and Picard-Vessiot theory, Transactions of the American Mathematical Society 85 (1957), 327–356.

58. J. J. Gray, Fuchs and the theory of differential equations, Bulletin of the American Matehmatical Society 10 (1984), no. 1, 1 – 26.

59. , Linear Differential Equations and Group Theory from Riemann to Poincaré, Birkhäuser, Boston, Basel, Stuttgart, 1986.

60. N. V. Grigorenko, G-Primitive extensions of differential fields, Mathematical Notes 23 (1978), no. 3-4, 231–235, Originally published in Akademiya Nauk SSR. Matematicheskie Zametki, V. 23, No. 3, 1978.

61. , Two problems in the Galois theory of differential fields for the field of formal power series, Mathematics of the USSR- Sbornik 37 (1980), no. 3, 327–335, Originally published in Matematicheskiu i Sbonik. Novaya Seriya, V. 109(151) No. 3, 1979.

62. D. Yu. Grigoriev, Complexity for irreducibility testing for a system of linear ordinary differential equations, Proceedings of the International Symposium on Symbolic and Algebraic Computation- ISSAC’90 (M. Nagata and S. Watanabe, eds.), ACM Press, 1990, pp. 225–230.

63. , Complexity of factoring and calculating the gcd of linear ordinary differential operators, Journal of Symbolic Computation 10 (1990), no. 1, 7–38.

64. A. Haefliger, Local theory of meromorphic connections in dimension one (Fuchs theory), Algebraic D-Modules, Borel et al, Academic Press, 1987, pp. 129–149.

65. P. Hendriks, Shidlovskii irreducibility, Indagationes Mathematicae 5 (1994), no. 4, 439–456.

66. P. A. Hendriks and M. van der Put, Galois action on solutions of a differential equation, Journal of Symbolic Computation 19 (1995), no. 6, 559 – 576.

67. S. Hessinger, Computing Galois groups of fourth order linear differential equations, Ph.D. thesis, North Carolina State University, 1997.

68. A. Hilali, On the algebraic and differential Newton-Puiseux polygons, Journal of Symbolic Computation 4 (1987), no. 3, 335–349.

69. E. Hilb, Lineare Differentialgleichungen im komplexen Gebiet, Encyclopädie der mathematischen Wissenschaften, Vol. II, B. 5, Teubner, Leipzig, 1915, pp. 471–562.

70. M. van Hoeij, Rational solutions of the mixed differential equation and its application to factorization of differential operators, Proceedings of the 1996 International Symposium on Symbolic and Algebraic Computation, ACM Press, 1996, pp. 219 – 225.

71. , Factorization of differential operators with rational function coefficients, to appear in the Journal of Symbolic Computation, 1997.

72. , Formal solutions and factorization of differential operators with power series coefficients, to appear in the Journal of Symbolic Computation, 1997.

73. M. van Hoeij and J.-A. Weil, An Algorithm for Computing Invariants of Differential Galois Groups, to appear in Journal of Pure and Applied Algebra, 1996.

74. T. Honda, Algebraic differential equations, Symposia Mathematica 24 (1981), 169–204.

75. N. Jacobson, Pseudo-linear transformations, Annals of Mathematics 38 (1937), 484–507.

76. C. Jordan, Mémoire sur les équations différentielles linéaires à intégrale algébrique, Journal für die reine und angewandte Mathematik 84 (1878), 89 – 215.

77. I. Kaplansky, An Introduction to Differential Algebra, second ed., Hermann, Paris, 1976.

78. N. Katz, A conjecture in the arithmetic theory of differential equations, Bulletin de la Société Mathématique de France 110 (1982), 203–239.

79. , On the calculation of some differential Galois groups, Inventiones Mathematicae 87 (1987), 13–61.

80. , A simple algorithm for cyclic vectors, American Journal of Mathematics 109 (1987), 65–70.

81. , Exponential Sums and Differential Equations, Annals of Mathematics Studies, vol. 124, Princeton University Press, Princeton, 1990.

82. N. Katz and R. Pink, A note on pseudo-CM representatives and differential Galois groups, Duke Mathematics Journal 54 (1987), no. 1, 57–65.

83. F. Klein, Über lineare Differentialgleichungen, I, Mathematische Annalen 11 (1877), 115– 118.

84. , Über lineare Differentialgleichungen, II, Mathematische Annalen 12 (1878), 167– 179.

85. E. R. Kolchin, Algebraic matric groups and the Picard-Vessiot theory of homogeneous linear ordinary differential equations, Annals of Mathematics 49 (1948), 1–42.

86. , Algebraic groups and algebraic dependence, American Journal of Mathematics 90 (1968), 1151–1164.

87. , Some problems in differential algebra, Proceedings of the International Congress of Mathematicians, Moscow, 1966 (Moscow), 1968, pp. 269–276.

88. , Differential Algebra and Algebraic Groups, Academic Press, New York, 1976.

89. J. Kovacic, The inverse problem in the Galois theory of differential fields, Annals of Mathematics 89 (1969), 583–608.

90. , On the inverse problem in the Galois theory of differential fields, Annals of Mathematics 93 (1971), 269–284.

91. , An Eisenstein criterion for noncommutative polynomials, Prroceedings of the American Mathematical Society 34 (1972), no. 1, 25–29.

92. , An algorithm for solving second order linear homogeneous differential equations, Journal of Symbolic Computation 2 (1986), 3–43.

93. M. Kuga, Galois’ Dream, Birkhäuser, Boston, 1993.

94. A. H. M. Levelt, Jordan decomposition for a class of singular differential operators, Archiv für Mathematik 13 (1975), no. 1, 1–27.

95. , Differential Galois theory and tensor products, Indagationes Mathematicae, New Series 1 (1990), no. 4, 439 – 450.

96. M. Loday-Richaud, Calcul des invariants de Birkhoff des systèmes d’ordre deux, Funkcialaj Ekvacioj 33 (1990), 161–225.

97. , Introduction à la multisommabilité, Gazette des Mathématiciens, SMF 44 (1990), 41–63.

98. , Stokes phenomenon, multisummability and differential Galois groups, Annales de l’Institut Fourier 44 (1994), no. 3, 849–906.

99. , Solutions formelles des systèmes différentiels linéaires méromorphes et sommation, Expositiones Mathematicae 13 (1995), 116–162.

100. A. Magid, Lectures on Differential Galois Theory, University Lecture Series, American Mathematical Society, 1994.

101. B. Malgrange, Sur la réduction formelle des équations différentielles à singularités irrégulières, manuscript, 1979.

102. M. F. Marotte, Les équations différentielles linéaires et la théorie des groupes, Annales de la Faculté des Sciences de Toulouse 12 (1887), no. 1, H1 – H92.

103. J. Martinet and J.-P. Ramis, Théorie de Galois différentielle et resommation, Computer Algebra and Differential Equations (E. Tournier, ed.), Academic Press, 1989, pp. 115–214.

104. , Elementary acceleration and multisummability, Annales de l’Institut Henri Poincaré, Physique Théorique 54 (1991), no. 4, 331–401.

105. J. Miller, On differentially hilbertian differential fields, Ph.D. thesis, Columbia University, 1970.

106. C. Mitschi, Differential Galois groups and G-functions, Computer Algebra and Differential Equations (M. F. Singer, ed.), Academic Press, 1991, pp. 149–180.

107. , Differential Galois groups of confluent generalized hypergeometric equations: An approach using Stokes multipliers, Pacific Journal of Mathematics 176 (1996), no. 2, 365– 405.

108. C. Mitschi and M. F. Singer, Connected linear groups as differential Galois groups, Journal of Algebra 184 (1996), 333–361.

109. , The inverse problem in differential Galois theory, The Stokes Phenomenon and Hilbert’s 16th Problem (B. L. J. Braaksma et al., ed.), World Scientific, River Edge, NJ, 1996, pp. 185–197.

110. , On Ramis’s solution of the local inverse problem of differential Galois theory, Journal of Pure and Applied Algebra 110 (1996), 185–194.

111. F. Naegele and J. Thomann, Algorithmic approach of the multisummation of formal power series solutions of linear ODE applied to Stokes phenomena, The Stokes Phenomenon and Hilbert’s 16^{th} Problem (Braaksma et. al., ed.), World Scientific, 1996, pp. 197–214.

112. P. Painlevé, Sur les équations différentielles linéaires, Comptes Rendus de l’Académie des Sciences, Paris 105 (1887), 165– 168.

113. P. Th. Pépin, Méthodes pour obtenir les intégrales algébriques des équations différentielles linéaires du second ordre, Atti dell’Accad. Pont. de Nuovi Lincei 36 (1881), 243–388.

114. M. Petkovšek and B. Salvy, Finding all hypergeometric solutions of linear differential equations, Proceedings of the 1993 International Symposium on Symbolic and Algebraic Computation (ISSAC’93) (M. Bronstein, ed.), ACM Press, 1993, pp. 27–33.

115. E. Pflügel, An algorithm for computing exponential solutions of first order linear differential systems, To Appear in the Proceedings of the 1997 International Symposium on Symbolic and Algebraic Computation (ISSAC’97).

116. A. Pillay, Differential Galois theory, I, II, Preprint, University of Notre Dame, 1996.

117. M. Pohst and H. Zassenhaus, Algorithmic Algebraic Number Theory, Encyclopedia of Mathematics and its Applications, Cambridge University Press, Cambridge, 1989.

118. E. G. C. Poole, Introduction to the Theory of Linear Differential Equations, Dover Publications, Inc, New York, 1960.

119. M. van der Put, Symbolic analysis of differential equations, To appear in Some Tapas of Computer Algebra, A.M.Cohen, H.Cuypers, H. Sterk, eds., .

120. , Differential equations in characteristic p, Compositio Mathematica 97 (1995), 227– 251.

121. , Singular complex differential equations: An introduction, Nieuw Archief voor Wiskunde, vierde serie 13 (1995), no. 3, 451–470.

122. , Reduction modulo p of differential equations, Indagationes Mathematicae 7 (1996), 367–387.

123. J.-P. Ramis, Théorèmes d’indices Gevrey pour les équations différentielles ordinaires, Memoirs of the American Mathematical Society, vol. 296, American Mathematical Society, 1984.

124. , Filtration Gevrey sur le groupe de Picard-Vessiot d’une équation différentielle irrégulière, Informes de Matematica, Preprint IMPA, Series A-045/85, 1985.

125. , Phénomène de Stokes et filtration Gevrey sur le groupe de Picard-Vessiot, Comptes Rendus de l’Académie des Sciences, Paris 301 (1985), 165–167.

126. , Phénomène de Stokes et resommation, Comptes Rendus de l’Académie des Sciences, Paris 301 (1985), 99–102.

127. , About the solution of some inverse problems in differential Galois theory by Hamburger equations, Differential Equations, Dynamical Systems and Control Science, Lecture Notes in Pure and Applied Mathematics, 152 (K.P. Elsworthy et. al., ed.), Marcel Dekker, 1994, pp. 277–300.

128. , About the inverse problem in differential Galois theory: Solutions of the local inverse problem and of the differential Abhyankar conjecture, Tech. report, Université Paul Sabatier, Toulouse, 1996.

129. , About the inverse problem in differential Galois theory: The differential Abhyankar conjecture, The Stokes Phenomenon and Hilbert’s 16^{th} Problem (Braaksma et. al., ed.), World Scientific, 1996, pp. 261 – 278.

130. R. H. Risch, The solution of the problem of integration in finite terms, Bulletin of the American Mathematical Society 76 (1970), 605–608.

131. L. Schlesinger, Handbuch der Theorie der Linearen Differentialgleichungen, Teubner, Leipzig, 1887.

132. L. Schlesinger, Bericht über die Entwicklung der Theorie der linearen Differentialgleichungen seit 1865, Jahresbericht den Deutschen Vereinigung, XVIII, G. Reimer, Berlin, 1909, pp. 133– 266.

133. F. Schwarz, A factorization algorithm for linear ordinary differential operators, Proceedings of the ACM-SIGSAM 1989 International Symposium on Symbolic and Algebraic Computation (G. Gonnet, ed.), ACM Press, 1989, pp. 17–25.

134. H. A. Schwarz, Ueber diejenigen Fälle, in welchen die Gaussische hypergeometrische Reihe eine algebraische Funktion ihres vierten Elements darstellt, Journal für die reine und angewandte Mathematik 75 (1872), 292–335.

135. M. F. Singer, Algebraic solutions of n^{th} order linear differential equations, Proceedings of the 1979 Queen’s Conference on Number Theory, Queen’s Papers in Pure and Applied Mathematics, 59, 1979, pp. 379–420.

136. , Liouvillian solutions of n^{th} order homogeneous linear differential equations, American Journal of Mathematics 103 (1981), 661–681.

137. , Solving homogeneous linear differential equations in terms of second order linear differential equations, American Journal of Mathematics 107 (1985), 663–696.

138. , Algebraic relations among solutions of linear differential equations, Transactions of the American Mathematical Society 295 (1986), 753–763.

139. , Algebraic relations among solutions of linear differential equations: Fano’s theorem, American Journal of Mathematics 110 (1988), 115–144.

140. , An outline of differential Galois theory, Computer Algebra and Differential Equations (E. Tournier, ed.), Academic Press, 1989, pp. 3–57.

141. , Liouvillian solutions of linear differential equations with liouvillian coefficients, Journal of Symbolic Computation 11 (1991), 251–273.

142. , Moduli of linear differential equations on the Riemann sphere with fixed Galois group, Pacific Journal of Mathematics 106 (1993), no. 2, 343–395.

143. , Testing reducibility of linear differential operators: a group theoretic perspective, Applicable Algebra in Engineering, Communication and Computing 7 (1996), 77–104.

144. M. F. Singer and F. Ulmer, Galois groups of second and third order linear differential equations, Journal of Symbolic Computation 16 (1993), no. 3, 9–36.

145. , Liouvillian and algebraic solutions of second and third order linear differential equations, Journal of Symbolic Computation 16 (1993), no. 3, 37–73.

146. , Necessary conditions for liouvillian solutions of (third order) linear differential equations, Applied Algebra in Engineering, Communication, and Computing 6 (1995), no. 1, 1–22.

147. , Linear differential equations and products of linear forms, to appear in the Journal of Pure and Applied Algebra, 1996.

148. R. Sommeling, Characteristic classes for irregular singularities, Ph.D. thesis, Catholic University of Nijmegen, 1993, An extended abstract appeared as Characteristic Classes for Irregular Singularities, Proceedings of ISSAC’94, ACM Press, 1994.

149. M. Toulouse, Étude de systèmes différentieles linéaires d’ordre deux et trois: Algorithmes de calcul du groupe de Galois différentiel, Thèse, Université Louis Pasteur, Strasbourg, 1996.

150. E. Tournier, Solutions formelles d’équations différentielles, Thèse, Faculté des Sciences de Grenoble, 1987.

151. B. M. Trager, On the integration of algebraic functions, Ph.D. thesis, MIT, 1984.

152. C. Tretkoff and M. Tretkoff, Solution of the inverse problem in differential Galois theory in the classical case, American Journal of Mathematics 101 (1979), 1327–1332.

153. S. P. Tsarev, Problems that appear during factorization of ordinary linear differential operators, Programming and Computer Software 20 (1994), no. 1, 27–29.

154. , An algorithm for complete enumeration of all factorizations of a linear ordinary differential operator, Proceedings of the 1996 International Symposium on Symbolic and Algebraic Computation (Lakshman Y. N., ed.), ACM Press, 1996, pp. 226–231.

155. F. Ulmer, On liouvillian solutions of differential equations, Applicable Algebra in Engineering, Communication and Computing 2 (1992), 171–193.

156. , Irreducible linear differential equations of prime order, Journal of Symbolic Computation 18 (1994), no. 4, 385–401.

157. F. Ulmer and J.-A. Weil, A note on Kovacic’s algorithm, Journal of Symbolic Computation 22 (1996), no. 2, 179 – 200.

158. V. S. Varadarajan, Meromorphic differential equations, Expositiones Mathematicae 9 (1991), no. 2, 97–188.

159. , Linear meromorphic differential equations: A modern point of view, Bulletin (New Series) of the American Mathematical Society 33 (1996), no. 1, 1 – 42.

160. E. Vessiot, Méthodes d’intégration élémentaires, Encyclopédie des Sciences Mathématiques Pures et Appliquées, Tome II, Vol. 3, Fasc. 1, Gauthier-Villars, Paris, 1910, pp. 58–170.

161. E. Volcheck, Resolving singularities and computing in the jacobian of a plane algebraic curve, Ph.D. thesis, UCLA, 1994.

162. , Testing torsion divisors for symbolic integration, The ISSAC’96 Poster Session Abstracts (Zurich, Switzerland) (Wolfgang W. Küchlin, ed.), ETH, July 24–26 1996.

163. B. L. van der Waerden, Modern Algebra, second ed., Frederick Ungar Publishing Co., New York, 1953.

164. A. Zharkov, Coefficient fields of solutions in Kovacic’s algorithm, Journal of Symbolic Computation 19 (1995), no. 5, 403–408.

Department of Mathematics, North Carolina State University, Raleigh, NC 27698-8205

E-mail address: singer@math.ncsu.edu