No title

Around the numeric-symbolic computation

of differential Galois groups

Joris van der Hoeven

Dépt. de Mathématiques (bât. 425)

Université Paris-Sud

91405 Orsay Cedex

France

Email: vdhoeven@texmacs.org

July 3, 2006

Let $L \in 𝕂 (z) [\partial]$ be a linear differential operator, where $𝕂$ is an effective algebraically closed subfield of $ℂ$ . It can be shown that the differential Galois group of $L$ is generated (as a closed algebraic group) by a finite number of monodromy matrices, Stokes matrices and matrices in local exponential groups. Moreover, there exist fast algorithms for the approximation of the entries of these matrices.

In this paper, we present a numeric-symbolic algorithm for the computation of the closed algebraic subgroup generated by a finite number of invertible matrices. Using the above results, this yields an algorithm for the computation of differential Galois groups, when computing with a sufficient precision.

Even though there is no straightforward way to find a “sufficient precision” for guaranteeing the correctness of the end-result, it is often possible to check a posteriori whether the end-result is correct. In particular, we present a non-heuristic algorithm for the factorization of linear differential operators.

1.Introduction

Let $L \in 𝕂 (z) [\partial]$ be a monic linear differential operator of order $n$ , where $𝕂$ is an effective algebraically closed subfield of $ℂ$ . A holonomic function is a solution to the equation $L f = 0$ . The differential Galois group $𝒢$ of $L$ is a linear algebraic group which acts on the space $H$ of solutions (see section 2.2 and [Kap57, vdPS03, Kol73]). It carries a lot of information about the solutions in $H$ and on the relations between different solutions. For instance, the existence of non-trivial factorizations of $L$ and the existence of Liouvillian solutions can be read off from the Galois group. This makes it an interesting problem to explicitly compute the Galois group of $L$ .

A classical approach in this area is to let $𝒢$ act on other vector spaces obtained from $H$ by the constructions from linear algebra, such as symmetric powers $\otimes^{k} H$ and exterior powers $\land^{k} H$ [Bek94, SU93]. For a suitable such space $S$ , the Galois group $𝒢$ consists precisely of those invertible $n \times n$ matrices which leave a certain one-dimensional subspace of $S$ invariant [Hum81, chapter 11]. Invariants in $\otimes^{k} H$ or $\land^{k} H$ under $𝒢$ may be computed more efficiently by considering the local solutions of $L f = 0$ at singularities [vHW97, vH97, vH96]. More recently, and assuming (for instance) that the coefficients of $L$ are actually in $ℚ (z)$ , alternative algorithms appeared which are based on the reduction of the equation $L f = 0$ modulo a prime number $p$ [Clu04, vdP95, vdPS03].

In this paper, we will study another type of “analytic modular” algorithms, by studying the operator $L$ in greater detail near its singularities using the theory of accelero-summation [É85, É87, É92, É93, Bra91, Bra92]. More precisely, we will use the following facts:

The differential Galois group of $L$ is generated (as a closed algebraic group) by a finite number of monodromy matrices, Stokes matrices and matrices in so called local exponential groups.
There exists an algorithm [vdH99, vdH01b, vdH05b] for the approximation of the entries of the above matrices. If $𝕂 = ℚ^{alg}$ is the algebraic closure of $ℚ$ , then $d$ -digit approximations can be computed in time $O (d \log^{4} d \log \log d)$ .

When using these facts for the computation of differential Galois groups, the bulk of the computations is reduced to linear algebra in dimension $n$ with multiple precision coefficients.

In comparison with previous methods, this approach is expected to be much faster than algorithms which rely on the use of exterior powers. A detailed comparison with arithmetic modular methods would be interesting. One advantage of arithmetic methods is that they are easier to implement in existing systems. On the other hand, our analytic approach relies on linear algebra in dimension $n$ (with floating coefficients), whereas modulo $p$ methods rely on linear algebra in dimension $n p$ (with coefficients modulo $p$ ), so the first approach might be a bit faster. Another advantage of the analytic approach is that it is more easily adapted to coefficients fields $𝕂$ with transcendental constants.

Let us outline the structure of this paper. In section 2, we start by recalling some standard terminology and we shortly review the theorems on which our algorithms rely. We start with a survey of differential Galois theory, monodromy and local exponential groups. We next recall some basic definitions and theorems from the theory of accelero-summation and the link with Stokes matrices and differential Galois groups. We finally recall some theorems about the effective approximation of the transcendental numbers involved in the whole process.

Before coming to the computation of differential Galois groups, we first consider the simpler problem of factoring $L$ in section 3. We recall that there exists a non-trivial factorization of $L$ if and only if the Galois group of $L$ admits a non-trivial invariant subspace. By using computations with limited precision, we show how to use this criterion in order to compute candidate factorizations or a proof that there exist no factorizations. It is easy to check a posteriori whether a candidate factorization is correct, so we obtain a factorization algorithm by increasing the precision until we obtain a correct candidate or a proof that there are no factorizations.

In section 4 we consider the problem of computing the differential Galois group of $L$ . Using the results from section 2, it suffices to show how to compute the algebraic closure of a matrix group $𝒢$ generated by a finite number of given elements. A theoretical solution for this problem based on Gröbner basis techniques has been given in [DJK03]. The main idea behind the present algorithm is similar, but more emphasis is put on efficiency (in contrast to generality).

First of all, in our context of complex numbers with arbitrary precisions, we may use the LLL-algorithm for the computation of linear and multiplicative dependencies [LLL82]. Secondly, the connected component of $𝒢$ is represented as the exponential of a Lie algebra $ℒ$ given by a basis. Computations with such Lie algebras essentially boil down to linear algebra. Finally, we use classical techniques for finite groups in order to represent and compute with the elements in $𝒢 / e^{ℒ}$ [Sim70, Sim71, MO95]. Moreover, we will present an algorithm for non-commutative lattice reduction, similar to the LLL-algorithm, for the efficient computation with elements in $𝒢 / e^{ℒ}$ near the identity.

The algorithms in section 4 are all done using a fixed precision. Although we do prove that we really compute the Galois group when using a sufficiently large precision, it is not clear a priori how to find such a “sufficient precision”. Nevertheless, we have already seen in section 3 that it is often possible to check the correctness of the result a posteriori, especially when we are not interested in the Galois group $𝒢$ itself, but only in some information provided by $𝒢$ . Also, it might be possible to reduce the amount of dependence on “transcendental arguments” in the algorithm modulo a further development of our ideas. Some hints are given in the last section.

Remark 1. The author first suggested the main approach behind this paper during his visit at the MSRI in 1998. The outline of the algorithm in section 4.5 came up in a discussion with Harm Derksen (see also [DJK03]). The little interest manifested by specialists in effective differential Galois theory for this approach is probably due to the fact that current computer algebra systems have very poor support for analytic computations. We hope that the present article will convince people to put more effort in the implementation of such algorithms. We started such an effort [vdHea05], but any help would be appreciated. Currently, none of the algorithms presented in this paper has been implemented.

2.Preliminaries

2.1.Notations

Throughout this paper, we will use the following notations:

$𝕂 \subseteq ℂ$: An algebraically closed field of constants.
${Mat}_{n} (𝕂)$: The algebra of $n \times n$ matrices with coefficients in $𝕂$ .
${GL}_{n} (𝕂)$: The subgroup of ${Mat}_{n} (𝕂)$ of invertible matrices.
$Vect (S)$: The vector space generated by a subset $S$ of a larger vector space.
$Alg (S)$: The algebra generated by a subset $S$ of a larger algebra.

Vectors are typeset in bold face $𝒗 = (v_{1}, \dots, v_{n})$ and we use the following vector notations:

\begin{array}{rcl} 𝒗 \cdot 𝒘 & = & v_{1} w_{1} + \dots + v_{n} w_{n} \\ 𝒗^{𝒌} & = & v_{1}^{k_{1}} \dots v_{n}^{k_{n}} \end{array}

Matrices $M \in {Mat}_{n} (𝕂)$ will also be used as mappings $M : 𝕂^{n} \to 𝕂^{n}; 𝒗 \mapsto M 𝒗$ . When making a base change in $𝕂^{n}$ , we understand that we perform the corresponding transformations $M \to P M P^{- 1}$ on all matrices under consideration. We denote $Diag (X_{1}, \dots, X_{p})$ for the diagonal matrix with entries $X_{1}, \dots, X_{p}$ . The $X_{i}$ may either be scalars or square matrices. Given a matrix $M \in {Mat}_{n} (𝕂)$ and a vector $𝒗 \in 𝕂^{n}$ , we write $𝒗^{M}$ for the vector $𝒘$ with $w_{i} = v_{1}^{M_{i, 1}} \dots v_{n}^{M_{i, n}}$ for all $i$ .

2.2.Differential Galois groups

Consider a monic linear differential operator $L = \partial^{n} + L_{n - 1} \partial + \dots + L_{0} \in ℱ [\partial]$ , where $𝕂$ is an algebraically closed subfield of $ℂ$ and $ℱ = 𝕂 (z)$ . We will denote by $𝒮 = 𝒮_{L} \subseteq 𝕂 \cup {\infty}$ the finite set of singularities of $L$ (in the case of $\infty$ , one considers the transformation $z \mapsto z^{- 1}$ ). A Picard-Vessiot extension of $ℱ$ is a differential field $𝒦 \supseteq ℱ$ such that

PV1: $𝒦 = ℱ ⟨ h_{1}, \dots, h_{n} ⟩$ is differentially generated by $ℱ$ and a basis of solutions $𝒉 = (h_{1}, \dots, h_{n}) \in 𝒦^{n}$ to the equation $L f = 0$ .
PV2: $𝒦$ has $𝕂$ as its field of constants.

A Picard-Vessiot extension always exists: given a point $z_{0} \in 𝕂 ∖ 𝒮$ and $i \in {1, \dots, n}$ , let $h_{i}$ be the unique solution to $L f = 0$ with $h_{i}^{(j)} (z_{0}) = δ_{i, j + 1}$ for $j \in {0, \dots, n - 1}$ . We call $𝒉 = 𝒉^{z_{0}} = (h_{1}, \dots, h_{n})$ the canonical basis for the solution space of $L f = 0$ at $z_{0}$ , and regard $𝒉$ as a column vector. Taking $𝒦 = ℱ ⟨ h_{1}, \dots, h_{n} ⟩$ , the condition PV2 is trivially satisfied since $𝒉 (z_{0} + ε) \in 𝕂 [[ε]] \subseteq 𝕂 ((ε))$ and the constant field of $𝕂 ((z))$ is $𝕂$ .

Let $𝒦$ be a Picard-Vessiot extension of $ℱ$ and let $𝒉 \in 𝒦^{n}$ be as in PV1. The differential Galois group $𝒢_{𝒦 / ℱ}$ of the extension $𝒦 / ℱ$ is the group of differential automorphisms which leave $ℱ$ pointwise invariant. It is classical [Kol73] that $𝒢_{𝒦 / ℱ}$ is independent (up to isomorphism) of the particular choice of the Picard-Vessiot extension $𝒦$ .

Given an automorphism $σ \in 𝒢_{𝒦 / ℱ}$ , any solution $f$ to $L f = 0$ is sent to another solution. In particular, there exists a unique matrix $M = M_{σ, 𝒉} \in {GL}_{n} (𝕂)$ with $σ h_{i} = M h_{i} ≔ \sum_{j = 1}^{n} M_{i, j} h_{j}$ for all $i$ . This yields an embedding $ρ_{𝒉}$ of $𝒢_{𝒦 / ℱ}$ into ${GL}_{n} (𝕂)$ and we define $𝒢_{L, 𝒉} ≔ ρ_{𝒉} (𝒢_{𝒦 / ℱ})$ . Conversely, $M \in {GL}_{n} (𝕂)$ belongs to $𝒢_{L, 𝒉}$ if every differential relation $P (h_{1}, \dots, h_{n}) = 0$ satisfied by $h_{1}, \dots, h_{n}$ is also satisfied by $M h_{1}, \dots, M h_{n}$ (with $P \in 𝕂 {F_{1}, \dots, F_{n}}$ ). Since this assumption constitutes an infinite number of algebraic conditions on the coefficients of $M$ , it follows that $𝒢_{L, 𝒉}$ is a Zariski closed algebraic matrix group. Whenever $𝒈 = P 𝒉$ is another basis, we obtain the same matrix group $𝒢_{L, 𝒈} = P 𝒢_{L, 𝒉} P^{- 1}$ up to conjugation.

Assume now that $\hat{𝕂} \supseteq 𝕂$ is a larger algebraically closed subfield of $ℂ$ . Then the field $\hat{𝒦} = \hat{𝕂} (z) ⟨ h_{1}, \dots, h_{n} ⟩ = 𝒦 \otimes \hat{𝕂}$ is again a Picard-Vessiot extension of $\hat{𝕂} (z)$ . Furthermore, the Ritt-Raudenbush theorem [Rit50] implies that the perfect differential ideal of all $P \in 𝕂 {F_{1}, \dots, F_{n}}$ with $P (h_{1}, \dots, h_{n}) = 0$ is finitely generated, say by $G_{1}, \dots, G_{k}$ . But then $G_{1}, \dots, G_{k}$ is still a finite system of generators of the perfect differential ideal of all $P \in \hat{𝕂} {F_{1}, \dots, F_{n}}$ with $P (h_{1}, \dots, h_{n}) = 0$ . Consequently, ${\hat{𝒢}}_{L, 𝒈} \subseteq {GL}_{n} (\hat{𝕂})$ (i.e. as an algebraic group over $\hat{𝕂}$ ) is determined by the same algebraic equations as $𝒢_{L, 𝒈}$ . We conclude that $𝒢_{L, 𝒉} = {\hat{𝒢}}_{L, 𝒉} \cap {GL}_{n} (𝕂)$ .

Let $𝒦$ be a Picard-Vessiot extension of $ℱ$ . Any differential field $ℒ$ with $ℱ \subseteq ℒ \subseteq 𝒦$ naturally induces an algebraic subgroup $ℒ^{'} \subseteq 𝒢_{𝒦 / ℱ}$ of automorphisms of $𝒦$ which leave $ℒ$ fixed. Inversely, any algebraic subgroup $ℋ$ of $𝒢_{𝒦 / ℒ}$ gives rise to the differential field $ℋ^{'}$ with $ℱ \subseteq ℋ^{'} \subseteq 𝒦$ of all elements which are invariant under the action of $ℋ$ . We say that $ℒ$ (resp. $ℋ$ ) is closed if $ℒ = ℒ^{''}$ (resp. $ℋ^{''} = ℋ$ ). In that case, the extension $ℒ / ℱ$ is said to be normal, i.e. every element in $ℒ ∖ ℱ$ is moved by an automorphism of $ℒ$ over $ℱ$ . The main theorem from differential Galois theory states that the Galois correspondences are bijective [Kap57, Theorem 5.9].

Theorem 2. With the above notations:

The correspondences $ℒ \mapsto ℒ^{'}$ and $ℋ \mapsto ℋ^{'}$ are bijective.

The group $ℋ$ is a closed normal subgroup of $𝒢_{𝒦 / ℱ}$ if and only if the extension $ℋ^{'} / ℱ$ is normal. In that case, $𝒢_{𝒦 / ℱ} / ℋ ≅ 𝒢_{ℋ^{'} / ℱ}$ .

Corollary 3. Let $f \in ℱ ⟨ h_{1}, \dots, h_{n} ⟩$ . If $M f = f$ for all $M \in 𝒢_{L, 𝒉}$ , then $f \in ℱ$ .

2.3.Monodromy

Consider a continuous path $γ$ on $ℂ \cup {\infty} ∖ 𝒮$ from $z_{0} \in 𝕂$ to $z_{1} \in 𝕂$ . Then analytic continuation of the canonical basis $𝒉^{z_{0}}$ at $z_{0}$ along $γ$ yields a basis of solutions to $L f = 0$ at $z_{1}$ . The matrix $Δ_{γ} \in {GL}_{n} (𝕂)$ with

𝒉^{z_{1}} = Δ_{γ} 𝒉^{z_{0}}

(1)

is called the connection matrix or transition matrix along $γ$ . In particular, if $z_{1} = z_{0}$ , then we call $Δ_{γ}$ a monodromy matrix based in $z_{0}$ . We clearly have

Δ_{γ_{2} \circ γ_{1}} = Δ_{γ_{2}} Δ_{γ_{1}}

