# Algebraic solutions of linear differential equations:
an arithmetic approach

Alin Bostan111Inria, Université Paris-Saclay, 1 rue Honoré d’Estienne d’Orves,
91120 Palaiseau, France. Xavier Caruso222CNRS; Université de Bordeaux, IMB;
Inria Bordeaux Sud-Ouest, LFANT, 351 cours de la Libération, 33405 Talence,
France. Julien Roques333Université de Lyon, Université Claude Bernard Lyon 1,
CNRS UMR 5208, Institut Camille Jordan, 43 Bd du 11 Novembre 1918, 69622
Villeurbanne, France.

###### Abstract

Given a linear differential equation with coefficients in $\mathbb{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

  1. 1 Context, motivation and basic examples
  2. 2 Several natural differential equations have algebraic solutions
    1. 2.1 Examples from Special functions: Hypergeometic functions
    2. 2.2 Examples from Algebra: Diagonals
    3. 2.3 Examples from Combinatorics: Walks in the Quarter Plane
    4. 2.4 Examples from Number Theory
  3. 3 Grothendieck’s conjecture and the $p$-curvature
    1. 3.1 The case of equations of order $1$
    2. 3.2 Grothendieck’s conjecture
    3. 3.3 Computation of the $p$-curvature
    4. 3.4 Algebraicity and integrality

##  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)+\cdots+a_{1}(x)y^{\prime}(x)+a_{0}(x)y(x)=0,$
(1)

where the $a_{i}$’s are known rational functions in $\mathbb{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 $\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[N]{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^{\prime}(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^{\prime}(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^{\prime}(x)$ lives in
the $\mathbb{Q}(x)$-vector space generated by $1,y(x),\ldots,y(x)^{n-1}$. The
same similarly holds for all derivatives
$y(x),y^{\prime}(x),y^{\prime\prime}(x),\ldots,y^{(n)}(x)$, and hence these
elements must satisfy a nontrivial linear relation over $\mathbb{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\geq
0}C_{k}x^{k}$ satisfies the algebraic equation $P(x,y(x))=0$ where
$P(x,y)=xy^{2}-y+1$. Then,

$y^{\prime}(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^{\prime}(x)+(2x-1)y(x)+1=0$.

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\geq 0}x^{k}/k!$, solution of $y^{\prime}=y$, is
transcendental. Here is a purely algebraic proof. Let us assume by
contradiction that it satisfies a polynomial equation, of minimal degree
$n\geq 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^{\prime}(x)=\exp(x)$ we get a new
degree-$n$ equation
$ne^{nx}+\sum_{k=0}^{n-1}(r_{k}^{\prime}(x)+kr_{k}(x))e^{kx}=0$ which by
minimality is the $n$-th multiple of the former. In other words,
$r_{k}^{\prime}(x)+kr_{k}(x)=nr_{k}(x)$ for all $k<n$. In particular,
$r_{0}^{\prime}(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^{\prime}B-AB^{\prime}=nAB$, then $B$ divides $AB^{\prime}$, hence $B$
divides $B^{\prime}$, thus $B^{\prime}\equiv 0$; similarly, $A^{\prime}\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\geq 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\geq 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\geq 0}$ obviously all prime numbers
appear as divisors, 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 $\mathscr{L}(y)=0$, where $\mathscr{L}$
is the linear differential operator

$\mathscr{L}=a_{r}(x){\cdot}\partial_{x}^{r}+a_{r-1}(x){\cdot}\partial_{x}^{r-1}+\cdots+a_{1}(x){\cdot}\partial_{x}+a_{0}(x).$
(2)

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^{\prime}(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(\mathscr{L})$ of the nonzero operator $\mathscr{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 $\mathscr{L}$ has all its coefficients divisible by $p$.

######  Example 1.7.

The generating function of the Catalan numbers, $y(x)=\sum_{k\geq
0}C_{k}x^{k}$, satisfies the differential equation
$(4x^{2}-x)y^{\prime\prime}(x)+(10x-2)y^{\prime}(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
$\mathscr{L}=\left(4x^{2}-x\right)\partial_{x}^{2}+\left(10x-2\right)\partial_{x}+2$,
and the remainders of the left Euclidean divisions of $\partial_{x}^{p}$ by
$\mathscr{L}$ for $p\in\\{2,3,5\\}$ are

$\displaystyle\partial_{x}^{2}\bmod\mathscr{L}$
$\displaystyle=-\frac{2\left(5x-1\right)}{x\left(4x-1\right)}\partial_{x}-\frac{2}{x\left(4x-1\right)},$
$\displaystyle\partial_{x}^{3}\bmod\mathscr{L}$
$\displaystyle=\frac{6\left(22x^{2}-9x+1\right)}{x^{2}\left(4x-1\right)^{2}}\partial_{x}+\frac{6(6x-1)}{x^{2}\left(4x-1\right)^{2}},$
$\displaystyle\partial_{x}^{5}\bmod\mathscr{L}$
$\displaystyle=\frac{120\left(386x^{4}-325x^{3}+110x^{2}-17x+1\right)}{x^{4}\left(4x-1\right)^{4}}\partial_{x}+\frac{120(130x^{3}-69x^{2}+14x-1)}{x^{4}\left(4x-1\right)^{4}}.$

Note that indeed, we have $\partial_{x}^{p}\bmod\mathscr{L}=0$ modulo $p$, in
the three cases.

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
$\mathscr{L}=\partial_{x}-1$. Hence $\partial_{x}^{p}\bmod\mathscr{L}$ is
equal to 1 for all $p$. Indeed, in this case, $\mathscr{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.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 (1.4) can be applied since $\log(1-x)=-\sum_{k\geq 1}x^{k}/k$.
Second, we have $\mathscr{L}=(1-x)\partial_{x}^{2}-\partial_{x}$ and it holds
that (exercise!)

$\partial_{x}^{n}\bmod\mathscr{L}=\frac{(n-1)!}{(1-x)^{n-1}}\partial_{x}\qquad\text{for
all}\;n\geq 1.$

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

A natural question is whether the converses of 1.4 and 1.6 have any chance to
hold true. Concerning 1.4, the first example that comes to mind is the
function $y(x)=\sum_{k\geq 0}k!x^{k}$, which is D-finite and satisfies
$x^{2}y^{\prime\prime}(x)+(3x-1)y^{\prime}(x)+y(x)=0$. It obviously satisfies
the assumption of 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\geq 0}$ grows too fast, which is not
compatible with the growth of the coefficient sequence of an algebraic
function. A better converse of 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\geq 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^{\prime\prime}(x)+2(16x-1)y^{\prime}(x)+4y(x)=0$. From there, it
follows that $y(x)$ is the Gauss hypergeometric function
${}_{2}F_{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 1.4 appears to be false. One may wonder if
there is any way to reinforce even further the conclusion of 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\geq 0}a_{k}x^{k}\in\mathbb{Q}[[x]]$ is D-finite,
such that:

  * $(1)$

the sequence $(a_{k})_{k\geq 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.

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 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 $\mathscr{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 $\mathscr{L}$ has all its coefficients divisible by $p$,
then all solutions of (1) are algebraic functions.

######  Example 1.12.

Consider the operator

$\mathscr{L}=2x\left(x-1\right)\partial_{x}^{2}+\left(4x-1\right)\partial_{x}+1.$

Then, the reduction modulo $p$ of $\partial_{x}^{p}\bmod\mathscr{L}$ is equal
to 0 if $p\equiv 1\bmod 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 1.6
implies that $\mathscr{L}$ does not admit only algebraic solutions.

######  Example 1.13.

Consider now the operator

$\mathscr{L}_{r}=2x\left(x-1\right)\partial_{x}^{2}+\left(4x-1\right)\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}\bmod\mathscr{L}_{r}$ is equal to

$\frac{r(r+1)\cdots\savestack{\tmpbox}{\stretchto{\scaleto{\scalerel*[\widthof{(r+\frac{p-1}{2})}]{\kern-0.6pt\bigwedge\kern-0.6pt}{\rule[-505.89pt]{4.30554pt}{505.89pt}}}{}}{0.5ex}}\stackon[1pt]{(r+\frac{p-1}{2})}{\tmpbox}\cdots(r+p-1)}{(x(x-1))^{\frac{p-1}{2}}}\partial_{x}+\frac{\frac{p+1}{2}\cdot
r(r+1)\cdots\savestack{\tmpbox}{\stretchto{\scaleto{\scalerel*[\widthof{(r+\frac{p-1}{2})}]{\kern-0.6pt\bigwedge\kern-0.6pt}{\rule[-505.89pt]{4.30554pt}{505.89pt}}}{}}{0.5ex}}\stackon[1pt]{(r+\frac{p-1}{2})}{\tmpbox}\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 $\mathscr{L}_{r}$ admits
only algebraic solutions? 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 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.

###  2.1 Examples from Special functions: Hypergeometic 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{\bigintsss_{0}^{1}\sqrt{\frac{1-x^{2}u^{2}}{1-u^{2}}}\,\mathrm{d}u}=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}-\cdots.$
(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):

$\left({(x-x^{3})\partial_{x}^{2}+(1-x^{2})\partial_{x}+x}\right)\left(\sqrt{\frac{1-x^{2}u^{2}}{1-u^{2}}}\right)=\partial_{u}\left(\frac{xu\sqrt{1-u^{2}}}{\sqrt{1-x^{2}u^{2}}}\right).$
(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^{\prime\prime}(x)+(1-x^{2})p^{\prime}(x)+xp(x)=0.$ (5)

Writing $p(x)=\sum_{k\geq 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\geq 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\geq 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}:\qquad 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{\mathrm{d}u}{y}=\frac{\mathrm{d}u}{\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

$\left({(4x^{2}-4x)\partial_{x}^{2}+(8x-4)\partial_{x}+1}\right)\omega_{x}=-\mathrm{d}\left(\frac{2\sqrt{u(u-1)}}{(u-x)^{3/2}}\right).$
(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^{\prime\prime}(x)+(8x-4)y^{\prime}(x)+y(x)=0.$ (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_ ,

$\bigintssss_{C}\omega_{x}=2\bigintssss_{1}^{\infty}\frac{\mathrm{d}u}{\sqrt{u(u-1)(u-x)}}=\sum_{k\geq
0}b_{k}x^{k},$

where $b_{0}=2\bigintsss_{1}^{\infty}\frac{\mathrm{d}u}{u\sqrt{u-1}}=2\pi$ and
$\left(2k+1\right)^{2}b_{k}=4\left(k+1\right)^{2}b_{k+1}$ for all $k\geq 0$,
this recurrence relation being a consequence of the fact that
$y(x)=\int_{C}\omega_{x}$ satisfies Eq. 7. Thus,

$\bigintssss_{C}\omega_{x}=2\pi\sum_{k\geq
0}\binom{2k}{k}^{2}\left(\frac{x}{16}\right)^{k}.$ (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}_{\leq 0}$, defined by

${}_{2}F_{1}([a,b],[c];x)=\sum_{k\geq
0}\frac{(a)_{k}(b)_{k}}{(c)_{k}k!}x^{k},$ (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{}_{2}F_{1}([-1/2,1/2],[1];x^{2})$,
while $\int_{C}\omega_{x}$ in Eq. 8 is equal to
$2\pi\cdot{}_{2}F_{1}([1/2,1/2],[1];x)$. We have seen that in both cases these
functions are transcendental.

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

$x(x-1)y^{\prime\prime}(x)+((a+b+1)x-c)y^{\prime}(x)+aby(x)=0$ (10)

and the name _hypergeometric_ comes from the fact that the coefficient
sequence $(u_{k})_{k}$ of ${}_{2}F_{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}\qquad(k\geq 0).$

For other choices of parameters we recover the functions

$\displaystyle(1-x)^{\alpha}$
$\displaystyle={}_{2}F_{1}([-\alpha,1],[1];x),\quad\text{for
all}\;\alpha\in\mathbb{Q},$ $\displaystyle\sum_{k\geq 0}C_{k}x^{k}$
$\displaystyle={}_{2}F_{1}([1,1/2],[2];4x),$ $\displaystyle\log(1-x)$
$\displaystyle=-x\cdot{}_{2}F_{1}([1,1],[2];x),$ $\displaystyle\arcsin(x)$
$\displaystyle=x\cdot{}_{2}F_{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 functions even
becomes a polynomial: this is so for

$P_{n}(x)=2^{n}\cdot{}_{2}F_{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{}_{2}F_{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 ${}_{2}F_{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)\coloneqq
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. 1.

the hypergeometric function ${}_{2}F_{1}([a,b],[c];x)$ is algebraic;

  2. 2.

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

  3. 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 ${}_{2}F_{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 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},\ldots,a_{s+1}],[b_{1},\ldots,b_{s}];x)=\sum_{k\geq
0}\frac{(a_{1})_{k}\cdots(a_{s+1})_{k}}{(b_{1})_{k}\cdots(b_{s})_{k}k!}x^{k}.$
(11)

###  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},\dotsc,i_{n}}x_{1}^{i_{1}}\dotsm
x_{n}^{i_{n}}\;\in\mathbb{Q}[[x_{1},\ldots,x_{n}]]$

is the univariate power series

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

######  Example 2.1 (Dyck bridges).

Let $B_{n}$ be the number of $\\{\uparrow,\rightarrow\\}$-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\geq 0}B_{n}t^{n}$. Then,

$B(t)=\operatorname{Diag}\left(\frac{1}{1-x-y}\right)=\sum_{n\geq
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 observation444Here, and in all
the text, $[x^{n}]$ denotes coefficient extraction of $x^{n}$.
$\textsf{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$)

$\operatorname{Diag}\left(F\right)(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 $\textsf{Diag}(F)$.

######  Example 2.2 (Dyck bridges, continued).

The proof sketched above directly concludes that

$\operatorname{Diag}\left(\frac{1}{1-x-y}\right)=\frac{1}{2\pi
i}\oint_{|x|=\epsilon}\frac{dx}{x-x^{2}-t}={\left.{\frac{1}{1-2x}}\right|_{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

$\operatorname{Diag}\left(\frac{1}{1-x-y-z}\right)=\sum_{n\geq
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}$ when $n$
goes to infinity, and the presence of the factor $n^{-1}$ is incompatible with
algebraicity. Another proof is based on rewriting

$\operatorname{Diag}\left(\frac{1}{1-x-y-z}\right)={}_{2}F_{1}\left(\left[\frac{1}{3},\frac{2}{3}\right],\left[1\right];27t\right),$
(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},\ldots,x_{n})$ is a multivariate D-finite function555This 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},\ldots,x_{n}$., then $\operatorname{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},\ldots,x_{n})\cap\mathbb{Q}[[x_{1},\ldots,x_{n}]]$,
then the residue theorem allows to write (for some $\epsilon>0$)

$\operatorname{Diag}(F)(t)=\frac{1}{(2\pi
i)^{n-1}}\bigointsss_{|x_{1}|=\cdots=|x_{n-1}|=\epsilon}F\left(x_{1},\ldots,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 $\operatorname{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}^{n}_{\mathbb{C}(t)}$ defined by the
equations $Q(x_{1},\ldots,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 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. (1)

$f(t)=\operatorname{Diag}(F)$ for some
$F\in\mathbb{Q}(x_{1},\ldots,x_{n})\cap\mathbb{Q}[[x_{1},\ldots,x_{n}]]$;

  2. (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 2.4
and it is still open as of today.

######  Question 2.5.

Is

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

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)=\operatorname{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

$\displaystyle(1+t)^{-1/4}$ $\displaystyle\;\bmod 5,$
$\displaystyle(1+6t+6t^{2})^{-1/6}$ $\displaystyle\;\bmod 7,$
$\displaystyle(1+6t+2t^{2}+8t^{3})^{-1/10}$ $\displaystyle\;\bmod 11.$

On the other hand, the Christol-André 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\left(27t-1\right)\partial_{t}^{2}+\left(54t-1\right)\partial_{t}+6$
as minimal-order differential equation, with local basis

$1+6t+90t^{2}+\cdots\quad\text{and}\quad\log\\!\left(t\right)+\left(6\log\\!\left(t\right)+15\right)t+\cdots$

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 ${}_{3}F_{2}$ (transcendental)
function from 2.5 is algebraic (of degree at most $p^{54}$). Hence, even if
this ${}_{3}F_{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 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) $\mathscr{S}$ which is a fixed subset of the set of
nearest-neighbor steps $\\{{\swarrow,}\ {\leftarrow,}\ {\nwarrow,}\
{\uparrow,}\ {\nearrow,}\ {\rightarrow,}\ {\searrow,}\ {\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 $\mathscr{S}\subseteq\\{{\swarrow,}\ {\leftarrow,}\ {\nwarrow,}\
{\uparrow,}\ {\nearrow,}\ {\rightarrow,}\ {\searrow,}\ {\downarrow}\\}$, we
denote by
$\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}q_{i,j,n}$
the number of $\mathscr{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
$\mathscr{S}$-walks of length $n$ returning to $(0,0)$ (“excursions”) and
$q_{n}:=\sum_{i,j\geq 0}q_{i,j,n}$, the number of $\mathscr{S}$-walks with
prescribed length $n$.

To these sequences one attaches various functions, namely the _full generating
function_

$Q_{\mathscr{S}}(x,y,t)=\sum_{n=0}^{\infty}\biggl{(}\sum_{i,j=0}^{\infty}q_{i,j,n}x^{i}y^{j}\biggr{)}t^{n}\;\in{\mathbb{Q}}[x,y][[t]],\vspace{-0.09cm}$

and its corresponding univariate specializations
$Q_{\mathscr{S}}(0,0,t)=\sum_{n\geq 0}e_{n}t^{n}$ (“excursions generating
function”), $Q_{\mathscr{S}}(1,1,t)=\sum_{n\geq 0}q_{n}t^{n}$ (“length
generating function”), $Q_{\mathscr{S}}(1,0,t)$ and
$\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}Q_{\mathscr{S}}(0,1,t)$
(“boundary returns”) and $[x^{0}]\,Q_{\mathscr{S}}(x,1/x,t)$ (“diagonal
returns”).

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

The model $\mathscr{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 $\mathscr{S}$ is included in $\\{\ {\uparrow,}\
{\nearrow,}\ {\rightarrow,}\ {\searrow,}\ {\downarrow}\\}$ or in
$\\{{\leftarrow,}\ {\nwarrow,}\ {\uparrow,}\ {\nearrow,}\ {\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 $\mathscr{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 algebro-differential
properties of $Q_{\mathscr{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
$\mathscr{S}=\\{{\nwarrow,}\ {\uparrow,}\ {\nearrow,}\ {\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\\},\\{\nearrow\\}$) and $7$ trident walks of length $2$
($\\{\uparrow-\uparrow\\},\\{\uparrow-\downarrow\\},\\{\uparrow-\nearrow\\},\\{\nearrow-\nwarrow\\},\\{\nearrow-\uparrow\\},\\{\nearrow-\nearrow\\},\\{\nearrow-\downarrow\\}$).
It was proved in [16] that the length generating function of trident walks

$Q(t)=\sum_{n\geq
0}q_{n}t^{n}=1+2\,t+7\,t^{2}+23\,t^{3}+84\,t^{4}+301\,t^{5}+1127\,t^{6}+\cdots$

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$:

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

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,\ldots,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/\cdots/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}}\times{}\right.\right.\\\
\left.\left.\left((1-v)\,_{2}F_{1}\left(\left[\frac{1}{2},\frac{3}{2}\right]\\!\\!,[1];\frac{16t^{2}}{4t^{2}+1}\right)-(1+v)(1-4v+8v^{2})\,_{2}F_{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 ${}_{2}F_{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
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
$\mathscr{S}=\\{\uparrow,\leftarrow,\searrow\\}$ and in case 18 for the model
$\mathscr{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 trident 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
$\mathscr{S}={\\{\nearrow,\swarrow,\leftarrow,\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
${{}_{3}F_{2}}\left([5/6,1/2,1],[5/3,2];16t^{2}\right).$

######  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 2.6 had no implication concerning 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\geq 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\left(4t-1\right)^{2}H^{8}-18\left(4t-1\right)^{2}H^{4}-8\left(16t^{2}+24t+1\right)H^{2}-\left(4t-1\right)^{2}=0$,
and

$G(t)=\frac{1}{2t}\cdot\left({{}_{2}{{}{{F_{1}}}}\\!\left(\left[-\frac{1}{12},\frac{1}{4}\right],\left[\frac{2}{3}\right];-\frac{64t\left(4t+1\right)^{2}}{\left(4t-1\right)^{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 $\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\bmod t^{1000}$ and
$\mathcal{L}_{0,y}({G(0,y,t)})=0\bmod 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
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 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 2.6 and 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\geq 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:

$\displaystyle
c_{n-3}+20\left(4500n^{2}-18900n+19739\right)c_{n-2}+80352000n(5n-1)(5n-2)(5n-4)c_{n}$
$\displaystyle+25\left(2592000n^{4}-16588800n^{3}+39118320n^{2}-39189168n+14092603\right)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}\coloneqq(2^{10}\cdot 3^{5}\cdot
5^{4})^{n}\cdot({\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}3/5})_{n}\cdot({\color[rgb]{1,.5,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,.5,0}4/5})_{n}\cdot
c_{n}\in\mathbb{Z}$ for all integers $\geq 0$;

  * •

[Dubrovin & Yang]: $b_{n}\coloneqq(2^{12}\cdot 3^{5}\cdot
5^{4})^{n}\cdot({\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}2/5})_{n}\cdot({\color[rgb]{1,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,1}\pgfsys@color@cmyk@stroke{0}{1}{0}{0}\pgfsys@color@cmyk@fill{0}{1}{0}{0}9/10})_{n}\cdot
c_{n}\in\mathbb{Z}$ for all integers $\geq 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
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 $\widetilde{c}_{n}\coloneqq
w^{n}\cdot(u)_{n}\cdot(v)_{n}\cdot c_{n}\in\mathbb{Z}$ for all $n\geq 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\geq 0}\widetilde{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 $\widetilde{c}_{n}\coloneqq
w^{n}\cdot(u)_{n}\cdot(v)_{n}\cdot c_{n}\in\mathbb{Z}$ for all $n\geq 0$ are
the ones listed in Fig. 1. Moreover, for each of these pairs, the
corresponding generating function $\sum_{n\geq 0}\widetilde{c}_{n}x^{n}$ is
algebraic, of algebraicity degree as in Fig. 1.

$\;\\#\;$ $\;u\;$ $\;v\;$ order alg. degree $\;\\#\;$ $\;u\;$ $\;v\;$ order
alg. degree 1 1/5 4/5 2 120 6 19/60 49/60 4 155520 2 3/5 4/5 2 120 7 19/60
59/60 4 46080 3 2/5 9/10 4 120 8 29/60 49/60 4 46080 4 7/30 9/10 4 155520 9
29/60 59/60 4 155520 5 9/10 17/30 4 155520

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.

For instance, in case 4 of Figure 1, 2.11 states that the generating function
of the sequence $\widetilde{c}_{n}\coloneqq(2^{14}\cdot 3^{7}\cdot
5^{4})^{n}\cdot(7/30)_{n}\cdot(9/10)_{n}\cdot c_{n}$,

$\sum_{n\geq
0}\widetilde{c}_{n}x^{n}=1-3042900x+58917109730850x^{2}-1389307608898903890000x^{3}+\cdots$

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

$\displaystyle\mathscr{L}_{4}=125x^{3}\left(88335360x+1\right)\left(7739670528000x^{2}+31104000x+1\right)\partial_{x}^{4}+$
$\displaystyle
25x^{2}\left(35095911228443197440000x^{3}+95685546737664000x^{2}+2823828480x+23\right)\partial_{x}^{3}+$
$\displaystyle
60x\left(36896918938488668160000x^{3}+56436938459136000x^{2}+1177963920x+7\right)\partial_{x}^{2}+$
$\displaystyle\left(1254982687120120872960000x^{3}+654118326337536000x^{2}+16648081920x+12\right)\partial_{x}+$
$\displaystyle 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 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
$\mathscr{L}_{4}$ is zero for all primes $5<p<100$ except for
$p\in\\{7,31\\}$. 1.11 then suggests that indeed $\mathscr{L}_{4}$ possesses
algebraic solutions only.

##  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 $\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.11)
provides such a criterion: in its enhanced version (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$

$\mathscr{L}=\partial_{x}+a(x)$ (13)

with $a(x)\in\mathbb{Q}(x)$. It makes sense to consider the reduction
$a(x)\,\text{\rm 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

$\mathscr{L}_{p}=\partial_{x}+a(x)\,\text{\rm mod}\,p$ (14)

of $\mathscr{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 $\mathscr{L}$
(resp. of $\mathscr{L}_{p}$) when it is a solution of the corresponding
differential equation, _i.e._ when $\mathscr{L}(f)=0$ (resp.
$\mathscr{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{\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}}$

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^{\prime}(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^{\prime}(x)=a(x)f(x)$, we get

$0=M(f)^{\prime}=Nf^{N-1}f^{\prime}+\sum_{i=0}^{N-1}m_{i}^{\prime}(x)f^{i}+\sum_{i=0}^{N-1}m_{i}(x)if^{i-1}f^{\prime}\\\
=Nf^{N-1}a(x)f+\sum_{i=0}^{N-1}m_{i}^{\prime}(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}^{\prime}(x)+m_{i}(x)ia(x))f^{i}.$

Hence, the polynomial
$P(Y)=Na(x)Y^{N}+\sum_{i=0}^{N-1}(m_{i}^{\prime}(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^{\prime}(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. ∎

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 (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^{\prime}=\frac{1}{2(x-1)}y.$ (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^{\prime}=\frac{n_{p}}{x-1}y$ where
$n_{p}\in\mathbb{Z}$ is such that $n_{p}\equiv\frac{1}{2}\,\text{\rm mod}\,p$
and, hence $\widetilde{f}_{p}(x)=(1-x)^{n_{p}}$ is a nonzero solution of the
reduction modulo $p$ of (15). The interesting point is that
$\widetilde{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^{\prime}+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}$. ∎

######  Example 3.4.

Consider the differential equation

$y^{\prime}=\frac{1}{x^{2}+1}y$ (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 $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}}$ (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)}\rightarrow\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)\,\text{\rm
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}}\rightarrow\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)\,\text{\rm mod}\,p=a(x)\,\text{\rm
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. ∎

####  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.

###### 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}_{\geq 1}$.
According to Proposition 3.1, we have to prove that $P(x)$ and the
$\alpha_{i,j}$’s for $j\geq 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)\,\text{\rm mod}\,p=a(x)\,\text{\rm
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)\,\text{\rm
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,\ldots,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,\ldots,r_{i}\\}$, we have $\alpha_{i,j}=0$. Similarly, Proposition
3.3 also ensures that, for almost all primes $p$, $a(x)\,\text{\rm 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. ∎

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)\,\text{\rm 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^{\prime}+b(x)y=0$ (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

$\displaystyle\Delta:\mathbb{F}_{p}(x)$ $\displaystyle\rightarrow$
$\displaystyle\mathbb{F}_{p}(x)$ $\displaystyle f$ $\displaystyle\mapsto$
$\displaystyle f^{\prime}+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)\ |\ f^{\prime}(x)=0\\}$)
implying that $(\alpha f)^{\prime}=\alpha f^{\prime}$ 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)\rightarrow\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\geq 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\bmod 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)$). ∎

######  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\geq 0$, we have in the
ring of differential operators a relation of the form

$\big{(}\partial_{x}+b(x)\big{)}^{k}=\partial_{x}^{k}+\star\partial_{x}^{k-1}+\cdots+\star\partial_{x}+b_{k}(x),$
(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\geq 0,\ b_{k+1}(x)=b_{k}^{\prime}(x)+b(x)b_{k}(x).$ (20)

This gives the expected inductive formula for the $p$-curvature of (18), 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 $\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\leq i<p$ have to vanish, and that
$b_{p}(x)$ belongs to $\mathbb{F}_{p}(x^{p})$.

In conclusion, we have the relation

$\big{(}\partial_{x}+b(x)\big{)}^{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
$\mathscr{L}=\partial_{x}+b(x)$. In particular, the $p$-curvature vanishes if
and only if $\mathscr{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},\ldots,\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})}\qquad\text{(for
}\alpha\in I_{k}\text{)},$

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

$\tau_{i}(\underline{\alpha})=(\alpha_{1},\,\ldots,\,\alpha_{i-2},\,\alpha_{i-1}{-}1,\,\alpha_{i}{+}1,\,\alpha_{i+1},\,\ldots,\,\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},\ldots,\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}}\cdot(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,\ldots,0)$ or
$\underline{\alpha}=(0,\ldots,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. ∎

######  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_{\begin{subarray}{c}1\leq
j\leq r_{i}\\\ j\equiv 1\text{ mod
}p\end{subarray}}\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,\ldots,m\\}$, we have $r_{i}=1$ and $\beta_{i,1}^{p}=\beta_{i,1}$,
_i.e._ $\beta_{i,1}\in\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

$\mathscr{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:

$\mathscr{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
$\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,\ldots\\}$ 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 $\mathscr{L}=\partial_{x}+a(x)$ as in Eq. (13) and, for almost all prime
numbers $p$, denote by $\mathscr{L}_{p}$ its reduction modulo $p$ as in Eq.
(14). The following properties are equivalent:

  1. (1)

$\mathscr{L}$ has a nonzero algebraic solution;

  2. (2)

for almost all primes $p$, $\mathscr{L}_{p}$ has a nonzero rational solution;

  3. (3)

for almost all primes $p$, the $p$-curvature of $\mathscr{L}_{p}$ vanishes;

  4. (4)

for almost all primes $p$, the operator $\mathscr{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 Grothendieck’s conjecture

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

$\mathscr{L}=\partial_{x}^{n}+a_{n-1}(x){\cdot}\partial_{x}^{n-1}+\cdots+a_{1}(x){\cdot}\partial_{x}+a_{0}(x)$
(21)

with $a_{i}(x)\in\mathbb{Q}(x)$. As in the order-$1$ case, one can consider
the reduction $\mathscr{L}_{p}$ of $\mathscr{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 $\mathscr{L}$ to the rationality of the solutions of
$\mathscr{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 hypergeometric
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 $\mathscr{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 $\mathscr{L}$ has a full basis of algebraic solutions. Similarly,
it is tempting to look at the set of solutions of $\mathscr{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
$\mathscr{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 $\mathscr{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
$\mathscr{L}\in\mathbb{Q}(x)\langle\partial_{x}\rangle$ as in Eq. (21), the
following properties are equivalent:

  1. (1)

$\mathscr{L}$ has a full basis of algebraic solutions;

  2. (2)

for almost all primes $p$, $\mathscr{L}_{p}$ has a full basis of rational
solutions.

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

Consider the equation

$\mathscr{L}=\partial_{x}^{n}+b_{n-1}(x){\cdot}\partial_{x}^{n-1}+\cdots+b_{1}(x){\cdot}\partial_{x}+b_{0}(x)$
(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.

Let $Y^{\prime}+B(x)Y=0$ be the differential system associated to (22), where

$B=\left(\begin{array}[]{cccccc}0&-1&0&\cdots&0&0\\\ 0&0&-1&\cdots&0&0\\\
\vdots&\vdots&\vdots&\vdots&\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{array}\right)\in
M_{n}(\mathbb{F}_{p}(x)).$ (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

$\displaystyle\Delta:\mathbb{F}_{p}(x)^{n}$ $\displaystyle\rightarrow$
$\displaystyle\mathbb{F}_{p}(x)^{n}$ $\displaystyle F$ $\displaystyle\mapsto$
$\displaystyle F^{\prime}+B(x)F.$

######  Definition 3.17.

The map

$\Delta^{p}:\mathbb{F}_{p}(x)^{n}\rightarrow\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}^{\prime}(x)+B(x)B_{k}(x)$ (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 $\mathscr{L}\in\mathbb{F}_{p}(x)\langle\partial_{x}\rangle$ be a
differential operator as in Eq. (22). The following properties are equivalent:

  1. (1)

$\mathscr{L}$ has a full basis of rational solutions;

  2. (2)

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

  3. (3)

$\mathscr{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$.

The equivalence between the first two properties is immediate. The equivalence
between the last two properties follows from the wronskian lemma.

If $\mathscr{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

$\displaystyle P:\mathbb{F}_{p}(x)^{n}$ $\displaystyle\rightarrow$
$\displaystyle\mathbb{F}_{p}(x)^{n}$ $\displaystyle F$ $\displaystyle\mapsto$
$\displaystyle\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),\ldots,f_{r-1}(x),g_{0}(x),\ldots,g_{r-1}(x)$, the equality

$\Delta\big{(}f_{0}(x),\ldots,f_{r-1}(x)\big{)}=\big{(}g_{0}(x),\ldots,g_{r-1}(x)\big{)}$

is equivalent to the following congruence in
$\mathbb{F}_{p}(x)\langle\partial_{x}\rangle$:

$\big{(}f_{0}(x)+\cdots+f_{r-1}(x)\partial_{x}^{r}\big{)}\cdot\partial_{x}\equiv
g_{0}(x)+\cdots+g_{r-1}(x)\partial_{x}^{r}\pmod{\mathscr{L}}.$

It follows from this observation that, writing
$E_{i}=(0,\ldots,0,1,0,\ldots,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 $\mathscr{L}$. Hence
$\Delta^{p}(E_{i})$ vanishes if and only if $\mathscr{L}$ divides
$\partial_{x}^{p+i}$. The equivalence between the second and the third
condition of the theorem follows immediately. ∎

######  Remark 3.19.

The three assertions of 3.18 are also equivalent to

  1. (4)

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

  2. (5)

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

The implication (5) $\Longrightarrow$ (4) is proved in [43, Lemma 1], while
(5) $\Longrightarrow$ (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 $\mathscr{L}$ in (22).

######  Remark 3.20.

Assume that $\mathscr{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))$

is a solution of $Y^{\prime}+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^{\prime}+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^{\prime}+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\geq 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 $\mathscr{L}$ as in Eq. (21), the following
properties are equivalent:

  1. (1)

$\mathscr{L}$ has a full basis of algebraic solutions;

  2. (2)

for almost all primes $p$, the $p$-curvature of $\mathscr{L}_{p}$ vanishes;

  3. (3)

for almost all primes $p$, $\mathscr{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 ${\bf a}=\\{a_{1},\ldots,a_{s+1}\\}$ and ${\bf
b}=\\{b_{1},\ldots,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

$\mathscr{Hyp}({\bf a},{\bf
b})\coloneqq(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 $\mathscr{Hyp}({\bf a},{\bf b})$ admits in its
solution space the generalized hypergeometric function
${}_{s+1}F_{s}([a_{1},\ldots,a_{s+1}],[b_{1},\ldots,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 ${\bf a}=\\{a_{1},\ldots,a_{s+1}\\}$ and
${\bf b}=\\{b_{1},\ldots,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:

  1. 1.

the hypergeometric function
${}_{s+1}F_{s}([a_{1},\ldots,a_{s+1}],[b_{1},\ldots,b_{s}];x)$ is algebraic;

  2. 2.

the operator $\mathscr{Hyp}({\bf a},{\bf b})$ admits a full basis of algebraic
solutions;

  3. 3.

for all $1\leq\ell<D$ with $\gcd(\ell,D)=1$ the sets $\\{e^{2\pi i\ell
a_{j}},j\leq s+1\\}$ and $\\{e^{2\pi i\ell b_{j}},j\leq s+1\\}$ interlace on
the unit circle.

######  Example 3.23.

The Beukers-Heckman criterion immediately implies that the operator
$\mathscr{Hyp}({\bf a},{\bf b})$ admits a full basis of algebraic solutions
for the choice

${\bf
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{\bf
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\geq 0}u_{n}x^{n}$ of
the sequence

$u_{n}\coloneqq\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 $\mathscr{Hyp}({\bf a},{\bf
b})$, the situation is much more subtle. For instance,
${}_{2}F_{1}([1/2,1/3],[3/2];x)$ is transcendental, while
${}_{2}F_{1}([3/2,1/3],[1/2];x)$ is algebraic. In a work (in progress) by
Fürnsinn and Yurkevich, a generalization of 3.22 is given, which allows to
decide algebraicity/transcendence of arbitrary generalized hypergeometric
functions (with potentially irrational parameters).

In addition to 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
${}_{2}F_{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 ${}_{2}F_{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 $\mathscr{L}$, an integer $N(\mathscr{L})$ such that the fact
that $\mathscr{L}$ has a full basis of algebraic solutions can be read off the
$p$-curvatures of $\mathscr{L}$ for the primes $p<N(\mathscr{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^{\prime\prime}(x)+\frac{1}{2}p^{\prime}(x)y^{\prime}(x)-\big{(}n(n+1)x+B\big{)}{\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}\backslash\\{0,1,\infty\\}$. In our setting, this means that
one can safely assume that the differential operator $\mathscr{L}$ has only
singularities at $0$, $1$ and $\infty$. Under this additional assumption, Tang
[68] proves that if _all_ 666When $\mathscr{L}$ does not reduce properly at a
prime $p$, the $p$-curvature of $\mathscr{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]. the $p$-curvatures of $\mathscr{L}$
vanish, then $\mathscr{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. (1)

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

  2. (2)

for almost all primes $p$, all the roots of $L\text{ mod }p$ are in
$\mathbb{F}_{p}$;

  3. (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{\mathscr{L},p}$, _i.e._ that the
right-hand side shifts from $X$ to $0$, is explained by the fact the classical
Frobenius map behaves “multiplicatively” (it belongs naturally to some Galois
group) while the $p$-curvature behaves “additively” (it belongs naturally to
some Lie algebra).

In the classical setting, Kronecker’s theorem is obtained as a corollary of
Chebotarev’s density theorem, which is itself proved by means of Artin’s
$L$-functions. Unfortunately, similar tools do not seem to be available so far
in the differential context; developing them might then sound as an exciting
project.

As mentioned above, Honda proved that the Grothendieck conjecture for order-1
differential equations is equivalent to Kronecker’s theorem. In [30, §4], the
Chudnovsky brothers gave an elementary (although “extravagant”) proof of these
equivalent statements; their approach is based on Hermite’s explicit Hermite-
Padé approximants to binomial functions. More precisely, they proved that if
$y^{\prime}(x)=\frac{x}{\alpha}y(x)$ has zero $p$-curvature for almost all
primes $p$, then for all primes ideals $\mathfrak{p}$ of $\mathbb{Q}(\alpha)$
all the binomial coefficients $\binom{\alpha}{n}$ are $\mathfrak{p}$-integral
for all $n$. From there, it is shown that Hermite-Padé approximants to
$1,x^{\alpha},\ldots,x^{(m-1)\alpha}$ at $x=1$ with weights $(N,\ldots,N)$ are
trivial for large $m$ and $N$. This in turn implies that
$1,x^{\alpha},\ldots,x^{(m-1)\alpha}$ are linearly dependent over
$\mathbb{Q}(x)$, that is $x^{\alpha}$ is an algebraic function, which is
equivalent to $\alpha\in\mathbb{Q}$.

###  3.3 Computation of the $p$-curvature

After what we have done previously, it is clear that the $p$-curvature is an
invariant of primary importance of linear differential equations in
characteristic $p$. In this subsection, we outline some algorithms for
computing it (or other quantities associated to it) efficiently.

####  3.3.1 Operators of order $1$

In the case of differential equations of order $1$ of the form (18):

$y^{\prime}+b(x)y=0$

we have seen in Theorem 3.12 that the $p$-curvature is explicitly given by the
formula

$b_{p}(x)=b^{(p-1)}(x)+b(x)^{p}.$

Furthermore, computing explicitly the latter is a quite easy task which
directly reduces to writing the partial fraction decomposition of $b(x)$.
Indeed, we have seen that if $b(x)$ decomposes as

$b(x)=P(x)+\sum_{i=1}^{m}\sum_{j=1}^{r_{i}}\frac{\alpha_{i,j}}{(x-a_{i})^{j}}$

then

$b_{p}(x)=P^{(p-1)}(x)+P(x)^{p}-\sum_{i=1}^{m}\sum_{\begin{subarray}{c}1\leq
j\leq r_{i}\\\ j\equiv 1\text{ mod
}p\end{subarray}}\frac{\alpha_{i,j}}{(x-a_{i})^{j+p-1}}+\sum_{i=1}^{m}\sum_{j=1}^{r_{i}}\frac{\alpha_{i,j}^{p}}{(x-a_{i})^{pj}}.$

Importantly for algorithmic purposes, we observe that the size of $b_{p}(x)$
is roughly the same as the same of the input $b(x)$, although the degree of
(the numerator and the denominator of) the former is $p$ times larger the
degree of the latter. This apparent contradiction is explained by the fact
that $b_{p}(x)$ is actually a function of $x^{p}$; it is then a sparse
rational function, in the sense that a large proportion of its coefficients
vanishes.

######  Remark 3.25.

Another option for computing explicitly the $p$-curvature of differential
operators of order $1$ is presented in [21, Thm. 2]; it avoids the computation
of partial fraction decomposition and to factor the denominator of $b(x)$. Let
us briefly sketch it with the differential operator

$\partial_{x}-\frac{1}{x^{2}+1}$

of Example 3.4. We write $b(x)=-1/(x^{2}+1)$ and assume $p>2$ for simplicity.
In order to compute $b_{p}(x)$, we expand $b(x)$ in power series:

$b(x)=-\sum_{n=0}^{\infty}(-1)^{n}x^{2n}.$

The $(p{-}1)$-st derivative of $x^{2n}$ is $0$ when $2n\not\equiv-1\pmod{p}$,
and it is $-x^{2n-p+2}$ otherwise thanks to Wilson’s theorem. Writing
$2n=p-1+pk$ and noticing that $k$ has to be even, $k=2\ell$, we end up with

$b^{(p-1)}(x)=-\sum_{\ell=0}^{\infty}(-1)^{\ell-\frac{p-1}{2}}x^{2\ell p}$

On the other hand, it is clear that
$b(x)^{p}=-\sum_{n=0}^{\infty}(-1)^{n}x^{2np}.$ Adding both sums, we find

$b_{p}(x)=-\sum_{n=0}^{\infty}(-1)^{n}\cdot\left(1-(-1)^{\frac{p-1}{2}}\right)\cdot
x^{2np}.$

When $p\equiv 1\pmod{4}$, the exponent $\frac{p-1}{2}$ is even and the term in
the parenthesis vanishes. Therefore $b_{p}(x)=0$ in this case. On the
contrary, when $p\equiv 3\pmod{4}$, we have

$b_{p}(x)=-2\cdot\sum_{n=0}^{\infty}(-1)^{n}\cdot
x^{2np}=-\frac{2}{1+x^{2p}}=-\frac{2}{(1+x^{2})^{p}}.$

and we recover the result of Example 3.14.

The same idea applies actually to any differential operator
$\mathscr{L}=\partial_{x}-b(x)$. Indeed, as already noticed its $p$-curvature
is a rational function in $x^{p}$. Besides, it is of the form
$f(x)/\text{denom}(b(x))$, where the numerator $f(x)$ is a polynomial of
degree at most $d=\deg(b(x))$. Hence, it is enough to determine the power
series expansion of $(b(x)^{(p-1)})^{1/p}$ at precision $x^{d}$, starting from
the power series expansion of $b(x)$ at the same precision $d$. If
$b(x)=\sum_{n\geq 0}u_{n}x^{n}$, then by Wilson’s theorem we have
$(b(x)^{(p-1)})^{1/p}=-\sum_{n\geq 1}u_{np-1}x^{n-1}$, and hence it is enough
to be able to compute the terms $u_{p-1},\ldots,u_{dp-1}$. Since $b(x)$ is a
rational function, the sequence $(u_{n})_{n\geq 0}$ satisfies a linear
recursion of order at most $d$, with coefficients in $\mathbb{F}_{p}$ (given
by the coefficients of $\text{denom}(b)$). As the $N$-th term of such a linear
recurrence with _constant_ coefficients can be computed using
$O(d\log(d)\log(N))$ operations in $\mathbb{F}_{p}$ using the technique of
_binary powering_ combined with fast polynomial multiplication in
$\mathbb{F}_{p}[x]$, we conclude that the $p$-curvature $b_{p}(x)$ can be
computed by an algorithm that uses $O(d^{2}\log(d)\log(p))$ operations in
$\mathbb{F}_{p}$.

Note that the reasoning above shows that the $p$-curvature $b_{p}(x)$ of
$\mathscr{L}=\partial_{x}-b(x)$ is zero if and only if the following infinite
systems of congruences holds

$u_{n}\equiv u_{(n+1)p-1}\pmod{p}\quad\text{for all}\;n\geq 0.$

####  3.3.2 Reading the $p$-curvature on the solutions

For differential equations of higher orders, the sparcity of the $p$-curvature
no longer holds in general. However, we have the following result.

######  Proposition 3.26.

Let

$\mathscr{L}=\partial_{x}^{n}+b_{n-1}(x){\cdot}\partial_{x}^{n-1}+\cdots+b_{1}(x){\cdot}\partial_{x}+b_{0}(x)$

with $b_{i}(x)\in\mathbb{F}_{p}(x)$ and let $B(x)$ be the associated companion
matrix (see Equation (23)). Let $f(x)\in\mathbb{F}_{p}(x)$ be a common
denominator of the $b_{i}(x)$’s and

$d=\max\big{(}\deg
f(x),\,\deg(f(x)b_{0}(x)),\,\ldots,\,\deg(f(x)b_{n-1}(x))\big{)}.$

Let $B_{p}(x)$ be the matrix of the $p$-curvature of $\mathscr{L}$ defined by
the recurrence (24). Then, the following holds.

  * (i)

The matrix $B_{p}(x)$ has the form $\frac{1}{f(x)^{p}}C_{p}(x)$ where the
entries of $C_{p}(x)$ are all polynomials of degree at most $dp$.

  * (ii)

The matrix $B_{p}(x)$ is similar to a matrix with coefficients in
$\mathbb{F}_{p}(x^{p})$.

The last assertion implies that the trace, the determinant of $B_{p}(x)$ and,
more generally, all the coefficients of its characteristic polynomial lie in
$\mathbb{F}_{p}(x^{p})$; they are then sparse rational functions. Combining
with Proposition 3.26.(i), we deduce that their sizes is comparable to the
size of the $b_{i}(x)$’s, although the size of the $p$-curvature itself is in
general $p$ times larger.

In order to design fast algorithms for computing the $p$-curvature, it is
useful to go beyond Cartier’s lemma (see Proposition 3.18) and relate the
$p$-curvature to the shape of solutions. Let

$\mathscr{L}=\partial_{x}^{n}+b_{n-1}(x){\cdot}\partial_{x}^{n-1}+\cdots+b_{1}(x){\cdot}\partial_{x}+b_{0}(x)$

be a differential operator as before. In §3.2.1, we have seen that, when the
$p$-curvature of $\mathscr{L}$ vanishes and the $b_{i}(x)$’s have no pole at
$0$, a fundamental system of solutions of $\mathscr{L}$ is explicitly given by

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

where the $B_{k}(x)$’s are the matrices defined by the recurrence (24). In
full generality, _i.e._ without assuming the vanishing of $B_{p}$, the idea is
to consider the formal expansion

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

Of course, this does not make sense in $\mathbb{F}_{p}(x)$ because of the
division by $k!$, but we shall see that it does make sense in a suitable ring.
A natural idea to achieve this goal is to introduce divided powers, _i.e._ to
consider the so-called ring of Hurwitz series, denoted by
$\mathbb{F}_{p}[[x]]^{\text{\rm dp}}$, whose elements are formal series of the
form

$a_{0}+a_{1}\gamma_{1}(x)+a_{2}\gamma_{2}(x)+\cdots+a_{k}\gamma_{k}(x)+\cdots.$

In the above expression, the $\gamma_{k}(x)$’s are just formal names without
further additional meaning. Of course, they should be thought of as
$\frac{x^{k}}{k!}$ but we cannot write this division because the denominator
may vanish. The multiplication on $\mathbb{F}_{p}[[x]]^{\text{\rm dp}}$ is
governed by the rule

$\gamma_{m}(x)\cdot\gamma_{n}(x)=\binom{m+n}{m}\cdot\gamma_{n+m}(x)$

for any nonnegative integers $m$ and $n$. Besides $k[[x]]^{\text{\rm dp}}$ is
equipped with a natural derivation that takes $\sum_{k}a_{k}\gamma_{k}(x)$ to
$\sum_{k}a_{k+1}\gamma_{k}(x)$. We have to be careful however that
$\mathbb{F}_{p}[[x]]^{\text{\rm dp}}$ is not a domain (_e.g._
$\gamma_{1}(x)^{p}=0$) and, because of that, we cannot consider its ring of
fractions. But still, if the matrix $B(x)$ has polynomial coefficients, all
the $B_{k}(x)$’s have the same property and we can consider their images
$B_{k}^{\text{\rm dp}}(x)$ is the ring
$M_{n}\big{(}\mathbb{F}_{p}[[x]]^{\text{\rm dp}}\big{)}$. We then can form

$S^{\text{\rm dp}}(x)=\sum_{k=0}^{\infty}(-1)^{k}B_{k}^{\text{\rm
dp}}(x)\cdot\gamma_{k}(x)$ (25)

obtaining this way a fundamental matrix of solutions of $\mathscr{L}$ over
$\mathbb{F}_{p}[[x]]^{\text{\rm dp}}$. This construction works actually more
generally as soon as the entries of $B(x)$ have no pole at zero: in this case,
we can expand them as series in $x$ in order to view them in
$\mathbb{F}_{p}[[x]]^{\text{\rm dp}}$. The precise relation between
$S^{\text{\rm dp}}(x)$ and the $p$-curvature is given by the next lemma.

######  Lemma 3.27 (Bostan–Caruso–Schost [13]).

We have the matrix relation:

$\frac{d^{p}S^{\text{\rm dp}}(x)}{dx^{p}}=-B_{p}^{\text{\rm dp}}(x)\cdot
S^{\text{\rm dp}}(x).$

###### Proof.

Set $M=\mathbb{F}_{p}[x]$ and let $\Delta:M^{n}\to
M^{n},Y\mapsto\frac{dY}{dx}+B(x)Y.$ By definition of the $p$-curvature,
$\Delta^{p}$ is the multiplication by $B_{p}(x)$.

Now consider the endomorphism $\Delta^{\text{\rm dp}}$ of $M^{\text{\rm
dp}}=\mathbb{F}_{p}[[x]]^{\text{\rm dp}}\otimes_{\mathbb{F}_{p}[x]}M$ defined
by

$\Delta^{\text{\rm dp}}=\frac{d}{dx}\otimes\text{\rm
id}_{M}+1\otimes\Delta_{M}.$

One checks that it satisfies the Leibniz rule: for
$f\in\mathbb{F}_{p}[[x]]^{\text{\rm dp}}$ and $m\in M$, we have

$\Delta^{\text{\rm dp}}(f\otimes m)=\frac{df}{dx}\otimes m+f\otimes\Delta(m).$

Hence, raising it to the $p$-th power, we obtain

$(\Delta^{\text{\rm dp}})^{p}(Y^{\text{\rm dp}})=\frac{d^{p}Y^{\text{\rm
dp}}}{dx^{p}}+B_{p}^{\text{\rm dp}}(x)\cdot Y^{\text{\rm dp}}$

for all vector $Y^{\text{\rm dp}}\in M^{\text{\rm dp}}$. The equality of the
lemma follows given that the columns of $S^{\text{\rm dp}}(x)$ maps to $0$
under $\Delta^{\text{\rm dp}}$. ∎

####  3.3.3 Application to algorithmics

Given that the matrix $S^{\text{\rm dp}}(x)$ is invertible, it follows from
Lemma 3.27 that one can deduce the value of $B_{p}^{\text{\rm dp}}(x)$ from
that of $S^{\text{\rm dp}}(x)$ which, in turn, can be computed using the
techniques of [15]. However, at this point, we have not solved entirely the
question of the computation of the $p$-curvature because the knowledge of
$B_{p}^{\text{\rm dp}}(x)$ is not enough to recover $B_{p}$. Precisely,
letting $\mathbb{F}_{p}(x)_{0}$ denote the subring of $\mathbb{F}_{p}(x)$
consisting of functions with no pole at $0$, the natural map
$\delta_{0}:\mathbb{F}_{p}(x)_{0}\to\mathbb{F}_{p}[[x]]^{\text{\rm dp}}$ is
not injective; its kernel is the ideal generated by $x^{p}$.

To tackle this issue, the idea is shift around any other base point
$a\in\mathbb{F}_{p}$. Doing so, we get a new differential ring homomorphism
$\delta_{a}:\mathbb{F}_{p}(x)_{a}\to k[[x{-}a]]^{\text{\rm dp}}$ and, reusing
the same techniques, we end up with a fast algorithm that computes the
$p$-curvature $B_{p}$ modulo $(x{-}a)^{p}$. Since we have moreover at our
disposal _a priori_ bounds on the size of the $p$-curvature (see Proposition
3.26), one can pick enough elements $a$ in $\mathbb{F}_{p}$ (or in a finite
extension of $\mathbb{F}_{p}$, if needed), compute the $p$-curvature modulo
$(x{-}a)^{p}$ for all those points $a$ and reconstruct the complete matrix
$B_{p}(x)$ using the Chinese Remainder Theorem. Implementing this strategy, we
end up with the following theorem.

######  Theorem 3.28 (Bostan–Caruso–Schost [13]).

There exists an algorithm that takes as input a differential operator

$\mathscr{L}=\partial_{x}^{n}+b_{n-1}(x){\cdot}\partial_{x}^{n-1}+\cdots+b_{1}(x){\cdot}\partial_{x}+b_{0}(x)$

over $\mathbb{F}_{p}(x)$ and outputs its $p$-curvature for a cost of
$O^{\sim}(dn^{\omega}p)$ operations in $\mathbb{F}_{p}$ with

$d=\max\big{(}\deg
f(x),\,\deg(f(x)b_{0}(x)),\,\ldots,\,\deg(f(x)b_{n-1}(x))\big{)}$

where $f(x)$ is a common denominator of the $b_{i}(x)$’s.

Before commenting on the above result, we need to explain some notation.
Firstly, the notation $O^{\sim}(-)$ means that we are hiding logarithmic
factors. Secondly, the exponent $\omega$ refers to what we usually call a
_feasible_ exponent for the matrix multiplication. It simply means that we
suppose that we are given an algorithm that computes the product of two square
matrices of size $n$ with at most $O(n^{\omega})$ operations in the base
field. The naive method for multiplying matrices (the one we have all learnt
in our first course of linear algebra) indicates that we can take $\omega=3$.
However, it turns out that better algorithms exist. For example, Strassen’s
algorithm [66] results in $\omega=\log_{2}7\approx 2.8$. Nowadays, the best
known value for $\omega$ is about $2.37188$ and the corresponding algorithm is
due to Duan, Wu and Zhou [33]. It is a widely open conjecture if one can take
$\omega=2+\varepsilon$ for all $\varepsilon>0$.

The announced complexity $O^{\sim}(dn^{\omega}p)$ should be compared to the
size of the output, _i.e._ the number of scalars in $\mathbb{F}_{p}$ needed to
write down completely the $p$-curvature. By Proposition 3.26, $B_{p}$ if an
$n\times n$ matrix whose entries are rational functions with numerators and
denominators of degree at most $dp$; in practice, this bound is in general
sharp. Therefore, the size of the output is about $dn^{2}p$. As a consequence,
the algorithm behind Theorem 3.28 would be quasi-optimal (_i.e._ optimal up to
constant and logarithmic factors) if $\omega$ were equal to $2$. Even if this
limit cannot be attained, this comparison underlines the good performances of
the algorithm. In practice, using it makes it possible to compute
$p$-curvatures of operators of order and degree $20$ in a few seconds when
$p<100$ and in about half an hour when $p=12007$.

####  3.3.4 Similarity class and characteristic polynomial

We have seen previously (after Proposition 3.26) that, although the size of
the $p$-curvature grows linearly with respect to $p$, its characteristic
polynomial has roughly the same size as the input operator $\mathscr{L}$ even
when $p$ gets large. For this reason, one might hope to be able to compute the
characteristic polynomial faster than the $p$-curvature itself.

The main observation for achieving this is a refinement of Lemma 3.27 which
asserts that $B_{p}^{\text{\rm dp}}(x)=B_{p}(x)\text{ mod }x^{p}$ is not only
equal to

$-(S^{\text{\rm dp}}(x))^{-1}\cdot\frac{d^{p}S^{\text{\rm dp}}(x)}{dx^{p}}$

but it is further _similar_ to the value at $x=0$ (_i.e._ the reduction modulo
$x$) of the latter product. On the other hand, evaluating this reduction can
be done with standard algorithmic techniques (based on a so-called “baby step
/ giant step” approach) in time proportional to $\sqrt{p}$. Based on this, we
obtain the next theorem.

######  Theorem 3.29 (Bostan–Caruso–Schost [14]).

There exists an algorithm that takes as input a differential operator

$\mathscr{L}=\partial_{x}^{n}+b_{n-1}(x){\cdot}\partial_{x}^{n-1}+\cdots+b_{1}(x){\cdot}\partial_{x}+b_{0}(x)$

over $\mathbb{F}_{p}(x)$ and outputs the invariant factors of its
$p$-curvature for a cost of

$O^{\sim}\big{(}d^{\omega+\frac{3}{2}}n^{\omega+1}\sqrt{p}\big{)}$

operations in $\mathbb{F}_{p}$ where $d$ is defined as in Theorem 3.28.

We notice that the knowledge of the invariant factors is finer than that of
the characteristic polynomial since the latter is the product of the formers.
Furthermore, knowing the invariant factors, one can decide whether the
$p$-curvature vanishes or not, whereas the characteristic polynomial only
gives information about its nilpotency.

On the complexity side, we notice that the cost of the algorithm of Theorem
3.29 is worse with respect to the parameters $d$ and $n$ but better with
respect to $p$. It is then interesting for small operators but large
characteristic.

Finally, we mention that, if we are only interested by the characteristic
polynomial of the $p$-curvature, faster algorithms (based on different
techniques) exist.

######  Theorem 3.30 (Bostan–Caruso–Schost [12]).

There exists an algorithm that takes as input a differential operator

$\mathscr{L}=\partial_{x}^{n}+b_{n-1}(x){\cdot}\partial_{x}^{n-1}+\cdots+b_{1}(x){\cdot}\partial_{x}+b_{0}(x)$

over $\mathbb{F}_{p}(x)$ and outputs the characteristic polynomial of its
$p$-curvature for a cost of

$O^{\sim}\big{(}(d{+}n)^{\omega}\min(d,n)\sqrt{p}+(d{+}n)^{\omega+1}\min(d,n)\big{)}$

operations in $\mathbb{F}_{p}$ where $d$ is defined as in Theorem 3.28.

In practice, this algorithm performs quite well and allows for computing the
characteristic polynomial in less than one hour for the parameters $d=n=20$
and $p=120\>011$.

Recently, Pagès proved an “average version” of this theorem which, roughly
speaking, states that, starting with a differential operator over
$\mathbb{Q}(x)$, one can compute all its $p$-curvatures (up to some given
bound) in average time proportional to $\log p$.

######  Theorem 3.31 (Pagès [57]).

There exists an algorithm that takes as input a differential operator

$\mathscr{L}=b_{n}(x)\partial_{x}^{n}+b_{n-1}(x){\cdot}\partial_{x}^{n-1}+\cdots+b_{1}(x){\cdot}\partial_{x}+b_{0}(x)$

with $b_{i}(x)\in\mathbb{Z}[x]$ and outputs the characteristic polynomial of
all the $p$-curvatures of $\mathscr{L}\text{ mod }p$ for $p\leq N$ for a cost
of

$O^{\sim}\big{(}\big{(}(d{+}n)^{\omega}(d{+}m)+(d{+}n)^{3}\big{)}\cdot
Nd\big{)}$

operations on bits where $d$ is the maximal degree of the $b_{i}(x)$’s and $m$
is the maximal bitsize of an integer appearing as the coefficient of one of
the $b_{i}(x)$’s.

###  3.4 Algebraicity and integrality

The theoretical developments we carried out in §3.3.2 have also interesting
consequences in characteristic $0$. Let

$\mathscr{L}=\partial_{x}^{n}+b_{n-1}(x){\cdot}\partial_{x}^{n-1}+\cdots+b_{1}(x){\cdot}\partial_{x}+b_{0}(x)$

be a differential operator over $\mathbb{Q}(x)$ and set:

$S(x)=\sum_{k=0}^{\infty}(-1)^{k}B_{k}(x)\cdot\frac{x^{k}}{k!}$ (26)

where the $B_{k}(x)$’s are defined, as previously, by Equation (24). The
matrix $S(x)$ has entries in $\mathbb{Q}[[x]]$ and we write
$S(x)=\sum_{i=0}^{\infty}S_{i}x^{i}$ where the $S_{i}$ are matrices over
$\mathbb{Q}$. We emphasize that $S_{i}$ is _not_ equal to
$\frac{(-1)^{i}}{i!}B_{i}(x)$ because the latter has in general coefficients
in $\mathbb{Q}(x)$.

####  3.4.1 Growth of denominators and $p$-curvatures

We would like to reduce everything modulo a prime number $p$ in order to
compare $S(x)$ with the matrix $S^{\text{\rm dp}}(x)$ we have studied earlier;
however, this operation requires some care because the $B_{k}(x)$’s may
exhibit denominators. In order to do it properly, we introduce new rings. For
any subring $R\subset\mathbb{Q}$, we set:

$\displaystyle R(x)$ $\displaystyle=\left\\{\,\frac{P}{Q}\quad\text{with}\quad
P,Q\in R[x]\text{ and }Q\text{ monic}\,\right\\},$ $\displaystyle R(x)_{0}$
$\displaystyle=\left\\{\,\frac{P}{Q}\quad\text{with}\quad P,Q\in
R[x],\,Q\text{ monic}\text{ and }Q(0)\neq 0\,\right\\},$ $\displaystyle
R[[x]]^{\text{\rm dp}}$
$\displaystyle=\left\\{\,\sum_{i=0}^{\infty}a_{i}\>\frac{x^{i}}{i!}\quad\text{with}\quad
a_{i}\in R\text{ for all }i\,\right\\}.$

One has the following chain of inclusions $R[x]\subset R(x)_{0}\subset R(x)$
together with an injective morphism of rings $R(x)_{0}\hookrightarrow R[[x]]$.
Besides, all these maps commute with the derivation $\frac{d}{dx}$ and, if $p$
is a prime number which is noninvertible in $R$, they are compatible with the
reduction modulo $p$; in particular, we have the following commutative
diagram:

$\textstyle{R(x)_{0}\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\,\text{\rm
mod}\,p}$$\textstyle{R[[x]]\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\,\text{\rm
mod}\,p}$$\textstyle{R[[x]]^{\text{\rm
dp}}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\scriptstyle{\,\text{\rm
mod}\,p}$$\textstyle{\mathbb{F}_{p}(x)_{0}\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\mathbb{F}_{p}[[x]]\ignorespaces\ignorespaces\ignorespaces\ignorespaces}$$\textstyle{\mathbb{F}_{p}[[x]]^{\text{\rm
dp}}}$

where all the arrows are homomorphisms of rings and commute with the
derivation. We now assume that the entries of $B(x)$ have no pole at $0$ and
choose $R$ in such a way that they all belong to $R(x)_{0}$ (one can always
take $R=\mathbb{Z}[\frac{1}{D}]$ for $D$ large enough). All the $B_{m}(x)$’s
then assume coefficients in $R(x)_{0}$ as well and the matrix $S(x)$ is
defined over $R[[x]]^{\text{\rm dp}}$. Besides, the image of $S(x)$ modulo $p$
is the matrix $S^{\text{\rm dp}}(x)$ modulo $p$ associated to the differential
system $Y^{\prime}+(B(x)\,\text{\rm mod}\,p)\cdot Y=0$ in characteristic $p$.
Lemma 3.27 then lefts us with the congruence:

$S_{p}\equiv\frac{B_{p}(x)}{p!}\pmod{x},\quad\text{i.e.}\quad
S_{p}=\frac{B_{p}(0)}{p!}.$ (27)

Hence the $p$-curvatures (which, we recall, are the matrices
$B_{p}(x)\,\text{\rm mod}\,p$) are directly related to the coefficients
appearing in a fundamental system of solutions. In particular, the vanishing
of $B_{p}(0)$ modulo $p$ is equivalent to the fact that the denominator of
$S_{p}$ is coprime with $p$. Many variations on this theme are possible; a
beautiful example is given by the next theorem.

######  Theorem 3.32 (see Proposition 5.3.3 in [4]).

Let

$\mathscr{L}=\partial_{x}^{n}+b_{n-1}(x){\cdot}\partial_{x}^{n-1}+\cdots+b_{1}(x){\cdot}\partial_{x}+b_{0}(x)$

be a differential operator over $\mathbb{Q}(x)$ and $D$ be a positive integer.
We assume that $\mathscr{L}$ admits $n$ solutions $Y_{1},\ldots,Y_{r}$ which
have coordinates in $\mathbb{Z}[\frac{1}{D}][[x]]$ and are linearly
independent over $\mathbb{Q}$. Then almost all the $p$-curvatures of
$\mathscr{L}$ vanish.

######  Remark 3.33.

Under Grothendieck conjecture, Theorem 3.32 can be elegantly rephrased as
follows: if a differential system admits a basis of solutions in
$\mathbb{Z}[\frac{1}{D}][[x]]$ for some positive integer $D$ (_i.e._ , a basis
of _globally bounded_ solutions), then it also admits a basis of algebraic
solutions. This is known as _Bézivin’s conjecture_ ; it was formulated by
Bézivin in [9, p. 299] and proved by him for $q$-differential equations [9,
Thm. 7-1]. It is widely open whether Bézivin’s conjecture is more difficult
than Grothendieck’s conjecture; at any rate, it appears that for the time
being the only cases for which Bézivin’s conjecture is proven are those for
which Grothendieck’s conjecture is known to be true.

######  Example 3.34.

We illustrate Theorem 3.32 with the differential equation

$y^{\prime}=\frac{1}{x^{2}+1}y$

already considered in Example 3.4. Over the rationals, the solutions are all
proportional to the fundamental solution

$y_{0}(x)=\exp(\arctan(x))=\sum_{n=0}^{\infty}c_{n}x^{n}$

where the $c_{n}$’s are rational numbers. We would like to find bounds on
denominators of the $c_{n}$’s. More precisely, we fix a prime number $p\neq 2$
(for simplicity) and ask whether the denominators of the $c_{n}$’s are all
coprime with $p$. For this, we use Dwork’s criterion (see for instance [61, p.
409]) which asserts that the previous property holds if and only if

$\arctan(x^{p})-p\cdot\arctan(x)\in p\mathbb{Z}_{(p)}[[x]]$

where we recall that $\mathbb{Z}_{(p)}$ is the subring of $\mathbb{Q}$
consisting of fractions $\frac{a}{b}$ with $b$ coprime with $p$. We have:

$\arctan(x^{p})-p\cdot\arctan(x)=\sum_{n=0}^{\infty}\frac{(-1)^{n}}{2n+1}x^{(2n+1)p}-p\cdot\sum_{n=0}^{\infty}\frac{(-1)^{n}}{2n+1}x^{(2n+1)}.$
(28)

Clearly, when $2n+1$ is coprime with $p$, the coefficient
$p\cdot\frac{(-1)^{n}}{2n+1}$ is divisible by $p$. Therefore, we can only
retain in the second sum of Eq. (28) the terms for which $2n\equiv-1\pmod{p}$,
_i.e._ $2n=p-1+2\ell p$ with $\ell\in\mathbb{N}$. We thus get:

$\displaystyle\arctan(x^{p})-p\cdot\arctan(x)$
$\displaystyle\equiv\sum_{n=0}^{\infty}\frac{(-1)^{n}}{2n+1}x^{(2n+1)p}-\sum_{\ell=0}^{\infty}\frac{(-1)^{\ell-\frac{p-1}{2}}}{2\ell+1}x^{(2\ell+1)p}$
$\displaystyle=\sum_{n=0}^{\infty}\frac{(-1)^{n}}{2n+1}\cdot\left(1-(-1)^{\frac{p-1}{2}}\right)\cdot
x^{(2n+1)p}\pmod{p\mathbb{Z}_{(p)}[[x]]},$

hence $\arctan(x^{p})-p\cdot\arctan(x)$ is divisible by $p$ when $p\equiv
1\,\text{\rm mod}\,4$ and is not otherwise. In conclusion, the denominators of
the $c_{n}$’s are all coprime with $p$ (that is, $\exp(\arctan(x))$ can be
reduced modulo $p$) if and only if $p\equiv 1\,\text{\rm mod}\,4$.

######  Remark 3.35.

Note that the sequence $(T_{n})_{n\geq 0}$ defined by $T_{n}=n!\cdot c_{n}$,
satisfies the linear recurrence $T_{n+2}=T_{n+1}-n(n+1)T_{n}$ with
$T_{0}=T_{1}=1$, hence its terms are all integer numbers. Kelinsky proved in
[50, Thm. 3] that for any prime $p\neq 2$, the term $T_{p}$ is congruent to
$0$ modulo $p$ if $p\equiv 1\,\text{\rm mod}\,4$ (and to $2$ if $p\equiv
3\,\text{\rm mod}\,4$). The computation in 3.34 shows that a much stronger
property holds: if $p\equiv 1\,\text{\rm mod}\,4$, then $T_{n}$ is congruent
to $0$ modulo $p$ for all $n\geq p$, in other terms the generating function
$\sum_{n\geq 0}T_{n}x^{n}$ is a _polynomial_ modulo $p$.

In the same orbit, we mention two other theorems which are not directly
related to our discussion but highlights other intricate relations between
algebraicity and integrality.

######  Theorem 3.36 (Conjectured by Ogus [56], proved by André [3]).

Let $f(x)\in\mathbb{Z}[[x]]$ such that $f^{\prime}(x)$ is algebraic over
$\mathbb{Q}(x)$. Then $f(x)$ is algebraic over $\mathbb{Q}(x)$.

######  Theorem 3.37 (Conjectured by Katz [45], proved by the
Chudnovsky–Chudnovsky [30]).

Let $f(x)\in\mathbb{Z}[[x]]$ such that $f^{\prime}(x)/f(x)$ is algebraic over
$\mathbb{Q}(x)$. Then $f(x)$ is algebraic over $\mathbb{Q}(x)$.

####  3.4.2 An analytic perspective on the $p$-curvature

All what precedes indicates that the vanishing properties of the
$p$-curvatures tend to control the growth of the denominators of the
coefficients of the fundamental system of solutions $S(x)$. Typically, after
Eq. (27), we have seen that $B_{p}(0)\equiv 0\pmod{p}$ is equivalent to the