<figure><img src="image_1.png" /></figure>

HAL
open science

# Algebraic solutions of linear differential equations: an arithmetic approach

Alin Bostan, Xavier Caruso, Julien Roques

► To cite this version:

Alin Bostan, Xavier Caruso, Julien Roques. Algebraic solutions of linear differential equations: an arithmetic approach. 2023. hal-04065092

HAL Id: hal-04065092

https://hal.science/hal-04065092

Preprint submitted on 11 Apr 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.
# Algebraic solutions of linear differential equations: An arithmetic approach

Alin Bostan, Xavier Caruso, Julien Roques

<figure><img src="image_1.png" /></figure>

## To cite this version:

Alin Bostan, Xavier Caruso, Julien Roques. Algebraic solutions of linear differential equations: An arithmetic approach. Bulletin of the American Mathematical Society, 2024, 61 (4), pp.609-658. 10.1090/bull/1835. hal-04065092v2

HAL Id: hal-04065092

https://hal.science/hal-04065092v2

Submitted on 4 Jan 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Algebraic solutions of linear differential equations:
an arithmetic approach

Alin Bostan*

Xavier Caruso†

Julien Roques‡

April 11, 2023

Abstract

Given a linear differential equation with coefficients in $Q(x)$, 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 $p$-curvature conjecture.

Contents

<table><tr><td>1 Context, motivation and basic examples</td><td>2</td></tr><tr><td>2 Several natural differential equations have algebraic solutions</td><td>6</td></tr><tr><td>2.1 Examples from Special functions: Hypergeometric functions</td><td>7</td></tr><tr><td>2.2 Examples from Algebra: Diagonals</td><td>10</td></tr><tr><td>2.3 Examples from Combinatorics: Walks in the Quarter Plane</td><td>12</td></tr><tr><td>2.4 Examples from Number Theory</td><td>16</td></tr><tr><td>3 Grothendieck's conjecture and the p-curvature</td><td>18</td></tr><tr><td>3.1 The case of equations of order 1</td><td>18</td></tr><tr><td>3.2 Grothendieck's conjecture</td><td>26</td></tr><tr><td>3.3 Computation of the p-curvature</td><td>32</td></tr><tr><td>3.4 Algebraicity and integrality</td><td>38</td></tr></table>

<footnote>*Inria, Université Paris-Saclay, 1 rue Honoré d'Estienne d'Orves, 91120 Palaiseau, France.</footnote>

<footnote>†CNRS; Université de Bordeaux, IMB; Inria Bordeaux Sud-Ouest, LFANT, 351 cours de la Libération, 33405 Talence, France.</footnote>

<footnote>‡Université de Lyon, Université Claude Bernard Lyon 1, CNRS UMR 5208, Institut Camille Jordan, 43 Bd du 11 Novembre 1918, 69622 Villeurbanne, France.</footnote>
# Algebraic solutions of linear differential equations: an arithmetic approach

Alin Bostan*

Xavier Caruso†

Julien Roques‡

August 26, 2024

## Abstract

Given a linear differential equation with coefficients in $Q(x)$, 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 $p$-curvature conjecture.

## Contents

<table><tr><td>1</td><td>Context, motivation and basic examples</td><td>2</td></tr><tr><td>2</td><td>Several natural differential equations have algebraic solutions</td><td>9</td></tr><tr><td>2.1</td><td>Examples from Special functions: Hypergeometric functions</td><td>10</td></tr><tr><td>2.2</td><td>Examples from Algebra: Diagonals</td><td>13</td></tr><tr><td>2.3</td><td>Examples from Combinatorics: Walks in the Quarter Plane</td><td>16</td></tr><tr><td>2.4</td><td>Examples from Number Theory</td><td>19</td></tr><tr><td>3</td><td>Grothendieck's conjecture</td><td>21</td></tr><tr><td>3.1</td><td>The case of equations of order 1</td><td>21</td></tr><tr><td>3.2</td><td>The general case</td><td>29</td></tr><tr><td>3.3</td><td>Progresses toward Grothendieck's conjecture</td><td>33</td></tr><tr><td>3.4</td><td>A formal parallel with Kronecker's theorem</td><td>35</td></tr></table>

<footnote>*Inria, Université Paris-Saclay, 1 rue Honoré d'Estienne d'Orves, 91120 Palaiseau, France.</footnote>

<footnote>†CNRS; Université de Bordeaux, IMB; Inria Bordeaux Sud-Ouest, CANARI, 351 cours de la Libération, 33405 Talence, France.</footnote>

<footnote>‡Université de Lyon, Université Claude Bernard Lyon 1, CNRS UMR 5208, Institut Camille Jordan, 43 Bd du 11 Novembre 1918, 69622 Villeurbanne, France.</footnote>

<footnote n="2020">2020 Mathematics Subject Classification: Primary: 11-02; Secondary: 12H05, 33C20. 12H25, 34A20, 34A30, 34M15, 05A15, 68W30.</footnote>
# 1 Context, motivation and basic examples

We consider in this text linear differential equations of order r

$$a_{r}(x)y^{(r)}(x) + a_{r-1}(x)y^{(r-1)}(x) + \dots + a_{1}(x)y'(x) + a_{0}(x)y(x) = 0, \quad (1)$$

where the $a_i$'s are known rational functions in $Q(x)$ and $y(x)$ is an unknown “function”. In many applications, the sought solution $y(x)$ is a formal power series with coefficients in $Q$. Therefore, in what follows, when we write “function” we actually mean an element of $Q[[x]]$ unless otherwise specified. We will say that a function $y \in Q[[x]]$ is differentially finite (in short, D-finite) if it satisfies a linear differential equation like (1).

A function $y \in Q[[x]]$ is called algebraic if it is algebraic over $Q(x)$, that is, if $y(x)$ satisfies a polynomial equation of the form $P(x, y(x)) = 0$, for some $P \in Q[x, y] \setminus \{0\}$. Otherwise, $y(x)$ is called transcendental. The simplest algebraic functions are polynomials in $Q[x]$, closely followed by rational power series: these are rational functions in $Q(x)$ that have no pole at $x = 0$ and therefore admit a Taylor expansion around the origin. A little more general are N-th roots of rational power series, such as $y(x) = 1/\sqrt[\sqrt{1-x}]{1-x}$. In all these three cases, $y(x)$ is clearly D-finite and satisfies a linear differential equation of order $r = 1$.

More generally, it is an old result (already known by Abel!) that any algebraic function is D-finite. Precisely, if $y(x)$ satisfies an algebraic equation $P(x, y(x)) = 0$ with $P$ of degree $n$ in $y$, then $y(x)$ also satisfies a differential equation like (1) of order $r$ upper bounded by $n$. This follows easily by the following reasoning. By differentiating $P(x, y(x)) = 0$ with respect to $x$ and by using the chain rule, we obtain the equality

$$P_x(x, y(x)) + y'(x)P_y(x, y(x)) = 0.$$

Here and in what follows we denote by $P_x$ the derivative $\partial P/\partial x$ of $P$ with respect to $x$. Therefore, if $P$ is assumed to be a polynomial of minimal degree in $y$ satisfied by $y(x)$, then $P_y(x, y(x))$ is a nonzero function in $Q[[x]]$, and hence $y'(x) = -P_x(x, y(x))/P_y(x, y(x))$ is a rational function in $y(x)$. By using again the equation $P(x, y(x)) = 0$, it is easy to see (exercise!) that any rational function in $y(x)$ can be re-written as a polynomial of degree at most $n-1$ in $y(x)$. In other terms, the derivative $y'(x)$ lives in the $Q(x)$-vector space generated by $1, y(x), \dots, y(x)^{n-1}$. The same similarly holds for all derivatives $y(x), y'(x), y''(x), \dots, y^{(n)}(x)$, and hence these elements must satisfy a nontrivial linear relation over $Q(x)$; any such relation yields a differential equation (1) of order at most $n$. Observe that the same reasoning also proves the existence of an inhomogeneous linear differential equation of order at most $n-1$ for $y(x)$.

**Example 1.1 (Catalan numbers).** Consider walks on the half-line $\mathbb{N}$ that start from 0 and consist of unit steps $\pm 1$, and denote by $C_k$ the number of such walks of length $k$ (the length counts the number of used steps). One can prove that $C_k = \frac{1}{k+1}\binom{2k}{k}$ (exercise!) and that $y(x) = \sum_{k \ge 0} C_k x^k$ satisfies the algebraic equation $P(x, y(x)) = 0$ where $P(x, y) = xy^2 - y + 1$. Then,

$$y'(x) = \frac{y(x)^2}{1 - 2xy(x)} = \frac{(2x - 1)y(x) + 1}{x(1 - 4x)},$$

hence $y$ satisfies the inhomogeneous differential equation $(4x^2 - x)y'(x) + (2x - 1)y(x) + 1 = 0$.
<table>
  <tbody>
    <tr>
      <td>4</td>
      <td>About the computation of the p-curvature</td>
      <td>36</td>
    </tr>
    <tr>
      <td>4.1</td>
      <td>Operators of order 1</td>
      <td>36</td>
    </tr>
    <tr>
      <td>4.2</td>
      <td>Reading the p-curvature on the solutions</td>
      <td>37</td>
    </tr>
    <tr>
      <td>4.3</td>
      <td>Application to algorithmics</td>
      <td>39</td>
    </tr>
    <tr>
      <td>4.4</td>
      <td>Similarity class and characteristic polynomial</td>
      <td>41</td>
    </tr>
    <tr>
      <td>5</td>
      <td>Algebraicity and integrality</td>
      <td>42</td>
    </tr>
    <tr>
      <td>5.1</td>
      <td>Growth of denominators and p-curvatures</td>
      <td>42</td>
    </tr>
    <tr>
      <td>5.2</td>
      <td>An analytic perspective on the p-curvature</td>
      <td>45</td>
    </tr>
  </tbody>
</table>

# 1 Context, motivation and basic examples

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

$$a_r(x)y^{(r)}(x) + a_{r-1}(x)y^{(r-1)}(x) + \cdots + a_1(x)y'(x) + a_0(x)y(x) = 0, \quad (1)$$

where the $a_i$'s are known rational functions in $\mathbb{Q}(x)$, with $a_r$ not identically zero and $y(x)$ is an unknown “function”. In many applications, the desired solution $y(x)$ is a formal power series with coefficients in $\mathbb{Q}$. Therefore, in what follows, when we write “function” we actually mean an element of $\mathbb{Q}[[x]]$ unless otherwise specified. We will say that a function $y \in \mathbb{Q}[[x]]$ is *differentially finite* (in short, *D-finite*) if it satisfies a linear differential equation like (1).

A function $y \in \mathbb{Q}[[x]]$ is called *algebraic* if it is algebraic over $\mathbb{Q}(x)$, that is, if $y(x)$ satisfies a polynomial equation of the form $P(x, y(x)) = 0$, for some $P \in \mathbb{Q}[x, y] \setminus \{0\}$. Otherwise, $y(x)$ is called *transcendental*. The simplest algebraic functions are polynomials in $\mathbb{Q}[x]$, closely followed by rational power series: these are rational functions in $\mathbb{Q}(x)$ that have no pole at $x = 0$ and therefore admit a Taylor expansion around the origin. A little more general are $N$-th roots of rational power series, such as $y(x) = 1/\sqrt[\sqrt{1-x}](1-x)$. In all these three cases, $y(x)$ is clearly D-finite and satisfies a linear differential equation of order $r = 1$.

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 $\mathbb{N}^2$ that starts at (0, 0), consists of steps $\nearrow$ (directed by the vector (1, 1)) or $\searrow$ (directed by the vector (1, -1)) and finally ends on the $x$-axis (see Figure 1).

Let $C_n$ be the number of Dyck paths ending at $(2n, 0)$; we say that such paths have length $n$. For instance $C_1 = 1$ since there is a single Dyck path ending at (2, 0), namely $\nearrow-\searrow$, while $C_2 = 2$ since there are two Dyck paths ending at (4, 0), namely $\nearrow-\nearrow-\searrow-\searrow$ and $\nearrow-\searrow-\nearrow-\searrow$. We use the convention that $C_0 = 1$. We notice that any Dyck path of length $n+1$ can be written uniquely as the concatenation of (1) a step $\nearrow$, (2) a Dyck path of length $k-1$ (translated by (1, 1)), (3) a step $\searrow$ and (4) a Dyck path of length $n-k$. It follows that the sequence $(C_n)_{n \ge 0}$ satisfies the following nonlinear recurrence relation:

$$C_n = \sum_{k=1}^{n} C_{k-1}C_{n-k}, \quad \text{for all } n \ge 1.$$
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 $r = 1$, as the following example shows.