for the composition of paths, so the monodromy matrices based in $z_{0}$ form a group ${Mono}_{z_{0}}$ which is called the monodromy group. Given a path $γ$ from $z_{0}$ to $z_{1}$ , we notice that ${Mono}_{z_{1}} = Δ_{γ} {Mono}_{z_{0}} Δ_{γ}^{- 1}$ . Since any differential relation satisfied by $𝒉^{z_{0}}$ is again satisfied by its analytic continuation along $γ$ , we have ${Mono}_{z_{0}} \subseteq 𝒢_{L, 𝒉^{z_{0}}}$ and $𝒢_{L, 𝒉^{z_{1}}} = Δ_{γ} 𝒢_{L, 𝒉^{z_{0}}} Δ_{γ}^{- 1}$ .

Remark 4. The definition of transition matrices can be slightly changed depending on the purpose [vdH05b, Section 4.3.1]: when interpreting $𝒉^{z_{0}}$ and $𝒉^{z_{1}}$ as row vectors, then (1) has to be transposed. The roles of $𝒉^{z_{0}}$ and $𝒉^{z_{1}}$ may also be interchanged modulo inversion of $Δ_{γ}$ .

Now assume that $L$ admits a singularity at $0$ (if $𝒮 \neq \emptyset$ then we may reduce to this case modulo a translation; singularities at infinity may be brought back to zero using the transformation $z \to z^{- 1}$ ). It is well-known [Fab85, vH96] that $L f$ admits a computable formal basis of solutions of the form

f = (f_{0} (\sqrt[p]{z}) + \dots + f_{n - 1} (\sqrt[p]{z}) \log^{n - 1} z) z^{α} e^{P (\sqrt[p]{z})},

(2)

with $h_{0}, \dots, h_{n - 1} \in 𝕂 [[z]]$ , $p \in ℕ^{>}$ , $α \in 𝕂$ and $P \in 𝕂 [z]$ . We will denote by $𝕊$ the set of finite sums of expressions of the form (2). We may see $𝕊$ as a differential subring of a formal differential field of “complex transseries” $𝕋$ [vdH01a] with constant field $ℂ$ .

We recall that transseries in $𝕋$ are infinite linear combinations $f = \sum_{𝔪 \in 𝔗} f_{𝔪} 𝔪$ of “transmonomials” with “grid-based support”. The set $𝔗$ of transmonomials forms a totally ordered vector space for exponentiation by reals and the asymptotic ordering $≼$ . In particular, each non-zero transseries $f$ admits a unique dominant monomial $𝔡_{f}$ . It can be shown [vdH01a] that there exists a unique basis $𝒉 = (h_{1}, \dots, h_{n})$ of solutions to $L f = 0$ of the form (2), with $h_{1} ≺ \dots ≺ h_{n}$ and ${(h_{i})}_{𝔡 (h_{j})} = δ_{i, j}$ for all $i, j \in {1, \dots, n}$ . We call $𝒉^{0} = 𝒉$ the canonical basis of solutions in $0$ and there is an algorithm which computes $𝒉$ as a function of $L$ .

Let $𝕃$ be the subset of $𝕊$ of all finite sums of expressions of the form (2) with $P = 0$ . Then any $f \in 𝕊$ can uniquely be written as a finite sum $f = \sum_{𝔢 \in 𝔈} f_{𝔢} 𝔢$ , where $𝔈 = \exp (⋃_{p} ℂ [\sqrt[p]{z}])$ . Let ${Expo}_{0}$ be the group of all automorphisms $σ : 𝕊 \to 𝕊$ for which there exists a mapping $λ : 𝔈 \to 𝕂^{\neq}; 𝔢 \mapsto λ_{𝔢}$ with $σ (f) = \sum_{𝔢 \in 𝔈} λ_{𝔢} f_{𝔢} 𝔢$ for all $f \in 𝕊$ . Then every $σ \in 𝕊$ preserves differentiation and maps the Picard-Vessiot extension $𝒦 = ℱ ⟨ h_{1}, \dots, h_{n} ⟩$ of $ℱ$ into itself. In particular, the restriction ${Expo}_{0, 𝒉}$ of ${Expo}_{0}$ to $𝒦$ is a subset of $𝒢_{L, 𝒉}$ .

Proposition 5. Assume that $f \in 𝕊$ is fixed under ${Expo}_{0}$ . Then $f \in 𝕃$ .

Proof. Assume that

f \notin 𝕃

and let

𝔢 \in 𝔈

be an exponential with

f_{𝔢} \neq 0

. Let

ℋ

be a supplement of the

ℚ

-vector space

\log 𝔈

. Let

σ : 𝕊 \to 𝕊

be the mapping in

{Expo}_{0}

which sends

𝔢^{α} 𝔣

e^{α} 𝔢^{α} 𝔣

for each

α \in ℚ

and

𝔣 \in \exp ℋ

. Then we clearly have

σ (f) \neq f

□

Let $𝔢_{1}, \dots, 𝔢_{n}$ be the set of exponents corresponding to the exponents of the elements of the canonical basis $𝒉^{0}$ . Using linear algebra, we may compute a multiplicatively independent set $𝔣_{1}, \dots, 𝔣_{r} \in 𝔢_{1}^{ℚ} \dots 𝔢_{n}^{ℚ}$ such that $𝔢_{i} = 𝔣_{1}^{β_{i, 1}} \dots 𝔣_{r}^{β_{i, r}}$ for certain $β_{i, j} \in ℤ$ and all $i$ .

Proposition 6. With the above notations, the algebraic group ${Expo}_{0, 𝒉}$ is generated by the matrices $Diag (λ^{β_{i, 1}}, \dots, λ^{β_{i, n}})$ where $λ \in 𝕂^{\neq} ∖ {μ : \exists n, μ^{n} = 1}$ is chosen arbitrarily.

Proof. Let $ℰ$ be the group generated by the matrices $Diag (λ^{β_{i, 1}}, \dots, λ^{β_{i, n}})$ . Notice that each individual matrix $Diag (λ^{β_{i, 1}}, \dots, λ^{β_{i, n}})$ generates $𝒮 = {Diag (α^{β_{i, 1}}, \dots, α^{β_{i, n}}) : α \in 𝕂^{\neq}}$ : assuming $𝔢_{i} \neq 1$ , the variety $𝒮$ is irreducible of dimension $1$ and $Diag (λ^{β_{i, 1}}, \dots, λ^{β_{i, n}})$ is not contained in an algebraic group of dimension $0$ . Now any $σ \in {Expo}_{0, 𝒉}$ is a diagonal matrix $Diag (λ_{𝔢_{1}}, \dots, λ_{𝔢_{n}})$ for some multiplicative mapping $λ : 𝔈 \mapsto 𝕂^{\neq}$ . Hence

Diag (λ_{𝔢_{1}}, \dots, λ_{𝔢_{n}}) = Diag (λ_{𝔣_{1}}^{β_{1, 1}}, \dots, λ_{𝔣_{1}}^{β_{n, 1}}) \dots Diag (λ_{𝔣_{r}}^{β_{1, r}}, \dots, λ_{𝔣_{r}}^{β_{n, r}}) \in ℰ .

Conversely, each element

σ \in Diag (α_{1}^{β_{1, 1}}, \dots, α_{1}^{β_{n, 1}}) \dots Diag (α_{r}^{β_{1, r}}, \dots, α_{r}^{β_{n, r}}) \in ℰ

determines a multiplicative mapping

λ : 𝔣_{1}^{ℤ} \dots 𝔣_{r}^{ℤ} \to 𝕂^{\neq}; f_{1}^{k_{1}} \dots f_{r}^{k_{r}} \mapsto α_{1}^{k_{1}} \dots α_{r}^{k_{r}}

which may be further extended to

𝔈

using Zorn's lemma and the fact that

𝕂

is algebraically closed. It follows that

σ \in {Expo}_{0, 𝒉}

□

Assume that $2 π ⅈ \in 𝕂$ and let $M_{0} : 𝕊 \to 𝕊$ be the transformation which sends $\log z$ to $\log z + 2 π ⅈ$ , $z^{α}$ to $e^{2 π ⅈ α} z^{α}$ and $e^{P (\sqrt[p]{z})}$ to $e^{M_{0} (P (\sqrt[p]{z}))}$ . Then $σ$ preserves differentiation, so any solution to $L f = 0$ of the form (2) is sent to another solution of the same form. In particular, there exists a matrix $Δ_{↺ 0}$ with $M_{0} 𝒉 = Δ_{↺ 0} 𝒉$ , called the formal monodromy matrix around $0$ . We have $Δ_{↺ 0} \in 𝒢_{L, 𝒉}$ .

Proposition 7. Assume that $f \in 𝕊$ is fixed under ${Expo}_{0}$ and $M_{0}$ . Then $f \in 𝕂 ((z))$ .

Proof. We already know that $f \in 𝕃$ . Interpreting $f = c_{k} \log^{k} z + \dots + c_{0}$ as a polynomial in $\log z$ with $k > 0 \Rightarrow c_{k} \neq 0$ , we must have $k = 0$ since

M_{0} (f) - f = 2 π ⅈ k c_{k} \log^{k - 1} z + \dots = 0 .

Consequently, $f$ is of the form $f = \sum_{α \in 𝕂} f_{α} z^{α}$ and

M_{0} (f) = \sum_{α \in 𝕂} e^{2 π ⅈ α} f_{α} z^{α} = \sum_{α \in 𝕂} f_{α} z^{α} = f (z),

We conclude that

e^{2 π ⅈ α} = 1

for every

α \in 𝕂

with

f_{α} \neq 0

, whence

f \in ℂ ((z))

□

2.4.The process of accelero-summation

Let $ℂ [[z^{ℚ^{>}}]]$ be the differential $ℂ$ -algebra of infinitesimal Puiseux series in $z$ for $δ = z \partial$ and consider a formal power series solution $\tilde{f} \in 𝕆 = ℂ [[z^{ℚ^{>}}]] [\log z]$ to $L \tilde{f} = 0$ . The process of accelero-summation enables to associate an analytic meaning $f$ to $\tilde{f}$ in a sector near the origin of the Riemann surface $\dot{ℂ}$ of $\log$ , even in the case when $\tilde{f}$ is divergent. Schematically speaking, we obtain $f$ through a succession of transformations:

\begin{array}{rcccccccl} \tilde{f} & f \\ {\tilde{ℬ}}_{z_{1}} ↓ & ↑ ℒ_{z_{p}}^{α_{p}} \\ {\hat{f}}_{1} & ⟶_{𝒜_{z_{1} \to z_{2}}^{α_{1}}} & {\hat{f}}_{2} & ⟶ & \dots & ⟶ & {\hat{f}}_{p - 1} & ⟶_{𝒜_{z_{p - 1} \to z_{p}}^{α_{p - 1}}} & {\hat{f}}_{n} \end{array}

(3)

Each ${\hat{f}}_{i}$ is a “resurgent function” which realizes ${\tilde{f}}_{i} (z_{i}) = \tilde{f} (z)$ in the “convolution model” with respect to the $i$ -th “critical time” $z_{i} = \sqrt[k_{i}]{z}$ (with $k_{i} \in ℚ^{>}$ and $k_{1} > \dots > k_{p}$ ). In our case, ${\hat{f}}_{i}$ is an analytic function which admits only a finite number of singularities above $ℂ$ . In general, the singularities of a resurgent function are usually located on a finitely generated grid. Let us describe the transformations $\tilde{ℬ}$ , $𝒜_{z_{i} \to z_{i + 1}}^{α_{i}}$ and $ℒ_{z_{p}}^{α_{p}}$ in more detail.

The Borel transform

We start by applying the formal Borel transform to the series

{\tilde{f}}_{1} (z_{1}) = \tilde{f} (z) = \sum_{σ, r} {\tilde{f}}_{1, σ, r} z_{1}^{σ} \log^{r} z_{1} \in ℂ [[z_{1}^{ℚ^{>}}]] [\log z_{1}]

. This transformation sends each

z_{1}^{σ} \log^{r} z_{1}

({\tilde{ℬ}}_{z_{1}} z_{1}^{σ} \log^{r} z_{1}) (ζ_{1}) = ζ_{1}^{σ - 1} \sum_{i = 0}^{r} (\begin{array}{c} k \\ i \end{array}) γ^{(r - i)} (σ) \log^{i} ζ_{1},

where $γ (σ) = 1 / Γ (σ)$ , and extends by strong linearity:

{\hat{f}}_{1} (ζ_{1}) = ({\tilde{ℬ}}_{z_{1}} {\tilde{f}}_{1}) (ζ_{1}) = \sum_{\begin{array}{c} σ \in ℚ^{>} \\ r \in ℕ \end{array}} {\tilde{f}}_{1, r, σ} ({\tilde{ℬ}}_{z_{1}} z_{1}^{σ} \log^{r} z_{1}) (ζ_{1}),

The result is a formal series ${\hat{f}}_{1} \in ζ_{1}^{- 1} ℂ [[ζ_{1}^{ℚ^{>}}]] [\log ζ_{1}]$ in $ζ_{1}$ which converges near the origin of $\dot{ℂ}$ . The formal Borel transform is a morphism of differential algebras which sends multiplication to the convolution product, i.e. ${\tilde{ℬ}}_{z_{1}} (f g) = ({\tilde{ℬ}}_{z_{1}} f) * ({\tilde{ℬ}}_{z_{1}} g)$ .

Accelerations

Given

i < p

, the function

{\hat{f}}_{i}

is defined near the origin of

\dot{ℂ}

, can be analytically continued on the axis

e^{α_{i} ⅈ} ℝ^{>} \subseteq \dot{ℂ}

, and admits a growth of the form

{\hat{f}}_{i} (ζ_{i}) = \exp O (| ζ_{i} |^{k_{i} / (k_{i} - k_{i + 1})})

at infinity. The next function

{\hat{f}}_{i + 1}

is obtained from

{\hat{f}}_{i}

by an acceleration of the form

{\hat{f}}_{i + 1} (ζ_{i + 1}) = (𝒜_{z_{i} \to z_{i + 1}}^{α_{i}} {\hat{f}}_{i}) (ζ_{i + 1}) = \int_{ζ_{i} \in e^{α_{i} ⅈ} ℝ^{>}} K_{k_{i}, k_{i + 1}} (ζ_{i}, ζ_{i + 1}) {\hat{f}}_{i} (ζ_{i}) ⅆ ζ_{i},

where the acceleration kernel $K_{k_{i}, k_{i + 1}}$ is given by

\begin{array}{rcl} K_{k_{i}, k_{i + 1}} (ζ_{i}, ζ_{i + 1}) & = & \frac{1}{ζ_{i + 1}} K_{k_{i + 1} / k_{i}} (\frac{ζ_{i}}{ζ_{i + 1}^{k_{i + 1} / k_{i}}}) \\ K_{λ} (ζ) & = & \frac{1}{2 π ⅈ} \int_{c - \infty ⅈ}^{c + \infty ⅈ} e^{z - ζ z^{λ}} ⅆ z . (4) \end{array}

For large $ζ$ on an axis with $| \arg ζ | < (1 - λ) π / 2$ , it can be shown that $K_{λ} (ζ) ⩽ \exp (- C | ζ |^{1 / (1 - λ)})$ for some constant $C > 0$ . Assuming that $α_{i + 1}$ satisfies

| k_{i + 1} α_{i + 1} - k_{i} α_{i} | < (k_{i} - k_{i + 1}) π / 2,

(5)

it follows that the acceleration ${\hat{f}}_{i + 1}$ of ${\hat{f}}_{i}$ is well-defined for small $ζ_{i + 1}$ on $e^{α_{i + 1}} ℝ^{>}$ . The set $𝒟_{i} \subseteq ℝ$ of directions $α$ such ${\hat{f}}_{i}$ admits a singularity on $e^{α ⅈ} ℝ^{>}$ is called the set of Stokes directions. Accelerations are morphisms of differential $ℂ$ -algebras which preserve the convolution product.

The Laplace transform

The last function

{\hat{f}}_{p}

is defined near the origin of

\dot{ℂ}

, can be analytically continued on the axis

e^{α_{i} ⅈ} ℝ^{>} \subseteq \dot{ℂ}

and admits at most exponential growth at infinity. The function

f

is now obtained using the analytic Laplace transform

f (z) = f_{p} (z_{p}) = (ℒ_{z_{p}}^{α_{p}} {\hat{f}}_{p}) (z_{p}) = \int_{ζ_{p} \in e^{α_{p} ⅈ} ℝ^{>}} {\hat{f}}_{p} (ζ_{p}) e^{- ζ_{p} / z_{p}} ⅆ ζ_{p} .

