pith. sign in

arxiv: 1906.08703 · v1 · pith:QHFYZYE5new · submitted 2019-06-20 · 🧮 math.NT · cs.FL

A note on Christol's theorem

Boris Adamczewski , Reem Yassawi This is my paper

Pith reviewed 2026-05-25 19:04 UTC · model grok-4.3

classification 🧮 math.NT cs.FL
keywords Christol's theoremalgebraic power seriesfinite automatadiagonals of rational functionsfinite fieldsquantitative boundsminimal polynomial
0
0 comments X

The pith

Diagonals of bivariate rational functions produce the same bounds on automaton size as algebraic geometry for Christol's theorem.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

Christol's theorem states that a power series over a finite field is algebraic if and only if its coefficient sequence is generated by a finite automaton. Recent work gave explicit bounds on the size of this automaton in terms of the height and degree of the series together with the genus of the curve defined by its minimal polynomial, but those bounds were obtained through Kähler differentials on the function field. The present note shows that the same bounds follow from an elementary construction that extracts the diagonal of a suitable bivariate rational function built from the minimal polynomial. A sympathetic reader would care because the quantitative content of the theorem turns out not to require the apparatus of algebraic geometry.

Core claim

The paper establishes that the size of the finite automaton attached to an algebraic power series over a finite field is bounded in terms of the height and degree of the series and the genus of the curve of its minimal polynomial, and that these bounds are recovered by forming the diagonal of an associated bivariate rational function without any appeal to Kähler differentials or the geometry of the function field.

What carries the argument

The diagonal of a bivariate rational function, which extracts the univariate series whose coefficients lie on the main diagonal and thereby encodes the transition data of the automaton.

If this is right

  • The same three parameters—height, degree, and genus—control the automaton size in both the geometric and the diagonal proofs.
  • No properties of Kähler differentials are needed to reach the quantitative statement of Christol's theorem.
  • The diagonal construction supplies an explicit, combinatorial route from the minimal polynomial to the automaton.
  • Quantitative versions of other automata characterizations may be approachable by similar diagonal extractions.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The diagonal method may be the combinatorial core that explains why the geometric bounds hold.
  • Direct computation of diagonals could yield practical algorithms for producing small automata from algebraic equations.
  • The approach suggests that other automatic-sequence problems might admit elementary proofs that previously appeared to require algebraic geometry.

Load-bearing premise

The size estimates produced by the diagonal construction apply directly to the minimal automaton without extra multiplicative factors or hidden geometric conditions.

What would settle it

Take the minimal polynomial of a concrete algebraic series such as the generating function for the Thue-Morse sequence, form the associated bivariate rational function, compute the diagonal bound on automaton size, and compare it with the order of the smallest known automaton for that sequence.

read the original abstract

Christol's theorem characterises algebraic power series over finite fields in terms of finite automata. In a recent article, Bridy develops a new proof of Christol's theorem by Speyer, to obtain a tight quantitative version, that is, to bound the size of the corresponding automaton in terms of the height and degree of the power series, as well as the genus of the curve associated with the minimal polynomial of the power series. Speyer's proof, and Bridy's development, both take place in the setting of algebraic geometry, in particular by considering K\"ahler differentials of the function field of the curve. In this note we show how an elementary approach, based on diagonals of bivariate rational functions, provides essentially the same bounds.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The manuscript claims that an elementary construction based on diagonals of bivariate rational functions yields quantitative bounds on the size of the finite automaton associated to an algebraic power series (in terms of the height and degree of the series and the genus of the curve defined by its minimal polynomial) that are essentially the same as those obtained by Bridy via Kähler differentials on the function field.

Significance. If the claimed bounds are recovered, the note supplies an accessible, non-geometric route to the quantitative form of Christol's theorem. The diagonal method is presented as self-contained and avoids the machinery of algebraic curves and differentials, which is a concrete strength for readers primarily interested in automata or formal power series.

minor comments (3)
  1. [Abstract / §1] The abstract and introduction repeatedly use the qualifier 'essentially the same bounds' without an explicit side-by-side statement of the two sets of constants (or at least the functional dependence on height, degree, and genus). A short displayed comparison would make the claim immediately verifiable.
  2. [Main argument (around the diagonal construction)] The transfer of size estimates from the diagonal of the rational function to the automaton is the central step; the manuscript should state the precise lemma or proposition that converts the degree of the diagonal into the number of states, including any dependence on the height.
  3. [Introduction] A reference to the exact statement of the bounds in Bridy's work (or Speyer's) would allow the reader to confirm that the elementary method matches the dependence on genus.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary and significance assessment of the manuscript. The report accurately reflects the elementary diagonal-based approach and its relation to Bridy's quantitative bounds. No specific major comments appear in the report, so we offer no point-by-point replies. We are happy to incorporate any minor editorial changes the editor may request.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper develops an independent elementary derivation of the quantitative bounds on automaton size using diagonals of bivariate rational functions applied to the minimal polynomial. The abstract states that the estimates are carried out directly from this diagonal construction, without reduction to the Kähler-differential method of Bridy or any self-citation chain. No load-bearing step equates a prediction to a fitted input by construction, imports uniqueness from prior author work, or renames a known result. The derivation is self-contained against the stated external benchmark (Bridy's bounds), satisfying the criteria for an honest non-finding.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on standard assumptions in combinatorics on words and algebraic functions over finite fields, with no new free parameters or invented entities introduced in the abstract.

