An elementary proof of Bridy's theorem
arXiv:2308.10977 · doi:10.1016/j.ffa.2025.102621
Abstract
Christol's theorem states that a power series with coefficients in a finite field is algebraic if and only if its coefficient sequence is automatic. A natural question is how the size of a polynomial describing such a sequence relates to the size of an automaton describing the same sequence. Bridy used tools from algebraic geometry to bound the size of the minimal automaton for a sequence, given its minimal polynomial. We produce a new proof of Bridy's bound by embedding algebraic sequences as diagonals of rational functions.
31 pages, 2 figures, 2 tables; publication version