Testing Reducibility of Linear Differential Operators: A Group Theoretic Perspective

Michael F. Singer^{∗}

North Carolina State University Department of Mathematics Box 8205 Raleigh, N.C. 27695-8205

                            e-mail: singer@math.ncsu.edu

January 4, 1995

1 Introduction

Let k be an ordinary differential field of characteristic zero and let D = k[D] be the ring of linear differential operators over k, that is, the noncommutative polynomial ring in the variable D, where D · a − a · D = a′ for all a ∈ k. An element L ∈ D is said to be reducible if L = L_{1} · L_{2} for some L_{1}, L_{2} ∈ D, L_{1}, L_{2} ∉ k. In this case, L_{1} and L_{2} are called factors of L. This paper was motivated by the desire to answer the following question:

Can one decide if a linear differential operator is reducible without having to find a factor?

This question is in turn motivated by the following theorem (and its generalizations, [43]): Let k be a differential field with algebraic closed field of constants and let L ∈ D be a second order operator. The equation L(y) = 0 has non-zero liouvillian solutions over k if and only if L^{◯ s 6} is reducible in D. Here, the operator L^{◯ s 6} is the operator of order 7 whose solution space (in the Picard-Vessiot extension of k corresponding to L) is spanned by all 6^{th} powers of solutions of L. The techniques and results of [43] show how one can reduce many questions concerning the Galois group of a differential equation to questions of factorizations of auxillary operators.

∗Partially supported by NSF Grant 90-24624

Each element of D can be expressed as a product of irreducible factors and, when k = \overline{ℚ}(x), x′ = 1, \overline{ℚ} the algebraic closure of the rational numbers, there exist algorithms to carry out such a factorization ([13], [38], [39]). Furthermore, in [14], Grigoriev gives a method (and complexity analysis) for testing reducibility of a system of linear operators but this method is equivalent to finding factors (in the case of a single operator). We present a method based on different ideas. In previous methods the question of deciding if a linear operator L factors is reduced to:

1. Constructing auxillary linear operators L̃ whose associated Riccati equations have among their solutions all possible coefficients a_{i}(x) of factors L_{1} = D^{m}+a_{m−1}(x)D^{m−1}+ … + a_{0}(x) of L. From L̃ one can bound the degrees of the numerators and denominators of these coefficients (in fact, more information can be extracted from these auxillary operators, [8])

2. Explicitly finding the coefficients of a factor of L. This involves, in general, solving large systems of polynomial equations for the coefficients of the a_{i}(x) (or at least deciding if such a system has a solution).

Techniques for solving 1. have been implemented by Bronstein in Axiom, [8]. Schwarz has implemented the full algorithm for equations of small order. Our aim is to give a method that avoids the need to actually find the coefficients of a factor. Our method will also yield two other benefits. First of all, it gives a method to decide if the Galois group is a reductive group (see section 3.3.1). Secondly, if one knows in advance that the group is reductive (for example, if one knows that the group is finite, as happens in situations discussed in [43]) one can take advantage of this fact to simplify further the reducibility test.

To understand our approach, let us first consider the question of factorization in other contexts. First, consider the commutative ring of polynomials 𝔽_{q}[x] of polynomials over the field 𝔽_{q} with q elements and let f ∈ 𝔽_{q}[x]. The approach of the Berlekamp algorithm for factorization is to form the ideal 𝔽_{q}[x]·f and relate factorization properties of f to the structure of the quotient ring A = 𝔽_{q}[x]/𝔽_{q}[x]·f (c.f., [32], pp. 247-259). In particular, if f = f_{1} · · · · · f_{m} where the f_{i} are pairwise relatively prime irreducible polynomials of degree d_{i}, then A will be a direct sum of fields, A = 𝔽_{q^{d_{1}}} ⊕⋯⊕𝔽_{q^{dm}}. If Φ is the map Φ : x ↦ x^{q} −x, one has that dim_{𝔽_{q}}(Ker Φ) = m. Therefore, computing the kernel of the map Φ gives a quick way of determining the number of factors of f and, in particular, of determining if f is irreducible.

When one tries to generalize this idea to noncommutative polynomial rings one runs into various problems. For example, let K be a field and σ a nontrivial automorphism of K and consider the ring K[x; σ] of polynomials in x over K with the usual addition and multiplication defined by x · a = σ(a) · x for all a ∈ K. These rings were studied by Ore [34], Jacobson [18, 19], Macdonald [31] and Cohn [9]. Most recently, Giesbrecht [12] has given factorization algorithms when K is a finite field. One can begin to proceed as in the commutative case. Let f ∈ K[x; σ] and consider the left ideal K[x; σ] · f. The quotient M = K[x; σ]/K[x; σ] · f no longer has a canonical ring structure but is only a left K[x; σ]−module. The key idea is to consider the ring E(M) of K[x; σ]−endomorphisms of M (also called the eigenring of K[x; σ] · f) instead of the module M. Building on [19], Giesbrecht shows that f is irreducible if and only if E(M) has no zero divisors (and so can be shown to be a field). Furthermore Giesbrecht shows how one can determine zero divisors of this ring. He is then able to give algorithms for finding the number of irreducible factors and finally for factorization. The key property that is used is that K[x; σ] has a rich supply of two sided ideals (see [12] for details).

When one considers the ring D one can begin to proceed as with the ring K[x; σ] (in fact, in [18], [19], [34] many results are developed in a context that includes both these rings). In contrast to K[x; σ], the ring D will in general have a very poor supply of two sided ideals (for example, if k = \overline{ℚ}(x), D has no non-trivial two sided ideals ([6], p. 27)). Furthermore, it is easy to construct (see Example 2.8) operators L_{1}, L_{2} ∈ D such that L_{1} is reducible and L_{2} is irreducible, and End_{D}(D/D · L_{1}) and End_{D}(D/D · L_{2}) are isomorphic. Therefore, one cannot completely rely on these rings to determine irreducibility. We therefore look beyond purely ring theoretic properties to find criteria for irreducibility. For us the key fact will be that to each linear operator L ∈ D one can associate a linear algebraic group G, its Galois group, and that the factorization properties of the operator are intimately connected to the structure and representation theory of G. The key is to distinguish the two cases:

(1) G a reductive group, and (2) G a non-reductive group. When G is a reductive group, properties of End_{D}(D/D · L) (already known to Ore) determine if L is reducible. When G is not reductive, L must already be reducible. Our main contribution is to give a procedure to test if G is reductive.

The rest of the paper is organized as follows. In section 2, we will describe properties of the ring D and its modules and relate these properties to Galois groups of differential operators. The section ends with Corollary 2.19 which gives a criterion for the Galois group to be reductive, and Corollary 2.21 which gives us a criterion for irreducibility. Section 3 concerns itself with making this criterion effective, and giving examples and applications to determining Galois groups of linear differential equations.

We would like to thank A. Fauntelroy and F. Ulmer for stimulating conversations concerning the contents of this paper.

2 Factorization in the Ring D

Let k be a differential field of charactersitic 0 with algebraically closed field of constants C. We shall assume that the reader is familliar with the basic facts of the Picard-Vessiot theory (see [21]). Most of the material in Sections 2.1, and 2.2 is either classical or follows from simple considerations concerning D−modules (see the remarks at the end of the section). Nonetheless we have included this material to offer the reader an elementary bridge between the old and the new, to bring out their group theoretic nature and to put these facts in a context suitable for use in the quest for algorithms.

2.1 Generalities

For any L = a_{n}D^{n}+…+a_{0} ∈ D with a_{n} ≠ 0, we define the order of L, ord(L) to be the integer n and we define ord(0) = −∞ . The ring D is both a left and right euclidean ring, that is, for any L_{1} ≠ 0, L_{2} ∈ D there exist unique Q_{r}, R_{r}, Q_{l}, R_{l} ∈ D with ord(R_{r}), ord(R_{l}) < ord(L_{1}) such that L_{2} = Q_{r}L_{1} + R_{r} and L_{2} = L_{1}Q_{l} + R_{l}. For k ⊂ K, we denote by Soln_{K}(L) the space of solutions of L(y) = 0 in K.

Lemma 2.1 Let L_{1}, L_{2} ∈ D and assume that ord(L_{1}) = m, ord(L_{2}) = n. Let K be a differential extension of k having the same constants C.

1. dim_{C}Soln_{K}(L_{1}) ≤ m

2. If dim_{C}Soln_{K}(L_{1}) = m and any solution in K of L_{1}(y) = 0 is a solution of L_{2}(y) = 0, then L_{1} divides L_{2} on the right in D.

3. If dim_{C}Soln_{K}(L_{1}) = m and L_{2} divides L_{1} on the right, then dim_{C}Soln_{K}(L_{2}) = n and Soln_{K}(L_{2}) ⊂ Soln_{K}(L_{1}).

Proof: The first claim follows from a standard wronskian argument ([21], p. 21). To prove the second claim, write L_{2} = QL_{1} + R. Applying both sides of this expression to solutions of L_{1}(y) = 0, we see that R(y) = 0 has a solution space of dimension at least m. Since its order is at most m − 1, we have that R = 0. To prove the final claim note that L_{2} can be applied to any element of Soln_{K}(L_{1}) and in this way maps this space to Soln_{K}(Q) where L_{1} = QL_{2}. The dimension of the image Im of this map is at most ord(Q) and the dimension of the kernel Ker is at most ord(L_{2}). Since ord(L_{1}) = dim_{C}Soln_{K}(L_{1}) = dim_{C}Im+dim_{C}Ker ≤ ord(Q)+ord(L_{2}) = ord(L_{1}), we have that dim_{C}Soln_{K}(L_{2}) = ord(L_{2}) and Soln_{K}(L_{2}) ⊂ Soln_{K}(L_{1}).

When dim_{C}Soln_{K}(L) = ord(L), we say that K contains a full set of solutions of L. The main fact connecting the Galois group of a linear operator to factorization properties of that operator is the following:

Lemma 2.2 Let K be a Picard-Vessiot extension of k with Galois group G and let V ⊂ K be a finite dimensional C vector space. V is the solution space of some homogeneous linear differential equation L(y) = 0 with coefficients in k if and only if V is left invariant by G.

Proof: If V is the solution space of L(y) = 0, then V is left invariant by G because the elements of G take solutions of this equation to other solutions of this equation. Conversely, assume V is G−invariant and let y_{1}, …, y_{m} be a C−basis. Let

L(y) = det(W r(y, y_{1}, …, y_{m}))/det(W r(y_{1}, …, y_{m})),

