## Christol’s theorem and the Cartier operator February 11, 2010

Posted by David Speyer in Algebraic Geometry, characteristic p, Number theory.

Let’s suppose that we want to compute $2^n \mod p$, and we have already been given $n$ written out in base $p$ as $n = \sum n_i p^i$. Here $p$ is a small prime and we want to do this conversation repeatedly for many $n$‘s.

Remember that $2^p \equiv 2 \mod p$ and thus $2^n \equiv 2^{n_0+n_1 p + n_2 p^2 + \cdots + n_{\ell} p^{\ell}} \equiv 2^{n_0} 2^{n_1} \cdots 2^{n_{\ell}} \mod p$. So, start with $1$, multiply it by $2^{n_0}$, then by $2^{n_1}$, then by $2^{n_2}$ and so forth. When you get to the end, read off $2^n$.

We can precompute the effect on $\mathbb{F}_p$ of multiplying by $2^k$, for $0 \leq k \leq p-1$. Then we can compute $2^n$ just by scanning across the base $p$ representation of $n$ and applying these precomputed maps to the finite set $\mathbb{F}_p$.

The precise way to say that this is a simple, one-pass, process is that it is a computation which can be done by a finite-state automaton. Here is the definition: let $I$, $S$ and $O$ be finite sets (input, states and output), and $s \in S$ (the start). For each $i \in I$, let $A(i)$ be a map $S \to S$. We also have a map $r:S \to O$ (readout). Given a string $(i_0, i_1, \ldots, i_{\ell})$ in $I^{\ell}$, we compute $r( A(i_{\ell}) \circ \cdots A(i_1) \circ A(i_0) (s))$. So our input is a string of characters from $I$, and our output is in $O$.

We can say that our example above shows that $(n_{\ell}, \ldots, n_1, n_0) \mapsto 2^{\sum n_i p^i} \mod p$ is computable by a finite-state automaton. (In our example, the sets $I$, $S$ and $O$ all have cardinality $p$, but I do not want to identify them.)

This is a special case of an amazing result of Christol et al: Let $f_n$ be a sequence of elements of $\mathbb{F}_p$. Then $(n_{\ell}, \ldots, n_1, n_0) \mapsto f_{\sum n_i p^i}$ can be computed by a finite-state automaton if and only if the generating function $\sum f_n x^n$ is algebraic over $\mathbb{F}_p(x)$!

We have just explained the case $\sum f_n x^n = 1/(1-2x)$. The reader might enjoy working out the cases $1/(1-x-x^2)$ (the Fibonacci numbers) and $(1 - \sqrt{1-4x})/2x$ (the Catalans).

In this post, I will use Christol’s theorem as an excuse to promote the Cartier operator, an amazing tool for working with differential forms in characteristic $p$.

## Reformulating the problem

Let $f$ be a power series in $\mathbb{F}_p[[ x ]]$. Define the power series $s_0(f)$, $s_1(f)$, …, $s_{p-1}(f)$ by $f(x) = \sum_{i=0}^{p-1} x^i s_i(f)(x^p)$. So $s_i( 1/(1-2x)) = 2^i/(1-2^p x) = 2^i/(1-2x)$. Notice that $g(x^p) = g(x)^p$ for $g \in \mathbb{F}_p[[ x ]]$. It will be convenient for future generalization to write the defining equation of the $s_i$‘s as

$\displaystyle{f(x) = \sum_{i=0}^{p-1} x^i s_i(f)(x)^p}. \quad (*)$.

Let $\mathfrak{S}(f)$ be the set of all power-series which can be obtained from $f$ by applying the operators $s_i$ finitely many times. So $\mathfrak{S}(f)$ consists of $f$, $s_0 \ f$, …, $s_{p-1} f$, $s_0 s_0 \ f,$, $s_1 s_0\ f$, …, $s_{p-1} s_{p-1} f$, $s_0 s_0 s_0 \ f$ and so forth.

Please stare at the following claim until it is obvious to you: The function $(n_{\ell}, \ldots, n_1, n_0) \mapsto f_{\sum n_i p^i}$ can be computed by an FSA if and only if the set $\mathfrak{S}(f)$ is finite. Indeed, in that case, we can take $S = \mathfrak{S}(f)$.

