Propriétés arithmétiques des substitutions et automates infinis
[Arithmetics properties of substitutions and infinite automata]
Annales de l'Institut Fourier, Volume 56 (2006) no. 7, pp. 2525-2549.

This work concerns the study of arithmetical and statistical properties of infinite words and sequences of integers generated by a substitution on an infinite denumerable alphabet or by a deterministic automata with an infinite denumerable set of states. In particular, we prove that if u is a sequence of integers generated by an automaton whose associated graph represents a random walk with zero average on a d-dimensional lattice, then the sequence (nα) nu is uniformly distributed modulo 1 if and only if α.

L’objet de ce travail est d’étudier les propriétés arithmétiques et statistiques des mots infinis et des suites de nombres entiers engendrés par des substitutions sur un alphabet infini ou par des automates déterministes ayant un nombre infini dénombrable d’états. En particulier, nous montrons que si u est une suite de nombres entiers engendrée par un automate dont le graphe étiqueté associé représente une marche aléatoire de moyenne nulle sur un réseau de d (d entier positif), alors la suite (nα) nu est équirépartie modulo 1 si et seulement si α.

DOI: 10.5802/aif.2248
Classification: 11B85,  11K06,  11L15,  68Q45,  68R15
Keywords: Infinite words, substitutions, automata, uniform distribution modulo 1
@article{AIF_2006__56_7_2525_0,
     author = {Mauduit, Christian},
     title = {Propri\'et\'es arithm\'etiques des substitutions et automates infinis},
     journal = {Annales de l'Institut Fourier},
     pages = {2525--2549},
     publisher = {Association des Annales de l{\textquoteright}institut Fourier},
     volume = {56},
     number = {7},
     year = {2006},
     doi = {10.5802/aif.2248},
     mrnumber = {2290789},
     zbl = {1147.11016},
     language = {fr},
     url = {https://aif.centre-mersenne.org/articles/10.5802/aif.2248/}
}
TY  - JOUR
TI  - Propriétés arithmétiques des substitutions et automates infinis
JO  - Annales de l'Institut Fourier
PY  - 2006
DA  - 2006///
SP  - 2525
EP  - 2549
VL  - 56
IS  - 7
PB  - Association des Annales de l’institut Fourier
UR  - https://aif.centre-mersenne.org/articles/10.5802/aif.2248/
UR  - https://www.ams.org/mathscinet-getitem?mr=2290789
UR  - https://zbmath.org/?q=an%3A1147.11016
UR  - https://doi.org/10.5802/aif.2248
DO  - 10.5802/aif.2248
LA  - fr
ID  - AIF_2006__56_7_2525_0
ER  - 
%0 Journal Article
%T Propriétés arithmétiques des substitutions et automates infinis
%J Annales de l'Institut Fourier
%D 2006
%P 2525-2549
%V 56
%N 7
%I Association des Annales de l’institut Fourier
%U https://doi.org/10.5802/aif.2248
%R 10.5802/aif.2248
%G fr
%F AIF_2006__56_7_2525_0
Mauduit, Christian. Propriétés arithmétiques des substitutions et automates infinis. Annales de l'Institut Fourier, Volume 56 (2006) no. 7, pp. 2525-2549. doi : 10.5802/aif.2248. https://aif.centre-mersenne.org/articles/10.5802/aif.2248/

[1] Allouche, Jean-Paul; Shallit, J. Automatic sequences. Theory, applications, generalizations, Cambridge Univ. Press, Cambridge, 2003 | MR | Zbl

[2] Banderier, Cyril; Bousquet-Mélou, Mireille; Denise, Alain; Flajolet, Philippe; Gardy, Danièle; Gouyou-Beauchamps, Dominique Generating functions of generating trees, Discrete Mathematics, Tome 246 (2002) no. 1-3, pp. 29-55 | DOI | MR | Zbl

[3] Banderier, Cyril; Flajolet, Philippe Basic analytic combinatorics of directed lattice paths, Theoretical Computer Science, Tome 281 (2002) no. 1-2, pp. 37-80 | DOI | MR | Zbl

[4] Banks, W.; Conlitti, A.; Shparlinski, I. E. Character sums over integers with restricted g-ary digits, Illinois J. Math., Tome 46 (2002), pp. 819-836 | MR | Zbl

[5] Banks, W.; Shparlinski, I.E. Arithmetic properties of numbers with restricted digits, Acta Arithmetica, Tome 112 (2004), pp. 313-332 | DOI | MR | Zbl

[6] Cassaigne, Julien Complexité et facteurs spéciaux, Bull. Belg. Math. Soc., Tome 4 (1997) no. 1, pp. 67-88 | MR | Zbl

[7] Caucal, D. A hierarchy of graph families (preprint)

[8] Cobham, A. On the base-dependence of sets of numbers recognizable by finite automata, Math. Syst. Theory, Tome 3 (1969), pp. 186-192 | DOI | MR | Zbl

[9] Cobham, A. Uniform tag sequences, Math. Syst. Theory, Tome 6 (1972), pp. 164-192 | DOI | MR | Zbl

[10] Coquet, J. On the uniform distribution modulo one of some subsequences of polynomial sequences, J. Number Theory, Tome 10 (1978), pp. 291-296 | DOI | MR | Zbl

[11] Coquet, J. On the uniform distribution modulo one of some subsequences of polynomial sequences II,, J. Number Theory, Tome 12 (1980), pp. 244-250 | DOI | MR | Zbl

[12] Coquet, J. Graphes connexes, représentation des entiers et équirépartition, J. Number Theory, Tome 16 (1983), pp. 363-375 | DOI | MR | Zbl

[13] Dartyge, C.; Mauduit, C. Nombres presque premiers dont l’écriture en base r ne comporte pas certains chiffres, Journal of Number Theory, Tome 81 (2000), pp. 270-291 | DOI | MR | Zbl

[14] Dartyge, C.; Mauduit, C. Ensembles de densité nulle contenant des entiers possédant au plus deux facteurs premiers, Journal of Number Theory, Tome 91 (2001), pp. 230-255 | DOI | MR | Zbl

[15] Eilenberg, S. Automata, languages and machines, Pure and Applied Mathematics, Tome A, Academic Press, New York, 1974 | Zbl

[16] Erdős, P.; Mauduit, C.; Sárközy, A. On arithmetic properties of integers with missing digits, I, J. Number Theory, Tome 70 (1998), pp. 99-120 | DOI | MR | Zbl

[17] Erdős, P.; Mauduit, C.; Sárközy, A. On arithmetic properties of integers with missing digits, II, Discrete Math., Tome 200 (1999), pp. 149-164 | DOI | MR | Zbl

[18] Ferenczi, S. Substitution on infinite alphabet (Ann. Inst. Fourier, à paraître)

[19] Filaseta, M.; Konyagin, S. V. Squarefree values of polynomials all of whose coefficients are 0 and 1, Acta Arith., Tome 74 (1996), pp. 191-205 | MR | Zbl

[20] Flajolet, P.; Sedgewick, R. Analytic combinatorics (en préparation)

[21] Fouvry, E.; Mauduit, C. Sur les entiers dont la somme des chiffres est moyenne, J. Number Theory, Tome 114 (2005), pp. 135-152 | DOI | MR | Zbl

[22] Gambaudo, J.-M.; Hubert, P.; Tisseur, P.; Vaienti (Eds), S. Dynamical systems : from crystal to chaos, World Scientific, Cambridge, 2000 (Proceedings in honor of G. Rauzy on his 60th birthday) | MR | Zbl

[23] Konyagin, S. V. Arithmetic properties of integers with missing digits : distribution in residue classes, Period. Math. Hungar., Tome 42 (2001), pp. 145-162 | DOI | MR | Zbl

[24] Konyagin, S. V.; Mauduit, C.; Sárközy, A. On the number of prime factors of integers characterized by digit properties, Period. Math. Hungar., Tome 40 (2000), pp. 37-52 | DOI | MR | Zbl

[25] Le Gonidec, M. Sur la complexité des mots infinis engendrés par des q-automates dénombrables (Ann. Inst. Fourier, à paraître) | Numdam

[26] Mauduit, C. Automates finis et ensembles normaux, Ann. Inst. Fourier, Tome 36 (1986), pp. 1-25 | DOI | Numdam | MR | Zbl

[27] Mauduit, C. Sur l’ensemble normal des substitutions de longueur quelconque, J. Number Theory, Tome 29 (1988), pp. 235-250 | DOI | MR | Zbl

[28] Mauduit, C. Caractérisation des ensembles normaux substitutifs, Invent. Math., Tome 95 (1989), pp. 133-147 | DOI | MR | Zbl

[29] Minsky, M. L.; Papert, S. Unrecognizable sets of numbers, J. Assoc. Comput. Mach., Tome 13 (1966), pp. 281-286 | MR | Zbl

[30] Pytheas Fogg, N. Substitutions in dynamicals, arithmetics and combinatorics, Lecture Notes in Mathematics, 1794, Springer-Verlag, Berlin, 2002 (Edited by V. Berthé, S. Ferenczi, C. Mauduit and A. Siegel) | MR | Zbl

[31] Queffelec, M. Substitution dynamical systems - Spectral analysis, Lecture Notes in Mathematics, 1294, Springer-Verlag, Berlin, 1987 | MR | Zbl

[32] Rauzy, G. Propriétés statistiques de suites arithmétiques, Collection SUP, Presses universitaires de France, Paris, 1976 | MR | Zbl

[33] Ritchie, R. W. Finite automata and the set of squares, J. Assoc. Comput. Mach., Tome 10 (1963), pp. 528-531 | MR | Zbl

[34] Spitzer, F. Principles of random walks, second edition, Graduate Texts in Mathematics, Tome 34, Springer-Verlag, New-York-Heidelberg, 1976 | MR | Zbl

[35] Thomas, W. A short introduction to infinite automata, 5 th DLT 01 LNCS, Tome 2295 (2001), pp. 134-144 (W. Kuich, G. Rosenberg, A. Salomaa (Eds)) | MR | Zbl

[36] Thomas, W. Constructing infinite graphs with a decidable monadic theory, 28 th MFCS LNCS, Tome 2747 (2003), pp. 113-124 (R. Rovan, Vojtáš (Eds)) | MR | Zbl

Cited by Sources: