A SHARPER MULTIVARIATE CHRISTOL’S THEOREM WITH
APPLICATIONS TO DIAGONALS AND HADAMARD PRODUCTS
BORIS ADAMCZEWSKI, ALIN BOSTAN, AND XAVIER CARUSOA BSTRACT. We provide a new proof of the multivariate version of Christol’s
theorem about algebraic power series with coefficients in finite fields, aswell as of its extension to perfect ground fields of positive characteristic
obtained independently by Denef and Lipshitz, Sharif and Woodcock, andHarase. Our proof is elementary, effective, and allows for much sharper
estimates. We discuss various applications of such estimates, in particular
to a problem raised by Deligne concerning the algebraicity degree of
reductions modulo p of diagonals of multivariate algebraic power series
with integer coefficients.

1. I NTRODUCTION
Rational and algebraic power series play an important role in various
areas of mathematics, and especially in number theory and combinatorics.
There are two fundamental results concerning rationality of power series in
one variable.
The first one is that, given an arbitrary field k, a power seriesPn ∈ k[[t]] is rational if and only if its coefficient sequencef (t) = ∞a(n)tn=0a(n) satisfies a linear recurrence with coefficients in k. The second one is
the famous Skolem-Mahler-Lech theorem stating that, when k is a field of
characteristic zero, the zero set
Z(f ) := {n ∈ N : a(n) = 0}of a rational power series f ∈ k[[t]] is a periodic set, that is the unionof a finite set and of finitely many arithmetic progressions. When k has
characteristic zero, it seems difficult to obtain similar results for algebraic
power series, i.e. power series f ∈ k[[t]] for which there exists a nonzero
bivariate polynomial P ∈ k[t, y] such that P (t, f ) = 0. Although it is known
that the coefficient sequences of univariate algebraic power series do satisfy
linear recurrences with polynomial coefficients, a characterization of suchsequences is still lacking. On the other hand, proving that the corresponding
zero sets are periodic remains a challenging open problem (cf. [Zan09, p.
176]). The situation in several variables is worse and not much is known or
Key words and phrases. Christol’s theorem; automatic sequences; algebraic power series;
diagonals; Hadamard products.
Partially supported by the French grant DeRerumNatura (ANR-19-CE40-0018), and by the
French–Austrian project EAGLES (ANR-22-CE91-0007 & FWF I6130-N).
1

2

BORIS ADAMCZEWSKI, ALIN BOSTAN, AND XAVIER CARUSO

even conjectured about zero sets of multivariate rational power series; this isvery unfortunate, as they encode interesting Diophantine problems.
In a short but influential paper, Furstenberg [Fur67] observed for the firsttime that algebraic power series over ground fields of positive characteristic
have a very particular structure. For instance, when k = Fq is a finite field, heproved that the ringof algebraic power series is closed under the HadamardP∞nproductandthat
n=0 a(n)t ∈ Fq [[t]] is algebraic over Fq (t) if and only ifPnn:a(n)=a t is algebraic for every a ∈ Fq ; these two properties do not holdin characteristic zero. Later, Christol [Chr79] elaborated on Furstenberg’s
approach and proved the following beautiful result.
PnTheorem A (Christol). A power series ∞n=0 a(n)t ∈ Fq [[t]] is algebraic overFq (t) if and only if its coefficient sequence a(n) can be generated by a finite
q-automaton.
We refer the reader to [AS03, Chapters 4 and 5] for the notions of finite
automata and automatic sequences. A different proof of Christol’s theorem
was given in [CKMFR80], from which Salon [Sal87, Sal86] also derived
a natural extension to multivariate power series. What makes Christol’s
theorem deep and fascinating is that it establishes an intimate connection
between two important objects coming from seemingly unrelated areas.
When the ground field k is an arbitrary field of positive characteristic,
the characterization of algebraic power series in terms of finite automata
is somewhat lost but there are still important related results. Furstenberg[Fur67] proved that the diagonal of a multivariate rational power series
remains algebraic; this result was generalized by Deligne [Del84] to diagonals of multivariate algebraic power series. A related result is that thering of multivariate algebraic power series is closed under the Hadamard
product (cf. [DL87, SW88, Har88]). More recently, Derksen [Der07] found
an appropriate version of the Skolem-Mahler-Lech theorem involving finite
automata. Derksen’s theorem was then generalized to zero sets of arbitrary
multivariate algebraic power series by Adamczewski and Bell [AB12].
It turns out that all the previously mentioned results (in positive characteristic) can be proved by using some splitting process associated with the Frobenius map (cf. Equality (1.1)). Let k be a perfect field of characteristic p > 0.
Then the Frobenius endomorphism F, that maps x to xp , is an automorphismof k. Let t = (t1 , . . . , tn ) be indeterminates, and let K denote the field of fractions of the ring of power series k[[t]] := k[[t1 , . . . , tn ]]. The Frobenius map F
extends naturally to K as an injective homomorphism. We let K hpi denotethe image of K by F, so that F defines an isomorphism between K and K hpi .
Then K is a K hpi -vector space of dimension pn , a basis being given by all the
products of the form tr := tr11 · · · trnn , with r := (r1 , . . . , rn ) ∈ {0, . . . , p − 1}n .
Thus, every f ∈ K has a unique expansion of the form
X
(1.1)
f=
tr fr .
r∈{0,...,p−1}nA SHARPER MULTIVARIATE CHRISTOL’S THEOREM

3

For every r ∈ {0, . . . , p − 1}n , the section operator Sr is defined by
Sr (f ) := F−1 (fr ) .

(1.2)

SectionP operators are semilinear maps from K into itself. For a power series
f := i∈Nn a(i)ti ∈ k[[t]], we haveXa(pi1 + r1 , . . . , pin + rn )1/p ti ∈ k[[t]]] .
Sr (f ) =i∈Nni=(i1 ,...,in )We let Ωn denote the monoid generated by all section operators undercomposition.
At the end of the 1980s, Denef and Lipshitz [DL87], Sharif and Woodcock[SW88] and Harase [Har88] obtained independently the following nicecharacterization of multivariate algebraic power series in terms of section
operators.
Theorem B. Let k be a perfect field of characteristic p. A power seriesf ∈ k[[t]] is algebraic over k(t) if and only if there exists a finite-dimensional
k-vector space W ⊂ K containing f and invariant under the action of Ωn .
Remark 1.1. When k = Fq , the putative vector space W has to be finite andits existence is thus equivalent to the finiteness of the orbit of f under Ωn .
By a classical result of Eilenberg, the latter property is itself equivalent to
the fact that the coefficient sequence of f is q-automatic, so one recovers themultivariate extension of Christol’s theorem.
In this paper, we investigate the problem of finding a sharp quantitative
version of Theorem B, i.e. finding a k-vector space W having the smallest
possible dimension in terms of the “complexity” of the algebraic power
series f .
The particular case of multivariate rational power series can be treated ina satisfactory way. Indeed, if f (t) = A(t)/B(t) ∈ k[[t]] for some A, B ∈ k[t],whose degree in ti is at most hi , then it is easy to prove that the k-vector
space


P (t)
W :=
: P ∈ k[t], degti P ≤ hi , 1 ≤ i ≤ nB(t)contains f and is invariant under Ωn . Similarly, if the total degree of both A
and B is at most h, then the same conclusion applies to


P (t)
0
W :=
: P ∈ k[t], degt P ≤ h .
B(t)Furthermore, W and W 0 have dimensions (h1 + 1) · · · (hn + 1) and n+hn ,respectively.
On the other hand, the case of algebraic irrational multivariate power
series is known to be more difficult and the known estimates are much
weaker. To summarize roughly, the main aim of this paper is to develop aunified method, which is able to deal with arbitrary multivariate algebraic

4

BORIS ADAMCZEWSKI, ALIN BOSTAN, AND XAVIER CARUSO

power series as if they were rational. In this direction, our main results are
Theorem 1.2 and Corollary 1.4. The proof of Theorem 1.2 follows a new
approach recently initiated in [BCCD19] for the case n = 1. Its main featureis that it combines all the advantages of the different methods used so far
to study (part of) this problem (cf. [Chr79, CKMFR80, Sal86, Sal87, DL87,
SW88, Har88, Har89, AB12, AB13, Bri17, AY19]). Indeed, our method iselementary, as general as possible in the sense that it applies to arbitrary
multivariate algebraic power series over arbitrary fields of characteristic p,
and it provides much sharper quantitative estimates. The methods used todate are briefly discussed in Section 1.3.
1.1. Statement of our main result. The “complexity” of an algebraic power
series f ∈ k[[t]] is classically measured by its degree and its height. The degreeof f is the minimal degree in y of a nonzero polynomial A(t, y) ∈ k[t, y] suchthat A(t, f ) = 0. It is also equal to [k(t)(f ) : k(t)], the degree of the field
extension k(t)(f ) of k(t). For the height, we have two natural choices, since
we can consider either the partial height or the total height. We say that f
has partial height h = (h1 , . . . , hn ) if, for all i, hi is the minimal degree inti of a nonzero polynomial A(t, y) ∈ k[t, y] such that A(t, f ) = 0, while thetotal height of f is the minimal total degree in t of such polynomials A(t, y).
In fact, a finer way to measure the complexity of multivariate polynomials,
and hence of algebraic power series, is to consider their Newton polytopes.
We recall that the Newton polytope (or, Newton polyhedron) NP(A) of amultivariate polynomialXA :=ai,j ti y j ∈ k[t, y]
i∈Nn
j∈N

is defined as the convex hull in Rn+1 of the tuples (i, j) with ai,j 6= 0.
An important result is that, for a generic polynomial A, the number ofinteger points in the interior of NP(A) is equal to the (geometric) genusof the hypersurface associated with A. This has been proved by Baker forplane curves [Bak93], by Hodge for surfaces [Hod29] and by Khovanskii for
arbitrary hypersurfaces [Hov78]. As a result, Theorem 1.2 has a geometricflavor, as does the result obtained by Bridy [Bri17] in the case where k is a
finite field and n = 1 (cf. Section 4 for more details).
Keeping the previous notation, our main result reads as follows.
Theorem 1.2. Let k be a perfect field of characteristic p. Let A(t, y) be anonzero polynomial in k[t, y] and let f ∈ k[[t]] satisfy the algebraic relation
A(t, f ) = 0. Set
C := NP(A) + (−1, 0]n+1 .
Then there exists a k-vector space W ⊂ K of dimension at mostCard(C ∩ Nn+1 )that contains f and that is closed under the action of Ωn .

A SHARPER MULTIVARIATE CHRISTOL’S THEOREM

