Codages de rotations et phénomènes d'autosimilarité
Journal de théorie des nombres de Bordeaux, Volume 14 (2002) no. 2, p. 351-386

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.

Nous étudions une classe de suites symboliques, les codages de rotations, intervenant dans des problèmes de répartition des suites (nα) 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.

@article{JTNB_2002__14_2_351_0,
     author = {Adamczewski, Boris},
     title = {Codages de rotations et ph\'enom\`enes d'autosimilarit\'e},
     journal = {Journal de th\'eorie des nombres de Bordeaux},
     publisher = {Universit\'e Bordeaux I},
     volume = {14},
     number = {2},
     year = {2002},
     pages = {351-386},
     zbl = {02184588},
     mrnumber = {2040682},
     language = {fr},
     url = {http://www.numdam.org/item/JTNB_2002__14_2_351_0}
}
Adamczewski, Boris. Codages de rotations et phénomènes d'autosimilarité. Journal de théorie des nombres de Bordeaux, Volume 14 (2002) no. 2, pp. 351-386. http://www.numdam.org/item/JTNB_2002__14_2_351_0/

[1] B. Adamczewski, Répartitions des suites (nα)n∈N et substitutions. Acta Arith., à paraître. | Zbl 1060.11043

[2] P. Arnoux, G. Rauzy, Représentation géométrique de suites de complexité 2n + 1. Bull. Soc. Math. France 119 (1991), 199-215. | Numdam | MR 1116845 | Zbl 0789.28011

[3] V. Berthé, R. Tijdeman, Balance properties of multi-dimensional words. Theoret. Comput. Sci. 273 (2002), 197-224. | MR 1872450 | Zbl 0997.68091

[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. | MR 1482988 | Zbl 0931.28013

[5] J. Cassaigne, S. Ferenczi, L.Q. Zamboni, Imbalances in Arnoux-Rauzy sequences. Ann. Inst. Fourier (Grenoble) 50 (2000), 1265-1276. | Numdam | MR 1799745 | Zbl 1004.37008

[6] E.M. Coven, G.A. Hedlund, Sequences with minimal block growth. Math. Systems Theory 7 (1973), 138-153. | MR 322838 | Zbl 0256.54028

[7] D. Crisp, W. Moran, A. Pollington, P. Shiue, Substitution invariant cutting sequences. J. Théor. Nombres Bordeaux 5 (1993), 123-137. | Numdam | MR 1251232 | Zbl 0786.11041

[8] G. Didier, Codages de rotations et fractions continues. J. Number Theory 71 (1998), 275-306. | MR 1633821 | Zbl 0921.11015

[9] G. Didier, Combinatoire des codages de rotations. Acta Arith. 85 (1998), 157-177. | MR 1630679 | Zbl 0910.11007

[10] J.-M. Dumont, A. Thomas, Systèmes de numération et fonctions fractales relatifs aux substitutions. Theoret. Comput. Sci. 65 (1989), 153-169. | MR 1020484 | Zbl 0679.10010

[11] F. Durand, A characterization of substitutive sequences using return words. Discrete Math. 179 (1998), 89-101. | MR 1489074 | Zbl 0895.68087

[12] R.L. Graham, Covering the positive integers by disjoint sets of the form {[nα + β]: n = 1, 2, ... }. J. Combinatorial Theory Ser. A 15 (1973), 354-358. | Zbl 0279.10042

[13] P. Hubert, Suites équilibrées. Theoret. Comput. Sci. 242 (2000), 91-108. | MR 1769142 | Zbl 0944.68149

[14] M. Keane, Interval exchange transformations. Math. Z. 141 (1975), 25-31. | MR 357739 | Zbl 0278.28010

[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. | MR 209253 | Zbl 0144.28902

[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. | MR 1684096 | Zbl 0914.68113

[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. | MR 1881453 | Zbl 1013.68150

[18] L.-M. Lopez, P. Narbel, Substitutions and interval exchange transformations of rotation class. Theoret. Comput. Sci. 255 (2001), 323-344. | MR 1819079 | Zbl 0974.68160

[19] M. Lothaire, Algebraic combinatorics on words. Cambridge University Press, 2002. | MR 1905123 | Zbl 1001.68093

[20] M. Morse, G.A. Hedlund, Symbolic dynamics II. Sturmian trajectories. Amer. J. Math. 62 (1940), 1-42. | JFM 66.0188.03 | MR 745 | Zbl 0022.34003

[21] G. Rauzy, Sequences defined by iterated morphisms. Sequences (Naples/Positano, 1988), Springer, New York, 1990, pp. 275-286. | MR 1040317 | Zbl 0955.28501

[22] G. Rauzy, Échanges d'intervalles et transformations induites. Acta Arith. 34 (1979), 315-328. | MR 543205 | Zbl 0414.28018

[23] G. Rote, Sequences with subword complexity 2n. J. Number Theory 46 (1994), 196-213. | MR 1269252 | Zbl 0804.11023

[24] F. Schweiger, Multidimensional continued fractions. Oxford University Press, 2000. | MR 2121855 | Zbl 0981.11029

[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. | Zbl 0519.10047

[26] W.A. Veech, Interval exchange transformations. J. Analyse Math. 33 (1978), 222-272. | MR 516048 | Zbl 0455.28006

[27] W.A. Veech, Gauss measures for transformations on the space of interval exchange maps. Ann. of Math. 115 (1982), 201-242. | MR 644019 | Zbl 0486.28014

[28] A. Zorich, Finite Gauss measure on the space of interval exchange transformations. Lyapunov exponents. Ann. Inst. Fourier (Grenoble) 46 (1996), 325-370. | Numdam | MR 1393518 | Zbl 0853.28007