Algebraic solutions of linear differential equations: An arithmetic approach

By Alin Bostan, Xavier Caruso, and Julien Roques

Abstract

Given a linear differential equation with coefficients in , an important question is to know whether its full space of solutions consists of algebraic functions, or at least if one of its specific solutions is algebraic. After presenting motivating examples coming from various branches of mathematics, we advertise in an elementary way a beautiful local-global arithmetic approach to these questions, initiated by Grothendieck in the late sixties. This approach has deep ramifications and leads to the still unsolved Grothendieck–Katz -curvature conjecture.

1. Context, motivation, and basic examples

In this text we consider linear differential equations (LDEs) of order

where the are known rational functions in , with not identically zero and is an unknown “function”. In many applications, the desired solution is a formal power series with coefficients in . Therefore, in what follows, when we write “function” we actually mean an element of unless otherwise specified. We will say that a function is differentially finite (in short, D-finite) if it satisfies a linear differential equation like Equation 1.

A function is called algebraic if it is algebraic over , that is, if satisfies a polynomial equation of the form , for some . Otherwise, is called transcendental. The simplest algebraic functions are polynomials in , closely followed by rational power series: these are rational functions in that have no pole at and therefore admit a Taylor expansion around the origin. A little more general are th roots of rational power series, such as . In all these three cases, is clearly D-finite and satisfies a linear differential equation of order .

Many other examples of interesting functions that might or might not be solutions of linear differential equations arise from combinatorics. A basic example is given by the Catalan numbers.

Example 1.1 (Catalan numbers).

By definition, a Dyck path is a path drawn in the quarter plane that starts at , consists of steps (directed by the vector ) or (directed by the vector ) and finally ends on the -axis (see Figure 1).

Let be the number of Dyck paths ending at ; we say that such paths have length . For instance, since there is a single Dyck path ending at , namely , while since there are two Dyck paths ending at , namely and . We use the convention that . We notice that any Dyck path of length can be written uniquely as the concatenation of

(1)

a step ,

(2)

a Dyck path of length (translated by ),

(3)

a step and

(4)

a Dyck path of length .

It follows that the sequence satisfies the following nonlinear recurrence relation:

If denotes the generating function of the , i.e., , the previous relation translates to the algebraic identity

(the summand comes from the fact that ). Therefore, is algebraic and one can even solve equation Equation 2 and get the closed formula . It is worth noting that, starting from the algebraic relation Equation 2, one can also derive a linear differential equation satisfied by . Indeed, differentiating Equation 2, one gets . Therefore,

The right-hand side in the latter expression can be further simplified using equation Equation 2 again. Notice that

and, consequently,

after replacing two times by .

Finally, one obtains the inhomogeneous differential equation

From this, we can derive new interesting information about the sequence . For instance, it easily implies the simpler recurrence relation for all , from which we further derive the closed formula . Using Stirling’s formula, we also deduce the asymptotic estimate .

The previous example shows that being able to write down an equation (either algebraic or differential) for a generating series can help a lot in studying its coefficients. Of course, obtaining explicit closed formulas (as we did for the Catalan numbers) will not be possible in general; however, meaningful information (such as the asymptotic growth of the coefficients) can often be extracted from the equation. Besides, in many cases it turns out that the algebraicity of a generating series is the mirror of a (sometimes hidden) “algebraic” structure on the combinatorial side, which often takes the form of a recursive tree structure: in Example 1.1, for instance, a Dyck path can be decomposed as a concatenation of smaller Dyck paths, which themselves can be decomposed similarly, etc. We refer to Reference 25 for a much more detailed discussion on this topic (including many more examples).

In Example 1.1, we transformed an algebraic equation into a differential equation. It is actually a general fact and an old result, already known by Abel, that any algebraic function is D-finite. Precisely if satisfies an algebraic equation with of degree  in , then also satisfies a differential equation like Equation 1 of order bounded from above by . This follows easily from the following reasoning. By differentiating with respect to  and by using the chain rule, we obtain the equality

Here and in what follows, we denote by the derivative of with respect to . Therefore, if is assumed to be a polynomial of minimal degree in  satisfied by , then is a nonzero function in , and hence is a rational function in . By using the equation again, it is easy to see that any rational function in  can be re-written as a polynomial of degree at most  in . In other terms, the derivative lives in the -vector space generated by . Similarly, the same holds for all derivatives , and hence these elements must satisfy a nontrivial linear relation over ; any such relation yields a linear differential equation Equation 1 of order at most . Observe that the same reasoning also proves the existence of an inhomogeneous linear differential equation of order at most  for .

A naive though very natural question is whether the converse of Abel’s result holds: is every D-finite function algebraic? The answer is negative, already for differential equations of order , as the following example shows.

Example 1.2.

The function , solution of , is transcendental. Here is a purely algebraic proof. Let us assume by contradiction that satisfies a polynomial equation, of minimal degree , of the form for some rational functions . By differentiating this equality with respect to  and using , we get a new degree- equation , which, by minimality, is equal the former up to a factor . In other words, for all . In particular, , which implies that . (Indeed, if for two coprime polynomials with , then divides , hence divides and . Thus , which implies and .) The nullity of now implies that satisfies a polynomial equation of degree , which contradicts the minimality of .