5Remark 1.3. The plus sign in the definition of C refers to the Minkowski sum.
In Theorems B and 1.2, the field k must be perfect for the section operators
to be well-defined, but this is not a real limitation. Indeed, replacing an
arbitrary field of characteristic p by its perfect closure does not affect our
results (cf. Section 3).
When measuring complexity of algebraic power series in terms of degreeand height, our main result can be translated as follows.
Corollary 1.4. We keep the notation of Theorem 1.2. Let us further assume
that degy (A) ≤ d, degt (A) ≤ h, and degti (A) ≤ hi for all 1 ≤ i ≤ n. Then,
there exists a k-vector space W ⊂ K of dimension at most
( n

)
Y
n+h
N := (d + 1) · min(hi + 1),ni=1that contains f and that is closed under the action of Ωn .
Remark 1.5. In the rest of the paper, we express our results mostly in termsof degree and height rather than in terms of Newton polytopes, which leads
to somewhat less precise bounds (compare, for instance, Theorem 1.2 andCorollary 1.4). This is the case for Theorems 4.1, 5.2, 6.1 and 6.3. The
reason for this choice is that we think it could be more meaningful for somereaders. However, there is no difficulty in deducing from our arguments andTheorem 1.2 more precise results involving Newton polytopes.
1.2. Motivation. Theorem 1.2 is motivated by various applications, in particular to the four following problems:(i) Given an algebraic power seriesXf (t) :=
a(i)ti ∈ Fq [[t]] ,i∈Nnfind upper bounds for the minimal number of states required for a
q-automaton in order to generate the sequence (a(i))i∈Nn .
(ii) Given an algebraic power seriesXf (t) :=
a(i)ti ∈ Z[[t]] ,i∈Nnfind upper bounds for the degree of algebraicity over Fp (t) of the
reduction modulo p of the diagonal of f , that is∆(f )|p :=∞X(a(i, . . . , i) mod p)ti ∈ Fp [[t]] .

i=0(iii) Given two multivariate algebraic power series over an arbitrary fieldof characteristic p, find upper bounds for the degree of algebraicityof their Hadamard product.

6

BORIS ADAMCZEWSKI, ALIN BOSTAN, AND XAVIER CARUSO(iv) Given an algebraic power seriesXf (t) :=
a(i)ti ∈ Fq [[t]]i∈Nn(encoded by its minimal polynomial over Fq (t) and a large enoughenclosure which guarantees uniqueness) and given a multi-indexi ∈ Nn , find fast algorithms to compute the coefficient a(i).
For each of them, our results strongly improve and/or generalize previously
known results (cf. Sections 4–7). For example, in connection with Problem(ii), we significantly improve the main upper bound obtained by Adamczewski and Bell [AB13] for the algebraicity degree of reductions modulo pof diagonals of algebraic power series with integer coefficients, thus fully
answering a question raised in 1984 by Deligne [Del84] (see Theorem 5.2).
1.3. Comparison of previous methods. There are essentially three different
approaches to prove results in the vein of Theorems A and 1.2. We briefly
recall them together with their main advantages and shortcomings.
(1) The most classical approach, initiated in [CKMFR80] and used in[Sal86, Sal87, DL87, SW88, Har88, Har89, AB12], is based on the fact thatalgebraic power series are roots of polynomials of a certain type called Ore
polynomials, i.e. they satisfy algebraic equations of the formda0 f + a1 f p + · · · + ad f p = 0 ,where a0 , . . . , ad ∈ k[t], not all zero. The main advantage of this approachis that it is elementary and general in the sense that it applies to arbitrary
multivariate algebraic power series over arbitrary fields of positive characteristic. Its main deficiency is that it provides poor bounds for the dimensionof the k-vector space W , namely bounds of the form pA , where A can bemade explicit and depends polynomially on the parameters d and h (or dand h1 , . . . , hn ), that is on the degree and the height of f .
(2) The second approach is based on the so-called rationalization process.
This means that one expresses the algebraic power series f as the diagonalof a rational function with more variables. Its main advantage is that itprovides bounds on the dimension of the k-vector space W that do notdepend on p. It is based on Furstenberg’s formula [Fur67, Proposition 2]
which is elementary. The main drawback is that Furstenberg’s formula only
applies to algebraic power series satisfying some specific polynomial relations.
For algebraic power series in one variable, one can overcome this difficulty
by using resultant techniques (see, for example, [AY19]). For multivariate
power series, one can use inductively these resultant methods as in [AB13],
but the worst case scenario leads to really huge bounds. The same approachis also used in [DL87], where the rationalization process is ensured by anonelementary and ineffective argument (cf. [AB13, Remark 3.1]).

A SHARPER MULTIVARIATE CHRISTOL’S THEOREM

7(3) The last approach consists in using a geometric setting, considering
the projective curve (or hypersurface) associated with the algebraic power
series f . It was used by Deligne [Del84] in order to reprove Furstenberg’s
theorem on diagonals, and more recently by Bridy [Bri17] to prove a strong
quantitative version of Christol’s theorem in dimension one. The main
advantage of the geometric approach is that it seems to provide tight bounds
for the dimension of the k-vector space W , which is indeed the case in[Bri17]. The main shortcomings of this method are that it is not elementary,since it requires tools from algebraic geometry, and that it does not seem towork as well in the multivariate setting.
1.4. Organization of the paper. Section 2 is devoted to the proof of Theorem 1.2. In Section 3, we prove a result ensuring that one can consider,without any loss in our bounds, algebraic power series over arbitrary groundfields of positive characteristic (instead of perfect fields as assumed in Theorem 1.2). This result is used in Sections 5 and 6. In Section 4, we discuss
Problem (i) and prove, in the multivariate setting, results similar to thoseobtained by Bridy [Bri17] for univariate algebraic power series. Section 5 isdevoted to Problem (ii). We consider diagonals of algebraic power series inseveral variables over arbitrary fields of characteristic p, and obtain a general upper bound for their algebraicity degree, which significantly improves
the main known result in this direction obtained by Adamczewski and Bell
[AB13]. In Section 6, we discuss Problem (iii). We obtain the first simply
exponential bound (with respect to the characteristic p of the ground field)
for the degree of algebraicity of the Hadamard product of two multivariate algebraic power series. We also prove a similar result for the Hurwitz
and the Lamperti products of two algebraic power series in one variable.
This considerably improves the doubly exponential bounds which follow
from [DL87, SW88, Har88] and that were made explicit by Harase [Har89].
Finally, in Section 7, we consider some algorithmic consequences of Theorem 1.2 to Problem (iv). In particular, we show that the M -th coefficient of
the diagonal of an algebraic power series f ∈ Fp [[t1 , . . . , tn ]] can be computed
using a number of operations in Fp which is logarithmic in M and almost
linear in pn+1 . Again, this improves significantly upon previously known
results.
Throughout the paper, we let N := {0, 1, . . .} denote the set of nonnegative
integers.
2. P ROOF OF T HEOREM 1.2
This section is devoted to the proof of our main result.
2.1. A variant of Furstenberg’s formula. Let K be a field and T be anindeterminate. The residue map res is defined from the field of Laurent series

8

BORIS ADAMCZEWSKI, ALIN BOSTAN, AND XAVIER CARUSO

K((T )) to K by setting
!
res

X

an T

n

:= a−1 .

n≥νGiven a polynomial A ∈ K[y], we let Ay denote its derivative with respect to y.
The following key lemma is a slight reformulation of [BCCD19, Lemma 2.3],
itself inspired by [Fur67, Proposition 2]. We provide a proof for the reader’sconvenience.
Lemma 2.1. Let K be a field, f ∈ K and A(y) ∈ K[y]. Assume that A(f ) = 0
and Ay (f ) 6= 0. Then
P (f )
P (f + T )=,res
A(f + T )Ay (f )
for all P ∈ K[y].
Proof. By assumption, the polynomial A(f + T ) ∈ K[T ] has a simple root at
T = 0. There thus exists a polynomial Q(T ) ∈ K[T ] such thatA(f + T ) = T · Q(T )and

Q(0) 6= 0 .

Taking the logarithmic derivative with respect to T yields the equality
Ay (f + T )1
Q0 (T )= +·A(f + T )T
Q(T )Setting g(T ) := P (f + T )/Ay (f + T ), we find that g belongs to K[[T ]], as
Ay (f + T ) does not vanish at T = 0. Furthermore, one has
P (f + T )g(T ) g(T )Q0 (T )=+·A(f + T )T
Q(T )Similarly, g(T )Q0 (T )/Q(T ) belongs to K[[T ]] since Q(0) 6= 0. It follows that
P (f + T )P (f )res= g(0) =,A(f + T )Ay (f )
as claimed.



2.2. Frobenius and section operators. Let k be a perfect field of characteristic p. We keep on with the notation introduced in Section 1. We let
F be the Frobenius map. We consider indeterminates t1 , . . . , tn and writet = (t1 , . . . , tn ). We set K0 := k(t), R := k[[t]] and K := Frac(R). For everyr ∈ {0, . . . , p − 1}n , the section operator Sr is the semilinear operator fromK into itself defined as in (1.2).

A SHARPER MULTIVARIATE CHRISTOL’S THEOREM

92.2.1. Section operators on K((T )). Let us consider a new indeterminate T .
Then F extends to an injective homomorphism from K((T )) into itself. We
let K((T ))hpi denote the image of K((T )) by F. As previously, K((T )) isa K((T ))hpi -vector space of dimension pn+1 , a basis being given by all the
products of the form tr T s with r ∈ {0, . . . , p − 1}n and 0 ≤ s ≤ p − 1.
However, it will be more convenient for our purpose to replace this standard
basis by a more appropriate one (depending on a given f ∈ R). We proceed
in the same way as in [BCCD19, Lemma 2.4].
Lemma 2.2. For any f ∈ R, the family
Bf := tr (f + T )s : r, s ∈ {0, . . . , p − 1}n+1
is a basis of K((T )) as a K((T ))hpi -vector space.
Proof. First, we observe that Bf is a generating family. Indeed, we can obtaintr T s as a linear combination of tr (f + T )i , 0 ≤ i ≤ s. To see this, it is enoughto invert the matrix


1
0
···
··· ··· 0f10· · · · · · 0
 2

f
2f
1
0 · · · 0


..
..
..
..  .
 ..
..
.
.
.
.
.
.


..
..
..
.. 
 ..
..
.
.
.
.
.
.
s(s−1) s−2
s
s−1
f sf
· · · sf 1
2 f
Since Bf has the same cardinality as the basis {tr T s : r, s ∈ {0, . . . , p−1}n+1 },it is also a basis of K((T )).
It follows that, given f ∈ R, every x ∈ K((T )) has a unique expansion of
the form
(2.1)

x=

X
r∈{0,...,p−1}np−1Xt(f + T )s xf,r,s ,r

s=0with xf,r,s ∈ K((T ))hpi . For every r ∈ {0, . . . , p − 1}n and s ∈ {0, . . . , p − 1},
we define the section operator Sf,r,s , from K((T )) into itself, by(2.2)

Sf,r,s (x) := F−1 (xf,r,s ) .

