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

algebraic curvesautomatic sequencesfinite fieldsformal power series

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

• A Second Course in Formal Languages and Automata Theory
• A Skolem-Mahler-Lech theorem in positive characteristic and finite automata
• Algebraic elements in formal power series rings
• Algebraic elements in formal power series rings. II
• Algebraic Function Fields and Codes
• 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)
• 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?)
• 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

(8)

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

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)