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

Liouvillian Solutions of Linear Differential Equations of Order Three and Higher

MARK VAN HOEIJ^{†}, JEAN-FRANÇOIS RAGOT^{‡}, FELIX ULMER^{⋆}, AND JACQUES-ARTHUR WEIL^{‡}

† Florida State University, U.S.A, hoeij@math.fsu.edu ‡ Université de Limoges, France, ragot@unilim.fr, weil@unilim.fr ⋆ Université de Rennes I, France, ulmer@univ-rennes1.fr

(Received July 98)

Singer and Ulmer (1997) gave an algorithm to compute Liouvillian (“closed-form”) solutions of homogeneous linear differential equations. However, there were several efficiency problems that made computations often not practical. In this paper we address these problems. We extend the algorithm in van Hoeij and Weil (1997) to compute semi-invariants and a theorem in Singer and Ulmer (1997) in such a way that, by computing one semi-invariant that factors into linear forms, one gets all coefficients of the minimal polynomial of an algebraic solution of the Riccati equation, instead of only one coefficient. These coefficients come “for free” as a byproduct of our algorithm for computing semi-invariants. We specifically detail the algorithm in the cases of equations of order 3 (order 2 equations are handled by the algorithm of Kovacic (1986), see also Ulmer and Weil (1996) or Fakler (1997)).

In the appendix, we present several methods to decide when a multivariate polynomial depending on parameters can admit linear factors, which is a necessary ingredient in the algorithm.

1. Introduction

In this paper k will denote a differential field whose field of constants C is algebraically closed of characteristic 0. For the computations, however (Section 2.2), we will consider more concretely the field C(x) with the usual derivation d/dx. We denote by L = ∂^{n} + a_{n−1}∂^{n−1} + ⋯ + a_{0}∂^{0} (a_{i} ∈ k, L ∈ k[∂]) a differential operator and by L(y) = y^{(n)} + a_{n−1}y^{(n−1)} + ⋯ + a_{0}y = 0 the corresponding linear homogeneous differential equation. We now briefly recall the basic definitions from differential Galois theory that are needed later on (see Magid, 1994, Singer, 1997, or van der Put, 1998, for details and references). A Picard-Vessiot extension (PVE) K of k for L is a differential field extension K = k < y_{1}, …, y_{n} >, where {y_{1}, …, y_{n}} a fundamental set of solutions, with no new constants in K. It is the equivalent of a splitting field for L(y) = 0. Under our assumptions a PVE exists and is unique up to differential automorphisms. We denote by V (L) the solution space V (L) = {y ∈ K|L(y) = 0} of an operator L. The dimension of V (L) equals the order of L. The differential Galois group G of L is the group of differential automorphisms of K/k. It acts faithfully on the vector space V (L), and so G can be viewed as a subgroup of GL(V (L)); more precisely, it is a linear algebraic group over C. There is a Galois correspondence between algebraic subgroups of G and differential subfields of the PVE of L(y) = 0. The fixed field of G under this correspondence is k. A solution of L(y) = 0 in k is called a rational solution, a solution in an algebraic extension of k is called an algebraic solution, a solution whose logarithmic derivative is in k is called an exponential solution and a solution belonging to a differential field obtained by successive adjunctions of integrals, exponentials of integrals and algebraic extensions is called a Liouvillian solution. If L has a Liouvillian solution then L also has a Liouvillian solution of the form y = exp(∫ r) where r ∈ \overline{k} is algebraic over k (see Singer, 1981 & 1997).

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

Definition 1.1. An element r of the PVE is called a Riccati solution for L if r is the logarithmic derivative r = y′/y of some non-zero solution y of L. If r is an algebraic Riccati solution (a Riccati solution in \overline{k}) then the minimum polynomial of r over k is called a Riccati polynomial of L.

Definition 1.2. An element I ∈ Sym^{m}(V (L)) is called a semi-invariant of the differential Galois group G of L of degree m if there is a character χ : G ↦ C of degree 1 such that for all g ∈ G the action of g on I is g(I) = χ(g)I. If χ is the trivial character, i.e. ∀g ∈ G, g(I) = I, then I is called an invariant.

We call a polynomial or semi-invariant completely factorable if it is a product of linear factors. It is known (see section 2 in Singer and Ulmer, 1997) that an algebraic Riccati solution r of degree m over k corresponds to a completely factorable semi-invariant I of degree m of the differential Galois group G. In Singer and Ulmer (1997), the Riccati polynomial of r is computed as follows:

1 Compute the spaces of all semi-invariants up to a certain degree. This degree can be bounded

in terms of the order of the operator using group theory. 2 In each such space, find a completely factorable semi-invariant I ∈ Sym^{m}(V (L)) where m is the

degree. If such a semi-invariant is found, then L(y) = 0 has an algebraic Riccati solution and the first coefficient of the associated Riccati polynomial is given by the logarithmic derivative of the value of I. The value of I is the image of I in K.

3 In Singer and Ulmer (1997), the factorization of I into linear forms is used to compute the remaining coefficients. This involves computing with splitting fields and so this step could be costly.

The main objective in this paper is to give an efficient method to compute (if it exists) a Riccati polynomial. The goal is a method that is efficient enough to handle operators of order 3 on a computer, or sometimes even higher order if the Riccati polynomial is not too big. First we extend the algorithm in van Hoeij and Weil (1997) for computing invariants to the case of semi-invariants. If a completely factorable semi-invariant is known and given in a certain form, then theorem 2.1 immediately gives us all coefficients of the Riccati polynomial. This central result avoids the third step above and makes the computation much more feasible in practice. In the appendix we discuss methods for finding the linear combinations of the basis corresponding to a completely factorable semi-invariant I (second step). If the dimension of the vector space of semi-invariants for a character is high then it is a very costly step. This can be resolved by looking at semi-invariants (not always of minimal degree) that are guaranteed to be completely factorable. This is particularly interesting because the second step above, i.e. selecting a completely factorable semi-invariant which can be a very costly step, is then no longer needed. The result is a Kovacic-like algorithm for order(L) = 3, given in section 4.

Acknowledgments: We thank Anne Bellido, Marius van der Put and Michael F. Singer for fruitful conversations during the preparation of this paper. J.A. Weil specially thanks Marius van der Put and the NWO aida project for their material and intellectual support. This research was partially supported by the European Cathode II working group and, for the third author, also by the Calife project (INTAS-RBFR 95-0412). Most computations were realized thanks to the French CNRS-UMS Medicis.

2. Semi-invariants of differential Galois groups

2.1. The formalism

The basis of our approach is the following useful formalism:

Proposition 2.1. (van Hoeij and Weil, 1997, Proposition 2.5) Let K be the Picard-Vessiot extension and G the differential Galois group of L. Define the C-algebra homomorphism

ϕ : Sym(V (L)) → K[X_{1}, …, X_{n}]

by (it suffices to define ϕ for homogeneous elements \overline{y} of degree 1)

ϕ(\overline{y}) = ∑_{i=1}^{n} X_{i}y^{(i−1)} for y ∈ V (L).

Here \overline{y} is the element of Sym^{1}(V (L)) ⊂ Sym(V (L)) that corresponds to the solution y ∈ V (L) ⊂ K of L. Then ϕ is an embedding (as C-algebra and as G- module) of Sym(V (L)) in K[X_{1}, …, X_{n}], where the action of G on X_{1}, …, X_{n} is trivial.

If I ∈ Sym(V (L)), then we say that ϕ(I) is the canonical image of I in K[X_{1}, …, X_{n}]. Often the two vector spaces V (L), which is a subset of K, and Sym^{1}(V (L)), which is a subset of Sym(V (L)), are identified. In this paper we can not directly do so because multiplication in K is not the same as multiplication in Sym(V (L)). The following extension of Theorem 3 of Singer and Ulmer (1997) illustrates the usefulness of the above formalism and is central to our approach.

Theorem 2.1. Let L(y) = 0 be a homogeneous linear differential equation over k. Let K be a Picard-Vessiot extension of k for L and G be its differential Galois group. Assume that G has a semi-invariant I ∈ Sym^{m} (V (L)) that is a product of linear factors and assume that the degree m of I is minimal with this property. Let P (X_{1}, …, X_{n}) = ϕ(I) ∈ K[X_{1}, …, X_{n}] be its canonical image. Let a be the coefficient of X_{1}^{m} in P. Then:

1 a ≠ 0

2 Let Q := \frac{1}{a}P (X, −1, 0, …, 0). Then Q ∈ k[X] and Q is a Riccati polynomial.