We observe that Sf,r,s (xy p ) = Sf,r,s (xF(y)) = Sf,r,s (x)y, for all x, y ∈K((T )), all r ∈ {0, . . . , p − 1}n , and all s ∈ {0, . . . , p − 1}.
2.2.2. Section operators and residues. The next result is the key observationof our proof. Roughly speaking, it shows some compatibility between taking
residues at f (t) and residues at 0. It corresponds to a multivariate extensionof [BCCD19, Proposition 2.5].

10

BORIS ADAMCZEWSKI, ALIN BOSTAN, AND XAVIER CARUSO

Proposition 2.3. For any f ∈ R and r ∈ {0, . . . , p−1}n , the following commutation relation holds over K((T )):Sr ◦ res = res ◦ Sf,r,p−1 .
Proof. Let x ∈ K((T )). By (2.1), we have
x=

X

tr

r∈{0,...,p−1}np−1X(f + T )s F(Sf,r,s (x)) .
s=0

Hence
res(x) =X
r∈{0,...,p−1}n

=

X

tr

p−1
X



res (f + T )s F(Sf,r,s (x))

s=0tr F res Sf,r,p−1 (x) .

r∈{0,...,p−1}nBy (1.1) and (1.2), we obtainSr ◦ res(x) = res ◦ Sf,r,p−1 (x) ,as wanted.



2.3. Proof of Theorem 1.2. We keep on with the previous notation and thenotation of Section 1. Let E(t, y) ∈ k[t, y] denote the minimal polynomial off over k(t), normalized so that its coefficients are globally coprime.
Lemma 2.4. The power series f is a simple root of E(t, y).
Proof. It is enough to show that E(t, y) is separable with respect to thevariable y. Since it is defined as a minimal polynomial, this further reduces toprove that E(t, y) is not of the form F (t, y p ) for some polynomial F (t, z) ∈k[t, z]. We assume by contradiction that this occurs, and we write
F (t, z) = a0 (t) + a1 (t)z + · · · + am (t)z m
with ai (t) ∈ k[t] and am (t) 6= 0. Let r ∈ {0, . . . , p−1}n . Applying the section
operator Sr to the identity F (t, f p ) = 0, we obtain
Sr a0 (t) + Sr a1 (t) f + · · · + Sr am (t) f m = 0 .
Moreover, since am (t) is nonzero, there must exist r for which Sr (am (t))
does not vanish either. For this particular r, we then get a polynomial
annihilating f with y-degree less than the y-degree of E. This contradicts
the minimality of E.
Let Ey be the partial derivative of E with respect to y. Lemma 2.4 ensuresthat Ey (t, f ) 6= 0. Besides, given that A annihilates f , it must be a multipleof E, i.e. we can write A = E · F for some polynomial F ∈ k[t, y]. Let J be
the interval (−1, 0] and set C 0 := NP(E) + J n+1 .

A SHARPER MULTIVARIATE CHRISTOL’S THEOREM

11

We claim that the k-vector space
P (t, f )0
W :=: P ∈ k[t, y], NP(P ) ⊂ C ⊂ K
Ey (t, f )contains f and is invariant under the action of Ωn . The fact that f ∈ W
follows from the observation that NP(yEy ) ⊂ NP(E) ⊂ C 0 . We now consider
a tuple r ∈ {0, 1, . . . , p−1}n together with a polynomial P ∈ k[t, y] whose
Newton polytope is a subset of C 0 . We set R := P · E p−1 and let Q ∈ k[t, y]
be defined by(2.3)

Q(t, f + T ) := Sf,r,p−1 (R(t, f + T )) ∈ K .

Combining Lemma 2.1 and Proposition 2.3, we obtain:P (t, f )P (t, f + T )Sr(2.4)= Sr ◦ res
Ey (t, f )E(t, f + T )
P (t, f + T )= res ◦ Sf,r,p−1
E(t, f + T )Q(t, f + T )= resE(t, f + T )Q(t, f )=·Ey (t, f )To establish our claim, it just remains to prove that NP(Q) ⊂ C 0 . We
recall the following standard fact about Newton polytopes. The formation of
Newton polytopes is compatible with products: given A, B ∈ k[t, y], we havethe relation
NP(AB) = NP(A) + NP(B).
From this property, we derive that
NP(R) ⊂ (p−1)·NP(E) + C 0 = p·NP(E) + J n+1 .
Let (i, j) be a tuple of exponents that belongs to the support of Q, i.e. forwhich the coefficient in Q in front of ti y j is nonzero. It follows from thedefinition of Sf,r,p−1 that (pi + r, pj + p − 1) must lie in NP(R). Dividing by
p and writing I := (− p1 , 0], we obtain that
i + p1 r, j + p−1∈ NP(E) + I n+1 ,pso that(i, j) ∈ NP(E) + I n+1 +no− p1 r, − p−1⊂ NP(E) + J n+1 = C 0 .
pFinally, we conclude that NP(Q) ⊂ C 0 , as wanted.
Clearly W is spanned by the fractions of the form ti f j /Ey (t, f ) with(i, j) ∈ C 0 ∩ Nn+1 . Hence its dimension is upper bounded by the cardinalityof this set. We observe moreover that C = NP(F ) + C 0 . Since F is nonzero,
its Newton polytope NP(F ) meets Nn+1 . Hence C contains a translate of

12

BORIS ADAMCZEWSKI, ALIN BOSTAN, AND XAVIER CARUSO

C 0 by an element with nonnegative integral coefficients. Consequently the
cardinality of C ∩ Nn+1 is at least that of C 0 ∩ Nn+1 , and we conclude that
dimk W ≤ Card(C 0 ∩ Nn+1 ) ≤ Card(C ∩ Nn+1 ) ,as wanted.
Remark 2.5. The proof above actually implies the following statement, which
is a little more precise than Theorem 1.2 and can be useful is some cases. Fora nonnegative integer m, let Jm be the interval (−1, −1+p−m ] and define:0:= NP(E) + (J0n × Jm ) ,CmP (t, f )0
Wm :=: P ∈ k[t, y], NP(P ) ⊂ Cm .
Ey (t, f )The Wm ’s form a nonincreasing sequence of k-vector spaces and the action ofΩn sends Wm to Wm+1 . In particular, it stabilizes the intersection of the Wm ’s.
However, it is not true that f belongs to Wm for all m: in full generality, it
only lies in W0 .
If we set Ω+
n ·f := {Sr 1 ◦ · · · ◦ Sr t (f ) : t ≥ 1}, we obtain that Ωn ·f =
,
while
Ω+
{f } ∪ Ω+·f
n ·f is contained in W1 , which can be strictly smallernthan W0 . For example, if we assume that degy (A) ≤ d, degt (A) ≤ h, anddegti (A) ≤ hi for all 1 ≤ i ≤ n, then
( n

)
Y
n+h
dimk W0 ≤ (d + 1) · min(hi + 1),,ni=1whereasdimk W1 ≤ d · min

( n
Y
i=1

)
n+h
(hi + 1),.
n

3. F ROM PERFECT TO ARBITRARY FIELDS OF POSITIVE CHARACTERISTICIn Theorem 1.2, the ground field k must be perfect for the section operators
to be well-defined. If k is not perfect, one can always replace k by its perfectclosure and then apply Theorem 1.2. In this section, we prove a result which
ensures that passing to the perfect closure does not affect the bounds weobtain in Sections 5 and 6.
Recall that if k is an arbitrary field of characteristic p, then adjoining to k
all the pr -th roots (r ≥ 1) of all the elements of k yields a perfect field; it iscalled the perfect closure of k and we will denote it by kp .
Proposition 3.1. Let k be an arbitrary field of characteristic p and let kp be its
perfect closure. Let f ∈ k[[t]] be algebraic over k(t). Then, [k(t)(f ) : k(t)] =[kp (t)(f ) : kp (t)].
Proposition 3.1 is a direct consequence of the following lemma.

A SHARPER MULTIVARIATE CHRISTOL’S THEOREM

13

Lemma 3.2. Let k0 be a field, k1 be an extension of k0 , t = (t1 , . . . , tn ) be
indeterminates, and f1 (t), . . . , fr (t) ∈ k0 [[t]]. If the power series f1 , . . . , fr are
linearly dependent over the field k1 (t), then they are linearly dependent overthe field k0 (t).
Proof. By assumption, there exist polynomials Ai (t) ∈ k1 [t], not all zero, such
that
r
X
(3.1)
Ai (t)fi (t) = 0 .
i=1Set
Ai (t) :=X

bi,j tjj∈Sinwhere we let Si ⊂ N denote the support of Ai , andfi (t) :=X

ai,j tj ∈ k0 [[t]] .

j∈Nn

