Automatic Sequences and Curves Over Finite Fields

Series: 
Student Algebraic Geometry Seminar
Friday, January 26, 2018 - 10:00am
1 hour (actually 50 minutes)
Location: 
Skiles 254
,  
Georgia Tech
,  
Organizer: 
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).