Automatic sequences and curves over finite fields

Bridy, Andrew

doi:10.2140/ant.2017.11.685

Download this article
	For screen
	For printing

Recent Issues

The Journal

Submission Guidelines

Submission Form

Policies for Authors

Ethics Statement

ISSN: 1944-7833 (e-only)

ISSN: 1937-0652 (print)

Author Index

To Appear

Other MSP Journals

Automatic sequences and curves over finite fields

Andrew Bridy

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

DOI: 10.2140/ant.2017.11.685

Abstract

We prove that if $y = \sum_{n = 0}^{\infty}$ a $(n) x^{n} \in F_{q} [[x]]$ 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

Vol. 11, No. 3, 2017