Proof. The semi-invariant I is completely factorable, so I = ∏_{i=1}^{m} \overline{y}_{i} where \overline{y}_{i} ∈ Sym^{1}(V (L)) ⊂ Sym(V (L)) and y_{i} ∈ V (L) are the corresponding solutions of L(y) = 0. Thus, as P = ϕ(I), we have

P = ∏_{i=1}^{m}(y_{i}X_{1} + y′_{i}X_{2} + ⋯ + y_{i}^{(n−1)}X_{n})

If g ∈ G then g(y_{i}) ∈ Cy_{j} for some j because of the uniqueness of factorization in Sym(V (L)) (which is isomorphic to a polynomial ring in n variables over C). Hence G permutes the set \{\frac{y′_{1}}{y_{1}} , …, \frac{y′_{m}}{y_{m}} \}. The action of G on this set is transitive because m is minimal. Note that a = ∏ y_{i} ≠ 0 because P ≠ 0.

Q = ∏_{i=1}^{m} \frac{1}{y_{i}} (y_{i} · X + y′_{i} · (−1) + y′′_{i} · 0 + ⋯ + y_{i}^{(n−1)} · 0) = ∏_{i=1}^{m}(X − \frac{y′_{i}}{y_{i}}).

Since G permutes the \frac{y′_{i}}{y_{i}} it follows that Q is invariant under G and hence by the Galois correspondence

Q ∈ k[X]. Q is irreducible because the action of G on the \frac{y′_{i}}{y_{i}} is transitive. The Riccati solutions \frac{y′_{i}}{y_{i}} are the roots of Q and hence they are algebraic functions with minimum polynomial Q. □

Remark: with notations as above, if m is not minimal, then it is easily seen that the polynomial Q is either irreducible or a product of Riccati polynomials. Conversely, theorem 3 of Singer and Ulmer (1997) (combined with our theorem) shows immediately that any Riccati polynomial is obtained that way. This is used implicitly in section 4.

The algorithm presented in van Hoeij and Weil (1997) computes the invariants I of G by computing their images ϕ(I). The reason for using ϕ in van Hoeij and Weil (1997) was to be able to compute invariants without having to compute symmetric powers Sym^{m}(L) ∈ k[∂]. In the following, this same approach is extended to the computation of semi-invariants. The above then shows that this approach does not only produce the semi-invariant whose logarithmic derivative is the first coefficient of the Riccati polynomial, but in fact gives all the coefficients. This makes this algorithm for computing (semi)-invariants very suitable for finding Liouvillian solutions. We now proceed with the computation of semi-invariants via the above formalism. The next subsection is rather technical and will be easier if the reader knows about the paper of van Hoeij and Weil (1997) and about Beke’s method for computing exponential solutions of operators (see van Hoeij, 1997, Singer, 1997, or Pflügel, 1998 for details and additional references).

2.2. Computation of semi-invariants

Lemma 2.1. The image of a semi-invariant under the embedding ϕ is an element of a · k[X_{1}, …, X_{n}] where a = exp(∫ y) for some y ∈ k.

Proof. Let I be a semi-invariant of degree m, and P = ϕ(I). Because ϕ is a G-homomorphism, g(P) = χ(g) · P for some character χ. Let a ∈ K be one of the non-zero coefficients of P ∈ K[X_{1}, …, X_{n}]. Now g(\frac{1}{a}P) = g(\frac{1}{a})χ(g)P = (a g(\frac{1}{a}) χ(g)) \frac{1}{a}P. The action of G on the X_{i} is trivial, so that the coefficients of g(\frac{1}{a}P) are just the image of the corresponding coefficients under g. One of the coefficients of \frac{1}{a}P equals 1 and since g(1) = 1 the corresponding coefficient of g(\frac{1}{a}P) must also be 1. Hence ∀g ∈ G, ag(\frac{1}{a})χ(g) = 1 and so \frac{1}{a}P is invariant under G. By the Galois correspondence

\frac{1}{a}P ∈ k[X_{1}, …, X_{n}].

Furthermore ∀g ∈ G, g(a) = χ(g) · a showing that a′/a is left invariant by G and thus y = a′/a ∈ k.

□

Remark: Using the embedding ϕ, we will often identify semi-invariants with elements of K[X_{1}, …, X_{n}]. ⋄

Definition 2.1. For t ∈ k, we note S_{t}^{∗} the k-automorphism of k[∂] defined by S_{t}^{∗}(∂) = ∂ + t.

Definition 2.2. The equivalence relation ∼ on k is defined as follows: t_{1} ∼ t_{2} when there exists y ∈ k for which t_{1} − t_{2} = y′/y.

Let V (L) ⊂ K, a ∈ K and assume t = a′/a ∈ k. Then multiplication by a is a C-linear map

μ_{a} : V (L) → V (S_{−t}^{∗}(L)).

The map μ_{a} induces a 1-1 linear map

μ_{a} : Sym^{m}(V (L)) → Sym^{m}(V (S_{−t}^{∗}(L))).

Let S ∈ Sym^{m}(V (L)), g ∈ G. Then g(μ_{a}(S)) = μ_{a}(g(S)) · g(a^{m})/a^{m} so if S is a semi-invariant then μ_{a}(S) is an invariant if and only if g(S) = S · a^{m}/g(a^{m}) for all g ∈ G. If S is a semi-invariant then ϕ(S) is of the form ϕ(S) = b · I for some I ∈ k[X_{1}, …, X_{n}], b ∈ K with t_{1} = b′/b ∈ k. Then g(S) = S · g(b)/b, so μ_{a}(S) is an invariant if and only if g(b)/b = a^{m}/g(a^{m}) for all g ∈ G. This holds if and only if b · a^{m} ∈ k, if and only if −tm ∼ t_{1}. Let L be a differential operator and K the Picard-Vessiot extension. Let S ∈ ϕ(Sym^{m}(V (L))) ⊂ K[X_{1}, …, X_{n}] be a semi-invariant of degree m. So S = b · I ∈ K[X_{1}, …, X_{n}] for some b ∈ K, I ∈ k[X_{1}, …, X_{n}]. Let t_{1} = b′/b ∈ k. The map μ_{a} induces a map on ϕ(Sym^{m}(V (L))) that we will denote by ϕ_{a}. Then ϕ_{exp(∫ −t/m)}(S) is an invariant of S_{t/m}^{∗}(L) if and only if t ∼ t_{1}.

In order to compute all semi-invariants of degree m, we will construct from L a finite set B, such that whenever L has a semi-invariant in b · k[X_{1}, …, X_{n}] then (b′/b mod ∼) ∈ B. Then for each t_{1} ∈ B we take a t ∈ k with t ∼ t_{1} and determine the invariants of S_{t/m}^{∗}(L). If I ∈ k[X_{1}, …, X_{n}] is an invariant of S_{t/m}^{∗}(L), then the corresponding semi-invariant of L is S = ϕ_{exp(∫ t/m)}(I). The remaining problem is to determine the set B, which will be done using the generalized exponents, in a way similar to the computation of the bounds in van Hoeij and Weil (1997). This leads to the algorithm below.

In the rest of this section, we assume that k = C(x). Algorithm Semi-invariants. Input: a differential operator L ∈ C(x)[∂] of order n, and an integer m. Output: all semi-invariants of degree m. Step 1. Compute a finite set B ⊂ C(x)/ ∼ such that for all semi-invariants aI of L, a ∈ K, I ∈ C(x)[X_{1}, …, X_{n}] the equivalence class of \frac{a′}{a} is an element of B. Step 2. For each element of B take a representant t ∈ C(x) and compute the invariants of S_{t/m}^{∗}(L). These correspond to semi- invariants of L.

Note that this algorithm resembles Beke’s algorithm for computing exponential solutions exp(∫ t) with t ∈ C(x). We give the same sketch of this algorithm as in section 4 in van Hoeij (1997): Step 1. Compute a finite set B ⊂ C(x)/ ∼ such that for all exponential solutions a one has (\frac{a′}{a} mod ∼) ∈ B. Step 2. For each element of B take a representant t ∈ C(x) and compute the rational solutions of S_{t}^{∗}(L). Return the corresponding exponential solutions of L.