Let (e` )`∈L be a basis of k1 , seen as a k0 -vector space. Thus, there exist someci,j,` ∈ k0 such thatXbi,j :=
ci,j,` e` .
`∈L

Then, Equality 3.1 implies that for all k ∈ Nn , one has
r XXbi,j ai,k−j = 0 ,i=1 j∈Si

and hencer XXX

ci,j,` e` ai,k−j =i=1 j∈Si `∈L

X
`∈L



r X
X

ci,j,` ai,k−j  e` = 0 .
i=1 j∈Si

Since the e` ’s are linearly independent over k0 , we obtain
r X
X
(3.2)
ci,j,` ai,k−j = 0
i=1 j∈SiP
for all ` ∈ L and all k ∈ Nn . Setting Ai,` (t) := j∈Si ci,j,` tj ∈ k0 [t], Equality(3.2) implies that
r
X
(3.3)
Ai,` (t)fi (t) = 0, for all ` ∈ L .
i=1

Since the polynomials Ai are not all zero, the coefficients bi,j are not all
zero, and the same is also true for the coefficients ci,j,` . Hence, there exists
an index ` such that the polynomials Ai,` , 1 ≤ i ≤ r, are not all zero. We
thus deduce from (3.3) that f1 , . . . , fr are linearly dependent over k0 (t), as
wanted.
14

BORIS ADAMCZEWSKI, ALIN BOSTAN, AND XAVIER CARUSO

4. S TATE COMPLEXITY IN C HRISTOL ’ S THEOREM
Given an integer q ≥ 2, a multidimensional sequence a = (a(i))i∈Nn withvalues in a finite set is said to be q-automatic if a(i) is a finite-state functionof the base-q expansions of the entries of i. This means that there exists a
deterministic finite automaton taking the base-q expansion of each entry of i
as input, and producing the symbol a(i) as output. For a formal definition,
we refer the reader to [AB21].
For the rest of this section, we let q denote a prime power. The multivariate
extension of Christol’s theorem can be stated as follows. It is usually provedby following the approach initiated in [CKMFR80] for the case n = 1 (cf.
[Sal86, Sal87, DL87, SW88, Har88]).
P
Theorem C. Let f (t) := i∈Nn a(i)ti ∈ Fq [[t]]. Then f is algebraic overFq (t) if and only if the sequence a := (a(i))i∈Nn is q-automatic.
On each side, there is a natural way to measure the complexity of thecorresponding objects, as described below. A natural problem is then to study
the interplay between the complexity of the algebraic power series f andthat of its sequence of coefficients a.
4.1. Two notions of complexity. As already mentioned in Section 1, thecomplexity of an algebraic power series f ∈ Fq [[t]] can be measured by its
degree d and either its partial height h := (h1 , . . . , hn ) or its total height h.
We recall that d := [Fq (t)(f ) : Fq (t)], and, for all i, 1 ≤ i ≤ n, hi (resp. h) is
the minimal degree in the variable ti (resp. the minimal total degree in t)of a nonzero polynomial A(t, y) such that A(t, f ) = 0. These two notions ofheight are the same when n = 1.
The complexity of a q-automatic sequence a is measured by its state←−complexity. We let compq (a) denote the number of states in a minimal
finite automaton generating a in reverse reading, by which we mean thatthe input i is read starting from the least significant digits. In a similar−→way, we let compq (a) denote the state complexity of a with respect to direct←−−→
reading. In general, compq (a) and compq (a) behave quite differently and
←−

−→

−→

are only related by the inequalities compq (a) ≤ q compq (a) and compq (a) ≤←−q compq (a) . These estimates are derived from classical bounds for converting anondeterministic finite automaton into a deterministic one (see, for example,[AS03, Chapter 4]).
4.2. Previous bounds on the state complexity. Let us first recall that if a
is generated by a q-automaton with at most m states in reverse reading, it is
not difficult to show that the associated power series f has degree d ≤ q m − 1
and total height h ≤ mq m (this follows, for instance, from the proofs of[AB13, Propositions 5.1 and 5.2]). Furthermore, it seems that these bounds
cannot be significantly improved in general.

A SHARPER MULTIVARIATE CHRISTOL’S THEOREM

15

Bounds in the other direction are more challenging. The approach basedon Ore’s polynomials, initiated in [CKMFR80] and pursued in [Sal86, Sal87,
DL87, SW88, Har88, Har89, AB12], leads to bounds of the form←−B

compq (a) ≤ q Aq ,where A and B are polynomial functions of the parameters d, h1 , . . . , hn , thatcan be made explicit. The common feature of these bounds is that they havea doubly exponential nature (with respect to the size q of the ground field).
By contrast, when f is a rational function (i.e. d = 1), one can easily
obtain the bound q N , where N := min{(h1 + 1) · · · (hn + 1), n+hn }, and thus
get rid of the double exponential. This follows from Proposition 4.2 using
the vector spaces W and W 0 introduced in Section 1, and suggests that theprevious bounds are artificially large. In a more recent paper, Bridy [Bri17]
drastically improved on these doubly exponential bounds in the case n = 1.
More precisely, he proved that
(4.1)

←−

compq (a) ≤ (1 + o(1))q h+d+g−1 ,where g is the genus of the projective curve associated with f , and where
the o(1) term tends to 0 for large values of any of q, h, d, or g. By Riemann’s
inequality, which gives g ≤ (h − 1)(d − 1), he deduced that
(4.2)

←−

compq (a) ≤ (1 + o(1))q hd .

He also proved that
(4.3)

−→

compq (a) ≤ q (h+1)d .

Bridy’s approach is based on a new proof of Christol’s theorem in thecontext of algebraic geometry, due to Speyer (see his blog post untitled
Christol’s theorem and the Cartier operator1). Speyer’s argument is elegant,connecting finite automata with the geometry of curves. However, the priceto pay to get (4.1) is that some classical but nonelementary background fromalgebraic geometry is needed: the Riemann-Roch theorem, the existence andthe basic properties of the Cartier operator acting on the space of Kähler
differentials of the function field associated with f , along with asymptotic
bounds for the Landau function. Also, this geometric method does notseem to generalize easily to higher dimension. In an unpublished note,
Adamczewski and Yassawi [AY19] showed how a slightly weaker bound canbe obtained in an elementary way using diagonals, as in the original proof of
Christol’s theorem [Chr79], and resultant techniques. However, the use of
resultants makes the proof somewhat tedious.
4.3. A simply exponential bound in all dimensions. As a consequence ofTheorem 1.2, we obtain the following bound valid in any dimension.
1Available at https://sbseminar.wordpress.com/2010/02/11.

16

BORIS ADAMCZEWSKI, ALIN BOSTAN, AND XAVIER CARUSO

P
Theorem 4.1. Let f (t) := i∈Nn a(i)ti ∈ Fq [[t]] be algebraic over Fq (t) with
degree d, total height h, and partial height h := (h1 , . . . , hn ). Set
( n

)
Y
n+h
N := d · min(hi + 1),
n
i=1

and
N 0 := (d + 1) · min

( n
Y
i=1

)
n+h
(hi + 1),
.
n


Then
←−

compq (a) ≤ 1 + q N

and

−→

0

compq (a) ≤ q N .

←−−→For n = 1 we obtain compp (a) ≤ 1 + p(h+1)d and compq (a) ≤ q (h+1)(d+1) ;these estimates are close to Bridy’s bounds (4.2) and (4.3). Note that this
could be pushed a little by considering separately the orbit of f under thesection operator S0 . In fact, this is precisely how Bridy proceeds to get (4.2).
Let C := NP(A) + (−1, 0]2 be defined as in Theorem 1.2 (in the case n = 1)
and let gA denote the number of integer points in the interior of NP(A).
Generically, we have that g = gA . To simplify the exposition, the bounds
given in Theorem 4.1 are obtained by overapproximating C ∩N2 (for instance,by (h1 + 1)(d + 1) for the second one). Using gA instead, we would obtainbounds with the same flavor as (4.1). Theorem 4.1 is new in dimension
n ≥ 2, where only doubly exponential bounds were available until now (cf.
[Har89, FKdM00, AB12] and the discussion in [Bri17]).
The proof of Theorem 4.1 is derived from Theorem 1.2 and the following
result.
P
Proposition 4.2. Let f (t) := i∈Nn a(i)ti ∈ Fq [[t]]. Assume that there exists
a Fq -vector space W ⊂ Fq ((t)) of dimension m containing f and invariant
under the action of Ωn . Then
(4.4)

−→

←−

max{compq (a), compq (a)} ≤ q m .

Furthermore, we have
(4.5)

←−

compq (a) = |Ωn · f | .

In the case n = 1, Inequality (4.4) is a rephrasing of [Bri17, Proposition
2.4], while Equality (4.5) is a rephrasing of a classical result of Eilenberg←−
which asserts that compq (a) is equal to the cardinality of the q-kernel ofthe sequence a. Both results extend straightforwardly to arbitrary positive
integers n.
←−

Proof of Theorem 4.1. The upper bound for compq (a) follows from Theo−→rem 1.2 and Equation 4.4. The upper bound for compq (a) is a directconsequence of Remark 2.5 and Equation (4.5).
A SHARPER MULTIVARIATE CHRISTOL’S THEOREM

17

5. D IAGONALSGiven a field k and a multivariate power seriesXf (t1 , . . . , tn ) :=a(i1 , . . . , in )ti11 · · · tinn ∈ k[[t1 , . . . , tn ]] ,(i1 ,...,in )∈Nn

the diagonal of f is defined as the univariate power series∆(f )(t) :=+∞Xa(i, . . . , i)ti ∈ k[[t]] .

i=0

When k is a number field, diagonals of algebraic functions form a remarkableclass of power series: they satisfy linear differential equations of PicardFuchs type, they belong to the class of Siegel’s G-functions, and they are
constantly reoccurring in enumerative combinatorics. Furthermore, diagonalization is related to integration and, in general, the diagonal of an algebraic
power series is transcendental over k(t). For more details, we refer to thesurvey [Chr15].
By contrast, Furstenberg [Fur67] proved that if k has characteristic p andf is a rational power series, then ∆(f ) is algebraic over k(t). In [Del84],
Deligne generalized this result to diagonals of algebraic power series. Then
Harase [Har88], Sharif and Woodcock [SW88], Denef and Lipshitz [DL87],
as well as Salon [Sal87, Sal86] (in some particular case) independently
reproved Deligne’s theorem.
Combining Theorem 1.2 with Propositions 5.1 and 5.2 of [AB13], we
readily obtain an effective version of Deligne’s theorem: given an algebraic
power series f ∈ k[[t]] with degree d and total heights h, the diagonal ∆(f )has degree at most pN and height at most N pN , where N is explicitly given
by


n+h
N := (d + 1) ·.
n
In this section, we will prove a further refinement of this result, which canbe formulated as follows.
Theorem 5.1. Let k be an arbitrary field of characteristic p. Let f ∈ k[[t]]be an algebraic power series with degree d, total height h, and partial heighth = (h1 , . . . , hn ). Set( n  )nYYn+hh
N := (d + 1) · min(hi + 1) −
hi ,
−
.
n
n
i=1

i=1

Then, there exist c0 , c1 , . . . , cN ∈ k[t], not all zero, such thatNc0 · ∆(f ) + c1 · ∆(f )p + · · · + cN · ∆(f )p = 0 .
In particular, ∆(f ) has degree at most pN − 1.

18

BORIS ADAMCZEWSKI, ALIN BOSTAN, AND XAVIER CARUSO

5.1. Reduction of diagonals
modulo primes. Given a prime number p andPa power series f (t) := i∈Nn a(i)ti ∈ Z[[t]], we let f|p denote the reductionof f modulo p, that isX
f|p (t) :=(a(i) mod p)ti ∈ Fp [[t]] .
i∈NnDeligne [Del84] made the following nice observation: since diagonalization
and reduction modulo p commute, that is ∆(f )|p = ∆(f|p ), if f (t) ∈ Z[[t]]is algebraic over Q(t), then ∆(f )|p is algebraic over Fp (t) for almost allprime p. Hence, it is natural to ask how the “complexity” of the algebraic
function ∆(f )|p may increase when p runs along the primes. When ∆(f )is transcendental, van der Poorten [vdP93] conjectured that the degree of∆(f )|p cannot remain bounded independently of p. On the other hand,
Deligne [Del84] suggested that the degree of ∆(f )|p should grow at mostpolynomially in p.
Using the vector spaces W and W 0 introduced in Section 1, we can deducethe polynomial bound pN , with N := min{(h1 + 1) · · · (hn + 1), n+hn }, forf a multivariate rational power series with total height h and partial heighth = (h1 , . . . , hn ). The case where f is not rational is much more challenging.
Deligne [Del84] obtained a first result in this direction by proving that if
f (t1 , t2 ) ∈ Z[[t1 , t2 ]] is algebraic, then, for all but finitely many primes p,∆(f )|p is of degree at most ApB , where A and B do not depend on p but
only on certain geometric quantities associated with f . On the other hand,
the works of Harase [Har88, Har89], Sharif and Woodcock [SW88], andAdamczewski and Bell [AB12] lead to doubly exponential bounds (i.e. ofM
the form pp ). The first general polynomial bound (i.e. of the form pA ) was
obtained by Adamczewski and Bell in [AB13]. They provide an effective A
that depends only on the degree and the total height of f . However, when f
has degree d > 1, the value of A becomes huge due to a recursive procedure
involving resultants. For instance, even for n = 2, the estimate for A is of theform
hd2
2 6 d44(h d )dand the length of the exponential tower increases at least linearly with n. It
is also possible to deduce from the work of Denef and Lipshitz [DL87] theexistence of such a polynomial bound, but with an ineffective constant A.
Theorem 5.1 readily implies the following result, which quite significantly
improves the previous known bounds.
Theorem 5.2. Let f ∈ Z[[t]] be an algebraic power series with degree d, totalheight h, and partial height h = (h1 , . . . , hn ). Set( n  )
n
Y
Y
n+h
h
(5.1)
N := (d + 1) · min(hi + 1) −
hi ,
−
.
n
n
i=1

i=1

Then, for all prime numbers p, ∆(f )|p has degree at most pN − 1 over Fp (t).

A SHARPER MULTIVARIATE CHRISTOL’S THEOREM

19

Remark 5.3. Not only Theorem 5.1 gives a nice bound on the degree of∆(f )|p , but it also shows that ∆(f )|p is annihilated by an Ore polynomial ofbounded p-degree. This additional feature implies that the Galois conjugatesof ∆(f )|p are all contained in an Fp -vector space of dimension N and eventually that the Galois group of ∆(f ) (i.e. the Galois group of the extension ofk(t) generated by ∆(f ) and all its Galois conjugates) canonically embeds, up
to conjugacy, into GLN (Fp ). This observation allows for asking more precise
questions about the uniformity with respect to p. For example, one may
wonder if the Galois groups of ∆(f )|p all come by reduction modulo p from aunique group (or maybe a finite number of groups) defined in characteristic
zero.
Remark 5.4. Using the same arguments as in [AB13, p. 967], we could also
prove a more general statement than Theorem 5.2 by replacing the ring Z
with a number field and consider reductions modulo prime ideals. In fact, we
could even consider the case where f has coefficients in an arbitrary field of
characteristic zero (see [AB13, Theorem 1.4]). Note that, beyond diagonalsof algebraic power series, there are other interesting families of G-functions
in Q[[t]] whose reductions modulo p are algebraic (cf. [VM21]). Furthermore,
algebraicity modulo p turns out to be useful to prove transcendence andalgebraic independence results for power series in characteristic zero (cf.
[WS89, AGBS98, AB13, ABD19, VM23]).
5.2. Generalized diagonals. In what follows, we consider a slight generalization of the diagonalization process. Let k be a perfect field of characteristic p and let t := (t1 , . . . , tn ) be a tuple of indeterminates. We set
K0 := k(t), R := k[[t]], and we let K denote the field of fractions of R. Let
G be a subgroup of Zn such that the quotient Zn /G has no torsion. We let
K0,G be the subfield of K0 generated by k and by the monomials ti withi ∈ G. Similarly,
RG as the k-subalgebra of R consisting of series
P we define
iof the form i∈G a(i)t . Given that G is abstractly isomorphic to Zm forsome integer m ≤ n, the rings KG and RG are respectively isomorphic tok(x1 , . . . , xm ) and k[[x1 , . . . , xm ]].
Definition 5.5. We keep the previous notation. The G-diagonal is the operator defined by∆G :R −→ RG
X
X
a(i)ti 7→
a(i)tii∈Nni∈Gwith the convention that a(i) = 0 when i 6∈ Nn .

When G is the subgroup generated by (1, . . . , 1), the ring RG is isomorphic
to k[[t]] via the map t1 · · · tn 7→ t and the diagonal operator ∆G is theusual diagonal operator ∆. However the general construction ∆G is more
flexible and allows in particular for partial diagonals: letting G be thesubgroup generated by (1, . . . , 1) and by ei = (0, . . . , 0, 1, 0, . . . , 0) (with 1 in

20

BORIS ADAMCZEWSKI, ALIN BOSTAN, AND XAVIER CARUSO

i-th position) for i ∈ {1, . . . , m}, we obtain that RG ' k[[t1 , . . . , tm , x]] and!
XX
ia(i1 , . . . , im , n, . . . , n) ti11 · · · timm xn .
∆G
a(i)t
=
(i1 ,...,im )∈Nm
n∈N

i∈Nn

In general, one can check that ∆G is K0,G -linear.
Theorem 5.6. Let k be an arbitrary field of characteristic p, G be a subgroup ofZn such that Zn /G has no torsion, let GR be the subvector space of Rn generated
by G, and let πG : Rn+1 → (Rn /GR ) × R denote the canonical projection. Let
A(t, y) ∈ k[t, y] and let f ∈ k[[t]] satisfying the algebraic relation A(t, f ) = 0.
Let C be the convex subset of Rn+1 defined by
C := NP(A) + GR × (−1, 0] .
Then, there exist c0 , c1 , . . . , cN ∈ K0,G , not all zero, such thatNc0 · ∆G (f ) + c1 · ∆G (f )p + · · · + cN · ∆G (f )p = 0 ,where N := Card πG (C ∩ Nn+1 ) .

(5.2)

Proof. We first observe that, by Proposition 3.1, we can replace without
any loss of generality the field k by the perfect closure of the subfield of k
generated over Fp by the coefficients of f . Hence, we can assume that k isperfect.
Let E ∈ k(t, y) be the minimal polynomial of f and Ey be the derivativeof E with respect to y. Set J := (−1, 0] and
C 0 := NP(E) + GR × J .
Repeating the proof of Theorem 1.2, we show that the k-vector space
P (t, f )0
W :=: P ∈ k[t, y], NP(P ) ⊂ C
Ey (t, f )contains f and is invariant under Sr for all r ∈ G. Noticing that ∆Gcommutes with Sr whenever r ∈ G, we conclude that ∆G (W ) is invariant
under Sr for all r ∈ G as well.
Let V be the K0,G -span of ∆G (W ) in KG := Frac(RG ). By linearity,
we find that V is spanned by the elements ti f j /Ey (t, f ) for (i, j) running00
over C 0 ∩ Nn+1 . Besides, two fractions ti f j /Ey (t, f ) and ti f j /Ey (t, f )are K0,G -collinear as soon as i ≡ i0 mod G, which occurs if and only if
πG (i, j) = πG (i0 , j). The dimension of V over K0,G is then upper boundedby the cardinality of πG (C 0 ∩ Nn+1 ), which is itself upper bounded by N (seethe last paragraph of the proof of Theorem 1.2 for more details).
The Frobenius map F acts as an endomorphism of K0,G . We consider the“relative” Frobenius map of KG defined byψ:

KG ⊗K0,G ,F K0,G −→ KGx ⊗ y 7→ xp y

A SHARPER MULTIVARIATE CHRISTOL’S THEOREM

21

where the notation ⊗K0,G ,F means that we view K0,G as an algebra over itself
via F. Hence, in KG ⊗K0,G ,F K0,G , we have 1 ⊗ y = y p ⊗ 1. This construction
ensures that ψ is a K0,G -linear isomorphism. Moreover, it is related to thesection operators via the formulaXψ −1 (f ) =Sr (f ) ⊗ tr ,r∈Gpwhere we let Gp ⊂ G denote a set of representatives of G/pG. Recall that
we have proved earlier that V is closed under the action of Sr for all r ∈ G.
Therefore, we find that ψ −1 induces a K0,G -linear morphism from V toV ⊗K0,G ,F K0,G . Being the restriction of an injective map, this morphism
is clearly injective. Given that V is finite dimensional over K0,G and that
dimK0,G V = dimK0,G (V ⊗K0,G ,F K0,G ), we conclude that it is an isomorphism.
Hence ψ takes V ⊗K0,G ,F K0,G to V , which further implies that V is invariant
under the Frobenius map.
s
In particular, ∆G (f )p lies in V for all nonnegative integers s. SinceN
moreover dimK0,G V ≤ N , it follows that ∆G (f ), ∆G (f )p , . . . , ∆G (f )p mustbe linearly dependent over K0,G . Thus, there exist c0 , c1 , . . . , cN ∈ K0,G , notall zero, such thatNc0 · ∆G (f ) + c1 · ∆G (f )p + · · · + cN · ∆G (f )p = 0 ,as desired.



5.3. Proof of Theorem 5.1. We apply Theorem 5.6 with the group G generated by (1, . . . , 1). As already noticed, the diagonal ∆G is then the usual
diagonal ∆, up to the identification t := t1 · · · tn . Let A(t, y) be the minimal
polynomial of f , so that A has degree d, total height h, and partial heighth = (h1 , . . . , hn ). Let πG be the mapping and C be the convex set definedin the statement of Theorem
5.6. By Theorem 5.6, it remains to prove that
Card πG (C ∩ Nn+1 ) ≤ N .
Let c := (a1 , . . . , an , b) ∈ C ∩ Nn+1 . We have −1 < b ≤ d and, given that b
is an integer, we conclude that 0 ≤ b ≤ d. Moreover, up to translating c by anelementof G, one may assume that 0 ≤ ai ≤ hi for all i ∈ {1, . . . , n} and thatPna≤h. Define a := min{a1 , . . . , an } and, for all i, set ãi := ai − a. Theni=1 i
one of the first n coordinates ofPc̃ := (ã1 , . . . , ãn , b) vanishes. On the other
hand, one has 0 ≤ ãi ≤ hi and ni=1 ãi ≤ h. Furthermore, πG (c) = πG (c̃).
This ensures that any element of πG (C ∩ Nn+1 ) has a preimage in each of thesetsE1 := (a1 , . . . , an , b) ∈ Nn+1 : b ≤ d, ∀i, ai ≤ hi , ∃i, ai = 0
and
(
E2 :=

(a1 , . . . , an , b) ∈ N

n+1: b ≤ d,

n
X
i=1

)
ai ≤ h, ∃i, ai = 0.

22

BORIS ADAMCZEWSKI, ALIN BOSTAN, AND XAVIER CARUSO

Since
Card(E1 ) = (d + 1) ·nnYY(hi + 1) −
hi
i=1

and



!

i=1

  
n+h
h
−
,
n
n

Card(E2 ) = (d + 1) ·
we have that Card πG (C ∩ Nn+1 ) ≤ min{Card(E1 ), Card(E2 )} = N , aswanted.
6. H ADAMARD PRODUCT AND OTHER SIMILAR PRODUCTS
Let k be a field and t := (t1 , . . . , tn )P
be a vector of indeterminates.
GivenP
two multivariate power series f (t) := i∈Nn a(i)ti and g(t) := i∈Nn b(i)ti
in k[[t]], their Hadamard product is defined byX
f g :=
a(i)b(i)ti ∈ k[[t]] .
i∈Nn

The Hadamard product is intimately connected to diagonalization. Indeed,
we have1∆(f ) = ϕ f,
1 − t1 · · · tn
where ϕ is the map defined by t1 · · · tn 7→ t, whilefg = ∆G (f (t)g(y)) ,where G is the subgroup of Z2n generated by the vectors vi , 1 ≤ i ≤ n, whosei-th and (i + n)-th entries are 1 and the other entries are 0.
As with diagonals, if k has characteristic zero, the Hadamard product of
two algebraic power series in k[[t]] is in general transcendental. The situation
is totally different if k has characteristic p. When k is a finite field and n = 1,
Furstenberg [Fur67] proved that the ring of algebraic power series is closed
under Hadamard product. This was independently extended to arbitrary
fields k of characteristic p and positive integers n, by Denef and Lipshitz[DL87], Sharif and Woodcock [SW88], and Harase [Har88]. Harase [Har89]
also obtained a quantitative version of this result when k is a perfect field:Bthe degree of algebraicity of f g over k(t) is bounded by pAp for some A
and B that are made explicit and depend polynomially on the degrees andthe heights of f and g.
The following theorem improves considerably Harase’s bound.
Theorem 6.1. Let k be a field of characteristic p and let f, g ∈ k[[t]] be two
algebraic power series of degree d and d0 , total height h and h0 , and partial
height h := (h1 , . . . , hn ) and h0 := (h01 , . . . , h0n ), respectively. Set
( n

)
Y
n+h
N1 := (d + 1) · min(hi + 1),ni=1A SHARPER MULTIVARIATE CHRISTOL’S THEOREM

and0

N2 := (d + 1) · min( nY(h0i + 1),

i=1Then fn + h0n

23

).

g is an algebraic power series of degree at most pN1 N2 − 1 over k(t).

We will prove this theorem in Section 6.2.
Remark 6.2. Again, we could also bound the total height h of f
the argument in [AB13, Proposition 5.2].

g following

6.1. Hurwitz and Lamperti products. All along this section, we only consider univariate power series,
the case n =Given a field k andP that is
P1.
∞
i and g(t) :=i
two power series f (t) := ∞
a(i)t
i=0
i=0 b(i)t in k[[t]], their
Hurwitz product is defined by
!
∞
i  
X
X
i
f ◦H g :=a(k)b(i − k) ti ∈ k[[t]] ,
k
i=0

k=0

and their Lamperti product by


∞
X
X
i!

αj β k γ ` a(j + k)b(` + k) ti ∈ k[[t]] ,f ◦L g :=j!k!`!
i=0

j+k+`=iwhere the parameters α, β, and γ belong to k. The Lamperti product generalizes both the Hadamard product (taking α = β = 0 and γ = 1) andthe Hurwitz product (taking α = β = 1 and γ = 0). When k has positive
characteristic, Harase [Har88, Har89] proved that the Lamperti product of
two algebraic power series f and g remains algebraic and he provided aBdoubly exponential bound (i.e. of the form pAp ) for the degree of f ◦L g(and thus for f ◦H g). Again, our approach leads to a simply exponential
bound.
Theorem 6.3. Let k be a field of characteristic p and let f, g ∈ k[[t]] be two
algebraic power series of degree d and d0 and height h and h0 , respectively. Set
N := (d + 1)(d0 + 1)(h + 1)(h0 + 1) .
Then f ◦L g is an algebraic power series of degree at most pN − 1 over k(t). In
particular, the same result holds for f g and f ◦H g.
6.2. Proof of Theorems 6.1 and 6.3. As previously, we let K denote thefield of fractions of k[[t]] and Sr , r ∈ {0, . . . , p − 1}n be the section operators.
We first deduce from Theorem 1.2 and Proposition 3.1 the following general
result.
Proposition 6.4. Let k be a field of characteristic p and let ? be a bilinear
product defined over k[[t]] such that for all f, g ∈ k[[t]] one has(6.1)