axioms (1)
  • domain assumption Properties of diagonals of rational functions and their algebraic nature over finite fields.
    The method builds on known results about diagonals corresponding to algebraic series.

pith-pipeline@v0.9.0 · 5646 in / 1088 out tokens · 31979 ms · 2026-05-25T19:04:33.826012+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

18 extracted references · 18 canonical work pages

  1. [1]

    Boris Adamczewski and Jason P. Bell. On vanishing coefficients of algebraic power series over fields of positive characteristic. Invent. Math. , 187(2):343--393, 2012

    work page 2012

  2. [2]

    Boris Adamczewski and Jason P. Bell. Diagonalization and rationalization of algebraic L aurent series. Ann. Sci. \'Ec. Norm. Sup\'er. (4) , 46(6):963--1004, 2013

    work page 2013

  3. [3]

    Automatic Sequences: Theory, Applications, Generalizations

    Jean-Paul Allouche and Jeffrey Shallit. Automatic Sequences: Theory, Applications, Generalizations . Cambridge University Press, Cambridge, 2003

    work page 2003

  4. [4]

    Fast coefficient computation for algebraic power series in positive characteristic

    Alin Bostan, Xavier Caruso, Gilles Christol, and Philippe Dumas. Fast coefficient computation for algebraic power series in positive characteristic. volume 2, pages 119--135, 2019

    work page 2019

  5. [5]

    A generalization of B aker's theorem

    Peter Beelen. A generalization of B aker's theorem. Finite Fields Appl. , 15(5):558--568, 2009

    work page 2009

  6. [6]

    Noncommutative rational series with applications , volume 137 of Encyclopedia of Mathematics and its Applications

    Jean Berstel and Christophe Reutenauer. Noncommutative rational series with applications , volume 137 of Encyclopedia of Mathematics and its Applications . Cambridge University Press, Cambridge, 2011

    work page 2011

  7. [7]

    Automatic sequences and curves over finite fields

    Andrew Bridy. Automatic sequences and curves over finite fields. Algebra Number Theory , 11(3):685--712, 2017

    work page 2017

  8. [8]

    Ensembles presque periodiques k -reconnaissables

    Gilles Christol. Ensembles presque periodiques k -reconnaissables. Theoret. Comput. Sci. , 9(1):141--145, 1979

    work page 1979

  9. [9]

    Suites alg\'ebriques, automates et substitutions

    Gilles Christol, Teturo Kamae, Michel Mend \`e s France, and G\'erard Rauzy. Suites alg\'ebriques, automates et substitutions. Bull. Soc. Math. France , 108(4):401--419, 1980

    work page 1980

  10. [10]

    Denef and L

    J. Denef and L. Lipshitz. Algebraic power series and diagonals. J. Number Theory , 26(1):46--67, 1987

    work page 1987

  11. [11]

    Automata, languages, and machines

    Samuel Eilenberg. Automata, languages, and machines. V ol. A . Academic Press [A subsidiary of Harcourt Brace Jovanovich, Publishers], New York, 1974. Pure and Applied Mathematics, Vol. 58

    work page 1974

  12. [12]

    Automata and transcendence in positive characteristic

    Jean Fresnel, Michel Koskas, and Bernard de Mathan. Automata and transcendence in positive characteristic. J. Number Theory , 80(1):1--24, 2000

    work page 2000

  13. [13]

    Algebraic functions over finite fields

    Harry Furstenberg. Algebraic functions over finite fields. J. Algebra , 7:271--277, 1967

    work page 1967

  14. [14]

    Algebraic elements in formal power series rings

    Takashi Harase. Algebraic elements in formal power series rings. Israel J. Math. , 63(3):281--288, 1988

    work page 1988

  15. [15]

    Algebraic elements in formal power series rings

    Takashi Harase. Algebraic elements in formal power series rings. II . Israel J. Math. , 67(1):62--66, 1989

    work page 1989

  16. [16]

    Automatic congruences for diagonals of rational functions

    Eric Rowland and Reem Yassawi. Automatic congruences for diagonals of rational functions. J. Th\'eor. Nombres Bordeaux , 27(1):245--288, 2015

    work page 2015

  17. [17]

    https://sbseminar.wordpress.com/2010/02/11/christols-theorem-and-the-cartier-operator/

    Christol's theorem and the C artier operator. https://sbseminar.wordpress.com/2010/02/11/christols-theorem-and-the-cartier-operator/. Accessed: 2010-09-30

    work page 2010

  18. [18]

    Woodcock

    Habib Sharif and Christopher F. Woodcock. Algebraic functions over a field of positive characteristic and H adamard products. J. London Math. Soc. (2) , 37(3):395--403, 1988

    work page 1988