Computation of set B in step 1 of algorithm semi-invariants: In van Hoeij and Weil (1997) and van Hoeij (1997) a generalization of the classical notion of exponents has been defined. A generalized exponent is an element of C[x^{−1/r}] for some integer r (called the ramification index). In the regular singular case the generalized exponents are the exponents and the ramification index is 1 in this case. For t ∈ C(x) and p ∈ IP^{1}(C) denote EP_{p}(∂ − t) ∈ C[x^{−1}]/ZZ as the generalized exponent e ∈ C[x^{−1}] at the point p of ∂ − t modulo the integers. EP_{p}(∂ − t) is the exponential part of ∂ − t at p. Now t modulo ∼ is determined by the EP_{p}(∂ − t) for all p (van Hoeij, 1997). Let e ∈ C[x^{−1}] be the generalized exponent of ∂ − t at the point p. Then e/m is the generalized exponent of ∂ − t/m at p. The generalized exponents of S_{t/m}^{∗}(L) at p equal −e/m plus the generalized exponents of L at p. So the generalized exponents of the monomials in lemma 28 in section 4.1 in van Hoeij and Weil (1997) for S_{t/m}^{∗}(L) are −e plus the generalized exponents of the monomials for L. According to this lemma, at least one of those generalized exponents should be in \frac{1}{r}ZZ (where r is the ramification index at p) if S_{t/m}^{∗}(L) has an invariant. This leaves only finitely many possibilities for e modulo ZZ and hence for EP_{p}(∂ − t) = e + ZZ ∈ C[x^{−1}]/ZZ. At regular points, there is only one possibility for e + ZZ, namely e + ZZ = ZZ, because r = 1 and the generalized exponents are integers at regular points. At a singular point p, we can compute all generalized exponents of L, and all generalized exponents of the monomials in the lemma (these are sums of m generalized exponents of L) and so we can compute a finite set of possible values of EP_{p}(∂ − t). If p_{1}, …, p_{l} are the singularities, and we find N_{i} possible EP_{p_{i}}(∂ − t) then we have N = N_{1} · N_{2} ⋯ N_{l} possible combinations, so we find at most† N possible values of t modulo ∼. These t modulo ∼ are the elements of the set B in the algorithm.

A comment on step 2: We need to compute invariants of a number of operators (one for each element of B). It can be faster first to apply the heuristic algorithm in van Hoeij and Weil (1997), and to apply the complete algorithm invariants in van Hoeij and Weil (1997) only for the cases when the heuristic does not prove that no invariants exist.

Another efficiency improvement can be obtained as follows: For computing the invariants of S_{t/m}^{∗}(L) we need the generalized exponents of S_{t/m}^{∗}(L) at all singularities. However, these can be easily com-

† not every combination of exponential parts corresponds to a t, only those combinations that satisfy a generalized Fuchs’ relation (lemma 9.2 in van Hoeij, 1997)

puted from t and the generalized exponents of L. Furthermore we compute with formal solutions of S_{t/m}^{∗}(L) at one singularity, but these can be computed from the formal solutions of L. This way we only need to compute generalized exponents and formal solutions of L, not of each S_{t/m}^{∗}(L) for every t ∈ B.

Our algorithm for computing semi-invariants has the same drawback as Beke’s algorithm for computing exponential solutions: If the singularities or the generalized exponents involve algebraic extensions over the coefficients field then the algorithm may need to compute in exponentially large algebraic extensions. For m = 1 it is in fact the same algorithm. If the set B is very large then the computation can also be long. However, in many examples the generalized exponents are rational numbers, and the number of singularities is small (typically 3) so that B will not be big. In such examples computing semi-invariants will not be so hard.

Sometimes, e.g. step [2.1] in section 4.1, we need to compute only those semi-invariants whose n-th power is rational (with n ∈ IN given). The computation is then shorter: in step 2 of algorithm semiinvariants, we need only to consider those t ∈ B for which nt ∼ 0 (i.e. the generalized exponents of ∂ − t are in \frac{1}{n}ZZ). This will be used in section 4. Invariants are rational solutions of a system of differential equations, the symmetric power system Y′ = S^{m}(A)Y in section 2.1.2 of van Hoeij and Weil (1997). Semi-invariants are exponential solutions of this system. So invariants and semi-invariants can be obtained by applying the algorithms in Barkatou (1998) and Pflügel (1997) on the symmetric power system. However, this can be a costly computation because the dimension of the S^{m}(A) can be very high, and because the algorithms in Barkatou (1998) and Pflügel (1997) are general, so they do not benefit from the special structure of the symmetric power system.

2.3. A fourth-order example with group FP28

The following operator (constructed with the methods of van der Put and Ulmer, 1998) has a Galois group which is a central extension of S_{5} (FP28 in the notation of Hessinger, 1998).

L = ∂^{4} + 4\frac{(2x−1)∂^{3}}{x(x−1)} + \frac{(2295x^{2}−2032x+105)∂^{2}}{160x^{2}(x−1)^{2}} + \frac{(1500x^{2}−287x+105)∂}{320(x−1)^{2}x^{3}}
+\frac{7(148000x+9375x^{4}−10088x^{3}−67250x^{2}−73125)}{2560000x^{4}(x−1)^{4}}.

Its exponents at the singularities 0, 1, and ∞ are

E_{0} = \{−\frac{7}{8}, \frac{1}{8}, \frac{9}{8}, \frac{13}{8}\}, E_{1} = \{\frac{1}{10}, \frac{3}{10}, \frac{7}{10}, \frac{9}{10}\}, and E_{∞} = \{\frac{1}{8}, \frac{3}{8}, \frac{5}{8}, \frac{7}{8}\}.

The group FP28 has semi-invariants of degree 5, including a completely factorable semi-invariant. Following our method, we do the following to compute all semi-invariants of degree 5. Let E_{p} + E_{p} + E_{p} + E_{p} + E_{p} be the set of all sums of 5 exponents at x = p. Let F_{p} be this set modulo \frac{1}{r_{p}} ZZ where r_{p} is the ramification index. All ramification indices r_{p} are 1 in this example, so F_{p} is just E_{p} + ⋯ + E_{p} modulo the integers (i.e. we take the fractional parts of the elements of E_{p} + ⋯ + E_{p}). Then one finds F_{0} = {1/8, 5/8}, F_{1} = {1/10, 3/10, 1/2, 9/10, 7/10} and F_{∞} = {1/8, 3/8, 7/8, 5/8}. We need to try S_{t/5}^{∗}(L) for all t = c_{0}/x + c_{1}/(x − 1) for which

1 0 ≤ c_{i} < 1 for i ∈ {0, 1}.

2 (c_{p} + \frac{1}{r_{p}} ZZ) ⋂ F_{p} is non-empty for p ∈ \{0, 1, ∞\}, where c_{∞} = −c_{0} − c_{1}.

In general the c_{i} are taken in C[x^{−1/r_{p}}] modulo \frac{1}{r_{p}} ZZ, but since all generalized exponents are rational numbers we can take c_{i} to be non-negative rational numbers smaller than 1. The above conditions leave only very few (namely 2) cases for t, so computing all semi-invariants of L of degree 5 does not take much computer time here. Let L̃ = S_{t/5}^{∗}(L) where t = 5/(8x) + 1/(2(x − 1)). With the algorithm from van Hoeij and Weil (1997), we compute the 2-dimensional space of invariants of degree 5 of L̃, and determine an invariant that factors into linear factors using the appendix. We then apply theorem 2.1 and obtain the following Riccati polynomial:

P =  X^{5}(122683392 x^{3} + 246481521 x^{2} + 184373150 x − 557519375)
+X^{4}(245366784 x^{3} + 739444563 x^{2} + 737492600 x − 2787596875)/x
+X^{3}(966131712 x^{4} + 3750651762 x^{3} + 2746408210 x^{2}
−33407163250 x + 27875968750)/(5 (x − 1) x^{2})
+X^{2}(1878589440 x^{5} + 10760213334 x^{4} + 11619977980 x^{3}
−183778983600 x^{2} + 297197002500 x − 139379843750)/(25 (x − 1)^{2} x^{3})
+X(1808142336 x^{6} + 15408360513 x^{5} + 43238642915 x^{4}
−522670373950 x^{3} + 1182921498750 x^{2} − 1068395471875 x +
348449609375)/(125 (x − 1)^{3} x^{4})
+X^{0}(3451908096 x^{7} + 41967774147 x^{6} + 302211588068 x^{5}
−3042266659625 x^{4} + 8490891950000 x^{3} − 11023761109375 x^{2}
+6968992187500 x − 1742248046875)/(3125 (x − 1)^{4} x^{5})

Let r ∈ \overline{C(x)} be a root of P. Then exp(∫ r dx) is a Liouvillian solution (in fact: algebraic solution, but we have not computed its minimum polynomial) of L̃. To obtain a solution of L we have to multiply by exp(∫ t/5 dx), so we find the following Liouvillian solution of L

exp(∫ (r + \frac{t}{5}) dx) = x^{1/8}(x − 1)^{1/10} · exp(∫ r dx) ∈ V (L).

