An elementary proof of Bridy's theorem
Christol's theorem states that a power series with coefficients in a finite field \(\mathbb{F}_q\) is algebraic if and only if its coefficient sequence is automatic: Let \((a_n)\) be a sequence of elements in \(\mathbb{F}_q\). The generating series \(F=\sum_{n\ge 0} a_n x\) satisfies \(P(x,F)=0\) for some nonzero polynomial \(P\in\mathbb{F}_q[x,y]\) precisely when there exists a finite automaton that outputs \(a(n)\) when fed the base-\(q\) expansion of \(n\).\N\NThe natural question studied in this paper is how the number of states of such a (minimal) automaton depends on the size of the polynomial, measured by its height \(h := \deg_x P\) and degree \(d := \deg_y P\).\N\NBridy used tools from algebraic geometry to bound the size of the minimal automaton for a sequence, given its minimal polynomial. The authors produce a new proof of Bridy's bound by embedding algebraic sequences as diagonals of rational functions. They relate their approach to other works and, in particular, to [\textit{B. Adamczewski} et al., ``A sharper multivariate Christol's theorem with applications to diagonals and Hadamard products, Preprint, \url{arXiv:2306.02640}].
- \textsc{IntegerSequences}: a package for computing with \(k\)-regular sequences
- A generalization of Baker's theorem
- Algebraic elements in formal power series rings. II
- Algebraic functions over finite fields
- Algebraic power series and diagonals
- Automatic congruences for diagonals of rational functions
- Automatic Sequences
- Automatic sequences and curves over finite fields
- Diagonalization and rationalization of algebraic Laurent series
- Ensembles presque périodiques \(k\)-reconnaissables. (Almost periodic \(k\)-recognizable sets)
- Fast coefficient computation for algebraic power series in positive characteristic
- Fonctions et éléments algébriques. (Algebraic functions and elements)
- Intégration sur un cycle évanescent
- Suites algébriques, automates et substitutions
- The concrete tetrahedron. Symbolic sums, recurrence equations, generating functions, asymptotic estimates
- The On-Line Encyclopedia of Integer Sequences
- What is \dots an automatic sequence?
- Über die Maximalordnung der Permutationen gegebenen Grades.
This page was built for publication: An elementary proof of Bridy's theorem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6994692)