On an axis with

| \arg z_{p} - α_{p} | < π / 2,

(6)

the function $f_{p}$ is defined for all sufficiently small $z_{p}$ . The set $𝒟_{p}$ of Stokes directions is defined in a similar way as in the case of accelerations. The Laplace transform is a morphism of differential $ℂ$ -algebras which is inverse to the Borel transform and sends the convolution product to multiplication.

Remark 8. Intuitively speaking, one has $𝒜_{z_{i} \to z_{i + 1}}^{α_{i}} = ℬ_{z_{i + 1}} \circ ℒ_{z_{i}}^{α_{i}}$ .

Given critical times $k_{1} > \dots > k_{p}$ in $ℚ^{>}$ and directions $α_{1}, \dots, α_{p}$ satisfying (5), we say that a formal power series $\tilde{f} \in \tilde{𝕆}$ is accelero-summable in the multi-direction $𝛂 = (α_{1}, \dots, α_{p})$ if the above scheme yields an analytic function $f (z)$ near the origin of any axis on $\dot{ℂ}$ satisfying (6). We denote the set of such power series by $𝕆_{𝒌, 𝛂}$ , where $𝒌 = (k_{1}, \dots, k_{p})$ . Inversely, given $\tilde{f} \in 𝕆$ , we denote by ${dom}_{as} \tilde{f}$ the set of all triples $γ = (𝒌, 𝛂, z)$ such that $\tilde{f} \in 𝕆_{𝒌, 𝛂}$ and so that $f (z)$ is well-defined. In that case, we write $f = {sum}_{𝒌, 𝛂}$ and $f (z) = \tilde{f} (γ)$ .

The set $𝕆_{𝒌, 𝛂}$ forms a differential subring of $𝕆$ and the map $\tilde{f} \mapsto f$ for $\tilde{f} \in 𝕆_{𝒌, 𝛂}$ is injective. If $𝒌^{'}$ and $𝛂^{'}$ are obtained from $𝒌$ and $𝛂$ by inserting a new critical time and an arbitrary direction, then we have $𝕆_{𝒌, 𝛂} ⊊︀ 𝕆_{𝒌^{'}, 𝛂^{'}}$ . In particular, $𝕆_{𝒌, 𝛂}$ contains $𝕆_{cv} = ℂ {{z^{ℚ^{>}}}} [\log z]$ , where $ℂ {{z^{ℚ^{>}}}}$ denotes the ring of convergent infinitesimal Puiseux series. Let $ℛ_{1} = ℝ ∖ 𝒟_{1} \subseteq ℝ, \dots, ℛ_{p} = ℝ ∖ 𝒟_{p} \subseteq ℝ$ be sets of directions such that each $𝒟_{i}$ is finite modulo $2 π$ . Let $𝓡$ be the subset of $ℛ_{1} \times \dots \times ℛ_{p}$ of multi-directions $𝛂$ which verify (5). We denote $𝕆_{𝒌, 𝓡} = ⋂_{𝛂 \in 𝓡} 𝕆_{𝒌, 𝛂}$ , $𝕆_{𝒌} = ⋃_{𝓡} 𝕆_{𝒌, 𝓡}$ and $𝕆_{as} = ⋃_{𝒌} 𝕆_{𝒌}$ .

Taking $𝕂 = ℂ$ , the notion of accelero-summation extends to formal expressions of the form (2) and more general elements of $𝕊$ as follows. Given $\tilde{g} \in 𝕆_{𝒌, 𝛂}$ , $σ \in ℂ$ , $𝔢 = e^{P (\sqrt[p]{z})} \in 𝔈$ and $γ = (𝒌, 𝛂, z) \in {dom}_{as} \tilde{g}$ , we simply define $(\tilde{g} z^{σ} 𝔢) (γ) = \tilde{g} (γ) z^{σ} e^{P (\sqrt[p]{z})}$ . It can be checked that this definition is coherent when replacing $\tilde{g} z^{σ}$ by $(z^{k} \tilde{g}) z^{σ - k}$ for some $k \in ℚ$ . By linearity, we thus obtain a natural differential subalgebra $𝕊_{𝒌, 𝛂} \subseteq 𝕊$ of accelero-summable transseries with critical times $𝒌$ and in the multi-direction $𝛂$ . We also have natural analogues $𝕊_{𝒌}$ and $𝕊_{as}$ of $𝕆_{𝒌}$ and $𝕆_{as}$ .

The main result we need from the theory of accelero-summation is the following theorem [É87, Bra91].

Theorem 9. Let $\tilde{f} \in 𝕆$ be a formal solution to $L \tilde{f} = 0$ . Then $\tilde{f} \in 𝕆_{as}$ .

Corollary 10. Let $𝒉^{0} \in 𝕊^{n}$ be the canonical basis of formal solutions to $L \tilde{f} = 0$ at the origin. We have $𝒉^{0} \in 𝕊_{as}^{n}$ .

Proof. Holonomy is preserved under multiplication with elements of

z^{ℂ} 𝔈

□

Remark 11. We have aimed to keep our survey of the accelero-summation process as brief as possible. It is more elegant to develop this theory using resurgent functions and resurgence monomials [É85, CNP93].

2.5.The Stokes phenomenon

We say that $\tilde{f} \in 𝕊_{𝒌, 𝓡}$ is stable under Stokes morphisms is for all $𝛂, 𝛃 \in 𝓡$ , there exists a $\tilde{g} \in 𝕊_{𝒌, 𝓡}$ with ${sum}_{𝒌, 𝛂} \tilde{f} = {sum}_{𝒌, 𝛃} \tilde{g}$ , and if the same property is recursively satisfied by $\tilde{g}$ . We denote by ${\overset{˘}{𝕊}}_{𝒌, 𝓡}$ the differential subring of $𝕊_{𝒌, 𝓡}$ which is stable under Stokes morphisms. The mappings $Σ_{𝒌, 𝛂, 𝛃} : \tilde{f} \mapsto {sum}_{𝒌, 𝛃}^{- 1} {sum}_{𝒌, 𝛂} \tilde{f}$ will be called Stokes morphisms and we denote by ${Sto}_{0, 𝒌, 𝓡}$ the group of all such maps.

Proposition 12. Assume that $\tilde{f} \in 𝕊_{𝒌, 𝓡}$ is fixed under ${Sto}_{0, 𝒌, 𝓡}$ . Then $\tilde{f}$ is convergent.

Proof. Assume that one of the ${\hat{f}}_{i}$ admits a singularity at $ω = ρ e^{θ ⅈ} \neq 0$ and choose $i$ maximal and $ρ$ minimal. Modulo the removal of unnecessary critical times, we may assume without loss of generality that $i = p$ . Let $𝛂$ with $α_{p} = θ$ be a multi-direction satisfying (5), such that $α_{i} \in ℛ_{i}$ for all $i < p$ . Then

\begin{array}{rcl} 𝛂^{<} & = & (α_{1}, \dots, α_{p - 1}, α_{p} - ε) \in 𝓡 \\ 𝛂^{>} & = & (α_{1}, \dots, α_{p - 1}, α_{p} + ε) \in 𝓡 \end{array}

for all sufficiently small

ε > 0

. Now

g_{p} = ℒ_{z_{p}}^{θ + ε} {\hat{f}}_{p} - ℒ_{z_{p}}^{θ - ε} {\hat{f}}_{p}

is obtained by integration around

ω

along the axis

e^{θ ⅈ} ℝ^{>}

. By classical properties of the Laplace integral [CNP93, Pré I.2], the function

g_{p}

cannot vanish, since

{\hat{f}}_{i}

admits a singularity in

ω

(if the Laplace integrals corresponding to both directions

θ \pm ε

coincide, then the Laplace transform can be analytically continued to a larger sector, which is only possible if

{\hat{f}}_{i}

is analytic in a sector which contains both directions

θ \pm ε

). We conclude that

g (z) = g_{p} (z_{p}) = ({sum}_{𝒌, 𝛂^{>}} - {sum}_{𝒌, 𝛂^{<}}) (\tilde{f}) \neq 0

, so

f

is not fixed under

{Sto}_{0, 𝒌, 𝓡}

□

Remark 13. Let $𝓓$ be a set of multi-directions $𝛂$ satisfying (5), with $α_{i} \in 𝒟_{i}$ for exactly one $i$ , and so that for all $j \neq i$ , we have either $α_{j} = k_{i} α_{i} / k_{j}$ or $k_{i} α_{i} / k_{j} \in 𝒟_{j}$ and $α_{j} = k_{i} (α_{i} \pm ε) / k_{j}$ for some small $ε > 0$ . For every $𝛂 \in 𝓓$ , we have

\begin{array}{rcl} 𝛂^{<} & = & (α_{1}, \dots, α_{i - 1}, α_{i} - ε, α_{i + 1}, \dots, α_{p}) \in 𝓡 \\ 𝛂^{>} & = & (α_{1}, \dots, α_{i - 1}, α_{i} + ε, α_{i + 1}, \dots, α_{p}) \in 𝓡 . \end{array}

By looking more carefully at the proof of proposition 12, we observe that it suffices to assume that $\tilde{f}$ is fixed under all Stokes morphisms of the form $Σ_{𝒌, 𝛂^{<}, 𝛂^{>}}$ , instead of all elements in ${Sto}_{0, 𝒌, 𝓡}$ .

We say that $𝛂, 𝛃 \in 𝓓$ are equivalent, if $α_{i} - β_{i} \in 2 π ⅈ q_{i}$ for all $i$ , where $q_{i}$ is the denominator of $k_{i}$ . We notice that $𝓓$ is finite modulo this equivalent relation. We denote by $𝓓^{gen}$ a subset of $𝓓$ with one element in each equivalence class.

