A NOTE ON CHRISTOL’S THEOREMBORIS ADAMCZEWSKI AND REEM YASSAWI

Abstract. Christol’s theorem characterises algebraic power series over finite
fields in terms of finite automata. In a recent article, Bridy develops a new
proof of Christol’s theorem by Speyer, to obtain a tight quantitative version,that is, to bound the size of the corresponding automaton in terms of the heightand degree of the power series, as well as the genus of the curve associatedwith the minimal polynomial of the power series. Speyer’s proof, and Bridy’s
development, both take place in the setting of algebraic geometry, in particularby considering Kähler differentials of the function field of the curve. In thisnote we show how an elementary approach, based on diagonals of bivariate
rational functions, provides essentially the same bounds.

1. Introduction
The title of this paper refers to the following classical result of Christol.
Theorem 1.1 (Christol). Let q be a power of a prime number p and let f (x) =P∞nn=0 an x ∈ Fq [[x]]. Then f (x) is algebraic over Fq (x) if and only if the sequencea = (an )n≥0 is q-automatic.
Here, an infinite sequence a = (an )n≥0 is q-automatic if an is a finite-state function of the base-q expansion of n. This means that there exists a deterministic finite
automaton with output taking the base-q expansion of n as input, and producing
the symbol an as output. For a formal definition, we refer the reader to [AS03,
Chapter 5]. Christol’s theorem is easy to prove, but nevertheless deep, in the sensethat it provides an intimate connection between two apparently unrelated areas.
On the one hand, algebraic power series with coefficients over finite fields are fundamental for arithmetic in positive characteristic while, on the other hand, finite
automata are fundamental for computer science. On each side, there is a natural
way to measure the complexity of the corresponding objects. The complexity ofan algebraic power series f is measured by its degree d and its height h. Here,the degree of f is the degree of the field extension [Fq (x)(f (x)) : Fq (x)], while theheight of f is the minimal degree (in x) of a nonzero polynomial P (x, y) ∈ Fq [x, y]such that P (x, f (x)) = 0. With a more geometric flavor, one can also add the genus
g of the curve associated with the minimal polynomial of f . The complexity of aq-automatic sequence a, denoted by compq (a), is measured by the number of statesin a minimal finite automaton generating a in reverse reading, by which we meanthat the input n is read starting from the least significant digit. In Section 5, we
also discuss bounds in direct reading. By a result of Eilenberg [Eil74], a sequenceThis project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme under the Grant Agreement No
648132.
1

2

BORIS ADAMCZEWSKI AND REEM YASSAWI

a is q-automatic if and only if its q-kernel
kerq (a) = {(aqr n+j )n≥0 : r ≥ 0, 0 ≤ j < q r }is a finite set. By [AS03, Corollary 4.1.9 and Theorem 6.6.2], we have(1)

compq (a) = | kerq (a)|.

Thus we can bound the complexity of a by bounding | kerq (a)|.
We are interested here in the interplay between these two notions of complexity.
If a sequence a is generated by a q-automaton with at most m states, it is notdifficult to show that the associated power series f has degree at most q m − 1 andheight at most mq m+1 (see, for instance, [Bri17, Proposition 2.13]). Furthermore,these bounds cannot be significantly improved in general.
Bounds in the other direction are more challenging. If f is algebraic of degree2dd, the power series f, f q , f q , . . . , f q are linearly dependent over Fq (x) and thus
there exist polynomials A0 (x), . . . , Ad (x) ∈ Fq [x], not all zero, such that(2)dA0 (x)f (x) + · · · + Ad (x)f (x)q = 0 .

Furthermore, it is possible to ensure that A0 (x) 6= 0. Such a relation is called an
Ore relation for f . The standard proof of Christol’s theorem, which dates backto [CKMFR80], is based on such a relation, and is the proof given in Allouche
and Shallit’s book [AS03]. The arguments are effective and not particularly hardto quantify. Explicit bounds for compq (a) can be easily extracted from [Har88,
Har89, AB12], where the authors work in a more general framework (arbitrarybase fields of characteristic p and power series in several variables). The authorsof [FKdM00] also obtain a quantitative version of Christol’s theorem using similar
techniques. The common feature of all these bounds is that they have a doublykexponential nature1, that is, they are of the form q cq , where c and k are polynomial
functions of d and h. For, one can derive from (2) thatcompq (a) ≤ q d(2H+1) ,where H := max{deg Ai (x) : 0 ≤ i ≤ d} denotes the height of the Ore relation (2).
The double exponentiation appears because the upper bounds for H are alreadyexponential in q. For instance, the bound H ≤ 2hq d can be derived from [Har89];
see also [AB12].
In contrast, when f is a rational function (i.e. d = 1), one can easily obtain
the bound q h+1 and thus get rid of the double exponential. This suggests thatthe previous bounds are artificially large. In a recent paper, Bridy [Bri17] drastically improves on these doubly exponential bounds, confirming this guess. Moreprecisely, he obtains the following essentially sharp bound:(3)

compq (a) ≤ (1 + o(1))q h+d+g−1 ,where the o(1) terms 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), one can deduce that(4)

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