The reader could object that in Example 1.2 we were probably lucky, because the differential equation of is so simple, being of order 1 with constant coefficients. Indeed, in the particular case of the exponential function, there are many other ad hoc transcendence proofs, based on various branches of mathematics. For instance, a direct analytic argument is that, viewed as a complex analytic function, any nonpolynomial algebraic function needs to have a finite (and positive) radius of convergence, while is entire (that is, analytic in the whole complex plane). Another proof is that cannot satisfy a nontrivial algebraic equation, since by otherwise specializing that equation at we would find that the number is an algebraic number, a statement known be to false since Hermite (1873). One could qualify this last proof as “cheating”, since it is intuitively clear that proving transcendence of functions should be easier than proving transcendence of numbers.

A systematic and very useful analytic way to establish functional transcendence is Flajolet’s criterion Reference 46, Criterion D (see also Reference 47, Theorem VII.8 and Reference 67, §2.3). It is a consequence of the classical Newton–Puiseux theorem on fractional (Puiseux) series expansion of algebraic functions and on Darboux’s transfer results from the local behavior of around its singularities to the asymptotic behavior of its coefficient sequence . Before stating it, we recall the definition of the gamma function

where the variable is a complex number with positive real part. The gamma function interpolates the factorial in the sense that for any positive integer .

Proposition 1.3 (Reference 46, Theorems A and D).

Let be an algebraic nonpolynomial function. Then has a finite number of singularities, a finite nonzero radius of convergence, and its coefficient sequence is such that

where , , , , and with .

The most useful form of the criterion is Corollary 1.4.

Corollary 1.4 (“Flajolet’s criterion”).

If and with either , or , or , then is transcendental.

As an example of application, Proposition 1.3 immediately implies that is transcendental, since the sequence is not of the form Equation 3 (or, since the radius of convergence of is infinite).

At this point, we can ask ourselves: is there a purely arithmetic proof of the transcendence of ? This question can be seen as the starting point of the present article, whose main aim is precisely to advertise a very beautiful number-theoretic approach to algebraicity of solutions of linear differential equations. More generally, we can raise the following question.

Question 1.5.

Is there any number-theoretic way to recognize whether the differential equation Equation 1 admits only algebraic solutions in its solution space?

Nicely enough, the answer to this question is positive, for two distinct but related reasons. Let us first explain them a bit in the case of the exponential function . The first arithmetic proof of the transcendence of is based on the following result, which, in rough terms, asserts that the coefficients of algebraic functions are “almost integral”.

Proposition 1.6 (“Eisenstein’s criterion” (1852)).

If the function

is algebraic, then there exists such that . In particular, only a finite number of prime numbers can divide the denominators of the coefficients .

Since in the factorial sequence , obviously, all prime numbers appear as divisors, and Proposition 1.6 immediately implies that is transcendental.

To formulate the second arithmetic proof of the transcendence of , we will need a little bit of additional vocabulary. The differential equation Equation 1 can be rewritten in the compact form , where is the linear differential operator

We denote by the set of such linear differential operators. For convenience, we also allow the trivial operator, in which all coefficients are zero. The elements of act on functions in by letting the variable act through the differentiation . The set is then endowed with a structure of noncommutative ring where the addition is the usual one but the multiplication is twisted according to the following rule, reminiscent of Leibniz’s differentiation rule:

Although the ring is noncommutative, it shares many properties with the classical commutative ring of polynomials . First, one has a well-defined notion of degree: the degree of the nonzero operator in Equation 4 is the order of the corresponding differential equation Equation 1, that is, the largest integer  such that . We will denote it by in what follows. Second, the ring admits an Euclidean division.

Proposition 1.7.

The ring is right Euclidean, i.e., for all with , there exist and in such that and . Moreover, the pair is unique with these properties.

Using these notions, we can now formulate a very basic but important arithmetic result.

Proposition 1.8.

If all solutions of Equation 1 are algebraic functions, then for all but a finite number of prime numbers , the remainder of the right Euclidean division of by has all its coefficients divisible by .

Proof.

By Eisenstein’s criterion (Proposition 1.6), there exists a basis of algebraic solutions of and an integer such that is in for all . This implies that for all but a finite number of prime numbers (namely, the ones dividing and the denominators of ) the power series are in , i.e., zero modulo . Thus, writing with of order at most , we have for all . Writing , we deduce that the vector times the Wronskian matrix of the is zero modulo . Since the Wronskian matrix is invertible (because the form a basis of solutions of ), it is also invertible modulo  for all but a finite number of prime numbers , and thus the are all  modulo  for any such prime .

Example 1.9.

The generating function of the Catalan numbers satisfies the differential equation , which is easily deduced, either from the inhomogeneous differential equation of order 1 in Example 1.1, or directly from the recurrence . The associated differential operator is , and the remainders of the right Euclidean divisions of by for are