CS Talk - Andrew Bridy, Yale University

Event time: 
Thursday, January 30, 2020 - 4:00pm
Location: 
AKW 200 See map
51 Prospect Street
New Haven, CT 06511
Event description: 

CS Talk
Andrew Bridy, Yale University

Title: Finite automata and algebraic equations mod p

Host: Dana Angluin

Abstract:

A finite automaton is a very limited model of a computer, which assigns an output to every possible input string over a given alphabet. Choosing a base p, we can represent non-negative integers as strings (their base-p expansions) by using the alphabet {0,1,…,p-1}.  In this way, an automaton can generate a sequence: it takes the integers  0,1,2,3,…, reads their base-p expansions as input, and produces the sequence a_0,a_1,a_2,a_3,… as output.  We can then form a power series by writing

   y = a_0 + a_1*x + a_2*x^2 + a_3*x^3+…

If p is a prime number and we perform arithmetic mod p, this power series is always a solution to an algebraic equation like
y^2 = 1+x^3.  Amazingly, the converse is also true: working mod p, the sequence of coefficients of an algebraic power series can always be generated by some finite automaton.  This is known as Christol’s theorem.

I will go through some examples to explain how Christol’s theorem works, then explore some connections between the size of the automaton and the complexity of the algebraic function.

(This talk will also be accessible to undergraduates.)

Bio:

Andrew Bridy is a lecturer in Computer Science and Political Science at Yale.  He received his Ph.D. in mathematics from the University of Wisconsin in 2014 under the supervision of Eric Bach.

His research interests are in number theory, algebraic geometry, and their connections to theoretical computer science.