Automatic sequences and curves over finite fields

DOI10.2140/ANT.2017.11.685zbMATH Open1425.11051arXiv1604.08241OpenAlexW2423014504MaRDI QIDQ2397618FDOQ2397618

Andrew Bridy

Publication date: 23 May 2017

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

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.

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

Recommendations

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

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)

Cites Work

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

Cited In (5)

• Fast coefficient computation for algebraic power series in positive characteristic
• 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)