On vanishing coefficients of algebraic power series over fields of positive characteristic (Q664335): Difference between revisions

The authors prove the following remarkable result. Let \(p\) be a prime number, \(K\) a field of characteristic \(p>0\) and \(f=\sum_{{\mathbf n}\in{\mathbb Z}_{\geq 0}^d} a({\mathbf n})t_1^{n_1}\cdots t_d^{n_d} \in K[[t_1,\ldots t_d]]\) a power series over \(K\) in \(d\) variables which is algebraic over the rational function field \(K(t_1,\ldots ,t_d)\). Then the set \({\mathcal Z}(f)=\{ {\mathbf n}\in{\mathbb Z}_{\geq 0}^d:\, a({\mathbf n})=0\}\) is \(p\)-automatic. Moreover, \({\mathcal Z}(f)\) can be determined effectively, that is, the automaton recognizing \({\mathcal Z}(f)\) can be determined effectively. The authors deduce several important consequences from their main result. First, they deduce the following weaker form of a result of \textit{H. Derksen} [Invent. Math. 168, No. 1, 175--224 (2007; Zbl 1205.11030)]: Let \(a=\{ a_n\}_{n=0}^{\infty}\) be a linear recurrence sequence over a field \(K\) of characteristic \(p>0\), i.e., the sequence of coefficients of a power series representing a rational function. Then \({\mathcal Z}(a)=\{ n:\, a_n=0\}\) is \(p\)-automatic and can be determined effectively. Second, given \(c_1,\ldots ,c_m\in K^*\) and a finitely generated subgroup \(\Gamma\) of \(K^*\), then the set of \((x_1,\ldots ,x_m)\in\Gamma^m\) with \(c_1x_1+\cdots +c_mx_m=1\) is \(p\)-automatic and can be determined effectively. Third, the authors deduce the following analogue over positive characteristic of the Mordell-Lang conjecture: let \(X\) be a Zariski closed subset of \(\text{GL}_d(K)\) and \(\Gamma\) a finitely generated abelian subgroup of \(\text{GL}(d,K)\). Then \(X\cap\Gamma\) is \(p\)-automatic and can be determined effectively. Lastly, using their main theorem the authors give another proof of Christol's characterization of algebraic power series over finite fields: let \(q\) be a power of \(p\) and \(f=\sum_{n=0}^{\infty} a_nt^n\in {\mathbb F}_q[[t]]\). Then \(f\) is algebraic over \({\mathbb F}_q(t)\) if and only if \(a=\{ a_n\}\) is \(p\)-automatic, i.e., there is a finite automaton which on input the base \(p\)-representation of \(n\), outputs \(a_n\). The proofs are based on elementary but involved automata theory. We recall some definitions used in the above statements. In general, given a finite alphabet \(\Sigma\) and a subset \(S\) of the set \(\Sigma^*\) of all finite words with letters from \(\Sigma\), we say that \(S\) is automatic w.r.t. \(\Sigma\) or recognized by a finite automation with input alphabet \(\Sigma\) if there is such an automaton which on input \(w\in\Sigma^*\), outputs \(1\) if \(w\in S\) and \(0\) if \(w\not\in S\). If \(k\) is an integer \(\geq 2\), the base \(k\)-representation of a tuple \({\mathbf n}\in{\mathbb Z}_{\geq 0}^d\) is the \(d\)-tuple of base \(k\)-representations of the entries of \({\mathbf n}\), and a subset \(S\) of \({\mathbb Z}_{\geq 0}^d\) is called \(k\)-automatic if the set of base \(k\)-representations of its elements is automatic w.r.t. \(\{ 0,\ldots ,k-1\}^d\). If we represent \(a\in{\mathbb Z}\) by means of its sign (\(+\) or \(-\)) and the base \(k\)-representation of \(|a|\), the base \(k\)-representation of \({\mathbf n}\in{\mathbb Z}^d\) consists of the \(d\)-tuple of the base \(k\)-representations of the entries of \({\mathbf n}\), and a subset \(S\) of \({\mathbb Z}^d\) is called \(k\)-automatic if the set of base \(k\)-representations of its elements is automatic w.r.t. \(\{ +,-,0,\ldots ,k-1\}^d\). Lastly, given a finitely generated abelian group \(\Gamma\) with set of generators \(\{ \gamma_1,\ldots,\gamma_d\}\), a subset \(S\) of \(\Gamma\) is called \(k\)-automatic if the set of \(\{ (n_1,\ldots n_d)\in{\mathbb Z}^d\) with \(\gamma_1^{n_1}\cdots\gamma_d^{n_d}\in S\) is \(k\)-automatic. It is shown in the paper that this does not depend on the choice of \(\gamma_1,\ldots ,\gamma_d\).