Automatic Sequences and Curves Over Finite Fields

Student Algebraic Geometry Seminar
Friday, January 26, 2018 - 10:00
1 hour (actually 50 minutes)
Skiles 254
Georgia Tech
We will first give a quick introduction to automatic sequences. We will then outine an algebro-geometric proof of Christol's theorem discovered by David Speyer. Christol's theorem states that a formal power series f(t) over GF(p) is algebraic over GF(p)(t) if and only if there is some finite state automaton such that the n-th coefficent of f(t) is obtained by feeding in the base-p representation of n into the automaton. Time permitting, we will explain how to use the Riemann-Roch theorem to obtain bounds on the number of states in the automaton in terms of the degree, height and genus of f(t).