Propriétés arithmétiques des substitutions et automates infinis
Annales de l'Institut Fourier, Tome 56 (2006) no. 7, pp. 2525-2549.

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 α.

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 α.

DOI : https://doi.org/10.5802/aif.2248
Classification : 11B85,  11K06,  11L15,  68Q45,  68R15
Mots clés : mots infinis, substitutions, automates, équirépartition 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 = {http://archive.numdam.org/articles/10.5802/aif.2248/}
}
Mauduit, Christian. Propriétés arithmétiques des substitutions et automates infinis. Annales de l'Institut Fourier, Tome 56 (2006) no. 7, pp. 2525-2549. doi : 10.5802/aif.2248. http://archive.numdam.org/articles/10.5802/aif.2248/

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

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

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

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

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

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

[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, Volume 3 (1969), pp. 186-192 | Article | MR 250789 | Zbl 0179.02501

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

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

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

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

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

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

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

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

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

[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., Volume 74 (1996), pp. 191-205 | MR 1373708 | Zbl 0854.11015

[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, Volume 114 (2005), pp. 135-152 | Article | MR 2163909 | Zbl 02207373

[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 1796140 | Zbl 0946.00018

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

[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., Volume 40 (2000), pp. 37-52 | Article | MR 1774933 | Zbl 0963.11005

[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, Volume 36 (1986), pp. 1-25 | Article | Numdam | MR 850740 | Zbl 0576.10026

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

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

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

[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 1970385 | Zbl 1014.11015

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

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

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

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

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

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