1Sharif and Woodcock [SW88] apparently realise that they can obtain effective bounds, though
they do not spell them out, and here again, they would be doubly exponential.

A NOTE ON CHRISTOL’S THEOREM

3

Bridy’s approach is based on a new proof of Christol’s theorem in the context ofalgebraic geometry, due to Speyer [Spe]. Speyer’s argument is elegant, connecting finite automata with the geometry of curves. Furthermore, Bridy’s bound (3)shows that this approach is also very efficient. However, the price to pay is thatsome classical background from algebraic geometry is needed: the Riemann-Rochtheorem, existence and basic properties of the Cartier operator acting on the spaceof Kähler differentials of the function field associated with f , along with asymptotic
bounds for the Landau function.
Here, we come back to Christol’s original argument [Chr79], which appears
slightly before [CKMFR80]. It is based on a result of Furstenberg [Fur67] showingthat any algebraic power series in Fq [[x]] can be expressed as the diagonal of rational power series in two variables. Using diagonals avoids the use of an Ore relation,
which is the culprit behind the double exponentiation. In the end, we obtain simply
exponential bounds similar to those of Bridy, though slightly weaker. For instance,
we can show that(5)compq (a) ≤ (1 + o(1))q (h+1)d+1 ,where the o(1) terms tends to 0 for large values of any of q, d, or h. Furstenberg’s
theorem has been studied and applied by a number of authors, for example byDenef and Lipshitz [DL87], the first author and Bell [AB13], the second author andRowland [RY15] and Bostan, Caruso, Christol, and Dumas in [BCCD19].
The purpose of this note is to publicize that using diagonals to prove Christol’s
theorem gives us essentially the same bounds as the theoretically more demanding
approach using the Riemann Roch theorem. Indeed, diagonals have already been
used, by the first author and Bell, to obtain a singly exponential bound [AB13,
Theorem 7.1]; here we simply push this technique to optimise the bounds. Also,
we point out that the methods that we describe here can also be applied to thestudy of algebraic functions of several variables, Hadamard products, and reduction modulo prime powers of diagonals of multivariate rational functions, includingtranscendental ones, with little extra theoretical cost.
2. Cartier operators and diagonals
We recall here some definitions and basic results about Cartier operators anddiagonals.
Pn2.1. One-dimensional Cartier operators. Let f (x) =n≥0 an x ∈ Fq [[x]].
For every natural number i, 0 ≤ i ≤ q − 1, we define Λi as the Fq -linear operator
acting on Fq [[x]] by:∞X
Λi (f (x)) =anq+i xn .
n=0

We let Ω1 denote the monoid generated by these operators under composition. In
the framework of Christol’s theorem, the operators Λi are usually called Cartier
operators (see, for instance, [AS03]). They are the tools with which one drops down
to the elements of kerq (a). Indeed, we can rephrase Equation (1) as(6)compq (a) = |Ω1 (f )|where Ω1 (f ) is the orbit of f (x) under the action of Ω1 . All known proofs of thesufficiency direction of Christol’s theorem have the same blueprint. One finds a
finite set that contains f (x), and which is invariant under the action of the Cartier

4

BORIS ADAMCZEWSKI AND REEM YASSAWI

operators. Usually, this set is an Fq -vector space, say V , and one just has to provethat it is finite dimensional. However, in order to obtain finer quantitative results,
it will be convenient to trace the orbit Ω1 (f ) more closely inside V , and in doing
so, we will lose the vector space structure.
Let us briefly recall why the Λi ’s are referred to as the Cartier operators. To
make the connection with the real Cartier operator C, which comes from algebraic
geometry, we redefine our operators as follows. For every natural number i, 0 ≤i ≤ p − 1, we let Λ0i be the Fq -linear operator acting on Fq [[x]] by:
!
∞
∞
X
X
1/p
0
n
an x
Λi
=
anp+i xn .
n=0

n=0

If q = p , we retrieve the operator Λi as a composition of r operators Λ0j . With
this notation, Λ0p−1 is reminiscent of C. Let f (x) ∈ Fq [[x]] be an algebraic power
series and let X denote the smooth projective algebraic curve, obtained after thenormalization of the projective closure of the affine plane curve defined by theminimal polynomial of f . Let Fq (X) denote the function field associated withX, and let ΩFq (X)/Fq denote the one-dimensional Fq (X)-vector space of Kähler
differentials of Fq (X). Choosing x to be a separating variable, i.e. x 6∈ Fq (X)p , wecan define C asr

(7)

C(f (x)dx) = Λ0p−1 (f (x))dx ,so that C acts on differentials exactly as Λp−1 acts on power series. In Speyer’s
proof of Christol’s theorem, a finite dimensional Fq -vector space, containing f andinvariant under Ω1 , is obtained first by finding an effective divisor D on X suchthatΩ(D) := ω ∈ ΩFq (X)/Fq \ {0} : (ω) + D ≥ 0 ∪ {0}is invariant under C and also the twisted Cartier operators, which play the roleof the other operators Λi , and then by using (7). The fact that Ω(D) has finite
dimension over Fq is a direct consequence of the Riemann-Roch theorem. Bridy
finds the best choice for the divisor D; he also has to trace the orbit of f (x)dx more
precisely under C and the twisted Cartier operators inside Ω(D).
2.2. Two-dimensional Cartier operators. The definition of the Cartier operators Λi naturally extends to power series in an arbitrary number of variables. We
recall here the two-dimensional case. Given (i, j) ∈ {0, 1, . . . , q − 1}2 , we let Λi,jdenote the Fq -linear operator acting on Fq [[x, y]] by:


