# Christol’s theorem and the Cartier operator

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