Sr (f ? g) ∈ spank {Si f ? Sj g : i, j ∈ {0, . . . , p − 1}n } .

24

BORIS ADAMCZEWSKI, ALIN BOSTAN, AND XAVIER CARUSO

Let f1 , f2 ∈ k[[t]] and let us assume that for all i ∈ {1, 2} there exists a k-vector
space Wi ⊂ K of dimension at most di containing fi and invariant by Ωn . Then
f1 ? f2 is an algebraic power series of degree at most pd1 d2 − 1 over k(t).
Proof. Let us first assume that k is a perfect field. Let h1 , . . . , hr be a basis of
W1 and h01 , . . . , h0s be a basis of W2 . Set
W := spank {hi ? h0j : 1 ≤ i ≤ r, 1 ≤ j ≤ s} .
Then W has dimension at most d1 d2 and the bilinearity of ? implies that W
contains f1 ? f2 . On the other hand, since W1 and W2 are invariant under Ωn ,we infer from the bilinearity of ?, the semilinearity of the section operators,and (6.1) that W is also invariant under Ωn . Then it follows classically thatf1 ? f2 is algebraic over k(t) with degree at most pd1 d2 − 1 (cf., for instance,[Har89] and [AB13, Proposition 5.1]).
Now, if k is an arbitrary field of characteristic p, one can pass to its perfectclosure kp and then apply the previous argument to obtain that f1 ? f2 asdegree at most pd1 d2 − 1 over kp (t). By Proposition 3.1, we deduce that thedegree of f1 ? f2 over k(t) is also at most pd1 d2 − 1, as wanted.
Proof of Theorem 6.1. After noticing thatSr (fg) = Sr (f )Sr (g) ,the proof follows directly from Proposition 6.4 and Corollary 1.4.

