$F$-sets and finite automata

Jason Bell; Rahim Moosa

doi:10.5802/jtnb.1070

F

-sets and finite automata

Jason Bell ¹ ; Rahim Moosa ¹

¹ University of Waterloo Department of Pure Mathematics 200 University Avenue West Waterloo, Ontario N2L 3G1, Canada

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

Résumé
Abstract

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 $X \subseteq G$ est une sous-variété fermée, $X \cap Γ$ 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 \cap Γ$ 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 $X \subseteq G$ is a closed subvariety then $X \cap Γ$ 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 \cap Γ$ 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 : 2018-01-15
Révisé le : 2018-07-18
Accepté le : 2018-10-07
Publié le : 2019-07-28

MR

DOI : 10.5802/jtnb.1070

Classification : 11B85, 14G17
Mots clés : automatics sets, $F$-sets, semiabelian varieties, positive characteristic Mordell–Lang, Skolem–Mahler–Lech

Affiliations des auteurs :

Jason Bell ¹ ; Rahim Moosa ¹

¹ University of Waterloo Department of Pure Mathematics 200 University Avenue West Waterloo, Ontario N2L 3G1, Canada

Licence :

CC-BY-ND 4.0

Droits d'auteur : Les auteurs conservent leurs droits

@article{JTNB_2019__31_1_101_0,
     author = {Jason Bell and Rahim Moosa},
     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 = {https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.1070/}
}

TY  - JOUR
AU  - Jason Bell
AU  - Rahim Moosa
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  - https://jtnb.centre-mersenne.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 Jason Bell
%A Rahim Moosa
%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 https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.1070/
%R 10.5802/jtnb.1070
%G en
%F JTNB_2019__31_1_101_0

Jason Bell; Rahim Moosa. $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. https://jtnb.centre-mersenne.org/articles/10.5802/jtnb.1070/

Bibliographie
Cité par

[1] Boris Adamczewski; Jason P. Bell 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] 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., Volume 78 (2006) no. 1, pp. 267-272 | DOI

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

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

[6] Gerd Faltings 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] 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., Volume 21 (2010) no. 4, pp. 597-618 | DOI | MR | Zbl

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

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

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

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

[12] Oscar H. Ibarra; B. Ravikumar 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] Rahim Moosa; Thomas Scanlon 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] Rahim Moosa; Thomas Scanlon $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] 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), Volume 629, Springer, 1992, pp. 494-503 | DOI | MR

[16] V. I. Trofimov 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 :