We could also compute a semi-invariant of L from the invariant of L̃, and apply theorem 2.1 on that. The Riccati polynomial obtained that way has r + \frac{t}{5} as solution, so it can be also be obtained from P by a substitution. In most examples we prefer to compute a Riccati polynomial through invariants, not semi-invariants, because invariants are easier to compute. However, FP28 has a 5-dimensional space of invariants of degree 8, and no invariants of lower degree. So computing a completely factorable invariant will be very difficult because it has to be selected from a high dimensional space. So for FP28 it is easier to use semi-invariants.

2.4. Constructors of semi-invariants

In this part, we list some results from Weil (1995b) that will be used in section 4. Let X denote the transposed vector (X_{1}, …, X_{n})^{t}. Let D be the derivation on K[X_{1}, …, X_{n}] defined by D(X) = −A^{t}X and D is the usual derivation on K. Then, ϕ(Sym(V (L))) = {P ∈ K[X_{1}, …, X_{n}] : D(P) = 0} (Weil, 1995a)†. Let S be a semi-invariant of degree m, and P = ϕ(S) be its canonical image in K[X_{1}, …, X_{n}]. In this setting, it is shown in Weil (1995b, proposition 50, section 6, page 57) that the Hessian of P (with respect to X_{1}, …, X_{n}) is again, up to multiples, the canonical image of a semi-invariant (same results hold for the bordered Hessian and the Jacobian). Thus, once a semi-invariant is known, we can apply directly Hessians and related constructors on its canonical image (see Weil, 1995b, section 6.3 page 65 for a fairly detailed example). In view of theorem 2.1, this will allow (in section 4) to construct Riccati polynomials of high degrees directly from invariants of small degree.

† In fact, this derivation turns K[X_{1}, …, X_{n}] into a differential module isomorphic to Sym (D/DL).

3. Computing Liouvillian solutions of equations of order n

Lemma 3.1. If L is reducible and L has a Liouvillian solution then L has an irreducible right-hand factor R ∈ C(x)[∂] that has a Liouvillian solution.

Proof. The Liouvillian solutions of L form a subspace of V (L) that is invariant under the differential Galois group. Hence there exists a right-hand factor R′ having this subspace as solution space. Now take for R any irreducible right-hand factor of R′. □

From the fact that an operator M that has a Liouvillian solution must have a solution of the form exp(∫ r) for some algebraic function r ∈ \overline{C(x)}, i.e. M has a right-hand factor of order 1 in \overline{C(x)}[∂], it follows by induction that if all solutions are Liouvillian then M is completely factorable in \overline{C(x)}[∂] (i.e. M is a product of operators of order 1). Conversely, if M is completely factorable then all solutions are Liouvillian. Hence the operator R′ in the lemma is the highest order right-hand factor of L that is completely factorable in \overline{C(x)}[∂].

1 Reducible case. If L is reducible and has a Liouvillian solution then according to the lemma there exists an irreducible right-hand factor that has a Liouvillian solution. Though there may be infinitely many different right-hand factors, there are only finitely many types (Tsarev, 1996, Singer, 1995) of irreducible right-hand factors. For each type we need to compute one righthand factor and compute the Liouvillian solutions of that factor. This way we find a Liouvillian solution of L, if such solution exists.

2 Irreducible case. In Singer and Ulmer (1993b) and references therein, the authors give an upper bound for the lowest degree of (if it exists) a Riccati polynomial of L. So, by checking a finite number of degrees, one can decide if a Riccati polynomial exists. For each possible degree m, compute the semi- invariants of degree m and check (see appendix A) if there is a completely factorable semi-invariant. If so, return the corresponding Riccati polynomial.

In the algorithms the irreducible case is usually split into the imprimitive and the primitive case (containing only a finite list of possible groups); this is explained in Singer and Ulmer (1993b). Several ideas from section 4 below can be re-used when handling equations of higher order (e.g. the fact that knowing in advance which groups to check for allows us to check only a small number of degrees for the semi-invariants). The important classification work of Hessinger (1998) should pave the way to a better algorithm for computing Liouvillian solutions of equations of order 4.

4. Computing Liouvillian solutions of equations of order 3

The general algorithm can be improved in several ways. First of all, the computation of semi-invariants can often be avoided. For example in the case that L is irreducible of order 2, we know from Ulmer and Weil (1996) that it is sufficient to compute only invariants, which are easier to compute than semi-invariants. The factorization of a semi-invariant (cf. appendix A) becomes a problematic step if the number of parameters is not small. For second order equations this problem does not occur because any invariant will factor into linear forms. For third order equations we will use section 2.4 to find invariants that are guaranteed to factor, so that appendix A can be avoided in most cases. Furthermore we can reduce the size and number of different degrees m that need to be checked by studying the possible Galois groups. In this section, we develop along these guidelines a Kovacic-like algorithm for computing Liouvillian solutions of linear differential equations of order 3. For the possible Galois groups, we follow the notations from Singer and Ulmer (1993a, 1993b).

4.1. The algorithm

Let L = ∂^{3} + a_{2}∂^{2} + a_{1}∂ + a_{0} where the a_{i} ∈ C(x). If there exists an f ∈ k such that f′/f = a_{2}, then G ⊂ SL_{3}; if not, then we can first apply S_{−a_{2}/3}^{∗} to L so that the coefficient a_{2} will vanish. Hence, we may assume in all that follows that the Galois group is unimodular, i.e. G ⊂ SL_{3}. Remark: in the algorithm below, the sentences “there are s invariants of degree m” should be understood as “the vector space of all invariants of degree m has dimension s”.

1 Reducible case.

[1.1] If L can be written as L_{1} · (∂ − r) for some r ∈ C(x) then let a = exp(∫ r) and compute a basis y_{1}, y_{2} of solutions of L_{1}. Return a, a ∫ (y_{1}/a) , a ∫ (y_{2}/a).

[1.2] If L allows only a factorization L = L_{1}L_{2}, where L_{2} has order 2. Then apply the Kovacic algorithm on L_{2}. If a basis of Liouvillian solutions is found, then (assume that L is monic) L can be factored as (∂ − r)(∂ − a)(∂ − b) for some algebraic functions a and b and rational function r. Let z_{1} = exp(∫ (a−b) dx) and z_{2} = ∫ exp(∫ (r −a) dx) dx. Then y_{1} = exp(∫ b dx), y_{2} = y_{1} ∫ z_{1} dx and y_{3} = y_{1} ∫ z_{1}z_{2} dx is a basis of Liouvillian solutions of L.

2 Test if the group is imprimitive by doing one of the following steps, 2.1 or 2.2:

[2.1] Compute all semi-invariants of degree 3 whose square is invariant (see the remark at the end of section 2.2). Decide if one of these semi-invariants has a linear factor (use Appendix A if there is a semi-invariant linearly depending on parameters†). If this is the case then the group is imprimitive; return the Riccati polynomial Q using theorem 2.1. Otherwise the group is not imprimitive; proceed with step 3.

[2.2] Compute invariants of degree 6 and decide which of those is a square (see Appendix A4). The corresponding square roots are all semi-invariants of degree three whose square is invariant. Now proceed as in [2.1].

3 Compute the invariants of degree 2. If there is one (there can not be more) then compute the

invariants of degree 6 and one of the following two cases applies; otherwise proceed with step 4.

[3.1] Either there is ONE invariant of degree 6; then G ≃ P SL_{2}^{SL_{3}} and there is no Liouvillian solution.

[3.2] Or there are TWO invariants of degree 6; then G ≃ A_{5}^{SL_{3}}. Return either the unique Riccati polynomial of degree 6 (the corresponding completely factorable invariant must be found in a space of dimension 2) or the unique Riccati polynomial of degree 15 obtained from section 4.3.2.

4 Compute invariants of degree 4. If there is one (there can not be more), then G ≃ G_{168}^{SL_{3}}. Return

the Riccati polynomial of degree 21 obtained in section 4.3.3 5 Compute invariants of degree 6:

[5.1] If there are NO such invariants then one of the following 2 cases applies; otherwise proceed with step 5.2.

[5.1.1] If there is one invariant of degree 9 (there can not be more), then G ≃ H_{216}^{SL_{3}}. Return the corresponding Riccati polynomial of degree 9.

[5.1.2] Else, the group is SL_{3} and there are no Liouvillian solutions.

[5.2] If there is ONE invariant of degree 6, then one of the following 4 cases applies; if there are more invariants of degree 6 then proceed with step 5.3.

[5.2.1] If the invariant is a cube (Appendix A4), then G ≃ P SL_{2}^{SL_{3}} × C_{3} and there are no Liouvillian solutions.

[5.2.2] If there is one invariant of degree 9 (there can not be more), then G ≃ H_{72}^{SL_{3}}. Return the corresponding Riccati polynomial of degree 9.

[5.2.3] If there is an invariant‡ of degree 12 which is the cube of a semi-invariant S (Appendix

† i.e. a vector space of semi-invariants corresponding to the same character. ‡ Alternatively, at this step, one could directly search for a (unique) semi-invariant of degree 4 whose cube is rational.

Or, to avoid factorisation, one could compute the dimension of the space of invariants of degree 18 (dimension 2 for G_{168}^{SL_{3}} × C_{3} and dimension 3 for A_{6}^{SL_{3}}).

A4), then G ≃ G_{168}^{SL_{3}} × C_{3}. Return the Riccati polynomial of degree 21 corresponding to the unique invariant of degree 21 obtained in section 4.3.5

[5.2.4] Else G ≃ A_{6}^{SL_{3}}. Return the Riccati polynomial of degree 45 corresponding to the unique invariant of degree 45 obtained in section 4.3.6

[5.3] If there are TWO invariants of degree 6, then one of the following 2 cases applies:

[5.3.1] If there is one invariant of degree 9 (there can not be more), then G ≃ F_{36}^{SL_{3}}; Return the corresponding Riccati polynomial of degree 9.

[5.3.2] Else, G ≃ A_{5}^{SL_{3}} × C_{3}. Return either the unique Riccati polynomial of degree 6 (the corresponding completely factorable invariant must be found in a space of dimension 2) or the Riccati polynomial of degree 15 obtained in section 4.3.8.

4.2. Practical remarks on the algorithm

We note that, in practice, some cases from the algorithm can be quickly excluded by the necessary conditions from Singer and Ulmer (1995) and/or the heuristic from section 4.1 in van Hoeij and Weil (1997). For example, if the equation is not Fuchsian, then there are Liouvillian solutions if and only if step 1 or step 2 succeeds.

One consequence of the above algorithm is that we can decide whether an irreducible third order equation has Liouvillian solutions by using only invariants of degrees 2, 4, 6, and 9.

Another remark concerns the rationality problem: The algorithm we use for computing invariants, unlike for semi- invariants, does not introduce algebraic extensions in its output ϕ(I). The only case of an irreducible operator L of order 3 where we compute a Riccati polynomial that may require an extension of the constant field is the imprimitive case (there may be an extension of degree at most 4, see Hendriks and van der Put, 1994, Ulmer, 1994), because this is the only case where semi-invariants and appendix A need to be used.

Choosing step [2.2] instead of [2.1] to handle the imprimitive case has several extra advantages. For example, in step 3 and 5, we need not recompute the invariants of degree 6 (note, however, that one can not safely perform step 3 before step 2). Also, if the dimension of the space of invariants of degree 6 is bigger than 2, then we know automatically that the group is imprimitive (this follows from the properties of the primitive subgroups of SL_{3}(C)). Furthermore we do not need to compute semi-invariants this way.

4.3. Correctness of the algorithm

The fact that the successions of tests proposed in the algorithms yield the correct groups follow from the decomposition of the symmetrisations of the characters (Singer and Ulmer, 1993a) for all primitive subgroups of SL_{3}. To prove that the corresponding degrees of algebraic Riccati solutions are correct, we proceed by inspection of all imprimitive and finite primitive subgroups of SL_{3}.

4.3.1. Imprimitive groups

Assume that G is irreducible. If there is a semi-invariant of degree 3, then the group is either imprimitive or F_{36}^{SL_{3}} (Singer and Ulmer, 1993a, Table 2 and Proposition 3.6). In both cases there is a Liouvillian solution. If the group is F_{36}^{SL_{3}}, then there is no semi-invariant of degree 3 corresponding to a character of order 2 (i.e. whose square is an invariant). Thus, if there is a semi-invariant of degree 3 corresponding to a character of order 2 then the group must be imprimitive. An imprimitive group of degree 3 is monomial, i.e. there exists a basis {y_{1}, y_{2}, y_{3}} such that an element of G has only one non zero entry in row and column. Since G ⊂ SL(3, C), we have ∀g ∈ G, g(y_{1}y_{2}y_{3}) = ±y_{1}y_{2}y_{3} (Singer and Ulmer, 1993a, Proposition 3.6). There are at least one and at most 4 Riccati polynomials of degree 3 in this case (Hendriks and van der Put, 1994, Ulmer, 1994).

4.3.2. A_{5}

Lemma 4.1. If G ≃ A_{5} then there is exactly one Riccati polynomial of degree 6 and exactly one of degree 15. The Riccati polynomial of degree 6 can be obtained by applying appendix A on the 2dimensional space of invariants of degree 6. The canonical image of the invariant of degree 15 is obtained the following way: compute the images P_{2} and P_{6} of the invariants of degrees 2 and 6. Let P_{10} be their bordered Hessian, and P_{15} be the Jacobian of these three (P_{15} is unique and does not depend on the choice of P_{6}).

Proof. That there exists a Riccati polynomial of degree 6 is proven in Singer and Ulmer (1993b). Its uniqueness follows from the fact that there are 6 conjugate non-Abelian subgroups of index 6 having each one common eigenvector. So we turn to degree 15. There are 5 conjugate subgroups of order 4 in A_{5} which are all Abelian of exponent 2. Using the matrix representation of A_{5} given in Singer and Ulmer (1993b), we get that one such group, say H, is generated by the matrices {E_{2}E_{1}E_{2}E_{3}E_{2}E_{1}, E_{3}E_{1}} which have (−ζ_{5}^{3} + ζ_{5} + 1, ζ_{5}, 1)^{t} as a common eigenvector, where ζ_{5} = exp(2πi/5). In order to find the corresponding semi-invariant that factors into linear forms, we look at a set

S = {id, E_{1}^{−1}, E_{2}^{−1}, E_{3}^{−1}, E_{2}^{−1}E_{1}^{−1}, E_{1}^{−1}E_{2}^{−1}, E_{2}^{−1}E_{3}^{−1}, E_{1}^{−1}E_{2}^{−1}E_{1}^{−1}, E_{3}^{−1}E_{2}^{−1}E_{1}^{−1},
E_{1}^{−2}E_{2}^{−1}, E_{2}^{−1}E_{1}^{−1}E_{2}^{−1}, E_{1}^{−1}E_{2}^{−1}E_{3}^{−1}, E_{1}^{−2}E_{2}^{−1}E_{1}^{−1}, E_{3}^{−1}E_{1}^{−1}E_{2}^{−1}E_{1}^{−1}, E_{1}^{−1}E_{3}^{−1}E_{2}^{−1}E_{1}^{−1}}

of left coset representatives of H in A_{5}. The resulting polynomial

∏_{g∈S} g ((−ζ_{5}^{3} + ζ_{5} + 1)y_{1} + ζ_{5}y_{2} + y_{3})

which by construction factors into linear forms over the complex numbers, is a semi-invariant and thus an invariant† of the simple group A_{5}. The length of the orbit of the logarithmic derivative of the eigenvector, i.e. the degree of its minimal polynomial, divides 15 = [A_{5} : H]. From Singer and Ulmer (1993b), we know that this degree must be ≥ 6, so the degree must be 15 and that the associated polynomial must be a Riccati polynomial of degree 15. Note that there is, up to multiple, a unique invariant of degree 15 which thus must factor into linear forms. The statement on the construction of the invariant of degree 15 from the invariants of degree 2 and 6 follows from the uniqueness and from a simple direct computation on classical invariants (Miller, Blichfeldt, and Dickson, 1938, paragraph 125 pp 253–255). □

4.3.3. G_{168}

Lemma 4.2. If G ≃ G_{168}, then there is a unique Riccati polynomial of degree 21. Its canonical image P_{21} is obtained the following way. Let P_{4} be the image of the invariant of degree 4, let P_{6} be its Hessian, and let P_{14} be the bordered Hessian of P_{4} and P_{6}; then P_{21} is obtained from the Jacobian of P_{4}, P_{6}, P_{14}.

Proof. From Singer and Ulmer (1993b) we get that there exists a Riccati polynomial of degree 21. Since the group is simple, any semi-invariant must be an invariant. There is a unique trivial summand in the decomposition of the character of the 21-th symmetric power of the faithful irreducible unimodular 3-dimensional characters, we get that the semi-invariant must correspond to the, up to multiple, unique invariant of degree 21 and thus factor into linear forms. The corresponding group H and the coset representatives are given in Singer and Ulmer (1993b). The statement on P_{21} follows from the uniqueness and from direct computation on classical invariants (Miller, Blichfeldt, and Dickson, 1938, paragraph 125 pp 253–255). □

† This invariant does not correspond to the invariants given in Singer and Ulmer (1993b) where another basis of the solution space was chosen in order to express the invariants.

4.3.4. H_{216}^{SL_{3}} and H_{72}^{SL_{3}}

From Singer and Ulmer (1993b), we get that there exists a Riccati polynomial of degree 9. Since there is no non-trivial character of degree 1 and a unique trivial summand in the decomposition of the character of the 9-th symmetric power of the faithful irreducible unimodular 3-dimensional characters, we get that the semi-invariant must correspond to the, up to multiple, unique invariant of degree 9 which thus must factor into linear forms. The corresponding group H and the coset representatives are given in Singer and Ulmer (1993b).

4.3.5. G_{168} × C_{3}

The, up to multiple, unique invariant of degree 21 of G_{168} factors into linear forms (see section 4.3.3). Since its order is divisible by 3 it is also an invariant of C_{3} and thus a, up to multiple, unique invariant of G_{168} × C_{3} that factors into linear forms. Since 21 is the minimal degree of a Riccati polynomial in this case (Singer and Ulmer, 1993b), it must correspond to a Riccati polynomial. This Riccati polynomial can be constructed from the semi-invariant of degree 4 (whose cube is rational) as in section 4.3.3.

4.3.6. A_{6}^{SL_{3}}

Lemma 4.3. If G ≃ A_{6}^{SL_{3}}, then there is exactly one Riccati polynomial of degree 45, and it is obtained from an invariant, which can be computed in the following way: let P_{6} be the invariant of degree 6, let P_{12} be the Hessian of P_{6}, and let P_{30} be the bordered Hessian of P_{6} and P_{12}. Then P_{45} is obtained from the Jacobian of P_{6}, P_{12}, P_{30}.

We note that there is also a Riccati polynomial of degree 36 (Singer and Ulmer, 1993b) but we know of no simple formula to obtain it; furthermore, the space of invariants of degree 36 for A_{6}^{SL_{3}} has dimension 5 so selecting the completely factorable invariant would be a very hard task.

Proof. There are 3 types of non conjugate subgroups of order 24 in A_{6}^{SL_{3}}. Only one type consisting of 45 conjugate non Abelian subgroups of order 24 is 1-reducible (the 24 elements have a common eigenvector). Using the matrix representation of A_{6}^{SL_{3}} given in Singer and Ulmer (1993b), we get that one such group, say H, is generated by the matrices {E_{4}E_{1}E_{2}E_{3}E_{1}E_{2}E_{1}^{−1}E_{4}, (E_{4}E_{1}^{−1})^{2}, E_{3}E_{2}E_{4}E_{3}, E_{3}E_{4}E_{3}} which have a common eigenvector. In order to find the corresponding semiinvariant that factors into linear forms, we look at a set S of left coset representatives of H in A_{6}^{SL_{3}} (containing 45 elements). Since the group is perfect and has no non-trivial character of degree 1, the semi-invariant must be an invariant. There is, up to multiple, only one invariant of degree 45 for this group which thus must factor into linear forms by the above. The length of the orbit of the logarithmic derivative of the eigenvector divides 45 = [A_{6}^{SL_{3}} : H]. From Singer and Ulmer (1993b), we get that this degree must be ≥ 36 and thus that the degree must be 45 and that the associated polynomial must be a Riccati polynomial of degree 45. The statement on P_{45} follows from the uniqueness and from direct computation on classical invariants (Miller, Blichfeldt, and Dickson, 1938, paragraph 125 pp 253–255). □

4.3.7. F_{36}^{SL_{3}}

There are 9 conjugate subgroups of order 12 in F_{36}^{SL_{3}} which are all Abelian. Using the matrix representation of F_{36}^{SL_{3}} given in Singer and Ulmer, 1993b, we get that one such group, say H, is generated by the matrices {V, U^{3}} which have (0, −1, 1)^{t} (see Singer and Ulmer, 1993b for the notations) as a common eigenvector. Note that U^{3} is ω times the identity where ω is a third root of unity, and that U^{3} is in F_{36}^{SL_{3}}. In order to find the corresponding semi-invariant that factors into linear forms, we look at a set S = {id, S, T, S^{−1}, T^{−1}, T^{−1}S^{−1}, T S^{−1}, T^{−1}S, T S} of left coset representatives of H in F_{36}^{SL_{3}}. The resulting polynomial

∏_{g∈S} (g(−y_{2} + y_{3})) = −y_{3}^{3}y_{2}^{6} + y_{1}^{3}y_{2}^{6} − y_{1}^{6}y_{2}^{3} + y_{3}^{6}y_{2}^{3} − y_{3}^{6}y_{1}^{3} + y_{1}^{6}y_{3}^{3}

which by construction factors into linear forms over the complex numbers, is in fact an invariant† of F_{36}^{SL_{3}} (check using the generators). The length of the orbit of the logarithmic derivative of the eigenvector, i.e. the degree of its minimal polynomial, divides 9 = [F_{36}^{SL_{3}} : H]. From Singer and Ulmer (1993b) we know that this degree must be ≥ 6, so the degree must be 9 and the associated minimal polynomial must be an irreducible Riccati polynomial of degree 9.

4.3.8. A_{5}^{SL_{3}} × C_{3}

The, up to multiple, unique invariant of degree 15 of A_{5} which, by section 4.3.2, factors into linear forms is, since its order is divisible by 3, also an invariant of C_{3} and thus an, up to multiple, unique invariant of A_{5} × C_{3} which factors into linear forms. Since 6 is the minimal degree of a Riccati polynomial in this case (Singer and Ulmer, 1993b), it must correspond to such a Riccati polynomial.

4.4. Example

L = ∂^{3} + \frac{21 (x^{2} − x + 1)}{25 x^{2} (x − 1)^{2}}∂ − \frac{21 (2 x − 1) (x^{2} − x + 2)}{50 x^{3} (x − 1)^{3}}

The operator is irreducible. There is a two-dimensional space of invariants of degree 6. None of them is a square so we proceed to step 3. There is one invariant of degree 2, so we know that G/Z(G) ≃ A_{5}^{SL_{3}}. The invariants of degree 6 (variables \overline{y}_{i}, parameters a_{1}, a_{2}) are:

(2560 a_{1} − 30 a_{2}) \overline{y}_{1}^{3} \overline{y}_{2}^{3} + 6 \overline{y}_{3} \overline{y}_{1}^{5} a_{1}
+ (−1024 a_{1} + 30 a_{2}) \overline{y}_{3}^{6} − 393216 \overline{y}_{3} \overline{y}_{2}^{5} a_{1}
+ (15360 a_{1} − 90 a_{2}) \overline{y}_{1} \overline{y}_{2} \overline{y}_{3}^{4} + 90 \overline{y}_{3}^{2} \overline{y}_{2}^{2} \overline{y}_{1}^{2} a_{2}

Using a complete factorization approach, we find that for 256a_{1} = 3a_{2} we have the following factor (up to conjugation):

\overline{y}_{1} − α^{2}\overline{y}_{2} + α\overline{y}_{3}, where α^{5} − 256 = 0

and the remaining factor is simply \overline{y}_{3}. The coefficients of the corresponding canonical image are:

[ −4608 x^{4} (x − 1)^{4}, −3072 (−1 + 2 x) x^{3} (x − 1)^{3},

− 1536/5 x^{2} (7 x^{2} − 7 x − 3) (x − 1)^{2},

− \frac{1536}{25} x^{2} (133 x^{2} − 133 x + 33) (x − 1)^{2},

− \frac{2304}{125} x (x − 1) (−1 + 2 x) (77 x^{2} − 77 x − 34) , −\frac{110592}{625}

+ \frac{1204224}{625} x^{3} − \frac{602112}{625} x^{4} − \frac{562176}{625} x − \frac{39936}{625} x^{2},

− \frac{13824}{125} x (x − 1) (7 x − 4) (−1 + 2 x) (7 x − 3), \frac{262656}{625}

† Note that if the result would be a semi invariant, one could find the corresponding one dimensional character using this construction.

+ \frac{4666368}{625} x^{3} − \frac{2333184}{625} x^{4} − \frac{479232}{625} x − \frac{1853952}{625} x^{2},

− \frac{3072 (−1 + 2 x) (637 x^{4} − 1274 x^{3} + 25 x^{2} + 612 x + 126)}{3125 x (x − 1)}, …]

From this, we read the coefficients of the minimum polynomial of an algebraic solution of the corresponding Riccati equation using theorem 2.1. We use rows that correspond to the monomials X_{1}^{l}X_{2}^{6−l}, l = 0, 1, …, 6. The way we numbered the monomials X_{1}^{l_{1}}X_{2}^{l_{2}}X_{3}^{6−l_{1}−l_{2}}, this corresponds to rows 1, 2, 4, 7, 11, 16, 22. We obtain:

X^{6} − 4 \frac{(−1 + 2 x) X^{5}}{x (x − 1)} + \frac{(133 x^{2} − 133 x + 33) X^{4}}{5 x^{2} (x − 1)^{2}}

− \frac{12 (7 x − 4) (−1 + 2 x) (7 x − 3) X^{3}}{25 x^{3} (x − 1)^{3}}

+ \frac{(351 − 11662 x^{3} + 5831 x^{4} − 2862 x + 8693 x^{2}) X^{2}}{125 x^{4} (x − 1)^{4}}

− \frac{4 (−1 + 2 x) (9604 x^{4} − 19208 x^{3} + 14275 x^{2} − 4671 x + 567) X}{3125 x^{5} (x − 1)^{5}}

+ \frac{(16807 x^{4} − 33614 x^{3} + 24907 x^{2} − 8100 x + 972) (−1 + 2 x)^{2}}{12500 x^{6} (x − 1)^{6}}

Alternatively, we can avoid the factoring by using sections 2.4 and section 4.3.2 to construct directly the (unique) Riccati polynomial of degree 15 via bordered Hessian and Jacobian applied on the invariants of degree 2 and 6. The result is the following irreducible Riccati polynomial:

X^{15} − 6 \frac{(7 x^{4} − 14 x^{3} − 4 x^{2} + 11 x − 3)}{x (x − 1) (−2 + x) (−1 + 2 x) (x + 1)}X^{14}

+ \frac{21 (49 x^{4} − 98 x^{3} − 20 x^{2} + 69 x − 18)}{5 x^{2} (x + 1) (−2 + x) (x − 1)^{2}}X^{13}

− \frac{13 (9604 x^{6} − 28812 x^{5} + 19119 x^{4} + 9782 x^{3} − 15741 x^{2} + 6048 x − 756)}{50 x^{3} (−2 + x) (−1 + 2 x) (x + 1) (x − 1)^{3}}X^{12}

+ \frac{13 (50421 x^{6} − 151263 x^{5} + 107203 x^{4} + 37699 x^{3} − 71843 x^{2} + 27783 x − 3402)}{125 x^{4} (x + 1) (−2 + x) (x − 1)^{4}}X^{11} + …

Appendix: Deciding when a homogeneous polynomials admits linear factors

If A is a ring, we denote by A[X_{1}, …, X_{n}]_{m} the space of homogeneous polynomials of total degree m in the variables X_{i}. Let P ∈ C[t_{1}, …, t_{s}][X_{1}, …, X_{n}]_{m} be homogeneous of degree m in the variables X_{i}. In this appendix, we show how to compute potential values of the parameters t_{i} such that P (then viewed as a homogeneous polynomial in C[X_{1}, …, X_{n}]) admits a linear factor. The subproblem relevant in this paper is the following: Let P = ∑ t_{i}P_{i} where P_{i} ∈ C[X_{1}, …, X_{n}]_{m}. Decide for which values of the t_{i} the polynomial P admits a linear factor. This problem is part of the general problem of absolute factorization of polynomials. For the latter, the reader may consult Ragot (1997) where several methods and abundant references are given.

A1: Brill’s equations

Completely factorable polynomials of degree m form a Zariski closed set. The defining equations, the Brill equations, are homogeneous equations of degree m that can be computed (Brill, 1898, Gelfan’d, Kapranov, and Zelevinski, 1994). This can be used (Singer and Ulmer, 1997) to select the completely factorable semi-invariants.

A2: Complete factorization of non-parametrized polynomials

If there are no parameters in P, then many methods exist (Hohl, 1995, Kobayashi, Fujise, and Furukawa, 1988, and Ragot, 1997, for another method and references). We outline below a method that seems, from our experience, to be the most interesting. The tools and results are similar to the ones that are used in the three papers mentioned above. Let C be a perfect field (usually C is Q or a finite extension of Q).

Definition 4.1. Let P be a polynomial of C[X_{1}, …, X_{n}]_{m} of degree d > 0 in X_{1} . A n − 1-tuple (a_{2}, …, a_{n}) of C^{n−1} is called a non critical value for P in X_{1} if the polynomial P (T, a_{2}, …, a_{n}) is square-free and of degree d. This implies in particular that all roots of P (T, a_{2}, …, a_{n}) are simple.

Remark : The existence of such a non-critical value for P implies that P is square-free. From now on, let \underline{Z} denote the multi-variable X_{3}, …, X_{n}.

Lemma 4.4. Let P be a homogeneous square-free polynomial of C[X_{1}, X_{2}, \underline{Z}]_{m}, of degree d > 0 in X_{1} . Assume that P is of degree m in X_{2} , and let (1, 0, …, 0) be a non critical value for P in X_{1} . Denote by p(T) the polynomial P (T, 1, \underline{0}) and let α be a root of p(T) . Then P (X_{1} + α X_{2}, X_{2}, \underline{Z}) is of degree m − 1 in X_{2} .

Proof. Let P̄(X_{1}, X_{2}) = P (X_{1}, X_{2}, \underline{0}) . It is a homogeneous polynomial of C[X_{1}, X_{2}] . Write

P̄ = X_{2}^{m−d} ∑_{i=0}^{d} b_{i} X_{1}^{i} X_{2}^{d−i} ;

It factors in \overline{C}[X_{1}, X_{2}] as

b X_{2}^{m−d} ∏_{i=1}^{d}(X_{1} − α_{i} X_{2})

where the α_{i}, with i from 1 to d, are the roots of p(T) . Hence

P̄(X_{1} + α X_{2}, X_{2}) = b X_{2}^{m−d} ∏_{i=1}^{d} (X_{1} + (α − α_{i}) X_{2}) .

The roots of p(T) are simple, so α − α_{i} = 0 for one unique i, which proves that P̄(X_{1} + α X_{2}, X_{2}) is of degree m − 1 in X_{2} . It is also true for P (X_{1} + α X_{2}, X_{2}, \underline{Z}) , since P̄(X_{1} + α X_{2}, X_{2}) is its evaluation in \underline{Z} = \underline{0} . □

Proposition 4.1. Let notations and assumptions be as above, and let P̃_{T} (X_{1}, X_{2}, \underline{Z}) = P (X_{1} + T X_{2}, X_{2}, \underline{Z}); then P admits a linear factor in \overline{C}[X_{1}, X_{2}, \underline{Z}] if and only if there exists a root α of p

such that \frac{∂^{m−1}P̃_{α}}{∂ X_{2}^{m−1}} is a linear factor of P̃_{α} in C(α)[X_{1}, \underline{Z}] .

Proof. Let L = X_{1}+a X_{2}+∑_{i=3}^{n} c_{i} X_{i} be a linear factor of P and let C′ be the field of its coefficients. Denote by r the degree of C′ over C. The polynomial L is absolutely irreducible and by theorem 1.2.2 of Ragot (1997), F = Norm_{C′/C}(L) is an irreducible polynomial of C[X_{1}, X_{2}, \underline{Z}] . It is clearly of degree r, and it is a factor of P . The polynomial F (T, 1, 0, …, 0) is a factor of p(T) , it is hence square-free. On the other hand, F (T, 1, 0, …, 0) = Norm_{C′/C}(L(T, 1, 0, …, 0)) = Norm_{C′/C}(T + a) , and by lemma 1.2.1 of Ragot (1997) (or theorem 2.1 of Trager (1976) extended to perfect fields), Norm_{C′/C}(T + a) is a power of an irreducible polynomial of C[T] . This implies that F (T, 1, 0, …, 0) is an irreducible polynomial of degree r. Let α = −a; then α is of degree r and C′ = C(α) .

Hence,

L = X_{1} − α X_{2} + ∑_{i=3}^{n} c_{i}(α) X_{i}

where the c_{i}’s are polynomials with coefficients in C. Let P = L · Q, then P̃_{α} = L̃_{α} · Q̃_{α} = (X_{1} + ∑_{i=3}^{n} c_{i}(α) X_{i}) · Q̃_{α}. Now P̃_{α}, and then Q̃_{α}, are of degree m − 1 in X_{2} (lemma 4.4) and so

\frac{∂^{m−1}P̃_{α}}{∂ X_{2}^{m−1}} = c(α) · (X_{1} + ∑_{i=3}^{n} c_{i}(α) X_{i}) .

Conversely, if X_{1} + ∑_{i=3}^{n} c_{i}(α) X_{i} is a factor of P̃_{α} then X_{1} − α X_{2} + ∑_{i=3}^{n} c_{i}(α) X_{i} is a factor of P .

□

