Propriétés arithmétiques des substitutions et automates infinis

Mauduit, Christian

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 ${\left(n\alpha \right)}_{n\in u}$ est équirépartie modulo 1 si et seulement si $\alpha \in ℝ\setminus \mathbb{Q}$.

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 ${\left(n\alpha \right)}_{n\in u}$ is uniformly distributed modulo 1 if and only if $\alpha \in ℝ\setminus \mathbb{Q}$.

[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, Volume 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, Volume 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., Volume 46 (2002), pp. 819-836 | MR | Zbl

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

[6] Cassaigne, Julien Complexité et facteurs spéciaux, Bull. Belg. Math. Soc., Volume 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, Volume 3 (1969), pp. 186-192 | DOI | MR | Zbl

[9] Cobham, A. Uniform tag sequences, Math. Syst. Theory, Volume 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, Volume 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, Volume 12 (1980), pp. 244-250 | DOI | MR | Zbl

[12] Coquet, J. Graphes connexes, représentation des entiers et équirépartition, J. Number Theory, Volume 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, Volume 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, Volume 91 (2001), pp. 230-255 | DOI | MR | Zbl

[15] Eilenberg, S. Automata, languages and machines, Pure and Applied Mathematics, 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, Volume 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., Volume 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., Volume 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, Volume 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., Volume 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., Volume 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, Volume 36 (1986), pp. 1-25 | DOI | Numdam | MR | Zbl

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

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

[29] Minsky, M. L.; Papert, S. Unrecognizable sets of numbers, J. Assoc. Comput. Mach., Volume 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., Volume 10 (1963), pp. 528-531 | MR | Zbl

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

[35] Thomas, W. A short introduction to infinite automata, 5^th DLT 01 LNCS, Volume 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, Volume 2747 (2003), pp. 113-124 R. Rovan, Vojtáš (Eds) | MR | Zbl