X
X
(8)
Λi,j 
an,m xn y m  =anq+i,mq+j xn y m .
n,m≥0

n,m≥0

Analogous to the notation in one dimension, we let Ω2 denote the monoid generated
by the two-dimensional Cartier operators under composition. An elementary but
fundamental property of these operators is that(9)

Λi,j (f g q ) = Λi,j (f )g,

for all f, g ∈ Fq [[x, y]]. Notice that this useful equality also allows one to uniquely
extend Λi,j to the field of fractions of Fq [[x, y]] by setting Λ(f /g) := Λ(f g q−1 )/g.
Furthermore, if P ∈ Fq [x, y] then(10)degx Λi,j (P ) ≤ degx (P )/q and degy Λi,j (P ) ≤ degy (P )/q.

A NOTE ON CHRISTOL’S THEOREM

2.3. Diagonals. The diagonal of a power series f (x, y) =Fq [[x, y]] is defined by∞X∆(f )(x) =an,n xn .

5Pn,m≥0 an,m x

n m

y

∈

n=0

It is straightforward to check that(11)

Λi (∆(f )) = ∆(Λi,i (f )) ,for all f (x, y) ∈ Fq [[x, y]]. Furstenberg [Fur67] proved that any algebraic power
series in Fq [[x]] is the diagonal of a bivariate rational power series. His proof isbased on the following key formula [Fur67, Proposition 2].
Lemma 2.1 (Furstenberg). Let K be a field and let P (x, y) ∈ K[x, y]. Let f (x) ∈K[[x]] be a root of P (x, y). If f (0) = 0 and ∂P∂y (0, f (0)) 6= 0, then!
∂Py ∂y (xy, y)f (x) = ∆(12)·
y −1 P (xy, y)
The proof of this lemma is both easy and elementary, though it took Furstenberg’s insight to find the rational function in the right hand side of (12). Though theformula is valid over any field, it has its roots firmly planted in residue theory, where
we can express an algebraic function as an integral of a certain rational function.
Precisely, suppose that P (0, 0) = 0 and that 0 is an isolated root of P (0, y) = 0.
These conditions guarantee that there is a unique power series y = f (x) that converges close to the origin, and satisfying both P (x, f (x)) = 0 and f (0) = 0. By
Cauchy’s generalised residue theorem, one can express
Z y ∂P (x, y)
1
∂y
(13)
f (x) =dy
2πi γ P (x, y)for γ and |z| sufficiently small. On the other hand, if g(x, y) ∈ C[[x, y]], then ∆(g)is also a residue that can be simply expressed as
Z
1
dw
(14)
∆(g) =
g(x/w, w))
·
2πi γ
w
Now (13) and (14) allow us to deduce (12).
3. The smooth caseIn this section, we first describe our strategy in the smooth case and show how
it easilyPleads to simply exponential bounds. By the smooth case, we mean thatf (x) = n≥0 an xn ∈ xFq [[x]] is an algebraic power series whose minimal polynomial P (x, y) satisfies Furstenberg’s condition: ∂P∂y (0, 0) 6= 0. This conditions ensuresthat the plane algebraic curve associated with P is nonsingular at the origin.
By Furstenberg’s formula, there exists an explicit rational power series P/Q ∈Fq (x, y) such that f = ∆(P/Q). Let m be an upper bound for the degree in x andy of the polynomials P and Q. Then
W := A/Q : max(degx (A), degy (A)) ≤ m
is a Fq -vector space of dimension (m + 1)2 . Furthermore, W is invariant under Ω2 .
Indeed, Λi,j (A/Q) = Λi,j (AQq−1 )/Q and it follows from (10) thatdegx (Λi,j (AQq−1 )) ≤ m and degy (Λi,j (AQq−1 )) ≤ m .

6

BORIS ADAMCZEWSKI AND REEM YASSAWI

