Arithmetics properties of substitutions and infinite automata

Christian Mauduit[1]

  • [1] Institut de Mathématiques de Luminy 163, avenue de Luminy case 907 13288 Marseille cedex 9 (France)

Annales de l’institut Fourier (2006)

  • Volume: 56, Issue: 7, page 2525-2549
  • ISSN: 0373-0956

Abstract

top
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 α ) n ∈ u is uniformly distributed modulo 1 if and only if α ∈ ℝ ∖ ℚ .

How to cite

top

Mauduit, Christian. "Propriétés arithmétiques des substitutions et automates infinis." Annales de l’institut Fourier 56.7 (2006): 2525-2549. <http://eudml.org/doc/10212>.

@article{Mauduit2006,
abstract = {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\}$.},
affiliation = {Institut de Mathématiques de Luminy 163, avenue de Luminy case 907 13288 Marseille cedex 9 (France)},
author = {Mauduit, Christian},
journal = {Annales de l’institut Fourier},
keywords = {Infinite words; substitutions; automata; uniform distribution modulo 1},
language = {fre},
number = {7},
pages = {2525-2549},
publisher = {Association des Annales de l’institut Fourier},
title = {Propriétés arithmétiques des substitutions et automates infinis},
url = {http://eudml.org/doc/10212},
volume = {56},
year = {2006},
}

TY - JOUR
AU - Mauduit, Christian
TI - Propriétés arithmétiques des substitutions et automates infinis
JO - Annales de l’institut Fourier
PY - 2006
PB - Association des Annales de l’institut Fourier
VL - 56
IS - 7
SP - 2525
EP - 2549
AB - 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}$.
LA - fre
KW - Infinite words; substitutions; automata; uniform distribution modulo 1
UR - http://eudml.org/doc/10212
ER -

References

top
  1. Jean-Paul Allouche, J. Shallit, Automatic sequences. Theory, applications, generalizations, (2003), Cambridge Univ. Press, Cambridge Zbl1086.11015MR1997038
  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), 29-55 Zbl0997.05007MR1884885
  3. Cyril Banderier, Philippe Flajolet, Basic analytic combinatorics of directed lattice paths, Theoretical Computer Science 281 (2002), 37-80 Zbl0996.68126MR1909568
  4. W. Banks, A. Conlitti, I. E. Shparlinski, Character sums over integers with restricted g-ary digits, Illinois J. Math. 46 (2002), 819-836 Zbl1026.11068MR1951242
  5. W. Banks, I.E. Shparlinski, Arithmetic properties of numbers with restricted digits, Acta Arithmetica 112 (2004), 313-332 Zbl1049.11003MR2046944
  6. Julien Cassaigne, Complexité et facteurs spéciaux, Bull. Belg. Math. Soc. 4 (1997), 67-88 Zbl0921.68065MR1440670
  7. D. Caucal, A hierarchy of graph families Zbl0765.68082
  8. A. Cobham, On the base-dependence of sets of numbers recognizable by finite automata, Math. Syst. Theory 3 (1969), 186-192 Zbl0179.02501MR250789
  9. A. Cobham, Uniform tag sequences, Math. Syst. Theory 6 (1972), 164-192 Zbl0253.02029MR457011
  10. J. Coquet, On the uniform distribution modulo one of some subsequences of polynomial sequences, J. Number Theory 10 (1978), 291-296 Zbl0382.10034MR506123
  11. J. Coquet, On the uniform distribution modulo one of some subsequences of polynomial sequences II,, J. Number Theory 12 (1980), 244-250 Zbl0432.10026MR578819
  12. J. Coquet, Graphes connexes, représentation des entiers et équirépartition, J. Number Theory 16 (1983), 363-375 Zbl0512.10041MR707609
  13. C. Dartyge, C. Mauduit, Nombres presque premiers dont l’écriture en base r ne comporte pas certains chiffres, Journal of Number Theory 81 (2000), 270-291 Zbl0957.11039MR1752255
  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), 230-255 Zbl0988.11042MR1876274
  15. S. Eilenberg, Automata, languages and machines, A (1974), Academic Press, New York Zbl0359.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), 99-120 Zbl0923.11024MR1625049
  17. P. Erdős, C. Mauduit, A. Sárközy, On arithmetic properties of integers with missing digits, II, Discrete Math. 200 (1999), 149-164 Zbl0945.11006MR1692287
  18. S. Ferenczi, Substitution on infinite alphabet 
  19. M. Filaseta, S. V. Konyagin, Squarefree values of polynomials all of whose coefficients are 0 and 1, Acta Arith. 74 (1996), 191-205 Zbl0854.11015MR1373708
  20. P. Flajolet, R. Sedgewick, Analytic combinatorics 
  21. E. Fouvry, C. Mauduit, Sur les entiers dont la somme des chiffres est moyenne, J. Number Theory 114 (2005), 135-152 Zbl1084.11045MR2163909
  22. J.-M. Gambaudo, P. Hubert, P. Tisseur, S. Vaienti (Eds), Dynamical systems : from crystal to chaos, (2000), World Scientific, Cambridge Zbl0946.00018MR1796140
  23. S. V. Konyagin, Arithmetic properties of integers with missing digits : distribution in residue classes, Period. Math. Hungar. 42 (2001), 145-162 Zbl0980.11006MR1832701
  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), 37-52 Zbl0963.11005MR1774933
  25. M. Le Gonidec, Sur la complexité des mots infinis engendrés par des q-automates dénombrables 
  26. C. Mauduit, Automates finis et ensembles normaux, Ann. Inst. Fourier 36 (1986), 1-25 Zbl0576.10026MR850740
  27. C. Mauduit, Sur l’ensemble normal des substitutions de longueur quelconque, J. Number Theory 29 (1988), 235-250 Zbl0655.10053MR955950
  28. C. Mauduit, Caractérisation des ensembles normaux substitutifs, Invent. Math. 95 (1989), 133-147 Zbl0665.10035MR969415
  29. M. L. Minsky, S. Papert, Unrecognizable sets of numbers, J. Assoc. Comput. Mach. 13 (1966), 281-286 Zbl0166.00601MR207481
  30. N. Pytheas Fogg, Substitutions in dynamicals, arithmetics and combinatorics, (2002), Springer-Verlag, Berlin Zbl1014.11015MR1970385
  31. M. Queffelec, Substitution dynamical systems - Spectral analysis, (1987), Springer-Verlag, Berlin Zbl0642.28013MR924156
  32. G. Rauzy, Propriétés statistiques de suites arithmétiques, (1976), Presses universitaires de France, Paris Zbl0337.10036MR409397
  33. R. W. Ritchie, Finite automata and the set of squares, J. Assoc. Comput. Mach. 10 (1963), 528-531 Zbl0118.12601MR167374
  34. F. Spitzer, Principles of random walks, second edition, 34 (1976), Springer-Verlag, New-York-Heidelberg Zbl0359.60003MR388547
  35. W. Thomas, A short introduction to infinite automata, 5 DLT 01 LNCS 2295 (2001), 134-144 Zbl1073.68671MR1964166
  36. W. Thomas, Constructing infinite graphs with a decidable monadic theory, 28 MFCS LNCS 2747 (2003), 113-124 Zbl1124.03314MR2081322

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.