F-sets and finite automata
Journal de théorie des nombres de Bordeaux, Tome 31 (2019) no. 1, pp. 101-130.

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.

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.

Reçu le :
Révisé le :
Accepté le :
Publié le :
DOI : 10.5802/jtnb.1070
Classification : 11B85, 14G17
Mots clés : automatics sets, $F$-sets, semiabelian varieties, positive characteristic Mordell–Lang, Skolem–Mahler–Lech
Bell, Jason 1 ; Moosa, Rahim 1

1 University of Waterloo Department of Pure Mathematics 200 University Avenue West Waterloo, Ontario N2L 3G1, Canada
@article{JTNB_2019__31_1_101_0,
     author = {Bell, Jason and Moosa, Rahim},
     title = {$F$-sets and finite automata},
     journal = {Journal de th\'eorie des nombres de Bordeaux},
     pages = {101--130},
     publisher = {Soci\'et\'e Arithm\'etique de Bordeaux},
     volume = {31},
     number = {1},
     year = {2019},
     doi = {10.5802/jtnb.1070},
     mrnumber = {3994721},
     language = {en},
     url = {http://www.numdam.org/articles/10.5802/jtnb.1070/}
}
TY  - JOUR
AU  - Bell, Jason
AU  - Moosa, Rahim
TI  - $F$-sets and finite automata
JO  - Journal de théorie des nombres de Bordeaux
PY  - 2019
SP  - 101
EP  - 130
VL  - 31
IS  - 1
PB  - Société Arithmétique de Bordeaux
UR  - http://www.numdam.org/articles/10.5802/jtnb.1070/
DO  - 10.5802/jtnb.1070
LA  - en
ID  - JTNB_2019__31_1_101_0
ER  - 
%0 Journal Article
%A Bell, Jason
%A Moosa, Rahim
%T $F$-sets and finite automata
%J Journal de théorie des nombres de Bordeaux
%D 2019
%P 101-130
%V 31
%N 1
%I Société Arithmétique de Bordeaux
%U http://www.numdam.org/articles/10.5802/jtnb.1070/
%R 10.5802/jtnb.1070
%G en
%F JTNB_2019__31_1_101_0
Bell, Jason; Moosa, Rahim. $F$-sets and finite automata. Journal de théorie des nombres de Bordeaux, Tome 31 (2019) no. 1, pp. 101-130. doi : 10.5802/jtnb.1070. http://www.numdam.org/articles/10.5802/jtnb.1070/

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Cité par Sources :