Thus we deduce from (11) that Ω1 (f ) ⊂ ∆(W ). Since ∆ is linear, ∆(W ) is an
Fq -vector space of dimension at most (m + 1)2 . Furthermore, if f has degree d andheight h, Furstenberg’s formula shows that we can choose m = h + d. Then we getfrom Equality (6) that2|Ω1 (f )| ≤ q (h+d+1) ,which is already an acceptable simply exponential bound.
In the next theorem, we refine the previous argument to obtain a bound that is
only very slightly weaker than the one given by Bridy in (4).
P
Theorem 3.1. Let f (x) = n≥0 an xn ∈ xFq [[x]] be an algebraic power series ofdegree d and height h, and let P (x, y) ∈ Fq [x, y] denote the minimal polynomial off . If ∂P∂y (0, 0) 6= 0, thencompq (a) ≤ 1 + q (h+1)d .
Pdi
Proof. Let P (x, y) =i=0 Ai (x)y . By assumption, we have A0 (0) = 0 and
A1 (0)) 6= 0. This implies that y divides P (xy, y). By Lemma 2.1, we have!
y ∂P∂y (xy, y)(15)f (x) = ∆.
y −1 P (xy, y)Consider the three Fq -vector spaces(16)
U := spanFq (xy)i y j : 0 ≤ i ≤ qh, 0 ≤ j ≤ qd − 1 ,V := spanFq (xy)i y j : 0 ≤ i ≤ h, 0 ≤ j ≤ d − 1 ,(xy)i y j
W := spanFq: 0 ≤ i ≤ h, 0 ≤ j ≤ d − 1 .
y −1 P (xy, y)Let ` ∈ {0, . . . , q − 1}. For any u ∈ U , note that Λ`,` (u) ∈ V . We claim thatΛ` (f ) ∈ ∆(W ). For, using Properties (11) and (9), we have
q−1 
(xy, y) y −1 P (xy, y)
y ∂P
∂y

Λ` ∆ 
q(y −1 P (xy, y))q−1 
−1
P (xy, y)∆ Λ`,` y ∂P∂y (xy, y) yΛ` (f )==y −1 P (xy, y)

·

q−1
−1
P (xy, y)is an Fq -linear comNow notice that the polynomial y ∂P∂y (xy, y) yi jbination of monomials in the set {(xy) y : 0 ≤ i ≤ qh, 2 − q ≤ j ≤ (d − 1)q + 1}.
Notice also that if j 6≡ 0 mod q, then Λ`,` ((xy)i y j ) = 0 for any `. This implies
that the image of this last set under Λ`,` is the same as that of U , so


q−1
∂P
Λ`,` y(xy, y) y −1 P (xy, y)∈ Λ`,` (U ) ⊂ V,∂yand this proves our claim that Λ` (f ) ∈ ∆(W ). The same reasoning shows that∆(W ) is invariant under Ω1 . Since Λ` (f ) ∈ ∆(W ) for all ` ∈ {0, . . . , q − 1}, itfollows that Ω1 (f ) \ {f } is a subet of (xy)i y j∆(W ) = spanFq ∆
:
0
≤
i
≤
h,
0
≤
i
≤
d
−
1
,
y −1 P (xy, y)which has dimension at most (h + 1)d over Fq . The result follows.

A NOTE ON CHRISTOL’S THEOREM

7

4. The general case
The aim of this section is to remove the assumption needed in Furstenberg’s
formula, proving the following general bound.
P
Theorem 4.1. Let f (x) = n≥0 an xn ∈ Fq [[x]] be an algebraic power series ofdegree d and height h. Thencompq (a) ≤ (1 + o(1))q (h+1)d+1 ,where the o(1) term tends to 0 for large values of any of q, h, or d.
P
Notation. Throughout this section, we let f (x) = n≥0 an xn ∈ Fq [[x]] denotean algebraic power series of degree d and height h, and we let P (x, y) denote its
minimal polynomial. Also we fix r to be the order at 0 of the resultant of P (x, y)and ∂P∂y (x, y). By the determinantal formula for the resultant, we haver ≤ h(2d − 1).

(17)
We definerX

an xn ,Vr (x):=

f (r) (x):= x−r (f (x) − Vr (x)) ∈ xFq [[x]] ,

n=0

(18)

Mr (x, y):= Vr (x) + xr y , andQr (x, y):= P (x, Mr (x, y)) ∈ Fq [x; y].

Notice that(19)f (r) (0) = 0 and Qr (x, f (r) (x)) = 0 .

The following elementary argument shows that f (r) is the only power series rootof Qr with no constant term. The proof follows the argument given in [AB13, proof
of Lemma 6.2]; we include it for the sake of completeness.
Lemma 4.2. There exists a nonnegative integer s such that x−s Qr (x, y) is a poly−s
nomial satisfying the condition of Furstenberg’s formula, that is ∂(x ∂yQr ) (0, 0) 6= 0,
so that!
ry ∂Q∂y (xy, y)(r)·f (x) = ∆y −1 Qr (xy, y)Pd
Proof. Let S(x) denote the resultant of P (x, y) = i=0 Ai (x)y i and ∂P∂y (x, y), sothat S(x) = xr T (x) with T (0) 6= 0. To simplify notation, let V (x) := Vr (x),g(x) := f (r) (x), and Q := Qr . Setting
Bi (x) :=1 ∂iP(x, V (x)) ,i! ∂y iwe get that
Q(x, y) =dXi=0Bi (x)xri y i .

8

BORIS ADAMCZEWSKI AND REEM YASSAWI

Note that
P (x, V (x))

with C(x) =Pd

i=1 Ai (x)= P (x, V (x)) − P (x, f (x))= (V (x) − f (x))C(x)= −xr g(x)C(x) ,

i−1
k
i−k−1
V
(x)
f
(x)
∈ Fq [[x]]. Thus xr+1 divides
k=0

P