where W r is the wronskian matrix. Note that if σ ∈ G, then σ(det(W r(y, y_{1}, …, y_{m}))) = det(W r(y, y_{1}, …, y_{m})det(A_{σ}) and σ(det(W r(y_{1}, …, y_{m}))) = det(W r(y_{1}, …, y_{m})det(A_{σ}), where A_{σ} is the matrix of σ with respect to the given basis. We then have that the coefficients of L(y) are left fixed by all elements of G. Therefore L ∈ D.

We define an element L ∈ D of positive order to be reducible if L = L_{1}L_{2} for operators L_{1}, L_{2} ∈ D of positive order. If L is not reducible, we say it is irreducible.

Corollary 2.3 Let L ∈ D. The following are equivalent:

1. L is irreducible.

2. The Galois group of L acts irreducibly on the solution space of L in the Picard-Vessiot extension of k corresponding to L(y) = 0.

3. If K is any Picard-Vessiot extension of k containing the Picard-Vessiot extension of k corresponding to L(y) = 0, then the Galois group of K acts irreducibly on the solution space of L(y) = 0 in K.

Proof: This follows easily from Lemma 2.1 and Lemma 2.2.

We say two operators L_{1}, L_{2} ∈ D are relatively prime if there is no operator of positive order dividing both on the right.

Corollary 2.4 Let L_{1}, L_{2} ∈ D. The following are equivalent:

1. L_{1} and L_{2} are relatively prime.

2. There exist R, S ∈ D such that RL_{1} + SL_{2} = 1.

3. L_{1} and L_{2} have no common nonzero solution in any extension of k.

Proof: The equivalence of 1. and 2. follows from the existence of a euclidean algorithm. If L_{1} and L_{2} are not relatively prime then they have a common nonzero solution in the Picard-Vessiot extension corresponding to the common factor. Conversely, if there exist R, S ∈ D such that RL_{1} + SL_{2} = 1, then any common solution v of L_{1} and L_{2} satisfies 0 = RL_{1}(v) + SL_{2}(v) = v.

As we have already noted, the module D/D · L is not a ring and one cannot apply Berlekamp techniques directly to this module. A substitute for this module is the ring End_{D}(D/D · L). We shall show that this ring arises in several settings.

Let L_{1}, L_{2} ∈ D and denote by \overline{R} the equivalence class of R in D/D · L_{2} and define

E_{D}(L_{1}, L_{2}) = \{\overline{R} ∈ D/D · L_{2} | L_{1}R is divisible on the right by L_{2}\}

One easily checks that this condition depends only on the equivalence class and not on the choice of representative. Note that E_{D}(L_{1}, L_{2}) is closed under addition and multiplication by elements in C. If L_{1} = L_{2} = L, one can define a multiplication on this vector space and the resulting ring is called the (left) eigenring of L and is denoted by E_{D}(L). The multiplication on E_{D}(L) is defined in the following way: for \overline{R}_{1}, \overline{R}_{2} ∈ E_{D}, let \overline{R}_{1} · \overline{R}_{2} = \overline{R_{1}R_{2}}. To see that this is well defined, let S_{1} = R_{1}+Q_{1}L and S_{2} = R_{2}+Q_{2}L. S_{1}S_{2} = R_{1}R_{2}+R_{1}Q_{2}L+Q_{1}LR_{2}+ Q_{1}LQ_{2}L. Since \overline{R}_{2} ∈ E_{D}(L), we have that LR_{2} is divisible on the right by L. Therefore \overline{S_{1}S_{2}} = \overline{R_{1}R_{2}}. This shows that E_{D}(L) is a C−algebra.

Lemma 2.5 Let L_{1}, L_{2} ∈ D, let K be a Picard-Vessiot extension containing a full set of solutions of L_{1} and L_{2}, and let G be its Galois group.

1. The following three C−spaces are isomorphic:

• E_{D}(L_{1}, L_{2})

• Hom_{D}(D/D · L_{1}, D/D · L_{2})

• Hom_{G}(V_{2}, V_{1}), where V_{i} is the solution space of L_{i}(y) = 0 in K for i = 1, 2.

Furthermore, if L_{1} = L_{2}, then these rings are isomorphic as C−algebras.

2. Assuming L_{1} and L_{2} have the same order, the isomorphisms of these rings may be chosen in such a way as to induce bijections among the following sets:

• E_{D}(L_{1}, L_{2})^{∗} = \{\overline{R} ∈ E_{D}(L_{1}, L_{2}) | R and L_{2} have no common factors\}

• Isom_{D}(D/D·L_{1}, D/D·L_{2}) = {ϕ ∈ Hom_{D}(D/D·L_{1}, D/D·L_{2}) | ϕ is an isomorphism}

• Isom_{G}(V_{2}, V_{1}) = {ψ ∈ Hom_{G}(V_{2}, V_{1}) | ψ is an isomorphism} Proof: We will first show that there is an isomorphism between E_{D}(L_{1}, L_{2}) and Hom_{D}(D/D· L_{1}, D/D · L_{2}). Let \overline{R} ∈ E_{D}(L_{1}, L_{2}). We define an element ϕ_{R} ∈ Hom_{D}(D/D · L_{1}, D/D · L_{2}) by ϕ_{R}(1 + D/D · L_{1}) = \overline{R}. One easily checks that this map is well defined and is a D−homomorphism. The map Φ : \overline{R} ↦ ϕ_{R} is clearly a C−homomorphism. If ϕ_{R} = 0, then R ∈ D · L_{2} so \overline{R} = 0. Therefore Φ is injective. If ϕ ∈ Hom_{D}(D/D · L_{1}, D/D · L_{2}), let \overline{R} = ϕ(1 + D/D · L_{1}). Since 0 = ϕ(L_{1}(1 + D/D · L_{1})) = \overline{L_{1}R}, we have that L_{1}R is divisible on the right by L_{2}. Therefore, \overline{R} ∈ E_{D}(L_{1}, L_{2}) and ϕ = ϕ_{R}, so Φ is surjective.

We now show that Φ is a bijection on the corresponding sets mentioned in 2. The Euclidean algorithm shows that R and L_{2} are relatively prime if and only if there exist P, Q ∈ D such that P R + QL_{2} = 1. Let \overline{R} ∈ E_{D}(L_{1}, L_{2}) with R relatively prime to L_{2}. Then for any S ∈ D, SP R + SQL_{2} = S. Therefore ϕ_{R}(SP + D · L_{1}) = \overline{S}, so ϕ_{R} is surjective. Since D/D · L_{1} and D/D · L_{2} have the same dimension as vector spaces, this map must be an isomorphism. Conversely, assume that ϕ_{R} is an isomorphism. Then for some P ∈ D we have ϕ_{R}(P + D · L_{1}) = \overline{1}. Therefore, there is a Q ∈ D such that P R = 1 + QL_{2}, so R and L_{2} are relatively prime.

Now we show that there is an isomorphism between E_{D}(L_{1}, L_{2}) and Hom_{G}(V_{2}, V_{1}). Let \overline{R} ∈ E_{D}(L_{1}, L_{2}) and let v ∈ V_{2}. We may apply R to v. Since L_{1}R is divisible on the right by L_{2} we have that R(v) ∈ V_{1}. Therefore the map ψ_{R} : v ↦ R(v) is a linear map of V_{2} to V_{1} and this map depends only on the equivalence class of R. One easily checks that, since the coefficients of R lie in k, one has ψ_{R} ∈ Hom_{G}(V_{2}, V_{1}). Therefore the map Ψ : \overline{R} ↦ ψ_{R} is well defined and can be seen to be a C−homomorphism. If ψ_{R} = 0 then R(v) = 0 for all v ∈ V_{2}, so (by Lemma 2.1) L_{2} divides R on the right. Therefore \overline{R} = 0 and so Ψ is injective. Let ψ ∈ Hom_{G}(V_{2}, V_{1}) and let v_{1}, …, v_{n} be a basis of V_{2}. One sees that the entries of the matrix A = W r(ψ(v_{1}), …, ψ(v_{n})) · W r(v_{1}, …, v_{n})^{−1} are left invariant by G and so lie in k. If (a_{0}, …, a_{n−1}) is the first row of A, let R = a_{n−1}D^{n−1} + … + a_{0}. One then checks that ψ = ψ_{R}. Therefore Ψ is surjective.

We now show that Ψ is a bijection between the corresponding sets mentioned in 2. Let \overline{R} ∈ E_{D}(L_{1}, L_{2}) with R relatively prime to L_{2} (c.f., Lemma 2.1). If v ∈ V_{2} satisfies ψ_{R}(v) = 0, then R(y) = 0 and L_{2}(y) = 0 have a common solution v contradicting the fact that these two operators are relatively prime. Therefore ψ_{R} is injective and so must be an isomorphism. Conversely, assume that R and L_{2} have a common factor L_{3}. We may write R = P L_{3} and L_{2} = QL_{3}. By Lemma 2.1.3, L_{3} has a full set of solutions in K so the map v ↦ L_{3}(v) has a nontrivial kernel. Therefore the map ψ_{R} : v ↦ R(v) has a nontrivial kernel, so ψ_{R} is not an isomorphism.

We leave the statement concerning the case when L_{1} = L_{2} = L to the reader.

From part 2. of the above (and its proof), we conclude:

Corollary 2.6 Let L_{1}, L_{2} be monic operators in D, both of order n. The following are equivalent:

1. If K is a Picard-Vessiot extension of k containing the Picard-Vessiot extensions of k corresponding to L_{1} and L_{2}, then the solution spaces of L_{1}(y) = 0 and L_{2}(y) = 0 are isomorphic G-modules, where G is the Galois group of K.

2. There exist u_{0}, …, u_{n−1} ∈ k such that for any Picard-Vessiot extension K of k containing the Picard-Vessiot extension of k corresponding to L_{1}, the map y ↦ ∑ u_{j}y^{(j)} is a vector space isomorphism of the solution space of L_{1} onto the solution space of L_{2}.

3. There exists an operator L_{3}, with coefficients in k, relatively prime to L_{1} such that L_{2} ∘ L_{3} = L_{4} ∘ L_{1} for some operator L_{4} with coefficients in k.

4. D/(D · L_{1}) ≃ D/(D · L_{2}) as D-modules.

Classically, two operators of the same order are said to be of the same type if conditions 2. or 3. hold.

Corollary 2.7 Let L_{1}, L_{2} ∈ D. If L_{1} and L_{2} are irreducible then E_{D}(L_{1}, L_{2}) has dimension 1 or 0, depending on whether L_{1} and L_{2} are of the same type or not. In particular, if L is irreducible then E_{D}(L) is isomorphic to C.

Proof: Let K be a Picard-Vessiot extension of k containing the Picard-Vessiot extensions of L_{1} and L_{2}, let G be the Galois group of L and let V_{i} be the solution space of L_{i}(y) = 0 in K, for i = 1, 2. Since each L_{i} is irreducible, Corollary 2.3 implies that V_{i} is an irreducible G−module. Schur’s Lemma implies that Hom_{G}(V_{2}, V_{1}) has dimension 1 or 0 depending on whether V_{1} and V_{2} are isomorphic or not. Note that for any L ∈ D, C ⊂ E_{D}(L) so dimE_{D}(L) ≥ 1. Therefore when L is irreducible, we conclude from the first part that E_{D}(L) ≃ C

Example 2.8 The converse of the last statement of the above corollary is not true. To see this, let k = ℂ(x) and L = D^{2} + \frac{1}{x}D − (1 + \frac{1}{x}) = (D + (1 + \frac{1}{x}))(D − 1). This has a fundamental set of solutions y_{1} = e^{x}, y_{2} = e^{x} ∫ \frac{e^{−2x}}{x}. The corresponding Picard-Vessiot

extension is K = k(e^{x}, ∫ (e^{−2x}/x)) and the Galois group is G = \{( \begin{matrix}a & b \\ 0 & a^{−1} \end{matrix} ) | a ∈ ℂ^{∗}, b ∈ ℂ\}.

The only matrices that commute with each of the matrices in this group are the constant matrices. Since we can identify Hom_{G}(V, V), V = Soln_{K}(L), with E_{D}(L), we see that E_{D}(L) is isomorphic to C, while L is reducible.

Let L_{1} have order m and L_{2} have order n. Note that each element of E_{D}(L_{1}, L_{2}) has a unique representative in D of order at most n − 1. Therefore, one may identify E_{D}(L_{1}, L_{2}) with a C−subspace W of k^{n} via the map R = a_{n−1}D^{n−1} + … + a_{0} ↦ (a_{n−1}, …, a_{0}). Since dim_{C}(Hom_{G}(V_{2}, V_{1})) ≤ nm, we have that dim_{C}W ≤ nm. Let R be a linear operator with differential indeterminates \overline{a}_{n−1}, …, \overline{a}_{0} for coefficients. If we divide L_{1}R on the right by L_{2} we will get a remainder R̃ where the coefficient ã_{i} of each D^{i}, 0 ≤ i ≤ n − 1, is a linear expression (with coefficients in k) in the \overline{a}_{j} and their derivatives. Therefore, there is an n×n matrix A_{L_{1},L_{2}} with entries in D such that A_{L_{1},L_{2}} · (\overline{a}_{n−1}, …, \overline{a}_{0})^{T} = (ã_{n−1}, …, ã_{0})^{T}. This implies that R = a_{n−1}D^{n−1} + … + a_{0} ∈ D, of order at most n, represents an element of E_{D}(L_{1}, L_{2}) if and only if A_{L_{1},L_{2}} · (a_{n−1}, …, a_{0})^{T} = 0. If F is a differential field containing k with the same constants as K, we denote by Soln_{F} (A_{L_{1},L_{2}}) the C−space of solutions of A_{L_{1},L_{2}} · \overline{a} = 0 with \overline{a} ∈ F^{n}. We then have:

Corollary 2.9 Let F be a differential extension field of k with the same constants. Then the vector spaces E_{F [D]}(L_{1}, L_{2}) and Soln_{F} (A_{L_{1},L_{2}}) are isomorphic. In particular, if L = L_{1} = L_{2} is irreducible in F [D], then Soln_{F} (A_{L}) has dimension one.

Example 2.10 Let k = C(x) and L = D^{4}. E_{D}(L) = {R ∈ D | ord(R) < 4 and D^{4}R is divisible on the right by D^{4}\}. If we let R = \overline{a}_{3}D^{3} + \overline{a}_{2}D^{2} + \overline{a}_{1}D + \overline{a}_{0}, the condition that \overline{R} ∈ E_{D}(L) is that the coefficients of D^{3}, D^{2}, D^{1}, and D^{0} in D^{4}R are all zero. This yields the following system A_{L}):

\overline{a}_{0}^{(iv)} = 0
4\overline{a}_{0}^{(iii)} + \overline{a}_{1}^{(iv)} = 0
6\overline{a}_{0}^{(ii)} + 4\overline{a}_{1}^{(iii)} + \overline{a}_{2}^{(iv)} = 0
4\overline{a}′_{0} + 6\overline{a}_{1}^{(ii)} + 4\overline{a}_{2}^{(iii)} + \overline{a}_{3}^{(iv)} = 0

By inspection, one sees that all solutions (\overline{a}_{3}, \overline{a}_{2}, \overline{a}_{1}, \overline{a}_{0}) have polynomial entries and that the space of such solutions has dimension 16. Therefore, dim_{C}E_{D}(L) = 16. One can verify this by noting that the Galois group of L is trivial, so End_{G}(V) is the ring of all 4 × 4 matrices.

In Section 3.1, we will discuss how one determines, in general, the dimension of Soln_{F} (A_{L}) and show how this result gives an effective sufficient condition for reducibility.

We close this subsection by stating the theorem of unique factorization for linear operators. One cannot hope to claim that the operators appearing in a factorization into irreducible operators are unique. For example, D^{2} = D · D = (D + \frac{1}{x})(D − \frac{1}{x}).

Proposition 2.11 For any L ∈ D of positive order, we may write L = rL_{1} ⋯ L_{m} where r ∈ k and each L_{i} ∈ D is monic and irreducible. If L = r̃L̃_{1} ⋯ L̃m̃ is another such factorization, then r = r̃, m = m̃, and there exists a permutation π such that L_{i} and L̃_{π(i)} are of the same type.

Proof: Let G be the Galois group of L. A factorization of L = rL_{1} ⋯ L_{m} corresponds to a normal series in the solution space V = V_{1} ⊇ … V_{m} ⊇ {0} where each V_{i} is the solution space of L_{i}L_{i−1} ⋯ L_{m}(y) = 0. Note that each V_{i}/V_{i−1} is G-isomorphic to the solution space of L_{i}(y) = 0 and so is an irreducible G-module. The Jordan-Hölder Theorem ([17], Ch. VII.1; [44], Sec. 46) implies that any two such normal series are equivalent, that is, there is a permutation such that V_{i}/V_{i−1} and Ṽ_{i}/Ṽ_{i−1} are G−isomorphic. Lemma 2.6 implies that the coresponding operators would be of the same type.

We note that a proof could also proceed by applying the Jordan-Hölder Theorem directly to the D-module D/D · L.

2.2 Reducibility of Completely Reducible Operators

We have seen above that the structure of E_{D}(L) does not determine, in general, whether or not L is reducible. In this section we describe a class of operators where the structure of this ring does determine the factorization properties of L.

Given two operators L_{1}, L_{2} ∈ D one can define the least commmon left multiple of L_{1} and L_{2}, [L_{1}, L_{2}]_{l} to be the monic nonzero operator of smallest order such that both L_{1} and L_{2} divide this operator on the right. To see that this definition uniquely defines [L_{1}, L_{2}]_{l}, note that if S and T are two such operators, then they must be of the same order. Writing S = QT + R with ord(R) < ord(T), one sees that L_{1} and L_{2} divide R on the right. Therefore, R = 0 and so comparing orders and leading coefficients, one has S = T. One can clearly define the least common left multiple [L_{1}, …, L_{m}]_{l} of any finite set of operators {L_{1}, …, L_{m}}. We say that a linear operator is completely reducible if it is a k-left multiple of the least common left multiple of a set of irreducible operators. In Lemma 2.13, we shall give a group theoretic characterization of this notion.

Lemma 2.12 Let L, L_{1}, …, L_{m} ∈ D and let K be a Picard-Vessiot extension of k containing a full set of solutions of each of L(y) = 0, L_{1}(y) = 0, …, L_{m}(y) = 0. L = a[L_{1}, …, L_{m}]_{l}, for some a ∈ k if and only if the solution spaces V_{i} of L_{i}(y) = 0 generate the solution space V of L(y) = 0.

Proof: Let W be the vector space spanned by the V_{i} and let G be the Galois group of K. Clearly W is G-invariant, so it is the solution space of some monic \overline{L} ∈ D. Since V_{i} ⊂ W, L_{i} divides \overline{L} on the right. If L̃ ∈ D and for each i, L_{i} divides L̃, then L̃ vanishes on W, so \overline{L} divides L̃ on the right. Therefore \overline{L} = [L_{1}, …, L_{m}]_{l} and so L = a\overline{L} if and only if V = W.

Let G be a linear algebraic group. Given a G−module W and a submodule W_{1}, we say W_{1} has a complementary submodule if there is a submodule W_{2} of W such that W = W_{1} ⊕ W_{2}. A finite dimensional G−module V is said to be completely reducible if every submodule has a complementary invariant submodule. This is equivalent to V being the direct sum of irreducible submodules. Recall that the unipotent radical G_{u} of a group is the largest normal unipotent subgroup (see [16] for a definition of these and related notions). Note that G_{u} coincides with the unipotent radical of the connected component of the identity. The group G is said to be reductive if its unipotent radical is trivial. When the field is algebraically closed and of characteristic zero, it is well known that G is reductive if and only if it has a faithful completely reducible G−module. In this case, all G-modules will be completely reducible [7].

Lemma 2.13 Let L ∈ D. Let K be a Picard-Vessiot extension of k corresponding to L(y) = 0, and let G be the Galois group of K. The following are equivalent:

1. L is completely reducible.

2. The solution space of L(y) = 0 in K is a completely reducible G−submodule.

3. The Galois group of L is a reductive group.

Proof: Assume 1. is true and let L = [L_{1}, …, L_{m}]_{l} be a minimal representation of L as a least common left multiple of irreducible operators. By minimality, we have that L_{i} does not divide [L_{1}, …, L̂_{i}, …, L_{m}]_{l}. For each i, we may write L = L̃_{i}L_{i}. By Lemma 2.1, L_{i} has a full set of solutions in K. Furthermore, since each L_{i} is irreducible, each V_{i} is an irreducible G−module. From the condition that L_{i} does not divide [L_{1}, …, L̂_{i}, …, L_{m}]_{l} on the right, we have that V_{i} ∩ V_{1} + … + V̂_{i} + … + V_{m} = {0}. Lemma 2.12 implies that V is the direct sum of the V_{i}. Therefore V is a completely reducible G−module.

Assume 2. is true and write V = V_{1} ⊕ … ⊕ V_{m} where the V_{i} are irreducible G−modules. By Lemma 2.2, each V_{i} is the solution space of an irreducible operator L_{i} and by Lemma 2.12, we have that 1. is true.

The equivalence of 2. and 3. follows from the discussion preceding the lemma.

One can easily describe E_{D}(L) when L is completely reducible. Given any ring R, any completely reducible R−module M may be written in the form M = M_{1}^{(n_{1})} ⊕ ⋯ ⊕ M_{1}^{(n_{r})} where the M_{i} are non-isomorphic irreducible M−modules, each repeated n_{i}−times in the direct sum. It is a well known extension of Schur’s Lemma (c.f., [23], Chapter XVII, Section 1, Proposition 1.2) that End_{R}(M) is isomorphic to Mat_{n_{1}}(End_{R}(M_{1})) ⊕ … ⊕ Mat_{n_{r}}(End_{R}(M_{r})), where Mat_{n_{i}}(End_{R}(M_{i})) is the ring of n_{i} × n_{i} matrices with entries in End_{R}(M_{i}). If L is a completely reducible operator, we can apply this result to the C[G]- module V, where V is the solution space of L in the associated Picard-Vessiot extension of k and C[G] is the group algebra of G. Note that since C is algebraically closed we have (by Schur’s Lemma) that any End_{C[G]}(V_{i}) is isomorphic to C. Therefore, using the isomorphisms of Lemma 2.5, we have the following:

Lemma 2.14 If L be a completely reducible linear operator, then E_{D}(L) is isomorphic to Mat_{n_{1}}(C) ⊕ … ⊕ Mat_{n_{r}}(C) for some integers n_{i}. In this case, L is irreducible if and only if E_{D}(L) is isomorphic to C.

Recalling the notation of the previous section, we have:

Corollary 2.15 A completely reducible operator L is reducible if and only if dim_{C}Soln_{k}(A_{L}) > 1. This happens if and only if A_{L} · \overline{a}^{T} = 0 for some \overline{a} = (a_{n−1}, …, a_{0}) ∈ k^{n} with either a_{i} ≠ 0 \underline{for some i > 0} or a_{0} ∉ C.

Proof: The first part of the corollary follows from the fact that E_{D}(L) is isomorphic to Soln_{k}(A_{L}) as C−vector spaces. Recall that End_{G}(V) always contains the endomorphisms induced by constant multiplication. Such an endomorphism corresponds to an element \overline{R} = 0D^{n−1} + … 0D + a ∈ E_{D}(L), a ∈ C and so is given by (0, …, 0, a) ∈ Soln_{k}(A_{L}). Therefore dim_{C}Soln_{k}(A_{L}) > 1 if and only if this space contains elements not of this form.

2.3 Reducibility of General Operators

In this section we give a criterion for a linear operator to be completely reducible. If L is an operator that is not completely reducible, then it cannot be irreducible. Therefore, this criterion together with the results of the previous section will yield a criterion for an operator to be reducible.

An operator is not completely reducible if and only if its Galois group G is a non-reductive group. This happens if and only if the solution space (in the associated Picard-Vessiot extension) is not a completely reducible G-module. We begin by considering a modification of the notion of completely reducible. We say that W is 1-reductive if every 1-dimensional G-submodule has a complementary submodule.

Lemma 2.16 Let G be a linear algebraic group over an algebraically closed field, V a Gmodule and W_{1} be the sum of all one dimensional submodules of V. The following are equivalent:

1. V is 1-reductive.

2. W_{1} has a complementary submodule in V.

3. If W is a submodule of W_{1}, then W has a complementary submodule in V.

Proof: Assume 2. holds. Since W_{1} is the sum of irreducible modules it is completely reducible. Therefore, for any submodule W ⊂ W_{1}, W has a complementary submodule in W_{1}. Since W_{1} has a complementary submodule in V, W will have a complementary submodule in V. Therefore 3. holds.

Assume 3. holds. Any 1-dimensional submodule V_{1} of V is a submodule of W_{1}, so V_{1} has a complementary submodule in V. Therefore 1. holds.

Assume 1. holds. Let W_{0} be a submodule of W_{1}, maximal with respect to the property of having a complementary submodule in V and write V = W_{0} ⊕ W̃_{0}. If W_{0} ≠ W_{1}, then there is a one dimensional submodule V_{1} ⊂ W_{1}, V_{1} ⊄ W_{0}. Using 1., we may write V = V_{1} ⊕ Ṽ_{1}. Let π be the projection of V onto W̃_{0} with kernel W_{0}. Since V_{1} is one dimensional and V_{1} ∩ W_{0} = (0), we have that π(V_{1}) ≠ (0). Writing W̃_{0} = π(V_{1}) ⊕ π(Ṽ_{1}), we have that (W_{0} ⊕ π(V_{1})) ⊕ π(Ṽ_{1}) = V. Therefore W_{0} ⊕ π(V_{1}) is strictly larger than W_{0} and has a complementary submodule in V, contradicting the maximality of W_{0}. Therefore, W_{0} = W_{1} and 2. holds.

For a non-reductive group G, we have that the unipotent radical G_{u} ≠ (0) so we begin by studying unipotent groups. The following contains the facts we will need concerning unipotent groups.

Lemma 2.17 Let U be a nontrivial unipotent group defined over an algebraically closed field C and let V be a faithful U−module of dimension n.

1. V_{0} = {v ∈ V | σ(v) = v for all σ ∈ U} is a nonzero invariant U−submodule of V of dimension at most n − 1.

2. If dim V_{0} = i then ⋀^{i} V_{0} is a one-dimensional submodule of ⋀^{i} V that has no complementary submodule and so ⋀^{i} V is not 1-reductive.

Proof: V_{0} is nonzero by ([16], Thm 17.5). If its dimension is n, then the group would be trivial, since the module is a faithful module.

To prove 2., note that ⋀^{i} V_{0} is clearly one-dimensional and U−invariant. Applying 1. to the module V/V_{0}, we see that there is an element w ∈ V, w ∉ V_{0} such that for any σ ∈ U, there exists a w_{σ} ∈ V_{0} such that σ(w) = w + w_{σ}. Furthermore, for some σ ∈ U, we must have w_{σ} ≠ 0, otherwise w would lie in V_{0}. Fix such a σ. Now assume that ⋀^{i} V_{0} has a complementary submodule W and write ⋀^{i} V = ⋀^{i} V_{0} ⊕ W. Let v_{1} = w_{σ}, …, v_{i} be a basis of V_{0}, so v_{1} ∧ v_{2} ∧ ⋯ ∧ v_{i} is a basis of ⋀^{i} V_{0}. Therefore σ(w) = w + v_{1}. We may write w ∧ v_{2} ∧ ⋯ ∧ v_{i} = w_{0} + bv_{1} ∧ v_{2} ∧ ⋯ ∧ v_{i}, for some w_{0} ∈ W. Therefore we have

σ(w ∧ v_{2} ∧ ⋯ ∧ v_{i}) = w ∧ v_{2} ∧ ⋯ ∧ v_{i} + v_{1} ∧ v_{2} ∧ ⋯ ∧ v_{i} = w_{0} + (1 + b)v_{1} ∧ v_{2} ∧ ⋯ ∧ v_{i}

and

σ(w ∧ v_{2} ∧ ⋯ ∧ v_{i}) = σ(w_{0} + bv_{1} ∧ v_{2} ∧ ⋯ ∧ v_{i}) = σ(w_{0}) + bv_{1} ∧ v_{2} ∧ ⋯ ∧ v_{i}

Comparing the final expressions in these two formulas we see

w_{0} − σ(w_{0}) = v_{1} ∧ v_{2} ∧ ⋯ ∧ v_{i}

Since w_{0} − σ(w_{0}) is in W and W and ⋀^{i} V_{0} are complementary, we must have v_{1} ∧ v_{2} ∧ ⋯ ∧ v_{i} = 0 a contradiction

Proposition 2.18 Let G be a linear algebraic group defined over an algebraically closed field C and let V be a faithful G−module of dimension n. Then G is reductive if and only if for every i, 1 ≤ i ≤ n − 1, ⋀^{i} V is 1-reductive.

Proof: If G is reductive then any submodule of a module has a complementary submodule. Now assume that G is not reductive and so G_{u} ≠ (0). In the notations of Lemma 2.17.1, V_{0} ≠ (0). Since G_{u} is normal in G and the elements of V_{0} are the only elements of V left fixed by G_{u}, V_{0} is a G−invariant subspace of V. ⋀^{i} V_{0} is therefore a one dimensional G−submodule of ⋀^{i} V and by Lemma 2.17.2, it does not have a G_{u}−complement, so it cannot have a G−complement.

Let L_{0} ∈ D and let K_{0} be the Picard-Vessiot extension of k asociated to L_{0} with Galois group G_{0}. We say that L_{0} is 1-reductive if the solution space of L_{0} is 1-reductive as a G_{0} module. If K is any Picard-Vessiot extension of k, with Galois group G having a full set of solutions of L_{0}(y) = 0, then we can embedd K_{0} into K. The action of G on K_{0} factors through the action of G_{0} on K_{0}. Therefore L_{0} is 1-reductive if and only if for any Picard-Vessiot extension of k with Galois group G, having a full set of solutions of L_{0}(y) = 0, the solution space of L_{0}(y) = 0 in K is 1-reductive as a G module. Also note that L_{0} is 1reductive if and only if for each first order right factor L_{1} ∈ D of L_{0}, there exists an L̃_{1} ∈ D, relatively prime to L_{1} such that L_{0} = [L_{1}, L̃_{1}]_{l}. We shall show in the next section how the following gives an effective method to test if a linear operator is completely reducible.

Corollary 2.19 Let L ∈ D and let K be the associated Picard-Vessiot extension with Galois group G. Let L^{∧i} be an operator whose solution space is G−isomorphic to ⋀^{i} V, where V is the solution space of L in K. L is a completely reducible operator if and only if L^{∧i} is 1− reductive for each i = 1, …, n − 1.

Proof: This follows from the previous lemma by noting that L is completely reducible if and only if its Galois group is reductive.

Proposition 2.20 Let G be a linear algebraic group defined over an algebraically closed field C and let V be a faithful G−module of dimension n. Then V is an irreducible G−module if and only if:

1. For each i, 1 ≤ i ≤ n − 1, ⋀^{i} V, is 1-reductive, and

2. End_{G}(V) = C

Proof: If V is irreducible then the second condition holds by Schur’s Lemma. Furthermore, in this case G is reductive, so any submodule of a module will have a complement.

If V is not irreducible and G is reductive then End_{G}(V) ≠ C by the discussion preceeding Lemma 2.14. Assume V is not irreducible and G is not reductive. Then Proposition 2.18 implies that the first condition cannot hold.

Corollary 2.21 Let L ∈ D and let K be the associated Picard-Vessiot extension with Galois group G. Let L^{∧i} be an operator whose solution space is G−isomorphic to ⋀^{i} V, where V is the solution space of L in K. L is irreducible if and only if all of the following hold:

1. For each i, 1 ≤ i ≤ n − 1, L^{∧i} is 1−reductive.

2. dim_{C}Soln_{k}(A_{L}) = 1

Proof: This is just a restatement of Proposition 2.20.

Corollary 2.21 is the basis of our reducibility tests. Condition 2. can be restated in several ways using Lemma 2.5 and we will show in section 3.1 how each of these equivalent statements can be used to develop algorithms to test reducibility. Condition 1. appears to require that one check a possibly infinite number of possibilities. We shall show in section 3.2 that this is not the case and give an algorithm that decides if condition 1. holds.

2.4 Remarks

A good guide to the nineteenth century literature concerning linear differential equations is [15]. We will give a brief indication of the sources of the results in sections 2.1 and 2.2. Lemma 2.1.2 already occurs in [11]. In this paper, Frobenius also determines necessary and sufficient conditions for a Fuchsian equation with three singular points to be reducible. The connection between reduciblity of the equation and reducibility of the group was made by Jordan in [20] for Fuchsian equations and by Beke in [4] for general equations. In Beke’s paper, one can also find a decision procedure for determining if a linear differential equation with rational coefficients is reducible or not (a related procedure is described in [38]). Unique factorization of linear differential operators is discussed in [22]. In this paper, Landau proves the uniqueness of the number of irreducible factors and their sets of orders. At the end of the paper, Landau notes the similarity of his techniques with those used by Jordan to prove his theorem concerning composition series for finite groups. In [24], Loewy gives the complete factorization theorem (although the notion of linear equations of the same type goes back to (at least) Poincaré [36]). In a subsequent series of papers [25, 26, 27, 28], Loewy examined the notion of completely reducible operators, factorization into completely reducible operators, and what properties carry over to operators of the same type. In [29, 30] Loewy considers systems of linear differential equations and proves results analogous to the results in the above papers. These results follow easilly from either the group theoretic or D−module approach. In [33], Ore considers the ring of linear differential operators from a ring theoretic perspective. In the second part of this sequence, he defines the eigenring of an operator and shows that it is a finite dimensional algebra corresponding to solutions of a certain system of differential equations (our A_{L}). He also discusses various kinds of factorizations. In [34], Ore generalizes many of these results to skew polynomial rings F [T] where for some derivation D of F and automorphism σ of F we have T · v = σ(v)T + Dv, for all v ∈ F. Jacobson [18] (see also [19]) develops a theory of finite dimensional modules over such a ring. This theory applies to the situation when V is a finite dimension D−module (let σ= identity, so F [T] is isomorphic to F [D]). In the general situation, Jacobson shows that such a vector space can be decomposed into cyclic subspaces. Furthermore he shows that when V is completely reducible, the eigenring is a sum of matrix rings (with entries in a division algebra). For the special case of D−modules, Jacobson shows that all finite dimensional D−modules are cyclic (see [3] for references to other proofs and effective methods). Jacobson ends his paper by noting that when T is irreducible, the eigenring is a division algebra over C (here we do not assume that C is algebraically closed) and that this observation may be used to construct interesting division algebras. Amitsur further develops this idea in [1]. He recapitulates the results of Ore and Jacobson in more modern language and then uses these ideas to classify all central division algebras over a field C that are split by k where k is a transcendental extension of C. Some of the results of Ore, Jacobson and Amitsur are contained in Chapter 0 of [9].

The results of section 2.3 seem new.

Finally we note that the classical factorization algorithms can be considered in this light. Given L ∈ D let V = Soln_{k}(L) and let W be a G−invariant subspace of V, where G is the Galois group of L. If W is nontrivial, it will be the solution space of some factor L_{1} of L. We can think of L_{1} as a surjective element of Hom_{G}(V, V/W). Therefore, to decide if L is reducible, we only need to decide if there exists a surjective G−morphism of V onto a nontrivial G−module of smaller dimension. This is the philosophy behind the algorithm in [14], where the question of reducibility of systems is examined. This approach seems to be equivalent to factoring.

3 Algorithmic Considerations

Let L ∈ D, K the associated Picard-Vessiot extension of k with Galois group G and V the space of solutions of L(y) = 0 in K. Proposition 2.20 states that to test if L is irreducible in D it is necessary and sufficient to:

1. Show that End_{G}(V) = C, and

2. Show that for each i, 1 ≤ i ≤ n − 1, ⋀^{i} V is 1−reductive, i.e., each one-dimensional submodule V_{i} of ⋀^{i} V, has a complementary submodule.

In the next two subsections we will describe techniques for performing these tasks. In the third subsection we will describe an applications to computing Galois groups and some directions for further investigations.

Since the goal of this paper is to describe reducibility tests for linear differential equations (scalar equations) and not systems, we tailor our strategies to handle single n^{th} order equations (although some of these strategies can be clearly modified to handle systems). Regretably, some of the strategies require one to convert to systems. We review this process now. Recall that the companion matrix of a scalar equation L(y) = y^{(n)}−a_{n−1}y^{(n−1)}−…−a_{0} is

A = ( \begin{matrix}0 & 1 & 0 & & 0 \\ 0 & 0 & 1 & & 0 \\ ⋮ & ⋮ & ⋮ & ... & ⋮ \\ 0 & 0 & 0 & … & 1 \\ a_{n−1} & a_{n−2} & a_{n−3} & … & a_{0} \end{matrix} )

The system Y′ = AY is equivalent to the equation L(y) = 0. This means one of the following equivalent statements:

• The D modules D/D · L and k^{n} (where the action is defined by D · (v_{1}, …, v_{n})^{T} = (v′_{1}, …, v′_{n})^{T} + A(v_{1}, …, v_{n})^{T} for v ∈ k^{n}) are D−isomorphic,

• The solution spaces of L(y) = 0 and Y′ = AY (in the Picard-Vessiot extension of L) are G-isomorphic.

Using the second characterization, one sees that the space of solutions of L(y) = 0 in k and the space of solutions of Y′ = AY in k^{n} are isomorphic since these are just the G−fixed points of the solution spaces of these respective equations.

We shall also need the notion of the adjoint of a differential equation (see [35]). If L is as above, the adjoint L^{∗} of L is defined to be the equation L^{∗}(y) = (−1)^{n}y^{(n)} − (−1)^{n−1}(a_{n−1}y)^{(n−1)} − … − a_{0}y. One can show that • The D modules D/D · L^{∗}, Hom_{k}(D/D · L, k) and k^{n} (where the action is defined by

D · (v_{1}, …, v_{n})^{T} = (v′_{1}, …, v′_{n})^{T} − A^{T} (v_{1}, …, v_{n})^{T} for v ∈ k^{n}) are D−isomorphic,

• The solution spaces of L^{∗}(y) = 0 and Y′ = −A^{T} Y (in the Picard-Vessiot extension of L) are G-isomorphic.

3.1 Calculating dim_{C}End_{G}(V)

Let L be a linear differential operator with coefficients in C(x), K the associated Picar-Vessiot extension, G the Galois group and V the space of solutions of L(y) = 0 in K. In this subsection, we shall present three algorithms for calculating dim_{C}End_{G}(V) and discuss their relative merits.

Algorithm 1: We shall use the fact that End_{G}(V) is isomorphic to E_{D}(L). In the discussion preceding Corollary 2.9, we noted that this space is precisely the set of solutions in k of a system of linear differential equations A_{L}(Y) = 0 and we described how, using the division algorithm, one could effectively calculate this system (an alternate method is described in [33] II, p. 237). One then is confronted with calculating the dimension of the space of solutions in k^{n}. Occasionally, one is lucky and one can easily read off this dimension (see the example below). At present, the only general technique we know is to convert this system to a single scalar equation (of order n^{2}) using a cyclic vector computation (see the bibliography of [3]) or to an equivalent system in companion block diagonal form as in [3]. This reduces the problem to finding solutions (in k) of one or several scalar equations. When k = C(x), this latter problem was solved in the nineteenth century. For recent algorithms, that also consider other fields k, see [8, 41]. An open problem is the problem of finding the dimension of the space of solutions in k^{n} of this system without having to convert to scalar equations.

We also note that if one has found an element \overline{R} ∈ E_{D}(L), R of order greater than or equal to 1, then one can produce a non-trivial factor of L. To do this, let R ∈ E_{D}(L), ord(R) ≥ 1. We then have that LR is divisible on the right by L. Therefore, if z is a solution of L(y) = 0, we have that R(z) is again a solution of L(y) = 0. This implies that z ↦ R(z) is a linear map of the solution space of L(y) = 0 into itself. If c is an eigenvalue of this map, then (R − c)(y) = 0 and L(y) = 0 have a common solution. Since 0 < ord(R − c) < n, GCRD(R − c, L) will be a non-trivial factor of L. Therefore given \overline{R} ∈ E_{D}(L), the condition GCRD(R − c, L) ≠ 1, defines a nonempty set of at most n constants and for each of these GCRD(R − c, L) will be a non-trivial factor of L.

Example 3.1 In Example 2.10 we determined A_{L} using the above method. One can also find factors as described above. For example, \overline{a}_{0} = −4, \overline{a}_{1} = x, \overline{a}_{2} = 0, \overline{a}_{3} = 0 is a solution of the system, so R = xD − 4 ∈ E(D^{4}). We then have that GCRD(D^{4}, xD − 4 − c) ≠ 1 if and only if c = −1, −2, −3, −4. One can see this by perfoming the euclidean algorithm or more simply (in this case) by noting that GCRD(D^{4}, xD − 4 − c) ≠ 1 if and only if xD − 4 − c divides D^{4} which happens if and only if y = x^{4+c} is a solution of D^{4}(y) = 0.

Algorithm 2: This strategy is based on the fact that End_{G}(V) is G-isomorphic to (V^{∗}⊗V)^{G}, the G−invariant elements of the tensor product of V and its dual V^{∗}. We shall construct an operator whose solution space is G-isomorphic to this latter G-module. Let A be the companion matrix of L and let B = −A^{T} ⊗ I + I ⊗ A, where I is the n × n identity matrix. It is known ([10], Sec. 1.2.7) that the solution space of Y′ = BY is (V^{∗} ⊗ V)^{G}. We are now again confronted with finding the dimension of the space of rational solutions of a system of differential equations. The advantage of this approach over the previous one is that the system Y′ = BY is easy to compute and that it is a first order system. On the other hand, one has lost whatever special properties the system Y′ = A_{L}Y possesses. Again, one can occassionally be lucky and avoid a cyclic vector computation. (Note that the system Y′ = BY can be rerwritten in a more classical way using matrix notation. If we represent an element of End_{D}(D/caldL) as a map X ↦ ZX, Z an n × n matrix, for which X′ = AX and (ZX)′ = A(ZX), then Z will satisfy Z′ = AZ − ZA.)

Example 3.2 Let k = C(x) and L = D^{4}. The associated companion matrix is the 4 × 4 zero matrix, so the matrix B = −A^{T} ⊗ I + I ⊗ A is the 16 × 16 zero matrix. Clearly the space of solutions of Y′ = BY in k^{16} has dimension 16.

Algorithm 3: The disadvantage of the previous two strategies is that they convert a question about a scalar equation to a question about a system of equations and that to answer the latter question one must (at present) convert back to scalar equations. We will give two algorithms that avoid this and discuss nondeterministic versions of these as well. Given a linear operator L we wish to construct, as directly as possible an operator L̂ whose solution space is G−isomorphic to V ⊗ V^{∗}. It is not hard to find an equation whose solution space is V^{∗} - this is just the adjoint. The question is therefore: given two operators L_{1} and L_{2} with solution spaces V_{1} and V_{2}, construct an equation whose solution space is V_{1} ⊗ V_{2}. We shall do this below. The basic philosophy motivating this algorithm is that tensor products of generic cyclic vectors are again cyclic.

Given two operators L_{1}, L_{2} ∈ D there exists an operator L_{1}◯ s L_{2} ∈ D having the following property: If K is a differential extension of k containing a full set of solutions {u_{1}, …, u_{n_{1}}} of L_{1}(y) = 0 and {v_{1}, …, v_{n_{2}}} of L_{2}(y) = 0, then K contains a full set of solutions of L_{1}◯ s L_{2}(y) = 0 and the solution space of this latter equation is spanned by {u_{1}v_{1}, …, u_{n_{1}}v_{1}, …, u_{n_{1}}v_{n_{2}}}. (see [40, 43] where a method is given to compute this operator). When L_{1} = L_{2} we write L^{◯ s 2} for L◯ s L. Note that the solution space of L_{1}◯ s L_{2}(y) = 0 is a homomorphic image of V_{1} ⊗ V_{2} where V_{i} is the solution space of L_{i}(y) = 0.

Example 3.3 Let L = D^{4} and k = C(x). The solution space V of L(y) = 0 is the set of polynomials of degree at most 3. Therefore the solution space of L^{◯ s 2}(y) = 0 is the set of polynomials of degree at most 6, so L^{◯ s 2} = D^{7}. This latter space has dimension 7 while V ⊗ V has dimension 16.

Despite this example, we will want to use the construction of L_{1}◯ s L_{2}(y) = 0 to find an operator whose solution space is isomorphic to V_{1} ⊗ V_{2}. To do this we will have to replace L_{2} by an operator of the same type. The following lemma gives two ways that this can be done. Before we state this lemma, we describe an ancillary construction. Given L ∈ D, ord(L) = n and (b_{0}, …, b_{n−1}) ∈ k^{n}, we denote by L^{(b_{0},...,b_{n−1})} the monic operator whose solution space is {z | z = b_{0}y + b_{1}y′ + … + b_{n−1}y^{(n−1)} for y satisfying L(y) = 0}. One can effectively construct L^{(b_{0},...,b_{n−1})} from L by letting z and y be indeterminates and differentiating z = b_{0}y + b_{1}y′ + … + b_{n−1}y^{(n−1)} n times. Using L(y) = 0 to replace all y^{(i)}, i ≥ n by k-linear combinations of y^{(i)}, i < n, we are left with n + 1 k-linear equations in the n quantities y, …, y^{(n−1)}. Therefore, there will be a relation c_{n}z^{(n)} + … + c_{0}z = 0. Such a relation of smallest order will give L^{(b_{0},...,b_{n−1})}. Note that L^{(b_{0},...,b_{n−1})} will have order n if and only if L(y) = 0 and R(y) = b_{0}y + … + b_{n−1}y^{(n−1)} = 0 have no common solutions. In this case, L and L^{(b_{0},...,b_{n−1})} will be of the same type.

Lemma 3.4 Let k = C(x) and let L_{1}, L_{2} ∈ D, ord(L_{1}) = n, ord(L_{2}) = m.

1. For all but a finite number of c ∈ C, ord(L_{1}◯ s L_{2}^{(1,(x−c)^{mn},(x−c)^{2mn},...,(x−c)^{(n−1)mn})}) = mn.

2. There exist polynomials b_{0}, …, b_{m−1} with constant coefficients and of degree at most mn − 1 such that ord(L_{1}◯ s L_{2}^{(b_{0},...,b_{n−1})}) = mn.

Proof: To prove 1., first consider the operators L_{1}◯ s L_{2}, L_{1}◯ s L_{2}^{(0,1,0,...,0)}, …, L_{1}◯ s L_{2}^{(0,0,0,...,1)}. Each has order at most mn and only a finite number of singular points. Let c be a regular point of all of these operators. The standard existence and uniqueness theorem implies that if y is any solution of one of these such that y and all of its derivatives up to order mn vanish at c, then y is identically zero. Let {u_{1}, …, u_{n}} and {v_{1}, …, v_{m}} be fundamental sets of solutions of L_{1}(y) = 0 and L_{2}(y) = 0 respectively and let z_{i} = v_{i} + (x − c)^{mn}v′_{i} + (x − c)^{2mn}v′′_{i} + … + (x − c)^{mn(mn−1)}v_{i}^{(m−1)} for 1 ≤ i ≤ m. We claim that the elements {u_{i}v_{j} | 1 ≤ i ≤ n, 1 ≤ j ≤ m} are linearly independent. This suffices to prove 1. To prove the claim, assume that for some c_{ij} ∈ C, 0 = ∑_{i,j} c_{ij}u_{i}z_{j}. We then have that

0 = ∑_{i,j} c_{ij}u_{i}z_{j} = ∑_{t=0}^{m−1}(∑_{i,j} c_{i,j}u_{i}v_{j}^{(t)})(x − c)^{tmn}

Each ∑_{i,j} c_{i,j}u_{i}v_{j}^{(t)} is either zero or vanishes to order at most mn−1 at c. Comparing powers of x − c in the above expression we can therefore conclude that for each t, ∑_{i,j} c_{i,j}u_{i}v_{j}^{(t)} = 0.

Since the matrix (v_{j}^{(k)}) is invertible, we have that for each j, ∑_{i,j} c_{i,j}u_{i} = 0. Since the u_{i} are linearly independent, we have c_{i,j} = 0 for all i, j.

To prove 2., let B_{0}, …, B_{m−1} be differential indeterminates, let {u_{1}, …, u_{n}} and {v_{1}, …, v_{m}} be as above and let z_{i} = B_{0}v_{i} +B_{1}v′_{i} +…+B_{m−1}v_{i}^{(m−1)}. Consider the differential polynomial R(B_{0}, …, B_{m−1}) = det(W r(u_{1}z_{1}, …, u_{1}z_{m}, …, u_{n}z_{m})). This polynomial is not identically zero (this follows from 1.) and has order at most mn − 1 in each variable B_{i}. Therefore, a result of Ritt ([37], p.35) implies that there exist polynomials b_{0}, …, b_{m−1} of degree at most mn − 1 such that R(b_{0}, …, b_{m−1}) ≠ 0. These polynomials satisfy the conclusion of 2.

Example 3.5 This illustrates statement 1. of the above lemma. Let L = D^{4}. We then have that L^{(1,x^{16},x^{32},x^{48})} =

D^{4}−^{\frac{480 x14(364 x15+577536 x45+8336640 x60+3+37748736 x75+21387 x30)}{228128 x45+5824 x30+96 x15+4620288 x60+53354496 x75+201326592 x90+1}} D^{3}
+^{\frac{480 x13(−1339 x15+6983424 x45+164465664 x60−28+1063256064 x75+79696 x30)}{228128 x45+5824 x30+96 x15+4620288 x60+53354496 x75+201326592 x90+1}} D^{2}
−^{\frac{(4399992668160 x75+214477701120 x60−8726446080 x45−413806080 x30−4569600 x15+43680)x12}{228128 x45+5824 x30+96 x15+4620288 x60+53354496 x75+201326592 x90+1}} D

If one calculates L◯ s L^{(1,x^{16},x^{32},x^{48})} one gets an operator of order 16 with enormous coefficients. For example the coefficient of D^{8} is a quotient of polynomials of degree 150 with 48 digit coefficients.

Example 3.6 This illustrates statement 2. of the above lemma. We again let L = D^{4}. We then have that L^{(x^{12},x^{8},x^{4},1)} =

D^{4}− \frac{884736+48 x30−1032 x25+14592 x20−131736 x15+559104 x10−1333632 x5}{x(−24 x25+384 x20−3992 x15+19968 x10−57984 x5+49152+x30)} D^{3}
+ \frac{936 x30−17664 x25+213624 x20−1617792 x15+5643648 x10−10520064 x5+5455872}{x2(−24 x25+384 x20−3992 x15+19968 x10−57984 x5+49152+x30)} D^{2}
− \frac{8736 x30−141144 x25+1383264 x20−7997952 x15+21523968 x10−26855424 x5+11354112}{(−24 x25+384 x20−3992 x15+19968 x10−57984 x5+49152+x30)x3} D
+^{\frac{360 x(39232 x5−14336−24704 x10+8612 x15+91 x25−1220 x20)}{−24 x25+384 x20−3992 x15+19968 x10−57984 x5+49152+x30}}

Note that the degrees of the numerators and denominators of the coefficients are considerably smaller than in the previous example. If one calculates L◯ s L^{(x^{12},x^{8},x^{4},1)} one again gets an operator of order 16 but with better coefficients. For example the coefficient of D^{8} is a quotient of polynomials of degree 35 with 13 digit coefficients.

We now give two procedures to calculate the dimension of End_{G}(V).

Algorithm 3A: This uses Lemma 3.4.1. Select c ∈ C and form L^{∗}◯ s L^{(1,(x−c)^{n^{2}},(x−c)^{2n^{2}},...,(x−c)^{(n−1)n^{2}})}. If ord(L^{∗}◯ s L^{(1,(x−c)^{n^{2}},(x−c)^{2n^{2}},...,(x−c)^{(n−1)n^{2}})}) = n^{2}, then we have found an operator whose solution space is G-isomorphic to V^{∗} ⊗ V. One then proceeds as in the other algorithms to find the dimension of the space of rational solutions of this operator.

If ord(L^{∗}◯ s L^{(1,(x−c)^{n^{2}},(x−c)^{2n^{2}},...,(x−c)^{(n−1)n^{2}})}) < n^{2}, select another value for c and recalculate. Since there are only a finite number of bad values for c, we will eventually find one that works. In Example 3.5, this strategy was used. The proof of Lemma 3.4 gives a way of finding a value of c that works. An alternative approach is to form L^{∗}◯ s L^{(1,(x−c)^{n^{2}},(x−c)^{2n^{2}},...,(x−c)^{n^{2}(n^{2}−1)})} for an indeterminate c with c′ = 0. The condition that this operator have order n^{2} will be equivalent to p(c) ≠ 0 for some polynomial p that will be found in the process of forming the operator. We also note that the size of the set of “bad points” can be bounded in terms of the coefficients of L using the generalization of Fuchs’ relation ([5, 42]).

Algorithm 3B: This is based on Lemma 3.4.2 and was used in Example 3.6. Let B_{0}, …, B_{n−1} be polynomials of degree n^{2}−1 with indeterminate coefficients. The condition that L^{∗}◯ s L^{(B_{0},...,B_{n−1})} is of order n^{2} − 1 gives a non-empty (by Lemma 3.4.2) Zariski open set of coefficients in C. The defining equations can be constructed and a element of this set can be found. One then proceeds as above to find the dimension of the space of rational solutions.

In practice (and in Example 3.6) one should select arbitrary polynomials b_{0}, …, b_{n−1} with constant coefficients and of degree at most n^{2} − 1 and form L^{∗}◯ s L^{(b_{0},...,b_{n−1})}. If this operator has order n^{2}, proceed as above to find the dimension of the space of rational solutions. If the order is less than n^{2}, select another choice of b_{0}, …, b_{n−1}. We know from Lemma 3.4 that some choice will work. It would be of interest to understand the probabilistic aspects of this approach.

3.2 Deciding if ∧^{i}V is 1-reductive

To decide if, for 1 ≤ i ≤ n − 1, ∧^{i}V is 1-reductive, we proceed in two steps. Firstly, we shall show how to find an operator L^{∧i} whose solution space is G-isomorphic to ∧^{i}V. Secondly, we shall produce an algorithm that, given a linear operator, decides if this operator is 1−reductive.

3.2.1 An operator whose solution space is ∧^{i}V

We shall present two algorithms.

Algorithm 4: Let A be the n × n companion matrix of L. One can construct an ( \begin{matrix}n \\ i \end{matrix} ) ×

( \begin{matrix}n \\ i \end{matrix} ) first order system whose solution space is G−isomorphic to ∧^{i}V. This is done in

[14] in the following way. Let y_{1}, …, y_{n} be indeterminates and let Y = (y_{1}, …, y_{n})^{T}. Let S_{i} be the set of all i−tuples J = (j_{1}, …, j_{i}), 1 ≤ j_{1} < … < j_{i} ≤ n. For each J ∈ S_{i}, let z_{J} = y_{j_{1}} ∧…∧y_{j_{i}}. Formally differentiating, we have z′_{J} = y′_{j_{1}} ∧…∧y_{j_{i}} +…+y_{j_{1}} ∧…∧y′_{j_{i}}. Using Y′ = AY, we may rewrite each y′_{j} as a linear combination of the y_{i}, …, y_{n} and so have z′_{J} = ∑_{H∈S_{i}} c_{J,H}z_{H} for some constants c_{J,H}. Ordering the i−tuples in S_{i} in some manner, we

have Z′ = A^{∧i}Z where Z = (z_{1}, …, z_{j_{t}}), t = ( \begin{matrix}n \\ i \end{matrix} ) , and A^{∧i} = (c_{J,H}). We refer the reader to

[14] for a proof that the solution space of this system is G−isomorphic to ∧^{i}V. Construction

of a cyclic vector (for the dual system) will yield an operator L^{∧i} of order ( \begin{matrix}n \\ i \end{matrix} ) whose

solution space is G−isomorphic to ∧^{i}V.

Algorithm 5: We now give an algorithm that avoids the conversion from scalar equation to matrix system and back. This relies on the following definitions and lemmas.

We first define the i^{th} Associated Operator L. Let K be the Picard-Vessiot extension of k associated to L(y) = 0 and let y_{1}, …, y_{n} be a fundamental set of solutions of L(y) = 0 in K. We define L^{det(i)} to be the monic operator of smallest order whose solution set is spanned by {detW r(y_{j_{1}}, …, y_{j_{i}}) | (j_{1}, …, j_{i}) ∈ S_{i}}. One sees that the vector space V^{det(i)} spanned by these elements is left invariant under the action of the Galois group G and so this operator has coefficients in k. If V is the solution space of L(y) = 0, one sees that the map sending y_{j_{1}} ∧ … ∧ y_{j_{i}} to detW r(y_{j_{1}}, …, y_{j_{i}}) is a G-homomorphism of ∧^{i}V onto V^{det(i)}. Therefore, the solution space of L^{det(i)} is a homomorphic image of ∧^{i}V and is an isomorphic image if

and only if the order of L^{det(i)} is ( \begin{matrix}n \\ i \end{matrix} )^{1}.

One can calculate L^{det(i)} directly from L by setting w = detW r(y_{1}, …, y_{i}) differentiating

this ν = ( \begin{matrix}n \\ i \end{matrix} ) times, using the relation L(y_{j}) = 0 to eliminate derivatives of y_{j} of order

larger than n−1, and then finding a linear dependence among the resulting ν +1 expressions for z, z′, …, z^{ν}. If there is more than one such dependence, one takes one where the maximum z^{(j)} is as small as possible.

Example 3.7 Let L = D^{4} and i = 2. If we use y_{i} = x^{i}, i = 0, 1, 2, 3 as a basis for the solution space, the set {detW r(y_{j_{1}}, …, y_{j_{i}}) | (j_{1}, …, j_{i}) ∈ S_{i}} is {1, 2x, 3x^{2}, x^{2}, 2x^{3}, x^{4}}. Therefore, L^{det(2)} = D^{5}, so the solution space of L^{det(2)} is not ∧^{2}V, which has dimension 6.

1In [38], Section 167, Schlesinger also defines an associated operator. Schlesinger only defines this operator when the space V^{det(i)} has dimension ( \begin{matrix}n \\ i \end{matrix} ). In this case, our i^{th} associated operator would be called the (n − i)^{te} associirte Differentialgleichung in his terminology.

Example 3.8 Let L = D^{4} − 4xD − (x^{4} + 2). Calculating^{2} one finds that

L^{det(2)} = D^{6} − \frac{1}{x}D^{5} + 4x^{4}D^{2} + 20x^{3}D

Therefore in this case the solution space of L^{det(2)} is ∧^{2}V.

Since we want an operator whose solution space is G−isomorphic to ∧^{i}V, we wish to guarantee that L^{det(i)} has the correct order. This will be done with the aid of the following two lemmas. Again, we shall follow the philosophy that the tensor product of generic cyclic vectors is cyclic.

Let K be a differential field with constants C and y_{1}, …, y_{n} ∈ K, linearly independent over C. Let B_{0}, …, B_{n−1} be differential indeterminates and, for i = 1, …, n, let z_{i} = B_{0}y_{i} + B_{1}y′_{i} + … + B_{n−1}y_{i}^{(n−1)}. Note that the differential field K < B_{0}, …, B_{n−1} > has the same constants as K. For each J = (j_{1}, …, j_{i}) ∈ S_{i} let W_{J} = detW r(z_{j_{1}}, …, z_{j_{i}}) ∈ K < B_{0}, …, B_{n−1} >.

Lemma 3.9 For each i, 1 ≤ i ≤ n, {W_{J} | J ∈ S_{i}} forms a linear independent set over C.

Proof: The proof proceeds by induction on i. For i = 1 this is just a restatement of the fact that y_{1}, …, y_{n} are linearly independent over C. Now assume that the statement is true

for i − 1. For each J = (j_{1}, …, j_{i}) ∈ S_{i}, we have that W_{J} = ∑_{r=1}^{i}(−1)^{r+1}z_{j_{r}}^{(i−1)}W_{(j_{1},...,_{j_{r}},...,j_{i})}

(expand by minors using the last row). Note that the order of each B_{t}, 0 ≤ t ≤ n − 1 in

W_{(j_{1},...,_{j_{r}},...,j_{i})} is at most i − 2. Furthermore, note that z_{j_{r}}^{(i−1)} = B_{0}^{(i−1)}y_{j_{r}} + … + B_{n−1}^{(i−1)}y_{j_{r}}^{(n−1)} +

R(B_{0}, …, B_{n−1}, y_{j_{r}}) where R is a differential polynomial with rational coefficients and of order at most i − 2 in each B_{j}. Therefore

W_{J} = ∑_{r=1}^{i}(−1)^{i−1} ∑_{t=0}^{n−1} B_{t}^{(i−1)}y_{j_{r}}^{(t)}W_{(j_{1},...,_{j_{r}},...,j_{i})} + R_{J}

where R_{J} has order at most i − 2 in each B_{t}. Now assume that ∑_{J∈S_{i}} c_{J}W_{J} = 0 for some C_{J} ∈ C. If we write ∑_{J∈S_{i}} c_{J}W_{J} as a polynomial in the B_{t}^{(i−1)}, t = 0, …, n − 1 we see that for each t the coefficient of B_{t}^{(i−1)} is

∑_{J=(j_{1},...,j_{i})∈S_{i}} c_{J} ∑_{r=1}^{i}(−1)^{i−1}y_{j_{r}}^{(t)}W_{(j_{1},...,_{j_{r}},...,j_{i})}

and that this must equal 0. Rewriting this last expression, we get, for t = 0, …, n − 1

∑_{j=1}^{n} y_{j}^{(t)} ∑_{J∈S_{i}^{j}} ±c_{J}W_{J|j} = 0

2In [2], Appell works out most of the relations for L^{det(2)}, when L is a fourth order operator

where S_{i}^{j} = {J ∈ S_{i} | i appears in J} and J | j is the (i − 1)−tuple obtained from J by deleting j. Since the matrix (y_{j}^{(t)})_{j=1,...,n}^{t=0,...,n−1} is invertible, we have for each j, that

∑_{J∈S_{i}^{j}} ±c_{J}W_{J|j} = 0

By induction, {W_{J|j} | J ∈ S_{i}^{j}} is a linearly independent set, so all c_{J} = 0. .

Lemma 3.10 Let k = C(x) and L ∈ D. For each i, 1 ≤ i ≤ n − 1, there exist polynomials p_{0}, …, p_{n−1} of degree at most i+( \begin{matrix}n \\ i \end{matrix} )−2 such that the i^{th} associated operator of L^{(p_{0},...,p_{n−1})} has order ( \begin{matrix}n \\ i \end{matrix} ). Furthermore, one can select p_{0}, …, p_{n−1} of degree at most max_{0≤i≤n−1}\{i+ ( \begin{matrix}n \\ i \end{matrix} ) − 2\} such that for all i = 1, …, n − 1, the order of the i^{th} associated operator of

L^{(p_{0},...,p_{n−1})} is ( \begin{matrix}n \\ i \end{matrix} ).

Proof: Fix i and let W_{i} be the determinant of the wronskian matrix of the {W_{J} | J ∈ S_{i}}. By the previous lemma, we know that W_{i} is non-zero. This differential polynomial has order at most i − 1 + ( \begin{matrix}n \\ i \end{matrix} ) − 1 = i + ( \begin{matrix}n \\ i \end{matrix} ) − 2 in the variables P_{0}, …, P_{n−1}. Therefore, the result of Ritt ([37], p.35) implies that there exist polynomials p_{0}, …, p_{n−1} of degree at most i + ( \begin{matrix}n \\ i \end{matrix} ) − 2 such that W_{i}(p_{0}, …, p_{n−1}) ≠ 0. This guarantees that the order of L^{det(i)} is ( \begin{matrix}n \\ i \end{matrix} ). Setting W = ∏_{i=1}^{n−1} W_{i}, the result of Ritt implies that there are polynomials

p_{0}, …, p_{n−1} of degree at most max_{2≤i≤n−1}\{i + ( \begin{matrix}n \\ i \end{matrix} ) − 2\} such that W(p_{0}, …, p_{n−1}) ≠ 0.

This gives the final result.

We can now state the algorithm. Let P̃_{0}, …, P̃_{n−1} be polynomials of degree i+ ( \begin{matrix}n \\ i \end{matrix} )−2 with indeterminates for coefficients. The condition that (L^{(P̃_{0},...,P̃_{n−1})})^{i} have order ( \begin{matrix}n \\ i \end{matrix} ) defines a non-empty Zariski open set of constants whose defining equations can be found. Furthermore one can find a point in this set. Using this as coefficients in the P̃_{0}, …, P̃_{n−1}, we can get polynomials p_{0}, …, p_{n−1} such that (L^{(p_{0},...,p_{n−1})})^{det(i)} has order ( \begin{matrix}n \\ i \end{matrix} ).

In practice, we keep selecting arbitrary p_{0}, …, p_{n−1} and form (L^{(p_{0},...,p_{n−1})})^{det(i)} until we find one of the prescribed order.

Example 3.11 Let L = D^{4}. We have seen that L^{det(2)} has order 5. When we consider L^{(1,x^{2},0,0)} we get L^{(1,x^{2},0,0)} =

D^{4} − \frac{(72 x^{2} + 12 + 72 x)}{36 x^{2} + 24 x^{3} + 1 + 12 x}D^{3} + \frac{(72 + 144 x)}{36 x^{2} + 24 x^{3} + 1 + 12 x}D^{2} − \frac{144}{36 x^{2} + 24 x^{3} + 1 + 12 x}D

and that (L^{(1,x^{2},0,0)})^{det(2)} =

D^{6}+^{\frac{(145152 x8+580608 x7+852768 x6+544752 x5+125064 x4−13392 x3−10332 x2−1440 x−54)}{12096 x9+54432 x8+94176 x7+77544 x6+30024 x5+3852 x4−756 x3−288 x2−30 x−1}} D^{5}

+^{\frac{(6967296 x10+34836480 x9+68117760 x8+64696320 x7+28615680 x6+1990656 x5−3363120 x4−1438560 x3−252720 x2−19800 x−504)}{290304 x12+1741824 x11+4364928 x10+5916672 x9+4696704 x8+2198016 x7+558360 x6+42120 x5−16308 x4−5316 x3−684 x2−42 x−1}} D^{4}

−^{\frac{(15178752 x5+6967296 x9−1052352 x3+53747712 x7+684288 x4+43047936 x6−28512 x+31352832 x8−792−292896 x2)}{290304 x12+1741824 x11+4364928 x10+5916672 x9+4696704 x8+2198016 x7+558360 x6+42120 x5−16308 x4−5316 x3−684 x2−42 x−1}} D^{3}

+^{\frac{(15552 x2+2592+15552 x)(336 x4+672 x3+288 x2+32 x+1)}{290304 x12+1741824 x11+4364928 x10+5916672 x9+4696704 x8+2198016 x7+558360 x6+42120 x5−16308 x4−5316 x3−684 x2−42 x−1}} D^{2}

−^{\frac{(15552+31104 x)(336 x4+672 x3+288 x2+32 x+1)}{290304 x12+1741824 x11+4364928 x10+5916672 x9+4696704 x8+2198016 x7+558360 x6+42120 x5−16308 x4−5316 x3−684 x2−42 x−1}} D

+ \frac{10450944 x4+20901888 x3+8957952 x2+995328 x+31104}{290304 x12+1741824 x11+4364928 x10+5916672 x9+4696704 x8+2198016 x7+558360 x6+42120 x5−16308 x4−5316 x3−684 x2−42 x−1}

3.2.2 Deciding if an operator is 1-reductive

We will show that the algorithm 1-reductive, below, decides if an operator L is 1−reductive. We shall asume that our differential field k (with algebraically closed constants) comes equiped with two ancillary algorithms. The first is an algorithm to decide if, given a differential operator L ∈ D, L(y) = 0 has a nonzero solution in k and, if so, produces such a solution. The second is an algorithm to decide if, given a differential operator L ∈ D, L(y) = 0 has a solution y such that y′/y = u ∈ k, and, if such a solution exists, produces such an element u ∈ k. This is equivalent to deciding if the associated Riccati equation has a solution u in k and is also equivalent to deciding if L has a first order right factor of the form D −u for some u ∈ k. As we have already noted, such algorithms exist for \overline{ℚ}(x), as well as for any finite purely transcendental liouvillian extension of \overline{ℚ}(x) or for any elementary extension of \overline{ℚ}(x). In the following, if L_{1}, L_{2} ∈ D, Quotient(L_{1}, L_{2}) will denote the unique operator A ∈ D such that L_{1} = AL_{2} + B for some B ∈ D with ord(R) < ord(L_{1}) and L_{1}^{∗} will denote the adjoint of L_{1}.

Recall that an operator R is 1−reductive if, for any first order right factor S of R there exists an S̃, relatively prime to S, such that R = [S, S̃]_{l}. We first will present an effective criterion (Lemma 3.12) to decide if, given such an S, whether or not an S̃ as above exisits. We will then show that one does not need to check this for all right factors S (a possibly infinite set) and that it is enought to check this for a suitably defined sequence of pairs of operators (R_{i}, S_{i}), where S_{i} has order 1 and is a right divisor of R_{i}. In the following lemma, we have occasion to take an operator L and an element h ∈ k and form the new operator e^{∫ h} ∘ L ∘ e^{− ∫ h}. Note that is nothing more that the operator gotten from L by replacing D by D − h.

Lemma 3.12 Let S, R ∈ D, S = D − h, R ≠ 0 and assume that S is a right divisor of R. The following are equivalent:

1. There exists an S̃ ∈ D, relatively prime to S, such that R = [S, S̃]_{l}.

2. There exists an \overline{R}_{0} ∈ E_{D}(S, R) ≠ 0 such that S does not divide R_{0} on the right.

3. For T := e^{∫ h} ∘ R^{∗} ∘ e^{− ∫ h}, T (y) = 0 has a nonzero solution g ∈ k, such that for R_{0} = (Quotient(R^{∗}, −g^{−1}D + g^{−2}g′ − g^{−1}h))^{∗}, S does not divide R_{0} on the right.

Proof: Let K be the Picard-Vessiot extension of k corresponding to R and let G be its Galois group. Assume that 1. is true. We then have that Soln_{K}(R) = Soln_{K}(S)⊕Soln_{K}(S̃) as G− modules. Let ϕ be the projection of Soln_{K}(R) onto Soln_{K}(S). Using the correspondence given in Lemma 2.5, this implies that there exists an \overline{R}_{0} ∈ E_{D}(S, R) such that R_{0}(y) = y for all y ∈ Soln_{K}(S) ⊂ Soln_{K}(R). In particular S does not divide R_{0} on the right, so 2. holds.

Now assume, that 2. holds. Using the correspondence given in Lemma 2.5, \overline{R}_{0} corresponds to a homomorphism ϕ ∈ Hom_{G}(Soln_{K}(R), Soln_{K}(S)). Since S does not divide R_{0} on the right, ϕ induces an isomorphism on Soln_{K}(S). Therefore, we may write Soln_{K}(R) = Soln_{K}(S) ⊕ Ker(ϕ). Since Ker(ϕ) is a G−submodule of Soln_{K}(R), there exists an operator S̃ such that Soln_{K}(S̃) = Ker(ϕ). Therefore, 1. holds.

Assume that 2. is true and let \overline{R}_{0} ∈ E_{D}(S, R) with R_{0} ≠ 0 and ord(R_{0}) < ord(R). We then have that SR_{0} = AR for some A ∈ D. Comparing orders, we see that ord(A) = 0 so A = g ∈ k, g ≠ 0. Taking adjoints of both sides of the equation R = g^{−1}SR_{0} we have

R^{∗} = R_{0}^{∗}S^{∗}g^{−1}
= R_{0}^{∗}(−D − h)g^{−1}
= R_{0}^{∗}(−g^{−1}D + g^{−2}g′ − g^{−1}h)
= R_{0}^{∗}(−g^{−1})(D − g^{−1}g′ + h)

Therefore y = ge^{− ∫ h} is a solution of R^{∗}(y) = 0 and so g is a solution of T. Furthermore, R_{0}^{∗} = Quotient(R^{∗}, −g^{−1}D + g^{−2}g′ − g^{−1}h) so R_{0} = (Quotient(R^{∗}, −g^{−1}D + g^{−2}g′ − g^{−1}h))^{∗} and 3. holds.

Now assume that T has a non-zero solution g ∈ k. This implies that y = ge^{− ∫ h} is a solution of R^{∗}(y) = 0. Therefore, for some R̃ ∈ D, we have

R^{∗} = R̃(D − g^{−1}g′ + h)
= R̃(−g)(−g^{−1}D + g^{−2}g′ − g^{−1}h)
= R_{0}^{∗}(−g^{−1}D + g^{−2}g′ − g^{−1}h)

where R_{0} = (R̃(−g))^{∗}. Therefore, R = (−g^{−1}D + g^{−2}g′ − g^{−1}h)^{∗}R_{0} = g^{−1}(D − h)R_{0}. Rewritting this as gR = (D − h)R_{0}, we see R_{0} ∈ E_{D}(S, R). Therefore, 3. holds.

We now show that the problem of deciding if an operator is 1− reductive can be reduced to applying the above criterion to a suitably defined sequence of pairs of operators. We will need the following definition. Let L ∈ D and m > 1. A test set T_{m} of length m for L is a set of two sequences {(R_{1}, …, R_{m}), (S_{1}, …, S_{m−1})} of nonzero operators R_{i}, S_{i} ∈ D such that

1. R_{1} = L,

2. ord(S_{i}) = 1 and S_{i} divides R_{i} on the right for i = 1, …, m − 1.

3. ord(R_{i+1}) < ord(R_{i}), \overline{R}_{i+1} ∈ E_{D}(S_{i}, R_{i}) and S_{i} does not divide R_{i+1} on the right for i = 1, …, m − 1.

The only test set of length 1 for L is the set {R_{1} = L}. Note that the conditions R_{1} = L and ord(R_{i+1}) < ord(R_{i}) imply that any test set for L has length at most ord(L). We say that a test set Tm̃ = {(R̃_{1}, …, R̃m̃), (S̃_{1}, …, S̃_{m̃−1})} extends a test set T_{m} = {(R_{1}, …, R_{m}), (S_{1}, …, S_{m−1})} if m̃ ≥ m, R̃_{i} = R_{i} for i = 1, …, m and S̃_{i} = S_{i} for i = 1, …, m − 1.

Lemma 3.13 Let L ∈ D and let K be the Picard-Vessiot extension of k corresponding to L(y) = 0. Let T_{m} be a test set of length m for L. Then for i = 2, …, m, R_{i}(y) = 0 and S_{i}(y) = 0 have complete sets of solutions in K and

Soln_{K}(L) = Soln_{K}(R_{i}) ⊕ Soln_{K}(S_{i−1}) ⊕ … ⊕ Soln_{K}(S_{1})

Proof: Note that Soln_{K}(L) = Soln_{K}(R_{1}) so to prove the lemma it is enough to show that Soln_{K}(R_{i}) = Soln_{K}(R_{i+1}) ⊕ Soln_{K}(S_{i}) (Lemma 2.1 will yield the statement concerning complete sets of solutions). Since \overline{R}_{i+1} ∈ E_{D}(S_{i}, R_{i}) we have S_{i}R_{i+1} = T R_{i} for some T ∈ D. Comparing orders, we see that ord(T) = 0. Therefore R_{i+1} maps solutions of R_{i} onto the solution space of S_{i}. The solution space of R_{i+1} is the kernel of this map. Furthermore, the condition that S_{i} does not divide R_{i+1} on the right insures that Soln_{K}(R_{i+1}) ∩ Soln_{K}(S_{i}) =

(0) so Soln_{K}(R_{i}) = Soln_{K}(R_{i+1}) ⊕ Soln_{K}(S_{i}).

Lemma 3.14 Let L ∈ D. The following are equivalent:

1. L is 1−reductive.

2. For any m, if T_{m} = {(R_{1}, …, R_{m}), (S_{1}, …, S_{m−1})} is a test set for L of length m then either

(a) for any first order right factor S_{m} of R_{m} there exists an R_{m+1} ∈ D such that T_{m+1} = {(R_{1}, …, R_{m}, R_{m+1}), (S_{1}, …, S_{m−1}, S_{m})} is a test set, or

(b) R_{m} has no first order right factor in D

3. For some m ≤ n, there is a test set T_{m} for L of length m such that R_{m} has no first order right factor in D.

Proof: Let G be the Galois group of L. Assuming 1. holds we wish to show that 2. holds. Let T_{m} be a test set for L of length m. If R_{m} has no first order right factor, we are done. Let S_{m} be a first order right factor. Lemma 3.13, R_{m} has a full set of solutions in K and Soln_{K}(R_{m}) ⊂ Soln_{K}(L). By Lemma 2.1.3, S_{m} will also have a full set of solutions in K and Soln_{K}(S_{m}) ⊂ Soln_{K}(R_{m}) ⊂ Soln_{K}(L). Since L is 1−reductive, we may write Soln_{K}(L) = Soln_{K}(S_{m})⊕W for some G-module W. We then have Soln_{K}(R_{m}) = Soln_{K}(S_{m})⊕(W ∩Soln_{K}(R_{m})). Let π be the projection of Soln_{K}(R_{m}) onto Soln_{K}(S_{m}) with kernel (W ∩Soln_{K}(R_{m})). We have that π is a nonzero element of Hom_{G}(Soln_{K}(R_{m}), Soln_{K}(S_{m})) and so, by Lemma 2.5, corresponds to a nonzero element \overline{R}_{m+1} of E_{D}(S_{m}, R_{m}). We can select R_{m+1} so that ord(R_{m+1}) < ord(R_{m}) and any such R_{m+1} has no solutions in common with S_{m}, (otherwise it would not induce a projection onto this solution space). Therefore we have that S_{m} does not divide R_{m+1} on the right and this gives an extension of T to a larger test set. Therefore 2. holds.

Assume that 2. holds. By convention {L} is a test set. Let T_{m} be a maximal test set (with respect to extension). By 2. we have that R_{m} has no first order right factor. Therefore 3. holds.

Assume that 3. holds. Lemma 3.13 allows us to write Soln_{K}(L) = Soln_{K}(R_{m}) ⊕ Soln_{K}(S_{m−1}) ⊕ … ⊕ Soln_{K}(S_{1}). Since R_{m} has no first order right factor, Soln_{K}(R_{m}) has no one dimensional G−submodules. Therefore any one dimensional G−submodule of Soln_{K}(L) lies in Soln_{K}(S_{m−1})⊕…⊕Soln_{K}(S_{1}). This implies that this latter space is the sum of all one dimensional G−submodules of Soln_{K}(L). Since it clearly has a complementary submodule, Lemma 2.16 implies that L is 1−reductive so 1. holds.

Algorithm 1−reductive uses Lemma 3.12 to generate a test set and decide if condition 3. of the above lemma holds. We shall state this algorithm, give three examples and then prove its correctness.

Algorithm 1-reductive

Input: A non-zero L ∈ D

Output: ‘true’ if L is 1−reductive; ‘false’ if L is not 1−reductive

Status:= true;

R := L;

While R has a first order right factor and Status= 1−reductive do h:= a solution in k of the Riccati equation associated to R; T:= e^{∫ h} ∘ R^{∗} ∘ e^{∫ −h};

If T (y) = 0 has a non-zero solution in k then g_{1}, …, g_{t} := a basis of the space of solutions in k of T (y) = 0; g := c_{1}g_{1} + … + c_{t}g_{t} for new variables c_{1}, …, c_{t}; R̃(c_{1}, …, c_{t}):= (Quotient(R^{∗}, −g^{−1}D + g^{−2}g′ − hg^{−1}))^{∗}; If there exist constants d_{1}, …, d_{t} such that

D − h does not divide R̃(d_{1}, …, d_{t}) on the right then

R := R̃(d_{1}, …, d_{t});

else Status:= false;

else Status:= false; od; return(Status); end;

In the above algorithm, the phrase Quotient(R^{∗}, −g^{−1}D +g^{−2}g′ −hg^{−1}) denotes the right quotient in the ring k(c_{1}, …, c_{t})[D] where each c′_{i} = 0. Also note that if L ∈ D where L = p(D) for some polynomial p(D) ∈ k[D], then e^{∫ h} ∘ L ∘ e^{∫ −h} = p(D − h). This implies that the operator T defined in the algorithm has coefficients in k and also gives an efficient way of calculating T. We finally note that the algorithm could be modified so that the While loop is exited when the order of R is at most 1. To see this note that if R = D − h (the case where R is not monic is similar, but notationally more complex and is left to the reader), then T := D, g := c_{1}, and R̃ := c_{1}. Therefore c_{1} can always be chosen so that D − h does not divide R̃(d_{1}, …, d_{t}) on the right and one updates R := 1. Therefore the algorithm will end with Status = true.

Example 3.15 Let k = ℂ and L = D^{2}. We begin by setting R = D^{2}. Clearly R has a right factor D, so we set h := 0 and T := R^{∗} = D^{2}. The equation T (y) = 0 has a nonzero solution y = 1 in k and this forms a basis for all solutions in k. We set g := c_{1} and R̃(c_{1}) = Quotient(D^{2}, −c_{1}^{−1}D) = c_{1}D. For all values d_{1} of c_{1} we have that D divides (R̃(d_{1}) = d_{1}D so the above equation is not 1−reductive. Note that the Galois group of L is

G = \{( \begin{matrix}1 & t \\ 0 & 1 \end{matrix} ) | t ∈ ℂ\}.

Example 3.16 Let k = ℂ(x) and again let L = D^{2}. We again have that R := D^{2} has a right factor D. Let h := 0 and T := R^{∗} = D^{2}. The equation T (y) = 0 is now satisfied by 1 and x and these two elements form a basis for the solution space of T (y) = 0 in k. Let g = c_{1}·1+c_{2}·x and let c_{1} = 0, c_{2} = 1. We then have that (Quotient(D^{2}, −\frac{1}{x}D+ \frac{1}{x}))^{∗} = xD−1 and D does not divide xD − 1 on the right. Therefore we update R := xD − 1. This has a first order factor and we set h := \frac{1}{x}. We then have T := xD + 1 and \frac{−1}{x} forms a basis for the solution space of T (y) = 0 in k. Setting g := c_{1} \frac{−1}{x} we get R̃ := c_{1}, so setting c_{1} = 1 allows us to update R := 1. Since this has no first order right factor, we exit the algorithm and conclude that the original operator is 1−reductive. As we have already noted, we could have concluded this when we reached the stage that R had order 1. Also note that the Galois group is trivial.

Example 3.17 Let k = ℂ(x). The equation L^{det(2)} = D^{6} − \frac{1}{x}D^{5} + 4x^{4}D^{2} + 20x^{3}D was constructed in Example 3.8. We shall consider the equation gotten by clearing denominators. We begin by setting R = xL^{det(2)} = xD^{6}−D^{5}+4x^{5}D^{2}+20x^{4}D = (xD^{5}−D^{4}+4x^{5}D+20x^{4})D so R clearly has a right first order factor D. We set h := 0 and T := R^{∗} = xD^{6} + 7D^{5} + 4x^{5}D^{2} +20x^{4}D. The equation T (y) = 0 has a nonzero solution y = 1 in k, and this is a basis of the space of all solutions in k. Set g := c_{1} and redefine R̃(c_{1}) := Quotient(xD^{6} + 7D^{5} + 4x^{5}D^{2} + 20x^{4}D, −c_{1}^{−1}D)^{∗} = c_{1}(−xD^{5} − 7D^{4} − 4x^{5}D − 20x^{4})^{∗} = c_{1}(xD^{5} − 2D^{4} + 4x^{5}D). For all values d_{1} of c_{1} we have that D divides R̃(d_{1}) on the right.Therefore Status changes to ‘false‘.

This furthermore, implies that L^{det(2)} is not 1−reductive. As we have noted, L^{det(2)} is an operator whose solution space is ∧^{2}V where V is the solution space of L = D^{4}−4xD−(x^{4}+2). Therefore, Corollary 2.21 implies that this latter operator is not completely reducible and, in particular, factors. One can easily show that it has no first or third order right factors (for the latter look at the adjoint), so this operator factors as the product of two second order operators.

Proof of correctness of Algorithm 1−Reductive: We shall show that the algorithm generates a maximal test set T_{m} and terminates with ‘true‘ if R_{m} has no first order right factor or ‘false‘ if R_{m} has a first order right factor. Lemma 3.14 implies that the algorithm is correct.

Initially the algorithm sets R := L. Assume, inductively, that at the beginning of the i^{th} pass through the While statement, we have generated a test set T_{i} = {(R_{1}, …, R_{i}), (S_{1}, …, S_{i−1})} with R := R_{i}. We shall show that the algorithm either extends this test set or concludes that it is maximal, in which case it halts with the correct output. Since there is an upper bound on the length of test sets, this will also show that the algorithm terminates.

If R has no first order right factor then the test set is maximal and the algorithm will terminate with Status = true, which is the correct output by Lemma 3.14.3. Assume that R has a first order right factor. The algorithm will find a h ∈ k such that S_{i} = D − h is a right factor of R. The algorithm then determines if T (y) = 0 has a nonzero solution in k. If it does, Lemma 3.12.3 implies that the algorithm finds a nonzero R_{i+1} with \overline{R}_{i+1} ∈ E_{D}(S, R) and updates the value of R := R_{i+1}. The algorithm therefore has generated a test set T_{i+1} = {(R_{1}, …, R_{i}, R_{i+1}), (S_{1}, …, S_{i−1}, S_{i})} extending T_{i} and does not change Status. If the only solution of T (y) = 0 in k is y = 0, then Lemma 3.12.3 implies that E_{D}(S_{i}, R_{i}) = (0). Therefore, R_{i} has a first order right factor but T_{i} cannot be extended. Lemma 3.14 implies that L is not 1−reductive. In this case the algorithm changes Status:= ‘false‘ and halts with the correct output.

3.3 Remarks

1. In [43], the authors show how various properties of the Galois group of a linear differential equation L(y) = 0 can be determined by determining factorization properties of auxillary operators. The above methods can be used to do this. In many instances, one does not need to apply the full irreducibility test, but in fact can just use the criterion for completely reducible operators (Corollary 2.15).

Let us consider the result mentioned in the introduction: Let k be a differential field with algebraic closed field of constants and let L ∈ D be a second order operator. The equation L(y) = 0 has non-zero liouvillian solutions over k if and only if L^{◯ s 6} is reducible in D. If one knows that L is irreducible, then the Galois group G must be a reductive group. The solution space of L^{◯ s 6} is a G−module and so will be completely reducible. Therefore, L^{◯ s 6} will be a completely reducible operator (Lemma 2.13). Furthermore, it is reducible if and only if dim_{C} E_{D}(L^{◯ s 6}) > 1. Let L_{1} be an operator (of order 49) whose solution space is G−isomorphic to Hom_{G}(Soln_{K}(L^{◯ s 6}), Soln_{K}(L^{◯ s 6})), where K is the Picard-Vessiot extension corresponding to L. We can therefore restate the above theorem as:

Theorem 3.18 Let k, L, and L_{1} be as above. The equation L(y) = 0 has non-zero liouvillian solutions over k if and only if

• The equation L(y) = 0 has a solution y ≠ 0 such that y′/y ∈ k, or

• The equation L_{1}(y) = 0 has two solutions in k linearly independent over the constants.

Proof: The operator L is reducible if and only if the equation L(y) = 0 has a solution y ≠ 0 such that y′/y ∈ k, in which case, L(y) = 0 has a liouvillian solution. If the operator L is irreducible, then the discussion preceeding this Theorem shows that the equation L(y) = 0 has non-zero liouvillian solutions over k if and only if L_{1}(y) = 0 has two solutions in k linearly independent over the constants.

Simillar results can be stated for third order operators using the results of [43]. In general, once one knows that an operator L is irreducible (or, at worst, completely reducible), any operator that one constructs from L will be completely reducible and so special methods for testing reduciblity can be used.

2. One of the goals of this paper was to develop reducibility tests that, starting with a linear differential operator, do not resort to systems and cyclic vector techniques to make a determination. To do this, we replaced the original operator L with an operator of the form L^{(b_{0},...,b_{n−1})} before constructing L^{∗}◯ s L. In reality, this construction allows one to go directly from a cyclic vector for L to a cyclic vector for the system A_{L}(Y) in section 3.1. Algorithms 1, 2 and 4 require one to construct a cyclic vector for a system. The reason for having to find a cyclic vector (or companion block diagonal form) in Algorithms 1, 2, and 4 is that we know of no direct method of finding the dimension of the space of solutions of a system Y′ = AY in k^{n}, even when k = C(x). Is there a direct method for determining the dimension of this space of solutions? Given a single linear differential equation, is there a method to find the dimension of the space of solutions in k without having to find the solutions?

References

[1] Amitsur, A. S., Differential polynomials and division algebras, Ann. of Math., 59, (1954), 245-278.

[2] Appell, P., Mémoire sur les Équations Différentielles Linéaires, Ann. Scient. Éc. Norm. Sup., Ser. 2, 10, (1881), 391-424.

[3] Barkatou, M.A., An algorithm for computing a companion diagonal form for a system of linear differential equations, AAECC, 4, (1993), 185-195.

[4] Beke, E., Die Irreducibilität der homogenen linearen Differentialgleichungen, Math. Ann., 45, (1894), 278-294.

[5] Bertrand, D., Beukers, F., Équations Différentielles Linéaires et Majorations de Multiplicités, Ann. Scient. Éc. Norm. Sup., 18, (1985), 181-192.

[6] Björk, J.-E., Rings of Differential Operators, North Holland, New York, 1979.

[7] Borel, A., Linear algebraic groups In Proc. Symp. Pure Math., 9, 3-19. Amer. Math. Soc., Providence, 1966.

[8] Bronstein, M., On solutions of linear ordinary differential equations in their coefficient field, J. Symb. Comp., 13, (1992), 413-439.

[9] Cohn, P., Free Rings and their Relations, Academic Press, London, 1985.

[10] Deligne, P., Equations Différentielles à Points Singuliers Réguliers, Lecture Notes in Mathematics, 163 Springer-Verlag, New York, 1970.

[11] Frobenius, G. Über den Begriff der Irreducibilität in der Theorie der linearen Differentialgleichungen, J. für Math., 76 236-271, 1873.

[12] Giesbrecht, M., Factoring in skew-polynomial rings, Department of Computer Science, University of Toronto, preprint, 1992.

[13] Grigoriev, D. Yu., Complexity of factoring and calculating the GCD of linear ordinary differential operators, J. Symbolic Computation (1990), 10, 7-37.

[14] Grigoriev, D. Yu., Complexity of irreducibility testing for a system of linear ordinary differential equations, Proc. Int. Symp. on Symb. Alg. Comp., ACM Press (1990) 225-230.

[15] Hilb, E., Lineare Differentialgleichungen im Komplexen Gebiet, in Encyklopedie der mathematischen Wissenschaften, IIBb, , Teubner, Leipzig, 1915.

[16] Humphreys, J., Linear Algebraic Groups, Graduate Texts in Mathematics, 21, Springer-Verlag, 1975.

[17] Hungerford, T., Algebra, Graduate Texts in Mathematics, 73, Springer-Verlag, New York, 1974.

[18] Jacobson, N., Pseudo-linear transformations, Ann. of Math., 38, (1937), 484-507.

[19] Jacobson, N., Structure of Rings, American Mathematical Society Colloquium Publications, XXXVII, Second Edition, Providence, 1964

[20] Jordan, C., Sur une application de la théorie des substitutions à l’étude des équations différentielles linéaires, Bull. Soc. Math. France II, 100, 1875.

[21] Kaplansky, I., Introduction to Differential Algebra, Paris: Hermann 1957.

[22] Landau, E., Ein Satz über die Zerlegung homogener linearer Differentialausdrücke in irreducible Factoren, J. Für Math., 24, (1902), 115-120.

[23] Lang, S., Algebra, Second Edition, Addison-Wesley, 1984.

[24] Loewy, A., Über reduzible lineare homogene Differentialgleichungen, Math. Ann., 56, (1903), 549 -584.

[25] Loewy, A., Über vollständig reduzible lineare homogene Differentialgleichungen, Math. Ann., 62, (1906), 89-117.

[26] Loewy, A., Über lineare homogene Differentialgleichungen derselben Art, Math. Ann., 70, (1911), 551-560.

[27] Loewy, A., Zur Theorie der linearen homogenen Differentialausdrücke, Math. Ann., 72, (1912), 203-210.

[28] Loewy, A., Über die Zerlegungen eines linearen homogenen Differentialausdruckes in grösste volständig reduzible Faktoren, Sitz. der Heidelberger Akad. der Wiss., 8, (1917), 1-20.

[29] Loewy, A., Über Matrizen- und Differentailkomplexe, Math Ann., 78, (1917), I: 1-51; II: 343-358; III: 359-368.

[30] Loewy, A., Begleitmatrizen und lineare homogene Differentialausdrücke, Math. Zeit., 7, (1920), 58-125.

[31] MacDonald, B., Finite Rings with Identity, Marcel Dekker, New York, 1974.

[32] Mignotte, M., Mathematics for Computer Algebra, Springer-Verlag, New York, 1992

[33] Ore,O., Formale Theorie der linearen Differentialgleichungen, J. für Math., 167, (1932), 221-234, II, ibid., 168, (1932), 233-252.

[34] Ore, O, Theory of non-commutative polynomial rings, Ann. of Math., 34, (1933), 480-508.

[35] Poole, E.G.C., Introducion to the Theory of Linear Differential Equations, Dover Publications, New York, 1960.

[36] Poincaré, H., Mémoire sur les fonctions Zétafuchsiennes, Acta Math., 5, (1884), 209-278.

[37] Ritt, J.F., Differential Algebra, Dover Publications, New York, 1966.

[38] Schlesinger, L., Handbuch für Theorie der linearen Differentialgleichungen II, Leipzig: Teubner, (1887).

[39] Schwarz, F., A factorization algorithm for linear ordinary differential equations, Proc. of the ACM-SIGSAM 1989 ISSAC, ACM Press, (1989), 17-25.

[40] Singer, M.F., Algebraic solutions of n^{th} order linear differential equations, Proceedings of the 1979 Queens Conference on Number Theory, Queens Papers in Pure and Applied Mathematics 54, (1980).

[41] Singer, M.F., Liouvillian solutions of linear differential equations with liouvillian coefficients, J. Symb. Comp., 11, (1991), 251-273.

[42] Singer, M.F., Moduli of linear differential equations on the Riemann Sphere with fixed Galois groups, Pacific Journal of Math., 160, No. 2, (1993), 343-395.

[43] Singer, M.F., Ulmer, F., Galois groups of second and third order linear differential equations, J. Symb. Comp., 16, July 1993, 9 - 36.

[44] van der Waerden, B.L., Modern Algebra, Vol. I, Second Edition, Frederick Ungar, New York, 1953.