Automatic sequences and curves over finite fields (Q2397618): Difference between revisions

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, \textit{B. Adamczewski} and \textit{R. Yassawi} have obtained similar bounds using a method based on diagonals of bivariate rational functions, see ``A note on Christol's theorem''. \url{arxiv:1906.08703}.