Let’s suppose that we want to compute , and we have already been given written out in base as . Here is a small prime and we want to do this conversation repeatedly for many ‘s.

Remember that and thus . So, start with , multiply it by , then by , then by and so forth. When you get to the end, read off .

We can precompute the effect on of multiplying by , for . Then we can compute just by scanning across the base representation of and applying these precomputed maps to the finite set .

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 , and be finite sets (**input**, **states** and **output**), and (the **start**). For each , let be a map . We also have a map (**readout**). Given a string in , we compute . So our input is a string of characters from , and our output is in .

We can say that our example above shows that is computable by a finite-state automaton. (In our example, the sets , and all have cardinality , but I do not want to identify them.)

This is a special case of an amazing result of Christol et al: Let be a sequence of elements of . Then can be computed by a finite-state automaton if and only if the generating function is algebraic over !

We have just explained the case . The reader might enjoy working out the cases (the Fibonacci numbers) and (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 .