Proof of Theorem 6.3. After noticing, as in [Har89], thatXr!
αs/p β t/p γ (r−s−t)/p Sr−t (f ) ◦L Sr−s (g) ,Sr (f ◦L g) =s!t!(r − s − t)!
0≤s,r
s+t≤r

the proof follows directly from Proposition 6.4 and Corollary 1.4 (withn = 1).

7. A LGORITHMIC CONSEQUENCES OF T HEOREM 1.2
Throughout this section, we assume for simplicity that k is a finite field Fq .
We address the question of the efficient computation of one “faraway” coefficient of a power series f (t) ∈ k[[t]] assumed to be algebraic over k(t).
It was pointed out in [AS92, Corollary 4.5] that the M -th term of an
automatic sequence (and more generally of a k-regular sequence) can becomputed using O(log M ) operations in k. By Christol’s theorem (and its
multivariate version) it follows that, given i := (i1 , . . . , in ), the coefficient of
ti := ti11 · · · tinn in the expansion of f can be computed in O(log M ) operations
in k, where M := max(i1 , . . . , in ). (For fields of characteristic zero, there is
no algorithm achieving polynomial time in log M for the same task, even if
n = 1.) However, this estimate is oversimplified in the sense that the O(·)
hides dependencies in the other parameters, namely the characteristic p of
the ground field k, the number of variables n and the various algebraicity
degree and heights of f . The actual efficiency of any algorithm that computes

A SHARPER MULTIVARIATE CHRISTOL’S THEOREM

25

the coefficient of ti of f heavily depends on these parameters, especiallygiven that before entering the O(log M )-part, some of these algorithms mayneed to perform precomputations whose cost is so large with respect tothe other parameters, that the algorithms are highly inefficient in practice.
This is particularly true for the class of algorithms that start with building a
q-automaton: the running time of this precomputation depends on numberof states of the automaton, which can be huge. For these reasons, in thealgorithmic design, it is important to care about the dependencies withrespect to all the other parameters. This is the object of this section.
7.1. The algorithm. For algorithmic purposes, the starting point is always tofind a suitable finite representation of the objects we want to compute with.
In our setting, it is of course not possible to represent a power series f (t)by its full sequence of coefficients in k, because this sequence is an infinite
object. However, when f (t) is algebraic, we can hope to come back to a
finite representation by working with an annihilating polynomial of f (t),together with sufficiently many initial coefficients in the expansion of f (t).
This indeed works but requires some caution, given that the aforementioned
polynomial may in general have severalProots. In what follows, we shallencode an algebraic power series f (t) := i∈Nn a(i)ti by the following data:(a) its minimal polynomial E(t, y) ∈ k[t, y] over k(t), which we normalize (up to a unit in k) by requiring it to have polynomial coefficientsin k[t] that are globally coprime,(b) a minimal element (for the product order on Nn ), denoted by ρ :=(ρ1 , . . . , ρn ), of NP Ey (t, y) ∩ Nn (which is nonempty thanks to
Lemma 2.4),(c) the coefficients a(i) for all tuples i := (i1 , . . . , in ) with 0 ≤ ij ≤ ρjfor all 1 ≤ j ≤ n.
Lemma 7.1. The previous data uniquely determines the algebraic power series f .
Proof. Let i := (i1 , . . . , in ) ∈ Nn be a multiindex. For each j ∈ {1, . . . , n}, wewrite the decomposition in base p of ij
ij =

`−1
X

rj,m pm ,m=0where ` is a positive integer and all the rj,m ’s are integers between 0 and
p−1. For each m, we form the tuple r m := (r1,m , . . . , rn,m ) and consider thecorresponding section operator Srm . It follows from the definitions that thecoefficient a(i) is equal to the p` -th power of the constant coefficient of thepower seriesg(t) := Sr`−1 ◦ · · · ◦ Sr1 ◦ Sr0 f (t) .

26

BORIS ADAMCZEWSKI, ALIN BOSTAN, AND XAVIER CARUSO