**Example 1.2.** The function $\exp(x) := \sum_{k>0} x^k/k!$, solution of $y' = y$, is transcendental. Here is a purely algebraic proof. Let us assume by contradiction that it satisfies a polynomial equation, of minimal degree $n \ge 1$, of the form $e^{nx} + \sum_{k=0}^{n-1} r_k(x)e^{kx} = 0$ for some rational functions $r_k \in \mathbb{Q}(x)$. By differentiating this equality with respect to $x$ and by using $\exp'(x) = \exp(x)$ we get a new degree-$n$ equation $ne^{nx} + \sum_{k=0}^{n-1} (r'_k(x) + kr_k(x))e^{kx} = 0$ which by minimality is the $n$-th multiple of the former. In other words, $r'_k(x) + kr_k(x) = nr_k(x)$ for all $k < n$. In particular, $r'_0(x) = nr_0(x)$, which implies $r_0(x) \equiv 0$ (indeed, if $r_0(x) = A(x)/B(x)$ for two coprime polynomials $A, B \in \mathbb{Q}[x]$ with $A'B - AB' = nAB$, then $B$ divides $AB'$, hence $B$ divides $B'$, thus $B' \equiv 0$; similarly, $A' \equiv 0$ and hence $nAB = 0$, which implies $A \equiv 0$). But the nullity of $r_0$ implies that $\exp(x)$ satisfies a polynomial equation of degree $n-1$, a contradiction.

The reader could object that in Example 1.2 we were probably lucky, because the differential equation of $\exp(x)$ 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, an analytic argument is that, viewed as a complex analytic function, any algebraic function needs to have a finite (and positive) radius of convergence, while $\exp(z)$ is entire (that is, analytic in the whole complex plane). Another proof is that $\exp(x)$ cannot satisfy a nontrivial algebraic equation, since otherwise by specializing that equation at $x = 1$ we would obtain that the number $e = \exp(1)$ 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.

At this point, we can ask ourselves: is there a purely arithmetic proof of the transcendence of $\exp(x)$? 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.3.** Is there any number-theoretic way to recognize whether the differential 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 $\exp(x) = \sum_{k \ge 0} x^k/k!$. The first arithmetic proof of the transcendence of $\exp(x)$ is based on the following result.

**Proposition 1.4** (“Eisenstein’s criterion” (1852)). If the function $y(x) = \sum_{k \ge 0} a_k x^k \in \mathbb{Q}[[x]]$ is algebraic, then there exists $N \in \mathbb{N} \setminus \{0\}$ such that $y(Nx) - y(0) \in \mathbb{Z}[[x]]$. In particular, only a finite number of prime numbers can divide the denominators of the coefficients $a_k$.

Since in the factorial sequence $(k!)_{k \ge 0}$ obviously all prime numbers appear as divisors, Proposition 1.4 immediately implies that $\exp(x)$ is transcendental.

To formulate the second arithmetic proof of the transcendence of $\exp(x)$, we will need a little bit of additional vocabulary. The differential equation (1) can be rewritten in the compact form $\mathcal{L}(y) = 0$, where $\mathcal{L}$ is the linear differential operator

$$ \mathcal{L} = a_r(x) \partial_x^r + a_{r-1}(x) \partial_x^{r-1} + \dots + a_1(x) \partial_x + a_0(x). \quad (2) $$
<figure><img src="image_3.png" /><figcaption>Figure 1: A Dyck path</figcaption></figure>

If $y(x)$ denotes the generating function of the $C_n$'s, i.e. $y(x) = \sum_{n=0}^{\infty} C_n x^n$, the previous relation translates to the algebraic identity

$$y(x) = 1 + x \cdot y(x)^2 \qquad (2)$$

(the summand 1 comes from the fact that $C_0 = 1$). Therefore $y(x)$ is algebraic and one can even solve equation (2) and get the closed formula $y(x) = \frac{1-\sqrt{1-4x}}{2x}$. It is worth noting that, starting from the algebraic relation (2), one can also derive a linear differential equation satisfied by $y(x)$. Indeed differentiating (2), one gets $y'(x) = y(x)^2 + 2x y(x) y'(x)$. Therefore:

$$y'(x) = \frac{y(x)^2}{1 - 2x y(x)}.$$

The right hand side in the latter expression can be further simplified using again equation (2). Indeed notice that

$$(1 - 2x y(x))^2 = 1 - 4x y(x) + 4x^2 y(x)^2 = 1 - 4x$$

and consequently

$$\frac{y(x)^2}{1 - 2x y(x)} = \frac{y(x)^2 \cdot (1 - 2x y(x))}{1 - 4x} = \frac{(y(x) - 1)(1 - 2x y(x))}{x(1 - 4x)} = \frac{2x y(x) - y(x) + 1}{x(1 - 4x)}$$

after replacing two times $y(x)^2$ by $\frac{y(x)-1}{x}$.

Finally, one obtains the inhomogeneous differential equation

$$(4x^2 - x)y'(x) + (2x - 1)y(x) + 1 = 0.$$

From this, we can derive new interesting information about the sequence $(C_n)_{n \ge 0}$. For instance, it easily implies the simpler recurrence relation $C_n = \frac{4n-2}{n+1} \cdot C_{n-1}$ for all $n \ge 1$, from which we further derive the closed formula $C_n = \frac{1}{n+1} \binom{2n}{n}$. Using Stirling's formula, we also deduce the asymptotic estimate $C_n \sim 4^n/\sqrt{\pi n^3}$.

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 be often extracted from the equation. Besides, in many cases it turns out that the
We denote by $\mathbb{Q}(x)\langle\partial_x\rangle$ the set of such linear differential operators. For convenience, we also allow the trivial operator, in which all coefficients $a_i(x)$ are zero. The elements of $\mathbb{Q}(x)\langle\partial_x\rangle$ act on functions in $x$ by letting the variable $\partial_x$ act through the differentiation $\frac{d}{dx}$. The set $\mathbb{Q}(x)\langle\partial_x\rangle$ 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 from Leibniz's differentiation rule:

$$ \forall r \in \mathbb{Q}(x), \quad \partial_x r(x) = r(x) \partial_x + r'(x). $$

Although the ring $\mathbb{Q}(x)\langle\partial_x\rangle$ is noncommutative, it shares many properties with the classical commutative ring of polynomials $\mathbb{Q}(x)[y]$. First, one has a well-defined notion of degree: the degree $\deg(\mathcal{L})$ of the nonzero operator $\mathcal{L}$ in (2) is the order $r$ of the corresponding differential equation (1), that is the largest integer $r$ such that $a_r(x) \neq 0$. Second, the ring $\mathbb{Q}(x)\langle\partial_x\rangle$ admits an Euclidean division.

**Proposition 1.5.** The ring $\mathbb{Q}(x)\langle\partial_x\rangle$ is left Euclidean, i.e., for all $A, B \in \mathbb{Q}(x)\langle\partial_x\rangle$ with $B \neq 0$, there exist $Q$ and $R$ in $\mathbb{Q}(x)\langle\partial_x\rangle$ such that $A = BQ + R$ and $\deg R < \deg B$. Moreover, the pair $(Q, R)$ is unique with these properties.

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

**Proposition 1.6 ("Cartier's lemma").** If all solutions of (1) are algebraic functions, then for all but a finite number of prime numbers $p$, the remainder of the left Euclidean division of $\partial_x^p$ by $\mathcal{L}$ has all its coefficients divisible by $p$.

**Example 1.7.** The generating function of the Catalan numbers, $y(x) = \sum_{k \ge 0} C_k x^k$, satisfies the differential equation $(4x^2 - x)y''(x) + (10x - 2)y'(x) + 2y(x) = 0$, which is easily deduced, either from the inhomogeneous differential equation of order 1 in Example 1.1, or directly from the recurrence $(k+2)C_{k+1} - (4k+2)C_k = 0$. The associated differential operator is $\mathcal{L} = (4x^2 - x)\partial_x^2 + (10x - 2)\partial_x + 2$, and the remainders of the left Euclidean divisions of $\partial_x^p$ by $\mathcal{L}$ for $p \in \{2, 3, 5\}$ are

$$ \partial_x^2 \mod \mathcal{L} = -\frac{2(5x-1)}{x(4x-1)}\partial_x - \frac{2}{x(4x-1)}, $$

$$ \partial_x^3 \mod \mathcal{L} = \frac{6(22x^2 - 9x + 1)}{x^2(4x-1)^2} \partial_x + \frac{6(6x-1)}{x^2(4x-1)^2}, $$

$$ \partial_x^5 \mod \mathcal{L} = \frac{120(386x^4 - 325x^3 + 110x^2 - 17x + 1)}{x^4(4x-1)^4} \partial_x + \frac{120(130x^3 - 69x^2 + 14x - 1)}{x^4(4x-1)^4}. $$

Note that indeed, we have $\partial_x^p \mod \mathcal{L} = 0$ modulo $p$, in the three cases.

**Proposition 1.6** will be discussed in more detail in §3.2.1. For now, let us simply observe how it implies the transcendence of $\exp(x)$. In this case $\mathcal{L} = \partial_x - 1$. Hence $\partial_x^p \mod \mathcal{L}$ is equal to 1 for all $p$. Indeed, in this case, $\mathcal{L}$ and $\partial_x$ commute, hence the computation of the remainder is the same as the computation in $\mathbb{Q}[x]$ of the remainder of $x^p$ by $x - 1$, that is the evaluation of $x^p$ at $x = 1$.
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 [25] for a much more detailed discussion on this topic (including much 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 $y(x)$ satisfies an algebraic equation $P(x, y(x)) = 0$ with $P$ of degree $n$ in $y$, then $y(x)$ also satisfies a differential equation like (1) of order $r$ bounded from above by $n$. This follows easily from the following reasoning. By differentiating $P(x, y(x)) = 0$ with respect to $x$ and by using the chain rule, we obtain the equality

$$P_x(x, y(x)) + y'(x)P_y(x, y(x)) = 0.$$

Here and in what follows we denote by $P_x$ the derivative $\partial P/\partial x$ of $P$ with respect to $x$. Therefore, if $P$ is assumed to be a polynomial of minimal degree in $y$ satisfied by $y(x)$, then $P_y(x, y(x))$ is a nonzero function in $\mathbb{Q}[[x]]$, and hence $y'(x) = -P_x(x, y(x))/P_y(x, y(x))$ is a rational function in $y(x)$. By using again the equation $P(x, y(x)) = 0$, it is easy to see that any rational function in $y(x)$ can be re-written as a polynomial of degree at most $n-1$ in $y(x)$. In other terms, the derivative $y'(x)$ lives in the $\mathbb{Q}(x)$-vector space generated by $1, y(x), \dots, y(x)^{n-1}$. The same similarly holds for all derivatives $y(x), y'(x), y''(x), \dots, y^{(n)}(x)$, and hence these elements must satisfy a nontrivial linear relation over $\mathbb{Q}(x)$; any such relation yields a linear differential equation (1) of order at most $n$. Observe that the same reasoning also proves the existence of an inhomogeneous linear differential equation of order at most $n-1$ for $y(x)$.

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 $r=1$, as the following example shows.

**Example 1.2.** The function $\exp(x) := \sum_{n \ge 0} x^n/n!$, solution of $y' = y$, is transcendental. Here is a purely algebraic proof. Let us assume by contradiction that $\exp(x)$ satisfies a polynomial equation, of minimal degree $d \ge 1$, of the form $e^{dx} + \sum_{k=0}^{d-1} r_k(x)e^{kx} = 0$ for some rational functions $r_k(x) \in \mathbb{Q}(x)$. By differentiating this equality with respect to $x$ and using $\exp'(x) = \exp(x)$, we get a new degree-$d$ equation $de^{dx} + \sum_{k=0}^{d-1} (r'_k(x) + kr_k(x))e^{kx} = 0$ which by minimality is equal the former up to a factor $d$. In other words, $r'_k(x) + kr_k(x) = dr_k(x)$ for all $k < d$. In particular, $r'_0(x) = dr_0(x)$, which implies that $r_0 = 0$. (Indeed, if $r_0(x) = A/B$ for two coprime polynomials $A, B \in \mathbb{Q}[x]$ with $A'B - AB' = dAB$, then $B$ divides $AB'$, hence $B$ divides $B'$ and $B' = 0$. Thus $A' = dA$, which implies $A = 0$ and $r_0(x) = 0$.) The nullity of $r_0$ now implies that $\exp(x)$ satisfies a polynomial equation of degree $d-1$, which contradicts the minimality of $d$.

The reader could object that in Example 1.2 we were probably lucky, because the differential equation of $\exp(x)$ 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 non-polynomial algebraic function needs to have a finite (and positive) radius of convergence, while $\exp(x)$ is entire (that is, analytic
**Example 1.8.** Let us consider the logarithmic function $y(x) = \log(1-x)$. Of course, since $\log(\exp(x)) = x$ and $\exp(\log(1-x)) = 1-x$, the transcendence of the logarithm function follows from the one of the exponential function. However, the two arithmetic criteria can be used directly. First, Eisenstein's criterion (Proposition 1.4) can be applied since $\log(1-x) = -\sum_{k \ge 1} x^k/k$. Second, we have $\mathcal{L} = (1-x)\partial_x^2 - \partial_x$ and it holds that (exercise!)

$$ \partial_x^n \mod \mathcal{L} = \frac{(n-1)!}{(1-x)^{n-1}} \partial_x \quad \text{for all } n \ge 1. $$

Therefore, Wilson's theorem implies that modulo any prime number $p$, the remainder $\partial_x^p \mod \mathcal{L}$ is equal to $-\frac{1}{(1-x)^{p-1}}\partial_x$, hence it is never 0. Then, Proposition 1.6 implies that $\log(1-x)$ is transcendental.

A natural question is whether the converses of Proposition 1.4 and Proposition 1.6 have any chance to hold true. Concerning Proposition 1.4, the first example that comes to mind is the function $y(x) = \sum_{k \ge 0} k!x^k$, which is D-finite and satisfies $x^2y''(x)+(3x-1)y'(x)+y(x) = 0$. It obviously satisfies the assumption of Proposition 1.4 since its coefficients are integers. But $y(x)$ is not algebraic. This can be seen in various ways. One of them is again analytic, by observing that $y(x)$ has radius of convergence 0. Another one is more algebraic, by seeing that $y(x)$ does not satisfy any first-order differential equation, and that its second-order differential equation above admits in its solution space the transcendental solution $e^{-1/x}/x$.

However, the reader may object that this counterexample is “degenerate” since the coefficient sequence $(k!)_{k \ge 0}$ grows too fast, which is not compatible with the growth of the coefficient sequence of an algebraic function. A better converse of Proposition 1.4 would be: is there any example of a D-finite but transcendental function $y \in \mathbb{Z}[[x]]$, whose coefficient sequence grows at most geometrically? The answer is again positive.

**Example 1.9.** Let again $(C_k)$ be the sequence of Catalan numbers, and consider the function $y(x) = \sum_{k \ge 0} C_k \binom{2k}{k} x^k$. One easily checks that it is D-finite and it satisfies the second-order equation $x(16x-1)y''(x) + 2(16x-1)y'(x) + 4y(x) = 0$. From there, it follows that $y(x)$ is the Gauss hypergeometric function ${}_2F_1([1/2, 1/2], [2]; 16x)$ and classical results (that we shall recall in §2.1.3) imply that $y(x)$ is transcendental.

Thus, even the stronger converse of Proposition 1.4 appears to be false. One may wonder if there is any way to reinforce even further the conclusion of Proposition 1.4, such that its converse becomes true. As of today, this is still an open problem, although there exist conjectural statements in this spirit. One of them is the following:

**Conjecture 1.10 (Christol-André conjecture).** Assume that $y(x) = \sum_{k \ge 0} a_k x^k \in \mathbb{Q}[[x]]$ is D-finite, such that:

(1) the sequence $(a_k)_{k \ge 0}$ has at most geometric growth;

(2) there exists $N \in \mathbb{N}$ such that $y(Nx) - y(0) \in \mathbb{Z}[[x]]$;

(3) in the minimal-order monic linear differential equation satisfied by $y(x)$, the point $x = 0$ is not a pole of any of the coefficients $a_i(x)$.

Then, $y(x)$ is algebraic.
in the whole complex plane). Another proof is that $\exp(x)$ cannot satisfy a nontrivial algebraic equation, since otherwise by specializing that equation at $x = 1$ we would obtain that the number $e = \exp(1)$ is an algebraic number, a statement known to be 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 [46, Criterion D] (see also [47, Thm. VII.8] and [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 $f(x) = \sum_{n \ge 0} a_n x^n$ around its singularities to the asymptotic behavior of its coefficient sequence $(a_n)_{n \ge 0}$. Before stating it, we recall the definition of the gamma function

$$ \Gamma(s) := \int_{0}^{+\infty} t^{s-1} e^t dt, $$

where the variable $s$ is a complex number with positive real part. The gamma function interpolates the factorial in the sense that $\Gamma(n) = (n-1)!$ for any positive integer $n$.

**Proposition 1.3** (Theorems A and D in [46]). Let $f(x) = \sum_{n \ge 0} a_n x^n \in \mathbb{Q}[[x]] \setminus \mathbb{Q}[x]$ be an algebraic non-polynomial function. Then $f(x)$ has a finite number of singularities, a finite nonzero radius of convergence, and its coefficient sequence $(a_n)_{n \ge 0}$ is such that

$$ a_n = \frac{\beta^n n^r}{\Gamma(r+1)} \sum_{i=0}^{m} C_i \omega_i^n + O(\beta^n n^q), \quad (3) $$

where $m \in \mathbb{Z}_{\ge 0}$, $r \in \mathbb{Q} \setminus \mathbb{Z}_{< 0}$, $q < r$, $\beta \in \overline{\mathbb{Q}}_{> 0}$, and $C_i$, $\omega_i \in \overline{\mathbb{Q}} \setminus \{0\}$ with $|\omega_i| = 1$.

The most useful form of the criterion is the following:

**Corollary 1.4** (“Flajolet’s criterion”). If $f(x) = \sum_{n \ge 0} a_n x^n \in \mathbb{Q}[[x]]$ and $a_n \sim \gamma \beta^n n^r$ with either $r \notin \mathbb{Q} \setminus \mathbb{Z}_{< 0}$, or $\beta \notin \overline{\mathbb{Q}}_{> 0}$, or $\gamma \cdot \Gamma(r+1) \notin \overline{\mathbb{Q}}$, then $f(x)$ is transcendental.

As an example of application, Proposition 1.3 immediately implies that $\exp(x) = \sum_{n \ge 0} x^n/n!$ is transcendental, since the sequence $1/n!$ is not of the form (3) (or, since the radius of convergence of $\exp(x)$ is infinite).

At this point, we can ask ourselves: is there a purely arithmetic proof of the transcendence of $\exp(x)$? 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 (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 $\exp(x) = \sum_{k \ge 0} x^k/k!$. The first arithmetic proof of the transcendence of $\exp(x)$ is based on the following result, which in rough terms asserts that the coefficients of algebraic functions are “almost integral”.
It is also conjectured that condition (3) can be replaced by

(3b) the minimal-order linear differential equation satisfied by $y(x)$ does not have any logarithms in its “local solutions” at $x = 0$.

Now, what about the converse of Proposition 1.6? It turns out that this converse is one of the simplest formulations of what is usually called the Grothendieck conjecture. This conjecture has been formulated in the late 1960s and it has a rich history. It was proved for some important classes of differential equations (1), which will be discussed in Section 3.

**Conjecture 1.11** (Grothendieck's conjecture, version 1). Let $\mathcal{L} \in \mathbb{Q}(x)\langle\partial_x\rangle$ be the differential operator attached to (1). If for all but a finite number of prime numbers $p$, the remainder of the left Euclidean division of $\partial_x^p$ by $\mathcal{L}$ has all its coefficients divisible by $p$, then all solutions of (1) are algebraic functions.

**Example 1.12.** Consider the operator

$$ \mathcal{L} = 2x(x-1)\partial_x^2 + (4x-1)\partial_x + 1. $$

Then, the reduction modulo $p$ of $\partial_x^p \mod \mathcal{L}$ is equal to 0 if $p \equiv 1 \mod 4$; else, it is equal to

$$ -\frac{2}{(x(x-1))^{\frac{p-1}{2}}} \partial_x - \frac{1}{(x-1)^{\frac{p+1}{2}} x^{\frac{p-1}{2}}}. $$

Therefore, for half of the primes $p$, the remainder is nonzero, hence Proposition 1.6 implies that $\mathcal{L}$ does not admit only algebraic solutions.

**Example 1.13.** Consider now the operator

$$ \mathcal{L}_r = 2x(x-1)\partial_x^2 + (4x-1)\partial_x + 2r(1-r), \quad \text{with } r \in \mathbb{Q}, $$

which is a tiny modification of the operator in Example 1.12: only the constant term has changed. Then, the reduction modulo $p$ of $\partial_x^p \mod \mathcal{L}_r$ is equal to

$$ \frac{r(r+1)\cdots\widehat{(r+\frac{p-1}{2})}\cdots(r+p-1)}{(x(x-1))^{\frac{p-1}{2}}} \partial_x + \frac{\frac{p+1}{2} \cdot r(r+1)\cdots\widehat{(r+\frac{p-1}{2})}\cdots(r+p-1)}{(x-1)^{\frac{p+1}{2}} x^{\frac{p-1}{2}}}. $$

For any $p$ not dividing (the numerator of) $2r-1$, the previous remainder is zero modulo $p$. Therefore, for all but finitely many primes $p$, the remainder is zero. Can we conclude that the operator $\mathcal{L}_r$ admits only algebraic solutions? Conjecture 1.11 predicts that the answer is positive and, as we will see in Section 2.1.3, this is indeed the case.

## 2 Several natural differential equations have algebraic solutions

As we have just seen in Section 1, although in general the solutions $y(x)$ of (1) are transcendental functions (e.g., $y(x) = \exp(x)$ and $y(x) = \log(1-x)$), it may happen sometimes that they are algebraic. Most of the examples given in Section 1 were “academic examples”, in the sense they were simple and constructed to illustrate the exposition. In this section, we give several examples (of different nature) showing that it is not quite unusual that natural linear differential equations arising “in practice” do possess algebraic solutions. Sometimes this is so for well-understood reasons, sometimes the explanations are still mysterious, either ad-hoc or completely missing.
**Proposition 1.6** (“Eisenstein’s criterion” (1852)). If the function $y(x) = \sum_{k \ge 0} a_k x^k \in \mathbb{Q}[[x]]$ is algebraic, then there exists $N \in \mathbb{N} \setminus \{0\}$ such that $y(Nx) - y(0) \in \mathbb{Z}[[x]]$. In particular, only a finite number of prime numbers can divide the denominators of the coefficients $a_k$.

Since in the factorial sequence $(k!)_{k \ge 0}$ obviously all prime numbers appear as divisors, Proposition 1.6 immediately implies that $\exp(x)$ is transcendental.

To formulate the second arithmetic proof of the transcendence of $\exp(x)$, we will need a little bit of additional vocabulary. The differential equation (1) can be rewritten in the compact form $\mathcal{L}(y) = 0$, where $\mathcal{L}$ is the linear differential operator

$$ \mathcal{L} = a_r(x) \partial_x^r + a_{r-1}(x) \partial_x^{r-1} + \dots + a_1(x) \partial_x + a_0(x). \quad (4) $$

We denote by $\mathbb{Q}(x)\langle\partial_x\rangle$ the set of such linear differential operators. For convenience, we also allow the trivial operator, in which all coefficients $a_i(x)$ are zero. The elements of $\mathbb{Q}(x)\langle\partial_x\rangle$ act on functions in $x$ by letting the variable $\partial_x$ act through the differentiation $\frac{d}{dx}$. The set $\mathbb{Q}(x)\langle\partial_x\rangle$ 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 from Leibniz’s differentiation rule:

$$ \forall r \in \mathbb{Q}(x), \quad \partial_x r(x) = r(x) \partial_x + r'(x). $$

Although the ring $\mathbb{Q}(x)\langle\partial_x\rangle$ is noncommutative, it shares many properties with the classical commutative ring of polynomials $\mathbb{Q}(x)[y]$. First, one has a well-defined notion of degree: the degree of the nonzero operator $\mathcal{L}$ in (4) is the order $r$ of the corresponding differential equation (1), that is the largest integer $r$ such that $a_r(x) \neq 0$. We will denote it by $\mathrm{ord}(\mathcal{L})$ in what follows. Second, the ring $\mathbb{Q}(x)\langle\partial_x\rangle$ admits an Euclidean division.

**Proposition 1.7.** The ring $\mathbb{Q}(x)\langle\partial_x\rangle$ is right Euclidean, i.e., for all $A, B \in \mathbb{Q}(x)\langle\partial_x\rangle$ with $B \neq 0$, there exist $Q$ and $R$ in $\mathbb{Q}(x)\langle\partial_x\rangle$ such that $A = QB + R$ and $\mathrm{ord}R < \mathrm{ord}B$. Moreover, the pair $(Q, R)$ 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 (1) are algebraic functions, then for all but a finite number of prime numbers $p$, the remainder of the right Euclidean division of $\partial_x^p$ by $\mathcal{L}$ has all its coefficients divisible by $p$.

*Proof.* By Eisenstein’s criterion (Proposition 1.6), there exists a basis of algebraic solutions $y_1, \dots, y_r$ of $\mathcal{L}$ and an integer $N \in \mathbb{N} \setminus \{0\}$ such that $y_i(x)$ is in $\mathbb{Q} + x\mathbb{Z}[[\frac{x}{N}]]$ for all $i$. This implies that for all but a finite number of prime numbers $p$ (namely, the ones dividing $N$ and the denominators of $y_i(0)$) the power series $y_i^{(p)}(x)$ are in $p\mathbb{Z}[[x]]$, i.e. zero modulo $p$. Thus, writing $\partial_x^p = \mathcal{Q}\mathcal{L} + R$ with $R$ of order at most $r-1$, we have $R(y_i) = 0 \mod p$ for all $i$. Writing $R = c_0(x) + \dots + c_{r-1}(x)\partial_x^{r-1}$, we deduce that the vector $(c_0, \dots, c_{r-1})$ times the Wronskian matrix of the $y_i$’s is zero modulo $p$. Since the Wronskian matrix is invertible (because the $y_i$’s form a basis of solutions of $\mathcal{L}$), it is also invertible modulo $p$ for all but a finite number of prime numbers $p$, and thus the $c_i$’s are all $0$ modulo $p$ for any such prime $p$. $\square$

**Example 1.9.** The generating function of the Catalan numbers, $y(x) = \sum_{k \ge 0} C_k x^k$, satisfies the differential equation $(4x^2 - x)y''(x) + (10x - 2)y'(x) + 2y(x) = 0$, which is easily deduced,
## 2.1 Examples from Special functions: Hypergeometric functions

### 2.1.1 Elliptic integrals: Euler's differential equation

Perhaps one of the oldest special functions distinct from the classical algebraic, exponential, logarithmic, or trigonometric functions, is the one arising from the question: what is the perimeter $p(x)$ of an ellipse with semi-major axis 1, as a function of its eccentricity $x$? (Recall that the eccentricity is the quotient between the focal distance and the semi-major axis.)

This question is more challenging than the analogue one with “perimeter” replaced by “area”, since the area is expressible algebraically as $\pi\sqrt{1-x^2}$. Already in 1733, Euler [36, §7] could solve this question. Here is one of the possible solutions, not his own, based on what is nowadays called the “method of creative telescoping” [1]. First, we express the arc length using a real integral and the parametrization of the ellipse:

$$p(x) = 4 \int_{0}^{1} \sqrt{\frac{1-x^2 u^2}{1-u^2}} \, du = 2\pi - \frac{\pi}{2} x^2 - \frac{3\pi}{32} x^4 - \frac{5\pi}{128} x^6 - \frac{175\pi}{8192} x^8 - \dots \quad (3)$$

Up to the factor of 4, the function $p(x)$ is called the complete elliptic integral of the second kind. The second equality above is obtained by expanding the integrand in power series with respect to $x$, and integrating between 0 and 1. Now, the “magic” of creative telescoping is that it constructs the equality below, which expresses a linear combination of the integrand and of its first and second derivative w.r.t. $x$ as a pure derivative w.r.t. $u$ of another algebraic function (a rational multiple of the integrand):

$$((x - x^3)\partial_x^2 + (1 - x^2)\partial_x + x) \left( \sqrt{\frac{1 - x^2 u^2}{1 - u^2}} \right) = \partial_u \left( \frac{u x \sqrt{1 - u^2}}{\sqrt{1 - x^2 u^2}} \right). \quad (4)$$

Now, integrating both sides of Eq. (4) w.r.t. $u$, it follows that $p(x)$ is a D-finite function w.r.t. $x$, and that it satisfies the linear differential equation

$$(x - x^3)p''(x) + (1 - x^2)p'(x) + xp(x) = 0. \quad (5)$$

Writing $p(x) = \sum_{k \ge 0} a_k x^k$, we deduce from Eq. (5) the recursion $(k-1)(k+1)a_k = (k+2)^2 a_{k+2}$ for all $k \ge 0$. From $a_0 = 2\pi$ and $a_1 = 0$ it follows that

$$a_{2k} = \frac{2\pi \binom{2k}{k}^2}{(1 - 2k)16^k} \quad \text{and} \quad a_{2k+1} = 0 \quad \text{for all } k \ge 0.$$

Stirling's formula then implies that $a_{2k} \sim -1/k^2$, which excludes algebraicity of $p(x)$. Indeed, the presence of the factor $k^{-2}$ is incompatible with algebraicity by the Newton-Puiseux theorem, see e.g. [39, Theorem D].

### 2.1.2 Elliptic integrals: Legendre's differential equation

A special function similar to $p(x)$ is obtained by a different construction. Consider the family of elliptic curves (with $x \in \mathbb{C}$) given by the so-called Legendre equation

$$E_x : \quad y^2 = u(u-1)(u-x).$$
either from the inhomogeneous differential equation of order 1 in Example 1.1, or directly from the recurrence $(k+2)C_{k+1} - (4k+2)C_k = 0$. The associated differential operator is $\mathcal{L} = (4x^2 - x) \partial_x^2 + (10x - 2) \partial_x + 2$, and the remainders of the right Euclidean divisions of $\partial_x^p$ by $\mathcal{L}$ for $p \in \{2, 3, 5\}$ are

$$ \partial_x^2 \mod \mathcal{L} = -\frac{2(5x-1)}{x(4x-1)}\partial_x - \frac{2}{x(4x-1)}, $$

$$ \partial_x^3 \mod \mathcal{L} = \frac{6(22x^2 - 9x + 1)}{x^2(4x-1)^2} \partial_x + \frac{6(6x-1)}{x^2(4x-1)^2}, $$

$$ \partial_x^5 \mod \mathcal{L} = \frac{120(386x^4 - 325x^3 + 110x^2 - 17x + 1)}{x^4(4x-1)^4} \partial_x + \frac{120(130x^3 - 69x^2 + 14x - 1)}{x^4(4x-1)^4}. $$

Note that indeed, we have $\partial_x^p \mod \mathcal{L} = 0$ modulo $p$, in the three cases.

**Proposition 1.8** will be discussed in more detail in §3.2. For now, let us simply observe how it implies the transcendence of $\exp(x)$. In this case $\mathcal{L} = \partial_x - 1$. Hence $\partial_x^p \mod \mathcal{L}$ is equal to 1 for all $p$. Indeed, in this case, $\mathcal{L}$ and $\partial_x$ commute, hence the computation of the remainder is the same as the computation in $\mathbb{Q}[x]$ of the remainder of $x^p$ by $x-1$, that is the evaluation of $x^p$ at $x=1$.

**Example 1.10.** Let us consider the logarithmic function $y(x) = \log(1-x)$. Of course, since $\log(\exp(x)) = x$ and $\exp(\log(1-x)) = 1-x$, the transcendence of the logarithm function follows from that of the exponential function. However, the two arithmetic criteria can be used directly. First, Eisenstein's criterion (Proposition 1.6) can be applied since $\log(1-x) = -\sum_{k \ge 1} x^k/k$. Second, we have that a full basis of solutions of $\mathcal{L} = (1-x)\partial_x^2 - \partial_x$ is $\{1, \log(1-x)\}$, and it holds by induction that

$$ \partial_x^n \mod \mathcal{L} = \frac{(n-1)!}{(1-x)^{n-1}} \partial_x \quad \text{for all } n \ge 1. $$

Therefore, Wilson's theorem implies that modulo any prime number $p$, the remainder $\partial_x^p \mod \mathcal{L}$ is equal to $-\frac{1}{(1-x)^{p-1}}\partial_x$, hence it is never 0. Then, Proposition 1.8 implies that $\log(1-x)$ is transcendental.

A natural question is whether the converses of Proposition 1.6 and Proposition 1.8 have any chance to hold true. Concerning Proposition 1.6, it is not difficult to exhibit a transcendental D-finite power series with integer coefficients, showing that its converse is false. A natural example that comes to mind is $y(x) = \sum_{k \ge 0} k!x^k$, which satisfies $x^2y''(x) + (3x-1)y'(x) + y(x) = 0$. One can prove that $y(x)$ is not algebraic in various ways. One of them is again analytic, by observing that $y(x)$ has radius of convergence 0 and by applying Proposition 1.3. A purely algebraic proof also exists, but it is less immediate: it relies on the combination of the following facts: (i) $y(x)$ does not satisfy any first-order differential equation, hence the second-order differential equation above is the minimal-order LDE satisfied by $y(x)$; (ii) this second-order differential equation admits in its solution space the transcendental solution $e^{-1/x}/x$; (iii) if $y(x)$ were algebraic, then its minimal-order LDE would have only algebraic solutions (Proposition 2.5 in [80]).
On $E_x$, there exists a unique (up to a constant multiple) holomorphic 1-form, given by

$$ \omega_x = \frac{du}{y} = \frac{du}{\sqrt{u(u-1)(u-x)}} $$

This form is necessarily closed since it is a holomorphic 1-form on a variety of complex dimension 1. The method of creative telescoping finds an exact form that is a linear combination of $\omega_x$ and of its first and second derivatives with respect to $x$, namely

$$ ((4x^2 - 4x)\partial_x^2 + (8x - 4)\partial_x + 1) \omega_x = -d \left( \frac{2\sqrt{u(u-1)}}{(u-x)^{3/2}} \right). \qquad (6) $$

From Eq. (6) it follows that the integral $y(x) = \int_{\gamma} \omega_x$ over any closed curve $\gamma$ on $E_x$ satisfies the so-called *Legendre differential equation*

$$ (4x^2 - 4x)y''(x) + (8x - 4)y'(x) + y(x) = 0. \qquad (7) $$

This is the most basic case of the *Picard-Fuchs differential equation* of a period function. For instance, by taking $C$ to be the curve on $E_x$ given by the double cover $y = \pm\sqrt{u(u-1)(u-x)}$ of $[1, \infty)$, the corresponding period is the so-called *complete elliptic integral of the first kind*,

$$ \int_C \omega_x = 2 \int_1^\infty \frac{du}{\sqrt{u(u-1)(u-x)}} = \sum_{k \ge 0} b_k x^k, $$

where $b_0 = 2 \int_1^\infty \frac{du}{u\sqrt{u-1}} = 2\pi$ and $(2k+1)^2 b_k = 4(k+1)^2 b_{k+1}$ for all $k \ge 0$, this recurrence relation being a consequence of the fact that $y(x) = \int_C \omega_x$ satisfies Eq. (7). Thus,

$$ \int_C \omega_x = 2\pi \sum_{k \ge 0} \binom{2k}{k}^2 \left(\frac{x}{16}\right)^k. \qquad (8) $$

Once again, Stirling's formula gives $b_k \sim 1/k$, which excludes algebraicity of $y(x) = \int_C \omega_x$.

### 2.1.3 Gauss' hypergeometric functions

The D-finite functions considered in Sections 2.1.1 and 2.1.2 are special cases of the so-called *Gauss hypergeometric function* with parameters $a, b, c \in \mathbb{Q}, c \notin \mathbb{Z}_{\le 0}$, defined by

$$ {}_2F_1([a, b], [c]; x) = \sum_{k \ge 0} \frac{(a)_k (b)_k}{(c)_k k!} x^k, \qquad (9) $$

where $(a)_k = a(a+1)\cdots(a+k-1)$ denotes the rising factorial. Indeed, $p(x)$ in Eq. (3) is equal to $2\pi \cdot {}_2F_1([-1/2, 1/2], [1]; x^2)$, while $\int_C \omega_x$ in Eq. (8) is equal to $2\pi \cdot {}_2F_1([1/2, 1/2], [1]; x)$. We have seen that in both cases these functions are transcendental.

In general, $y(x) = {}_2F_1([a, b], [c]; x)$ satisfies the second-order differential equation

$$ x(x-1)y''(x) + ((a+b+1)x-c)y'(x) + aby(x) = 0 \qquad (10) $$
However, the reader may object that this counterexample is “degenerate” since the co-efficient sequence $(k!)_{k \ge 0}$ grows too fast, which is not compatible with the growth of the coefficient sequence of an algebraic function. A better converse of Proposition 1.6 would be: is there any example of a D-finite but transcendental function $y \in \mathbb{Z}[[x]]$, whose coefficient sequence grows at most geometrically? The answer is again positive.

**Example 1.11.** Let again $(C_k)$ be the sequence of Catalan numbers, and consider the function $y(x) = \sum_{k \ge 0} C_k \binom{2k}{k} x^k$. One easily checks that it is D-finite and it satisfies the second-order equation $x(16x - 1)y''(x) + 2(16x - 1)y'(x) + 4y(x) = 0$. From there, it follows that $y(x)$ is the Gauss hypergeometric function ${}_2F_1([1/2, 1/2], [2]; 16x)$ and classical results (that we shall recall in §2.1.3) imply that $y(x)$ is transcendental.

Thus, even the stronger converse of Proposition 1.6 appears to be false. One may wonder if there is any way to reinforce even further the conclusion of Proposition 1.6, such that its converse becomes true. As of today, this is still an open problem, although there exist conjectural statements in this spirit. One of them is the following:

**Conjecture 1.12 (Christol-André conjecture).** Assume that $y(x) = \sum_{k \ge 0} a_k x^k \in \mathbb{Q}[[x]]$ is D-finite. Let $\mathcal{L}$ be the minimal-order monic linear differential equation satisfied by $y(x)$. We assume that:

(1) the sequence $(a_k)_{k \ge 0}$ has at most geometric growth;

(2) there exists $N \in \mathbb{N}$ such that $y(Nx) - y(0) \in \mathbb{Z}[[x]]$;

(3) the point $x = 0$ is not a pole of any of the coefficients of $\mathcal{L}$.

Then, $y(x)$ is algebraic.

If $r$ denotes the order of $\mathcal{L}$, it is also conjectured that condition (3) can be replaced by

(3b) $\mathcal{L}$ has $r$ linearly independent solutions in $\mathbb{C}((x^{1/D}))$ for some positive integer $D$.

Now, what about the converse of Proposition 1.8? It turns out that this converse is one of the simplest formulations of what is usually called the *Grothendieck conjecture*. This conjecture has been formulated in the late 1960s and it has a rich history. It was proved for some important classes of differential equations (1), which will be discussed in Section 3.

**Conjecture 1.13 (Grothendieck's conjecture, version 1).** Let $\mathcal{L} \in \mathbb{Q}(x)\langle \partial_x \rangle$ be the differential operator attached to (1). If for all but a finite number of prime numbers $p$, the remainder of the right Euclidean division of $\partial_x^p$ by $\mathcal{L}$ has all its coefficients divisible by $p$, then all solutions of (1) are algebraic functions over $\mathbb{Q}(x)$.

**Example 1.14.** Consider the operator

$$ \mathcal{L} = 2x(x-1)\partial_x^2 + (4x-1)\partial_x + 1. $$

Then, for any prime number $p > 2$, the reduction modulo $p$ of $\partial_x^p \mod \mathcal{L}$ is equal to 0 if $p \equiv 1 \mod 4$; else, it is equal to

$$ -\frac{2}{(x(x-1))^{\frac{p-1}{2}}} \partial_x - \frac{1}{(x-1)^{\frac{p+1}{2}} x^{\frac{p-1}{2}}}. $$

Therefore, for half of the primes $p$, the remainder is nonzero, hence Proposition 1.8 implies that $\mathcal{L}$ does not admit only algebraic solutions.
and the name hypergeometric comes from the fact that the coefficient sequence $(u_k)_k$ of ${}_2F_1([a, b], [c]; x)$ satisfies a linear recurrence of order 1, namely

$$ (a + k)(b + k)u_k = (k + 1)(k + c)u_{k+1} \quad (k \ge 0). $$

For other choices of parameters we recover the functions

$$ \begin{aligned} (1-x)^\alpha &= {}_2F_1([-\alpha, 1], [1]; x), & \text{for all } \alpha \in \mathbb{Q}, \\ \sum_{k \ge 0} C_k x^k &= {}_2F_1([1, 1/2], [2]; 4x), \\ \log(1-x) &= -x \cdot {}_2F_1([1, 1], [2]; x), \\ \arcsin(x) &= x \cdot {}_2F_1([1/2, 1/2], [3/2]; x^2), \end{aligned} $$

the first two of which are algebraic, the last two of which are transcendental. In some cases, the Gauss' hypergeometric functions even becomes a polynomial: this is so for

$$ P_n(x) = 2^n \cdot {}_2F_1([-n, n+1], [1]; (x+1)/2), $$

the *Legendre polynomial* given by $P_n(x) := \frac{1}{n!} \cdot \frac{\partial^n}{\partial x^n} (x^2 - 1)^n$, as well as for

$$ T_n(x) = (-1)^n \cdot {}_2F_1([-n, n], [1/2]; (x+1)/2), $$

the *Chebyshev polynomial of the first kind* given by $T_n(\cos x) = \cos(nx)$.

Deciding the algebraicity of ${}_2F_1$ hypergeometric functions is an old problem, solved by Schwarz [62] using geometric tools (Riemann mappings, Schwarzian derivatives and sphere tilings by spherical triangles) and by Landau [53, 54] and Errera [35] using arithmetic tools (Eisenstein's theorem on algebraic power series, and Dirichlet's theorem on prime numbers in arithmetic progressions). Both approaches are algorithmic: Schwarz's criterion reduces the problem to a table look-up after some preprocessing on the parameters $a, b, c$; the Landau-Errera criterion amounts to checking a finite number of inequalities.

More precisely, let us assume that none of $a, b, c-a$ and $c-b$ is an integer (equivalently, the operator $H(a, b; c) := x(1-x)\partial_x^2 + (c-(a+b+1)x)\partial_x - ab$ is irreducible) and let $D$ be the common denominator of $a, b$ and $c$. Then, the Landau-Errera criterion says that the following assertions are equivalent:

1. the hypergeometric function ${}_2F_1([a, b], [c]; x)$ is algebraic;

2. the operator $H(a, b; c)$ admits only algebraic solutions;

3. for every $\ell < D$ coprime with $D$, either $\{\ell a\} < \{\ell c\} < \{\ell b\}$ or $\{\ell b\} < \{\ell c\} < \{\ell a\}$. (Here $\{x\}$ denotes the fractional part $x - \lfloor x \rfloor$ of $x$.)

The last condition is equivalent to the fact that, for every $\ell < D$ coprime with $D$, the two sets $\{e^{2\pi i \ell a}, e^{2\pi i \ell b}\}$ and $\{e^{2\pi i \ell c}, 1\}$ are interlaced on the unit circle. This "interlacing condition" was first proved by Landau [53, 54] to be necessary for the algebraicity of ${}_2F_1([a, b], [c]; x)$ and then proved to also be sufficient by Errera [35]; see also Stridsberg's intermediate contribution [67], who relates the conditions in Eisenstein's criterion to the ones in the Landau-Errera condition. In §3.2.2 we will see that Theorem 3.22 provides an extension of the Landau-Errera "interlacing criterion" to the generalized hypergeometric function ${}_{s+1}F_s$ defined by

$$ {}_{s+1}F_s([a_1, \dots, a_{s+1}], [b_1, \dots, b_s]; x) = \sum_{k \ge 0} \frac{(a_1)_k \cdots (a_{s+1})_k}{(b_1)_k \cdots (b_s)_k k!} x^k. \quad (11) $$
**Example 1.15.** Consider now the operator

$$ \mathcal{L}_r = 2x(x-1)\partial_x^2 + (4x-1)\partial_x + 2r(1-r), \quad \text{with } r \in \mathbb{Q} \setminus \{1/2\}, $$

which is a tiny modification of the operator in Example 1.14: only the constant term has changed. Then, for any prime $p \neq 2$ not dividing the denominator of $r$, the reduction modulo $p$ of $\partial_x^p \mod \mathcal{L}_r$ is equal to

$$ \frac{r(r+1)\cdots\widehat{(r+\frac{p-1}{2})}\cdots(r+p-1)}{(x(x-1))^{\frac{p-1}{2}}} \partial_x + \frac{r(r+1)\cdots\widehat{(r+\frac{p-1}{2})}\cdots(r+p-1)}{2(x-1)^{\frac{p+1}{2}}x^{\frac{p-1}{2}}}, $$

where the notation $\widehat{(r+\frac{p-1}{2})}$ indicates that $r + \frac{p-1}{2}$ is missing in the above products. For any prime number $p > 2$ not dividing the denominator of $r$ nor the numerator of $2r-1$, the previous remainder is zero modulo $p$. Therefore, for all but finitely many primes $p$, the remainder is zero modulo $p$.

Can we conclude that the operator $\mathcal{L}_r$ admits only algebraic solutions? Conjecture 1.13 predicts that the answer is positive and, indeed, one easily checks that $\mathcal{L}_r$ admits the algebraic solutions $f_1 = (\sqrt{x} + \sqrt{x-1})^{2r-1}/\sqrt{x-1}$ and $f_2 = (\sqrt{x} + \sqrt{x-1})^{1-2r}/\sqrt{x-1}$, which are linearly independent for $r \neq \frac{1}{2}$ since $f_1 f'_2 - f_2 f'_1 = (1-2r)/(\sqrt{x} (x-1)^{3/2})$.

## 2 Several natural differential equations have algebraic solutions

As we have just seen in Section 1, although in general the solutions $y(x)$ of (1) are transcendental functions (e.g., $y(x) = \exp(x)$ and $y(x) = \log(1-x)$), it may happen sometimes that they are algebraic. Most of the examples given in Section 1 were “academic examples”, in the sense that they were simple and constructed to illustrate the exposition.

The aim of this section is to give evidences showing that linear differential equations naturally appear in many areas of mathematics, including algebra, combinatorics and number theory. In all these settings, we shall see examples of differential equations that admit algebraic solutions and others that do not, demonstrating that both behaviors are common and deserve our attention. Hence, besides its beauty and intrinsic fundamental nature, being able to recognize whether a given D-finite function is algebraic or not appears as an important question, likely to have profound applications.

For instance, in number theory one often wants to understand the (algebraic or transcendental) nature of a complex number given as the value $f(\alpha)$ of a function $f \in \mathbb{Q}[[x]]$ at an algebraic point $\alpha \in \overline{\mathbb{Q}}$; understanding the algebraic nature of the corresponding function $f(x)$ is a first important step in this process. In the theory of the *E-functions* (an important class of D-finite functions generalizing the exponential function), the methods of Siegel and Shidlovskii, revisited recently in [1] and [21], are used to show that a number (such as $e = \exp(1)$) is transcendental by checking, among other things, that it is the value of a transcendental *E-function*. Another motivation comes from combinatorics, where predicting the nature of the generating function of some class of combinatorial objects is a central task, as it may reveal strong underlying structures. Indeed, knowing that a class of objects is counted by an algebraic function suggests that it should be possible to construct these objects recursively by concatenation of objects of the same type [25].
## 2.2 Examples from Algebra: Diagonals

As proved in Section 1, algebraic functions are D-finite. A larger, yet very important, class of D-finite functions is formed by the so-called *diagonals of rational functions*. By definition, the *diagonal* of a multivariate power series

$$F = \sum_{(i_1, \dots, i_n) \in \mathbb{N}^n} a_{i_1, \dots, i_n} x_1^{i_1} \cdots x_n^{i_n} \in \mathbb{Q}[[x_1, \dots, x_n]]$$

is the univariate power series

$$\mathrm{Diag}(F) = \sum_{i \in \mathbb{N}} a_{i, \dots, i} t^i \in \mathbb{Q}[[t]].$$

**Example 2.1 (Dyck bridges).** Let $B_n$ be the number of $\{\uparrow, \to\}$-walks in $\mathbb{Z}^2$ from $(0,0)$ to $(n, n)$ (i.e., there are exactly $B_n$ ways of going from the origin to $(n, n)$ using only North and East steps, see §2.3 for a more general context) and let $B(t)$ be its generating function $\sum_{n \ge 0} B_n t^n$. Then,

$$B(t) = \mathrm{Diag} \left( \frac{1}{1-x-y} \right) = \sum_{n \ge 0} \binom{2n}{n} t^n.$$

This is perhaps the simplest example of a diagonal. By the binomial theorem, it comes that $B(t) = 1/\sqrt{1-4t}$, hence this diagonal is even an algebraic function. This is not an accident. Indeed, a century ago Pólya [60] proved that diagonals of bivariate rational functions are algebraic. (Later, Furstenberg [42] showed that the converse also holds true.) Pólya's result can be proved as follows. First, using the simple observation<fnref n="1" /> $\mathrm{Diag}(F)(t) = [x^0] F(x, t/x)$, the diagonal of the rational function $F(x, y) \in \mathbb{Q}(x, y)$ is encoded as a complex integral using Cauchy's integral theorem (for some $\epsilon > 0$)

$$\mathrm{Diag}(F)(t) = [x^{-1}] \frac{1}{x} F\left(x, \frac{t}{x}\right) = \frac{1}{2\pi i} \oint_{|x|=\epsilon} F\left(x, \frac{t}{x}\right) \frac{dx}{x},$$

which in a second step can be evaluated using the residues theorem as a sum of residues (precisely: the residues of $F(x, t/x)/x$ at its “small poles”, having limit 0 at $t = 0$). Each of these residues are algebraic functions, and so is their sum $\mathrm{Diag}(F)$.

**Example 2.2 (Dyck bridges, continued).** The proof sketched above directly concludes that

$$\mathrm{Diag} \left( \frac{1}{1-x-y} \right) = \frac{1}{2\pi i} \oint_{|x|=\epsilon} \frac{dx}{x-x^2-t} = \frac{1}{1-2x} \Big|_{x=\frac{1-\sqrt{1-4t}}{2}} = \frac{1}{\sqrt{1-4t}}.$$

**Example 2.3.** Interestingly, Pólya's result becomes false for more than two variables. A simple example is provided by the rational function $1/(1-x-y-z) = \sum_{i,j,k} \frac{(i+j+k)!}{i!j!k!} x^i y^j z^k$, whose diagonal is

$$\mathrm{Diag} \left( \frac{1}{1-x-y-z} \right) = \sum_{n \ge 0} \frac{(3n)!}{n!^3} t^n.$$

<footnote n="1">¹Here, and in all the text, $[x^n]$ denotes coefficient extraction of $x^n$.</footnote>
## 2.1 Examples from Special functions: Hypergeometric functions

### 2.1.1 Elliptic integrals: Euler's differential equation

Perhaps one of the oldest special functions distinct from the classical algebraic, exponential, logarithmic, or trigonometric functions, is the one arising from the question: what is the perimeter $p(x)$ of an ellipse with semi-major axis 1, as a function of its eccentricity $x$? (Recall that the eccentricity is the quotient between the focal distance and the semi-major axis.)

This question, which was solved by Euler [43, §7] in 1733, is more challenging than the analogue one with “perimeter” replaced by “area”, since the area is expressible algebraically as $\pi\sqrt{1-x^2}$. First, we express the arc length using a real integral and the parametrization of the ellipse:

$$p(x) = 4 \int_{0}^{1} \sqrt{\frac{1-x^2 u^2}{1-u^2}} du = 2\pi - \frac{\pi}{2}x^2 - \frac{3\pi}{32}x^4 - \frac{5\pi}{128}x^6 - \frac{175\pi}{8192}x^8 - \dots \quad (5)$$

Up to the factor of 4, the function $p(x)$ is called the complete elliptic integral of the second kind. The second equality above is obtained by expanding the integrand in power series with respect to $x$, and integrating between 0 and 1. It is a fact familiar to algebraic geometers that this function $p(x)$ satisfies a linear differential equation: $p(x)$ is what we call a period function and, as such, it satisfies a linear differential equation called Picard-Fuchs differential equation (or Gauss-Manin connection). An alternative way to establish this fact and to find a differential equation satisfied by $p(x)$ is to use the “method of creative telescoping” [2]. The “magic” of creative telescoping is that it constructs the equality below, which expresses a linear combination of the integrand and of its first and second derivative with respect to $x$ as a pure derivative with respect to $u$ of another algebraic function (a rational multiple of the integrand):

$$((x - x^3)\partial_x^2 + (1 - x^2)\partial_x + x) \left( \sqrt{\frac{1 - x^2 u^2}{1 - u^2}} \right) = \partial_u \left( \frac{u x \sqrt{1 - u^2}}{\sqrt{1 - x^2 u^2}} \right). \quad (6)$$

Now, integrating both sides of Eq. (6) with respect to $u$, it follows that $p(x)$ is a D-finite function with respect to $x$, and that it satisfies the linear differential equation

$$(x - x^3)p''(x) + (1 - x^2)p'(x) + xp(x) = 0. \quad (7)$$

Writing $p(x) = \sum_{k \ge 0} a_k x^k$, we deduce from Eq. (7) the recursion $(k-1)(k+1)a_k = (k+2)^2 a_{k+2}$ for all $k \ge 0$. From $a_0 = 2\pi$ and $a_1 = 0$ it follows that

$$a_{2k} = \frac{2\pi \binom{2k}{k}^2}{(1 - 2k)16^k} \quad \text{and} \quad a_{2k+1} = 0 \quad \text{for all } k \ge 0.$$

Stirling's formula then implies that $a_{2k} \sim -1/k^2$, and hence transcendence of $p(x)$. Indeed, the presence of the factor $k^{-2}$ is incompatible with algebraicity by Flajolet's criterion (Corollary 1.4).
The transcendence of this function can be proved in various ways, for instance by using asymptotics: Stirling's formula implies that $(\frac{(3n)!}{n!})^3 \sim \frac{\sqrt{3}}{2\pi} \frac{27^n}{n}$ when $n$ goes to infinity, and the presence of the factor $n^{-1}$ is incompatible with algebraicity. Another proof is based on rewriting

$$ \mathrm{Diag}\left(\frac{1}{1-x-y-z}\right) = {}_2F_1\left(\left[\frac{1}{3}, \frac{2}{3}\right], [1]; 27t\right), \qquad (12) $$

and by using the Schwarz or the Landau-Errera criteria mentioned above.

The diagonal in Eq. (12) is hypergeometric, hence D-finite. In general, there is no reason that the diagonal of a multivariate rational function be hypergeometric. However, that all such diagonals are D-finite functions is a general fact. In fact, much more holds: a theorem by Lipshitz [55] states that if $F(x_1, \dots, x_n)$ is a multivariate D-finite function$^2$, then $\mathrm{Diag}(F)$ is D-finite.

The particular case where $F$ is rational is already interesting and nontrivial to prove. In this case, the argument is the following. First, as in the bivariate case, if $F = P/Q \in \mathbb{Q}(x_1, \dots, x_n) \cap \mathbb{Q}[[x_1, \dots, x_n]]$, then the residue theorem allows to write (for some $\epsilon > 0$)

$$ \mathrm{Diag}(F)(t) = \frac{1}{(2\pi i)^{n-1}} \oint_{|x_1|=\dots=|x_{n-1}|=\epsilon} F\left(x_1, \dots, x_{n-1}, \frac{t}{x_1 \cdots x_{n-1}}\right) \frac{dx_1 \cdots dx_{n-1}}{x_1 \cdots x_{n-1}}, $$

so that $\mathrm{Diag}(F)(t)$ is the period function of a (family of) rational functions. Its D-finiteness is then a consequence of the finite-dimensionality over $\mathbb{C}(t)$ of the de Rham cohomology for the complement of the variety in $\mathbb{A}_{\mathbb{C}(t)}^n$ defined by the equations $Q(x_1, \dots, x_n) = 0$ and $x_1 \cdots x_n = t$. (This finiteness proof usually relies on a geometric argument in the smooth case, and on Hironaka's resolution of singularities in the general case.) In more down-to-earth terms this proof guarantees, in a non-effective way, that repeated differentiation under the integral sign eventually produces a finite sequence of rational integrands that admit a linear combination with coefficients in $\mathbb{Q}(t)$ that becomes an exact differential.

If $f(t)$ is the diagonal of a rational function, then not only $f(t)$ is D-finite, but in addition $f(t)$ is globally bounded, that is, $f(t)$ has a nonzero radius of convergence in $\mathbb{C}$ and $\beta \cdot f(\alpha \cdot t) \in \mathbb{Z}[[t]]$ for some $\alpha, \beta \in \mathbb{Z}$. (Note that this second property is equivalent to the existence of an $N \in \mathbb{N} \setminus \{0\}$ such that $f(Nt) - f(0) \in \mathbb{Z}[[t]]$, as in Proposition 1.4.) The following beautiful conjecture predicts that the converse is also true; it was formulated by Christol in the late 1980s, see e.g. [27] and [28, Conjecture 4]:

**Conjecture 2.4 (Christol's conjecture).** For $f(t) \in \mathbb{Q}[[t]]$, the following properties are equivalent:

(1) $f(t) = \mathrm{Diag}(F)$ for some $F \in \mathbb{Q}(x_1, \dots, x_n) \cap \mathbb{Q}[[x_1, \dots, x_n]]$;

(2) $f \in \mathbb{Q}[[t]]$ is D-finite and globally bounded.

Christol's conjecture is far from being proved; the following explicit problem, also due to Christol [28, p. 51], is a very particular case of Conjecture 2.4 and it is still open as of today.

<footnote>$^2$This means that $F$ satisfies a system of $n$ linear partial differential equations, the $i$-th one being an ordinary linear differential equation with respect to $\frac{\partial}{\partial x_i}$ and with polynomial coefficients in $x_1, \dots, x_n$.</footnote>
### 2.1.2 Elliptic integrals: Legendre's differential equation

A special function similar to $p(x)$ is obtained by a different construction. Consider the family of elliptic curves (with $x \in \mathbb{C}$) given by the Legendre equation

$$E_x: \quad y^2 = u(u-1)(u-x).$$

On $E_x$, there exists a unique (up to a constant multiple) holomorphic 1-form, given by

$$\omega_x = \frac{du}{y} = \frac{du}{\sqrt{u(u-1)(u-x)}}.$$

This form is necessarily closed since it is a holomorphic 1-form on a variety of complex dimension 1. The method of creative telescoping finds an exact form that is a linear combination of $\omega_x$ and of its first and second derivatives with respect to $x$, namely

$$((4x^2 - 4x)\partial_x^2 + (8x - 4)\partial_x + 1) \omega_x = -d \left( \frac{2\sqrt{u(u-1)}}{(u-x)^{3/2}} \right). \quad (8)$$

From Eq. (8) it follows that the integral $y(x) = \int_{\gamma} \omega_x$ over any closed curve $\gamma$ on $E_x$ satisfies the Legendre differential equation

$$(4x^2 - 4x)y''(x) + (8x - 4)y'(x) + y(x) = 0. \quad (9)$$

This is the most basic case of the Picard-Fuchs differential equation of a period function. For instance, by taking $C$ to be the curve on $E_x$ given by the double cover $y = \pm\sqrt{u(u-1)(u-x)}$ of $[1, \infty)$, the corresponding period is the complete elliptic integral of the first kind,

$$\int_C \omega_x = 2 \int_1^\infty \frac{du}{\sqrt{u(u-1)(u-x)}} = \sum_{k \ge 0} b_k x^k,$$

where $b_0 = 2 \int_1^\infty \frac{du}{u\sqrt{u-1}} = 2\pi$ and $(2k+1)^2 b_k = 4(k+1)^2 b_{k+1}$ for all $k \ge 0$, this recurrence relation being a consequence of the fact that $y(x) = \int_C \omega_x$ satisfies Eq. (9). Thus,

$$\int_C \omega_x = 2\pi \sum_{k \ge 0} \left(\binom{2k}{k}\right)^2 \left(\frac{x}{16}\right)^k. \quad (10)$$

Once again, Stirling's formula gives $b_k \sim 2/k$, which excludes algebraicity of $y(x) = \int_C \omega_x$ by Flajolet's criterion (Corollary 1.4).

### 2.1.3 Gauss' hypergeometric functions

The D-finite functions considered in Sections 2.1.1 and 2.1.2 are special cases of the Gauss hypergeometric function with parameters $a, b, c \in \mathbb{Q}, c \notin \mathbb{Z}_{\le 0}$, defined by

$${}_2F_1([a, b], [c]; x) := \sum_{k \ge 0} \frac{(a)_k (b)_k}{(c)_k k!} x^k, \quad (11)$$
**Question 2.5.** Is

$$f(t) = {}_3F_2\left(\left[\frac{1}{9}, \frac{4}{9}, \frac{5}{9}\right], \left[1, \frac{1}{3}\right]; 3^6 t\right) \\ = 1 + 60t + 20475t^2 + 9373650t^3 + 4881796920t^4 + \dots$$

the diagonal of a rational power series?

Therefore, even understanding diagonals which are hypergeometric functions is a very difficult problem; for some recent progress see [22].

Another natural and difficult question is whether a given diagonal of a rational function is algebraic or transcendental. This question is directly connected to the main aim of this article. One may wonder whether it is possible to detect transcendence of a given diagonal $f(t) = \text{Diag}(F)$ by reducing it modulo a prime $p$, and proving the transcendence of $f(t) \bmod p$ over $\mathbb{F}_p(t)$. Unfortunately, this strategy is systematically doomed to failure: indeed, even if the diagonal $f(t)$ is transcendental, its reduction modulo $p$ is necessarily algebraic! This was proved by Furstenberg in [42, Theorem 1]. For instance, the transcendental diagonal in (12) is equal to

$$\begin{align*} (1+t)^{-1/4} &\bmod 5, \\ (1+6t+6t^2)^{-1/6} &\bmod 7, \\ (1+6t+2t^2+8t^3)^{-1/10} &\bmod 11. \end{align*}$$

On the other hand, the Christol-André conjecture (Conjecture 1.10) implies that if $f(t)$ is the diagonal of a rational function, then $f(t)$ is algebraic if and only if its minimal-order differential equation does not have any logarithms in its local solutions around $t = 0$. The direct implication is clear: if the minimal-order differential equation has local logs, this implies that there are transcendental solutions, and hence that $f(t)$ is transcendental as well (by minimality of the order, if $f(t)$ were algebraic, the differential equation would only have algebraic solutions). For instance, the diagonal in (12) admits $t(27t-1)\partial_t^2 + (54t-1)\partial_t + 6$ as minimal-order differential equation, with local basis

$$1 + 6t + 90t^2 + \dots \quad \text{and} \quad \log(t) + (6\log(t) + 15)t + \dots$$

Hence it is transcendental.

As a final remark, note that Theorem 1.1 in [71] implies that for any prime $p \neq 3$, the reduction modulo $p$ of the ${}_3F_2$ (transcendental) function from Question 2.5 is algebraic (of degree at most $p^{54}$). Hence, even if this ${}_3F_2$ function is not known to be a diagonal of a rational function, its reductions modulo $p$ are known to behave as reductions modulo $p$ of diagonals of rational functions.

## 2.3 Examples from Combinatorics: Walks in the Quarter Plane

In combinatorics, studying the nature of generating functions is of primary importance; for instance, algebraicity may reveal essential (but potentially hidden) recursive structures of the combinatorial classes under consideration. In particular, many examples have been studied over the past decades in lattice path combinatorics, a subfield of enumerative combinatorics. A
where $(a)_k = a(a+1)\cdots(a+k-1)$ denotes the rising factorial. Indeed, $p(x)$ in Eq. (5) is equal to $2\pi \cdot {}_2F_1([-1/2, 1/2], [1]; x^2)$, while $\int_C \omega_x$ in Eq. (10) is equal to $2\pi \cdot {}_2F_1([1/2, 1/2], [1]; x)$. We have seen that in both cases these functions are transcendental.

In general, $y(x) = {}_2F_1([a, b], [c]; x)$ satisfies the second-order differential equation

$$x(x-1)y''(x) + ((a+b+1)x-c)y'(x) + aby(x) = 0 \quad (12)$$

and the name hypergeometric comes from the fact that the coefficient sequence $(u_k)_{k \ge 0}$ of ${}_2F_1([a, b], [c]; x) = \sum_{k \ge 0} u_k x^k$ satisfies a linear recurrence of order 1, namely

$$(a+k)(b+k)u_k = (k+1)(k+c)u_{k+1}, \quad (k \ge 0).$$

For other choices of parameters we recover the functions

$$(1-x)^\alpha = {}_2F_1([-\alpha, 1], [1]; x), \quad \text{for all } \alpha \in \mathbb{Q},$$

$$\sum_{k \ge 0} C_k x^k = {}_2F_1([1, 1/2], [2]; 4x),$$

$$\log(1-x) = -x \cdot {}_2F_1([1, 1], [2]; x),$$

$$\arcsin(x) = x \cdot {}_2F_1([1/2, 1/2], [3/2]; x^2),$$

the first two of which are algebraic, the last two of which are transcendental. In some cases, the Gauss' hypergeometric function even becomes a polynomial: this is so for

$$P_n(x) = {}_2F_1([-n, n+1], [1]; (1-x)/2),$$

the Legendre polynomial given by $P_n(x) := \frac{1}{2^{n\cdot n!}} \cdot \frac{\partial^n}{\partial x^n} (x^2 - 1)^n$, as well as for

$$T_n(x) = (-1)^n \cdot {}_2F_1([-n, n], [1/2]; (x+1)/2),$$

the Chebyshev polynomial of the first kind given by $T_n(\cos x) = \cos(nx)$.

Deciding the algebraicity of ${}_2F_1$ hypergeometric functions is an old problem, solved by Schwarz [76] using geometric tools (Riemann mappings, Schwarzian derivatives and sphere tilings by spherical triangles) and by Landau [64, 65] and Errera [42] using arithmetic tools (Eisenstein's criterion for algebraic power series, and Dirichlet's theorem on prime numbers in arithmetic progressions). Both approaches are algorithmic: Schwarz's criterion reduces the problem to a table look-up after some preprocessing on the parameters $a, b, c$; the Landau-Errera criterion amounts to checking a finite number of inequalities.

More precisely, let us assume that none of $a, b, c-a$ and $c-b$ is an integer (equivalently, the operator $H(a, b; c) := x(1-x)\partial_x^2 + (c-(a+b+1)x)\partial_x - ab$ is irreducible) and let $D$ be the common denominator of $a, b$ and $c$. Then, the Landau-Errera criterion says that the following assertions are equivalent:

1. the hypergeometric function ${}_2F_1([a, b], [c]; x)$ is algebraic;

2. the operator $H(a, b; c)$ admits only algebraic solutions;

3. for every $\ell < D$ coprime with $D$, either $\{\ell a\} < \{\ell c\} < \{\ell b\}$ or $\{\ell b\} < \{\ell c\} < \{\ell a\}$. (Here $\{x\}$ denotes the fractional part $x - \lfloor x \rfloor$ of $x$.)
plethora of interesting mathematical phenomena occur even when restricting to the so-called walks with small steps in the quarter plane $\mathbb{N}^2$. These are walks in the lattice $\mathbb{Z}^2$, confined to the cone $\mathbb{R}_+^2$ that start at the origin $(0, 0)$ and use steps in a model (or stepset) $\mathcal{S}$ which is a fixed subset of the set of nearest-neighbor steps $\{\uparrow, \leftarrow, \nwarrow, \rightarrow, \nwarrow, \downarrow\}$. The systematic study of small step walks in $\mathbb{N}^2$ has been initiated by Bousquet-Mélou and Mishna in their germinal article [24]. An earlier reference on the topic, in a probabilistic context, is the book [38]. The study of generating functions of walks with small steps in the quarter plane now spans several decades and dozens of articles. For instance, in [32] the differential-algebraic nature of these generating functions is completely elucidated using tools from differential Galois theory. A survey with many references can be found in the recent article [11].

Given a model $\mathcal{S} \subseteq \{\uparrow, \leftarrow, \nwarrow, \rightarrow, \nwarrow, \downarrow\}$, we denote by $q_{i,j,n}$ the number of $\mathcal{S}$-walks of length $n$ ending at $(i, j)$. The full counting sequence $(q_{i,j,n})_{(i,j,n) \in \mathbb{N}^3}$ admits several interesting specializations, for instance $e_n := q_{0,0,n}$, the number of $\mathcal{S}$-walks of length $n$ returning to $(0, 0)$ ("excursions") and $q_n := \sum_{i,j \ge 0} q_{i,j,n}$, the number of $\mathcal{S}$-walks with prescribed length $n$.

To these sequences one attaches various functions, namely the full generating function

$$Q_{\mathcal{S}}(x, y, t) = \sum_{n=0}^{\infty} \left( \sum_{i,j=0}^{\infty} q_{i,j,n} x^i y^j \right) t^n \in \mathbb{Q}[x, y][[t]]$$

and its corresponding univariate specializations $Q_{\mathcal{S}}(0, 0, t) = \sum_{n \ge 0} e_n t^n$ ("excursions generating function"), $Q_{\mathcal{S}}(1, 1, t) = \sum_{n \ge 0} q_n t^n$ ("length generating function"), $Q_{\mathcal{S}}(1, 0, t)$ and $Q_{\mathcal{S}}(0, 1, t)$ ("boundary returns") and $[x^0]Q_{\mathcal{S}}(x, 1/x, t)$ ("diagonal returns").

The general question in this setting is: given a model $\mathcal{S}$, what can be said about the generating function $Q_{\mathcal{S}}(x, y, t)$, and its specializations? In particular, is $Q_{\mathcal{S}}(x, y, t)$ algebraic? Is it at least D-finite? Does $Q_{\mathcal{S}}(x, y, t)$ (or at least some of its specializations) admit closed-form expressions?

The model $\mathcal{S} = \{\uparrow, \rightarrow\}$ in Example 2.1 (Dyck walks) is one of the simplest possible models. In that case, the generating function $Q(x, y, t)$ is algebraic. This is actually a particular case of a classical result stating that whenever $\mathcal{S}$ is included in $\{\uparrow, \rightarrow, \rightarrow, \downarrow\}$ or in $\{\leftarrow, \leftarrow, \rightarrow, \rightarrow\}$, that is, if the walks are essentially 1-dimensional, then $Q(x, y, t)$ is algebraic.

For this reason, most studies in the area focus on the truly 2-dimensional cases, that is on models $\mathcal{S}$ that contain both a step oriented towards the horizontal and the vertical axes (see Figure 1 in [11]). A full classification is now available, according to the algebraic-differential properties of $Q_{\mathcal{S}}(x, y, t)$, but here we restrict to two examples.

### 2.3.1 Trident walks

Up to some canonical reductions, there are exactly 23 models of walks with small steps in the quarter plane whose full generating function $Q(x, y, t)$ is D-finite (with respect to $x, y$ and $t$). They are displayed in Figure 4 in [11].

One of these models is that of the so-called "trident walks", with $\mathcal{S} = \{\nwarrow, \uparrow, \nwarrow, \downarrow\}$. This is entry 7 in [11, Fig. 4] and in [16, Table 6]. There is 1 trident walk of length 0 (the empty walk), 2 trident walks of length 1 ($\{\uparrow\}$, $\{\nwarrow\}$) and 7 trident walks of length 2 ($\{\uparrow - \uparrow\}$, $\{\uparrow - \downarrow\}$, $\{\uparrow - \nwarrow\}$, $\{\nwarrow - \uparrow\}$, $\{\nwarrow - \nwarrow\}$, $\{\nwarrow - \downarrow\}$). It was proved in [16]
The last condition is equivalent to the fact that, for every $\ell < D$ coprime with $D$, the two sets $\{e^{2\pi i \ell a}, e^{2\pi i \ell b}\}$ and $\{e^{2\pi i \ell c}, 1\}$ are interlaced on the unit circle. This “interlacing condition” was first proved by Landau [64, 65] to be necessary for the algebraicity of $_2F_1([a, b], [c]; x)$ and then proved to also be sufficient by Errera [42]; see also Stridsberg’s intermediate contribution [82], which relates the conditions in Eisenstein’s criterion to the ones in the Landau-Errera condition. In §3.3 we will see that Theorem 3.23 provides an extension of the Landau-Errera “interlacing criterion” to the generalized hypergeometric function $_{s+1}F_s$ defined by

$$ {}_{s+1}F_s([a_1, \dots, a_{s+1}], [b_1, \dots, b_s]; x) = \sum_{k \ge 0} \frac{(a_1)_k \cdots (a_{s+1})_k}{(b_1)_k \cdots (b_s)_k k!} x^k. \quad (13) $$

## 2.2 Examples from Algebra: Diagonals

As proved in Section 1, algebraic functions are D-finite. A larger, yet very important, class of D-finite functions is formed by the *diagonals of rational functions*. By definition, the *diagonal* of a multivariate power series

$$ F = \sum_{(i_1, \dots, i_n) \in \mathbb{N}^n} a_{i_1, \dots, i_n} x_1^{i_1} \cdots x_n^{i_n} \in \mathbb{Q}[[x_1, \dots, x_n]] $$

is the univariate power series

$$ \mathrm{Diag}(F) = \sum_{i \in \mathbb{N}} a_{i, \dots, i} t^i \in \mathbb{Q}[[t]]. $$

**Example 2.1 (Dyck bridges).** Let $B_n$ be the number of $\{\uparrow, \to\}$-walks in $\mathbb{Z}^2$ from $(0,0)$ to $(n, n)$ (i.e., there are exactly $B_n$ ways of going from the origin to $(n, n)$ using only North and East steps, see §2.3 for a more general context) and let $B(t)$ be its generating function $\sum_{n \ge 0} B_n t^n$. Then,

$$ B(t) = \mathrm{Diag} \left( \frac{1}{1 - x - y} \right) = \sum_{n \ge 0} \binom{2n}{n} t^n. $$

This is perhaps the simplest example of a diagonal. By the binomial theorem, it comes that $B(t) = 1/\sqrt{1-4t}$, hence this diagonal is even an algebraic function. This is not an accident. Indeed, a century ago Pólya [73] proved that diagonals of bivariate rational functions are algebraic. (Later, Furstenberg [50] showed that the converse also holds true.) Pólya’s result can be proved as follows. First, using the simple observation<fnref n="1" /> $\mathrm{Diag}(F)(t) = [x^0] F(x, t/x)$, the diagonal of the rational function $F(x, y) \in \mathbb{Q}(x, y)$ is encoded as a complex integral using Cauchy’s integral theorem (for some $\epsilon > 0$)

$$ \mathrm{Diag}(F)(t) = [x^{-1}] \frac{1}{x} F\left(x, \frac{t}{x}\right) = \frac{1}{2\pi i} \oint_{|x|=\epsilon} F\left(x, \frac{t}{x}\right) \frac{dx}{x}, $$

which in a second step can be evaluated using the residues theorem as a sum of residues (precisely: the residues of $F(x, t/x)/x$ at its “small poles”, having limit 0 at $t = 0$). Each of these residues are algebraic functions, and so is their sum $\mathrm{Diag}(F)$.

<footnote n="1">¹Here, and in all the text, $[x^n]$ denotes coefficient extraction of $x^n$.</footnote>
that the length generating function of trident walks

$$Q(t) = \sum_{n \ge 0} q_n t^n = 1 + 2t + 7t^2 + 23t^3 + 84t^4 + 301t^5 + 1127t^6 + \dots$$

is D-finite and satisfies $L_5(Q(t)) = 0$, where $L_5$ is the following differential equation of order 5 with polynomial coefficients of degree at most 15:

$$ 
\begin{aligned}
& t^2 (t-1) (4t-1) (12t^2-1) (5184t^7 - 4128t^6 + 4416t^5 + 400t^4 + 252t^3 - 90t^2 - 42t + 3) (4t^2 + 1) \partial_t^5 + \\
& \quad t (21399552t^{13} - 38486016t^{12} + 43416576t^{11} - 25803264t^{10} + 7762176t^9 - 3848960t^8 + \\
& \quad \quad 337088t^7 + 143168t^6 - 7128t^5 + 45328t^4 - 11304t^3 - 1854t^2 + 540t - 27) \partial_t^4 + \\
& (143327232t^{13} - 222621696t^{12} + 257753088t^{11} - 122575104t^{10} + 36213888t^9 - 19897728t^8 + \\
& \quad 1942656t^7 + 70768t^6 - 100456t^5 + 254712t^4 - 35124t^3 - 7404t^2 + 1116t - 48) \partial_t^3 + \\
& (346374144t^{12} - 454643712t^{11} + 545398272t^{10} - 166067712t^9 + 59053824t^8 - 32668800t^7 + \\
& \quad 2167392t^6 + 54912t^5 - 687744t^4 + 500616t^3 - 31176t^2 - 5004t + 288) \partial_t^2 + \\
& (262766592t^{11} - 284000256t^{10} + 358041600t^9 - 21846528t^8 + 33115392t^7 - 13748736t^6 - \\
& \quad 1184640t^5 + 651744t^4 - 894672t^3 + 278496t^2 - 7272t + 2880) \partial_t + \\
& 35831808t^{10} - 31186944t^9 + 42163200t^8 + 11639808t^7 + 4981248t^6 - \\
& \quad 981504t^5 - 809280t^4 + 72576t^3 - 177408t^2 + 8064t - 3168.
\end{aligned}
$$

The length generating function $Q(t)$ is completely and uniquely defined by $L_5$ and by the first coefficients $[t^k]Q(t)$ for $k = 0, \dots, 14$. The question is: how to determine the algebraic or transcendental nature of $Q(t)$?

Note that the asymptotic estimate $q_n \sim \gamma\beta^n n^r$ in [11, Fig. 4], with $\gamma = 4/(3\sqrt{\pi})$, $\beta = 4$, $r = -1/2$, is compatible with algebraicity, since $r \in \mathbb{Q} \setminus \mathbb{Z}_{<0}$, $\beta \in \overline{\mathbb{Q}}$ and $\gamma\Gamma(r+1) = 4/3 \in \overline{\mathbb{Q}}$. Hence we cannot conclude the transcendence using asymptotic arguments as in Example 2.3.

An interesting feature is that $L_5$ admits a factorization $L_2 \cdot L_{1,a} \cdot L_{1,b} \cdot L_{1,c}$, where the three operators $L_{1,\star}$ have order 1, and $L_2$ has order 2. This type of factorization $2/1/\dots/1$ actually holds in all the cases 1–19 in [11, Fig. 4]. On the other hand, the algorithmic method (a variant of the creative telescoping mentioned in Section 2.1.1) that produces the differential equation $L_5$ does not guarantee that it is the least-order one satisfied by $Q(t)$. In [16], the above factorization was algorithmically computed and exploited (together with some other computer algebra algorithms) in order to produce the following expression for $Q(t)$ (and similar expressions for all cases 1–19 in [11, Fig. 4]):

$$ Q(t) = \frac{1}{t(t-1)} \int_0^t \frac{u}{(1-4u)^{3/2}} \left\{ 4 + \int_0^u \frac{(1-4v)^{1/2}(\frac{1}{2}+v)}{v^2} \left[ 1 + \frac{1}{2v(1+2v)(1+4v^2)^{1/2}} \right] \times \right. \\
\left. \left( (1-v) {}_2F_1\left(\left[\frac{1}{2}, \frac{3}{2}\right], [1]; \frac{16t^2}{4t^2+1}\right) - (1+v)(1-4v+8v^2) {}_2F_1\left(\left[\frac{1}{2}, \frac{1}{2}\right], [1]; \frac{16t^2}{4t^2+1}\right) \right) \right] dv \right\} du. $$

Note that although the ${}_2F_1$ functions occurring in this expression are transcendental, it is in principle still possible that the linear combination produce an algebraic function in the end. In [16, §4.2] it was shown that $Q(t)$ is transcendental by exploiting the explicit factorization
**Example 2.2 (Dyck bridges, continued).** The proof sketched above directly concludes that

$$ \mathrm{Diag} \left( \frac{1}{1-x-y} \right) = \frac{1}{2\pi i} \oint_{|x|=\epsilon} \frac{dx}{x-x^2-t} = \frac{1}{1-2x} \bigg|_{x=\frac{1-\sqrt{1-4t}}{2}} = \frac{1}{\sqrt{1-4t}} $$

**Example 2.3.** Interestingly, Pólya's result becomes false for more than two variables. A simple example is provided by the rational function $1/(1-x-y-z) = \sum_{i,j,k} \frac{(i+j+k)!}{i!j!k!} x^i y^j z^k$, whose diagonal is

$$ \mathrm{Diag} \left( \frac{1}{1-x-y-z} \right) = \sum_{n \ge 0} \frac{(3n)!}{n!^3} t^n. $$

The transcendence of this function can be proved in various ways, for instance by using asymptotics: Stirling's formula implies that $\frac{(3n)!}{n!^3} \sim \frac{\sqrt{3}}{2\pi} \frac{27^n}{n}$ and the presence of the factor $n^{-1}$ is incompatible with algebraicity by Corollary 1.4. Another proof is based on rewriting

$$ \mathrm{Diag} \left( \frac{1}{1-x-y-z} \right) = {}_2F_1 \left( \left[ \frac{1}{3}, \frac{2}{3} \right], [1]; 27t \right), \quad (14) $$

and by using the Schwarz or the Landau-Errera criteria mentioned above.

The diagonal in Eq. (14) is hypergeometric, hence D-finite. In general, there is no reason that the diagonal of a multivariate rational function be hypergeometric. However, that all such diagonals are D-finite functions is a general fact. In fact, much more holds: a theorem by Lipshitz [66] states that if $F(x_1, \dots, x_n)$ is a multivariate D-finite function$^2$, then $\mathrm{Diag}(F)$ is D-finite.

The particular case where $F$ is rational is already interesting and nontrivial to prove. In this case, the argument is the following. First, as in the bivariate case, if $F = P/Q \in \mathbb{Q}(x_1, \dots, x_n) \cap \mathbb{Q}[[x_1, \dots, x_n]]$, then the residue theorem allows to write (for some $\epsilon > 0$)

$$ \mathrm{Diag}(F)(t) = \frac{1}{(2\pi i)^{n-1}} \oint_{|x_1|=\dots=|x_{n-1}|=\epsilon} F \left( x_1, \dots, x_{n-1}, \frac{t}{x_1 \cdots x_{n-1}} \right) \frac{dx_1 \cdots dx_{n-1}}{x_1 \cdots x_{n-1}}, $$

so that $\mathrm{Diag}(F)(t)$ is the period function of a (family of) rational functions. Its D-finiteness is then a consequence of the finite-dimensionality over $\mathbb{C}(t)$ of the de Rham cohomology for the complement of the variety in $\mathbb{A}_{\mathbb{C}(t)}^n$ defined by the equations $Q(x_1, \dots, x_n) = 0$ and $x_1 \cdots x_n = t$. (This finiteness proof usually relies on a geometric argument in the smooth case, and on Hironaka's resolution of singularities in the general case.) In more down-to-earth terms this proof guarantees, in a non-effective way, that repeated differentiation under the integral sign eventually produces a finite sequence of rational integrands that admit a linear combination with coefficients in $\mathbb{Q}(t)$ that becomes an exact differential.

If $f(t)$ is the diagonal of a rational function, then not only is $f(t)$ D-finite, but in addition $f(t)$ is globally bounded, that is, $f(t)$ has a nonzero radius of convergence in $\mathbb{C}$ and $\beta \cdot f(\alpha \cdot t) \in \mathbb{Z}[[t]]$ for some $\alpha, \beta \in \mathbb{Z} \setminus \{0\}$. (Note that this second property is equivalent to the existence of an $N \in \mathbb{N} \setminus \{0\}$ such that $f(Nt) - f(0) \in \mathbb{Z}[[t]]$, as in Proposition 1.6.) The following beautiful conjecture predicts that the converse is also true; it was formulated by Christol in the late 1980s, see e.g. [31] and [33, Conjecture 4]:

<footnote>$^2$This means that $F$ satisfies a system of $n$ linear partial differential equations, the $i$-th one being an ordinary linear differential equation with respect to $\frac{\partial}{\partial x_i}$ and with polynomial coefficients in $x_1, \dots, x_n$.</footnote>
of $L_5$, and by applying to $L_2$ a specific algorithm that decides algebraicity of solutions for operators of order 2, namely Kovacic's algorithm [51]. The same approach uniformly works on the models 1–19 and allows to prove transcendence of the corresponding $Q(t)$ except in case 17 for the model $\mathcal{S} = \{\uparrow, \leftarrow, \searrow, \downarrow, \rightarrow, \nwarrow\}$ and in case 18 for the model $\mathcal{S} = \{\uparrow, \leftarrow, \searrow, \downarrow, \rightarrow, \nwarrow\}$ (in these two cases the algorithm proves algebraicity of all solutions of the corresponding $L_2$). Very interestingly, the full generating function $Q(x, y, t)$ is proved to be transcendental in all cases 1–19, and cases 17 and 18 are the only ones with algebraic specialization $Q(1, 1, t)$.

An alternative proof of the transcendence of the length generating function $Q(t)$ for tri-
dent walks is based on the fact that $L_5$ is indeed the minimal-order differential equation for
$Q(t)$; this implies that if $Q(t)$ were algebraic, then $L_5$ would only have algebraic solutions,
a situation discarded by exhibiting logarithms in the local solutions of $L_5$ at $t = 0$. This
approach to the proof of transcendence of solutions of linear differential equations is used
in [20]; its heart is the “minimization” algorithm from [19].

2.3.2 Gessel walks

The most difficult model of small-step walks in the quarter plane is Gessel’s model, for which
$\mathcal{S} = \{\uparrow, \leftarrow, \searrow, \downarrow, \rightarrow, \nwarrow\}$. For notational simplicity we will write $G(x, y, t)$ for the full generating
function in this case, and $G(t)$ for the length generating function for Gessel walks $G(1, 1, t)$.

Around 2000, Ira Gessel formulated two conjectures equivalent to the following statements:

**Conjecture 2.6.** The generating function $G(0, 0, t) = 1+2t^2+11t^4+85t^6+782t^7+\cdots$ of Gessel excursions is equal to ${}_3F_2([5/6, 1/2, 1], [5/3, 2]; 16t^2)$.

**Conjecture 2.7.** The generating function $G(x, y, t)$ is not D-finite.

Gessel's first conjecture was first solved in 2009 by Kauers, Koutschan and Zeilberger in [47] using a computerized guess-and-prove approach. Unfortunately, solving Conjecture 2.6 had no implication concerning Conjecture 2.7, and in particular on the D-finiteness of the length generating function $G(t)$. It came as a total surprise when Bostan and Kauers [17] proved that Gessel's second conjecture was false.

**Theorem 2.8 ([17]).** The generating function $G(x, y, t)$ for Gessel walks is algebraic.

Moreover, the coefficients $(g_n)$ of $G(t) = 1 + 2t + 7t^2 + 21t^3 + 78t^4 + 260t^5 + \cdots$ satisfy
$(3n + 1) g_{2n} = (12n + 2) g_{2n-1}$ and $(n + 1) g_{2n+1} = (4n + 2) g_{2n}$ for all $n \ge 0$.

In addition, $G(t) = (H(t) - 1)/(2t)$ where $H(t) = 1 + 2t + 4t^2 + 14t^3 + 42t^4 + \cdots$ is a root of $27(4t-1)^2 H^8 - 18(4t-1)^2 H^4 - 8(16t^2 + 24t + 1) H^2 - (4t-1)^2 = 0$, and

$$
G(t) = \frac{1}{2t} \cdot \left( {}_2F_1\left(\left[-\frac{1}{12}, \frac{1}{4}\right], \left[\frac{2}{3}\right]; -\frac{64t(4t+1)^2}{(4t-1)^4}\right) - 1 \right).
$$

The original discovery and proof of Theorem 2.8 was computer-driven, and used a guess-and-prove approach, based on Hermite-Padé approximants. As a byproduct of this proof, the size of the minimal polynomial of $G(x, y, t)$ has been estimated to have more than $10^{11}$ terms when written in expanded form, for a total size of ≈ 30 Gb (!). The guess-and-prove method is a 3-step process: (i) compute $G(x, y, t)$ to precision $t^{1200}$ (≈ 1.5 billion coefficients!); (ii)
**Conjecture 2.4 (Christol's conjecture).** For $f(t) \in \mathbb{Q}[[t]]$, the following properties are equivalent:

(1) $f(t) = \text{Diag}(F)$ for some $F \in \mathbb{Q}(x_1, \dots, x_n) \cap \mathbb{Q}[[x_1, \dots, x_n]]$;

(2) $f \in \mathbb{Q}[[t]]$ is D-finite and globally bounded.

Christol's conjecture is far from being proved; the following explicit problem, also due to Christol [33, p. 51], is a very particular case of Conjecture 2.4 and it is still open as of today.

**Question 2.5.** Is

$$f(t) = {}_3F_2\left(\left[\frac{1}{9}, \frac{4}{9}, \frac{5}{9}\right], \left[1, \frac{1}{3}\right]; 3^6 t\right) \\ = 1 + 60t + 20475t^2 + 9373650t^3 + 4881796920t^4 + \dots$$

the diagonal of a rational power series?

Therefore, even understanding diagonals which are hypergeometric functions is a very difficult problem; for some recent progress see [24].

Another natural and difficult question is whether a given diagonal of a rational function is algebraic or transcendental. This question is directly connected to the main aim of this article. One may wonder whether it is possible to detect transcendence of a given diagonal $f(t) = \text{Diag}(F)$ by reducing it modulo a prime $p$, and proving the transcendence of $f(t) \mod p$ over $\mathbb{F}_p(t)$. Unfortunately, this strategy is systematically doomed to failure: indeed, even if the diagonal $f(t)$ is transcendental, its reduction modulo $p$ is necessarily algebraic! This was proved by Furstenberg in [50, Theorem 1]. For instance, the transcendental diagonal in (14) is equal to

$$\begin{align*} (1+t)^{-1/4} &\mod 5, \\ (1+6t+6t^2)^{-1/6} &\mod 7, \\ (1+6t+2t^2+8t^3)^{-1/10} &\mod 11. \end{align*}$$

On the other hand, the Christol-André conjecture (Conjecture 1.12) implies that if $f(t)$ is the diagonal of a rational function, then $f(t)$ is algebraic if and only if the condition (3b) is fulfilled. The direct implication is true without the Christol-André conjecture; it relies on three nontrivial facts: (i) the minimal-order LDE for a diagonal has only regular singularities with rational exponents [32]; (ii) the classification of local solutions of Fuchsian linear differential equations [74, §19]; (iii) if $f(t)$ is algebraic, then its minimal-order LDE has only algebraic solutions [36, §2]. If the condition (3b) fails, then by (i) and (ii) at least one local solution $g(t)$ around $t=0$ of the minimal-order LDE for $f(t)$ involves logarithms, hence $g(t)$ is transcendental; then (iii) implies that $f(t)$ must be transcendental as well.

For instance, the diagonal in (14) admits $t(27t-1)\partial_t^2 + (54t-1)\partial_t + 6$ as minimal-order differential equation, with local basis

$$1 + 6t + 90t^2 + \dots \quad \text{and} \quad \log(t) + (6\log(t) + 15)t + \dots$$

Hence it is transcendental.
conjecture polynomial equations for $G(x, 0, t)$ and $G(0, y, t)$; (iii) conclude the proof by computing multivariate resultants of (very big) polynomials (30 pages each).

As a matter of fact, the discovery of algebraicity was initially performed in a different way: the expansion of the generating function $G(x, y, t)$ modulo $t^{1000}$ was sufficient to guess (by using differential Hermite-Padé approximants) two differential operators

* $\mathcal{L}_{x,0} \in \mathbb{Q}(x,t)\langle \partial_t \rangle$, of order 11 in $\partial_t$, bidegree (96, 78) in $(t, x)$, and integer coefficients of at most 61 digits

* $\mathcal{L}_{0,y} \in \mathbb{Q}(y,t)\langle \partial_t \rangle$, of order 11 in $\partial_t$, bidegree (68, 28) in $(t, y)$, and integer coefficients of at most 51 digits

such that $\mathcal{L}_{x,0}(G(x, 0, t)) = 0 \mod t^{1000}$ and $\mathcal{L}_{0,y}(G(0, y, t)) = 0 \mod t^{1000}$.

After this guessing step of plausible differential equations for $Q(x, 0, t)$ and for $Q(0, y, t)$, an important step in the discovery process was to apply Conjecture 1.11 with several primes $p$. More precisely, for randomly chosen prime numbers $p$, and $a, b \in \mathbb{F}_p$, both $\mathcal{L}_{a,0}$ and $\mathcal{L}_{0,b}$ right-divide the pure power $\partial_t^p$ in $\mathbb{F}_p(x)\langle \partial_t \rangle$; in other terms, they have zero $p$-curvature for all the tested primes $p$ (see Definition 3.17). This was the key observation in the discovery [17] that the trivariate generating function for Gessel walks is algebraic.

Several human proofs of Conjecture 2.6 and Theorem 2.8 have been discovered since the publication of [17]: the first one used complex analysis [18], the second one is purely algebraic [23], the third one is both combinatorial and analytic [25], while the more recent one is probably the most elementary [6].

## 2.4 Examples from Number Theory

In his ICM 2018 paper [73, p. 768], Zagier introduced a recurrent sequence of rational numbers $(c_n)_{n \ge 0}$ defined by initial terms $c_0 = 1, c_1 = -161/(2^{10} \cdot 3^5)$ and $c_2 = 26605753/(2^{23} \cdot 3^{12} \cdot 5^2)$, and by the following linear recursion with polynomial coefficients:

$$c_{n-3} + 20(4500n^2 - 18900n + 19739)c_{n-2} + 80352000n(5n-1)(5n-2)(5n-4)c_n + 25(2592000n^4 - 16588800n^3 + 39118320n^2 - 39189168n + 14092603)c_{n-1} = 0.$$

This mysteriously looking sequences arises from a topological differential equation in the work of Bertola, Dubrovin and Yang [7], each coefficient $c_n$ being defined by an integral over a moduli space. It is not difficult to prove that $c_n$ behaves asymptotically like $1/n!^2$. Inspired by an analogy with the behavior of the so-called quantum periods in mirror symmetry, Zagier asked whether if it is possible that the $c_n$'s become integers after multiplication by $n!^2$, or more generally by the product of two Pochhammer symbols. Zagier mentions the following highly nontrivial two results:

* [Yang & Zagier]: $a_n := (2^{10} \cdot 3^5 \cdot 5^4)^n \cdot (3/5)_n \cdot (4/5)_n \cdot c_n \in \mathbb{Z}$ for all integers $\ge 0$;

* [Dubrovin & Yang]: $b_n := (2^{12} \cdot 3^5 \cdot 5^4)^n \cdot (2/5)_n \cdot (9/10)_n \cdot c_n \in \mathbb{Z}$ for all integers $\ge 0$.

Both sequences are integer sequences of exponential growth, and hence can be expected to have a generating series that is a period. For the sequence $(b_n)$, Zagier mentions that the generating function is even algebraic, but that the sequence $(a_n)$ seems to be more challenging. Yurkevich [72, Theorem 2] proved that the generating function of the sequence $(a_n)$ is
As a final remark, note that Theorem 1.1 in [87] implies that for any prime $p \neq 3$, the reduction modulo $p$ of the ${}_3F_2$ (transcendental) function from Question 2.5 is algebraic (of degree at most $p^{54}$). Hence, even if this ${}_3F_2$ function is not known to be a diagonal of a rational function, its reductions modulo $p$ are known to behave as reductions modulo $p$ of diagonals of rational functions.

## 2.3 Examples from Combinatorics: Walks in the Quarter Plane

In combinatorics, studying the nature of generating functions is of primary importance; for instance, algebraicity may reveal essential (but potentially hidden) recursive structures of the combinatorial classes under consideration. In particular, many examples have been studied over the past decades in lattice path combinatorics, a subfield of enumerative combinatorics. A plethora of interesting mathematical phenomena occur even when restricting to the walks with small steps in the quarter plane $\mathbb{N}^2$. These are walks in the lattice $\mathbb{Z}^2$, confined to the cone $\mathbb{R}_+^2$ that start at the origin $(0, 0)$ and use steps in a model (or stepset) $\mathcal{S}$ which is a fixed subset of the set of nearest-neighbor steps $\{\uparrow, \leftarrow, \nearrow, \searrow, \rightarrow, \nwarrow, \downarrow\}$. The systematic study of small step walks in $\mathbb{N}^2$ has been initiated by Bousquet-Mélou and Mishna in their germinal article [27]. An earlier reference on the topic, in a probabilistic context, is the book [45]. The study of generating functions of walks with small steps in the quarter plane now spans several decades and dozens of articles. For instance, in [38] the differential-algebraic nature of these generating functions is completely elucidated using tools from differential Galois theory. A survey with many references can be found in the recent article [13].

Given a model $\mathcal{S} \subseteq \{\uparrow, \leftarrow, \nearrow, \searrow, \rightarrow, \nwarrow, \downarrow\}$, we denote by $q_{i,j,n}$ the number of $\mathcal{S}$-walks of length $n$ ending at $(i, j)$. The full counting sequence $(q_{i,j,n})_{(i,j,n) \in \mathbb{N}^3}$ admits several interesting specializations, for instance $e_n := q_{0,0,n}$, the number of $\mathcal{S}$-walks of length $n$ returning to $(0, 0)$ ("excursions") and $q_n := \sum_{i,j \ge 0} q_{i,j,n}$, the number of $\mathcal{S}$-walks with prescribed length $n$. To these sequences one attaches various functions, namely the full generating function

$$Q_{\mathcal{S}}(x, y, t) = \sum_{n=0}^{\infty} \left( \sum_{i,j=0}^{\infty} q_{i,j,n} x^i y^j \right) t^n \in \mathbb{Q}[x, y][[t]]$$

and its corresponding univariate specializations $Q_{\mathcal{S}}(0, 0, t) = \sum_{n \ge 0} e_n t^n$ ("excursions generating function"), $Q_{\mathcal{S}}(1, 1, t) = \sum_{n \ge 0} q_n t^n$ ("length generating function"), $Q_{\mathcal{S}}(1, 0, t)$ and $Q_{\mathcal{S}}(0, 1, t)$ ("boundary returns") and $[x^0] Q_{\mathcal{S}}(x, 1/x, t)$ ("diagonal returns").

The general question in this setting is: given a model $\mathcal{S}$, what can be said about the generating function $Q_{\mathcal{S}}(x, y, t)$, and its specializations? In particular, is $Q_{\mathcal{S}}(x, y, t)$ algebraic? Is it at least D-finite? Does $Q_{\mathcal{S}}(x, y, t)$ (or at least some of its specializations) admit closed-form expressions?

The model $\mathcal{S} = \{\uparrow, \rightarrow\}$ in Example 2.1 (Dyck bridges) is one of the simplest possible models. In that case, the generating function $Q_{\mathcal{S}}(x, y, t)$ is algebraic. This is actually a particular case of a classical result stating that whenever $\mathcal{S}$ is included in $\{\uparrow, \nearrow, \rightarrow, \nwarrow, \downarrow\}$ or in $\{\leftarrow, \searrow, \uparrow, \nwarrow, \rightarrow\}$, that is, if the walks are essentially 1-dimensional, then $Q_{\mathcal{S}}(x, y, t)$ is algebraic.

For this reason, most studies in the area focus on the truly 2-dimensional cases, that is on models $\mathcal{S}$ that contain both a step oriented towards the horizontal and the vertical axes (see Figure 1 in [13]). A full classification is now available, according to the algebraic-differential properties of $Q_{\mathcal{S}}(x, y, t)$, but here we restrict to two examples.
<table><thead><tr><th>#</th><th>u</th><th>v</th><th>order</th><th>alg. degree</th><th>#</th><th>u</th><th>v</th><th>order</th><th>alg. degree</th></tr></thead><tbody><tr><td>1</td><td>1/5</td><td>4/5</td><td>2</td><td>120</td><td>6</td><td>19/60</td><td>49/60</td><td>4</td><td>155520</td></tr><tr><td>2</td><td>3/5</td><td>4/5</td><td>2</td><td>120</td><td>7</td><td>19/60</td><td>59/60</td><td>4</td><td>46080</td></tr><tr><td>3</td><td>2/5</td><td>9/10</td><td>4</td><td>120</td><td>8</td><td>29/60</td><td>49/60</td><td>4</td><td>46080</td></tr><tr><td>4</td><td>7/30</td><td>9/10</td><td>4</td><td>155520</td><td>9</td><td>29/60</td><td>59/60</td><td>4</td><td>155520</td></tr><tr><td>5</td><td>9/10</td><td>17/30</td><td>4</td><td>155520</td><td></td><td></td><td></td><td></td><td></td></tr></tbody></table>

Figure 1: Pairs $(u, v)$ for which the sequence $(u)_n \cdot (v)_n \cdot c_n$ is (conjecturally) almost integral. In all cases, the generating functions are (conjecturally) algebraic. Algebraicity degrees are “guessed” by numerical monodromy computations.

also algebraic. (See [34, Thm. 2] for a very closely related result.) Inspired by these results, it is natural to look at the following question.

**Question 2.9.** Find $(u, v) \in \mathbb{Q}$ such that $\tilde{c}_n := w^n \cdot (u)_n \cdot (v)_n \cdot c_n \in \mathbb{Z}$ for all $n \ge 0$, for some $w \in \mathbb{Z}$.

A natural related question is the following.

**Question 2.10.** Is it true that for these $(u, v) \in \mathbb{Q}$, the generating function $\sum_{n \ge 0} \tilde{c}_n x^n$ is algebraic?

In a work (in progress) by Bostan, Weil and Yurkevich, the following result is conjectured:

**Conjecture 2.11.** The only pairs $(u, v) \in \mathbb{Q}^2 \cap (0, 1)^2$ such that there exists $w \in \mathbb{Z}$ such that $\tilde{c}_n := w^n \cdot (u)_n \cdot (v)_n \cdot c_n \in \mathbb{Z}$ for all $n \ge 0$ are the ones listed in Fig. 1. Moreover, for each of these pairs, the corresponding generating function $\sum_{n \ge 0} \tilde{c}_n x^n$ is algebraic, of algebraicity degree as in Fig. 1.

For instance, in case 4 of Figure 1, Conjecture 2.11 states that the generating function of the sequence $\tilde{c}_n := (2^{14} \cdot 3^7 \cdot 5^4)^n \cdot (7/30)_n \cdot (9/10)_n \cdot c_n$,

$$ \sum_{n \ge 0} \tilde{c}_n x^n = 1 - 3042900x + 58917109730850x^2 - 1389307608898903890000x^3 + \dots $$

is an algebraic solution of degree 155520 of the following order-4 (irreducible) operator

$$ \begin{aligned} \mathcal{L}_4 = & 125x^3 (88335360x + 1) (7739670528000x^2 + 31104000x + 1) \partial_x^4 + \\ & 25x^2 (35095911228443197440000x^3 + 95685546737664000x^2 + 2823828480x + 23) \partial_x^3 + \\ & 60x (36896918938488668160000x^3 + 56436938459136000x^2 + 1177963920x + 7) \partial_x^2 + \\ & (1254982687120120872960000x^3 + 654118326337536000x^2 + 16648081920x + 12) \partial_x + \\ & 42055270898174263296000x^2 - 134823448166400x + 36514800. \end{aligned} $$

In particular, this operator admits (conjecturally) only algebraic solutions. To our knowledge, this is an open problem. A heuristic check is based on Conjecture 1.11: it is not difficult to check (using a computer-algebra system) that the remainder of the left Euclidean division of $\partial_x^p$ by $\mathcal{L}_4$ is zero for all primes $5 < p < 100$ except for $p \in \{7, 31\}$. Conjecture 1.11 then suggests that indeed $\mathcal{L}_4$ possesses algebraic solutions only.
### 2.3.1 Trident walks

Up to some canonical reductions, there are exactly 23 models of walks with small steps in the quarter plane whose full generating function $Q(x, y, t)$ is D-finite (with respect to $x, y$ and $t$). They are displayed in Figure 4 in [13].

One of these models is that of the “trident walks”, with $\mathcal{S} = \{\nwarrow, \uparrow, \nearrow, \downarrow\}$. This is entry 7 in [13, Fig. 4] and in [18, Table 6]. There exist 1 trident walk of length 0 (the empty walk), 2 trident walks of length 1 ($\{\uparrow\}, \{\nearrow\}$) and 7 trident walks of length 2 ($\{\uparrow - \uparrow\}, \{\uparrow - \downarrow\}, \{\uparrow - \nearrow\}, \{\nearrow - \uparrow\}, \{\nearrow - \nearrow\}, \{\nearrow - \downarrow\}$). It was proved in [18] that the length generating function of trident walks

$$Q(t) = \sum_{n \ge 0} q_n t^n = 1 + 2t + 7t^2 + 23t^3 + 84t^4 + 301t^5 + 1127t^6 + \dots$$

is D-finite and satisfies $L_5(Q(t)) = 0$, where $L_5$ is the following differential equation of order 5 with polynomial coefficients of degree at most 15:

$$ 
\begin{aligned}
& t^2 (t-1) (4t-1) (12t^2-1) (5184t^7 - 4128t^6 + 4416t^5 + 400t^4 + 252t^3 - 90t^2 - 42t + 3) (4t^2 + 1) \partial_t^5 + \\
& t (21399552t^{13} - 38486016t^{12} + 43416576t^{11} - 25803264t^{10} + 7762176t^9 - 3848960t^8 + \\
& 337088t^7 + 143168t^6 - 7128t^5 + 45328t^4 - 11304t^3 - 1854t^2 + 540t - 27) \partial_t^4 + \\
& (143327232t^{13} - 222621696t^{12} + 257753088t^{11} - 122575104t^{10} + 36213888t^9 - 19897728t^8 + \\
& 1942656t^7 + 70768t^6 - 100456t^5 + 254712t^4 - 35124t^3 - 7404t^2 + 1116t - 48) \partial_t^3 + \\
& (346374144t^{12} - 454643712t^{11} + 545398272t^{10} - 166067712t^9 + 59053824t^8 - 32668800t^7 + \\
& 2167392t^6 + 54912t^5 - 687744t^4 + 500616t^3 - 31176t^2 - 5004t + 288) \partial_t^2 + \\
& (262766592t^{11} - 284000256t^{10} + 358041600t^9 - 21846528t^8 + 33115392t^7 - 13748736t^6 - \\
& 1184640t^5 + 651744t^4 - 894672t^3 + 278496t^2 - 7272t + 2880) \partial_t + \\
& 35831808t^{10} - 31186944t^9 + 42163200t^8 + 11639808t^7 + 4981248t^6 - \\
& 981504t^5 - 809280t^4 + 72576t^3 - 177408t^2 + 8064t - 3168.
\end{aligned}
$$

The length generating function $Q(t)$ is completely and uniquely defined by $L_5$ and by the first coefficients $[t^k]Q(t)$ for $k = 0, \dots, 14$. The question is: how to determine the algebraic or transcendental nature of $Q(t)$?

Note that the asymptotic estimate $q_n \sim \gamma\beta^n n^r$ in [13, Fig. 4], with $\gamma = 4/(3\sqrt{\pi})$, $\beta = 4$, $r = -1/2$, is compatible with algebraicity, since $r \in \mathbb{Q} \setminus \mathbb{Z}_{<0}$, $\beta \in \overline{\mathbb{Q}}$ and $\gamma\Gamma(r+1) = 4/3 \in \overline{\mathbb{Q}}$. Hence we cannot conclude the transcendence using asymptotic arguments as in Example 2.3.

An interesting feature is that $L_5$ admits a factorization $L_2 \cdot L_{1,a} \cdot L_{1,b} \cdot L_{1,c}$, where the three operators $L_{1,*}$ have order 1, and $L_2$ has order 2. This type of factorization $2/1/\dots/1$ actually holds in all the cases 1–19 in [13, Fig. 4]. On the other hand, the algorithmic method (a variant of the creative telescoping mentioned in Section 2.1.1) that produces the differential equation $L_5$ does not guarantee that it is the least-order one satisfied by $Q(t)$. In [18], the above factorization was algorithmically computed and exploited (together with some other computer algebra algorithms) in order to produce the following expression for $Q(t)$ (and
### 3 Grothendieck's conjecture and the p-curvature

The examples presented in §2 motivate the following question: given the linear differential equation (1) with coefficients in $Q(x)$, can we give necessary and/or sufficient conditions for admitting algebraic solutions (either one, or all of them)?

As already mentioned earlier, Grothendieck's conjecture (Conjecture 1.11) provides such a criterion: in its enhanced version (Conjecture 3.16) it relates the existence of a “full basis of algebraic solutions” of the differential equation (1) to the existence of a “full basis of rational solutions” of its reductions modulo almost all prime numbers $p$.

The aim of this section is, first of all, to introduce the notion of p-curvature and to state a precise version of Grothendieck's conjecture. We first examine in details the case of first order equations in §3.1 and come to the general case in §3.2. The next subsections are more focussed on the p-curvature itself: in §3.3, we will describe efficient methods for computing it in practice, while in §3.4, we will examine how it controls the growth of denominators and, in particular, the integrality of the solutions of the starting differential equation.

#### 3.1 The case of equations of order 1

Consider a linear differential operator of order 1

$$ \mathcal{L} = \partial_x + a(x) \qquad (13) $$

with $a(x) \in Q(x)$. It makes sense to consider the reduction $a(x) \mod p \in \mathbb{F}_p(x)$ of (the coefficients of) $a(x)$ modulo $p$ for almost all prime numbers $p$. Thus, one can consider the reduction

$$ \mathcal{L}_p = \partial_x + a(x) \mod p \qquad (14) $$

of $\mathcal{L}$ modulo $p$ for almost all primes $p$. This is a linear differential operator of order 1 with coefficients in $\mathbb{F}_p(x)$. Our aim is to relate the existence of a nonzero algebraic solution of (13) to the existence of nonzero rational solutions of the reduced equations (14).

In what follows, we say that a function $f$ is a solution of $\mathcal{L}$ (resp. of $\mathcal{L}_p$) when it is a solution of the corresponding differential equation, i.e. when $\mathcal{L}(f) = 0$ (resp. $\mathcal{L}_p(f) = 0$).

##### 3.1.1 Rational and algebraic solutions in characteristic 0: a criterion

What makes the case of first order equations tractable is the fact that there is an explicit criterion for the existence of a nonzero algebraic (or rational) solution.

**Proposition 3.1.** The monic first order differential operator (13) has a nonzero rational (resp. algebraic) solution if and only if its constant coefficient $a(x)$ has at most a simple pole with integral (resp. rational) residue at each point of $\overline{Q}$ and vanishes at $\infty$.

*Proof.* We first consider the “rational case”. Let us first assume that $a(x)$ has at most a simple pole with integral residue at each point of $\overline{Q}$ and vanishes at $\infty$. We thus have

$$ a(x) = \sum_{i=1}^{m} \frac{n_i}{x - a_i} $$
similar expressions for all cases 1–19 in [13, Fig. 4]):

$$Q(t) = \frac{1}{t(t-1)} \int_0^t \frac{u}{(1-4u)^{3/2}} \left\{ 4 + \int_0^u \frac{(1-4v)^{1/2}(\frac{1}{2}+v)}{v^2} \left[ 1 + \frac{1}{2v(1+2v)(1+4v^2)^{1/2}} \times \left( (1-v) {}_2F_1\left(\left[\frac{1}{2}, \frac{3}{2}\right], [1]; \frac{16t^2}{4t^2+1}\right) - (1+v)(1-4v+8v^2) {}_2F_1\left(\left[\frac{1}{2}, \frac{1}{2}\right], [1]; \frac{16t^2}{4t^2+1}\right) \right) \right] dv \right\} du.$$

From such an expression, it is not difficult to prove that $Q(t)$ is transcendental, using the fact that the ${}_2F_1$ occurring in the complete elliptic integral of the first kind, ${}_2F_1([1/2, 1/2], [1]; t)$, is transcendental. In [18, §4.2] it was shown that $Q(t)$ is transcendental by exploiting the explicit factorization of $L_5$, and by applying to $L_2$ a specific algorithm that decides algebraicity of solutions for operators of order 2, namely Kovacic's algorithm [62]. The same approach uniformly works on the models 1–19 and allows to prove the transcendence of the corresponding $Q(t)$ except in case 17 for the model $\mathcal{S} = \{\uparrow, \leftarrow, \searrow\}$ and in case 18 for the model $\mathcal{S} = \{\uparrow, \leftarrow, \searrow, \downarrow, \rightarrow, \nwarrow\}$ (in these two cases the algorithm proves algebraicity of all solutions of the corresponding $L_2$). Very interestingly, the full generating function $Q(x, y, t)$ is proved to be transcendental in all cases 1–19, and cases 17 and 18 are the only ones with algebraic specialization $Q(1, 1, t)$.

An alternative proof of the transcendence of the length generating function $Q(t)$ for tri- dent walks is based on the fact that $L_5$ is indeed the minimal-order differential equation for $Q(t)$; this implies that if $Q(t)$ were algebraic, then $L_5$ would only have algebraic solutions, a situation discarded by exhibiting logarithms in the local solutions of $L_5$ at $t = 0$. This approach to the proof of transcendence of solutions of linear differential equations is used in [22]; its heart is the “minimization” algorithm from [21].

### 2.3.2 Gessel walks

The most difficult model of small-step walks in the quarter plane is Gessel's model, for which $\mathcal{S} = \{\uparrow, \leftarrow, \searrow, \rightarrow\}$. For notational simplicity we will write $G(x, y, t)$ for the full generating function in this case, and $G(t)$ for the length generating function for Gessel walks $G(1, 1, t)$.

Around 2000, Ira Gessel formulated two conjectures equivalent to the following statements:

**Conjecture 2.6.** The generating function $G(0, 0, t) = 1+2t^2+11t^4+85t^6+782t^7+\cdots$ of Gessel excursions is equal to ${}_3F_2([5/6, 1/2, 1], [5/3, 2]; 16t^2)$.

**Conjecture 2.7.** The generating function $G(x, y, t)$ is not D-finite.

Gessel's first conjecture was first solved in 2009 by Kauers, Koutschan and Zeilberger in [58] using a computerized guess-and-prove approach. Unfortunately, solving Conjecture 2.6 had no implication concerning Conjecture 2.7, and in particular on the D-finiteness of the length generating function $G(t)$. It came as a total surprise when Bostan and Kauers [19] proved that Gessel's second conjecture was false.

**Theorem 2.8 ([19]).** The generating function $G(x, y, t)$ for Gessel walks is algebraic.

Moreover, the coefficients $(g_n)$ of $G(t) = 1 + 2t + 7t^2 + 21t^3 + 78t^4 + 260t^5 + \cdots$ satisfy $(3n + 1) g_{2n} = (12n + 2) g_{2n-1}$ and $(n + 1) g_{2n+1} = (4n + 2) g_{2n}$ for all $n \ge 0$.
for some $a_i \in \overline{\mathbb{Q}}$ and some $n_i \in \mathbb{Z}$. A straightforward calculation shows that

$$f(x) = \prod_{i=1}^{m} (x - a_i)^{n_i}$$

is a nonzero rational solution of (13).

Conversely, assume that (13) has a nonzero rational solution $f(x)$. This $f(x)$ can be factored as a product of linear factors $f(x) = c \prod_{i=1}^{m} (x - a_i)^{n_i}$ with $c \in \overline{\mathbb{Q}}^\times$, $a_i \in \overline{\mathbb{Q}}$ and $n_i \in \mathbb{Z}$. A straightforward calculation yields

$$a(x) = \frac{f'(x)}{f(x)} = \sum_{i=1}^{m} \frac{n_i}{x - a_i}.$$

This shows that $a(x)$ has at most a simple pole with integral residue at each point of $\overline{\mathbb{Q}}$ and vanishes at $\infty$, as expected.

We now consider the “algebraic case”. Let us first assume that $a(x)$ has at most a simple pole with rational residue at each point of $\overline{\mathbb{Q}}$ and vanishes at $\infty$. We thus have

$$a(x) = \sum_{i=1}^{m} \frac{e_i}{x - a_i}$$

for some $a_i \in \overline{\mathbb{Q}}$ and some $e_i \in \mathbb{Q}$. Then, again, a straightforward calculation shows that

$$f(x) = \prod_{i=1}^{m} (x - a_i)^{e_i}$$

is a nonzero algebraic solution of (13).

Conversely, assume that (13) has a nonzero algebraic solution $f(x)$. Let $M(Y) = Y^N + \sum_{i=0}^{N-1} m_i(x)Y^i \in \mathbb{Q}(x)[Y]$ be the minimal polynomial of $f(x)$ over $\mathbb{Q}(x)$. By differentiating the equality $M(f) = 0$ with respect to $x$ and by using $f'(x) = a(x)f(x)$, we get

$$\begin{aligned} 0 = M(f)' &= Nf^{N-1}f' + \sum_{i=0}^{N-1} m_i'(x)f^i + \sum_{i=0}^{N-1} m_i(x)if^{i-1}f' \\ &= Nf^{N-1}a(x)f + \sum_{i=0}^{N-1} m_i'(x)f^i + \sum_{i=0}^{N-1} m_i(x)if^{i-1}a(x)f \\ &= Na(x)f^N + \sum_{i=0}^{N-1} (m_i'(x) + m_i(x)ia(x))f^i. \end{aligned}$$

Hence, the polynomial $P(Y) = Na(x)Y^N + \sum_{i=0}^{N-1} (m_i'(x) + m_i(x)ia(x))Y^i$ satisfies $P(f) = 0$. By minimality of $M(Y)$, we get $P(Y) = Na(x)M(Y)$. Equating the constant terms in this equality, we get that $m_0(x)$ is a nonzero solution in $\mathbb{Q}(x)$ of $y'(x) = Na(x)y(x)$. Using the “rational case” treated above, we get that $Na(x)$ has at most a simple pole with integral residue at each point of $\overline{\mathbb{Q}}$ and vanishes at $\infty$. Hence, $a(x)$ has at most a simple pole with rational residue at each point of $\overline{\mathbb{Q}}$ and vanishes at $\infty$, as expected. $\square$

Note that the proof above is very similar (in fact, generalizes) the one used in Example 1.2 to prove that the exponential function is transcendental.
In addition, $G(t) = (H(t) - 1)/(2t)$ where $H(t) = 1 + 2t + 4t^2 + 14t^3 + 42t^4 + \cdots$ is a root of $27(4t - 1)^2 H(t)^8 - 18(4t - 1)^2 H(t)^4 - 8(16t^2 + 24t + 1) H(t)^2 - (4t - 1)^2 = 0$, and

$$H(t) = {}_2F_1\left(\left[-\frac{1}{12}, \frac{1}{4}\right], \left[\frac{2}{3}\right]; -\frac{64t(4t+1)^2}{(4t-1)^4}\right).$$

The original discovery and proof of Theorem 2.8 was computer-driven, and used a guess-and-prove approach, based on Hermite-Padé approximants. As a byproduct of this proof, the minimal polynomial of $G(x, y, t)$ has been estimated to have more than $10^{11}$ terms when written in expanded form, for a total size of $\approx 30$ Gb (!). The guess-and-prove method is a 3-step process: (i) compute $G(x, y, t)$ to precision $t^{1200}$ ($\approx 1.5$ billion coefficients!); (ii) conjecture polynomial equations for $G(x, 0, t)$ and $G(0, y, t)$; (iii) conclude the proof by computing multivariate resultants of (very big) polynomials (30 pages each).

As a matter of fact, the discovery of algebraicity was initially performed in a different way: the expansion of the generating function $G(x, y, t)$ modulo $t^{1000}$ was sufficient to guess (by using differential Hermite-Padé approximants) two differential operators

* $\mathcal{L}_{x,0} \in \mathbb{Q}(x,t)\langle\partial_t\rangle$, of order 11 in $\partial_t$, bidegree (96, 78) in $(t, x)$, and integer coefficients of at most 61 digits

* $\mathcal{L}_{0,y} \in \mathbb{Q}(y,t)\langle\partial_t\rangle$, of order 11 in $\partial_t$, bidegree (68, 28) in $(t, y)$, and integer coefficients of at most 51 digits

such that $\mathcal{L}_{x,0}(G(x, 0, t)) = 0 \mod t^{1000}$ and $\mathcal{L}_{0,y}(G(0, y, t)) = 0 \mod t^{1000}$.

After this guessing step of plausible differential equations for $Q(x, 0, t)$ and for $Q(0, y, t)$, an important step in the discovery process was to apply Conjecture 1.13 with several primes $p$. More precisely, for randomly chosen prime numbers $p$, and $a, b \in \mathbb{F}_p$, both $\mathcal{L}_{a,0}$ and $\mathcal{L}_{0,b}$ rightdivide the pure power $\partial_t^p$ in $\mathbb{F}_p(x)\langle\partial_t\rangle$; in other terms, they have zero $p$-curvature for all the tested primes $p$ (see Definition 3.18). This was the key observation in the discovery [19] that the trivariate generating function for Gessel walks is algebraic.

Several human proofs of Conjecture 2.6 and Theorem 2.8 have been discovered since the publication of [19]: the first one used complex analysis [20], the second one is purely algebraic [26], the third one is both combinatorial and analytic [28], while the more recent one is probably the most elementary [8].

## 2.4 Examples from Number Theory

In his ICM 2018 paper [89, p. 768], Zagier introduced a recurrent sequence of rational numbers $(c_n)_{n \ge 0}$ defined by initial terms $c_0 = 1$, $c_1 = -161/(2^{10} \cdot 3^5)$ and $c_2 = 26605753/(2^{23} \cdot 3^{12} \cdot 5^2)$, and by the following linear recursion with polynomial coefficients:

$$c_{n-3} + 20(4500n^2 - 18900n + 19739) c_{n-2} + 80352000n(5n-1)(5n-2)(5n-4)c_n + 25(2592000n^4 - 16588800n^3 + 39118320n^2 - 39189168n + 14092603) c_{n-1} = 0.$$

This mysteriously looking sequences arises from a topological differential equation in the work of Bertola, Dubrovin and Yang [9], each coefficient $c_n$ being defined by an integral over the Deligne-Mumford moduli spaces of stable curves of genus $g$ with $n$ marked points. It is not
### 3.1.2 Algebraic solutions: from characteristic 0 to characteristic p

We shall now consider the following question: assuming that (13) has a nonzero algebraic solution, what can be said about the reduced equation (14)? It is natural to expect that the latter has a nonzero algebraic solution as well for almost all primes $p$. Actually, something even better happens.

**Example 3.2.** Consider the differential equation

$$y' = \frac{1}{2(x-1)}y. \qquad (15)$$

It has a nonzero algebraic solution, namely $f(x) = (1-x)^{1/2}$. For any prime $p \neq 2$, one can consider the reduction of (15) modulo $p$. Any such reduced equation has a nonzero algebraic solution, namely $f_p(x) = (1-x)^{1/2}$. Let us clarify our notations: $f_p(x)$ is a root of the polynomial $Y^2 - (1-x) \in \mathbb{F}_p(x)[Y]$, whereas $f(x)$ is a root of the polynomial $Y^2 - (1-x) \in \mathbb{Q}(x)[Y]$. However, the reduction of (15) modulo $p$ can also be written as $y' = \frac{n_p}{x-1}y$ where $n_p \in \mathbb{Z}$ is such that $n_p \equiv \frac{1}{2} \mod p$ and, hence $\tilde{f}_p(x) = (1-x)^{n_p}$ is a nonzero solution of the reduction modulo $p$ of (15). The interesting point is that $\tilde{f}_p(x)$ is not only algebraic but rational, contrary to $f_p(x)$!

The conclusion of this example is a general fact as shown by Theorem 3.5 below. Let us first give an analogue in positive characteristic of the “rational case” of Proposition 3.1.

**Proposition 3.3.** Consider $b(x) \in \mathbb{F}_p(x)$. The differential equation

$$y' + b(x)y = 0$$

has a nonzero rational solution if and only if $b(x)$ has at most a simple pole with residue in $\mathbb{F}_p$ at each point of $\overline{\mathbb{F}}_p$ and vanishes at $\infty$.

*Proof.* The proof is entirely similar to the proof of the rational case of Proposition 3.1, it is sufficient to replace everywhere $\overline{\mathbb{Q}}$ by $\overline{\mathbb{F}}_p$ and $\mathbb{Z}$ by $\mathbb{F}_p$. $\square$

**Example 3.4.** Consider the differential equation

$$y' = \frac{1}{x^2 + 1}y \qquad (16)$$

whose general solution in characteristic zero is $c \cdot \exp(\arctan(x))$ where $c$ is a constant. We are interested in determining whether or not this equation has a rational solution in characteristic $p > 0$. Modulo $p = 2$, the rational function $b(x) = 1/(x^2 + 1)$ writes $1/(x+1)^2$; thus it has a pole of order 2 and hence the differential equation (16) has no nonzero rational solutions by Proposition 3.3. For $p \neq 2$, the partial fraction decomposition of $b(x)$ reads

$$b(x) = \frac{i}{2} \cdot \left( \frac{1}{x+i} - \frac{1}{x-i} \right)$$

where $i$ denotes a square root of $-1$ in $\overline{\mathbb{F}}_p$. We now need to distinguish between two cases depending on the congruence class of $p$ modulo 4. Indeed, when $p \equiv 1 \pmod 4$, we have
<table><thead><tr><th>#</th><th>u</th><th>v</th><th>order</th><th>alg. degree</th><th>#</th><th>u</th><th>v</th><th>order</th><th>alg. degree</th></tr></thead><tbody><tr><td>1</td><td>1/5</td><td>4/5</td><td>2</td><td>120</td><td>6</td><td>19/60</td><td>49/60</td><td>4</td><td>155520</td></tr><tr><td>2</td><td>3/5</td><td>4/5</td><td>2</td><td>120</td><td>7</td><td>19/60</td><td>59/60</td><td>4</td><td>46080</td></tr><tr><td>3</td><td>2/5</td><td>9/10</td><td>4</td><td>120</td><td>8</td><td>29/60</td><td>49/60</td><td>4</td><td>46080</td></tr><tr><td>4</td><td>7/30</td><td>9/10</td><td>4</td><td>155520</td><td>9</td><td>29/60</td><td>59/60</td><td>4</td><td>155520</td></tr><tr><td>5</td><td>9/10</td><td>17/30</td><td>4</td><td>155520</td><td></td><td></td><td></td><td></td><td></td></tr></tbody></table>

Figure 2: Pairs $(u, v)$ for which the sequence $(u)_n \cdot (v)_n \cdot c_n$ is (conjecturally) almost integral. In all cases, the generating functions are (conjecturally) algebraic. Algebraicity degrees are “guessed” by numerical monodromy computations.

difficult to prove that $c_n$ behaves asymptotically like $1/n!^2$. Inspired by an analogy with the behavior of the quantum periods in mirror symmetry, Zagier asked whether it is possible that the $c_n$'s become integers after multiplication by $n!^2$, or more generally by the product of two rising factorials. Zagier mentions the following highly nontrivial two results:

* [Yang & Zagier]: $a_n := (2^{10} \cdot 3^5 \cdot 5^4)^n \cdot (3/5)_n \cdot (4/5)_n \cdot c_n \in \mathbb{Z}$ for all integers $n \ge 0$;

* [Dubrovin & Yang]: $b_n := (2^{12} \cdot 3^5 \cdot 5^4)^n \cdot (2/5)_n \cdot (9/10)_n \cdot c_n \in \mathbb{Z}$ for all integers $n \ge 0$.

Both sequences are integer sequences of exponential growth, and hence can be expected to have a generating series that is (the Taylor expansion at 0 of) a period function in the sense of algebraic geometry. For the sequence $(b_n)$, Zagier mentions that its generating function is even algebraic, but that the sequence $(a_n)$ seems to be more challenging. Yurkevich [88, Theorem 2] proved that the generating function of the sequence $(a_n)$ is also algebraic. (See [40, Thm. 2] for a very closely related result.) Inspired by these results, it is natural to look at the following question.

**Question 2.9.** Find $(u, v) \in \mathbb{Q}$ such that $\tilde{c}_n := w^n \cdot (u)_n \cdot (v)_n \cdot c_n \in \mathbb{Z}$ for all $n \ge 0$, for some $w \in \mathbb{Z}$.

A natural related question is the following.

**Question 2.10.** Is it true that for these $(u, v) \in \mathbb{Q}$, the generating function $\sum_{n \ge 0} \tilde{c}_n x^n$ is algebraic?

In a work (in progress) by Bostan, Weil and Yurkevich, the following result is conjectured:

**Conjecture 2.11.** The only pairs $(u, v) \in \mathbb{Q}^2 \cap (0, 1)^2$ such that there exists $w \in \mathbb{Z}$ such that $\tilde{c}_n := w^n \cdot (u)_n \cdot (v)_n \cdot c_n \in \mathbb{Z}$ for all $n \ge 0$ are the ones listed in Fig. 2. Moreover, for each of these pairs, the corresponding generating function $\sum_{n \ge 0} \tilde{c}_n x^n$ is algebraic, of algebraicity degree as in Fig. 2.

For instance, in case 4 of Figure 2, Conjecture 2.11 states that the generating function of the sequence $\tilde{c}_n := (2^{14} \cdot 3^7 \cdot 5^4)^n \cdot (7/30)_n \cdot (9/10)_n \cdot c_n$,

$$ \sum_{n \ge 0} \tilde{c}_n x^n = 1 - 3042900x + 58917109730850x^2 - 1389307608898903890000x^3 + \dots $$
$i \in \mathbb{F}_p$ and so the residues belong to $\mathbb{F}_p$ as well. In this case, the equation (16) has then a nonzero rational solution, namely

$$y(x) = \left( \frac{x+i}{x-i} \right)^{i/2},$$

where the exponent $i/2$ is a lift in $\mathbb{Z}$ of $i/2 \in \mathbb{F}_p$. On the contrary, when $p \equiv 3 \pmod 4$, we know that $-1$ is not a square in $\mathbb{F}_p$, showing that the residues are not is $\mathbb{F}_p$ either. Therefore, in this case, the equation (16) has no nonzero rational solution.

**Theorem 3.5.** If (13) has a nonzero algebraic solution, then, for almost all primes $p$, (14) has a nonzero rational solution.

*Proof.* Proposition 3.1 (and its proof) ensures that

$$a(x) = \sum_{i=1}^{m} \frac{e_i}{x - a_i} \qquad (17)$$

for some $a_i \in \overline{\mathbb{Q}}$ and some $e_i \in \mathbb{Q}$.

Let us first assume that the $a_i$'s belong to $\mathbb{Q}$. For any prime $p$, we let $\mathbb{Z}_{(p)}$ be the ring of rational numbers with denominator relatively prime to $p$. We denote by $\pi_p : \mathbb{Z}_{(p)} \to \mathbb{F}_p$ the “reduction modulo $p$” map. For almost all primes $p$, the $a_i$'s and the $e_i$'s belong to $\mathbb{Z}_{(p)}$. For any such $p$, we have:

$$a(x) \mod p = \sum_{i=1}^{m} \frac{\pi_p(e_i)}{x - \pi_p(a_i)}$$

and the result follows from Proposition 3.3.

The proof in the general case is similar but requires basic notions from algebraic number theory. Let $K$ be a number field containing the $a_i$ and the $e_i$. Let $\mathcal{O}_K$ be the ring of integers of $K$. For any prime $\mathfrak{P}$ of $K$ (which is by definition a prime ideal of $\mathcal{O}_K$), we let $\mathcal{O}_{\mathfrak{P}}$ be the valuation ring of $K$ at $\mathfrak{P}$. We denote by $\kappa_{\mathfrak{P}}$ the corresponding residue field and by $\pi_{\mathfrak{P}} : \mathcal{O}_{\mathfrak{P}} \to \kappa_{\mathfrak{P}}$ the quotient map. The residue field $\kappa_{\mathfrak{P}}$ is a finite field of characteristic $p$ such that $\mathfrak{P} \cap \mathbb{Z} = (p)$. We say that $\mathfrak{P}$ is above $p$. For almost all primes $p$, for all primes $\mathfrak{P}$ of $K$ above $p$, the $a_i$'s and the $e_i$'s belong to $\mathcal{O}_{\mathfrak{P}}$. For such $p$ and $\mathfrak{P}$, we have:

$$a(x) \mod p = a(x) \mod \mathfrak{P} = \sum_{i=1}^{m} \frac{\pi_{\mathfrak{P}}(e_i)}{x - \pi_{\mathfrak{P}}(a_i)}.$$

Since $e_i$ is rational, $\pi_{\mathfrak{P}}(e_i)$ belongs to the prime subfield $\mathbb{F}_p$ of $\kappa_{\mathfrak{P}}$. The result follows from Proposition 3.3. $\square$

### 3.1.3 From characteristic $p$ to characteristic $0$

It is now tempting to ask: if (14) has a nonzero rational solution for almost all primes $p$, does (13) have a nonzero algebraic solution? The (positive) answer is given by the following result.

**Theorem 3.6 (Honda [43]).** The converse of Theorem 3.5 holds true, i.e., if, for almost all primes $p$, (14) has a nonzero rational solution, then (13) has a nonzero algebraic solution.
is an algebraic solution of degree 155520 of the following order-4 (irreducible) operator

$$ \mathcal{L}_4 = 125x^3 (88335360x + 1) (7739670528000x^2 + 31104000x + 1) \partial_x^4 + 25x^2 (35095911228443197440000x^3 + 95685546737664000x^2 + 2823828480x + 23) \partial_x^3 + 60x (36896918938488668160000x^3 + 56436938459136000x^2 + 1177963920x + 7) \partial_x^2 + (1254982687120120872960000x^3 + 654118326337536000x^2 + 16648081920x + 12) \partial_x + 42055270898174263296000x^2 - 134823448166400x + 36514800. $$

In particular, this operator admits (conjecturally) only algebraic solutions. To our knowledge, this is an open problem. A heuristic check is based on Conjecture 1.13: it is not difficult to check (using a computer-algebra system) that the remainder of the right Euclidean division of $\partial_x^p$ by $\mathcal{L}_4$ is zero for all primes $5 < p < 100$ except for $p \in \{7, 31\}$. Conjecture 1.13 then suggests that indeed $\mathcal{L}_4$ possesses algebraic solutions only.

# 3 Grothendieck's conjecture

The examples presented in §2 motivate the following question: given the linear differential equation (1) with coefficients in $\mathbb{Q}(x)$, can we give necessary and/or sufficient conditions for admitting algebraic solutions (either one, or all of them)?

As already mentioned earlier, Grothendieck's conjecture (Conjecture 1.13) provides such a criterion: in its enhanced version (Conjecture 3.17) it relates the existence of a "full basis of algebraic solutions" of the differential equation (1) to the existence of a "full basis of rational solutions" of its reductions modulo almost all prime numbers $p$.

The aim of this section is, first of all, to introduce the notion of $p$-curvature and to state a precise version of Grothendieck's conjecture. We first examine in detail the case of first order equations in §3.1 and come to the general case in §3.2. The next sections are more focussed on the $p$-curvature itself: in §4, we describe efficient methods for computing it in practice, while in §5, we examine how it controls the growth of denominators and, in particular, the integrality of the solutions of the starting differential equation.

## 3.1 The case of equations of order 1

Consider a linear differential operator of order 1

$$ \mathcal{L} = \partial_x + a(x) \qquad (15) $$

with $a(x) \in \mathbb{Q}(x)$. It makes sense to consider the reduction $a(x) \mod p \in \mathbb{F}_p(x)$ of (the coefficients of) $a(x)$ modulo $p$ for almost all prime numbers $p$. Thus, one can consider the reduction

$$ \mathcal{L}_p = \partial_x + a(x) \mod p \qquad (16) $$

of $\mathcal{L}$ modulo $p$ for almost all primes $p$. This is a linear differential operator of order 1 with coefficients in $\mathbb{F}_p(x)$. Our aim is to relate the existence of a nonzero algebraic solution of (15) to the existence of nonzero rational solutions of the reduced equations (16).

In what follows, we say that a function $f$ is a solution of $\mathcal{L}$ (resp. of $\mathcal{L}_p$) when it is a solution of the corresponding differential equation, i.e. when $\mathcal{L}(f) = 0$ (resp. $\mathcal{L}_p(f) = 0$).
Proof. Consider the partial fraction decomposition of $a(x)$:

$$a(x) = P(x) + \sum_{i=1}^{m} \sum_{j=1}^{r_i} \frac{\alpha_{i,j}}{(x - a_i)^j}$$

with $P(x) \in \overline{\mathbb{Q}}[x]$, $a_i \in \overline{\mathbb{Q}}$, $\alpha_{i,j} \in \overline{\mathbb{Q}}$ and $r_j \in \mathbb{Z}_{\ge 1}$. According to Proposition 3.1, we have to prove that $P(x)$ and the $\alpha_{i,j}$'s for $j \ge 2$ are 0 and that the $\alpha_{i,1}$'s belong to $\mathbb{Q}$.

Let $K$ be a number field containing the $a_i$, the $\alpha_{i,j}$'s and the coefficients of $P(x)$. We will use the notation and terminology (prime $\mathfrak{P}$ of $K$, valuation ring $\mathcal{O}_{\mathfrak{P}}$, quotient map $\pi_{\mathfrak{P}}$, etc.) introduced in Theorem 3.5. For almost all primes $p$, for all primes $\mathfrak{P}$ of $K$ above $p$, the $a_i$'s, the $\alpha_{i,j}$'s and the coefficients of $P(x)$ belong to $\mathcal{O}_{\mathfrak{P}}$. For such $p$ and $\mathfrak{P}$, we have:

$$a(x) \mod p = a(x) \mod \mathfrak{P} = P^{\pi_{\mathfrak{P}}}(x) + \sum_{i=1}^{m} \sum_{j=1}^{r_i} \frac{\pi_{\mathfrak{P}}(\alpha_{i,j})}{(x - \pi_{\mathfrak{P}}(a_i))^j},$$

where $P^{\pi_{\mathfrak{P}}}(x)$ denotes the polynomial obtained from $P(x)$ by applying $\pi_{\mathfrak{P}}$ coefficientwise.

Proposition 3.3 ensures that, for almost all primes $p$, $a(x) \mod p$ has at most simple poles, so, for almost all primes $p$, for all primes $\mathfrak{P}$ of $K$ above $p$, for all $j \in \{2, \dots, r_i\}$, we have $\pi_{\mathfrak{P}}(\alpha_{i,j}) = 0$, i.e., $\alpha_{i,j} \in \mathfrak{P}$. This implies that, for all $j \in \{2, \dots, r_i\}$, we have $\alpha_{i,j} = 0$. Similarly, Proposition 3.3 also ensures that, for almost all primes $p$, $a(x) \mod p$ vanishes at $\infty$, so, for almost all primes $p$, for all primes $\mathfrak{P}$ of $K$ above $p$, $P^{\pi_{\mathfrak{P}}}(x) = 0$. This implies that $P(x) = 0$. Last, Proposition 3.3 ensures that, for almost all primes $p$, for all primes $\mathfrak{P}$ above $p$, we have $\pi_{\mathfrak{P}}(\alpha_{i,1}) \in \mathbb{F}_p$. Using Kronecker's Theorem recalled below, we get that $\alpha_{i,1}$ belongs to $\mathbb{Q}$ and Proposition 3.1 yields the desired result: (13) has a nonzero algebraic solution. $\square$

The Kronecker Theorem mentioned above (which is usually seen as a consequence of Chebotarev's density Theorem) reads as follows

**Theorem 3.7 (Kronecker).** An irreducible element $P(x)$ of $\overline{\mathbb{Q}}[x]$ such that, for almost all primes $p$, $P(x) \mod p$ has a zero in $\mathbb{F}_p$ is linear.

### 3.1.4 Rational solutions in characteristic $p$ and $p$-curvature

Consider a differential equation

$$y' + b(x)y = 0 \qquad (18)$$

with $b(x) \in \mathbb{F}_p(x)$. We will give an alternative criterion (an alternative to Proposition 3.3) for determining whether (18) has a nonzero rational solution based on the notion of $p$-curvature that we shall now introduce.

Consider the $\mathbb{F}_p(x^p)$-linear map

$$\Delta : \mathbb{F}_p(x) \to \mathbb{F}_p(x) \\ f \mapsto f' + b(x)f.$$

The additivity is clear, the homogeneity follows from the fact the elements of $\mathbb{F}_p(x^p)$ are constants of (the differential field) $\mathbb{F}_p(x)$ in the sense that their derivative is 0 (more precisely, $\mathbb{F}_p(x^p) = \{f(x) \in \mathbb{F}_p(x) \mid f'(x) = 0\}$) implying that $(\alpha f)' = \alpha f'$ for all $\alpha \in \mathbb{F}_p(x^p)$ and $f \in \mathbb{F}_p(x)$.
### 3.1.1 Rational and algebraic solutions in characteristic 0: a criterion

What makes the case of first order equations tractable is the fact that there is an explicit criterion for the existence of a nonzero algebraic (or rational) solution.

**Proposition 3.1.** The monic first order differential operator (15) has a nonzero rational (resp. algebraic) solution if and only if its constant coefficient $a(x)$ has at most a simple pole with integral (resp. rational) residue at each point of $\overline{\mathbb{Q}}$ and vanishes at $\infty$.

*Proof.* We first consider the “rational case”. Let us first assume that $a(x)$ has at most a simple pole with integral residue at each point of $\overline{\mathbb{Q}}$ and vanishes at $\infty$. We thus have

$$a(x) = \sum_{i=1}^{m} \frac{n_i}{x - a_i} \qquad (17)$$

for some $a_i \in \overline{\mathbb{Q}}$ and some $n_i \in \mathbb{Z}$. A straightforward calculation shows that

$$f(x) = \prod_{i=1}^{m} (x - a_i)^{n_i} \qquad (18)$$

is a nonzero rational solution of (15).

Conversely, assume that (15) has a nonzero rational solution $f(x)$. This $f(x)$ can be factored as a product of linear factors $f(x) = c \prod_{i=1}^{m} (x - a_i)^{n_i}$ with $c \in \overline{\mathbb{Q}}^\times$, $a_i \in \overline{\mathbb{Q}}$ and $n_i \in \mathbb{Z}$. A straightforward calculation yields

$$a(x) = \frac{f'(x)}{f(x)} = \sum_{i=1}^{m} \frac{n_i}{x - a_i}.$$

This shows that $a(x)$ has at most a simple pole with integral residue at each point of $\overline{\mathbb{Q}}$ and vanishes at $\infty$, as expected.

We now consider the “algebraic case”. Let us first assume that $a(x)$ has at most a simple pole with rational residue at each point of $\overline{\mathbb{Q}}$ and vanishes at $\infty$. Then, we can argue as we did above in the rational case, the only differences being that the $n_i$ involved in (17) are no longer in $\mathbb{Z}$ but in $\mathbb{Q}$ and that (18) is no longer rational but algebraic.

Conversely, assume that (15) has a nonzero algebraic solution $f(x)$. Let $M(Y) = Y^N + \sum_{i=0}^{N-1} m_i(x) Y^i \in \mathbb{Q}(x)[Y]$ be the minimal polynomial of $f(x)$ over $\mathbb{Q}(x)$. By differentiating the equality $M(f) = 0$ with respect to $x$ and by using $f'(x) = a(x)f(x)$, we get

$$\begin{aligned} 0 = M(f)' &= N f^{N-1} f' + \sum_{i=0}^{N-1} m_i'(x) f^i + \sum_{i=0}^{N-1} m_i(x) i f^{i-1} f' \\ &= N f^{N-1} a(x) f + \sum_{i=0}^{N-1} m_i'(x) f^i + \sum_{i=0}^{N-1} m_i(x) i f^{i-1} a(x) f \\ &= Na(x) f^N + \sum_{i=0}^{N-1} (m_i'(x) + m_i(x) i a(x)) f^i. \end{aligned}$$
**Definition 3.8.** The map

$$ \Delta^p : \mathbb{F}_p(x) \to \mathbb{F}_p(x) $$

is called the *p*-curvature of (18).

A remarkable and fundamental fact is that the *p*-curvature is not only $\mathbb{F}_p(x^p)$-linear but it is also $\mathbb{F}_p(x)$-linear. Indeed, a simple induction along with the Leibniz rule show that, for all $k \ge 0$, for all $\alpha, f \in \mathbb{F}_p(x)$, we have

$$ \Delta^k(\alpha f) = \sum_{i=0}^{k} \binom{k}{i} \alpha^{(i)} \Delta^{k-i}(f). $$

Taking $k = p$ and using the fact that $\binom{p}{i} \equiv 0 \mod p$ for all $1 < i < p$, we get

$$ \Delta^p(\alpha f) = \alpha^{(p)} + \alpha \Delta^p(f), $$

and therefore the $\mathbb{F}_p(x)$-homogeneity follows from the fact that $\alpha^{(p)} = 0$.

**Proposition 3.9.** The differential equation (18) has a nonzero rational solution if and only if $\Delta^p = 0$.

*Proof.* If (18) has a nonzero rational solution $f$, then $\Delta(f) = 0$ and, hence, $\Delta^p(f) = 0$. As $\Delta^p$ is $\mathbb{F}_p(x)$-linear, we get $\Delta^p = 0$. Conversely, if $\Delta^p = 0$, then $\Delta$ has a nonzero kernel (otherwise, $\Delta$ and, hence, $\Delta^p$ would be $\mathbb{F}_p(x^p)$-linear isomorphisms of $\mathbb{F}_p(x)$). $\square$

**Remark 3.10.** Actually, an easy calculation shows that, if (18) has *p*-curvature 0, then an explicit nonzero rational solution is given by

$$ \sum_{k=0}^{p-1} (-1)^k \frac{x^k}{k!} \Delta^k(1). $$

We conclude this section by giving inductive and closed formulae for the *p*-curvature. As it is $\mathbb{F}_p(x)$-linear, the *p*-curvature is entirely determined by its value at 1:

$$ \forall f \in \mathbb{F}_p(x), \Delta^p(f) = \Delta^p(1)f. $$

For this reason, we often say that the *p*-curvature of (18) is $\Delta^p(1)$.

It turns out that the *p*-curvature $\Delta^p(1)$ can be calculated inductively. Indeed, we first notice that, for all $k \ge 0$, we have in the ring of differential operators a relation of the form

$$ (\partial_x + b(x))^k = \partial_x^k + \star \partial_x^{k-1} + \cdots + \star \partial_x + b_k(x), \quad (19) $$

where $\star$ are some unspecified elements of $\mathbb{F}_p(x)$. Equating the terms of degree 0 (with respect to $\partial_x$) in the equality $(\partial_x + b(x))^{k+1} = (\partial_x + b(x)) \cdot (\partial_x + b(x))^k$, we get the following inductive formula for computing the $b_k(x)$'s:

$$ \forall k \ge 0, \quad b_{k+1}(x) = b'_{k}(x) + b(x)b_{k}(x). \quad (20) $$

This gives the expected inductive formula for the *p*-curvature of (18), since this is equal to

$$ \Delta^p(1) = b_p(x). $$
Hence, the polynomial $P(Y) = Na(x)Y^N + \sum_{i=0}^{N-1}(m'_i(x) + m_i(x)ia(x))Y^i$ satisfies $P(f) = 0$. By minimality of $M(Y)$, we get $P(Y) = Na(x)M(Y)$. Equating the constant terms in this equality, we get that $m_0(x)$ is a nonzero solution in $\mathbb{Q}(x)$ of $y'(x) = Na(x)y(x)$. Using the "rational case" treated above, we get that $Na(x)$ has at most a simple pole with integral residue at each point of $\overline{\mathbb{Q}}$ and vanishes at $\infty$. Hence, $a(x)$ has at most a simple pole with rational residue at each point of $\overline{\mathbb{Q}}$ and vanishes at $\infty$, as expected. $\square$

Note that the proof above is very similar (in fact, generalizes) the one used in Example 1.2 to prove that the exponential function is transcendental.

### 3.1.2 Algebraic solutions: from characteristic 0 to characteristic $p$

We shall now consider the following question: assuming that (15) has a nonzero algebraic solution, what can be said about the reduced equation (16)? It is natural to expect that the latter has a nonzero algebraic solution as well for almost all primes $p$. Actually, something even better happens.

**Example 3.2.** Consider the differential equation

$$y' = \frac{1}{2(x-1)}y. \qquad (19)$$

It has a nonzero algebraic solution, namely $f(x) = (1-x)^{1/2}$. For any prime $p \neq 2$, one can consider the reduction of (19) modulo $p$. Any such reduced equation has a nonzero algebraic solution, namely $f_p(x) = (1-x)^{1/2}$. Let us clarify our notations: $f_p(x)$ is a root of the polynomial $Y^2 - (1-x) \in \mathbb{F}_p(x)[Y]$, whereas $f(x)$ is a root of the polynomial $Y^2 - (1-x) \in \mathbb{Q}(x)[Y]$. However, the reduction of (19) modulo $p$ can also be written as $y' = \frac{n_p}{x-1}y$ where $n_p \in \mathbb{Z}$ is such that $n_p \equiv \frac{1}{2} \mod p$ and, hence $\tilde{f}_p(x) = (1-x)^{n_p}$ is a nonzero solution of the reduction modulo $p$ of (19). The interesting point is that $\tilde{f}_p(x)$ is not only algebraic but rational, contrary to $f_p(x)$!

The conclusion of Example 3.2 is a general fact as shown by Theorem 3.5 below. Let us first give an analogue in positive characteristic of the "rational case" of Proposition 3.1.

**Proposition 3.3.** Consider $b(x) \in \mathbb{F}_p(x)$. The differential equation

$$y' + b(x)y = 0$$

has a nonzero rational solution if and only if $b(x)$ has at most a simple pole with residue in $\mathbb{F}_p$ at each point of $\overline{\mathbb{F}}_p$ and vanishes at $\infty$.

*Proof.* The proof is entirely similar to the proof of the rational case of Proposition 3.1, it is sufficient to replace everywhere $\overline{\mathbb{Q}}$ by $\overline{\mathbb{F}}_p$ and $\mathbb{Z}$ by $\mathbb{F}_p$. $\square$

**Example 3.4.** Consider the differential equation

$$y' = \frac{1}{x^2 + 1}y \qquad (20)$$
**Remark 3.11.** When $k = p$, it is actually possible to determine the coefficients $\star$ in Eq. (19). Indeed, we observe that $(\partial_x + b(x))^p$ is a central element in $\mathbb{F}_p(x)\langle\partial_x\rangle$. This shows that the right-hand side of Eq. (19) must be central as well, implying eventually that all terms in $\partial_x^i$ with $0 \le i < p$ have to vanish, and that $b_p(x)$ belongs to $\mathbb{F}_p(x^p)$.

In conclusion, we have the relation

$$ (\partial_x + b(x))^p = \partial_x^p + b_p(x). $$

From this, we deduce that $b_p(x)$ is also the opposite of the remainder in the Euclidean division of $\partial_x^p$ by $\mathcal{L} = \partial_x + b(x)$. In particular, the $p$-curvature vanishes if and only if $\mathcal{L}$ divides $\partial_x^p$ in $\mathbb{F}_p(x)\langle\partial_x\rangle$.

Last, one can deduce from (20) the following remarkable closed formula (that does not extend to higher order equations).

**Theorem 3.12.** We have $b_p(x) = b^{(p-1)}(x) + b(x)^p$.

*Proof (after Jacobson [44]).* For a positive integer $k$, let $I_k$ be the set of all tuples $\underline{\alpha} = (\alpha_1, \dots, \alpha_k)$ of nonnegative integers such that $\sum_{i=1}^k i\alpha_i = k$. A calculation shows that $b_k(x)$ is explicitly given by

$$ b_k(x) = \sum_{\underline{\alpha} \in I_k} \lambda_{\underline{\alpha}} \cdot b(x)^{\alpha_1} \cdot b^{(1)}(x)^{\alpha_2} \cdots b^{(k-1)}(x)^{\alpha_k}, $$

where $\lambda_{\underline{\alpha}}$ is a coefficient in $\mathbb{Z}$ determined by the following rule

$$ \lambda_{\underline{\alpha}} = \sum_{i=1}^{k} (\alpha_{i-1} + 1) \cdot \lambda_{\tau_i(\underline{\alpha})} \quad (\text{for } \alpha \in I_k), $$

where $\tau_i$ denotes the function from $I_k$ to $I_{k-1}$ defined by

$$ \tau_i(\underline{\alpha}) = (\alpha_1, \dots, \alpha_{i-2}, \alpha_{i-1}-1, \alpha_i+1, \alpha_{i+1}, \dots, \alpha_{k-1}) $$

and where we agree that $\lambda_{\underline{\beta}} = 0$ if $\underline{\beta}$ has one negative coordinate. From this relation, one can check by induction on $k$ that $\lambda_{\underline{\alpha}}$ (with $\underline{\alpha} = (\alpha_1, \dots, \alpha_k) \in I_k$) is given by the closed formula:

$$ \lambda_{\underline{\alpha}} = \frac{k!}{(\alpha_1)! \cdots (\alpha_k)! \cdot (2!)^{\alpha_2} \cdots (3!)^{\alpha_3} \cdots (k!)^{\alpha_k}}. $$

In particular, when $k = p$, we find that the $\lambda_{\underline{\alpha}}$'s vanish modulo $p$ for all $\underline{\alpha} \in I_p$ (thanks to the numerator $p!$) except when $\underline{\alpha} = (p, 0, \dots, 0)$ or $\underline{\alpha} = (0, \dots, 0, 1)$ (because, in those cases, the numerator cancels with a factor $p!$ in the denominator). Besides, in both cases, one finds $\lambda_{\underline{\alpha}} = 1$. This concludes the proof. $\square$

**Remark 3.13.** Remarkably, the explicit formula of Theorem 3.12 provides a second proof of Proposition 3.3. Indeed, consider a rational function $b(x) \in \mathbb{F}_p(x)$ and write its partial fraction decomposition

$$ b(x) = P(x) + \sum_{i=1}^{m} \sum_{j=1}^{r_i} \frac{\beta_{i,j}}{(x - b_i)^j} $$
whose general solution in characteristic zero is $c \cdot \exp(\arctan(x))$ where $c$ is a constant. We are interested in determining whether or not this equation has a rational solution in characteristic $p > 0$. Modulo $p = 2$, the rational function $b(x) = 1/(x^2 + 1)$ writes $1/(x + 1)^2$; thus it has a pole of order 2 and hence the differential equation (20) has no nonzero rational solutions by Proposition 3.3. For $p \neq 2$, the partial fraction decomposition of $b(x)$ reads

$$b(x) = \frac{i}{2} \cdot \left( \frac{1}{x+i} - \frac{1}{x-i} \right)$$

where $i$ denotes a square root of $-1$ in $\overline{\mathbb{F}}_p$. We now need to distinguish between two cases depending on the congruence class of $p$ modulo 4. Indeed, when $p \equiv 1 \pmod 4$, we have $i \in \mathbb{F}_p$ and so the residues belong to $\mathbb{F}_p$ as well. In this case, the equation (20) has then a nonzero rational solution, namely

$$y(x) = \left( \frac{x+i}{x-i} \right)^{i/2},$$

where the exponent $i/2$ is a lift in $\mathbb{Z}$ of $i/2 \in \mathbb{F}_p$. On the contrary, when $p \equiv 3 \pmod 4$, we know that $-1$ is not a square in $\mathbb{F}_p$, showing that the residues are not in $\mathbb{F}_p$ either. Therefore, in this case, the equation (20) has no nonzero rational solution.

**Theorem 3.5.** If (15) has a nonzero algebraic solution, then, for almost all primes $p$, (16) has a nonzero rational solution.

*Proof.* Proposition 3.1 (and its proof) ensures that

$$a(x) = \sum_{i=1}^{m} \frac{e_i}{x - a_i} \qquad (21)$$

for some $a_i \in \overline{\mathbb{Q}}$ and some $e_i \in \mathbb{Q}$.

Let us first assume that the $a_i$'s belong to $\mathbb{Q}$. For any prime $p$, we let $\mathbb{Z}_{(p)}$ be the ring of rational numbers with denominator relatively prime to $p$. We denote by $\pi_p : \mathbb{Z}_{(p)} \to \mathbb{F}_p$ the “reduction modulo $p$” map. For almost all primes $p$, the $a_i$'s and the $e_i$'s belong to $\mathbb{Z}_{(p)}$. For any such $p$, we have:

$$a(x) \bmod p = \sum_{i=1}^{m} \frac{\pi_p(e_i)}{x - \pi_p(a_i)}$$

and the result follows from Proposition 3.3.

The proof in the general case is similar but requires basic notions from algebraic number theory. Let $K$ be a number field containing the $a_i$ and the $e_i$. Let $\mathcal{O}_K$ be the ring of integers of $K$. For any prime $\mathfrak{P}$ of $K$ (which is by definition a prime ideal of $\mathcal{O}_K$), we let $\mathcal{O}_{\mathfrak{P}}$ be the valuation ring of $K$ at $\mathfrak{P}$. We denote by $\kappa_{\mathfrak{P}}$ the corresponding residue field and by $\pi_{\mathfrak{P}} : \mathcal{O}_{\mathfrak{P}} \to \kappa_{\mathfrak{P}}$ the quotient map. The residue field $\kappa_{\mathfrak{P}}$ is a finite field of characteristic $p$ such that $\mathfrak{P} \cap \mathbb{Z} = (p)$. We say that $\mathfrak{P}$ is above $p$. For almost all primes $p$, for all primes $\mathfrak{P}$ of $K$ above $p$, the $a_i$'s and the $e_i$'s belong to $\mathcal{O}_{\mathfrak{P}}$. For such $p$ and $\mathfrak{P}$, we have:

$$a(x) \bmod p = a(x) \bmod \mathfrak{P} = \sum_{i=1}^{m} \frac{\pi_{\mathfrak{P}}(e_i)}{x - \pi_{\mathfrak{P}}(a_i)}.$$

Since $e_i$ is rational, $\pi_{\mathfrak{P}}(e_i)$ belongs to the prime subfield $\mathbb{F}_p$ of $\kappa_{\mathfrak{P}}$. The result follows from Proposition 3.3. $\square$
where $P(x)$ is a polynomial, the $b_i$'s are pairwise distinct elements of $\overline{\mathbb{F}}_p$ and $\beta_{i,j} \in \overline{\mathbb{F}}_p$ with $\beta_{i,r_i} \neq 0$. Each $b_i$ is a pole of $b(x)$ of multiplicity $r_i$ and residue $\beta_{i,1}$. Moreover, $b(x)$ has an extra pole at infinity when the degree of $P(x)$ is positive. A direct computation now gives:

$$b_p(x) = P^{(p-1)}(x) + P(x)^p - \sum_{i=1}^{m} \sum_{\substack{1 \le j \le r_i \\ j \equiv 1 \bmod p}} \frac{\beta_{i,j}}{(x - b_i)^{j+p-1}} + \sum_{i=1}^{m} \sum_{j=1}^{r_i} \frac{\beta_{i,j}^p}{(x - b_i)^{pj}}$$

and we see that the latter is zero if and only if $P(x)$ vanishes and, for all $i \in \{1, \dots, m\}$, we have $r_i = 1$ and $\beta_{i,1}^p = \beta_{i,1}$, i.e. $\beta_{i,1} \in \overline{\mathbb{F}}_p$. After Proposition 3.9, we then recover by different means the result of Proposition 3.3.

**Example 3.14.** Applying the above recipe with the differential operator

$$\mathcal{L}_p = \partial_x - \frac{1}{x^2 + 1}$$

of Example 3.4, we find that its $p$-curvature is explicitly given by

$$b_p(x) = - \frac{c_p}{(x^2 + 1)^p}$$

where $c_p = 1$ if $p = 2$, $c_p = 0$ for $p \equiv 1 \pmod 4$ and $c_p = 2$ for $p \equiv 3 \pmod 4$. In particular, we retrieve by different means the dichotomy that we had already observed in Example 3.4.

The situation can be more complex if we slightly change the coefficient $b(x)$. For instance, consider the first-order differential operator:

$$\mathcal{L}_p = \partial_x - \frac{1}{x^3 - x - 1}.$$

Its $p$-curvature is zero if and only if the polynomial $x^3 - x - 1$ splits in $\overline{\mathbb{F}}_p[x]$ and $p \neq 23$. By [64, §5.3], this happens only for the primes $p \in \{59, 101, 167, 173, 211, 223, 271, 307, 317, \dots\}$ that have the property that $p \neq 23$ and they can be written as $p = m^2 + mn + 6n^2$ with $m, n \in \mathbb{Z}$, or equivalently, if and only if the coefficient of $x^{p-1}$ in $\prod_{n=1}^{\infty} (1 - x^n)(1 - x^{23n})$ is equal to 2. We leave the proofs of these statements as nice exercises for the reader. (See also [69, Prop. 3.3].)

Putting together Theorem 3.5, Theorem 3.6, Proposition 3.9 and Remark 3.11, we obtain the following result.

**Theorem 3.15.** Let $\mathcal{L} = \partial_x + a(x)$ as in Eq. (13) and, for almost all prime numbers $p$, denote by $\mathcal{L}_p$ its reduction modulo $p$ as in Eq. (14). The following properties are equivalent:

(1) $\mathcal{L}$ has a nonzero algebraic solution;

(2) for almost all primes $p$, $\mathcal{L}_p$ has a nonzero rational solution;

(3) for almost all primes $p$, the $p$-curvature of $\mathcal{L}_p$ vanishes;

(4) for almost all primes $p$, the operator $\mathcal{L}_p$ divides $\partial_x^p$ in $\overline{\mathbb{F}}_p(x)\langle\partial_x\rangle$.

Grothendieck's $p$-curvature conjecture is a far reaching conjectural generalization of these equivalences for higher order equations.
### 3.1.3 From characteristic $p$ to characteristic $0$

It is now tempting to ask: if (16) has a nonzero rational solution for almost all primes $p$, does (15) have a nonzero algebraic solution? The (positive) answer is given by the following result.

**Theorem 3.6 (Honda [53]).** The converse of Theorem 3.5 holds true, i.e., if, for almost all primes $p$, (16) has a nonzero rational solution, then (15) has a nonzero algebraic solution.

*Proof.* Consider the partial fraction decomposition of $a(x)$:

$$a(x) = P(x) + \sum_{i=1}^{m} \sum_{j=1}^{r_i} \frac{\alpha_{i,j}}{(x - a_i)^j}$$

with $P(x) \in \overline{\mathbb{Q}}[x]$, $a_i \in \overline{\mathbb{Q}}$, $\alpha_{i,j} \in \overline{\mathbb{Q}}$ and $r_j \in \mathbb{Z}_{\ge 1}$. According to Proposition 3.1, we have to prove that $P(x)$ and the $\alpha_{i,j}$'s for $j \ge 2$ are 0 and that the $\alpha_{i,1}$'s belong to $\mathbb{Q}$.

Let $K$ be a number field containing the $a_i$, the $\alpha_{i,j}$'s and the coefficients of $P(x)$. We will use the notation and terminology (prime $\mathfrak{P}$ of $K$, valuation ring $\mathcal{O}_{\mathfrak{P}}$, quotient map $\pi_{\mathfrak{P}}$, etc.) introduced in the proof of Theorem 3.5. For almost all primes $p$, for all primes $\mathfrak{P}$ of $K$ above $p$, the $a_i$'s, the $\alpha_{i,j}$'s and the coefficients of $P(x)$ belong to $\mathcal{O}_{\mathfrak{P}}$. For such $p$ and $\mathfrak{P}$, we have:

$$a(x) \mod p = a(x) \mod \mathfrak{P} = P^{\pi_{\mathfrak{P}}}(x) + \sum_{i=1}^{m} \sum_{j=1}^{r_i} \frac{\pi_{\mathfrak{P}}(\alpha_{i,j})}{(x - \pi_{\mathfrak{P}}(a_i))^j},$$

where $P^{\pi_{\mathfrak{P}}}(x)$ denotes the polynomial obtained from $P(x)$ by applying $\pi_{\mathfrak{P}}$ coefficientwise.

Proposition 3.3 ensures that, for almost all primes $p$, $a(x) \mod p$ has at most simple poles, so, for almost all primes $p$, for all primes $\mathfrak{P}$ of $K$ above $p$, for all $j \in \{2, \dots, r_i\}$, we have $\pi_{\mathfrak{P}}(\alpha_{i,j}) = 0$, i.e., $\alpha_{i,j} \in \mathfrak{P}$. This implies that, for all $j \in \{2, \dots, r_i\}$, we have $\alpha_{i,j} = 0$. Similarly, Proposition 3.3 also ensures that, for almost all primes $p$, $a(x) \mod p$ vanishes at $\infty$, so, for almost all primes $p$, for all primes $\mathfrak{P}$ of $K$ above $p$, $P^{\pi_{\mathfrak{P}}}(x) = 0$. This implies that $P(x) = 0$. Last, Proposition 3.3 ensures that, for almost all primes $p$, for all primes $\mathfrak{P}$ above $p$, we have $\pi_{\mathfrak{P}}(\alpha_{i,1}) \in \mathbb{F}_p$. Using Kronecker's Theorem recalled below, we get that $\alpha_{i,1}$ belongs to $\mathbb{Q}$ and Proposition 3.1 yields the desired result: (15) has a nonzero algebraic solution. $\square$

The Kronecker Theorem mentioned above (which is usually seen as a consequence of Chebotarev's density Theorem) reads as follows

**Theorem 3.7 (Kronecker).** An irreducible element $P(x)$ of $\mathbb{Q}[x]$ such that, for almost all primes $p$, $P(x) \mod p$ has a zero in $\mathbb{F}_p$ is linear.

### 3.1.4 Rational solutions in characteristic $p$ and $p$-curvature

Consider a differential equation

$$y' + b(x)y = 0 \qquad (22)$$

with $b(x) \in \mathbb{F}_p(x)$. We will give an alternative criterion (an alternative to Proposition 3.3) for determining whether (22) has a nonzero rational solution based on the notion of $p$-curvature that we shall now introduce.
## 3.2 Grothendieck's conjecture

Let us now consider a linear differential operator of arbitrary order:

$$ \mathcal{L} = \partial_x^n + a_{n-1}(x) \cdot \partial_x^{n-1} + \cdots + a_1(x) \cdot \partial_x + a_0(x) \quad (21) $$

with $a_i(x) \in \mathbb{Q}(x)$. As in the order-1 case, one can consider the reduction $\mathcal{L}_p$ of $\mathcal{L}$ modulo $p$ for almost all primes $p$. This is a differential operator of order $n$ with coefficients in $\mathbb{F}_p(x)$. Grothendieck's conjecture relates the algebraicity of the solutions of $\mathcal{L}$ to the rationality of the solutions of $\mathcal{L}_p$ for almost all prime $p$.

First of all, we notice that the straightforward generalization of Theorem 3.15 cannot be true for higher order differential operators; indeed, we have seen in §2 many examples of differential equations that do not admit algebraic solutions and whose reductions modulo $p$ have nonzero rational solutions for almost all $p$; this is the case, for instance, of most of hyper-geometric functions and diagonals. The main new insight behind Grothendieck's conjecture is the brilliant idea to replace the existence of a unique nonzero solution by the existence of a full basis of solutions.

We remind that the set of solutions of $\mathcal{L}$ in $\overline{\mathbb{Q}}(x)$ is a $\overline{\mathbb{Q}}$-vector space of dimension at most $n$. When this dimension is maximal, that is, equal to $n$, we say that $\mathcal{L}$ has a full basis of algebraic solutions. Similarly, it is tempting to look at the set of solutions of $\mathcal{L}_p$ in $\mathbb{F}_p(x)$ as an $\mathbb{F}_p$-vector space. However, the example given by the differential equation $y^{(p)} = 0$ shows that this vector space may be infinite dimensional (any element of $\mathbb{F}_p(x)$ is a solution of $y^{(p)} = 0$). The point is that $\overline{\mathbb{Q}}$ is the relevant base field in characteristic 0 because it is the field of differential constants of $\overline{\mathbb{Q}}(x)$; in characteristic $p$, the field of differential constants of $\mathbb{F}_p(x)$ is not $\mathbb{F}_p$ but $\mathbb{F}_p(x^p)$ (thus, a differential constant may depend on $x$ in characteristic $p$!). Now, one can prove that the set of solutions of $\mathcal{L}_p$ in $\mathbb{F}_p(x)$ is an $\mathbb{F}_p(x^p)$-vector space of dimension at most $n$. When this dimension is maximal, that is, equal to $n$, we say that $\mathcal{L}_p$ has a full basis of rational solutions.

We are now ready to state Grothendieck's conjecture.

**Conjecture 3.16 (Grothendieck's conjecture).** For a differential operator $\mathcal{L} \in \mathbb{Q}(x)\langle\partial_x\rangle$ as in Eq. (21), the following properties are equivalent:

(1) $\mathcal{L}$ has a full basis of algebraic solutions;

(2) for almost all primes $p$, $\mathcal{L}_p$ has a full basis of rational solutions.

### 3.2.1 Rational solutions in characteristic $p$ and $p$-curvature

Consider the equation

$$ \mathcal{L} = \partial_x^n + b_{n-1}(x) \cdot \partial_x^{n-1} + \cdots + b_1(x) \cdot \partial_x + b_0(x) \quad (22) $$

with $b_i(x) \in \mathbb{F}_p(x)$. There is no straightforward generalization of Proposition 3.3 for determining whether (22) has a full basis of rational solutions but the criterion given by Proposition 3.9 via the $p$-curvature does extend to higher order equations. Let us briefly explain this.
Consider the $\mathbb{F}_p(x^p)$-linear map

$$ \Delta : \mathbb{F}_p(x) \to \mathbb{F}_p(x) \\ f \mapsto f' + b(x)f. $$

The additivity is clear, the homogeneity follows from the fact that the elements of $\mathbb{F}_p(x^p)$ are constants of (the differential field) $\mathbb{F}_p(x)$ in the sense that their derivative is 0 (more precisely, $\mathbb{F}_p(x^p) = \{f(x) \in \mathbb{F}_p(x) \mid f'(x) = 0\}$) implying that $(\alpha f)' = \alpha f'$ for all $\alpha \in \mathbb{F}_p(x^p)$ and $f \in \mathbb{F}_p(x)$.

**Definition 3.8.** The map

$$ \Delta^p : \mathbb{F}_p(x) \to \mathbb{F}_p(x) $$

is called the $p$-curvature of (22).

A remarkable and fundamental fact is that the $p$-curvature is not only $\mathbb{F}_p(x^p)$-linear but it is also $\mathbb{F}_p(x)$-linear. Indeed, a simple induction along with the Leibniz rule show that, for all $k \ge 0$, for all $\alpha, f \in \mathbb{F}_p(x)$, we have

$$ \Delta^k(\alpha f) = \sum_{i=0}^{k} \binom{k}{i} \alpha^{(i)} \Delta^{k-i}(f). $$

Taking $k = p$ and using the fact that $\binom{p}{i} \equiv 0 \mod p$ for all $1 < i < p$, we get

$$ \Delta^p(\alpha f) = \alpha^{(p)} + \alpha \Delta^p(f), $$

and therefore the $\mathbb{F}_p(x)$-homogeneity follows from the fact that $\alpha^{(p)} = 0$.

**Proposition 3.9.** The differential equation (22) has a nonzero rational solution if and only if $\Delta^p = 0$.

*Proof.* If (22) has a nonzero rational solution $f$, then $\Delta(f) = 0$ and, hence, $\Delta^p(f) = 0$. As $\Delta^p$ is $\mathbb{F}_p(x)$-linear, we get $\Delta^p = 0$. Conversely, if $\Delta^p = 0$, then $\Delta$ has a nonzero kernel and, hence, (22) has a nonzero rational solution. $\square$

**Remark 3.10.** An easy calculation shows that, if (22) has $p$-curvature 0, then an explicit nonzero rational solution is given by

$$ \sum_{k=0}^{p-1} (-1)^k \frac{x^k}{k!} \Delta^k(1). $$

We conclude this section by giving inductive and closed formulae for the $p$-curvature. As it is $\mathbb{F}_p(x)$-linear, the $p$-curvature is entirely determined by its value at 1:

$$ \forall f \in \mathbb{F}_p(x), \Delta^p(f) = \Delta^p(1)f. $$

For this reason, we often say that the $p$-curvature of (22) is $\Delta^p(1)$. It turns out that the $p$-curvature $\Delta^p(1)$ can be calculated inductively. Indeed, for all $k \ge 0$, we denote by $b_k(x) \in \mathbb{F}_p(x)$ the constant term of the differential operator $(\partial_x + b(x))^k$, so that

$$ (\partial_x + b(x))^k = \partial_x^k + \star\partial_x^{k-1} + \cdots + \star\partial_x + b_k(x), \quad (23) $$
Let $Y' + B(x)Y = 0$ be the differential system associated to (22), where

$$ B = \begin{pmatrix} 0 & -1 & 0 & \cdots & 0 & 0 \\ 0 & 0 & -1 & \cdots & 0 & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & 0 & \cdots & -1 & 0 \\ 0 & 0 & 0 & \cdots & 0 & -1 \\ b_0 & b_1 & b_2 & \cdots & b_{n-2} & b_{n-1} \end{pmatrix} \in M_n(\mathbb{F}_p(x)). \quad (23) $$

Mimicking what has been done in Section 3.1.4 in the order-1 case, we consider the $\mathbb{F}_p(x^p)$-linear map

$$ \Delta : \mathbb{F}_p(x)^n \to \mathbb{F}_p(x)^n \\ F \mapsto F' + B(x)F. $$

**Definition 3.17.** The map

$$ \Delta^p : \mathbb{F}_p(x)^n \to \mathbb{F}_p(x)^n $$

is called the $p$-curvature of (22).

As in the first-order case, one can easily prove that the $p$-curvature is not only $\mathbb{F}_p(x^p)$-linear, but also $\mathbb{F}_p(x)$-linear. Moreover, the inductive formula (20) for computing the $p$-curvature of equations of order 1 can be extended as follows: the matrix $B_p(x)$ of the $p$-curvature with respect to the canonical basis is given by the recurrence

$$ B_{k+1}(x) = B'_{k}(x) + B(x)B_{k}(x) \quad (24) $$

starting with $B_0(x) = B(x)$.

The following fundamental result is a generalization of Proposition 3.9 to higher order differential equations.

**Theorem 3.18 (Cartier's lemma).** Let $\mathcal{L} \in \mathbb{F}_p(x)\langle\partial_x\rangle$ be a differential operator as in Eq. (22). The following properties are equivalent:

(1) $\mathcal{L}$ has a full basis of rational solutions;

(2) the $p$-curvature of $\mathcal{L}$ (that is $\Delta^p$) vanishes;

(3) $\mathcal{L}$ divides $\partial_x^p$ in $\mathbb{F}_p(x)\langle\partial_x\rangle$.

*Proof.* Let us first note that the following properties, relative to the $\mathbb{F}_p(x^p)$-vector space $S := \ker(\Delta)$, are equivalent:

* the differential equation (22) has a full basis of rational solutions;

* the $\mathbb{F}_p(x^p)$-vector space $S$ has dimension $n$;

* the $\mathbb{F}_p(x)$-vector space $\mathbb{F}_p(x)^n$ is spanned by $S$.
where ⋆ are some unspecified elements of $\mathbb{F}_p(x)$. Equating the terms of degree 0 (with respect to $\partial_x$) in the equality $(\partial_x + b(x))^{k+1} = (\partial_x + b(x)) \cdot (\partial_x + b(x))^k$, we get the following inductive formula for computing the $b_k(x)$'s:

$$ \forall k \ge 0, \quad b_{k+1}(x) = b'_{k}(x) + b(x)b_{k}(x). \qquad (24) $$

This gives the expected inductive formula for the p-curvature of (22), since this is equal to

$$ \Delta^p(1) = b_p(x). $$

**Remark 3.11.** When $k = p$, it is actually possible to determine the coefficients ⋆ in equation (23). Indeed, we observe that $(\partial_x + b(x))^p$ is a central element in $\mathbb{F}_p(x)\langle\partial_x\rangle$. This shows that the right-hand side of equation (23) must be central as well, implying eventually that all terms in $\partial_x^i$ with $0 \le i < p$ have to vanish, and that $b_p(x)$ belongs to $\mathbb{F}_p(x^p)$.

In conclusion, we have the relation

$$ (\partial_x + b(x))^p = \partial_x^p + b_p(x). $$

From this, we deduce that $b_p(x)$ is also the opposite of the remainder in the right Euclidean division of $\partial_x^p$ by $\mathcal{L} = \partial_x + b(x)$. In particular, the p-curvature vanishes if and only if $\mathcal{L}$ divides $\partial_x^p$ in $\mathbb{F}_p(x)\langle\partial_x\rangle$.

Last, one can deduce from (24) the following remarkable closed formula (that does not extend to higher order equations).

**Theorem 3.12.** We have $b_p(x) = b^{(p-1)}(x) + b(x)^p$.

*Proof (after Jacobson [54]).* For a positive integer $k$, let $I_k$ be the set of all tuples $\underline{\alpha} = (\alpha_1, \dots, \alpha_k)$ of nonnegative integers such that $\sum_{i=1}^k i\alpha_i = k$. A calculation shows that $b_k(x)$ is explicitly given by

$$ b_k(x) = \sum_{\underline{\alpha} \in I_k} \lambda_{\underline{\alpha}} \cdot b(x)^{\alpha_1} \cdot b^{(1)}(x)^{\alpha_2} \cdots b^{(k-1)}(x)^{\alpha_k}, $$

where $\lambda_{\underline{\alpha}}$ is a coefficient in $\mathbb{Z}$ determined by the following rule

$$ \lambda_{\underline{\alpha}} = \sum_{i=1}^{k} (\alpha_{i-1} + 1) \cdot \lambda_{\tau_i(\underline{\alpha})} \quad (\text{for } \underline{\alpha} \in I_k), $$

where $\tau_i$ denotes the function from $I_k$ to $I_{k-1}$ defined by

$$ \tau_i(\underline{\alpha}) = (\alpha_1, \dots, \alpha_{i-2}, \alpha_{i-1}-1, \alpha_i+1, \alpha_{i+1}, \dots, \alpha_{k-1}) $$

and where we agree that $\lambda_{\underline{\beta}} = 0$ if $\underline{\beta}$ has one negative coordinate. From this relation, one can check by induction on $k$ that $\lambda_{\underline{\alpha}}$ (with $\underline{\alpha} = (\alpha_1, \dots, \alpha_k) \in I_k$) is given by the closed formula:

$$ \lambda_{\underline{\alpha}} = \frac{k!}{(\alpha_1)! \cdots (\alpha_k)! \cdot (2!)^{\alpha_2} \cdots (3!)^{\alpha_3} \cdots (k!)^{\alpha_k}}. $$

In particular, when $k = p$, we find that the $\lambda_{\underline{\alpha}}$'s vanish modulo $p$ for all $\underline{\alpha} \in I_p$ (thanks to the numerator $p!$) except when $\underline{\alpha} = (p, 0, \dots, 0)$ or $\underline{\alpha} = (0, \dots, 0, 1)$ (because, in those cases, the numerator cancels with a factor $p!$ in the denominator). Besides, in both cases, one finds $\lambda_{\underline{\alpha}} = 1$. This concludes the proof. $\square$
The equivalence between the first two properties is immediate. The equivalence between the last two properties follows from the wronskian lemma.

If $\mathcal{L}$ has a full basis of rational solutions, then the $\mathbb{F}_p(x)$-vector space $\mathbb{F}_p(x)^n$ is spanned by $S$. Since $\Delta^p$ is $\mathbb{F}_p(x)$-linear and vanishes on $S$, we have $\Delta^p = 0$. Conversely, assume that $\Delta^p = 0$. We will prove that the $\mathbb{F}_p(x)$-vector space $\mathbb{F}_p(x)^n$ is spanned by $S$. Consider the map

$$ P : \mathbb{F}_p(x)^n \to \mathbb{F}_p(x)^n \\ F \mapsto \sum_{k=0}^{p-1} (-1)^k \frac{x^k}{k!} \Delta^k(F). $$

A simple calculation shows that

$$ \Delta(P(F)) = -(-x)^{p-1} \Delta^p(F) = 0 $$

and, hence, $P$ has values in $S$. But, another simple calculation shows that, for all $F \in \mathbb{F}_p(x)^n$, we have

$$ F = \sum_{k=0}^{p-1} \frac{x^k}{k!} P(\Delta^k(F)). $$

This shows that the $\mathbb{F}_p(x)$-vector space $\mathbb{F}_p(x)^n$ is spanned by $S$. We have then proved the equivalence between the two first assertions.

Now, we notice that, given rational functions $f_0(x), \dots, f_{r-1}(x), g_0(x), \dots, g_{r-1}(x)$, the equality

$$ \Delta(f_0(x), \dots, f_{r-1}(x)) = (g_0(x), \dots, g_{r-1}(x)) $$

is equivalent to the following congruence in $\mathbb{F}_p(x)\langle\partial_x\rangle$:

$$ (f_0(x) + \dots + f_{r-1}(x)\partial_x^r) \cdot \partial_x \equiv g_0(x) + \dots + g_{r-1}(x)\partial_x^r \pmod{\mathcal{L}}. $$

It follows from this observation that, writing $E_i = (0, \dots, 0, 1, 0, \dots, 0)$ with the coordinate 1 in $i$-th position, the coordinates of $\Delta^p(E_i)$ are exactly the coefficients of the remainder in the division of $\partial_x^{p+i}$ by $\mathcal{L}$. Hence $\Delta^p(E_i)$ vanishes if and only if $\mathcal{L}$ divides $\partial_x^{p+i}$. The equivalence between the second and the third condition of the theorem follows immediately. $\square$

**Remark 3.19.** The three assertions of Theorem 3.18 are also equivalent to

(4) $\mathcal{L}$ admits $n$ power series solutions in $\mathbb{F}_p([x])$, linearly independent over $\mathbb{F}_p((x^p))$;

(5) $\mathcal{L}$ admits $n$ polynomial solutions in $\mathbb{F}_p[x]$, linearly independent over $\mathbb{F}_p((x^p))$.

The implication (5) $\implies$ (4) is proved in [43, Lemma 1], while (5) $\implies$ (1) is trivial. Moreover, under the equivalent assertions (1)–(5), Proposition 1 in [21] shows that there exists a full basis of polynomial solutions in $\mathbb{F}_p[x]$, each of them having degree less than $pd$, where $d$ is the maximal degree of the numerators/denominators of the coefficients $b_i(x)$ of $\mathcal{L}$ in (22).

**Remark 3.20.** Assume that $\mathcal{L}$ has $p$-curvature zero. An easy calculation shows that

$$ U_0(x) = \sum_{k=0}^{p-1} (-1)^k \frac{x^k}{k!} B_k(x) \in M_n(\mathbb{F}_p(x)) $$
**Remark 3.13.** Remarkably, the explicit formula of Theorem 3.12 provides a second proof of Proposition 3.3. Indeed, consider a rational function $b(x) \in \mathbb{F}_p(x)$ and write its partial fraction decomposition

$$b(x) = P(x) + \sum_{i=1}^{m} \sum_{j=1}^{r_i} \frac{\beta_{i,j}}{(x - b_i)^j}$$

where $P(x)$ is a polynomial, the $b_i$'s are pairwise distinct elements of $\overline{\mathbb{F}}_p$ and $\beta_{i,j} \in \overline{\mathbb{F}}_p$ with $\beta_{i,r_i} \neq 0$. Each $b_i$ is a pole of $b(x)$ of multiplicity $r_i$ and residue $\beta_{i,1}$. Moreover, $b(x)$ has an extra pole at infinity when the degree of $P(x)$ is positive. A direct computation now gives:

$$b_p(x) = P^{(p-1)}(x) + P(x)^p - \sum_{i=1}^{m} \sum_{\substack{1 \le j \le r_i \\ j \equiv 1 \bmod p}} \frac{\beta_{i,j}}{(x - b_i)^{j+p-1}} + \sum_{i=1}^{m} \sum_{j=1}^{r_i} \frac{\beta_{i,j}^p}{(x - b_i)^{pj}}$$

and we see that the latter is zero if and only if $P(x)$ vanishes and, for all $i \in \{1, \dots, m\}$, we have $r_i = 1$ and $\beta_{i,1}^p = \beta_{i,1}$, i.e. $\beta_{i,1} \in \overline{\mathbb{F}}_p$. After Proposition 3.9, we then recover by different means the result of Proposition 3.3.

**Example 3.14.** Applying the above recipe with the differential operator

$$\mathcal{L}_p = \partial_x - \frac{1}{x^2 + 1}$$

of Example 3.4, we find that its $p$-curvature is explicitly given by

$$b_p(x) = - \frac{c_p}{(x^2 + 1)^p}$$

where $c_p = 1$ if $p = 2$, $c_p = 0$ for $p \equiv 1 \pmod 4$ and $c_p = 2$ for $p \equiv 3 \pmod 4$. In particular, we retrieve by different means the dichotomy that we had already observed in Example 3.4.

The situation can be more complex if we slightly change the coefficient $b(x)$. For instance, consider the first-order differential operator:

$$\mathcal{L}_p = \partial_x - \frac{1}{x^3 - x - 1}.$$

Its $p$-curvature is zero if and only if the polynomial $x^3 - x - 1$ splits in $\overline{\mathbb{F}}_p[x]$ and $p \neq 23$. By [78, §5.3], this happens only for the primes $p \in \{59, 101, 167, 173, 211, 223, 271, 307, 317, \dots\}$ that have the property that $p \neq 23$ and they can be written as $p = m^2 + mn + 6n^2$ with $m, n \in \mathbb{Z}$, or equivalently, if and only if the coefficient of $x^{p-1}$ in $\prod_{n=1}^{\infty} (1 - x^n)(1 - x^{23n})$ is equal to 2. (See also [84, Prop. 3.3].)

**Remark 3.15.** There is a link between the $p$-curvature of first-order linear differential operators and a fairly famous algorithm for factoring polynomials in $\overline{\mathbb{F}}_p[x]$, designed by Niederreiter in [68]. This connection seems to have been unnoticed until now. To factor a separable polynomial $f = \prod_i g_i$ of $\overline{\mathbb{F}}_p[x]$, with irreducible $g_i$, Niederreiter considers the space of rational functions $y = h/f$ solutions of the equation $y^{(p-1)} + y^p = 0$, and shows that as a vector space over $\overline{\mathbb{F}}_p$ it is generated by the logarithmic derivatives $g'_i/g_i$. As a result, factoring boils down to a linear algebra problem over $\overline{\mathbb{F}}_p$. This algorithm created a lot of excitement as a promising alternative to the much more classical one due to Berlekamp [7].
is a solution of $Y' + B(x)Y = 0$. If, moreover, $B(x)$ has no pole at 0, then $U_0(x)$ has no pole at 0 as well and we have $U_0(0) = I_n$, so $U_0(x)$ is a fundamental matrix of rational solutions of $Y' + B(x)Y = 0$. If $B(x)$ has a pole at 0, then $U_0(x)$ is not necessarily invertible. Note that, more generally, if $a \in \mathbb{F}_p$ is not a pole of $B(x)$, then

$$U_a(x) = \sum_{k=0}^{p-1} (-1)^k \frac{(x-a)^k}{k!} B_k(x-a)$$

is a fundamental matrix of rational solutions of $Y' + B(x)Y = 0$.

Putting together all what precedes, we obtain a simple algorithm to determine whether (22) has a full basis of rational solutions: compute inductively $B_p(x)$ and, then, check whether $B_p(x)$ vanishes. Note however that no extension of the simple formula of Theorem 3.12 is known for higher order differential equations. Roughly speaking, this is due to the fact that, contrarily to $\mathbb{F}_p(x)$, the ring of $n \times n$ matrices over $\mathbb{F}_p(x)$ is noncommutative as soon as $n \ge 2$. Computing the $p$-curvature is then much more complicated in this case but rather efficient algorithms for this task are nevertheless available; we will present them in Subsection 3.3.

Using Theorem 3.18 (Cartier's lemma), we get the following reformulation of Grothendieck's conjecture.

**Conjecture 3.21** (Grothendieck's conjecture in terms of $p$-curvature). For a differential operator $\mathcal{L}$ as in Eq. (21), the following properties are equivalent:

(1) $\mathcal{L}$ has a full basis of algebraic solutions;

(2) for almost all primes $p$, the $p$-curvature of $\mathcal{L}_p$ vanishes;

(3) for almost all primes $p$, $\mathcal{L}_p$ divides $\partial_x^p$ in the ring of differential operators $\mathbb{F}_p(x)\langle\partial_x\rangle$.

### 3.2.2 Progresses toward Grothendieck's conjecture

#### A known case: the generalized hypergeometric equations

It is in general very difficult to determine whether a given differential equation has a full basis of algebraic solutions. In their celebrated work [8], Beukers and Heckman managed to do this for an important class of differential equations, omnipresent in the mathematical and physical literature, namely the so-called generalized hypergeometric equations. In fact, Beukers and Heckman extended the Landau-Errera criterion mentioned in §2.1.3. Let $\mathbf{a} = \{a_1, \dots, a_{s+1}\}$ and $\mathbf{b} = \{b_1, \dots, b_s, b_{s+1} = 1\}$ be two sets of rational parameters, assumed disjoint modulo $\mathbb{Z}$. This assumption is equivalent to the irreducibility in $\mathbb{Q}(x)\langle\partial\rangle$ of the “generalized hypergeometric operator” defined by

$$\mathcal{H}(\mathbf{a}, \mathbf{b}) := (x\partial_x + b_1 - 1) \cdots (x\partial_x + b_s - 1)x\partial_x - x(x\partial_x + a_1) \cdots (x\partial_x + a_{s+1}).$$

It is easy to check that $\mathcal{H}(\mathbf{a}, \mathbf{b})$ admits in its solution space the generalized hypergeometric function $s+1 F_s([a_1, \dots, a_{s+1}], [b_1, \dots, b_s]; x)$ defined in (11). The Beukers-Heckman result then reads as follows.

**Theorem 3.22** (“interlacing criterion”, Beukers-Heckman, [8]). Given two sets of rational numbers $\mathbf{a} = \{a_1, \dots, a_{s+1}\}$ and $\mathbf{b} = \{b_1, \dots, b_s, b_{s+1} = 1\}$, assumed to be disjoint modulo $\mathbb{Z}$, let $D$ be the common denominator of their elements. Then, the following assertions are equivalent:
Putting together Theorem 3.5, Theorem 3.6, Proposition 3.9 and Remark 3.11, we obtain the following result.

**Theorem 3.16.** Let $\mathcal{L} = \partial_x + a(x)$ as in equation (15) and, for almost all prime numbers $p$, denote by $\mathcal{L}_p$ its reduction modulo $p$ as in equation (16). The following properties are equivalent:

(1) $\mathcal{L}$ has a nonzero algebraic solution;

(2) for almost all primes $p$, $\mathcal{L}_p$ has a nonzero rational solution;

(3) for almost all primes $p$, the $p$-curvature of $\mathcal{L}_p$ vanishes;

(4) for almost all primes $p$, the operator $\mathcal{L}_p$ divides $\partial_x^p$ in $\mathbb{F}_p(x)\langle\partial_x\rangle$.

Grothendieck's $p$-curvature conjecture is a far reaching conjectural generalization of these equivalences for higher order equations.

## 3.2 The general case

Let us now consider a linear differential operator of arbitrary order:

$$ \mathcal{L} = \partial_x^n + a_{n-1}(x) \partial_x^{n-1} + \dots + a_1(x) \partial_x + a_0(x) \quad (25) $$

with $a_i(x) \in \mathbb{Q}(x)$. As in the order-1 case, one can consider the reduction $\mathcal{L}_p$ of $\mathcal{L}$ modulo $p$ for almost all primes $p$. This is a differential operator of order $n$ with coefficients in $\mathbb{F}_p(x)$. Grothendieck's conjecture relates the algebraicity of the solutions of $\mathcal{L}$ to the rationality of the solutions of $\mathcal{L}_p$ for almost all primes $p$.

First of all, we notice that the straightforward generalization of Theorem 3.16 cannot be true for higher order differential operators; indeed, we have seen in §2 many examples of differential equations that do not admit algebraic solutions and whose reductions modulo $p$ have nonzero rational solutions for almost all $p$; this is the case, for instance, of most of hyper-geometric functions and diagonals. The main new insight behind Grothendieck's conjecture is the brilliant idea to replace the existence of a unique nonzero solution by the existence of a full basis of solutions.

We recall that the set of solutions of $\mathcal{L}$ in $\overline{\mathbb{Q}}(x)$ is a $\overline{\mathbb{Q}}$-vector space of dimension at most $n$. When this dimension is maximal, that is, equal to $n$, we say that $\mathcal{L}$ has a full basis of algebraic solutions. Similarly, it is tempting to look at the set of solutions of $\mathcal{L}_p$ in $\mathbb{F}_p(x)$ as an $\mathbb{F}_p$-vector space. However, the example given by the differential equation $y^{(p)} = 0$ shows that this vector space may be infinite dimensional (any element of $\mathbb{F}_p(x)$ is a solution of $y^{(p)} = 0$). The point is that $\overline{\mathbb{Q}}$ is the relevant base field in characteristic 0 because it is the field of differential constants of $\overline{\mathbb{Q}}(x)$. In characteristic $p$, the field of differential constants of $\mathbb{F}_p(x)$ is not $\mathbb{F}_p$ but $\mathbb{F}_p(x^p)$; thus, a differential constant may depend on $x$ in characteristic $p$ (!) Now, one can prove that the set of solutions of $\mathcal{L}_p$ in $\mathbb{F}_p(x)$ is an $\mathbb{F}_p(x^p)$-vector space of dimension at most $n$. When this dimension is maximal, that is, equal to $n$, we say that $\mathcal{L}_p$ has a full basis of rational solutions.

We are now ready to state Grothendieck's conjecture.

**Conjecture 3.17 (Grothendieck's conjecture).** For a differential operator $\mathcal{L} \in \mathbb{Q}(x)\langle\partial_x\rangle$ as in equation (25), the following properties are equivalent:

(1) $\mathcal{L}$ has a full basis of algebraic solutions;
1. the hypergeometric function $s+1 F_s([a_1, \dots, a_{s+1}], [b_1, \dots, b_s]; x)$ is algebraic;

2. the operator $\mathcal{H}(a, b)$ admits a full basis of algebraic solutions;

3. for all $1 \le l < D$ with $\gcd(l, D) = 1$ the sets $\{e^{2\pi i l a_j}, j \le s+1\}$ and $\{e^{2\pi i l b_j}, j \le s+1\}$ interlace on the unit circle.

**Example 3.23.** The Beukers-Heckman criterion immediately implies that the operator $\mathcal{H}(a, b)$ admits a full basis of algebraic solutions for the choice

$$a = \left\{ \frac{1}{30}, \frac{7}{30}, \frac{11}{30}, \frac{13}{30}, \frac{17}{30}, \frac{19}{30}, \frac{23}{30}, \frac{29}{30} \right\}, \quad b = \left\{ \frac{1}{5}, \frac{1}{3}, \frac{2}{5}, \frac{1}{2}, \frac{3}{5}, \frac{2}{3}, \frac{4}{5}, 1 \right\}.$$

This proves in particular a beautiful observation due to Fernando Rodriguez-Villegas, namely that the generating function $\sum_{n \ge 0} u_n x^n$ of the sequence

$$u_n := \frac{(30n)!n!}{(15n)!(10n)!(6n)!}$$

(used by Chebyshev in his work on estimates for the prime counting function) is algebraic.

Note that without the irreducibility assumption on $\mathcal{H}(a, b)$, the situation is much more subtle. For instance, ${}_2F_1([1/2, 1/3], [3/2]; x)$ is transcendental, while ${}_2F_1([3/2, 1/3], [1/2]; x)$ is algebraic. In a work (in progress) by Fürnsinn and Yurkevich, a generalization of Theorem 3.22 is given, which allows to decide algebraicity/transcendence of arbitrary generalized hypergeometric functions (with potentially irrational parameters).

In addition to Theorem 3.22, Beukers and Heckman also drew up in [8] the list of generalized hypergeometric equations having a full basis of algebraic solutions, thus extending Schwarz's classification of algebraic ${}_2F_1$'s [62].

On the other hand, a calculation due to Katz in [46, §5.5] (also in [45, §6] for the specific case of ${}_2F_1$'s) shows that this list coincides with the list of generalized hypergeometric equations whose reductions modulo $p$ have a full basis of rational solutions for almost all primes $p$, in accordance with Grothendieck's conjecture.

## State of the art on Grothendieck's conjecture

Besides for order-1 equations and for generalized hypergeometric equations, Grothendieck's conjecture has been proved in several particular cases.

On the one hand, for Picard-Fuchs differential equations (satisfied by periods of a family of smooth algebraic varieties), and more generally for certain direct factors, Grothendieck's conjecture was established by Katz [45]. As an application, Katz gave in [46, Theorem 5.5.3] a new proof of the aforementioned results of Beukers and Heckman [8] about the generalized hypergeometric equations. Katz [45, §1], and later André [4, §III], related the $p$-curvatures to the reduction modulo $p$ of the so-called Kodaira-Spencer map. (See also Foucault [40] and Foucault and Toffin [41] for explicit computations for families of curves of genus 2 and 3.) As explained in [4, p. 108], this approach has a potential of delivering effective versions of Grothendieck's conjecture, similar to effective versions of Chebotarev's density theorem [52, 63]: the hope is to obtain, for instance for any Picard-Fuchs operator $\mathcal{L}$, an integer $N(\mathcal{L})$
(2) for almost all primes $p$, $\mathcal{L}_p$ has a full basis of rational solutions.

Consider the linear differential operator

$$ \mathcal{L} = \partial_x^n + b_{n-1}(x) \cdot \partial_x^{n-1} + \cdots + b_1(x) \cdot \partial_x + b_0(x) \quad (26) $$

with $b_i(x) \in \mathbb{F}_p(x)$. There is no straightforward generalization of Proposition 3.3 for determining whether (26) has a full basis of rational solutions but the criterion given by Proposition 3.9 via the $p$-curvature does extend to higher order equations. Let us briefly explain this.

Let $Y' + B(x)Y = 0$ be the differential system associated to (26), where

$$ B = \begin{pmatrix} 0 & -1 & 0 & \cdots & 0 & 0 \\ 0 & 0 & -1 & \cdots & 0 & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & 0 & \cdots & -1 & 0 \\ 0 & 0 & 0 & \cdots & 0 & -1 \\ b_0 & b_1 & b_2 & \cdots & b_{n-2} & b_{n-1} \end{pmatrix} \in M_n(\mathbb{F}_p(x)). \quad (27) $$

Mimicking what has been done in Section 3.1.4 in the order-1 case, we consider the $\mathbb{F}_p(x^p)$-linear map

$$ \Delta : \mathbb{F}_p(x)^n \to \mathbb{F}_p(x)^n \\ F \mapsto F' + B(x)F. $$

**Definition 3.18.** The map

$$ \Delta^p : \mathbb{F}_p(x)^n \to \mathbb{F}_p(x)^n $$

is called the $p$-curvature of (26).

As in the first-order case, one can easily prove that the $p$-curvature is not only $\mathbb{F}_p(x^p)$-linear, but also $\mathbb{F}_p(x)$-linear. Moreover, the inductive formula (24) for computing the $p$-curvature of equations of order 1 can be extended as follows: the matrix $B_p(x)$ of the $p$-curvature with respect to the canonical basis is given by the recurrence

$$ B_{k+1}(x) = B'_{k}(x) + B(x)B_{k}(x) \quad (28) $$

starting with $B_0(x) = B(x)$.

The following fundamental result is a generalization of Proposition 3.9 to higher order differential equations. We recall the fact, already mentioned at the very beginning of Section 3.2, that the set of solutions of a given $\mathcal{L} \in \mathbb{F}_p(x)\langle \partial_x \rangle$ in $\mathbb{F}_p(x)$ of order $n$ is an $\mathbb{F}_p(x^p)$-vector space of dimension at most $n$ and that, when this dimension is maximal, that is, equal to $n$, we say that $\mathcal{L}$ has a full basis of rational solutions.

**Theorem 3.19 (Cartier's lemma).** Let $\mathcal{L} \in \mathbb{F}_p(x)\langle \partial_x \rangle$ be a differential operator as in equation (26). The following properties are equivalent:

(1) $\mathcal{L}$ has a full basis of rational solutions;

(2) the $p$-curvature of $\mathcal{L}$ (that is $\Delta^p$) vanishes;

(3) $\mathcal{L}$ divides $\partial_x^p$ in $\mathbb{F}_p(x)\langle \partial_x \rangle$.
such that the fact that $\mathcal{L}$ has a full basis of algebraic solutions can be read off the $p$-curvatures of $\mathcal{L}$ for the primes $p < N(\mathcal{L})$.

On the other hand, an arithmetic approach to Grothendieck's conjecture was introduced by the Chudnovsky brothers [30] who proved Grothendieck's conjecture for any rank one linear homogeneous differential equation over an algebraic curve [30, Theorem 8.1] (the case of first order equations over $\mathbb{P}^1$ had been proved by Honda in [43, §1]). They also proved Grothendieck's conjecture for the class of Lamé equations [30, Theorem 7.2], of the form

$$p(x)y''(x) + \frac{1}{2}p'(x)y'(x) - (n(n+1)x + B) \cdot y(x) = 0$$

where $n \in \mathbb{N}$, $B \in \mathbb{Q}$ and $p(x) \in \mathbb{Q}[x]$ has degree 3. The arithmetic approach was extended by André to the case when the differential Galois group has a solvable neutral component [4] (see also [2], [3, Chap. VIII], [10, Thm. 2.9] and [26, Thm. 3.5]).

Using the language of schemes and sheaves, Grothendieck's conjecture can be formulated more generally for differential equations over any algebraic smooth curve defined over a number field. In [4, Remark 7.1.4], André noticed that, using Belyi maps, one can reduce the general case to that of the curve $X = \mathbb{P}^1 \setminus \{0, 1, \infty\}$. In our setting, this means that one can safely assume that the differential operator $\mathcal{L}$ has only singularities at 0, 1 and $\infty$. Under this additional assumption, Tang [68] proves that if all<fnref n="3" /> the $p$-curvatures of $\mathcal{L}$ vanish, then $\mathcal{L}$ has a full basis of rational solutions. Although this latter result differs from Grothendieck's in the hypotheses (which are stronger) and the conclusion (which is also stronger), it is closely related.

We also point out the work of Bost in [10] giving an algebraicity criterion for leaves of algebraic foliations defined over number fields. For additional details, we refer to [26]. We mention the work of van der Put in [70] concerned with inhomogeneous equations of order 1. Other special cases of the conjecture have been proven recently, see [37, 65, 58]. Last but not least, an analogue of Grothendieck's conjecture for $q$-difference equations was conjectured by Bézivin [9, §5] and proved by Di Vizio in [31].

### 3.2.3 A formal parallel with Kronecker's theorem

It is instructive to observe that Grothendieck's conjecture appears to be, in some sense, a differential version of Kronecker's theorem we have already encountered earlier (see Theorem 3.7). Indeed, Kronecker's theorem can be reformulated as follows.

**Theorem 3.24.** For a separable polynomial $L \in \mathbb{Q}[x]$, the following conditions are equivalent:

(1) all the roots of $L$ are in $\mathbb{Q}$;

(2) for almost all primes $p$, all the roots of $L \bmod p$ are in $\mathbb{F}_p$;

(3) for almost all primes $p$, we have $X^p \equiv X \pmod{L, p}$.

It is striking that the three conditions of Theorem 3.24 are formal analogues of the conditions of Conjecture 3.16, at least if we admit that algebraic solutions in the differential case correspond to rational solutions in the algebraic case. Besides, the fact that the condition $X^p \equiv X \pmod{L, p}$ translates to $\partial_x^p \equiv 0 \pmod{\mathcal{L}, p}$, i.e. that the right-hand side shifts from

<footnote n="3">³When $\mathcal{L}$ does not reduce properly at a prime $p$, the $p$-curvature of $\mathcal{L}_p$ is a priori not defined; however Tang manages to give an alternative definition of the vanishing of the $p$-curvature, see [68, Definition 2.1.7].</footnote>
Proof. Let us first note that the following properties, relative to the $\mathbb{F}_p(x^p)$-vector space $S := \ker(\Delta)$, are equivalent:

i) the differential equation (26) has a full basis of rational solutions;

ii) the $\mathbb{F}_p(x^p)$-vector space $S$ has dimension $n$;

iii) the $\mathbb{F}_p(x)$-vector space $\mathbb{F}_p(x)^n$ is spanned by $S$.

The equivalence between i) and ii) follows immediately from the easily verifiable fact that the map

$$f(x) \mapsto (f(x), f'(x), \dots, f^{(n-1)}(x))$$

induces an $\mathbb{F}_p(x^p)$-linear isomorphism from the $\mathbb{F}_p(x^p)$-vector space of solutions of $\mathcal{L}$ in $\mathbb{F}_p(x)$ to the $\mathbb{F}_p(x^p)$-vector space $S$. The equivalence between ii) and iii) follows from the “Wronskian lemma” [86, Lemma 1.12]. Indeed, the wronskian lemma ensures that any family of elements of $S$ is linearly dependent over $\mathbb{F}_p(x^p)$ if and only if it is linearly dependent over $\mathbb{F}_p(x)$. Therefore, the dimension of the $\mathbb{F}_p(x^p)$-vector space $S$ and the dimension of the $\mathbb{F}_p(x)$-vector space spanned by $S$ are equal. Considering the case where one or other of these dimensions is $n$, we obtain the equivalence between ii) and iii).

We are now ready to prove the theorem.

Let us first prove (1) $\Rightarrow$ (2). If $\mathcal{L}$ has a full basis of rational solutions, then the implication i) $\Rightarrow$ iii) ensures that the $\mathbb{F}_p(x)$-vector space $\mathbb{F}_p(x)^n$ is spanned by $S$. Since $\Delta^p$ is $\mathbb{F}_p(x)$-linear and vanishes on $S$, we have $\Delta^p = 0$.

Let us now prove (2) $\Rightarrow$ (1). We assume that $\Delta^p = 0$. We claim that the $\mathbb{F}_p(x)$-vector space $\mathbb{F}_p(x)^n$ is spanned by $S$. Consider the map

$$P : \mathbb{F}_p(x)^n \to \mathbb{F}_p(x)^n \\ F \mapsto \sum_{k=0}^{p-1} (-1)^k \frac{x^k}{k!} \Delta^k(F).$$

A simple calculation shows that

$$\Delta(P(F)) = -(-x)^{p-1} \Delta^p(F) = 0$$

and, hence, $P$ has values in $S$. But, another simple calculation shows that, for all $F \in \mathbb{F}_p(x)^n$, we have

$$F = \sum_{k=0}^{p-1} \frac{x^k}{k!} P(\Delta^k(F)).$$

This shows that the $\mathbb{F}_p(x)$-vector space $\mathbb{F}_p(x)^n$ is spanned by $S$ as claimed. Now, using the implication iii) $\Rightarrow$ i), we get that $\mathcal{L}$ has a full basis of rational solutions.

It remains to prove that (2) $\Leftarrow$ (3). In order to do so, we first notice that, given rational functions $f_0(x), \dots, f_{n-1}(x), g_0(x), \dots, g_{n-1}(x)$, the equality

$$\Delta(f_0(x), \dots, f_{n-1}(x)) = (g_0(x), \dots, g_{n-1}(x))$$

is equivalent to the following congruence in $\mathbb{F}_p(x) \langle \partial_x \rangle$:

$$(f_0(x) + \dots + f_{n-1}(x) \partial_x^{n-1}) \cdot \partial_x \equiv g_0(x) + \dots + g_{n-1}(x) \partial_x^{n-1} \pmod{\mathcal{L}}.$$