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

Adamczewski, Boris

Journal de théorie des nombres de Bordeaux, Tome 14 (2002) no. 2, pp. 351-386.

Nous étudions une classe de suites symboliques, les codages de rotations, intervenant dans des problèmes de répartition des suites ${\left(n\alpha \right)}_{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.

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 ${\left(n\alpha \right)}_{n\in \mathbb{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.

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

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

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

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

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

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

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

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

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

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

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

[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

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

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

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

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

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

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

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

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

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

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

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

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

[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

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

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

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