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 .