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

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

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

  • Volume: 15, Issue: 3, page 697-725
  • ISSN: 1246-7405

Abstract

top
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 2 n + 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 2 n + 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.

How to cite

top

Guimond, Louis-Sébastien, Masáková, Zuzana, and Pelantová, Edita. "Combinatorial properties of infinite words associated with cut-and-project sequences." Journal de théorie des nombres de Bordeaux 15.3 (2003): 697-725. <http://eudml.org/doc/249105>.

@article{Guimond2003,
abstract = {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.},
author = {Guimond, Louis-Sébastien, Masáková, Zuzana, Pelantová, Edita},
journal = {Journal de théorie des nombres de Bordeaux},
keywords = {cut-and-project sequences; Sturmian sequences; three-interval exchanges},
language = {eng},
number = {3},
pages = {697-725},
publisher = {Université Bordeaux I},
title = {Combinatorial properties of infinite words associated with cut-and-project sequences},
url = {http://eudml.org/doc/249105},
volume = {15},
year = {2003},
}

TY - JOUR
AU - Guimond, Louis-Sébastien
AU - Masáková, Zuzana
AU - Pelantová, Edita
TI - Combinatorial properties of infinite words associated with cut-and-project sequences
JO - Journal de théorie des nombres de Bordeaux
PY - 2003
PB - Université Bordeaux I
VL - 15
IS - 3
SP - 697
EP - 725
AB - 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.
LA - eng
KW - cut-and-project sequences; Sturmian sequences; three-interval exchanges
UR - http://eudml.org/doc/249105
ER -

References

top
  1. [1] B. Adamczewski, Codages de rotations et phénomènes d'autosimilarité: J. Théor. Nombres Bordeaux14 (2002), 351-386. Zbl1113.37003MR2040682
  2. [2] P. Alessandri, V. Berthé, Autour du théorème des trois longueurs. Enseign. Math.44 (1998), 103-132. Zbl0997.11051MR1643286
  3. [3] J.P. Allouche, Sur la complexité des suites infinies. Bull. Belg. Math. Soc.1 (1994), 133-143. Zbl0803.68094MR1318964
  4. [4] P. Arnoux, G. Rauzy, Représentation géométrique de suites de complexité 2n+1. Bull. Soc. Math. France119 (1991), 199-215. Zbl0789.28011MR1116845
  5. [5] P. Balái, Z. Masáková, E. Pelantová, Cut-and-project sequences invariant under morphism. In preparation, Czech Technical University, (2003) 
  6. [6] P. Balái, E. Pelantová, Selfsimilar Cut-and-project Sequences. To be published in Proceedings of Group 24, Paris2002. 
  7. [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. Zbl0976.11014MR1776754
  8. [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. [9] E.M. Coven, G.A. Hedlund, Sequences with minimal block growth. Math. Systems Theory7 (1973), 138-153. Zbl0256.54028MR322838
  10. [10] S. Ferenczi, Complexity of Sequences and Dynamical Systems. Discrete Math.206 (1999), 663-682. Zbl0858.68051MR1665394
  11. [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 Zbl1029.11036MR1849209
  12. [12] R.L. Graham, D.E. Knuth, O. Patashnik, Concrete mathematics. A foundation for computer science. Second edition, Addison Wesley, Reading MA, 1994. Zbl0836.00001MR1397498
  13. [13] M. Langevin, Stimulateur cardiaque et suites de Farey. Period. Math. Hungar.23 (1991), 75-86. Zbl0763.11007MR1141354
  14. [14] M. Lothaire, Algebraic Combinatorics on Words. Chapter 2: Sturmian words, by J. Berstel, P. Séébold, Cambridge University Press, (2002), 45-110. Zbl1001.68093MR1905123
  15. [15] W.F. Lunnon, P.A.B. Pleasants, Characterization of two-distance sequences. J. Austral. Math. Soc. (Series A) 53 (1992), 198-218. Zbl0759.11005MR1175712
  16. [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. Zbl0978.11006MR1801473
  17. [17] M. Morse, G.A. Hedlund, Symbolic dynamics II: Sturmian trajectories. Amer. J. Math.62 (1940), 1-42. Zbl0022.34003MR745JFM66.0188.03
  18. [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. Zbl0880.43008MR1460032
  19. [19] R.V. Moody, J. Patera, Densities, minimal distances, and coverings of quasicrystals. Comm. Math. Phys.195 (1998), 613-626. Zbl0929.52017MR1641011
  20. [20] Jan Patera, http://kmlinux.fjfi.cvut.cz/-patera/makerule.cgi. 
  21. [21] N.B. Slatter, Gaps and steps for the sequence nθ mod 1. Proc. Camb. Phil. Soc.63 (1967), 1115-1123. Zbl0178.04703
  22. [22] H. Weyl, Über die Gleichungverteilung von Zahlen mod. Eins. Math. Ann.77 (1916), 313-352. Zbl46.0278.06MR1511862JFM46.0278.06

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.