Combinatorial properties of infinite words associated with cut-and-project sequences

Guimond, Louis-Sébastien; Masáková, Zuzana; Pelantová, Edita

Journal de théorie des nombres de Bordeaux, Tome 15 (2003) no. 3, pp. 697-725.

Le but de cet article est d’étudier certaines propriétés combinatoires des suites binaires et ternaires obtenues par «coupe et projection». Nous considérons ici le processus de coupe et projection en dimension deux où les sous-espaces de projection sont en position générale. Nous prouvons que les distances entre deux termes adjacents dans une suite ainsi obtenue prennent toujours soit deux soit trois valeurs. Une suite obtenue par coupe et projection détermine ainsi de manière naturelle une suite symbolique (mot infini) sur deux ou trois lettres. En fait ces suites peuvent aussi être obtenues comme codages d’échanges de deux ou trois intervalles. Du point de vue de la complexité, la construction par coupe et projection donne des mots de complexité $n+1,n+$ constante et $2n+1$. Les mots binaires ont une complexité égale à $n+1$ et sont donc sturmiens. Les mots ternaires ont une complexité égale à $n+$ constante ou $2n+1$. Une coupe et projection a trois paramètres dont deux spécifient les sous-espaces de projection, le troisième déterminant la bande de coupe. Nous classifions les triplets qui correspondent à des mots infinis combinatoirement équivalents.

The aim of this article is to study certain combinatorial properties of infinite binary and ternary words associated to cut-and-project sequences. We consider here the cut-and-project scheme in two dimensions with general orientation of the projecting subspaces. We prove that a cut-and-project sequence arising in such a setting has always either two or three types of distances between adjacent points. A cut-and-project sequence thus determines in a natural way a symbolic sequence (infinite word) in two or three letters. In fact, these sequences can be constructed also by a coding of a $2$- or $3$-interval exchange transformation. According to the complexity the cut-and-project construction includes words with complexity $n+1,n+$ const. and $2n+1$. The words on two letter alphabet have complexity $n+1$ and thus are Sturmian. The ternary words associated to the cut-and-project sequences have complexity $n+$ const. or $2n+1$. A cut-and-project scheme has three parameters, two of them specifying the projection subspaces, the third one determining the cutting strip. We classify the triples that correspond to combinatorially equivalent infinite words.

[1] B. Adamczewski, Codages de rotations et phénomènes d'autosimilarité: J. Théor. Nombres Bordeaux 14 (2002), 351-386. | Numdam | MR | Zbl

[2] P. Alessandri, V. Berthé, Autour du théorème des trois longueurs. Enseign. Math. 44 (1998), 103-132. | MR | Zbl

[3] J.P. Allouche, Sur la complexité des suites infinies. Bull. Belg. Math. Soc. 1 (1994), 133-143. | MR | Zbl

[4] 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

[5] P. Balái, Z. Masáková, E. Pelantová, Cut-and-project sequences invariant under morphism. In preparation, Czech Technical University, (2003)

[6] P. Balái, E. Pelantová, Selfsimilar Cut-and-project Sequences. To be published in Proceedings of Group 24, Paris 2002.

[7] V. Berthé, Sequences of low complexity: automatic and sturmian sequences. Topics in Symbolic Dynamics and Applications, Eds. F. Blanchard, A. Maass, A. Nogueira, Cambridge Univ. Press (2000), 1-34. | MR | Zbl

[8] J. Cassaigne, Sequences with grouped factors. Developments in Language Theory III, Thessaloniki, Aristotle University of Thessaloniky (1998), 211-222. Available at ftp://iml.univ-mrs.fr/pub/cassaigne/publis/grouped.ps.gz.

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

[10] S. Ferenczi, Complexity of Sequences and Dynamical Systems. Discrete Math. 206 (1999), 663-682. | MR

[11] S. Ferenczi, C. Holton, L.Q. Zamboni, Structure of three interval exchange transformations I: An arithmetic study. Ann. Inst. Fourier (Grenoble) 51 (2001), 861-901. http://citeseer.nj.nec.com/article/ferenczi01structure.html | Numdam | MR | Zbl

[12] R.L. Graham, D.E. Knuth, O. Patashnik, Concrete mathematics. A foundation for computer science. Second edition, Addison Wesley, Reading MA, 1994. | MR

[13] M. Langevin, Stimulateur cardiaque et suites de Farey. Period. Math. Hungar. 23 (1991), 75-86. | MR | Zbl

[14] M. Lothaire, Algebraic Combinatorics on Words. Chapter 2: Sturmian words, by J. Berstel, P. Séébold, Cambridge University Press, (2002), 45-110. | MR | Zbl

[15] W.F. Lunnon, P.A.B. Pleasants, Characterization of two-distance sequences. J. Austral. Math. Soc. (Series A) 53 (1992), 198-218. | MR | Zbl

[16] Z. Masáková, J. Patera, E. Pelantová, Substitution rules for aperiodic sequences of the cut-and-project type. J. Phys. A: Math. Gen. 33 (2000), 8867-8886. | MR | Zbl

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

[18] R.V. Moody, Meyer sets and their duals, in Mathematics of Long Range Aperiodic Order. Proc. NATO ASI, Waterloo, 1996, ed. R. V. Moody, Kluwer (1996), 403-441. | MR | Zbl

[19] R.V. Moody, J. Patera, Densities, minimal distances, and coverings of quasicrystals. Comm. Math. Phys. 195 (1998), 613-626. | MR | Zbl

[20] Jan Patera, http://kmlinux.fjfi.cvut.cz/-patera/makerule.cgi.

[21] N.B. Slatter, Gaps and steps for the sequence nθ mod 1. Proc. Camb. Phil. Soc. 63 (1967), 1115-1123. | Zbl

[22] H. Weyl, Über die Gleichungverteilung von Zahlen mod. Eins. Math. Ann. 77 (1916), 313-352. | JFM | MR