On substitution invariant sturmian words : an application of Rauzy fractals

Berthé, Valérie; Ei, Hiromi; Ito, Shunji; Rao, Hui

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Volume 41 (2007) no. 3, pp. 329-349

sturmian words are infinite words that have exactly $n+1$ factors of length $n$ for every positive integer $n$. A sturmian word $s_{\alpha ,\rho }$ is also defined as a coding over a two-letter alphabet of the orbit of point $\rho$ under the action of the irrational rotation $R_{\alpha }:x\mapsto x+\alpha$ (mod 1). A substitution fixes a sturmian word if and only if it is invertible. The main object of the present paper is to investigate Rauzy fractals associated with two-letter invertible substitutions. As an application, we give an alternative geometric proof of Yasutomi’s characterization of all pairs $(\alpha ,\rho )$ such that $s_{\alpha ,\rho }$ is a fixed point of some non-trivial substitution.

Classification: 11J70, 37B10, 68R15
Keywords: sturmian words, Rauzy fractals, invertible substitutions, automorphisms of the free monoid, tilings

[1] S. Akiyama, and N. Gjini, Connectedness of number theoretic tilings. Arch. Math. (Basel) 82 (2004) 153-163. | Zbl

[2] C. Allauzen, Une caractérisation simple des nombres de Sturm. J. Théor. Nombres Bordeaux 10 (1998) 237-241. | Zbl | Numdam

[3] P. Arnoux, and S. Ito, Pisot substitutions and Rauzy fractals. Bull. Belg. Math. Soc. Simon Stevin 8 (2001) 181-207. | Zbl

[4] P. Baláži, S. Masáková, and E. Pelantová, Complete characterization of substitution invariant Sturmian sequences. Integers: electronic journal of combinatorial number theory 5 (2005) A14. | Zbl | MR

[5] M. Barge, and B. Diamond, Coincidence for substitutions of Pisot type, Bull. Soc. Math. France 130 (2002) 619-626. | Zbl | Numdam

[6] D. Bernardi, A. Guerziz, and M. Koskas, Sturmian Words: description and orbits. Preprint.

[7] J. Berstel, and P. Séébold, A remark on morphic Sturmian words. RAIRO-Theor. Inf. Appl. 28 (1994) 255-263. | Zbl | Numdam

[8] J. Berstel, and P. Séébold, Morphismes de Sturm. Bull. Belg. Math. Soc. Simon Stevin 1 (1994) 175-189. | Zbl

[9] V. Berthé, and L. Vuillon, Tilings and rotations on the torus: a two-dimensional generalization of Sturmian sequences. Discrete Math. 223 (2000) 27-53. | Zbl

[10] V. Berthé, C. Holton, and L.Q. Zamboni, Initial powers of Sturmian words. Acta Arith. 122 (2006) 315-347. | Zbl

[11] T.C. Brown, Descriptions of the characteristic sequence of an irrational. Canad. Math. Bull. 36 (1993) 15-21. | Zbl

[12] V. Canterini, Connectedness of geometric representation of substitutions of Pisot type. Bull. Belg. Math. Soc. Simon Stevin 10 (2003) 77-89. | Zbl

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

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

[15] H. Ei, and S. Ito, Decomposition theorem on invertible substitutions. Osaka J. Math. 35 (1998) 821-834. | Zbl

[16] I. Fagnot, A little more about morphic Sturmian words. RAIRO-Theor. Inf. Appl. 40 (2006), 511-518. | Zbl | Numdam

[17] K. Falconer, Techniques in Fractal Geometry. Oxford University Press, 5th edition (1979).

[18] S. Ito, and H. Rao, Purely periodic $\beta$-expansions with Pisot unit base. Proc. Amer. Math. Soc. 133 (2005) 953-964. | Zbl

[19] S. Ito, and H. Rao, Atomic surfaces, tilings and coincidence I. Irreducible case. Israel J. Math. 153 (2006) 129-156.

[20] S. Ito, and Y. Sano, On periodic $\beta$-expansions of Pisot numbers and Rauzy fractals. Osaka J. Math. 38 (2001) 349-368. | Zbl

[21] S. Ito, and S. Yasutomi, On continued fractions, substitutions and characteristic sequences $[nx+y]-\left[\right(n-1)x+y]$. Japan J. Math. 16 (1990) 287-306. | Zbl

[22] T. Komatsu, and A.J. Van Der Poorten, Substitution invariant Beatty sequences. Japan J. Math., New Ser. 22 (1996) 349-354. | Zbl

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

[24] F. Mignosi, and P. Séébold, Morphismes sturmiens et règles de Rauzy. J. Théor. Nombres Bordeaux 5 (1993) 221-233. | Zbl | Numdam

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

[26] B. Parvaix, Propriétés d'invariance des mots sturmiens. J. Théor. Nombres Bordeaux 9 (1997) 351-369. | Zbl | Numdam

[27] B. Parvaix, Substitution invariant Sturmian bisequences. J. Théor. Nombres Bordeaux 11 (1999) 201-210. | Zbl | Numdam

[28] N. Pytheas Fogg, Substitutions in Arithmetics, Dynamics and Combinatorics, V. Berthé, S. Ferenczi, C.Mauduit, A. Siegel Eds., Springer Verlag. Lect. Notes Math. 1794 (2002). | Zbl | MR

[29] M. Queffélec, Substitution Dynamical Systems. Spectral Analysis, Springer-Verlag. Lect. Notes Math. 1294 (1987). | Zbl | MR

[30] G. Rauzy, Nombres algebriques et substitutions, Bull. Soc. Math. France 110 (1982) 147-178. | Zbl | Numdam

[31] P. Séébold, On the conjugation of standard morphisms. Theoret. Comput. Sci. 195 (1998) 91-109. | Zbl

[32] V. Sirvent, and Y. Wang, Geometry of Rauzy fractals. Pacific J. Math. 206 (2002) 465-485. | Zbl

[33] B. Tan, and Z.-Y. Wen, Invertible substitutions and Sturmian sequences. European J. Combinatorics 24 (2003) 983-1002. | Zbl

[34] Z.-X. Wen, and Wen Z.-Y., Local isomorphisms of invertible substitutions. C. R. Acad. Sci. Paris Sér. I 318 (1994) 299-304. | Zbl

[35] S.-I. Yasutomi, On Sturmian sequences which are invariant under some substitutions, in Number theory and its applications (Kyoto, 1997). Kluwer Acad. Publ., Dordrecht (1999) 347-373. | Zbl