P (x, V (x)), as g(0) = 0. On the other hand, since S is the resultant of P and ∂P∂y ,there exist two polynomials A(x, y) and B(x, y) such thatxr T (x) = A(x, y)P (x, y) + B(x, y)∂P(x, y) .
∂y

It follows that
B(x, V (x))∂P
(x, V (x)) = xr T (x) − A(x, V (x))P (x, V (x)) ,∂ywhich implies that ν ≤ r, where ν denotes the order at 0 of B1 (x) = ∂P∂y (x, V (x)).
ri
Since the order of Bi (x)x ≥ 2r for all i such that 2 ≤ i ≤ d, we obtain that theorder of B0 (x) at 0 is at least equal to s := ν + r. It follows that x−s Q(x, y) is apolynomial such that∂(x−s Q)(x, 0) = B1 (x)x−ν∂y−s

and thus ∂(x∂y Q) (0, 0) 6= 0, as desired. By (19), we can apply Furstenberg’s Lemma
to f (r) and x−s Q(x, y), which provides the expected formula.

The idea behind proving Theorem 4.1 is to find successively shrinking vector
spaces to which most of Ω1 (f ) belongs. Iterating the following two lemmas willallow us to achieve this shrinkage. In the lemmas that follow we continue with thenotation given in (18).
Lemma 4.3. Let ` ∈ {0, . . . , q − 1}, let α be a rational number with 0 ≤ α ≤ r,
and let(xy)i Mr (xy, y)j(20) Vr,α := spanFq: r − α ≤ i ≤ r + h, 0 ≤ j ≤ d − 1 .
y −1 Qr (xy, y)Then we have(i) Λ`,` (Vr,α ) ⊂ Vr, αq +1− q1 ,(ii) Vr,α = Vr,0 if α < 1, and(iiii) Λ`,` (Vr,0 ) ⊂ Vr,0 .
Furthermore, if ` ≤ q − 2 then Λ`,` (Vr,1 ) ⊂ Vr,0 .
Proof. Note that (i) and (ii) implies (iii), while (ii) is trivial, so we just have toprove (i). Let i and j be two integers with(21)r − α ≤ i ≤ r + h and 0 ≤ j ≤ d − 1 ,so that(xy)i Mr (xy, y)j∈ Vr,α .
y −1 Qr (xy, y)A NOTE ON CHRISTOL’S THEOREM

9

We first infer from (9) thatΛ`,` (xy)i Mr (xy, y)j y 1−q Qr (xy, y)q−1(xy)i Mr (xy, y)j
=
(22)
Λ`,`
.
y −1 Qr (xy, y)y −1 Qr (xy, y)
Developing Qr (xy, y)q−1 , we note that (xy)i Mr (xy, y)j y 1−q Qr (xy, y)q−1 is an Fq linear combination of elements of the form y 1−q (xy)i+n Mr (xy, y)j+m where 0 ≤n ≤ (q − 1)h and 0 ≤ m ≤ d(q − 1). Setting i0 = i + n and j 0 = j + m, we obtain(23)r − α ≤ i0 ≤ r + qh and 0 ≤ j 0 ≤ qd − 1 .

Recall that Λ`,` (xa y b ) is nonzero if and only if a ≡ b ≡ ` mod q. Using Property
00(9), we obtain that either Λ`,` (y 1−q (xy)i Mr (xy, y)j ) = 0, or00Λ`,` (xy)i y 1−q Mr (xy, y)j

∗
=



j0
0
0
Λ`,` (xy)i y 1−q (Mr (xy, y)j mod q Mr (xy, y)b q cj00Λ`,` (xy)i (xy)r(q−1) Mr (xy, y)b q c

=

(xy)

=

(24)

i0 +r(q−1)−`qj0

Mr (xy, y)b q c ,where the asterisked equality follows because the only way this expression is nonzero
is if j 0 ≡ q − 1 mod q, and in this case only the (xy)r(q−1) y q−1 term in Mr (xy, y)q−1
will lead to a nonzero term after application of Λ`,` . By (23), we have(25) 0 ≤ bj 0 /qc ≤ d − 1 and r − (α/q + 1 − 1/q) ≤i0 + r(q − 1) − `≤ r + h,q

and we infer from (22) and (24) that Λ`,` (Vr,α ) ⊂ Vr,α/q+1−1/q . Finally, inspectionof the case ` < q − 1 and α = 1 gives us Λ`,` (Vr,1 ) ⊂ Vr,0 .

We also have the following similar result.
Lemma 4.4. Let(xy)i Mr (xy, y)j+Vr,α:= spanFq
:
r
−
α
≤
i
≤
r
+
h
−
1,
0
≤
j
≤
d
−
1
.
y −1 Qr (xy, y)Then+(i’) Λ`,` (Vr,α) ⊂ Vr,+α +1− 1 ,qq+(ii’) Vr,α= V0+ if α < 1, and++(iii’) Λ`,` (Vr,0) ⊂ Vr,0.

Furthermore, if ` ≥ 1 then Λ`,` (Vr,α ) ⊂ Vr,+α +1− 1 .
qq

Proof. The proof of (i’), (ii’), and (iii’) follows the same argument as in the proof of
Lemma 4.3. The fact that Λ`,` (Vr,α ) ⊂ Vr,+α +1− 1 when ` ≥ 1 is a direct consequenceqqof (25), since i0 + r(q − 1) − `/q < r + h when ` ≥ 1.

