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

Mauduit, Christian

Annales de l'Institut Fourier, Tome 56 (2006), p. 2525-2549 / Harvested from Numdam

Résumé

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 $\mathbb{R}^d$ ($d$ entier positif), alors la suite $(n \alpha )_{n\in u}$ est équirépartie modulo 1 si et seulement si $\alpha \in \mathbb{R}\setminus \mathbb{Q}$.

Abstract

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

Détail

Publié le : 2006-01-01

MR 2290789 | Zbl 1147.11016 | 3 citations dans Numdam

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

Bibliographie

[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, Tome 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, Tome 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., Tome 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, Tome 112 (2004), pp. 313-332 | Article | MR 2046944 | Zbl 1049.11003

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

[9] Cobham, A. Uniform tag sequences, Math. Syst. Theory, Tome 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, Tome 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, Tome 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, Tome 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, Tome 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, Tome 91 (2001), pp. 230-255 | Article | MR 1876274 | Zbl 0988.11042

[15] Eilenberg, S. Automata, languages and machines, Academic Press, New York, Pure and Applied Mathematics, Tome A (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, Tome 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., Tome 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., Tome 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, Tome 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., Tome 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., Tome 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, Tome 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, Tome 29 (1988), pp. 235-250 | Article | MR 955950 | Zbl 0655.10053

[28] Mauduit, C. Caractérisation des ensembles normaux substitutifs, Invent. Math., Tome 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., Tome 13 (1966), pp. 281-286 | MR 207481 | Zbl 0166.00601

[30] Pytheas Fogg, N. Substitutions in dynamicals, arithmetics and combinatorics, Springer-Verlag, Berlin, Lecture Notes in Mathematics, 1794 (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, Springer-Verlag, Berlin, Lecture Notes in Mathematics, 1294 (1987) | MR 924156 | Zbl 0642.28013

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

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

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

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