Let us now come back to our differential equation $L f = 0$ . Given $γ = (𝒌, 𝛂, z) \in {dom}_{as} 𝒉^{0} ≔ {dom}_{as} h_{1}^{0} \cap \dots \cap {dom}_{as} h_{n}^{0}$ , the map ${sum}_{𝒌, 𝛂}$ induces an isomorphism between $Vect (𝒉^{0})$ and $Vect (𝒉^{z})$ . We denote by $Δ_{γ} \in {GL}_{n} (ℂ)$ the unique matrix with $𝒉^{z} = Δ_{γ} {sum}_{𝒌, 𝛂} 𝒉^{0}$ . Given a second $γ^{'} = (𝒌, 𝛂^{'}, z) \in {dom}_{as} 𝒉^{0}$ , the vector ${sum}_{𝒌, 𝛂^{'}}^{- 1} {sum}_{𝒌, 𝛂} 𝒉^{0}$ is again in $𝕊_{𝒌, 𝓡}^{n}$ , whence $𝒉^{0} \in {\overset{˘}{𝕊}}_{𝒌, 𝓡}$ by repeating the argument. In particular, the Stokes morphism $Σ_{𝒌, 𝛂, 𝛂^{'}}$ induces the Stokes matrix $Δ_{(0, 𝒌, 𝛂 \to 𝛂^{'})} = Δ_{γ^{'}}^{- 1} Δ_{γ}$ .

We are now in the position that we can construct a finite set $ℳ$ of generators for the Galois group $𝒢_{L, 𝒉^{z_{0}}}$ in a regular point $z_{0} \in ℂ \cup {? \infty} ∖ 𝒮$ .

Algorithm Compute_generators $(L, z_{0})$

Input: an operator $L \in ℱ {[\partial]}^{\neq}$ and a regular point $z_{0} \in ℂ \cup {? \infty} ∖ 𝒮$

Output: a set $ℳ$ of generators for $𝒢_{L, 𝒉^{z_{0}}}$

$ℳ ≔ \emptyset$

for each $z_{i} \in 𝒮$ do

Reduce to the case when $z_{i} = 0$ modulo a suitable transformation of the form $z \mapsto z + c$ or $z \mapsto z^{- 1}$ .
Let $γ_{i}$ be an arbitrary path $(𝒌, 𝛂, u_{i}) \in {dom}_{as} 𝒉^{z_{i}}$ from $z_{i}$ to a point $u_{i}$ nearby $z_{i}$ , composed with an arbitrary path from $u_{i}$ to $z_{0}$ on $ℂ \cup {? \infty} ∖ 𝒮$ .
Compute a finite set of generators $𝒳_{i}$ for ${Expo}_{z_{i}, 𝒉^{z_{i}}}$ using proposition 6 and add $Δ_{γ_{i}} Χ Δ_{γ_{i}}^{- 1}$ to $ℳ$ for all $Χ \in 𝒳_{i}$ .
Add $Δ_{γ_{i}} Δ_{↺ z_{i}} Δ_{γ_{i}}^{- 1}$ to $ℳ$ .
For each $𝛂 \in 𝓓^{gen}$ with $𝓓^{gen}$ as in remark 13, add $Δ_{γ_{i}} Δ_{(z_{i}, 𝒌, 𝛂^{<} \to 𝛂^{>})} Δ_{γ_{i}}^{- 1}$ to $ℳ$ .

return $ℳ$

Theorem 14. With $ℳ$ constructed as above, the differential Galois group $𝒢_{L, 𝒉^{z_{0}}}$ is generated by $ℳ$ as a closed algebraic subgroup of ${Mat}_{n} (ℂ)$ .

Proof. Assume that

f \in ℱ ⟨ h_{1}^{z_{0}}, \dots, h_{n}^{z_{0}} ⟩

is fixed by each element of

ℳ

. We have to prove that

f \in ℱ

. Given a singularity

z_{i}

, let

\tilde{g}

be the “continuation” of

f

along

γ_{i}^{- 1}

(which involves analytic continuation until

u_{i}

followed by “decelero-unsummation”). By proposition 7, we have

\tilde{g} \in ℂ ((z))

. From proposition 12 and remark 13, we next deduce that

\tilde{g}

is convergent. Indeed, since

\tilde{g} \in ℂ ((z))

, its realization

{\hat{g}}_{i}

in the convolution model with critical time

z_{i} = z^{1 / k_{i}} = z^{q_{i} / p_{i}}

is a function in

\sqrt[q_{i}]{ζ_{i}}

. Consequently,

Σ_{𝒌, 𝛂^{<}, 𝛂^{>}} = Σ_{𝒌, 𝛃^{<}, 𝛃^{>}}

whenever

𝛂

and

𝛃

are equivalent. At this point we have shown that

f

is meromorphic at

z_{i}

. But a function which is meromorphic at all points of the Riemann sphere

ℂ \cup {? \infty}

is actually a rational function. It follows that

f \in ℱ

□

Remark 15. Slightly less effective versions of theorem 14 are due to Ramis [Ram85, MR91]. Both papers crucially use previous work by Écalle and we followed a similar approach as in the second paper. In the Fuchsian case, i.e. in absence of divergence, the result is due to Schlesinger [Sch95, Sch97].

Remark 16. We have tried to keep our exposition as short as possible by considering only “directional Stokes-morphisms”. In fact, Écalle's theory of resurgent functions gives a more fine-grained control over what happens in the convolution model by considering the pointed alien derivatives ${\dot{Δ}}_{ω}$ for $ω \in \dot{ℂ}$ . Modulo the identification of functions in the formal model, the convolution models and the geometric model via accelero-summation, the pointed alien derivatives commute with the usual derivation $\partial$ . Consequently, if $f$ is a solution to $L f = 0$ , then we also have $L {\dot{Δ}}_{ω} f = 0$ . In particular, given the canonical basis of solutions $𝒉^{0}$ to $L f = 0$ , there exists a unique matrix $B_{ω}$ with

{\dot{Δ}}_{ω} 𝒉^{0} = B_{ω} 𝒉^{0} .

This equation is called the bridge equation. Since ${\hat{f}}_{i}$ admits only a finite number of singularities and the alien derivations “translate singularities”, we have ${\dot{Δ}}_{ω}^{l} 𝒉^{0} = 0$ for some $l$ , so the matrices $B_{ω}$ are nilpotent. More generally, if $ω_{1}, \dots, ω_{r} \in ℂ^{\neq}$ are $ℕ$ -linearly independent, then all elements in the algebra generated by $B_{ω_{1}}, \dots, B_{ω_{r}}$ are nilpotent.

It is easily shown that the Stokes morphisms correspond to the exponentials $e^{{\dot{Δ}}_{θ}}$ of directional Alien derivations ${\dot{Δ}}_{θ} = \sum_{ω \in e^{θ ⅈ} ℝ^{>}} {\dot{Δ}}_{ω}$ . This yields a way to reinterpret the Stokes matrices in terms of the $B_{ω}$ with $ω \in e^{θ ⅈ} ℝ^{>}$ . In particular, the preceding discussion implies that the Stokes matrices are unipotent. The extra flexibility provided by pointwise over directional alien derivatives admits many applications, such as the preservation of realness [Men96]. For further details, see [É85, É87, É92, É93].

2.6.Effective complex numbers

A complex number $z$ is said to be effective if there exists an approximation algorithm for $z$ which takes $ε \in ℕ^{>} 2^{ℤ}$ on input and which returns an $ε$ -approximation $\tilde{z} \in (ℤ + ⅈ ℤ) 2^{ℤ}$ of $z$ for which $| \tilde{z} - z | < ε$ . The time complexity of this approximation algorithm is the time $T (d)$ it takes to compute a $2^{- d}$ -approximation for $z$ . It is not hard to show that the set $ℂ^{eff}$ of effective complex numbers forms a field. However, given $z \in ℂ^{eff}$ the question whether $z = 0$ is undecidable. The following theorems were proved in [CC90, vdH99, vdH01b].

Theorem 17. Let $L \in ℚ^{alg} (z) [\partial]$ , $z_{0} \in ℚ^{alg} ∖ 𝒮$ , $𝒗 \in {(ℚ^{alg})}^{n}$ and $f = 𝒗 \cdot 𝒉^{z_{0}}$ . Given a broken line path $γ = z_{0} \to \dots \to z_{k}$ on $ℂ^{eff} ∖ 𝒮$ , we have

The value $f (γ)$ of the analytic continuation of $f$ at the end-point of $γ$ is effective.

There exists an approximation algorithm of time complexity $O (d \log^{3} d \log^{2} \log d)$ for $f (γ)$ , when not counting the approximation time of the input data $L$ , $γ$ and $𝒗$ .

There exists an algorithm which computes an approximation algorithm for $f (γ)$ as in (b) as a function of $L$ , $γ$ and $𝒗$ .

Theorem 18. Let $L \in ℚ^{alg} (z) [\partial]$ be regular singular in $0$ . Let $z_{0} \in ℚ^{alg} ∖ 𝒮$ , $𝒗 \in {(ℚ^{alg})}^{n}$ and $f = 𝒗 \cdot 𝒉^{z_{0}}$ . Then $f (z)$ is well-defined for all sufficiently small $γ$ on the effective Riemann surface ${\dot{ℂ}}^{eff}$ of $\log$ above $ℂ^{eff}$ , and

$f (γ)$ is effective.

There exists an approximation algorithm of time complexity $O (d \log^{3} d \log^{2} \log d)$ for $f (γ)$ , when not counting the approximation time of the input data $L$ , $γ$ and $𝒗$ .

There exists an algorithm which computes an approximation algorithm for $f (γ)$ as in (b) as a function of $L$ , $γ$ and $𝒗$ .

In general, the approximation of $f (γ)$ involves the existence of certain bounds. In each of the above theorems, the assertion (c) essentially states that there exists an algorithm for computing these bounds as a function of the input data. This property does not merely follow from (a) and (b) alone.

The following theorem has been proved in [vdH05b].

Theorem 19. Let $L \in ℚ^{alg} (z) [\partial]$ be singular in $0$ . Let $𝒌$ be as in theorem 10 and $Γ = {(𝒌, 𝛂, z) \in {dom}_{as} 𝒉^{0} : α_{1}, \dots, α_{p}, z \in ℂ^{eff}}$ . Given $f = 𝒗 \cdot 𝒉^{0}$ with $𝒗 \in {(ℂ^{eff})}^{n}$ and $γ \in Γ$ , we have

$f (γ)$ is effective.

There exists an approximation algorithm of time complexity $O (d \log^{4} d \log \log d)$ for $f (γ)$ , when not counting the approximation time of the input data $L$ , $γ$ and $𝒗$ .

There exists an algorithm which computes an approximation algorithm for $f (γ)$ as in (b) as a function of $L$ , $γ$ and $𝒗$ .

If we replace $ℚ^{alg}$ by an arbitrary effective algebraically closed subfield $𝕂$ of $ℂ^{eff}$ , then the assertions (a) and (c) in the three above theorems remain valid (see [vdH05a, vdH03] in the cases of theorems 17 and 18), but the complexity in (b) usually drops back to $O (d^{2} \log^{O (1)} d)$ . Notice also that we may replace $f (γ)$ by the transition matrix along $γ$ in each of the theorems. The following theorem summarizes the results from section 2.

Theorem 20. Let $𝕂$ be an effective algebraically closed constant field of $ℂ^{eff}$ . Then there exists an algorithm which takes $L \in 𝕂 (z) [\partial]$ and $z_{0} \in 𝕂 \cup {\infty}$ on input, and which computes a finite set $ℳ \subseteq Mat (ℂ^{eff})$ , such that

The group $𝒢_{L, 𝒉^{z_{0}}}$ is generated by $ℳ$ as a closed algebraic subgroup of ${Mat}_{n} (ℂ)$ .

If $𝕂 = ℚ^{alg}$ , then the entries of the matrices in $ℳ$ have time complexity $O (d \log^{4} d \log \log d)$ .

Proof. It is classical that the set

ℂ^{eff}

of effective complex numbers forms a field. Similarly, the set

ℂ^{fast}

of effective complex numbers with an approximation algorithm of time complexity

O (d \log^{4} d \log \log d)

forms a field, since the operations

+

-

\times

and

/

can all be performed in time

O (d \log d \log \log d)

. In particular, the classes of matrices with entries in

ℂ^{eff}

resp.

ℂ^{fast}

are stable under the same operations. Now in the algorithm Compute_generators, we may take broken-line paths with vertices above

𝕂

for the

γ_{i}

. Hence (a) and (b) follow from theorem 19(a) resp. (b) and the above observations.

□

Given $ε \in ℕ^{>} 2^{ℤ}$ , we may endow $ℂ^{eff}$ with an approximate zero-test for which $z = 0$ if and only if $| z | < ε$ . We will denote this field by $ℂ^{\approx ε}$ . Clearly, this zero-test is not compatible with the field structure of $ℂ^{eff}$ . Nevertheless, any finite computation, which can be carried out in $ℂ^{eff}$ with an oracle for zero-testing, can be carried out in exactly the same way in $ℂ^{\approx ε}$ for a sufficiently small $ε$ . Given $z \in ℂ^{eff}$ , we will denote by $z^{\approx ε} \in ℂ^{\approx ε}$ the “cast” of $z$ to $ℂ^{\approx ε}$ and similarly for matrices with coefficients in $ℂ^{eff}$ .

Remark 21. In practice [vdH04], effective complex numbers $z$ usually come with a natural bound $M \in ℕ^{>} 2^{ℤ}$ for $| z |$ . Then, given $ε \in ℕ^{>} 2^{ℤ}$ with $ε < 1$ , it is even better to use the approximate zero-test $z = 0$ if and only if $| z | < ε M$ . Notice that the bound $M$ usually depends on the internal representation of $z$ and not merely on $z$ as a number in $ℂ^{eff}$ .

3.Factoring linear differential operators

Let $𝕂$ be an effective algebraically closed subfield of $ℂ^{eff}$ . Consider a monic linear differential operator $L = \partial^{n} + L_{n - 1} \partial + \dots + L_{0} \in ℱ [\partial]$ , where $ℱ = 𝕂 (z)$ . In this section, we present an algorithm for finding a non-trivial factorization $L = K_{1} K_{2}$ with $K_{1}, K_{2} \in ℱ [\partial]$ whenever such a factorization exists.

3.1.Factoring $L$ and invariant subspaces under $𝒢_{L, 𝒉}$

Let $𝒉 = (h_{1}, \dots, h_{n}) \in 𝒦^{n}$ be a basis of solutions for the equation $L f = 0$ , where $𝒦 \supseteq ℱ$ is an abstract differential field. We denote the Wronskian of $𝒉$ by

W_{𝒉} = W_{h_{1}, \dots, h_{n}} = | \begin{array}{ccc} h_{1} & \dots & h_{n} \\ ⋮ & ⋮ \\ h_{1}^{(n - 1)} & \dots & h_{n}^{(n - 1)} \end{array} | .

It is classical (and easy to check) that

L f = \frac{W_{f, h_{1}, \dots, h_{n}}}{W_{h_{1}, \dots, h_{n}}} .

(7)

When expanding the determinant $W_{f, h_{1}, \dots, h_{n}}$ in terms of the matrices

W_{i} = W_{𝒉, i} = | \begin{array}{ccc} h_{1} & \dots & h_{n} \\ ⋮ & ⋮ \\ h_{1}^{(n - i - 1)} & \dots & h_{n}^{(n - i - 1)} \\ h_{1}^{(n - i + 1)} & \dots & h_{n}^{(n - i + 1)} \\ ⋮ & ⋮ \\ h_{1}^{(n - 1)} & \dots & h_{n}^{(n - 1)} \end{array} |,

it follows that

L = \partial^{n} - \frac{W_{1}}{W_{0}} \partial^{n - 1} + \dots + {(- 1)}^{n} \frac{W_{n}}{W_{0}} .

Denoting by $φ^{†}$ the logarithmic derivative of $φ$ , it can also be checked by induction that

\tilde{L} = (\partial - {(\frac{W_{h_{1}, \dots, h_{n}}}{W_{h_{1}, \dots, h_{n - 1}}})}^{†}) \dots (\partial - {(\frac{W_{h_{1}, h_{2}}}{W_{h_{1}}})}^{†}) (\partial - W_{h_{1}}^{†})

admits $h_{1}, \dots, h_{n}$ as solutions, whence $\tilde{L} = L$ , using Euclidean division in the skew polynomial ring $ℱ [\partial]$ .

Proposition 22.

If $L$ admits a factorization $L = K_{1} K_{2}$ , then $𝒢_{L, 𝒉}$ leaves $\ker K_{2}$ invariant.

If $V$ is an invariant subvector space of $𝒢_{L, 𝒉}$ , then $L$ admits a factorization $L = K_{1} K_{2}$ with $V = \ker K_{2}$ .

Proof. Assume that $L$ admits a factorization $L = K_{1} K_{2}$ . Then, given $f \in \ker K_{2}$ and $M \in 𝒢_{L, 𝒉}$ , we have $K_{2} f = 0 = M K_{2} f = K_{2} M f$ , whence $M f \in \ker K_{2}$ . Conversely, assume that $V$ is an invariant subvector space of $𝒢_{L, 𝒉}$ and let $𝒈$ be a basis of $V$ . Then we observe that $M W_{𝒈, i} = (\det M) W_{𝒈, i}$ for all $i$ . Consequently,

M \frac{W_{𝒈, i}}{W_{𝒈, 0}} = \frac{W_{𝒈, i}}{W_{𝒈, 0}}

for all $i$ , so that $W_{𝒈, i} / W_{𝒈, 0} \in ℱ$ , by corollary 3. Hence

K_{2} = \partial^{r} - \frac{W_{𝒈, 1}}{W_{𝒈, 0}} \partial^{r - 1} + \dots + {(- 1)}^{r} \frac{W_{𝒈, r}}{W_{𝒈, 0}}

(8)

is a differential operator with coefficients in

ℱ

which vanishes on

V

. But this is only possible if

K_{2}

divides

L

□

3.2.A lemma from linear algebra

Lemma 23. Let $𝒜$ be a non-unitary algebra of nilpotent matrices in ${Mat}_{n} (𝕂)$ . Then there exists a basis of $𝕂^{n}$ in which $M$ is lower triangular for all $M \in 𝒜$ .

Proof. Let $M \in 𝒜$ be a matrix such that $V = im M$ is a non-zero vector space of minimal dimension. Given $𝒗 \in V$ and $N \in 𝒜$ , we claim that $N 𝒗 \in \ker M$ . Assume the contrary, so that $0 \neq M N 𝒗 \in im M N \subseteq V$ . By the minimality hypothesis, we must have $im M N = V$ . In particular, $𝒗 \in im M N$ and $0 \neq M N 𝒗 \in im M N M N$ . Again by the minimality hypothesis, it follows that $im M N M N = V$ . In other words, the restriction of $M N$ to $V$ is an isomorphism on $V$ . Hence $M N$ admits a non-zero eigenvector in $V$ , which contradicts the fact that $M N$ is nilpotent.

Let us now prove the lemma by induction over

n

. If

n ⩽ 1

𝒜 = 0

, then we have nothing to do, so assume that

n > 1

and

𝒜 \neq 0

. We claim that

𝕂^{n}

admits a non-trivial invariant subvector space

W

. Indeed, we may take

W = V

𝒜 V = 0

and

W = 𝒜 V

𝒜 V \neq 0

. Now consider a basis

(𝒃_{m + 1}, \dots, 𝒃_{n})

W

and complete it to a basis

(𝒃_{1}, \dots, 𝒃_{n})

𝕂^{n}

. Then each matrix in

𝒜

is lower triangular with respect to this basis. Let

𝒜_{1}

and

𝒜_{2}

be the algebras of lower dimensional matrices which occur as upper left resp. lower right blocks of matrices in

𝒜

. We conclude by applying the induction hypothesis on

𝒜_{1}

and

𝒜_{2}

□

Let $ℳ$ be a finite set of non-zero nilpotent matrices. If all matrices in the $𝕂$ -algebra $𝒜$ generated by $ℳ$ are nilpotent, then it is easy to compute a basis for which all matrices in $ℳ$ are lower triangular. Indeed, setting $K_{i} = ⋂_{M \in ℳ^{i}} \ker M$ for all $i$ , we first compute a basis of $K_{1}$ . We successively complete this basis into a basis of $K_{2}$ , $K_{3}$ and so on until $K_{p} = 𝕂^{n}$ .

If not all matrices in $𝒜$ are nilpotent, then the proof of lemma 23 indicates a method for the computation of a matrix in $𝒜$ which is not nilpotent. Indeed, we start by picking an $M \in ℳ$ and set $V ≔ im M^{p - 1}$ , where $p$ is smallest with $M^{p} = 0$ . We next set $𝒩 ≔ ℳ ∖ {M}$ and iterate the following loop. Take a matrix $N \in 𝒩$ and distinguish the following three cases:

$M N V = 0$: Set $𝒩 ≔ 𝒩 ∖ {N}$ and continue.
$0 ⊊︀ M N V ⊊︀ V$: Set $M ≔ M N M$ , $V ≔ im M$ and continue.
$M N V = V$: Return the non-nilpotent matrix $M N$ .

At the end of our loop, we either found a non-nilpotent matrix, or we have $N V \subseteq \ker M$ for all $N \in ℳ$ . In the second case, we obtain a non-trivial invariant subspace of $𝕂^{n}$ as in the proof of lemma 23 and we recursively apply the algorithm on this subspace and a complement. In fact, the returned matrix is not even monopotent (i.e. not of the form $λ + N$ , where $N$ is a nilpotent matrix), since it both admits zero and a non-zero number as eigenvalues.

3.3.Computation of non-trivial invariant subspaces

Proposition 22 in combination with theorem 20 implies that the factorization of linear differential operators in $ℱ [\partial]$ reduces to the computation of non-trivial invariant subvector spaces under the action of $ℳ_{L, 𝒉}$ whenever they exist.

In this section, we will first solve a slightly simpler problem: assuming that $𝕂$ is an effective algebraically closed field and given a finite set of matrices $ℳ \subseteq {Mat}_{n} (𝕂)$ , we will show how to compute a non-trivial invariant subspace $V$ of $𝕂^{n}$ under the action of $ℳ$ , whenever such a $V$ exists.

Good candidate vectors $𝒗$

Given a vector

𝒗 \in 𝕂^{n}

it is easy to compute the smallest subspace

{Inv}_{ℳ} (𝒗)

𝕂^{n}

which is invariant under the action of

ℳ

and which contains

𝒗

. Indeed, starting with a basis

ℬ = {𝒗}

, we keep enlarging

ℬ

with elements in

ℳ ℬ ∖ Vect (ℬ)

until saturation. Since

ℬ

will never contain more than

n

elements, this algorithm terminates. A candidate vector

𝒗 \in 𝕂^{n}

for generating a non-trivial invariant subspace of

𝕂^{n}

is said to be good if

0 < \dim {Inv}_{ℳ} (𝒗) < n

The $𝕂$ -algebra generated by $ℳ$

We notice that

V \subseteq 𝕂^{n}

is an invariant subspace for

ℳ

, if and only if

V

is an invariant subspace for the

𝕂

-algebra

Alg (ℳ)

generated by

ℳ

. Again it is easy to compute a basis for

Alg (ℳ)

. We start with a basis

ℬ

Vect (ℳ)

and keep adjoining elements in

ℬ^{2} ∖ Vect (ℬ)

ℬ

until saturation. We will avoid the explicit basis of

Alg (ℳ)

, which may contain as much as

n^{2}

elements, and rather focus on the efficient computation of good candidate vectors.

$ℳ$ -splittings

A decomposition

𝕂^{n} = E_{1} \oplus \dots \oplus E_{k}

, where

E_{1}, \dots, E_{k}

are non-empty vector spaces, will be called an $ℳ$ -splitting of

𝕂^{n}

, if the projections

P_{i} = P_{E_{i}}

𝕂^{n}

E_{i}

are all in

Alg (ℳ)

. Then, given

M \in {Mat}_{n} (𝕂)

, we have

M \in Alg (ℳ)

if and only if

P_{i} M P_{j} \in Alg (ℳ)

for all

i, j

. If we choose a basis for

𝕂^{n}

which is a union of bases for the

E_{i}

, we notice that the

P_{i} M P_{j}

are

\dim E_{i} \times \dim E_{j}

block matrices. In the above algorithm for computing the

𝕂

-algebra generated by

ℳ

it now suffices to compute with block matrices of this form. In particular, the computed basis of

Alg (ℳ)

will consist of such matrices. The trivial decomposition

𝕂^{n} = 𝕂^{n}

is clearly an

ℳ

-splitting. Given

N \in Alg (ℳ)

, we notice that any

{N}

-splitting is also an

ℳ

-splitting.

Refining $ℳ$ -splittings

ℳ

-splitting

𝕂^{n} = F_{1} \oplus \dots \oplus F_{l}

is said to be finer than the

ℳ

-splitting

𝕂^{n} = E_{1} \oplus \dots \oplus E_{k}

E_{i}

is a direct sum of a subset of the

F_{j}

for each

i

. Given an

ℳ

-splitting

𝕂^{n} = F_{1} \oplus \dots \oplus F_{l}

and an arbitrary element

M \in Alg (ℳ)

, we may obtain a finer $ℳ$ -splitting w.r.t $M$ as follows. Let

i \in {1, \dots, k}

and consider

M_{i} = P_{i} M P_{i}

. If

λ_{1}, \dots, λ_{p}

are the eigenvalues of

M_{i}

, then

E_{i} = \ker {(M_{i} - λ_{1})}^{n_{i}} \oplus \dots \oplus \ker {(M_{i} - λ_{k})}^{n_{i}}

is an

(P_{i} ℳ P_{i})

-splitting of

E_{i}

, where

n_{i} = \dim E_{i}

. Collecting these

(P_{i} ℳ P_{i})

-splittings, we obtain a finer

ℳ

-splitting

F_{1} \oplus \dots \oplus F_{l}

𝕂^{n}

. This

ℳ

-splitting, which is said to be refined w.r.t. $M$ , has the property that

P_{F_{i}} M P_{F_{i}}

is monopotent on

F_{i}

for each

i

, with unique eigenvalue

λ_{M, F_{i}}

We now have the following algorithm for computing non-trivial $ℳ$ -invariant subspaces of $𝕂^{n}$ when they exist.

Algorithm Invariant_subspace $(ℳ)$

Input: a set of non-zero matrices in ${Mat}_{n} (𝕂)$

Output: an $ℳ$ -invariant subspace of $𝕂^{n}$ or fail

Step 1. [Initial $ℳ$ -splitting]

Compute a “random non-zero element” $N$ of $Alg (ℳ)$

Compute an $ℳ$ -splitting $𝕂^{n} = E_{1} \oplus \dots \oplus E_{k}$ w.r.t. $N$ and each $M \in ℳ$

$𝒟 ≔ \emptyset$

Step 2. [One dimensional components]

For every $E_{i}$ with $\dim E_{i} = 1$ and $E_{i} \notin 𝒟$ , do the following:

Pick a $𝒗 \in E_{i}^{\neq}$ and compute ${Inv}_{ℳ} (𝒗)$

If ${Inv}_{ℳ} (𝒗) ⊊︀ 𝕂^{n}$ then return ${Inv}_{ℳ} (𝒗)$

Otherwise, set $𝒟 ≔ 𝒟 \cup E_{i}$

If $\dim E_{i} = 1$ for all $i$ then return fail

Step 3. [Higher dimensional components]

Let $i$ be such that $\dim E_{i} > 1$

Let $ℳ_{i} ≔ {P_{i} (M - λ_{M, E_{i}}) P_{i} : M \in ℳ}$

Let $K_{i} ≔ E_{i} \cap ⋂_{M \in ℳ_{i}} \ker M$

If $K_{i} = 0$ then go to step 4 and otherwise to step 5

Step 4. [Non-triangular case]

Let $N \in Alg (ℳ_{i})$ be non-monopotent on $E_{i}$ (cf. previous section)

Refine the $ℳ$ -splitting w.r.t. $N$ and return to step 2

Step 5. [Potentially triangular case]

Choose $𝒗 \in K_{i}$ and compute ${Inv}_{ℳ} (𝒗)$

If ${Inv}_{ℳ} (𝒗) ⊊︀ 𝕂^{n}$ then return ${Inv}_{ℳ} (𝒗)$

Otherwise, let $N$ be in $Alg (ℳ)$ with $P_{i} N 𝒗 \notin K_{i}$

Refine the $ℳ$ -splitting w.r.t. $N$

If this yields a finer $ℳ$ -splitting then return to step 2

Otherwise, set $ℳ ≔ ℳ \cup {N}$ and repeat step 5

The algorithm needs a few additional explanations. In step $1$ , we may take $N$ to be an arbitrary element in $ℳ$ . However, it is better to take a “small random expression in the elements of $ℳ$ ” for $N$ . With high probability, this yields an $ℳ$ -splitting which will not need to be refined in the sequel. Indeed, the subset of matrices in $Alg (ℳ)$ which yield non-maximal $ℳ$ -splittings is a closed algebraic subset of measure zero, since it is determined by coinciding eigenvalues. In particular, given an $ℳ$ -splitting $𝕂^{n} = E_{1} \oplus \dots \oplus E_{k}$ w.r.t. $N$ , it will usually suffice to check that each $M \in ℳ$ is monopotent on each $E_{i}$ , in order to obtain an $ℳ$ -splitting w.r.t. the other elements in $ℳ$ .

Throughout the algorithm, the $ℳ$ -splitting gets finer and finer, so the $ℳ$ -splitting ultimately remains constant. From this point on, the space $K_{i}$ can only strictly decrease in step $5$ , so $K_{i}$ also remains constant, ultimately. But then we either find a non-trivial invariant subspace in step 5, or all components of the $ℳ$ -splitting become one-dimensional. In the latter case, we either obtain a non-trivial invariant subspace in step 1, or a proof that ${Inv}_{ℳ} (𝒗) = 𝕂^{n}$ for every $𝒗 \in E_{1}^{\neq} \cup \dots \cup E_{n}^{\neq}$ (and thus for every $𝒗 \in 𝕂^{n} ∖ 0$ ).

Remark 24. Assume that $𝕂$ is no longer an effective algebraically closed field, but rather a field $ℂ^{\approx ε}$ with an approximate zero-test. In that case, we recall that a number which is approximately zero is not necessarily zero. On the other hand, a number which is not approximately zero is surely non-zero. Consequently, in our algorithm for the computation of $Inv (𝒗)$ , the dimension of $Inv (𝒗)$ can be too small, but it is never too large. In particular, if the algorithm Invariant_subspace fails, then the approximate proof that ${Inv}_{ℳ} (𝒗) = 𝕂^{n}$ for every $𝒗 \in E_{1}^{\neq} \cup \dots \cup E_{n}^{\neq}$ yields a genuine proof that there are no non-trivial invariant subspaces.

3.4.Factoring linear differential operators

Putting together the results from the previous sections, we now have the following algorithm for finding a right factor of $L$ .

Algorithm Right_factor $(L)$

Input: $L = \partial^{n} + L_{n - 1} \partial^{n - 1} + \dots + L_{0} \in 𝕂 (z) [\partial]$

Output: a non-trivial right-factor of $L$ or fail

Step 1. [Compute generators]

Choose $z_{0} \in 𝕂 ∖ 𝒮$ and let $𝒉 = 𝒉^{z_{0}}$

Compute a finite set $ℳ \subseteq {GL}_{n} (ℂ^{eff})$ of generators for $𝒢_{L, 𝒉}$ (cf. theorem 20)

Step 2. [Initial precision]

$T ≔ max (\deg L_{0}, \dots, \deg L_{n - 1}) + 1$

$δ ≔ 2^{- 32}$

while $δ^{'} ≔ min {M_{i, j} / M_{i^{'}, j^{'}} : M \in ℳ, M_{i^{'}, j^{'}}^{\approx δ / 2^{T}} \neq 0} < δ$ do $δ ≔ δ^{'}$

$ε ≔ δ / 2^{T}$

Step 3. [Produce invariant subspace]

Let $V ≔ (ℳ^{\approx ε})$

If $V =$ then return fail

Let $B \in {Mat}_{n, r} (ℂ^{\approx ε})$ be a column basis of $V$

Let $𝒈 ≔ {}^{t}B 𝒉 \in {({[ℂ^{eff}]}^{\approx ε} {[[z]]}^{eff})}^{r}$

Step 4. [Produce and check guess]

Let $K ≔ \partial^{r} - \frac{W_{𝒈, 1}}{W_{𝒈, 0}} \partial^{r - 1} + \dots + {(- 1)}^{r} \frac{W_{𝒈, r}}{W_{𝒈, 0}}$

Divide $L$ by $K$ , producing $Q, R \in {[ℂ^{\approx ε} ((z))]}^{eff} [\partial]$ with $L = Q K + R$

If $R \neq 0 \mod z^{T}$ then go to step 5

Reconstruct $\tilde{Q}, \tilde{K} \in 𝕂 (z) [\partial]$ from $Q$ and $K$ with precision $(ε, T)$

If we obtain no good approximations or $L \neq \tilde{Q} \tilde{K}$ then go to step 5

Return $\tilde{K}$

Step 5. [Increase precision]

$T ≔ 2 T$

$ε ≔ δ / 2^{T}$

Go to step 3

The main idea behind the algorithm is to use proposition 22 in combination with Invariant_subspace so as to provide good candidate right factors of $L$ in $ℂ^{eff} ((z)) [\partial]$ . Using reconstruction of coefficients in $𝕂 (z)$ from Laurent series in $ℂ^{eff} ((z))$ with increasing precisions, we next produce good candidate right factors in $𝕂 (z)$ . We keep increasing the precision until we find a right factor or a proof that $L$ is irreducible. Let us detail the different steps a bit more:

Step 2: We will work with power series approximations of $T$ terms and approximate zero-tests in $ℂ^{\approx ε}$ . The degree of a rational function $P / Q$ is defined by $\deg P / Q = max (\deg P, \deg Q)$ . The initial precisions $T$ and $- \log ε$ have been chosen as small as possible. Indeed, we want to take advantage of a possible quick answer when computing with a small precision (see also the explanations below of step 5).
Step 3: If Invariant_subspace fails, then there exists no factorization of $L$ , by remark 24. Effective power series and Laurent series are defined in a similar way as effective real numbers (in particular, we don't assume the existence of an effective zero-test). Efficient algorithm for such computations are described in [vdH02].
Step 4: The reconstruction of $\tilde{Q}$ and $\tilde{K}$ from $Q$ and $K$ contains two ingredients: we use Padé approximation to find rational function approximations of degree $⩽ T$ and the LLL-algorithm to approximate numbers $ℂ^{\approx ε}$ by numbers in $𝕂$ .
Step 5: Doubling the precision at successive steps heuristically causes the computation time to increase geometrically at each step. In particular, unsuccessful computations at lower precisions don't take much time with respect to the last successful computation with respect to the required precision. Instead of multiplying the precisions by two, we also notice that it would be even better to increase by a factor which doubles the estimated computation time at each step. Of course, this would require a more precise complexity analysis of the algorithm.

The problem of reconstructing elements in $𝕂$ from elements in $ℂ^{\approx ε}$ is an interesting topic on its own. In theory, one may consider the polynomial algebra over $ℤ$ generated by all coefficients occurring in $L$ and the number $z$ we wish to reconstruct. We may then apply the LLL-algorithm [LLL82] on the lattice spanned by $\sqrt{T}$ monomials of smallest total degree (for instance) and search for minimal $⩽ \sqrt{T}$ -digit relations. If $𝕂 = ℚ^{alg}$ is the algebraic closure of $ℚ$ , then we may simply use the lattice spanned by the first $n$ powers of $z$ .

At a sufficiently large precision $T$ , the LLL-algorithm will ultimately succeed for all coefficients of a candidate factorization which need to be reconstructed. If there are no factorizations, then the algorithm will ultimately fail at step 3. This proofs the termination of Right_factor.

Remark 25. In practice, and especially if $𝕂 \neq ℚ^{alg}$ , it would be nice to use more of the structure of the original problem. For instance, a factorization of $L$ actually yields relations on the coefficients which we may try to use. For high precision computations, it is also recommended to speed the LLL-algorithm up using a similar dichotomic algorithm as for fast g.c.d. computations [Moe73, PW02].

Remark 26. Notice that we did not use bounds for the degrees of coefficients of possible factors in our algorithm. If a bound $T^{B}$ is available, using techniques from [BB85, vH97, vdPS03], then one may take $T ≔ min (2 T, T^{B})$ instead of $T ≔ 2 T$ in step 5. Of course, bounds for the required precision $ε$ are even harder to obtain. See [BB85] for some results in that direction.

4.Computing differential Galois groups

4.1.Introduction

Throughout this section, $𝔽$ will stand for the field $ℂ^{\approx ε}$ of effective complex number with the approximate zero-test at precision $ε > 0$ . This field has the following properties:

EH1: We have an effective zero-test in $𝔽$ .
EH2: There exists an algorithm which takes on input $𝒄 \in {(𝔽^{\neq})}^{n}$ and which computes a finite set of generators for the $ℤ$ -vector space of integers $𝒌 \in ℤ^{n}$ with $𝒄^{𝒌} = 1$ .
EH3: There exists an algorithm which takes on input $𝒄 \in 𝔽^{n}$ and which computes a finite set of generators for the $ℤ$ -vector space of integers $𝒌 \in ℤ^{n}$ with $𝒄 \cdot 𝒌 = 0$ .
EH4: $𝔽$ is closed under exponentiation and logarithm.

Indeed, we obtain EH2 and EH3 using the LLL-algorithm. Some of the results in this section go through when only a subset of the conditions are satisfied. In that case, we notice that EH2 $\Rightarrow$ EH1, EH3 $\Rightarrow$ EH1 and EH4 $\Rightarrow$ (EH2 $\Leftrightarrow$ EH3).

Given a finite set of matrices $ℳ \subseteq {GL}_{n} (𝔽)$ , we give a numerical algorithm for the computation of the smallest closed algebraic subgroup $𝒢 = ⟨ ℳ ⟩$ of ${GL}_{n} (𝔽)$ which contains $ℳ$ . We will represent $𝒢$ by a finite set $ℱ \subseteq {GL}_{n} (𝔽)$ and the finite basis $ℬ \subseteq GL (𝔽)$ of a Lie algebra $ℒ$ over $ℂ$ , such that

𝒢 = ℱ e^{ℒ},

and each $N \in ℱ$ corresponds to a unique connected component $N e^{ℒ} = e^{ℒ} N$ of $𝒢$ . We will also prove that there exists a precision $ε_{0}$ such that the algorithm yields the theoretically correct result for all $ε < ε_{0}$ .

4.2.The algebraic group generated by a diagonal matrix

Let ${Tor}_{n} (𝔽)$ be the group of invertible diagonal matrices. Each matrix $M$ has the form $M = Diag (𝛂)$ , where $𝛂 = (α_{1}, \dots, α_{n})$ is the vector in ${(𝔽^{\neq})}^{n}$ of the elements on the diagonal of $M$ . The coordinate ring $ℛ$ of ${Tor}_{n} (𝔽)$ is the set $𝔽 [𝛂, 𝛂^{- 1}]$ of Laurent polynomials in $𝛂$ .

Now consider the case when $ℳ$ consists of a single diagonal matrix $M = Diag (𝛌)$ . Let $𝔦 \subseteq ℛ$ be the ideal which defines $⟨ M ⟩ \subseteq {Tor}_{n} (𝔽)$ . Given a relation $𝛌^{𝒌} = 1 (𝒌 \in ℤ^{n})$ between the $λ_{i}$ , any power $M^{i} = Diag (𝛌^{i})$ satisfies the same relation ${(𝛌^{i})}^{𝒌} = 1$ , whence $𝛂^{𝒌} - 1 \in 𝔦$ . Let $𝔧$ be the ideal generated by all $𝛂^{𝒌} - 1$ , such that $𝛌^{𝒌} = 1$ .

Lemma 27. We have $𝔧 = 𝔦$ .

Proof. We already observed that $𝔧 \subseteq 𝔦$ . Assuming for contradiction that $𝔧 \neq 𝔦$ , choose

f = \sum_{i = 1}^{r} f_{i} 𝛂^{𝒌_{i}} \in 𝔦 ∖ 𝔧

such that

r

is minimal. If

i \neq j

, then

𝛌^{𝒌_{i} - 𝒌_{j}} \neq 1

, since otherwise

𝛌^{𝒌_{i} - 𝒌_{j}} \in 𝔧

and

f - f_{i} 𝛂^{𝒌_{i}} + f_{i} 𝛂^{𝒌_{j}} \in 𝔦 ∖ 𝔧

has less than

r

terms. In particular, the vectors

(1, 𝛌^{𝒌_{i}}, \dots, 𝛌^{(r - 1) 𝒌_{i}})

with

i \in {1, \dots, r}

are linearly independent. But this contradicts the fact that

f (𝛌^{j}) = \sum_{i = 1}^{r} f_{i} 𝛌^{j 𝒌_{i}} = 0

for all

j \in {0, \dots, r - 1}

□

By EH2, we may compute a minimal finite set $𝒈_{1}, \dots, 𝒈_{p}$ of generators for the $ℤ$ -vector space of $𝒌 \in ℤ^{n}$ with $𝛌^{𝒌} = 1$ . We may also compute a basis $ℬ$ for $\ker φ$ , where $φ : ℤ^{n} \to ℤ^{p}; 𝒌 \mapsto (𝒌 \cdot 𝒈_{1}, \dots, 𝒌 \cdot 𝒈_{p})$ . Then $e^{ℒ} = e^{Vect (ℬ)}$ is the connected component of $⟨ M ⟩$ , since ${(e^{ℒ})}^{𝒈_{i}} = 1$ for all $i$ , and $ℒ$ cannot be further enlarged while conserving this property.

Let $𝒱 = (𝒈_{1} ℚ \oplus \dots \oplus 𝒈_{p} ℚ) \cap ℤ^{n}$ . We construct a basis $𝒉_{1}, \dots, 𝒉_{n}$ of $ℤ^{n}$ , by taking $𝒉_{i}$ to be shortest in $𝒱$ (if $i ⩽ p$ ) or $ℤ^{n}$ (if $i > p$ ), such that $𝒉_{i} \notin Vect (𝒉_{1}, \dots, 𝒉_{i - 1})$ . This basis determines a toric change of coordinates $𝛂 \to 𝛂^{P}$ with $P \in {GL}_{n} (ℤ)$ such that $𝒈_{1}, \dots, 𝒈_{p} \in ℤ^{p} \times 0^{n - p}$ with respect to the new coordinates. Similarly, we may construct a basis $𝒃_{1}, \dots, 𝒃_{p}$ of $ℤ^{p}$ , by taking each $𝒃_{i}$ to be shortest in $ℤ^{p} ∖ Vect (𝒃_{1}, \dots, 𝒃_{i - 1})$ such that $r_{i} = min {r \in ℕ^{>} : r 𝒃_{i} \in ℤ 𝒈_{1} \oplus \dots \oplus ℤ 𝒈_{p}}$ is maximal. This basis determines a second toric change of coordinates $𝛂 \to 𝛂^{Q}$ with $Q \in {GL}_{n} (ℤ)$ such that $𝒈_{i} = r_{i} 𝒆_{i}$ ( $i = 1, \dots, p$ ) with respect to the new coordinates.

After the above changes of coordinates, the ideal $𝔧$ is determined by the equations $α_{1}^{r_{1}} = \dots = α_{p}^{r_{p}} = 1$ . Setting

ℱ = {(e^{2 π ⅈ s_{1} / r_{1}}, \dots, e^{2 π ⅈ s_{p} / r_{p}}, 1, \dots, 1) : 𝒔 \in ℕ^{p}, s_{1} < r_{1}, \dots, s_{p} < r_{p}},

it follows that $⟨ M ⟩ = ℱ e^{ℒ}$ . Rewriting $ℱ$ with respect to the original coordinates now completes the computation of $⟨ M ⟩$ .

4.3.The algebraic group generated by a single matrix

Let us now consider the case when $ℳ$ consists of a single arbitrary matrix $M$ . Then we first compute the multiplicative Jordan decomposition of $M$ . Modulo a change of basis of $𝔽^{n}$ , this means that

M = D U = U D,

where $D = M_{s}$ and $U = M_{u}$ are the semi-simple and unipotent parts of $M$ :

D = (\begin{array}{ccc} λ_{1} I_{n_{1}} \\ ⋱ \\ λ_{k} I_{n_{k}} \end{array}), U = (\begin{array}{ccc} J_{n_{1}} \\ ⋱ \\ J_{n_{k}} \end{array}),

where

J_{n} = (\begin{array}{cccc} 1 & 1 \\ 1 & ⋱ \\ ⋱ & 1 \\ 1 \end{array}) .

Proposition 28. We have $⟨ U ⟩ = {\exp (μ \log U) : μ \in 𝔽} .$

Remark. Notice that $f (N) = \sum_{i = 0}^{\infty} f_{i} N^{i} = \sum_{i = 0}^{n - 1} f_{i} N^{i}$ is well-defined for power series $f \in 𝔽 [[z]]$ and nilpotent matrices $N \in {Mat}_{n} (𝔽)$ ; in this case, $f = {(1 + z)}^{μ}$ and $N = U - 1$ .

Proof. The assertion is clear if

U = I_{n}

, so assume

U \neq I_{n}

. Let

𝒳 = {\exp (μ \log U) : μ \in 𝔽}

. We clearly have

⟨ U ⟩ \subseteq 𝒳

, since

𝒳

is a closed algebraic group which contains

U

. Moreover, the set

U, U^{2}, U^{3}, \dots

is infinite, so

\dim ⟨ U ⟩ ⩾ 1

. Since

𝒳

is irreducible and

\dim 𝒳 = 1

, we conclude that

⟨ U ⟩ = 𝒳

□

Proposition 29. We have $⟨ M ⟩ = ⟨ D ⟩ ⟨ U ⟩$ .

Proof. Since

⟨ M ⟩

is a commutative group, [Hum81, Theorem 15.5] implies that

⟨ M ⟩ = {⟨ M ⟩}_{s} {⟨ M ⟩}_{u}

, where

{⟨ M ⟩}_{s} = {N_{s} : N \in ⟨ M ⟩}

and

{⟨ M ⟩}_{u} = {N_{u} : N \in ⟨ M ⟩}

are closed subgroups of

⟨ M ⟩

. Now

⟨ D ⟩

and

⟨ U ⟩

are closed subgroups of

{⟨ M ⟩}_{s}

resp.

{⟨ M ⟩}_{u}

, so

⟨ D ⟩ ⟨ U ⟩

is a closed subgroup of

⟨ M ⟩

. Since

M \in ⟨ D ⟩ ⟨ U ⟩

, it follows that

⟨ M ⟩ = ⟨ D ⟩ ⟨ U ⟩

□

Corollary 30. If $⟨ D ⟩ = ℱ e^{ℒ}$ , then $⟨ M ⟩ = ℱ e^{ℒ + 𝔽 \log U}$ .

4.4.Membership testing for the connected component

In order to compute the closure of the product of a finite number of algebraic groups of the form $ℱ e^{ℒ}$ , an important subproblem is to test whether a given matrix $M \in {GL}_{n} (𝔽)$ belongs to $e^{ℒ}$ .

We first observe that $M \in e^{ℒ}$ implies $⟨ M ⟩ \subseteq e^{ℒ}$ . After the computation of $ℱ^{'}$ and $ℒ^{'}$ with $⟨ M ⟩ = ℱ^{'} e^{ℒ^{'}}$ it therefore suffices to check that $ℒ^{'} \subseteq ℒ$ and $ℱ^{'} \subseteq e^{ℒ}$ . In fact, it suffices to check whether $M^{'} \in e^{ℒ}$ , where $M^{'}$ is the unique matrix in $ℱ^{'}$ with $M \in M^{'} e^{ℒ^{'}}$ . Modulo a suitable base change, we have thus reduced the general problem to the case when $M$ is a diagonal matrix whose eigenvalues are all roots of unity.

Assume that $M \in e^{ℒ}$ and $ℓ \in ℒ$ are such that $M \in e^{ℂ ℓ}$ . Since $M$ and $ℓ$ commute, it follows that $M$ and $ℓ$ can be diagonalized w.r.t. a common basis. The elements of this basis are elements of the different eigenspaces of $M$ . In other words, if $M = Diag (λ_{1} I_{n_{1}}, \dots, λ_{k} I_{n_{k}})$ with pairwise distinct $λ_{i}$ , then $P^{- 1} ℓ P$ is diagonal for some block matrix $P = Diag (P_{1}, \dots, P_{k})$ with $P_{i} \in {GL}_{n_{i}} (𝔽)$ for each $i$ . It follows that $ℓ = Diag (ℓ_{1}, \dots, ℓ_{k})$ for certain $ℓ_{i} \in {Mat}_{n_{i}} (𝔽)$ . Without loss of generality, we may therefore replace $ℒ$ by the intersection of $ℒ$ with $Diag ({Mat}_{n_{1}} (𝔽), \dots, {Mat}_{n_{k}} (𝔽))$ .

From now on, we assume that the above two reductions have been made. Let $ℓ = Diag (μ_{1}, \dots, μ_{n})$ be a diagonal matrix in $ℒ$ . By lemma 27, we have $M \in e^{ℂ ℓ}$ if and only if any $ℤ$ -linear relation $𝒍 \cdot 𝛍 = 0$ induces a relation $𝛌^{π (𝒍)} = 1$ , where $π (𝒍) = (l_{1} + \dots + l_{n_{1}}, \dots, l_{n - n_{k}} + \dots + l_{n})$ . Now consider a random matrix $R$ in $ℒ$ , i.e. a linear combination of the basis elements with small random integer coefficients. We compute its blockwise Jordan normal form $J = P^{- 1} R P$ so that $P \in Diag ({GL}_{n_{1}} (𝔽), \dots, {GL}_{n_{k}} (𝔽))$ and let $ℓ$ be the restriction of $J$ to the diagonal. We have $M \in e^{ℂ ℓ} \Leftrightarrow M \in e^{ℂ J} \Leftrightarrow M = P M P^{- 1} \in e^{ℂ R}$ . Computing a basis for the $ℤ$ -linear relations of the form $𝒍 \cdot 𝛍 = 0$ using EH3, the above criterion now enables us to check whether $M \in e^{ℂ R}$ .

If the check whether $M \in e^{ℂ R}$ succeeds, then we are clearly done. Otherwise, since $R$ was chosen in a random way, the relation $𝒍 \cdot 𝛍$ is very likely to be satisfied for all possible choices of $R \in ℒ$ (up to permutations of coordinates inside each block). Indeed, the $R$ for which this is not the case lie on a countable union $𝒰$ of algebraic variety of a lower dimension, so $𝒰$ has measure $0$ . Heuristically speaking, we may therefore conclude that $M \notin e^{ℒ}$ if the check fails (at least temporarily, modulo some final checks when the overall computation of $⟨ ℳ ⟩$ will be completed).

Theoretically speaking, we may perform the above computations with $R^{'} = \sum_{B \in ℬ} α_{B} B$ instead of $R$ , where $ℬ$ is a basis of $ℒ$ and the $α_{B}$ are formal parameters. We then check whether the relation $𝒍 \cdot 𝛍^{'}$ is still satisfied for the analogue $ℓ^{'} = Diag (μ_{1}^{'}, \dots, μ_{n}^{'})$ of $ℓ$ . If so, then we are sure that $M \notin e^{ℒ}$ . Otherwise, we keep trying with other random elements of $ℒ$ .

It is likely that a more efficient theoretical algorithm can be designed for testing $ℤ$ -linear relations between the eigenvalues of elements in $ℒ$ . One of the referees suggested to use similar methods as in [Mas88, Ber95, CS98]. However, we did not study this topic in more detail, since our final algorithm for the computation of Galois groups will be based on heuristics anyway. We also notice that a “really good” random number generator should actually never generate points which satisfy non-trivial algebraic relations.

4.5.Computing the closure of $ℳ$

A Lie algebra $ℒ$ is said to be algebraic, if it is the Lie algebra of some algebraic group, i.e. if $e^{ℒ}$ is an algebraic subset of ${GL}_{n} (𝔽)$ . It is classical [Bor91, Corollary 7.7] that the smallest Lie algebra generated by a finite number of algebraic Lie algebras is again algebraic. The Lie algebras we will consider in our algorithms will always assumed to be algebraic. Given a finite number $ℒ_{1}, \dots, ℒ_{l}$ of algebraic Lie algebras and a basis $ℬ$ for $ℒ_{1} + \dots + ℒ_{l}$ , it is easy to enrich $ℬ$ so that $ℒ = Vect (ℬ)$ is a Lie algebra: as long as $[𝒃_{1}, 𝒃_{2}] \notin ℒ$ for two elements $𝒃_{1}, 𝒃_{2} \in ℬ$ , we add $[𝒃_{1}, 𝒃_{2}]$ to $ℬ$ . By what precedes, the computed Lie algebra $ℒ$ is again algebraic.

Putting together the ingredients from the previous sections, we now have the following algorithm for computing the smallest closed algebraic group $⟨ ℳ ⟩$ which contains $ℳ$ .

Algorithm Closure( $ℳ$ )

Input: A subset $ℳ = {M_{1}, \dots, M_{m}}$ of ${GL}_{n} (𝔽)$

Output: a numeric approximation of $⟨ ℳ ⟩$

Step 1. [Initialize algorithm]

Compute $⟨ M_{i} ⟩ = ℱ_{i} e^{ℒ_{i}}$ for each $i \in {1, \dots, m}$

Let $ℱ ≔ ℱ_{1} \cup \dots \cup ℱ_{m}$ (notice that $1 \in ℱ$ )

Let $ℒ ≔ Lie (ℒ_{1} + \dots + ℒ_{m})$

Step 2. [Closure]

While there exists an $N \in ℱ ∖ {1}$ with $N ℒ N^{- 1} ⊈ ℒ$ set $ℒ ≔ Lie (ℒ + N ℒ N^{- 1})$

While there exists an $N \in ℱ ∖ {1}$ with $N \in e^{ℒ}$ set $ℱ ≔ ℱ ∖ {N}$

While there exists $N \in ℱ^{2}$ with $N \notin ℱ e^{ℒ}$ do

Compute $⟨ N ⟩ = ℱ^{'} e^{ℒ^{'}}$

If $ℒ^{'} ⊈ ℒ$ then set $ℒ ≔ Lie (ℒ + ℒ^{'})$ , quit loop and repeat step 2

Otherwise, set $ℱ ≔ ℱ \cup {N}$

Return $ℱ e^{ℒ}$

The termination of this algorithm relies on a lemma, whose proof was kindly communicated to the author by J.-Y. Hée.

Lemma 31. Let $ℋ$ be a closed algebraic subgroup of ${GL}_{n} (ℂ)$ and let $M_{1}, \dots, M_{m} \in {GL}_{n} (ℂ)$ be a finite number of matrices in the normalizer of $ℋ$ . Denote by $𝒢$ the group generated by $ℋ$ and $M_{1}, \dots, M_{m}$ . If all elements in $𝒢 / ℋ$ have finite order, then $𝒢 / ℋ$ is finite.

Proof. In the case when

ℋ = {1}

, the result is classical [Dix71, Theorem 9.2]. In the general case, the normalizer

𝒩

ℋ

is a closed algebraic subgroup of

{GL}_{n} (ℂ)

and

ℋ

is a normal subgroup of

𝒩

. By [Bor91, Theorem 6.8 and Proposition 1.10], it follows that

𝒩 / 𝒢

is an affine algebraic group which is isomorphic to a closed algebraic matrix group. This reduces the general case to the special case when

ℋ = {1}

□

Theorem 32. There exists an $ε_{0} \in ℕ^{>} 2^{ℤ}$ such that, for every $ε \in ℕ^{>} 2^{ℤ}$ with $ε < ε_{0}$ , the set $ℱ e^{ℒ}$ returned by Closure, considered as a subset of ${GL}_{n} (ℂ^{eff})$ , coincides with the smallest closed algebraic subgroup $⟨ ℳ ⟩$ of ${GL}_{n} (ℂ^{eff})$ which contains $ℳ$ .

Proof. Clearly, the dimension of $ℒ$ increases throughout the execution of the algorithm, so it remains ultimately constant. At this point, the set $ℱ$ will keep growing and the lemma implies that $ℱ$ ultimately stabilizes. When this happens, $ℱ$ is closed under multiplication modulo $e^{ℒ}$ , as well as under multiplicative inverses, since each element in $ℱ$ has finite order modulo $e^{ℒ}$ . We conclude that $ℱ e^{ℒ}$ is indeed the smallest closed algebraic subgroup of ${GL}_{n} (𝔽)$ which contains $ℳ$ , provided that the approximate zero-test always returns the right result.

In order to prove the correctness at a sufficient precision, we assume that we use the theoretic membership test from section 4.4 and that the random number generator successively generates the same random numbers each time we relaunch the algorithm at a higher precision. Now consider the trace of the execution of our algorithm when using an infinite precision. Let

ε_{0}

be a sufficient precision such that all zero-tests in this execution tree are still correct when we replace the infinite precision by a precision

ε < ε_{0}

. Then the trace of the execution any finite precision

ε < ε_{0}

coincides with the trace of the execution at infinite precision. This completes the proof.

□

Remark 33. The main improvement of the algorithm Closure w.r.t. the algorithm from [DJK03] lies in the more efficient treatment of the connected component (using linear algebra). On the other hand, the mere enumeration of representatives in each connected component can be very unefficient (although a Gröbner basis might be of the same size). Fortunately, we will see in the next sections how to remove this drawback.

Assume now that $ℳ$ is the set of generators for $𝒢_{L, 𝒉^{z_{0}}}$ as computed in theorem 20. Assume that we have computed a reasonable candidate $ℱ e^{ℒ}$ for $⟨ ℳ ⟩$ , expressed in the original basis corresponding to $𝒉^{z_{0}}$ . We still have to reconstruct $\tilde{ℱ} \subseteq {GL}_{n} (𝕂)$ and $\tilde{ℒ} = Vect (\tilde{ℬ})$ with $\tilde{ℬ} \in {Mat}_{n} (𝕂)$ such that $ℱ e^{ℒ} \cap {GL}_{n} (𝕂) = \tilde{ℱ} e^{\tilde{ℒ}} \cap {GL}_{n} (𝕂)$ .

In the case of $\tilde{ℒ}$ , by selecting a suitable basis of ${Mat}_{n} (𝔽)$ , we may consider $\tilde{ℬ}$ as a big $d \times n^{2}$ matrix whose first $d$ columns are linearly independent. We compute the row-echelon form of this basis:

E = (\begin{array}{cccccc} 1 & * & \dots & * \\ ⋱ & ⋮ & ⋮ \\ 1 & * & \dots & * \end{array}) .

The entries of $E$ must be in $𝕂$ : provided that $\tilde{ℒ}$ is indeed generated by a basis of matrices with entries in $𝕂$ , the row-echelon form of this second basis coincides with $E$ . It therefore suffices to reconstruct the entries of $E$ using the LLL-algorithm.

In the case of a matrix $M \in ℱ$ , the set $M e^{\tilde{ℒ}}$ is an algebraic variety of dimension $d$ over $𝕂$ . Now choose $\tilde{M} \in M e^{\tilde{ℒ}}$ close to $M$ in such a way that $d$ independent coordinates of $\tilde{M}$ are all in $ℚ \subseteq 𝕂$ . Then the other coordinates of $\tilde{M}$ , considered as elements of $ℂ^{eff}$ , are easily found using Newton's method. Since $M e^{\tilde{ℒ}}$ is an algebraic variety, these other coordinates are actually in $𝕂$ , and we reconstruct them using the LLL-algorithm.

4.6.Fast computations with the connected components

The algorithm Closure from the previous section is quite inefficient when the set $ℱ$ becomes large. It is therefore useful to seek for a better computational representation of $ℱ$ . For finite groups $𝒢$ , one classical idea is to search for a sequence of subgroups

1 = 𝒢_{0} ⊊︀ 𝒢_{1} ⊊︀ \dots ⊊︀ 𝒢_{k} = 𝒢

(9)

such that the indices $𝒢_{i} : 𝒢_{i - 1}$ are small. Then we may represent elements in $ℱ$ by sequences $(a_{1}, \dots, a_{k})$ with $a_{i} \in 𝒢_{i} / 𝒢_{i - 1}$ for each $i$ . This representation is particularly useful if $ℱ$ operates on a set $𝒮$ and if there exists points $a_{1}, \dots, a_{k}$ in $𝒮$ such that

𝒢_{i} = S_{a_{1}, \dots, a_{k - i}}

is the stabilizer of the set ${a_{1}, \dots, a_{k - i}}$ for each $i$ . Then the set $S_{a_{1}, \dots, a_{i - 1}} / S_{a_{1}, \dots, a_{i}}$ corresponds to the orbit of $a_{i}$ while leaving $a_{1}, \dots, a_{i - 1}$ fixed [Sim70, Sim71].

In the case of matrix groups, one often takes $𝔽^{n}$ for $𝒮$ [MO95]. However, this approach only yields interesting results when there exist non-trivial invariant subspaces under the action of the group, which will usually not be the case for us (otherwise we may factor $L$ and consider smaller problems). A theoretical way out of this is to also consider the action of $ℱ$ on exterior powers $\land^{p} 𝔽^{n}$ . However, this approach is very expensive from a computational point of view. In our more specific context of matrices with complex entries, we will therefore combine two other approaches: non-commutative lattice reduction and the operation of $ℱ$ on ${Mat}_{n} (𝔽) / e^{ℒ}$ via conjugations $M \mapsto M N M^{- 1}$ .

The algebra ${Mat}_{n} (𝔽)$ admits a natural (multiplicative) norm, given by

‖ M ‖ = sup {| M V | : V \in 𝔽^{n}, | V | = 1},

where $| \cdot |$ stands for the Euclidean norm on $𝔽^{n}$ . If $𝒢 = ⟨ ℳ ⟩ / e^{ℒ}$ is finite, this enables us to construct $𝒢_{0} = 1, 𝒢_{1}, \dots, 𝒢_{k}$ as in (9) as follows. Assuming that $𝒢_{0}, \dots, 𝒢_{i - 1}$ have been constructed, we consider a matrix $M_{i} \in ⟨ ℳ ⟩ ∖ 𝒢_{i - 1} e^{ℒ}$ for which $‖ M_{i} - 1 ‖$ is minimal, and let $𝒢_{i}$ be the set generated by $M_{i} e^{ℒ}$ and $𝒢_{i - 1}$ in $𝒢$ . This construction allows us to rapidly identify a big commutative part of $𝒢$ . More precisely, we have

Proposition 34. Let $A, B \in {GL}_{n} (𝔽)$ be such that $ε = ‖ A - 1 ‖ < 1$ and $δ = ‖ B - 1 ‖ < 1$ . Then we have

$‖ A B A^{- 1} B^{- 1} - 1 ‖ ⩽ B (δ, ε) = \frac{2 ε^{2}}{1 - ε} + \frac{2 δ^{2}}{1 - δ} + \frac{4 ε δ}{(1 - ε) (1 - δ)} .$

Proof. Writing $A = 1 + Δ$ and $B = 1 + Ε$ , we expand $A^{- 1} = 1 - Δ + Δ^{2} + \dots$ and $B^{- 1} = 1 - Ε + Ε^{2} + \dots$ in $A B A^{- 1} B^{- 1}$ . This yields a non-commutative power series in $Δ$ and $Ε$ whose terms in $1, Δ$ and $Ε$ vanish. It follows that

‖ A B A^{- 1} B^{- 1} - 1 ‖ ⩽ (1 + δ) (1 + ε) \frac{1}{1 - δ} \frac{1}{1 - ε} - 1 - 2 δ - 2 ε = B (δ, ε) .

□

The proposition implies that $‖ A B A^{- 1} B^{- 1} - 1 ‖ < min (ε, δ)$ whenever $max (ε, δ) < 5 - \sqrt{24}$ . Now take $A = M_{i}$ and $B = M_{j}$ with $i < j$ , where the $M_{i}$ are as above. Then it follows that $A$ and $B$ commute whenever $B (δ, ε) < ‖ M_{1} - 1 ‖$ . What is more, proposition 34 shows that taking commutators is a convenient way to construct matrices close to identity from a set of non-commutative generators.

However, from the effective point of view, we will not compute the exact computation of minimal representatives $M_{i}$ in cosets of algebraic groups in detail. We will rather simulate such a computation in a way which is sufficient for our purpose. If $M \in ℱ$ is such that $‖ M - 1 ‖$ is small, then we will also try to use the fact that the centralizer $C_{M}$ of $M$ is often a big subgroup of $⟨ ℳ ⟩ / e^{ℒ}$ , so the orbit of $N \mapsto N^{- 1} M N$ is small.

4.7.Non-commutative lattice reduction

Let $𝒢$ be a closed algebraic subgroup of ${Mat}_{n} (𝔽)$ with associated Lie-algebra $ℒ$ . In this section, we will show how to compute efficiently with elements of the finite group $ℋ = 𝒢 / e^{ℒ}$ . Until the very end of this section, we assume that $𝒢$ is included in the connected component of the normalizer of $e^{ℒ}$ in ${Mat}_{n} (𝔽)$ . We denote by $𝒩$ the Lie algebra of this connected component. By [Hum81, Theorem 13.3], we have $𝒩 = {N \in {Mat}_{n} (𝔽) : [N, ℒ] \subseteq ℒ}$ .

Orthogonal projection

Let

M \in 𝒢

and recall that

M

belongs to the normalizer of

e^{ℒ}

. If

‖ M - 1 ‖ < 1

, then

X = \log (1 + (M - 1))

also belongs to the normalizer of

e^{ℒ}

. Since

M \in e^{𝔽 X}

lies in the connected component of this normalizer, we have

X \in 𝒩

. Now consider the orthogonal supplement

ℒ^{⊥}

ℒ

for the Hermitian product on

{Mat}_{n} (𝔽)

. We define

π_{ℒ} (M) = e^{Y}

, where

Y

is the orthogonal projection of

X

ℒ^{⊥}

. From

[X, ℒ] \subseteq ℒ

, it follows that

π_{ℒ} (M) \in M e^{ℒ}

, and we denote

‖ M ‖_{ℒ} = ‖ π_{ℒ} (M) ‖

. Since

e^{𝒩}

is connected, the function

M \mapsto \log M

may actually be analytically continued to a multivalued function

e^{𝒩} \to 𝒩

. After choosing branch cuts (the way this is done is not crucial for what follows, provided that we make the standard choice for

M

with

‖ M - 1 ‖ < 1

), this allows us to extend the definitions of

π_{ℒ}

and

‖ \cdot ‖_{ℒ}

to the case when

‖ M - 1 ‖ ⩾ 1

Representation of the elements in $ℋ$

Let

X \in 𝒩

and

M = e^{X}

be such that

$M e^{ℒ} \in ℋ$ .
$M e^{ℒ}$ generates $(e^{𝔽 X} \cap 𝒢) / e^{ℒ}$ .
$‖ M ‖_{ℒ} ⩽ ‖ M^{k} ‖_{ℒ}$ whenever $M^{k} \in M^{ℤ}$ is another such generator.

Let $p_{1} \dots p_{l}$ be the prime-decomposition of the order of $M$ modulo $e^{ℒ}$ , with $p_{1} ⩾ \dots ⩾ p_{l}$ . Let $A_{0} = X$ and $A_{i} = M^{p_{1} \dots p_{i}}$ for all $i \in {1, \dots, l}$ . Let $ℋ_{i}$ be the subgroup of $ℋ$ of elements which commute with $A_{i}$ modulo $e^{ℒ}$ , so that $ℋ_{0} \subseteq \dots \subseteq ℋ_{l} = ℋ$ . For $i \in {1, \dots, r}$ , we represent elements in the quotient $ℋ_{i} / ℋ_{i - 1}$ by elements in the orbit of the action $Φ_{A_{i}} : N \mapsto A_{i} N A_{i}^{- 1}$ modulo $ℋ_{i - 1}$ . Since $[X, ℒ] \subseteq ℒ$ , the set $ℒ^{'} = ℒ \oplus 𝔽 X$ is a Lie algebra whose normalizer contains $ℋ_{0}$ . Consequently, $ℋ_{0} ≅ M^{ℤ} \times ℋ_{0} / e^{ℒ^{'}}$ , and we represent elements in $ℋ_{0}$ by products $M^{k} P$ , with $k \in ℤ$ and $P e^{ℒ^{'}} \in ℋ_{0} / e^{ℒ^{'}}$ . The elements in $ℋ_{0} / e^{ℒ^{'}}$ are represented in a similar way as the elements in $ℋ$ , using recursion. The successive matrices $M$ for $𝒢 / e^{ℒ}$ , $ℋ_{0} / e^{ℒ^{'}}$ , etc. will be called a basis for $ℋ$ . A basis $(B_{1}, \dots, B_{m})$ is said to be sorted if $‖ B_{1} ‖_{ℒ} ⩽ \dots ⩽ ‖ B_{m} ‖_{ℒ}$ .

Adding new elements to a basis

Let

(B_{1}, \dots, B_{m})

be a sorted basis for

ℋ = 𝒢 / e^{ℒ}

and assume that we want to compute the extension

\hat{𝒢} = ⟨ 𝒢, N ⟩

𝒢

by a new matrix

N

. Whenever we hit an element

\hat{M} e^{ℒ} \in \hat{ℋ} = \hat{𝒢} / e^{ℒ}

with

‖ \hat{M} ‖_{ℒ} < ‖ B_{1} ‖_{ℒ}

during our computations, then we start the process of basis reduction, which is described below. Whenever we find an element in

\hat{ℒ} ∖ ℒ

, then we abort all computations and return this element (indeed, in that case, we may continue with the closure of the connected component in Closure).

Let $M = B_{1}$ , $X$ , etc. be as above. We start by computing the orbit of $\hat{𝒢}$ modulo $ℋ_{r - 1}$ for $Φ_{A_{r}}$ . Whenever we hit an element $P \neq 1$ (modulo $e^{ℒ}$ ) with $‖ B_{1} P B_{1}^{- 1} P^{- 1} ‖_{ℒ} < ‖ B_{1} ‖_{ℒ}$ or $‖ P ‖_{ℒ} < ‖ B_{1} ‖_{ℒ}$ , then we start the process of basis reduction. Otherwise, we obtain a finite orbit, together with a finite number of matrices by which we have to extend $ℋ_{r - 1}$ . We keep doing this using the same method for $ℋ_{r - 1}$ until $ℋ_{1}$ .

At the end, we still have to show how to extend $ℋ_{0}$ with a new matrix $\tilde{N}$ . Now recursive application of the algorithm to $\tilde{ℋ} = ℋ_{0} / e^{ℒ^{'}}$ and $\tilde{N}$ yields a sorted basis ${\tilde{B}}_{1}, \dots, {\tilde{B}}_{\tilde{m}}$ . When keeping track of the corresponding powers of $e^{X}$ during the computations, we also obtain a finite system of generators for $\hat{𝒢} \cap e^{𝔽 X}$ . Using g.c.d. computations we either obtain a minimal generator ${\hat{B}}_{1}$ or a new element in the connected component. In the first case, we return $({\hat{B}}_{1}, {\tilde{B}}_{2}, \dots, {\tilde{B}}_{\tilde{m}})$ if $‖ {\hat{B}}_{1} ‖_{ℒ} < ‖ {\tilde{B}}_{2} ‖_{ℒ}$ and apply basis reduction otherwise.

Basis reduction

Let

B_{1}, \dots, B_{m}

be in

𝒢

with

‖ B_{1} ‖_{ℒ} ⩽ \dots ⩽ ‖ B_{m} ‖_{ℒ}

. We call

(B_{1}, \dots, B_{m})

a raw basis. In the above algorithms, raw bases occur when we are given an ordered basis

(B_{2}, \dots, B_{m})

for

𝒢

, and we find a new element

B_{1}

with

‖ B_{1} ‖_{ℒ} < ‖ B_{2} ‖_{ℒ}

Using the above base extension procedure, we may transform a raw basis $(B_{1}, \dots, B_{m})$ into a basis for $𝒢$ : starting with $(B_{1})$ , we successively add $B_{2}, \dots, B_{m}$ . However, it is more efficient to reduce $(B_{1}, \dots, B_{m})$ first. More precisely, let us now describe a procedure which tries to replace $(B_{1}, \dots, B_{m})$ by a better raw basis $({\tilde{B}}_{1}, \dots, {\tilde{B}}_{\tilde{m}})$ , with $⟨ {\tilde{B}}_{1}, \dots, {\tilde{B}}_{\tilde{m}} ⟩ = ⟨ B_{1}, \dots, B_{m} ⟩$ , and whose elements are closer to identity. Of course, we may always return the original basis if a better one could not be found.

We first test whether all basis elements are roots of unity modulo $ℒ$ . If not, then we found a new element in the connected component. We next test whether there exist $i, j$ with $‖ B_{i} B_{j} B_{i}^{- 1} B_{j}^{- 1} ‖_{ℒ} < ‖ B_{1} ‖_{ℒ}$ , in which case we keep adding the smallest such commutator to the basis. Whenever this stops, we write $B_{1} = e^{X_{1}}, \dots, B_{m} = e^{X_{m}}$ with $X_{1}, \dots, X_{m} \in ℒ^{⊥}$ and consider all lattice reductions $X_{i} \leftarrow X_{i} + k X_{j} (k \in ℤ)$ proposed by the LLL-algorithm in the commutative vector space $ℒ^{⊥}$ . Whenever $0 < ‖ B_{i} B_{j}^{k} ‖_{ℒ} < ‖ B_{i} ‖$ , for one such reduction, then we perform the corresponding reduction $B_{i} \leftarrow B_{i} B_{j}^{k}$ on our basis and keep repeating the basis reduction process.

The general case

We still have to show how to deal with the case when

𝒢

is not included in the connected component

e^{𝒩}

of the normalizer of

e^{ℒ}

{Mat}_{n} (𝔽)

. In that case, we start with the computation of a basis for

𝒩

, using linear algebra. Since

e^{𝒩} \cap 𝒢

is a normal subgroup of

𝒢

, we have

𝒢 ≅ (𝒢 / e^{𝒩}) (e^{𝒩} \cap 𝒢)

. Now we have explained above how to compute with elements in

e^{𝒩} \cap 𝒢

. If

𝒩 ⊋︀ ℒ

, then may use recursion for computations in the finite group

𝒢 / e^{𝒩}

. If

𝒩 = ℒ

, then elements in

𝒢 / e^{𝒩}

have necessarily small order, so we simply list the elements of

𝒢 / e^{ℒ}

5.Conclusion and final notes

We hope that we provided convincing evidence that analytic methods may be used for the efficient computation of differential Galois groups and related problems like the factorization of linear differential operators.

The two main remaining challenges are the concrete implementation of the algorithms presented here (as part of a more general library for the computation with analytic functions such as [vdHea05]) and the development of a priori or a posteriori methods for ensuring the correctness of the computed result. Some ideas into this direction are as follows:

Use theoretical bounds on the number of connected components of the computed Galois group and related bounds on the sizes of the basis elements in EH2 and EH3. See [DJK03, Section 3.2] for some results.
Use the classification theory for algebraic groups in order to gather more information about the computed Galois group $𝒢$ . In particular, it is useful to compute the radical (or unipotent radical) of $𝒢$ , thereby reducing the study of $𝒢$ to the study of a finite group, a semisimple (or reductive) group and a solvable (or unipotent) group [Hum81, page 125]. We refer to [dG00] for computational aspects of the corresponding Lie algebras.
Use the classical theory of invariant subspaces in symmetric products or exterior powers as an a posteriori correctness check and search for an effective version of Chevalley's theorem [Hum81, Theorem 11.2]. One may start with generalizing [vHW97, CS98] and notice that a better knowledge of the Galois group $𝒢$ helps to further restrict the number of monomials (i.e. “generalized exponents”) to be considered. Indeed, if $ℋ$ is an arbitrary algebraic subgroup of $𝒢$ , for which the ring of invariants is easy to compute, then the invariants for $𝒢$ must be searched in this ring. Also, their are known algorithms for computing the invariants for certain types of algebraic groups, like linearly reductive groups [Der99].
The representation for algebraic groups $𝒢$ we used in section 4 is efficient for computations (we merely do linear algebra in dimension $n^{2}$ , lattice reduction and computations with small finite groups). Nevertheless, it may be interesting to reconstruct the algebraic equations for $𝒢$ and search for equations which are particularly sparse with respect to suitably chosen coordinates. For instance, a big cyclic group admits a particularly nice (resp. large) Gröbner basis w.r.t. well chosen (resp. badly chosen) coordinates. Conversely, it may be interesting to switch back from a Gröbner basis representation to our representation.
Carefully identify those parts of the algorithm which either prove or disprove certain matrices to belong to the Galois group. For instance, we know that all Stokes matrices are unipotent. Given a non-zero transcendental number $λ$ , we may then reliably conclude that a Stokes matrix of the form $(\begin{array}{cc} 1 & λ \\ 0 & 1 \end{array})$ generates the group ${(\begin{array}{cc} 1 & α \\ 0 & 1 \end{array}) : α \in 𝕂}$ .
An interesting idea to get rid of the transcendental part of the computations might be to quotient the values of the functions in our basis $𝒉$ of solutions by the action of the Galois group. For instance, if $z_{0}$ and $z_{1}$ are close regular points in $𝕂$ , is it true that the orbit of $𝒉^{z_{0}} (z_{1})$ under the action of the Galois group necessarily contains a point in $𝕂^{n}$ ? This is clearly the case for finite Galois groups and the full Galois group, as well as for the equations $f^{'} = f$ and ${(z f^{'})}^{'} = 0$ . More generally, as soon as $𝒉^{z_{0}} (z_{1})$ becomes more transcendental, its orbit under the action of the Galois group becomes larger, so the likelihood of finding a point in the intersection with $𝕂^{n}$ increases.

Besides the above ideas for improving the algorithms, this paper also raises a few other interesting questions:

Are there more efficient approaches for the reconstruction of elements in $𝕂$ in section 3.4, both in the cases when $𝕂 = ℚ^{alg}$ and when $𝕂$ is more general? Also, as pointed out above, we may want to reconstruct equations for $𝒢$ from the variety.
Does there exists an efficient membership test in section 4.4 which does not rely on probabilistic arguments?
Can the approach of section 4 be adapted to the computation of a “basis” for the usual topological closure of a finitely generated matrix group?

Of course, a better mastering of the algorithms in this paper may also lead to more efficient algorithms for other computations which rely on differential Galois theory, like the computation of Liouvillian or other forms of solutions. More generally, our algorithms may be used for other computations with algebraic matrix groups over $ℂ$ and other fields of characteristic $0$ . We also expect all results to generalize to holonomic systems of linear partial differential equations.

Acknowledgment

The author would like to thank J.-Y. Hée, W. de Graaf, F. Zara, J. Écalle and the referees for several helpful comments and references.

Bibliography

[BB85] D. Bertrand and F. Beukers. équations différentielles linéaires et majorations de multiplicités. Ann. Sci. de l'École Norm. Sup., 28(4-5):473–494, 1985.

[Bek94] E. Beke. Die Irreduzibilität der homogenen linearen Differentialgleichungen. Math. Ann., 45, 1894.

[Ber95] D. Bertrand. Minimal heights and polarizations on group varieties. Duke Math. J., 80(1):223–250, 1995.

[Bor91] A. Borel. Linear algebraic groups. Springer-Verlag, 2nd edition, 1991.

[Bra91] B.L.J. Braaksma. Multisummability and Stokes multipliers of linear meromorphic differential equations. J. Diff. Eq, 92:45–75, 1991.

[Bra92] B.L.J. Braaksma. Multisummability of formal power series solutions to nonlinear meromorphic differential equations. Ann. Inst. Fourier de Grenoble, 42:517–540, 1992.

[CC90] D.V. Chudnovsky and G.V. Chudnovsky. Computer algebra in the service of mathematical physics and number theory (computers in mathematics, stanford, ca, 1986). In Lect. Notes in Pure and Applied Math., volume 125, pages 109–232, New-York, 1990. Dekker.

[Clu04] T. Cluzeau. Algorithmique modulaire des équations différentielles linéaires. PhD thesis, Université de Limoges, 2004.

[CNP93] B. Candelberger, J.C. Nosmas, and F. Pham. Approche de la résurgence. Actualités mathématiques. Hermann, 1993.

[CS98] É. Compoint and M. Singer. Computing Galois groups of completely reducible differential equations. JSC, 11:1–22, 1998.

[Der99] H. Derksen. Computation of reductive group invariants. Adv. in Math., 141:366–384, 1999.

[dG00] W. de Graaf. Lie Algebras: Theory and Algorithms, volume 56 of North Holland Mathematical Library. Elsevier science, 2000.

[Dix71] J.D. Dixon. The structure of linear groups. Van Nostrand Reinhold Company, 1971.

[DJK03] H. Derksen, E. Jaendel, and P. Koiran. Quantum automata and algebraic groups. Technical Report 2003-39, LIP, École Norm. Sup. de Lyon, 2003. Presented at MEGA 2003; to appear in JSC.

[É85] J. Écalle. Les fonctions résurgentes I–III. Publ. Math. d'Orsay 1981 and 1985, 1985.

[É87] J. Écalle. L'accélération des fonctions résurgentes (survol). Unpublished manuscript, 1987.

[É92] J. Écalle. Introduction aux fonctions analysables et preuve constructive de la conjecture de Dulac. Hermann, collection: Actualités mathématiques, 1992.

[É93] J. Écalle. Six lectures on transseries, analysable functions and the constructive proof of Dulac's conjecture. In D. Schlomiuk, editor, Bifurcations and periodic orbits of vector fields, pages 75–184. Kluwer, 1993.

[Fab85] E. Fabry. Sur les intégrales des équations différentielles linéaires à coefficients rationnels. PhD thesis, Paris, 1885.

[Hum81] J.E. Humphreys. Linear algebraic groups. Graduate Texts in Math. Springer, 1981.

[Kap57] I. Kaplansky. An introduction to differential algebra. Hermann, 1957.

[Kol73] E.R. Kolchin. Differential algebra and algebraic groups. Academic Press, New York, 1973.

[LLL82] A.K. Lenstra, H.W. Lenstra, and L. Lovász. Factoring polynomials with rational coefficients. Math. Ann., 261:515–534, 1982.

[Mas88] D. Masser. Linear relations on algebraic groups. In A. Baker, editor, New advances in transendence theory, pages 248–262. Cambridge Univ. Press, 1988.

[Men96] F. Menous. Les bonnes moyennes uniformisantes et leur application à la resommation réelle. PhD thesis, Université Paris-Sud, France, 1996.

[Mit96] C. Mitschi. Differential Galois groups of confluent generalized hypergeometric equations: an approach using stokes multipliers. Pac. J. Math., 176(2):365–405, 1996.

[MO95] Scott H. Murray and E. A. O'Brien. Selecting base points for the Schreier-Sims algorithm for matrix groups. J.S.C., 18:577–584, 1995.

[Moe73] R. Moenck. Fast computation of gcds. In Proc. of the 5th ACM Annual Symposium on Theory of Computing, pages 142–171, New York, 1973. ACM Press.

[MR91] J. Martinet and J.-P. Ramis. Elementary acceleration and multisummability. Ann. Inst. Henri Poincaré, 54(4):331–401, 1991.

[PW02] Victor Y. Pan and Xinmao Wang. Acceleration of euclidean algorithm and extensions. In Teo Mora, editor, Proc. ISSAC '02, pages 207–213, Lille, France, July 2002.

[Ram85] J.-P. Ramis. Phénomène de Stokes et filtration Gevrey sur le groupe de Picard-Vessiot. Notes aux CRAS, 301(I/5):165–167, 1985.

[Rit50] J.F. Ritt. Differential algebra. Amer. Math. Soc., New York, 1950.

[Sch95] L. Schlesinger. Handbuch der Theorie der linearen Differentialgleichungen, volume I. Teubner, Leipzig, 1895.

[Sch97] L. Schlesinger. Handbuch der Theorie der linearen Differentialgleichungen, volume II. Teubner, Leipzig, 1897.

[Sim70] C.C. Sims. Computational problems in abstract algebra, chapter Computational methods in the study of permutation groups, pages 169–183. Pergamon press, Oxford, 1970.

[Sim71] C.C. Sims. Determining the conjugacy classes of permutation groups. In G. Birkhoff and M. Hall Jr., editors, Computers in algebra and number theory, volume 4 of Proc. A.M.S., pages 191–195, New York, 1971. A.M.S.

[SU93] M. Singer and F. Ulmer. Galois groups of second and third order linear differential equations. J.S.C., 16:9–36, 1993.

[vdH99] J. van der Hoeven. Fast evaluation of holonomic functions. TCS, 210:199–215, 1999.

[vdH01a] J. van der Hoeven. Complex transseries solutions to algebraic differential equations. Technical Report 2001-34, Univ. d'Orsay, 2001.

[vdH01b] J. van der Hoeven. Fast evaluation of holonomic functions near and in singularities. JSC, 31:717–743, 2001.

[vdH02] J. van der Hoeven. Relax, but don't be too lazy. JSC, 34:479–542, 2002.

[vdH03] J. van der Hoeven. Majorants for formal power series. Technical Report 2003-15, Université Paris-Sud, Orsay, France, 2003.

[vdH04] J. van der Hoeven. Computations with effective real numbers. Technical Report 2004-02, Université Paris-Sud, Orsay, France, 2004. To appear in TCS.

[vdH05a] J. van der Hoeven. Effective complex analysis. J.S.C., 39:433–449, 2005.

[vdH05b] J. van der Hoeven. Efficient accelero-summation of holonomic functions. Technical Report 2005-54, Université Paris-Sud, Orsay, France, 2005. Submitted to JSC.

[vdHea05] J. van der Hoeven et al. Mmxlib: the standard library for Mathemagix, 2002–2005. http://www.mathemagix.org/mmxweb/web/welcome-mml.en.html.

[vdP95] M. van der Put. Differential equations modulo $p$ . Compositio Mathematica, 97:227–251, 1995.

[vdPS03] M. van der Put and M. Singer. Galois Theory of Linear Differential Equations, volume 328 of Grundlehren der mathematischen Wissenschaften. Springer, 2003.

[vH96] M. van Hoeij. Factorization of linear differential operators. PhD thesis, Univ. of Nijmegen, The Netherlands, 1996.

[vH97] M. van Hoeij. Factorization of differential operators with rational functions coefficients. J.S.C., 24:537–561, 1997.

[vHW97] M. van Hoeij and J.A. Weil. An algorithm for computing invariants of differential Galois groups. J. Pure Appl. Algebra, 117–118:353–379, 1997.

1.Introduction

2.Preliminaries

2.1.Notations

2.2.Differential Galois groups

2.3.Monodromy

2.4.The process of accelero-summation

The Borel transform

Accelerations

The Laplace transform

2.5.The Stokes phenomenon

2.6.Effective complex numbers

3.Factoring linear differential operators

3.1.Factoring L and invariant subspaces under 𝒢L,𝒉

3.2.A lemma from linear algebra

3.3.Computation of non-trivial invariant subspaces

Good candidate vectors 𝒗

The 𝕂-algebra generated by ℳ

ℳ-splittings

Refining ℳ-splittings

3.4.Factoring linear differential operators

4.Computing differential Galois groups

4.1.Introduction

4.2.The algebraic group generated by a diagonal matrix

4.3.The algebraic group generated by a single matrix

4.4.Membership testing for the connected component

4.5.Computing the closure of ℳ

4.6.Fast computations with the connected components

4.7.Non-commutative lattice reduction

Orthogonal projection

Representation of the elements in ℋ

Adding new elements to a basis

Basis reduction

The general case

5.Conclusion and final notes

Acknowledgment

Bibliography

3.1.Factoring $L$ and invariant subspaces under $𝒢_{L, 𝒉}$

Good candidate vectors $𝒗$

The $𝕂$ -algebra generated by $ℳ$

$ℳ$ -splittings

Refining $ℳ$ -splittings

4.5.Computing the closure of $ℳ$

Representation of the elements in $ℋ$