Lemma 4.5. Let ` ∈ {0, . . . , q − 1}. Then Λ` (f (r) ) ∈ ∆(Vr, rq +1− q1 ). Furthermore,
if ` ≥ 1, then Λ` (f (r) ) ∈ ∆(Vr,+r +1− 1 ).
q

q

10

BORIS ADAMCZEWSKI AND REEM YASSAWIProof. To simplify notation we let V (x) := Vr (x), g(x) := f (r) (x), and Q := Qr .
Let M (x, y) = V (x) + xr y, so that g(x) is a root of the polynomial Q(x, y) :=Pdk
k=0 Ak (x)M (x, y) . By Lemma 4.2, we have!
y ∂Q∂y (xy, y)(26)g(x) = ∆·y −1 Q(xy, y)Let ` ∈ {0, . . . , q − 1}. We first infer from (9) that
!
2−q ∂Q
q−1
∂Q
Λ
y
(xy,
y)Q(xy,y)`,`y ∂y (xy, y)
∂y
=
·
(27)
Λ`,`
y −1 Q(xy, y)y −1 Q(xy, y)
q−1
belongs to
Notice that ∂Q∂y (xy, y)Q(xy, y)ispanFq (xy) M (xy, y)j : r ≤ i ≤ r + qh, 0 ≤ j ≤ qd − 1 .

Let i and j be two such integers. Equality (9) implies thatj(28) Λ`,` y 2−q (xy)i M (xy, y)j = Λ`,` y 2−q (xy)i M (xy, y)j mod q M (xy, y)b q cand thus either Λ`,` y 2−q (xy)i M (xy, y)j = 0 or Λ`,` y 2−q (xy)i M (xy, y)j mod q 6=0, which is only possible if j ≡ q − 2 mod q or j ≡ q − 1 mod q. Continuing from(28), if j ≡ q − 2 mod q,i+(q−2)r−`jqΛ`,` y 2−q (xy)i M (xy, y)j = (xy)M (xy, y)b q c ,and if j ≡ q − 1 mod q,jΛ`,` y 2−q (xy)i M (xy, y)j = −Λ`,` (xy)i+(q−2)r V (xy) M (xy, y)b q c .
In all cases, Λ`,` y 2−q (xy)i M (xy, y)j belongs tono00
spanFq (xy)i M (xy, y)j : r − r/q − `/q ≤ i0 ≤ r + h − `/q, 0 ≤ j 0 ≤ d − 1 .
Combining this with (27), we get that
Λ`,`

y ∂Q
∂y (xy, y)!
∈ Vr, rq +1− q1 .

y −1 Q(xy, y)

Furthermore if ` ≥ 1, we see that
Λ`,`

y ∂Q
∂y (xy, y)y −1 Q(xy, y)!
∈ Vr,+r +1− 1 .
qq

By Equalities (11) and (26), this ends the proof.

Before proving Theorem 4.1, we need a last auxiliary result, which gives theintertwining relations between the operators Λ` and multiplication by a power of
x. Its proof is straightforward.
Lemma 4.6. Let 0 ≤ j ≤ q − 1 and 0 ≤ ` ≤ q − 1. Then(Λ`−j (f (x))
if j ≤ `jΛ` (x f (x)) =xΛq+`−j (f (x)) if j > `.
Note in particular that Lemma 4.6 implies that Λn0 (xf (x)) = xΛnq−1 (f (x)) for
each n > 0.

A NOTE ON CHRISTOL’S THEOREM

11

Proof of Theorem 4.1 . Recall thatf (x) = a0 + a1 x + · · · + ar xr + xr f (r) (x) .
Lemma 4.5 implies that Λ` (f (r) ) ∈ ∆(Vr, rq +1− q1 ) for all ` and that Λ` (f (r) ) ∈∆(Vr,+r +1− 1 ) if ` ≥ 1. Let
q

(29)

q

t0 = blogq rc .

Using Properties (9) and (10), we obtain that for t ≥ t0 , for any (`t , . . . `0 ), there
is a unique (`˜t , . . . `˜0 ) and a unique i ∈ {0, 1} such thatΛ`t Λ`t−1 · · · Λ`0 (xr f (r) ) = xi Λ`˜t Λ`˜t−1 · · · Λ`˜0 (f (r) ).
Iterating Lemmas 4.3 and 4.4, we have:(a) If `t q t + `t−1 q t−1 + · · · + `1 q + `0 > r, then+Λ`t Λ`t−1 · · · Λ`0 (f ) = Λ`˜t Λ`˜t−1 · · · Λ`˜0 (f (r) ) ∈ ∆(Vr,0),