This suggests the following fast algorithm to check whether a given square-free polynomial has linear factors (and compute them as a byproduct). After maybe a linear change of variables† we may assume that P satisfies the hypotheses of proposition 4.1. Form P_{α} and L_{α} as in proposition 4.1. Then the corresponding L is a factor of P if and only if L_{α} divides all coefficients of powers of X_{2} in P_{α}; the latter conditions are easily stated via resultants or even Euclidean divisions and, together with the relation p(α) = 0, they yield a system of polynomial equations for α: our polynomial P has a linear factor if and only if the latter system is consistent.

A3: Complete factorization of parametrized polynomials

The above method can be adapted to polynomials depending on parameters, although the conditions that P be square-free and that (1, 0, …, 0) be non-critical may induce some nuisance (non-linear branchings); if one avoids the branching, then the algorithm is incomplete but yields an interesting heuristic. The following straightforward method can also be used, without any restrictions on the parameters. Write L = X_{1}+∑_{i=2}^{n} c_{i}X_{i}. We want conditions for L to be a factor of P. Let R := resultant(P, L, X_{1}) = P (− ∑_{i=2}^{n} c_{i}X_{i}) (note that R = P (− ∑_{i=2}^{n} c_{n}X^{n}, X_{2}, …, X_{n})). Of course, there is a linear factor if and only if R is the zero polynomial. The coefficients of R depend on the t_{i} and the c_{i}; equating all these to zero yields a polynomial system that we solve with any available method (see e.g Cox, Little, and O’Shea (1992) for an introduction to these). In our specific problem, the system is linear in the t_{i} and non-linear in the c_{i} so we can also apply the methods of Sit (1992) for solving it. Surprisingly, this simple method is quite satisfactory in practice and can be faster than (our implementation of) the Brill equations. We may interpret this experimental fact as follows. Using the Brill equations is like solving the system that we would obtain by first eliminating the c_{i}; however, here, it may be that another solving strategy is better (e.g because of the linearity in the t_{i}) so it could compensate for the fact of adding the extra variables c_{i}.

A4: Deciding when a polynomial is an k-th power

Let P be of the form P = ∑ t_{i}P_{i} where the P_{i} ∈ C[X_{1}, …, X_{n}] are homogeneous of degree m. After a linear transformation we may assume that the degree of P in X_{1} equals m. Assume that P = Q^{k}. Let L be the coefficient of X_{1}^{m}. We need to distinguish two cases: After substituting values in C for the t_{i} either L vanishes or L remains non-zero. First we compute under the assumption that L vanishes. So we have a linear relation L = 0 between the parameters t_{i} (P is linear in the t_{i}). We use this relation to eliminate one of the t_{i} and then apply recursion.

† The condition on a change of variables to be such that P satisfies the hypothesis of proposition 4.1 are easily seen to form a Zariski closed set so “almost any” change of variables will do.

Afterwards we may assume that L does not vanish. Because P is homogeneous in the t_{i} we may then assume that L = 1. We use this relation to eliminate one of the t_{i}. Then P is a monic polynomial in X_{1} with coefficients in C[t_{1}, …, t_{s}, X_{2}, …, X_{n}], and the degree of Q in X_{1} is d = m/k. Write Q = ∑_{i=0}^{d} q_{i}X_{1}^{i} where q_{d} = 1. Taking the coefficient of X_{1}^{m−1} on both sides of the equation P = Q^{k} (the coefficient on the right-hand side is kq_{d−1}) we find q_{d−1} ∈ C[t_{1}, …, t_{s}, X_{2}, …, X_{n}]. Repeating this for the next coefficients X_{1}^{m−2}, X_{1}^{m−3}, …, X_{1}^{m−d} we determine q_{d−2}, q_{d−3}, …, q_{0} ∈ C[t_{1}, …, t_{s}, X_{2}, …, X_{n}]. Then we can compute P − Q^{k} and equate all coefficients with respect to X_{1}, …, X_{n} to 0. This gives a set of polynomial equations in the parameters t_{i}. Solving it gives the values of t_{i} for which P is a k-th power.

References

Barkatou, M.A. (1998). On rational solutions of systems of linear differential equations, This volume. Barkatou, M. A., Pflügel, E. (1998) An Algorithm Computing the Regular Formal Solutions of a System of Linear

Differential Equations, This volume Brill, A. (1998) Über die Zerfällung einer Ternärform in Linearfactoren, Math. Ann. 50, p. 157-182. Cox, D., Little, J., O’Shea, D. (1992). Ideals, varieties, and Algorithms Undergraduate Texts in Math, Springer Fakler, W. (1997). On second order homogeneous linear differential equations with Liouvillian solutions. Theoretical

Computer Science 187 (1-2):27-48. Gelfan’d, I.M, Kapranov, M.M, Zelevinski, A.V (1994). Discriminants, Resultants, and Multidimensional Determinants

Birkhaüser. Hendriks, P., van der Put, M. (1995). Galois action on solutions of a differential equation, J. Symb. Comp. 19, pp.

559-576. Hessinger, S. (1998). Galois groups of fourth order linear differential equations PhD dissertation, North Carolina State

University. Hoeij, M. van (1997). Factorization of Differential Operators with Rational Functions Coefficients, J. Symb. Comp. 24,

1-30. Hoeij, M. van, Weil, J.-A. (1997). An algorithm for computing invariants of differential Galois groups, J. Pure and

Applied Alg., 117 & 118, 353-379. Hohl, J.-C. (1995). Massively parallel search for linear factors in polynomials with many variables, ICM preprint . Kobayashi, H., Fujise, T., Furukawa, A. (1988). Solving systems of algebraic equations by a general elimination method,

J. Symb. Comp, Vol 5, 303-320. Kovacic, J. (1986). An algorithm for solving second order linear homogeneous differential equations J. Symb. Comp 2

3-43. Lang, S. (1992). Algebra Third edition, Addison-Wesley. Magid, A. (1994). Lectures on Differential Galois Theory, University Lecture Series of the American Mathematical

Society. Miller, G.A., Blichfeldt, H.F., Dickson L.E. (1938). Theory and Applications of Finite Groups. New York: G. G. Stechert

and Co. Pflügel, E. (1997). An Algorithm for Computing Exponential Solutions of First Order Linear Differential Systems,

ISSAC’97 Proceedings, ACM Press. Put, M. van der (1998) Galois theory of differential equations, Algebraic groups and Lie algebras, This volume Put, M. van der, Ulmer, F. (1998) Differential equations and finite groups, MSRI Preprint #1998-058 . Ragot, J.- F. (1997). Sur la factorisation absolue des polynômes, PhD dissertation, Université de Limoges. Singer, M. F. (1981). Liouvillian Solutions of n^{th} Order Linear Differential Equations Am. J. Math. 103, 661–682. Singer, M. F. (1995). Testing reducibility of linear differential operators: a group theoretic perspective, J. of Appl. Alg.

in Eng. Comm. and Comp. 7, 77-104. Singer, M. F. (1997). Direct and inverse problems in differential Galois theory. To appear in: Collected Works of Ellis

R. Kolchin. Singer, M. F., Ulmer, F. (1993a). Galois groups for second and third order linear differential equations J.Symb.Comp

16 No. 1, 1-36. Singer, M. F., Ulmer, F. (1993b). Liouvillian and algebraic solutions of second and third order linear differential equations

J.Symb.Comp 16 No. 1, 37-73. Singer, M. F., Ulmer, F. (1995). Necessary conditions for Liouvillian solutions of (third order) linear differential equations

J. of Appl. Alg. in Eng. Comm. and Comp. vol 6 No. 1, 1-22. Singer, M. F., Ulmer, F. (1997). Linear differential equations and products of linear forms. J. Pure and Applied Alg.,

117 & 118, 549-564. Sit, W. (1992). An algorithm for solving parametric linear systems, J. Symb. Comp. vol 13, No 4, 353-413. Trager, B. M. (1976). Algebraic Factoring and Rational Function Integration. Proceedings of the 1976 ACM Symposium

on Symbolic and algebraic Computation. Tsarev, S. P. (1996). An Algorithm for Complete Enumeration of All Factorizations of a Linear Ordinary Differential

Operator, ISSAC’96 Proceedings, ACM Press. Ulmer, F. (1994). Irreducible linear differential equations of prime order J. Symb. Comp. vol 18 No 4 , 385-401. Ulmer, F., Weil, J.-A. (1996). Note on Kovacic’s algorithm J.Symb.Comp. vol 22 n^{∘} 2, 179-200. Weil, J.-A. (1995a). First integrals and Darboux polynomials of homogeneous linear differential systems, Proceedings of

AAECC 11 (Ed. M. Giusti & T. Mora), Lect. Notes in Comp. Sci. 948, Springer. Weil, J.-A. (1995b). Constantes et polynômes de Darboux en algèbre différentielle : application aux systèmes différentiels

linéaires, PhD dissertation, École Polytechnique.