Automatic Sequences and Curves over Finite Fields

Abstract

We prove that if $y={\sum }_{n=0}^{\infty }\mathbf{a}(n)x^n\in {\mathbb{F}}_q[[x]]$ is an algebraic power series of degree $d$, height $h$, and genus $g$, then the sequence $\mathbf{a}$ is generated by an automaton with at most $q^{h+d+g-1}$ states, up to a vanishingly small error term. This is a significant improvement on previously known bounds. Our approach follows an idea of David Speyer to connect automata theory with algebraic geometry by representing the transitions in an automaton as twisted Cartier operators on the differentials of a curve.

22 pages, 6 figures

References in corpus (1)

• On vanishing coefficients of algebraic power series over fields of positive characteristic

Cited by in corpus (7)

• An elementary proof of Bridy's theorem
• On the maximum order complexity of the Thue-Morse and Rudin-Shapiro sequence
• A note on Christol's theorem
• Fast Coefficient Computation for Algebraic Power Series in Positive Characteristic
• Semi-galois Categories III: Witt vectors by deformations of modular functions
• Arithmetic statistics of Galois groups
• Computing the n-th coefficient of an algebraic power series modulo p in O(log n) operations