Input: A multiindex i = (i1 , . . . , in ) and an algebraic power seriesf (t) ∈ k[[t]] encoded by (E(t, y), ρ, f (t) mod tρ+1 )Output: The i-th coefficient of f (t)1. For j = 1, . . . , n,Pmwrite the decomposition of ij in base p: ij = `−1
m=0 rj,m p
2. Set Q0 (t, y) := y · Ey (t, y)
3. For i = 0, 1, . . . , ` − 1,set Qi+1 (t, y) := Sf,r1,m ,...,rn,m ,p−1 Qi (t, y) · E(t, y)p−1
4. Compute Q` (t, f (t)) mod tρ+1 and set α := [tρ ]Q` (t, f (t))
5. Compute Ey (t, f (t)) mod tρ+1 and set β := [tρ ]Ey (t, f (t))`
6. Return (α/β)pAlgorithm 1: i-th coefficient of an algebraic power series.
Moreover, by Eq. (2.4), there exists a polynomial Q ∈ k[t, y] such thatg(t) =Q(t, f (t)),
Ey (t, f (t))

i.e.

Q(t, f (t)) = g(t) · Ey (t, f (t)) .

Identifying the coefficients in tρ in the latter equality, we findX[tρ ]Q(t, f (t)) =[tu ]g(t) · [tv ]Ey (t, f (t)) ,u+v=ρ

where the notation [tj ]ϕ(t) refers to the coefficients in front of tj in the
power series ϕ(t). On the other hand, we derive from the definition of ρ(and especially from the minimality condition (b)) that the unique v ≤ ρ forwhich the coefficient [tv ]Ey (t, f (t)) does not vanish is ρ itself. Therefore, we
conclude that[tρ ]Q(t, f (t)) = [t0 ]g(t) · [tρ ]Ey (t, f (t))
which gives
 ρ
`
p `
[t ]Q(t, f (t)) p0a(i) = [t ]g(t)=.
[tρ ]Ey (t, f (t))
Since f (t) is given at precision O(tρ11 +1 · · · tρnn +1 ), we can compute Q(t, f (t))
at the same precision; this ensures that the coefficient [tρ ]Q(t, f (t)) can berecovered from the set of data that we have at our disposal. Hence the same
holds for a(i). Since i was chosen arbitrarily at the beginning of the proof,
the lemma is proved.

Importantly, we notice that the proof of Lemma 7.1 together with theexplicit formula (2.3) translate immediately to Algorithm 1 which computes
the coefficient a(i) of the power series f (t). Note that Algorithm 1 can beseen as a multivariate version of the algorithms in [BCCD19, Section 3].
We now study the (arithmetic) complexity of Algorithm 1. In what follows,
we will express complexity of algorithms in terms of the number of operations

A SHARPER MULTIVARIATE CHRISTOL’S THEOREM

27

they perform in the ground field k. By “operation”, we mean either a classicalarithmetical (field) operation (addition, subtraction, multiplication, division)or an application of the Frobenius map F, or its inverse. We recall the soft-O
notation Õ: by definition, Õ(c) is the union of the O(c logk (c)) for k varying
in N. Using Õ instead of the more customary O-notation makes it possible to“hide” logarithmic factors.
Theorem 7.2. Let f (t) ∈ k[[t]] be an algebraic power series encoded by thedata(E(t, y), ρ, f (t) mod tρ+1 ) .
Let h := (h1 , . . . , hn ) be the vector of partial heights of E(t, y) and d be its
degree. On input f (t) and i := (i1 , . . . , in ), Algorithm 1 performs at mostÕ 2n dpn+1 (h1 +1) · · · (hn +1) log M + 2n (ρ1 +1) · · · (ρn +1)
operations in k, where M := max(i1 , . . . , in ).
Proof. By construction, all intermediate polynomials Qi (t, y) have partial
heights at most h and degree at most d. Recall that polynomials in k[t, y]of degree at most d and partial heights at most h = (h1 , . . . , hn ) can be
multiplied in Õ (2n d(h1 + 1) · · · (hn + 1)) operations in k, using Fast Fourier
Transform (FFT) multiplication of univariate polynomials [CK91] and Kronecker’s substitution [Pan94]. Therefore, each iteration of the loop in line 3
requires at most Õ 2n dpn+1 (h1 +1) · · · (hn +1) operations in k. Besides, thenumber of times this loop is executed, namely `, grows at most logarithmically with respect to M . The total cost of line 3 then stays withinÕ 2n dpn+1 (h1 +1) · · · (hn +1) log M
operations in k. Similarly,
 the computations in lines 4 and 5 require at mostÕ 2n (ρ1 +1) · · · (ρn +1) operations in k. Adding both contributions, we findthe announced complexity.
Remark 7.3. A small optimization can be applied to Algorithm 1. It consistsiin computing QFi (that is the polynomial obtained from Qi by applying Fi
to each of its coefficients) instead of Qi on line 3, thanks to the recurrence
relation:

i+1
i
i
F
QFi+1 (t, y) = Sf,rQFi (t, y) · E F (t, y)p−1 ,1,m ,...,rn,m ,p−1
Fwhere Sf,r,s
is the same operator as Sf,r,s except that we do not take preimages of the coefficients by the Frobenius map F. Proceeding this way, we``
retrieve F` (α) = αp by selecting the coefficient of tρ in QF` (t, f (t)) and can`return F` (α)/β p on line 6. With this optimization, it becomes unnecessary toapply inverses of F in Algorithm 1. This may be beneficial since, in practice,
applying F−1 may be a more expensive operation than applying F.

Remark 7.4. It is possible to give a priori bounds on ρ in terms of h and d.
Indeed, let r(t) be the resultant in y of the polynomials E(t, y) and Ey (t, y).
A calculation shows that the ti -degree of r(t) is upper bounded by 2dhi .

28

BORIS ADAMCZEWSKI, ALIN BOSTAN, AND XAVIER CARUSO

Besides, it follows from the standard properties of resultants that Ey (t, f (t))
divides r(t) in the ring k[[t]]. Hence the Newton polytope of Ey (t, f (t))
necessarily has one point in the box [0, 2dh1 ] × · · · × [0, 2dhn ], from which
we derive that one can always choose ρ ≤ 2d·h. The above discussion showsthat the complexity of Algorithm 1 can be controlled in terms of h, d andlog M only: to simplify notation, setting
H := (h1 +1) · · · (hn +1) ,the number of operations used by Algorithm 1 is at most
(7.1)

Õ 2n dpn+1 H log M + 4n dn H .

For n = 1 and h1 = h > 0, the cost (7.1) reads Õ dhp2 log M . This issimilar to the complexity estimate Õ h(d+h)p2 +h2 (d+h)2 log M of [BCD16,
Algorithm 3]. Faster algorithms are available when
 n = 1, with quasi-linear
