#### Vol. 11, No. 3, 2017

 Download this article For screen For printing
 Recent Issues
 The Journal About the Journal Subscriptions Editorial Board Editors' Addresses Editors' Interests Scientific Advantages Submission Guidelines Submission Form Editorial Login Ethics Statement Author Index To Appear ISSN: 1944-7833 (e-only) ISSN: 1937-0652 (print) Other MSP Journals
Automatic sequences and curves over finite fields

### Andrew Bridy

Vol. 11 (2017), No. 3, 685–712
##### Abstract

We prove that if $y={\sum }_{n=0}^{\infty }$a$\left(n\right){x}^{n}\in {\mathbb{F}}_{q}\left[\left[x\right]\right]$ is an algebraic power series of degree $d$, height $h$, and genus $g$, then the sequence 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.

##### Keywords
automatic sequences, formal power series, algebraic curves, finite fields
##### Mathematical Subject Classification 2010
Primary: 11B85
Secondary: 11G20, 14H05, 14H25
##### Milestones
Received: 20 June 2016
Revised: 20 November 2016
Accepted: 19 December 2016
Published: 6 May 2017
##### Authors
 Andrew Bridy Department of Mathematics Texas A&M University Department of Mathematics Mailstop 3368 College Station, TX 77843 United States