Thus, Christol’s theorem is that $\sum f_n x^n$ is algebraic if and only if $\mathfrak{S}(f)$ is finite. It is convenient to generalize from $\mathbb{F}_p$ to an arbitrary perfect field $k$ of characteristic $p$. We continue to define the operators $s_i$ by equation $(*)$. So, for example, if $a$ is some element of $k$, then $s_i(1/(1-ax)) = a^{i/p}/(1-ax)$.

The right generalization of Christol’s theorem is then the following: $\sum f_n x^n$ is algebraic over $k(x)$ if and only if the $k$-vector subspace of $k[[x]]$ spanned by $\mathfrak{S}(f)$ is finite dimensional. Obviously, this reduces to Christol’s theorem when $k=\mathbb{F}_p$.

If $k \cdot \mathfrak{S}(f)$ is finite dimensional, it is fairly easy to see that $f$, and in fact all of $k \cdot \mathfrak{S}(f)$, must be algebraic. Taking $y_1$, …, $y_s$ a basis for $k \cdot \mathfrak{S}(f)$. we have $s$ equations of the form

$y_n = \sum x^i \left( \sum a_{imn} y_m \right)^p$

for constants $a_{imn}$ in $k$. These are $s$ polynomial equations in $s$ variables with coefficients in $k(x)$. One can show that the solution $(y_1, \ldots, y_s)$ is isolated and is therefore algebraic over $k(x)$.

We will now focus on the other direction. Let $K$ be a finite extension of $k(x)$, contained in $k (( x ))$, and let $f \in K$. We need to show that $k \mathfrak{S}(f)$ is finite dimensional.

## Surprising fact: $s_i$ takes $K$ to itself

Nothing like this is true in characteristic $0$. Working over $\mathbb{C}$, if we extract the terms with exponent divisible by $p$ from the power series $f:=\sqrt{1+x}$, we get $g:=(1/p) \sum_{j=0}^{p-1} \sqrt{1+\zeta^j x}$, where $\zeta$ is a primitive $p$-th root of unity. Although $g$ is algebraic over $\mathbb{C}(x)$, it is not in $\mathbb{C}(x)(f)$.

In orer to show $s_i(K) \subseteq K$, it is enough to do the case $i=p-1$, as $s_i(f) =s_{p-1}(x^{p-1-i} f)$.
We have the formula

$\displaystyle{s_{p-1}(f) = \sqrt[p]{\frac{1}{(p-1)!} \frac{\partial^{p-1} f}{(\partial x)^{p-1}}}}. \quad (**)$

Since $K \subset k((x))$, the extension $K/k(x)$ is separable (exercise!). We can use this to show that $\partial/\partial x$ takes $K$ to itself. The proof is simply implicit differentiation: Any $f \in K$ satisfies a polynomial relation $F(f,x)=0$. So $\partial f/\partial x = -F_2(f,x)/F_1(f,x)$, where the subscripts mean differentiation with respect to the first and second inputs of $F$. In particular, $\partial f/\partial x$ is in $K$. We used that $K/k(x)$ was separable to ensure that we didn’t divide by zero.

This shows that $\partial^{p-1} f/(\partial x)^{p-1}$ is in $K$. Note also that $\partial^{p} f/(\partial x)^{p} =0$. I leave it as an exercise for the reader to check that, if $g \in K$ satisfies $\partial g/\partial x=0$, then $g \in K^p$. Hint: Remember that $k$ is perfect!

Putting the above together, the right hand side of $(**)$ is in $K$. So the $s_i$ carry $K$ to itself.

## Making the $s$‘s coordinate free

But $K$ is infinite dimensional over $k$. Why is $k \cdot \mathfrak{S}(f)$ finite dimensional? Thinking geometrically, $K$ is the field of merormorphic functions on some complete curve $X$ over $k$. To prove a finite dimensionality theorem, we will need to work globally on $X$. But the definition of the $\sigma_i$ is very dependent on the choice of the coordinate $x$, which is a local choice. In this section, I will show how to get away from that choice.

Define a map $\mathcal{C}: k((x)) dx \to k((x)) dx$ by $f(x) dx \mapsto s_{p-1}(f) dx$. Here is the miracle: The map $\mathcal{C}$ does not depend on the choice of coordinate $x$.

Let’s see an example. Clearly, $\mathcal{C}(x^{p-1} dx) = dx$. Let $x=u+u^2$. So $x^{p-1} dx = (u+u^2)^{p-1} (1+2u) du$. Now, $(u+u^2)^{p-1} (1+2u) = \left( u^{p-1} + \cdots + u^{2p-2} \right) (1+2u)$ $= \left( u^{p-1} + \cdots + 2u^{2p-1} \right)$. So $s_{p-1} \left( (u+u^2)^{p-1} (1+2u) \right) = 1 + 2u$ and $\mathcal{C}\left( (u+u^2) (1+2u) du\right) = (1+2u) du = dx$!

This miracle deserves a proof, but I won’t give it. I’ll just make an analogy: In characteristic zero, there is a residue map, which takes the differential form $\sum f_i x^i dx$ to the coefficient of $dx/x$. A differential form can be locally written as $dg$ if and only if its residue is zero. And, working purely in formal power series, it is somewhat challenging to show that the residue map is well defined. $\mathcal{C}$ plays the same role in characteristic $p$: We have $\mathcal{C}(\omega)=0$ if and only if $\omega$ can be written as $dg$, and it is true but subtle that $\mathcal{C}$ does not depend on the choice of coordinates. But the residue is a mere number, while $\mathcal{C}$ is a differential form, so $\mathcal{C}$ is far more powerful! The operator $\mathcal{C}$ is merely the simplest example of a Cartier operator, an operation on differential forms which exists only in characteristic $p$.

The fact that $\mathcal{C}$ is independent of the choice of coordinate should be a hint that it sheafifies. Indeed, let $\Omega$ be the Kahler-differentials of $K$ over $k$. The elements of $\Omega$ are precisely $f dx$ for $f \in K$, but the formulation of $\Omega$ does not depend on the choice of $x$. Then $\mathcal{C}$ is a well-defined map from $\Omega$ to itself. Moreover, if $\omega$ does not have a pole at some point $z \in X$, then neither does $\mathcal{C}(\omega)$.

## Finishing the proof

We now restate our goal, changing all of our functions to differentials.

Let $x$ be an element of $K$. Define the operations $\sigma_0$, $\sigma_1$, …., $\sigma_{p-1}$ from $\Omega$ to $\Omega$ by $\sigma_i(\omega) = \mathcal{C}(x^{p-i-1} \omega)$. Fix a differential form $\omega \in \Omega$. Let $\Sigma(\omega)$ be the $k$-vector space spanned by those differential forms we get by applying the $s_i$ to $\omega$. We want to show that $\Sigma(\omega)$ is finite dimensional.

Let $z$ be a point of $X$. As we have already mentioned, if $x$ and $\omega$ do not have poles at $z$, then all the forms in $\Sigma(\omega)$ are likewise pole-free.

Suppose that $z$ is one of the finitely many points where $\omega$ or $x$ has a pole. If $\omega$ has a pole of order $\leq a$, and $x$ has a pole of order $\leq b$ at some point, then an easy computation shows that $\sigma_i(\omega)$ has a pole of order $\leq 1 + (a+(p-1-i)b)/p \leq a/p + 1 + (p-1)b/p$. Feeding this bound into itself, $\sigma_i \sigma_j(\omega)$ has a pole of order at most $a/p^2 + (1 + p^{-1}) ( 1 + (p-1)b/p)$. Continuing in this manner, no element of $\Sigma(\omega)$ will have a pole of order more than $\max_n(a/p^n + (1+p^{-1} + \cdots + p^{-n+1})( 1 + (p-1)b/p))$ $\leq a + b + 1-p^{-1}$ at $z$.

The exact numbers don’t matter. The moral is that there are only finitely many points where the forms in $\Sigma(\omega)$ can have poles; and the orders of the poles at those points are bounded. So the vector space $\Sigma(\omega)$ is finite dimensional. QED.

1. Jared Weinstein - February 12, 2010

I think some of the sigmas under the paragraph “Reformulating the Problem” ought to be s’s, or maybe vice versa.

2. Florian - April 9, 2010

Yes, very nice! A couple of small typos:

“It is convenient to generalize from F_p to an arbitrary perfect field k”:
but char. k = p!

a_{imn} \in k (not =)

df/dx = -F_2/F_1.

C \omega = 0 (not \omega = 0)

and I agree with Jared’s final comment.

3. David Speyer - April 12, 2010

Thanks for the corrections!