as for at least one j ≥ t0 , we have `˜j is nonzero, so that we can apply
Lemma 4.4.
(b) If `t q t + `t−1 q t−1 + · · · + `1 q + `0 = r, then(r)Λ`t Λ`t−1 · · · Λ`0 (f ) = ar + Λt+1
) ∈ Fq + ∆(Vr,0 ) .
0 (f(c) If `t q t + `t−1 q t−1 + · · · + `1 q + `0 < r, then+Λ`t Λ`t−1 · · · Λ`0 (f ) = α + xΛ`˜t Λ`˜t−1 · · · Λ`˜0 (f (r) ) ∈ Fq + x∆(Vr,1),

since `˜t = p − 1 for j ≥ t0 , so that we can apply Lemmas 4.3 and 4.4.
We stress that `t can be zero, so that each of cases (b) and (c) can correspondto arbitrarily long compositions of Cartier operators. Notice that+x∆(Vr,1)=+∆(xyVr,1)=∆(Vr,0 ) .

+Meanwhile, ∆(Vr,0) ⊂ ∆(Vr,0 ), so that the total contribution from (a), (b) and (c)combined is of dimension at most (h + 1)d + 1.
On the other hand, defining(30)

E(f ) = {Λ`t · · · Λ`0 (f ) : t < t0 } ,we claim that |E(f )| = o(1)q hd , where the the o(1) term tends to 0 for large valuesof any of q, d, h. Indeed, |E(f )| ≤ q t0 , while by (17) we have r ≤ h(2d − 1). Hence
Equality (29) gives the claim. We conclude that|Ω1 (f )| ≤ q (h+1)d+1 + o(q hd ).
Now (6) completes the proof of Theorem 4.1.



Remark 4.7. Note that in the smooth case r = 0, there is no contribution from(c) above, and, since a0 = 0, we have Ω1 (f )\{f } ⊂ ∆(V0,0 ), so that we recover
Theorem 3.1. Also for the smooth case, (b) is precisely the orbit of f under Λ0 ,and Bridy deals with this orbit by showing that its cardinality is at most o(q hd );this is where Bridy uses additional arguments involving Landau’s function.

12

BORIS ADAMCZEWSKI AND REEM YASSAWI

Similarly, in the general case, Cases (b) and (c) correspond to r+1 infinite orbits,
all of whose size could be bounded by Bridy’s arguments. This should lead toΩ1 (f )= |∆(Vr , 0+ )| + o(q hd )=(1 + o(1))q hd ,which is precisely Bridy’s bound (4). This would have identified (a) as containing
the bulk of f ’s kernel. However it is not clear how to bound the contributions from(b) and (c) in an elementary fashion.
5. Bounds for the direct reading complexity
A sequence a = (an )n≥0 can be q-automatic in either reverse or direct reading.
In the former case, we feed the base-q expansion of n into the q-automaton startingwith the least significant digit, and in the latter, starting with the most significant
digit. Now a is q-automatic in direct reading if and only if it is q-automatic inreverse reading, but the direct and reverse reading minimal automata that generate
a are generally different and thus there are two notions of complexity; thus far wehave bounded the reverse complexity compq (a). We now wish to bound the forward−→
reading complexity compq (a), which equals the number of states in a minimal q←−
automaton generating a. For the sake of symmetry, henceforth we write compq (a)instead of compq (a).
If we start with a reverse reading q-automaton whose states are labelled using
elements of an Fq -vector space of dimension k, then using basic duality theory forvector spaces, we obtain the following result.
P∞n
Proposition 5.1. Let f (x) =n=0 an x ∈ Fq [[x]]. If there exists a Fq -vector
space V of dimension m that contains f and that is invariant under the action of−→←−Ω1 , then both compq (a) and compq (a) are bounded by q m .
Proposition 5.1 is a rephrasing of Proposition 2.4 in [Bri17], where Bridy uses
the notion of a q-presentation for the sequence a. This concept is analogous to thenotion of a recognizable rational series, which follows from the fact that a deterministic finite automaton with output in a finite field can be seen as a weighted
automaton, so that its rational series is recognizable [BR11].
Bridy shows that he can inject Ω1 (f ) into a vector space of dimension (h + 1)d,−→so that he bounds compq (a) by q (h+1)d . Here too our bounds are only slightly
weaker, particularly in the smooth case.
P
Corollary 5.2. Let f (x) = n≥0 an xn ∈ Fq [[x]] be an algebraic power series ofdegree d and height h, and let P (x, y) ∈ Fq [x, y] denote the minimal polynomial off.
−→

1+(h+1)d(i) If ∂P.
∂y (0, 0) 6= 0 and f (0) = 0, then compq (a) ≤ q(ii) Otherwise, let r be the order at 0 of the resultant of P (x, y) and ∂P∂y (x, y).
−→−→Then compq (a) ≤ q 1+(h+1)d+r . In particular, compq (a) ≤ q (3h+1)d−h+1 .
Proof. We first prove (i), which corresponds to the smooth case. The proof of
Theorem 3.1 tells us that we can realise most of Ω1 (f ) in the Fq -vector space ∆(W )where W is defined in (16), of dimension (h + 1)d. The only element of Ω1 (f )\W isf itself. Thus we add f to ∆(W ), to obtain a vector space of dimension 1 + (h + 1)dinto which we have injected Ω1 (f ). Applying Proposition 5.1 gives the result.

A NOTE ON CHRISTOL’S THEOREM

13

In the general case, an inspection of the last part of the proof of Theorem 4.1
tells us that the vector space ∆(Vr,0 ), defined in Lemma 4.3 contains most of Ω1 (f ).
Here, we have to add another basis element, representing the addition of constantsin the expression Fq + ∆(Vr,0 ). We must also add (at most) r basis elements, torepresent the set E(f ) defined in (30). The result follows form Proposition 5.1 andthe bound in (17).

6. Linking the genus to our setting
Let P (x, y) ∈ Fq [x, y], let P be the Newton polygon of P (x, y), and let gP be thenumber of integral points in the interior of P. We recall that gP is closely related to
the genus g of the curve associated with P . In a majority of cases we have gP = g,
and in general g ≤ gP . For example, if P (x, y) is irreducible over every algebraic
extension of Fq , then this follows by work of Beelen [Bee09].
If f (x) ∈ Fq [[x]] is a root of P (x, y) ∈ Fq [x, y] of degree d and height h, thengP ≤ (h − 1)(d − 1). Bridy’s bound (3) is better than his general bound (4) when
the genus is smaller than (h − 1)(d − 1). In our case too, if gP < (h − 1)(d − 1),then it is possible to obtain better bounds: we can choose smaller vector spaces towork with, taking into account the shape of P, instead of the full rectangular basesthat we have in (16) or (20).
Acknowledgement
The second author is grateful to Peter Beelen for a discussion of his work. She
also thanks IRIF, Université Paris Diderot-Paris 7, for its hospitality and support.
References[AB12]

Boris Adamczewski and Jason P. Bell. On vanishing coefficients of algebraic power
series over fields of positive characteristic. Invent. Math., 187(2):343–393, 2012.
[AB13]
Boris Adamczewski and Jason P. Bell. Diagonalization and rationalization of algebraic Laurent series. Ann. Sci. Éc. Norm. Supér. (4), 46(6):963–1004, 2013.
[AS03]
Jean-Paul Allouche and Jeffrey Shallit. Automatic Sequences: Theory, Applications,
Generalizations. Cambridge University Press, Cambridge, 2003.
[BCCD19] Alin Bostan, Xavier Caruso, Gilles Christol, and Philippe Dumas. Fast coefficientcomputation for algebraic power series in positive characteristic. volume 2, pages
119–135, 2019.
[Bee09]Peter Beelen. A generalization of Baker’s theorem. Finite Fields Appl., 15(5):558–
568, 2009.
[BR11]
Jean Berstel and Christophe Reutenauer. Noncommutative rational series with applications, volume 137 of Encyclopedia of Mathematics and its Applications. Cambridge
University Press, Cambridge, 2011.
[Bri17]
Andrew Bridy. Automatic sequences and curves over finite fields. Algebra Number
Theory, 11(3):685–712, 2017.
[Chr79]Gilles Christol. Ensembles presque periodiques k-reconnaissables. Theoret. Comput.
Sci., 9(1):141–145, 1979.
[CKMFR80] Gilles Christol, Teturo Kamae, Michel Mendès France, and Gérard Rauzy. Suitesalgébriques, automates et substitutions. Bull. Soc. Math. France, 108(4):401–419,
1980.
[DL87]
J. Denef and L. Lipshitz. Algebraic power series and diagonals. J. Number Theory,26(1):46–67, 1987.
[Eil74]
Samuel Eilenberg. Automata, languages, and machines. Vol. A. Academic Press [Asubsidiary of Harcourt Brace Jovanovich, Publishers], New York, 1974. Pure andApplied Mathematics, Vol. 58.
[FKdM00] Jean Fresnel, Michel Koskas, and Bernard de Mathan. Automata and transcendence
in positive characteristic. J. Number Theory, 80(1):1–24, 2000.

14[Fur67][Har88][Har89][RY15][Spe][SW88]BORIS ADAMCZEWSKI AND REEM YASSAWIHarry Furstenberg. Algebraic functions over finite fields. J. Algebra, 7:271–277, 1967.
Takashi Harase. Algebraic elements in formal power series rings. Israel J. Math.,
63(3):281–288, 1988.
Takashi Harase. Algebraic elements in formal power series rings. II. Israel J. Math.,
67(1):62–66, 1989.
Eric Rowland and Reem Yassawi. Automatic congruences for diagonals of rational
functions. J. Théor. Nombres Bordeaux, 27(1):245–288, 2015.
Christol’s theorem and the Cartier operator. https://sbseminar.wordpress.com/
2010/02/11/christols-theorem-and-the-cartier-operator/. Accessed: 2010-0930.
Habib Sharif and Christopher F. Woodcock. Algebraic functions over a field of positive characteristic and Hadamard products. J. London Math. Soc. (2), 37(3):395–
403, 1988.

Université de Lyon, Université Claude Bernard Lyon 1, CNRS UMR 5208, Institut
Camille Jordan, F-69622 Villeurbanne Cedex, France
E-mail address: boris.adamczewski@math.cnrs.fr
Université de Lyon, Université Claude Bernard Lyon 1, CNRS UMR 5208, Institut
Camille Jordan, F-69622 Villeurbanne Cedex, France
E-mail address: yassawi@math.univ-lyon1.fr