×

On vanishing coefficients of algebraic power series over fields of positive characteristic. (English) Zbl 1257.11027

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 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\).

MSC:

11B85 Automata sequences
11G99 Arithmetic algebraic geometry (Diophantine geometry)
11D61 Exponential Diophantine equations
14G17 Positive characteristic ground fields in algebraic geometry

Citations:

Zbl 1205.11030
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Allouche, J.-P., Cateland, E., Gilbert, W.J., Peitgen, H.-O., Shallit, J.O., Skordev, G.: Automatic maps in exotic numeration systems. Theory Comput. Syst. 30, 285–331 (1997) · Zbl 0870.68105
[2] Allouche, J.-P., Shallit, J.: Automatic Sequences. Theory, Applications, Generalizations. Cambridge University Press, Cambridge (2003) · Zbl 1086.11015
[3] Bézivin, J.-P.: Une généralisation du théorème de Skolem–Mahler–Lech. Q. J. Math. Oxf. 40, 133–138 (1989) · Zbl 0678.10040
[4] Cerlienco, L., Mignotte, M., Piras, F.: Suites récurrentes linéaires : propriétés algébriques et arithmétiques. Enseign. Math. 33, 67–108 (1987) · Zbl 0626.10008
[5] Christol, G.: Ensembles presque périodiques k-reconnaissables. Theor. Comput. Sci. 9, 141–145 (1979) · Zbl 0402.68044
[6] Christol, G., Kamae, T., Mendès France, M., Rauzy, G.: Suites algébriques, automates et substitutions. Bull. Soc. Math. Fr. 108, 401–419 (1980) · Zbl 0472.10035
[7] Cobham, A.: On the base-dependence of sets of numbers recognizable by finite automata. Math. Syst. Theory 3, 186–192 (1969) · Zbl 0179.02501
[8] Deligne, P.: Intégration sur un cycle évanescent. Invent. Math. 76, 129–143 (1983) · Zbl 0538.13007
[9] Denef, J., Lipshitz, L.: Algebraic power series and diagonals. J. Number Theory 26, 46–67 (1987) · Zbl 0609.12020
[10] Derksen, H.: A Skolem-Mahler-Lech theorem in positive characteristic and finite automata. Invent. Math. 168, 175–224 (2007) · Zbl 1205.11030
[11] Derksen, H., Masser, D.: Linear equations over multiplicative groups, recurrences, and mixing I. Manuscript (2010) · Zbl 1269.11062
[12] Eilenberg, S.: Automata, Languages, and Machines, vol. A. Academic Press, San Diego (1974) · Zbl 0317.94045
[13] Everest, G., van der Poorten, A., Shparlinski, I., Ward, T.: Recurrence Sequences. Mathematical Surveys and Monographs, vol. 104. American Mathematical Society, Providence (2003) · Zbl 1033.11006
[14] Evertse, J.-H.: On sums of S-units and linear recurrences. Compos. Math. 53, 225–244 (1984) · Zbl 0547.10008
[15] Evertse, J.-H., Györy, K., Stewart, C.L., Tijdeman, R.: S-unit equations and their applications. In: New Advances in Transcendence Theory, Durham, 1986, pp. 110–174. Cambridge Univ. Press, Cambridge (1988)
[16] Evertse, J.-H., Schlickewei, H.P., Schmidt, W.M.: Linear equations in variables which lie in a multiplicative group. Ann. Math. 155, 807–836 (2002) · Zbl 1026.11038
[17] Faltings, G.: Diophantine approximation on abelian varieties. Ann. Math. 133, 549–576 (1991) · Zbl 0734.14007
[18] Furstenberg, H.: Algebraic functions over finite fields. J. Algebra 7, 271–277 (1967) · Zbl 0175.03903
[19] Ghioca, D.: The isotrivial case in the Mordell–Lang Theorem. Trans. Am. Math. Soc. 360, 3839–3856 (2008) · Zbl 1232.11071
[20] Hansel, G.: Une démonstration simple du théorème de Skolem–Mahler–Lech. Theor. Comput. Sci. 43, 91–98 (1986) · Zbl 0605.10007
[21] Harase, T.: Algebraic elements in formal power series rings. Isr. J. Math. 63, 281–288 (1988) · Zbl 0675.13015
[22] Honkala, J.: A decision method for the recognizability of sets defined by number systems. Theor. Inform. Appl. 20, 395–403 (1986) · Zbl 0639.68074
[23] Hrushovski, E.: The Mordell-Lang conjecture for function fields. J. Am. Math. Soc. 9, 667–690 (1996) · Zbl 0864.03026
[24] Kedlaya, K.: Finite automata and algebraic extensions of function fields. J. Théor. Nombres Bordeaux 18, 379–420 (2006) · Zbl 1161.11317
[25] Lang, S.: Integral points on curves. Publ. Math. IHÉS 6, 27–43 (1960) · Zbl 0112.13402
[26] Lech, C.: A note on recurring series. Ark. Mat. 2, 417–421 (1953) · Zbl 0051.27801
[27] Mahler, K.: Zur Approximation algebraischer Zahlen, I. (Über den grössten Primteiler binärer Formen). Math. Ann. 107, 691–730 (1933) · Zbl 0006.10502
[28] Mahler, K.: Eine arithmetische Eigenschaft der Taylor–Koeffizienten rationaler Funktionen. Proc. K. Ned. Akad. Wet. 38, 50–60 (1935) · JFM 61.0176.02
[29] Mahler, K.: On the Taylor coefficients of rational functions. Proc. Camb. Philos. Soc. 52, 39–48 (1956) · Zbl 0070.04004
[30] Mahler, K.: Addendum to the paper ”On the Taylor coefficients of rational functions”. Proc. Camb. Philos. Soc. 53, 544 (1957) · Zbl 0077.05205
[31] Masser, D.: Mixing and linear equations over groups in positive characteristic. Isr. J. Math. 142, 189–204 (2004) · Zbl 1055.37009
[32] Moosa, R., Scanlon, T.: F-structures and integral points on semiabelian varieties over finite fields. Am. J. Math. 126, 473–522 (2004) · Zbl 1072.03020
[33] van der Poorten, A.J.: Some facts that should be better known, especially about rational functions. In: Number Theory and Applications, Banff, AB, 1988. NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci., vol. 265, pp. 497–528. Kluwer Academic, Dordrecht (1989)
[34] van der Poorten, A.J., Schlickewei, H.P.: Additive relations in fields. J. Aust. Math. Soc. 51, 154–170 (1991) · Zbl 0747.11017
[35] Salon, O.: Suites automatiques à multi-indices et algébricité. C. R. Acad. Sci. Paris Sér. I Math. 305, 501–504 (1987) · Zbl 0628.10007
[36] Schmidt, K.: The dynamics of algebraic Z d -actions. In: European Congress of Mathematics, vol. I, Barcelona, 2000. Progress in Mathematics, vol. 201, pp. 543–553. Birkhäuser, Basel (2001) · Zbl 1071.28011
[37] Schmidt, K., Ward, T.: Mixing automorphisms of compact groups and a theorem of Schlickewei. Invent. Math. 111, 69–76 (1993) · Zbl 0824.28012
[38] Sharif, H., Woodcock, C.F.: Algebraic functions over a field of positive characteristic and Hadamard products. J. Lond. Math. Soc. 37, 395–403 (1988) · Zbl 0612.12018
[39] Skolem, T.: Ein Verfahren zur Behandlung gewisser exponentialer Gleichungen und dio-phantischer Gleichungen. In: Comptes Rendus Congr. Math. Scand., Stockholm, pp. 163–188 (1934) · JFM 61.1080.01
[40] Tao, T.: Structure and Randomness, Pages from Year One of a Mathematical Blog. American Mathematical Society, Providence (2008) · Zbl 1245.00024
[41] Voloch, J.F.: The equation ax+by=1 in characteristic p. J. Number Theory 73, 195–200 (1998) · Zbl 0916.11019
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.