Automatic sequences and curves over finite fields

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)

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.

Review text

A well-known result of Christol states that a formal power series \(y=\sum_{n\ge 0} a_n x^n\) in \(\mathbb{F}_qx\) 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}_qx\) 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}.

Recommendations

Cites work

Cited in

(8)

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)