Automatic sequences and curves over finite fields

DOI10.2140/ANT.2017.11.685MaRDI QIDQ2397618zbMATH OpenOpenAlexFDO

Authors Andrew Bridy

Publication date 23 May 2017

Published in Algebra \& Number Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1604.08241

zbMATH Keywords

formal power seriesfinite fieldsautomatic sequencesalgebraic curves

Mathematics Subject Classification ID

Automata sequences (11B85) Curves over finite and local fields (11G20) Algebraic functions and function fields in algebraic geometry (14H05) Arithmetic ground fields for curves (14H25)

Abstract: We prove that if $$ is an algebraic power series of degree $d$, height $h$, and genus $g$, then the sequence $$ 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.

Recommendations

• Finite automata and arithmetic
• Automata, algebraicity and distribution of sequences of powers.
• scientific article; zbMATH DE number 4065109
• Automata and transcendence in positive characteristic
• Finite automata and algebraic extensions of functions fields

Cites work

• scientific article; zbMATH DE number 3125781 (Why is no real title available?)
• scientific article; zbMATH DE number 3144928 (Why is no real title available?)
• scientific article; zbMATH DE number 3497806 (Why is no real title available?)
• scientific article; zbMATH DE number 3572315 (Why is no real title available?)
• A Second Course in Formal Languages and Automata Theory
• A Skolem-Mahler-Lech theorem in positive characteristic and finite automata
• Algebraic Function Fields and Codes
• Algebraic elements in formal power series rings
• Algebraic elements in formal power series rings. II
• Automata and transcendence in positive characteristic
• Automatic Sequences
• Diagonalization and rationalization of algebraic Laurent series
• Effective Bounds for the Maximal Order of an Element in the Symmetric Group
• Eisenstein's theorem on power series expansions of algebraic functions
• Ensembles presque périodiques \(k\)-reconnaissables. (Almost periodic \(k\)-recognizable sets)
• On vanishing coefficients of algebraic power series over fields of positive characteristic
• Suites algébriques, automates et substitutions
• The Arithmetic of Elliptic Curves

Cited in

(7)

• Semi-Galois categories. III: Witt vectors by deformations of modular functions
• Fast coefficient computation for algebraic power series in positive characteristic
• An elementary proof of Bridy's theorem
• Semi-Galois categories. II: An arithmetic analogue of Christol's theorem
• On the algebraicity of generalized power series
• Automata and finite order elements in the Nottingham group
• On certain recurrent and automatic sequences in finite fields

This page was built for publication: Automatic sequences and curves over finite fields

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2397618)