complexity in p: Õ h2 (h + d)2 log M + h(h + d)5 p ([BCD16, Theorem 11])and even Õ d2 h2 log M + d2 hp + d3 h ([BCCD19, Theorem 3.4]).
For a general n, the complexity estimate (7.1) is exponentially better(with respect to p) than all estimates that could be deduced from known
approaches. This important improvement is of course ultimately inheritedfrom Theorem 1.2. It would be interesting to design faster variants of
Algorithm 1, whose complexities improve the estimate (7.1), e.g. replacing
the term pn+1 by pn .
7.2. Applications to diagonals. Assume that f (t) ∈ Fp [[t]] is an algebraic
power series in n variables of degree d and partial height h := (h1 , . . . , hn ).
We consider here the following algorithmic problem: given M ∈ N, how fast
can one compute the M -th coefficient in the expansion of the diagonal ∆(f )?
When f is rational, Rowland and Yassawi proposed in [RY15, Section 2]
two algorithms to compute finite automata that could be used to computeterms of the coefficient sequence of ∆(f ). However, the number of states ofthe produced automata is prohibitively large: Remark 2.2 in [RY15] providesnan upper bound of the form p(h+1) , where h is the total height of f .
By Theorem 5.2 and the discussion above, ∆(f ) is an algebraic power
series in Fp [[t]] of degree D∆ ≤ pN − 1 and height H∆ ≤ N pN where N is at
most (d + 1)H and, as before, H = (h1 +1) · · · (hn +1). Hence, a “naive” wayof computing the coefficient [tM ]∆(f ) would be to first determine an annihilating polynomial E ∈ Fp [t, y] for ∆(f ), and then to apply the algorithmsof [BCD16] or [BCCD19] to this E. Starting from the first 2(D∆ +1)(H∆ +1)
terms in the expansion of ∆(f ), one can compute such an E, by (structured)ω H ) ⊆ Õ(N p(ω+1)N ) operations in F , as exlinear algebra, using Õ(D∆p∆plained in [BCCD19, p. 128]. Here ω ∈ [2, 3] is a feasible exponent for thematrix multiplication. Hence, using [BCCD19, Theorem 3.4], we conclude

A SHARPER MULTIVARIATE CHRISTOL’S THEOREM

29

that, for M  0, the coefficient [tM ]∆(f ) can be computed in

2
2
3
Õ H∆
(H∆ + D∆ )2 log M + D∆H∆ p + D∆
H∆⊆ Õ d4 H 4 p4(d+1)H log M

operations in Fp . This complexity estimate is quasi-optimal with respect
to M , but its dependence in p is far from optimal.
A much better method is to apply Algorithm 1 with i = (M, . . . , M )directly, without first precomputing an annihilating polynomial for ∆(f ).
The resulting complexity is then provided by Theorem 7.2, and is boundedin terms of n, p, d, h1 , . . . , hn by the estimate in (7.1), namelyÕ 2n dpn+1 H log M + 4n dn H .
This method then allows to compute the M -th coefficient of the diagonalof f (t1 , . . . , tn ) in arithmetic complexity linear in log M and quasi-linear in
pn+1 . This result was previously known only in the bivariate case. For morethan two variables, previous algorithms with complexity linear in log M
required (at least) doubly exponential time in the arithmetic size of f .
Note finally that the truth of Christol’s conjecture [Chr90, Conjecture 4]
would imply that log(M )-time algorithms for computing the M -th term
modulo p might well exist for the whole class of integer sequences withgeometric growth which are P-finite (i.e., which satisfy linear recurrence
relations with polynomial coefficients in the index n).
2
2
P:= nk=0 nk n+k7.3. Examples. We considertheApérynumbers
A(n)
.
k
P∞
n
Their generating function n=0 A(n)t is the diagonal of the rational function in n = 4 variables [Str14]
1
f (t1 , t2 , t3 , t4 ) :=·(1 − t1 − t2 )(1 − t3 − t4 ) − t1 t2 t3 t4Hence, by (7.1), A(M ) mod p can be computed in O(p5 log M ) operations
Pin Fp . This estimate can be lowered to Õ(p4 log M ) by using that n≥0 A(n)tn
is also the diagonal of the following algebraic function in n = 3 variables:p
1/ (t1 t2 t3 + t1 + t2 − 1)2 − 4(t1 + t2 − 1)2 t3 .
In this particular case, a better complexity bound can be obtained by exploiting nontrivial arithmetic properties of the Apéry numbers. Indeed, it turns
out that the sequence (A(n))n≥0 is p-Lucas [Ges82]: if M = (i`−1 . . . i1 i0 )p
is the base-p expansion of M , then A(M ) = A(i`−1 ) · · · A(i1 )A(i0 ) mod p,
hence it is sufficient to precompute A(0) mod p, . . . , A(p−1) mod p. Thiscan be done for a cost of O(p) operations in Fp by unrolling the recurrence(n + 1)3 A(n + 1) = (2n + 1) 17n2 + 17n + 5 A(n) − n3 A(n − 1) satisfiedby (A(n))n≥0 . After this, computing A(M ) mod p only requires O(log M )extra operations in Fp .
However, beyond this example, many other interesting integer sequences
are not p-Lucas, but are known to admit diagonals of algebraic functions as

30

BORIS ADAMCZEWSKI, ALIN BOSTAN, AND XAVIER CARUSO

generating functions. Most of the integer sequences from the combinatorial
literature, which are P-finite and have a geometric growth, are known tofall into this class. For instance, the sequence 1, 6, 222, 9918, . . . (A144045)
counting diagonal rook paths on a 3D chessboard was proved in [BCvHP12]
to satisfy the recurrence
2n2 (n − 1)a(n) − (n − 1)(121n2 − 91n − 6)a(n − 1)−(n−2)(475n2 −2512n+2829)a(n−2)+18(n−3)(97n2 −519n+702)a(n−3)− 1152(n − 3)(n − 4)2 a(n − 4) = 0 ,for n ≥ 4 ,P
and to admit a generating function F (t) := n≥0 a(n)tn equal to
Z t 2 F1 1/3 2/3 27w(2 − 3w)
2(1 − 4w)3
F (t) = 1 + 6 ·
dw .
(1
−
4w)(1
−
64w)
0
Given a prime p, neither the recurrence, nor the closed form of F (t) are
well-suited to compute rapidly the value a(M ) mod p for high values of M .
In exchange, a(M ) is the M -th coefficient of the diagonal of the rational
function in 3 variables(1 − t1 )(1 − t2 )(1 − t3 )f (t1 , t2 , t3 ) :=·1 − 2(t1 + t2 + t3 ) + 3(t1 t2 + t2 t3 + t1 t3 ) − 4t1 t2 t3Hence, by (7.1), a(M ) mod p can be computed using Õ(p4 log M ) operationsin Fp . This can be lowered to Õ(p3 log M ) by using a diagonal expression for
F (t) as the diagonal of an algebraic function in n = 2 variables, e.g. ofs(1 − t2 )
1 (1 − t1 )2+.
·2
2 − 3t1(1 − 2t1 )2 − (3 − 4t1 )2 t2
A similar example is given by the sequence 1, 2, 18, 255, 4522, . . . (A151362)
whose n-th term q(n) counts walks in the quarter plane N2 of length 2n starting at the origin and using steps
P in the set {N, S, NE, SE, NW, SW}. The
generating function Q(t) := n≥0 q(n)t2n of this sequence is known to betranscendental over Q(t) and to admit the 2 F1 expression [BCvH+ 17]
Z Z
t y


64 z 22
1
3/4 5/4dz dy
Q(t) = 2·F
2 1
2
t 0 0 (12 z 2 + 1)3/2(12 z 2 + 1)2
and also the diagonal expression [MM16]!
t22 − 1 t23 − 1 ,Q(t) = ∆1 − t1 t22 t23 + t2 t23 + t22 + t23 + t2 + 1with n = 3 and (h1 , h2 , h3 ) = (1, 2, 2). Using the last expression, q(M ) mod p
can be computed in Õ(p4 log M ) operations in Fp . The same remark actuallyapplies to all 19 × 4 − 3 transcendental generating functions of the form
Q(0, 0), Q(1, 0), Q(0, 1) and Q(1, 1) from [BCvH+ 17, Theorem 2].

A SHARPER MULTIVARIATE CHRISTOL’S THEOREM

31

R EFERENCES[AB12]

B. Adamczewski and J. Bell. On vanishing coefficients of algebraic power series
over fields of positive characteristic. Invent. Math., 187:343–393, 2012.
[AB13]
B. Adamczewski and J. Bell. Diagonalization and rationalization of algebraic
Laurent series. Ann. Sci. Éc. Norm. Supér., 46:963–1004, 2013.
[AB21]
B. Adamczewski and J. Bell. Automata in number theory. In Handbook of automata theory. Vol. II. Automata in mathematics and selected applications, pages
913–945. EMS Press, Berlin, 2021.
B. Adamczewski, J.. Bell, and E. Delaygue. Algebraic independence of G[ABD19]
functions and congruences “à la Lucas”. Ann. Sci. Éc. Norm. Supér., 52:515–559,
2019.
[AGBS98] J.-P. Allouche, D. Gouyou-Beauchamps, and G. Skordev. Transcendence of binomial and Lucas’ formal power series. J. Algebra, 210:577–592, 1998.
[AS92]
Jean-Paul Allouche and Jeffrey Shallit. The ring of k-regular sequences. Theoret.
Comput. Sci., 98(2):163–197, 1992.
[AS03]
J.-P. Allouche and J. Shallit. Automatic sequences. Cambridge University Press,
Cambridge, 2003.
B. Adamczewski and R. Yassawi. A note on Christol’s theorem. arXiv:1906.08703[AY19][math.NT], https://arxiv.org/abs/1906.08703, 2019.
H. F. Baker. Examples of the application of Newton’s polygon to the theory of[Bak93]
singular points of algebraic functions. Trans. Camb. Phil. Soc., XV(IV):403–450,
1893.
[BCCD19] A. Bostan, X. Caruso, G. Christol, and P. Dumas. Fast coefficient computation foralgebraic power series in positive characteristic. In Proceedings of the Thirteenth
Algorithmic Number Theory Symposium, volume 2 of Open Book Ser., pages
119–135. Math. Sci. Publ., Berkeley, CA, 2019.
Alin Bostan, Gilles Christol, and Philippe Dumas. Fast computation of the N th
[BCD16]term of an algebraic series over a finite prime field. In Proceedings of the 2016
ACM International Symposium on Symbolic and Algebraic Computation, pages
119–126. ACM, New York, 2016.
[BCvH+ 17] A. Bostan, F. Chyzak, M. van Hoeij, M. Kauers, and L. Pech. Hypergeometricexpressions for generating functions of walks with small steps in the quarter
plane. European J. Combin., 61:242–275, 2017.
[BCvHP12] A. Bostan, F. Chyzak, M. van Hoeij, and L. Pech. Explicit formula for the generating series of diagonal 3D rook paths. Sém. Lothar. Combin., 66:Art. B66a, 27,
2011/12.
[Bri17]
A. Bridy. Automatic sequences and curves over finite fields. Algebra Number
Theory, 11:685–712, 2017.
[Chr79]G. Christol. Ensembles presque periodiques k-reconnaissables. Theoret. Comput.
Sci., 9:141–145, 1979.
[Chr90]G. Christol. Globally bounded solutions of differential equations. In Analytic
number theory (Tokyo, 1988), volume 1434 of Lecture Notes in Math., pages
45–64. Springer, Berlin, 1990.
[Chr15]
G. Christol. Diagonals of rational fractions. Eur. Math. Soc. Newsl., 97:37–43,
2015.
[CK91]David G. Cantor and Erich Kaltofen. On fast multiplication of polynomials overarbitrary algebras. Acta Inform., 28(7):693–701, 1991.
[CKMFR80] G. Christol, T. Kamae, M. Mendès France, and G. Rauzy. Suites algébriques,automates et substitutions. Bull. Soc. Math. France, 108:401–419, 1980.
[Del84]
P. Deligne. Intégration sur un cycle évanescent. Invent. Math., 76:129–143,
1984.

32

[Der07][DL87][FKdM00][Fur67][Ges82][Har88][Har89][Hod29][Hov78][MM16][Pan94][RY15][Sal86][Sal87][Str14][SW88][vdP93][VM21][VM23][WS89][Zan09]BORIS ADAMCZEWSKI, ALIN BOSTAN, AND XAVIER CARUSO

H. Derksen. A Skolem-Mahler-Lech theorem in positive characteristic and finite
automata. Invent. Math., 168:175–224, 2007.
J. Denef and L. Lipshitz. Algebraic power series and diagonals. J. Number Theory,
26:46–67, 1987.
J. Fresnel, M. Koskas, and B. de Mathan. Automata and transcendence in positive
characteristic. J. Number Theory, 80:1–24, 2000.
H. Furstenberg. Algebraic functions over finite fields. J. Algebra, 7:271–277,
1967.
I. Gessel. Some congruences for Apéry numbers. J. Number Theory, 14:362–368,
1982.
T. Harase. Algebraic elements in formal power series rings. Israel J. Math.,
63:281–288, 1988.
T. Harase. Algebraic elements in formal power series rings. II. Israel J. Math.,
67:62–66, 1989.
W. V. D. Hodge. The Isolated Singularities of an Algebraic Surface. Proc. London
Math. Soc. (2), 30(2):133–143, 1929.
A. G. Hovanskiı̆. Newton polyhedra, and the genus of complete intersections.
Funktsional. Anal. i Prilozhen., 12(1):51–61, 1978.
S. Melczer and M. Mishna. Asymptotic lattice path enumeration using diagonals.
Algorithmica, 75:782–811, 2016.
Victor Y. Pan. Simple multivariate polynomial multiplication. J. Symbolic Comput., 18(3):183–186, 1994.
E. Rowland and R. Yassawi. Automatic congruences for diagonals of rational
functions. J. Théor. Nombres Bordeaux, 27:245–288, 2015.
O. Salon. Suites automatiques à multi-indices. Sém. Théorie Nombres Bordeaux(1986-1987),, Exposé 4:1–27, 1986.
O. Salon. Suites automatiques à multi-indices et algébricité. C. R. Acad. Sci. ParisSér. I Math., 305:501–504, 1987.
A. Straub. Multivariate Apéry numbers and supercongruences of rational functions. Algebra Number Theory, 8:1985–2007, 2014.
H. Sharif and C. F. Woodcock. Algebraic functions over a field of positive characteristic and Hadamard products. J. London Math. Soc. (2), 37:395–403, 1988.
A. J. van der Poorten. Power series representing algebraic functions. In Séminairede Théorie des Nombres, Paris, 1990–91, volume 108 of Progr. Math., pages 241–262. Birkhäuser Boston, Boston, MA, 1993.
D. Vargas-Montoya. Algébricité modulo p, séries hypergéométriques et structuresde Frobenius fortes. Bull. Soc. Math. France, 149:439–477, 2021.
D. Vargas-Montoya. Monodromie unipotente maximale, congruences “à la Lucas”
et indépendance algébrique. arXiv:2103.15192 [math.NT], to appear in Trans.
Amer. Math. Soc., DOI: https://doi.org/10.1090/tran/8913, 2023.
C. F. Woodcock and H. Sharif. On the transcendence of certain series. J. Algebra,
121:364–369, 1989.
U. Zannier. Lecture notes on Diophantine analysis, volume 8 of Appunti. Scuola
Normale Superiore di Pisa (Nuova Serie) [Lecture Notes. Scuola Normale Superiore
di Pisa (New Series)]. Edizioni della Normale, Pisa, 2009.

A SHARPER MULTIVARIATE CHRISTOL’S THEOREM

33

B. A DAMCZEWSKI : U NIV. C LAUDE B ERNARD LYON 1, CNRS UMR 5208, I NSTITUT C AMILLEJ ORDAN , 43 BLVD . DU 11 NOVEMBRE 1918, F-69622 V ILLEURBANNE CEDEX , F RANCE
Email address: boris.adamczewski@math.cnrs.fr
A. B OSTAN : I NRIA , U NIVERSIT É PARIS -S ACLAY, 1 RUE H ONOR É D ’E STIENNE D ’O RVES ,91120 PALAISEAU, F RANCE
Email address: alin.bostan@inria.fr
X. C ARUSO : CNRS, IMB, U NIVERSIT É DE B ORDEAUX , 351 COURS DE LA L IB ÉRATION ,33405 TALENCE , F RANCE
Email address: xavier@caruso.ovh