Codages de rotations et phénomènes d'autosimilarité

Boris Adamczewski

Journal de théorie des nombres de Bordeaux (2002)

  • Volume: 14, Issue: 2, page 351-386
  • ISSN: 1246-7405

Abstract

top
The paper focus on a class of symbolic sequences obtained by encoding rotations and offering a geometric framework for the study of generalizations of Sturmian sequences. Those symbolic sequences also appear in problems related to the uniform distribution of the sequences ( n α ) n ∈ ℕ . We show that they can be computed by iterating four different substitutions over a three-letter alphabet, followed by an appropriate projection. The iteration schema is governed by a two-dimensional continued fraction algorithm satisfying a full Lagrange type theorem. This property is used to characterize the subset of sequences having a self-similar structure and then to deduce a quantitative unbalance property for these particular codings.

How to cite

top

Adamczewski, Boris. "Codages de rotations et phénomènes d'autosimilarité." Journal de théorie des nombres de Bordeaux 14.2 (2002): 351-386. <http://eudml.org/doc/252260>.

@article{Adamczewski2002,
abstract = {Nous étudions une classe de suites symboliques, les codages de rotations, intervenant dans des problèmes de répartition des suites $(n \alpha )_\{n \in \mathbb \{N\}\}$ et représentant une généralisation géométrique des suites sturmiennes. Nous montrons que ces suites peuvent être obtenues par itération de quatre substitutions définies sur un alphabet à trois lettres, puis en appliquant un morphisme de projection. L’ordre d’itération de ces applications est gouverné par un développement bi-dimensionnel de type “fraction continue” vérifiant un théorème de Lagrange. Nous utilisons ensuite cette propriété pour caractériser les codages de rotations faisant intervenir des phénomènes d’autosimilarité, puis en déduire une propriété de déséquilibre du langage de ces codages.},
author = {Adamczewski, Boris},
journal = {Journal de théorie des nombres de Bordeaux},
keywords = {coding of rotation; Sturmian sequences; uniform distribution; substitution; continued fraction},
language = {fre},
number = {2},
pages = {351-386},
publisher = {Université Bordeaux I},
title = {Codages de rotations et phénomènes d'autosimilarité},
url = {http://eudml.org/doc/252260},
volume = {14},
year = {2002},
}

TY - JOUR
AU - Adamczewski, Boris
TI - Codages de rotations et phénomènes d'autosimilarité
JO - Journal de théorie des nombres de Bordeaux
PY - 2002
PB - Université Bordeaux I
VL - 14
IS - 2
SP - 351
EP - 386
AB - Nous étudions une classe de suites symboliques, les codages de rotations, intervenant dans des problèmes de répartition des suites $(n \alpha )_{n \in \mathbb {N}}$ et représentant une généralisation géométrique des suites sturmiennes. Nous montrons que ces suites peuvent être obtenues par itération de quatre substitutions définies sur un alphabet à trois lettres, puis en appliquant un morphisme de projection. L’ordre d’itération de ces applications est gouverné par un développement bi-dimensionnel de type “fraction continue” vérifiant un théorème de Lagrange. Nous utilisons ensuite cette propriété pour caractériser les codages de rotations faisant intervenir des phénomènes d’autosimilarité, puis en déduire une propriété de déséquilibre du langage de ces codages.
LA - fre
KW - coding of rotation; Sturmian sequences; uniform distribution; substitution; continued fraction
UR - http://eudml.org/doc/252260
ER -

References

top
  1. [1] B. Adamczewski, Répartitions des suites (nα)n∈N et substitutions. Acta Arith., à paraître. Zbl1060.11043
  2. [2] P. Arnoux, G. Rauzy, Représentation géométrique de suites de complexité 2n + 1. Bull. Soc. Math. France119 (1991), 199-215. Zbl0789.28011MR1116845
  3. [3] V. Berthé, R. Tijdeman, Balance properties of multi-dimensional words. Theoret. Comput. Sci.273 (2002), 197-224. Zbl0997.68091MR1872450
  4. [4] M.D. Boshernitzan, C.R. Carroll, An extension of Lagrange's theorem to interval exchange transformations over quadratic fields. J. Anal. Math.72 (1997), 21-44. Zbl0931.28013MR1482988
  5. [5] J. Cassaigne, S. Ferenczi, L.Q. Zamboni, Imbalances in Arnoux-Rauzy sequences. Ann. Inst. Fourier (Grenoble) 50 (2000), 1265-1276. Zbl1004.37008MR1799745
  6. [6] E.M. Coven, G.A. Hedlund, Sequences with minimal block growth. Math. Systems Theory7 (1973), 138-153. Zbl0256.54028MR322838
  7. [7] D. Crisp, W. Moran, A. Pollington, P. Shiue, Substitution invariant cutting sequences. J. Théor. Nombres Bordeaux5 (1993), 123-137. Zbl0786.11041MR1251232
  8. [8] G. Didier, Codages de rotations et fractions continues. J. Number Theory71 (1998), 275-306. Zbl0921.11015MR1633821
  9. [9] G. Didier, Combinatoire des codages de rotations. Acta Arith.85 (1998), 157-177. Zbl0910.11007MR1630679
  10. [10] J.-M. Dumont, A. Thomas, Systèmes de numération et fonctions fractales relatifs aux substitutions. Theoret. Comput. Sci.65 (1989), 153-169. Zbl0679.10010MR1020484
  11. [11] F. Durand, A characterization of substitutive sequences using return words. Discrete Math.179 (1998), 89-101. Zbl0895.68087MR1489074
  12. [12] R.L. Graham, Covering the positive integers by disjoint sets of the form {[nα + β]: n = 1, 2, ... }. J. Combinatorial Theory Ser. A15 (1973), 354-358. Zbl0279.10042
  13. [13] P. Hubert, Suites équilibrées. Theoret. Comput. Sci.242 (2000), 91-108. Zbl0944.68149MR1769142
  14. [14] M. Keane, Interval exchange transformations. Math. Z.141 (1975), 25-31. Zbl0278.28010MR357739
  15. [15] H. Kesten, On a conjecture of Erdõs and Szüsz related to uniform distribution mod 1. Acta Arith.12 (1966/1967), 193-212. Zbl0144.28902MR209253
  16. [16] L.-M. Lopez, P. Narbel, DOL-systems and surface automorphisms. Mathematical foundations of computer science, 1998 (Brno), Lecture Notes in Comput. Sci. 1450, Springer, Berlin, 1998, pp. 522-532. Zbl0914.68113MR1684096
  17. [17] L.-M. Lopez, P. Narbel, Substitutions from Rauzy induction (extended abstract). Developments in language theory (Aachen, 1999), World Sci. Publishing, River Edge, NJ, 2000, pp. 200-209. Zbl1013.68150MR1881453
  18. [18] L.-M. Lopez, P. Narbel, Substitutions and interval exchange transformations of rotation class. Theoret. Comput. Sci.255 (2001), 323-344. Zbl0974.68160MR1819079
  19. [19] M. Lothaire, Algebraic combinatorics on words. Cambridge University Press, 2002. Zbl1001.68093MR1905123
  20. [20] M. Morse, G.A. Hedlund, Symbolic dynamics II. Sturmian trajectories. Amer. J. Math.62 (1940), 1-42. Zbl0022.34003MR745JFM66.0188.03
  21. [21] G. Rauzy, Sequences defined by iterated morphisms. Sequences (Naples/Positano, 1988), Springer, New York, 1990, pp. 275-286. Zbl0955.28501MR1040317
  22. [22] G. Rauzy, Échanges d'intervalles et transformations induites. Acta Arith.34 (1979), 315-328. Zbl0414.28018MR543205
  23. [23] G. Rote, Sequences with subword complexity 2n. J. Number Theory46 (1994), 196-213. Zbl0804.11023MR1269252
  24. [24] F. Schweiger, Multidimensional continued fractions. Oxford University Press, 2000. Zbl0981.11029MR2121855
  25. [25] V.T. Sós, On strong irregularities of the distribution of {nα} sequences. Studies in pure mathematics, Birkhäuser, Basel, 1983, pp. 685-700. Zbl0519.10047
  26. [26] W.A. Veech, Interval exchange transformations. J. Analyse Math.33 (1978), 222-272. Zbl0455.28006MR516048
  27. [27] W.A. Veech, Gauss measures for transformations on the space of interval exchange maps. Ann. of Math.115 (1982), 201-242. Zbl0486.28014MR644019
  28. [28] A. Zorich, Finite Gauss measure on the space of interval exchange transformations. Lyapunov exponents. Ann. Inst. Fourier (Grenoble) 46 (1996), 325-370. Zbl0853.28007MR1393518

Citations in EuDML Documents

top
  1. Louis-Sébastien Guimond, Zuzana Masáková, Edita Pelantová, Combinatorial properties of infinite words associated with cut-and-project sequences
  2. Ondřej Turek, Balances and Abelian Complexity of a Certain Class of Infinite Ternary Words
  3. Boris Adamczewski, Symbolic discrepancy and self-similar dynamics
  4. Petr Ambrož, Zuzana Masáková, Edita Pelantová, Morphisms fixing words associated with exchange of three intervals
  5. L'ubomíra Balková, Edita Pelantová, Štěpán Starosta, Sturmian jungle (or garden?) on multiliteral alphabets
  6. L'ubomíra Balková, Edita Pelantová, Štěpán Starosta, Sturmian jungle (or garden?) on multiliteral alphabets

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.