F-sets and finite automata
Jason Bell; Rahim Moosa
Journal de Théorie des Nombres de Bordeaux, Volume 31 (2019) no. 1, p. 101-130

It is observed that Derksen’s Skolem–Mahler–Lech theorem is a special case of the isotrivial positive characteristic Mordell-Lang theorem due to the second author and Scanlon. This motivates an extension of the classical notion of a k-automatic subset of the natural numbers to that of an F-automatic subset of a finitely generated abelian group Γ equipped with an endomorphism F. Applied to the Mordell–Lang context, where F is the Frobenius action on a commutative algebraic group G over a finite field, and Γ is a finitely generated F-invariant subgroup of G, it is shown that the “F-subsets” of Γ introduced by the second author and Scanlon are F-automatic. It follows that when G is semiabelian and XG is a closed subvariety then XΓ is F-automatic. Derksen’s notion of a k-normal subset of the natural numbers is also here extended to the above abstract setting, and it is shown that F-subsets are F-normal. In particular, the XΓ appearing in the Mordell-Lang problem are F-normal. This generalises Derksen’s Skolem–Mahler–Lech theorem to the Mordell–Lang context.

On observe que le théorème de Skolem–Mahler–Lech de Derksen est un cas particulier du théorème de Mordell–Lang isotrivial en caractéristique positive dû au second auteur et Scanlon. Cela motive une extension de la notion classique d’un sous-ensemble k-automatique des nombres naturels à celle d’un ensemble F-automatique d’un groupe abélien de type fini Γ équipé d’un endomorphisme F. Dans le contexte de Mordell–Lang, où F est l’action de Frobenius sur un groupe algébrique commutatif G sur un corps fini, et Γ est un sous-groupe F-invariant de G, il est montré que les « F-sous-ensembles » de Γ introduits par le second auteur et Scanlon sont F -automatiques. Il en découle que lorsque G est semi-abélien et XG est une sous-variété fermée, XΓ est F-automatique. La notion d’un sous-ensemble k-normal des nombres naturels au sens de Derksen est également généralisée au contexte abstrait cité ci-dessus, et il est démontré que les F-sous-ensembles sont F-normaux. En particulier, les ensembles XΓ qui apparaissent dans le problème de Mordell–Lang sont F-normaux. Cela généralise le théorème de Skolem–Mahler–Lech de Derksen au contexte de Mordell–Lang.

Received : 2018-01-16
Revised : 2018-07-19
Accepted : 2018-10-08
Published online : 2019-07-29
DOI : https://doi.org/10.5802/jtnb.1070
Classification:  11B85,  14G17
Keywords: automatics sets, F-sets, semiabelian varieties, positive characteristic Mordell–Lang, Skolem–Mahler–Lech
     author = {Jason Bell and Rahim Moosa},
     title = {$F$-sets and finite automata},
     journal = {Journal de Th\'eorie des Nombres de Bordeaux},
     publisher = {Soci\'et\'e Arithm\'etique de Bordeaux},
     volume = {31},
     number = {1},
     year = {2019},
     pages = {101-130},
     doi = {10.5802/jtnb.1070},
     language = {en},
     url = {https://jtnb.centre-mersenne.org/item/JTNB_2019__31_1_101_0}
Bell, Jason; Moosa, Rahim. $F$-sets and finite automata. Journal de Théorie des Nombres de Bordeaux, Volume 31 (2019) no. 1, pp. 101-130. doi : 10.5802/jtnb.1070. jtnb.centre-mersenne.org/item/JTNB_2019__31_1_101_0/

[1] Boris Adamczewski; Jason P. Bell On vanishing coefficients of algebraic power series over fields of positive characteristic, Invent. Math., Tome 187 (2012) no. 2, pp. 343-393

[2] Jean-Paul Allouche; Jeffrey Shallit Automatic sequences. Theory, applications, generalizations, Cambridge University Press, 2003

[3] Jason P. Bell Corrigendum: “A generalised Skolem–Mahler–Lech theorem for affine varieties”, J. Lond. Math. Soc., Tome 78 (2006) no. 1, pp. 267-272

[4] Jason P. Bell A generalised Skolem–Mahler–Lech theorem for affine varieties, J. Lond. Math. Soc., Tome 73 (2006) no. 2, pp. 367-379

[5] Harm Derksen A Skolem–Mahler–Lech theorem in positive characteristic and finite automata, Invent. Math., Tome 168 (2007) no. 1, pp. 175-224

[6] Gerd Faltings The general case of S. Lang’s conjecture, Barsotti Symposium in Algebraic Geometry (Abano Terme, 1991) (Perspectives in Mathematics) Tome 15, Academic Press Inc., 1991, pp. 175-182 | Zbl 0823.14009

[7] Paweł Gawrychowski; Dalia Krieger; Narad Rampersad; Jeffrey Shallit Finding the growth rate of a regular or context-free language in polynomial time, Int. J. Found. Comput. Sci., Tome 21 (2010) no. 4, pp. 597-618 | Zbl 1206.68172

[8] Dragos Ghioca The isotrivial case in the Mordell–Lang theorem, Trans. Am. Math. Soc., Tome 360 (2008) no. 7, pp. 3839-3856 | Zbl 1232.11071

[9] Dragos Ghioca; Rahim Moosa Division points on subvarieties of isotrivial semi-abelian varieties, Int. Math. Res. Not., Tome 2006 (2006) no. 19, 65437, 23 pages | Zbl 1119.14017

[10] Seymour Ginsburg; Edwin H. Spanier Bounded regular sets, Proc. Am. Math. Soc., Tome 17 (1966), pp. 1043-1049 | Zbl 0147.25301

[11] Ehud Hrushovski The Mordell–Lang conjecture for function fields, J. Am. Math. Soc., Tome 9 (1996) no. 3, pp. 667-690

[12] Oscar H. Ibarra; B. Ravikumar On sparseness, ambiguity and other decision problems for acceptors and transducers, STACS 86 (Lecture Notes in Computer Science) Tome 210, Springer, 1986, pp. 171-179 | Zbl 0605.68080

[13] Rahim Moosa; Thomas Scanlon The Mordell–Lang conjecture in positive characteristic revisited, Model theory and applications (Quaderni di Matematica) Tome 11, Aracne, 2002, pp. 273-296 | Zbl 1088.11046

[14] Rahim Moosa; Thomas Scanlon F-structures and integral points on semiabelian varieties over finite fields, Am. J. Math., Tome 126 (2004) no. 3, pp. 473-522 | Zbl 1072.03020

[15] Andrew Szilard; Sheng Yu; Kaizhong Zhang; Jeffrey Shallit Characterizing regular languages with polynomial densities, Mathematical Foundations of Computer Science 1992 (Lecture Notes in Computer Science) Tome 629, Springer, 1992, pp. 494-503 | Article

[16] V. I. Trofimov Growth functions of some classes of languages, Kibernetika, Tome 1981 (1981) no. 6, pp. 9-12 (English translation in Cybernetics 17 (1981), p. 727–731) | Zbl 0512.68054