Table of contents for this issue | Previous article | Next article
Christian Mauduit
Propriétés arithmétiques des substitutions et automates infinis
(Arithmetics properties of substitutions and infinite automata)
Annales de l'institut Fourier, 56 no. 7 (2006), p. 2525-2549, doi: 10.5802/aif.2248
Article PDF | Reviews MR 2290789 | Zbl 1147.11016 | 3 citations in Cedram
Class. Math.: 11B85, 11K06, 11L15, 68Q45, 68R15
Keywords: Infinite words, substitutions, automata, uniform distribution modulo 1
[1] Jean-Paul Allouche & J. Shallit, Automatic sequences. Theory, applications, generalizations, Cambridge Univ. Press, Cambridge, 2003 MR 1997038 | Zbl 01993704
[2] Cyril Banderier, Mireille Bousquet-Mélou, Alain Denise, Philippe Flajolet, Danièle Gardy & Dominique Gouyou-Beauchamps, “Generating functions of generating trees”, Discrete Mathematics 246 (2002) no. 1-3, p. 29-55 Article | MR 1884885 | Zbl 0997.05007
[3] Cyril Banderier & Philippe Flajolet, “Basic analytic combinatorics of directed lattice paths”, Theoretical Computer Science 281 (2002) no. 1-2, p. 37-80 Article | MR 1909568 | Zbl 0996.68126
[4] W. Banks, A. Conlitti & I. E. Shparlinski, “Character sums over integers with restricted
[5] W. Banks & I.E. Shparlinski, “Arithmetic properties of numbers with restricted digits”, Acta Arithmetica 112 (2004), p. 313-332 Article | MR 2046944 | Zbl 1049.11003
[6] Julien Cassaigne, “Complexité et facteurs spéciaux”, Bull. Belg. Math. Soc. 4 (1997) no. 1, p. 67-88 Article | MR 1440670 | Zbl 0921.68065
[7] D. Caucal, “A hierarchy of graph families”, preprint
[8] A. Cobham, “On the base-dependence of sets of numbers recognizable by finite automata”, Math. Syst. Theory 3 (1969), p. 186-192 Article | MR 250789 | Zbl 0179.02501
[9] A. Cobham, “Uniform tag sequences”, Math. Syst. Theory 6 (1972), p. 164-192 Article | MR 457011 | Zbl 0253.02029
[10] J. Coquet, “On the uniform distribution modulo one of some subsequences of polynomial sequences”, J. Number Theory 10 (1978), p. 291-296 Article | MR 506123 | Zbl 0382.10034
[11] J. Coquet, “On the uniform distribution modulo one of some subsequences of polynomial sequences II,”, J. Number Theory 12 (1980), p. 244-250 Article | MR 578819 | Zbl 0432.10026
[12] J. Coquet, “Graphes connexes, représentation des entiers et équirépartition”, J. Number Theory 16 (1983), p. 363-375 Article | MR 707609 | Zbl 0512.10041
[13] C. Dartyge & C. Mauduit, “Nombres presque premiers dont l’écriture en base
[14] C. Dartyge & C. Mauduit, “Ensembles de densité nulle contenant des entiers possédant au plus deux facteurs premiers”, Journal of Number Theory 91 (2001), p. 230-255 Article | MR 1876274 | Zbl 0988.11042
[15] S. Eilenberg, Automata, languages and machines, Pure and Applied Mathematics A, Academic Press, New York, 1974 Zbl 0359.94067
[16] P. Erdős, C. Mauduit & A. Sárközy, “On arithmetic properties of integers with missing digits, I”, J. Number Theory 70 (1998), p. 99-120 Article | MR 1625049 | Zbl 0923.11024
[17] P. Erdős, C. Mauduit & A. Sárközy, “On arithmetic properties of integers with missing digits, II”, Discrete Math. 200 (1999), p. 149-164 Article | MR 1692287 | Zbl 0945.11006
[18] S. Ferenczi, “Substitution on infinite alphabet”, Ann. Inst. Fourier, à paraître
[19] M. Filaseta & S. V. Konyagin, “Squarefree values of polynomials all of whose coefficients are 0 and 1”, Acta Arith. 74 (1996), p. 191-205 Article | MR 1373708 | Zbl 0854.11015
[20] P. Flajolet & R. Sedgewick, “Analytic combinatorics”, en préparation
[21] E. Fouvry & C. Mauduit, “Sur les entiers dont la somme des chiffres est moyenne”, J. Number Theory 114 (2005), p. 135-152 Article | MR 2163909 | Zbl 02207373
[22] J.-M. Gambaudo, P. Hubert, P. Tisseur & S. Vaienti (Eds), 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] S. V. Konyagin, “Arithmetic properties of integers with missing digits : distribution in residue classes”, Period. Math. Hungar. 42 (2001), p. 145-162 Article | MR 1832701 | Zbl 0980.11006
[24] S. V. Konyagin, C. Mauduit & A. Sárközy, “On the number of prime factors of integers characterized by digit properties”, Period. Math. Hungar. 40 (2000), p. 37-52 Article | MR 1774933 | Zbl 0963.11005
[25] M. Le Gonidec, “Sur la complexité des mots infinis engendrés par des
[26] C. Mauduit, “Automates finis et ensembles normaux”, Ann. Inst. Fourier 36 (1986), p. 1-25 Cedram | MR 850740 | Zbl 0576.10026
[27] C. Mauduit, “Sur l’ensemble normal des substitutions de longueur quelconque”, J. Number Theory 29 (1988), p. 235-250 Article | MR 955950 | Zbl 0655.10053
[28] C. Mauduit, “Caractérisation des ensembles normaux substitutifs”, Invent. Math. 95 (1989), p. 133-147 Article | MR 969415 | Zbl 0665.10035
[29] M. L. Minsky & S. Papert, “Unrecognizable sets of numbers”, J. Assoc. Comput. Mach. 13 (1966), p. 281-286 MR 207481 | Zbl 0166.00601
[30] N. Pytheas Fogg, Substitutions in dynamicals, arithmetics and combinatorics, Lecture Notes in Mathematics,
[31] M. Queffelec, Substitution dynamical systems - Spectral analysis, Lecture Notes in Mathematics,
[32] G. Rauzy, Propriétés statistiques de suites arithmétiques, Collection SUP, Presses universitaires de France, Paris, 1976 MR 409397 | Zbl 0337.10036
[33] R. W. Ritchie, “Finite automata and the set of squares”, J. Assoc. Comput. Mach. 10 (1963), p. 528-531 MR 167374 | Zbl 0118.12601
[34] F. Spitzer, Principles of random walks, second edition, Graduate Texts in Mathematics 34, Springer-Verlag, New-York-Heidelberg, 1976 MR 388547 | Zbl 0359.60003
[35] W. Thomas, “A short introduction to infinite automata”, 5
[36] W. Thomas, “Constructing infinite graphs with a decidable monadic theory”, 28
Christian Mauduit
Propriétés arithmétiques des substitutions et automates infinis
(Arithmetics properties of substitutions and infinite automata)
Annales de l'institut Fourier, 56 no. 7 (2006), p. 2525-2549, doi: 10.5802/aif.2248
Article PDF | Reviews MR 2290789 | Zbl 1147.11016 | 3 citations in Cedram
Class. Math.: 11B85, 11K06, 11L15, 68Q45, 68R15
Keywords: Infinite words, substitutions, automata, uniform distribution modulo 1
Résumé - 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}$.
Bibliography
[2] Cyril Banderier, Mireille Bousquet-Mélou, Alain Denise, Philippe Flajolet, Danièle Gardy & Dominique Gouyou-Beauchamps, “Generating functions of generating trees”, Discrete Mathematics 246 (2002) no. 1-3, p. 29-55 Article | MR 1884885 | Zbl 0997.05007
[3] Cyril Banderier & Philippe Flajolet, “Basic analytic combinatorics of directed lattice paths”, Theoretical Computer Science 281 (2002) no. 1-2, p. 37-80 Article | MR 1909568 | Zbl 0996.68126
[4] W. Banks, A. Conlitti & I. E. Shparlinski, “Character sums over integers with restricted
g-ary digits”, Illinois J. Math. 46 (2002), p. 819-836 Article | MR 1951242 | Zbl 1026.11068[5] W. Banks & I.E. Shparlinski, “Arithmetic properties of numbers with restricted digits”, Acta Arithmetica 112 (2004), p. 313-332 Article | MR 2046944 | Zbl 1049.11003
[6] Julien Cassaigne, “Complexité et facteurs spéciaux”, Bull. Belg. Math. Soc. 4 (1997) no. 1, p. 67-88 Article | MR 1440670 | Zbl 0921.68065
[7] D. Caucal, “A hierarchy of graph families”, preprint
[8] A. Cobham, “On the base-dependence of sets of numbers recognizable by finite automata”, Math. Syst. Theory 3 (1969), p. 186-192 Article | MR 250789 | Zbl 0179.02501
[9] A. Cobham, “Uniform tag sequences”, Math. Syst. Theory 6 (1972), p. 164-192 Article | MR 457011 | Zbl 0253.02029
[10] J. Coquet, “On the uniform distribution modulo one of some subsequences of polynomial sequences”, J. Number Theory 10 (1978), p. 291-296 Article | MR 506123 | Zbl 0382.10034
[11] J. Coquet, “On the uniform distribution modulo one of some subsequences of polynomial sequences II,”, J. Number Theory 12 (1980), p. 244-250 Article | MR 578819 | Zbl 0432.10026
[12] J. Coquet, “Graphes connexes, représentation des entiers et équirépartition”, J. Number Theory 16 (1983), p. 363-375 Article | MR 707609 | Zbl 0512.10041
[13] C. Dartyge & C. Mauduit, “Nombres presque premiers dont l’écriture en base
rne comporte pas certains chiffres”, Journal of Number Theory 81 (2000), p. 270-291 Article | MR 1752255 | Zbl 0957.11039[14] C. Dartyge & C. Mauduit, “Ensembles de densité nulle contenant des entiers possédant au plus deux facteurs premiers”, Journal of Number Theory 91 (2001), p. 230-255 Article | MR 1876274 | Zbl 0988.11042
[15] S. Eilenberg, Automata, languages and machines, Pure and Applied Mathematics A, Academic Press, New York, 1974 Zbl 0359.94067
[16] P. Erdős, C. Mauduit & A. Sárközy, “On arithmetic properties of integers with missing digits, I”, J. Number Theory 70 (1998), p. 99-120 Article | MR 1625049 | Zbl 0923.11024
[17] P. Erdős, C. Mauduit & A. Sárközy, “On arithmetic properties of integers with missing digits, II”, Discrete Math. 200 (1999), p. 149-164 Article | MR 1692287 | Zbl 0945.11006
[18] S. Ferenczi, “Substitution on infinite alphabet”, Ann. Inst. Fourier, à paraître
[19] M. Filaseta & S. V. Konyagin, “Squarefree values of polynomials all of whose coefficients are 0 and 1”, Acta Arith. 74 (1996), p. 191-205 Article | MR 1373708 | Zbl 0854.11015
[20] P. Flajolet & R. Sedgewick, “Analytic combinatorics”, en préparation
[21] E. Fouvry & C. Mauduit, “Sur les entiers dont la somme des chiffres est moyenne”, J. Number Theory 114 (2005), p. 135-152 Article | MR 2163909 | Zbl 02207373
[22] J.-M. Gambaudo, P. Hubert, P. Tisseur & S. Vaienti (Eds), 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] S. V. Konyagin, “Arithmetic properties of integers with missing digits : distribution in residue classes”, Period. Math. Hungar. 42 (2001), p. 145-162 Article | MR 1832701 | Zbl 0980.11006
[24] S. V. Konyagin, C. Mauduit & A. Sárközy, “On the number of prime factors of integers characterized by digit properties”, Period. Math. Hungar. 40 (2000), p. 37-52 Article | MR 1774933 | Zbl 0963.11005
[25] M. Le Gonidec, “Sur la complexité des mots infinis engendrés par des
q-automates dénombrables”, Ann. Inst. Fourier, à paraître Cedram[26] C. Mauduit, “Automates finis et ensembles normaux”, Ann. Inst. Fourier 36 (1986), p. 1-25 Cedram | MR 850740 | Zbl 0576.10026
[27] C. Mauduit, “Sur l’ensemble normal des substitutions de longueur quelconque”, J. Number Theory 29 (1988), p. 235-250 Article | MR 955950 | Zbl 0655.10053
[28] C. Mauduit, “Caractérisation des ensembles normaux substitutifs”, Invent. Math. 95 (1989), p. 133-147 Article | MR 969415 | Zbl 0665.10035
[29] M. L. Minsky & S. Papert, “Unrecognizable sets of numbers”, J. Assoc. Comput. Mach. 13 (1966), p. 281-286 MR 207481 | Zbl 0166.00601
[30] N. Pytheas Fogg, 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] M. Queffelec, Substitution dynamical systems - Spectral analysis, Lecture Notes in Mathematics,
1294, Springer-Verlag, Berlin, 1987 MR 924156 | Zbl 0642.28013[32] G. Rauzy, Propriétés statistiques de suites arithmétiques, Collection SUP, Presses universitaires de France, Paris, 1976 MR 409397 | Zbl 0337.10036
[33] R. W. Ritchie, “Finite automata and the set of squares”, J. Assoc. Comput. Mach. 10 (1963), p. 528-531 MR 167374 | Zbl 0118.12601
[34] F. Spitzer, Principles of random walks, second edition, Graduate Texts in Mathematics 34, Springer-Verlag, New-York-Heidelberg, 1976 MR 388547 | Zbl 0359.60003
[35] W. Thomas, “A short introduction to infinite automata”, 5
[36] W. Thomas, “Constructing infinite graphs with a decidable monadic theory”, 28
© Annales de L'Institut Fourier - ISSN (électronique) : 1777-5310