Daily Archives: February 11, 2010

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.

Continue reading →