×

zbMATH — the first resource for mathematics

Automatic sequences and curves over finite fields. (English) Zbl 1425.11051
A well-known result of Christol states that a formal power series \(y=\sum_{n\ge 0} a_n x^n\) in \(\mathbb{F}_q[[x]]\) is algebraic over \(\mathbb{F}_q(x)\) if and only if the sequence \((a_n)\) of its coefficients is \(q\)-automatic (in the sense of Allouche and Shallit). For a \(q\)-automatic sequence, its (state) complexity is defined as the number of states of a minimal automaton generating it and fed with, least significant digit first, base-\(q\) expansions. The main aim of this paper is to give a quantitative result about Christol’s theorem: an upper bound on such state complexity compared with the algebraic complexity of the series.
Let \(y\) be algebraic over \(k(x)\). The degree \(d\) of \(y\) is the field degree \([k(x)[y]:k(x)]\) and the height \(h\) is the minimal \(x\)-degree of a bivariate polynomial \(P(x,T)\in k[x,T]\) such that \(P(x,y)=0\). The genus \(g\) of \(y\) is the genus of the normalization of the projective closure of the affine plane curve defined by the minimal polynomial of \(y\). With these definitions, the author proves that if \(y=\sum_{n\ge 0} a_n x^n\in \mathbb{F}_q[[x]]\) is algebraic over \(\mathbb{F}_q(x)\), then the state complexity of \((a_n)\) is bounded by \((1+o(1))q^{d+h+g-1}\) and the error term tends to zero for large values of \(q\), \(h\), \(d\), or \(g\). When reading most significant digit first, the author also obtains an upper bound of the form \(q^{h+2d+g-1}\).
One of the main ingredient of this paper is to use algebraic geometry and in particular the Riemann-Roch theorem, existence of the Cartier operator acting on the space of Kähler differentials of the function field associated with \(y\), and asymptotics for the Landau function. Such an idea was introduced by David Speyer in 2010 to give an alternative proof for one direction of Christol’s theorem.
The paper ends with some computations of the state complexity of an automatic sequence showing how the geometric approach can be useful. Note that recently, B. Adamczewski and R. Yassawi have obtained similar bounds using a method based on diagonals of bivariate rational functions, see “A note on Christol’s theorem”. arxiv:1906.08703.

MSC:
11B85 Automata sequences
11G20 Curves over finite and local fields
14H05 Algebraic functions and function fields in algebraic geometry
14H25 Arithmetic ground fields for curves
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] doi:10.1007/s00222-011-0337-4 · Zbl 1257.11027
[2] ; Adamczewski, Ann. Sci. Éc. Norm. Supér. (4), 46, 963, (2013)
[3] doi:10.1017/CBO9780511546563 · Zbl 1086.11015
[4] doi:10.1007/978-3-642-73235-5
[5] ; Brzozowski, Proc. Sympos. Math. Theory of Automata, 529, (1963)
[6] ; Cartier, C. R. Acad. Sci. Paris, 244, 426, (1957)
[7] doi:10.1016/0304-3975(79)90011-2 · Zbl 0402.68044
[8] ; Christol, Bull. Soc. Math. France, 108, 401, (1980)
[9] doi:10.1007/s00222-006-0031-0 · Zbl 1205.11030
[10] ; Eilenberg, Automata, languages, and machines. Pure and Applied Mathematics, 58, (1974) · Zbl 0317.94045
[11] ; Eisenstein, Preuss. Akad. d. Wissensch. Berlin, 441, (1852)
[12] doi:10.1006/jnth.1999.2444 · Zbl 0974.11011
[13] doi:10.1007/BF02778035 · Zbl 0675.13015
[14] doi:10.1007/BF02764899 · Zbl 0703.13016
[15] ; Hartshorne, Algebraic geometry. Graduate Texts in Mathematics, 52, (1977) · Zbl 0367.14001
[16] doi:10.1017/CBO9781139172769
[17] doi:10.2307/2008729 · Zbl 0675.10028
[18] ; Schmidt, Acta Arith., 56, 161, (1990)
[19] ; Serre, Symposium internacional de topología algebraica, 24, (1958)
[20] doi:10.1017/CBO9780511808876 · Zbl 1163.68025
[21] doi:10.1007/978-0-387-09494-6 · Zbl 1194.11005
[22] ; Stichtenoth, Algebraic function fields and codes. Graduate Texts in Mathematics, 254, (2009) · Zbl 1155.14022
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.