$*$-sturmian words and complexity

Nakashima, Izumi; Tamura, Jun-Ichi; Yasutomi, Shin-Ichi

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

Nous définissons des notions analogues à la complexité $p\left(n\right)$ et aux mots Sturmiens qui sont appelées respectivement $*$-complexité $p_{*}\left(n\right)$ et mots $*$-Sturmiens. Nous démontrons que la classe des mots $*$-Sturmiens coïncide avec la classe des mots satisfaisant à $p_{*}\left(n\right)\le n+1$ et nous déterminons la structure des mots $*$-Sturmiens. Pour une classe de mots satisfaisant à $p_{*}\left(n\right)=n+1$, nous donnons une formule générale et une borne supérieure pour $p(n$). En utilisant cette formule générale, nous donnons des formules explicites pour $p\left(n\right)$ pour certains mots appartenant à cette classe. En général, $p\left(n\right)$ peut prendre des valeurs élevées, à savoir $p\left(n\right)\ge 2^{n^{1-ϵ}}$ pour certains mots $*$-Sturmiens. Cependant l’entropie topologique de n’importe quel mot $*$-Sturmien est nulle.

We give analogs of the complexity $p\left(n\right)$ and of Sturmian words which are called respectively the $*$-complexity $p_{*}\left(n\right)$ and $*$-Sturmian words. We show that the class of $*$-Sturmian words coincides with the class of words satisfying $p_{*}\left(n\right)\le n+1$, and we determine the structure of $*$-Sturmian words. For a class of words satisfying $p_{*}\left(n\right)=n+1$, we give a general formula and an upper bound for $p\left(n\right)$. Using this general formula, we give explicit formulae for $p\left(n\right)$ for some words belonging to this class. In general, $p\left(n\right)$ can take large values, namely, $p\left(n\right)\ge 2^{n^{1-ϵ}}$ holds for some $*$-Sturmian words; however the topological entropy of any $*$-Sturmian word is zero.

[1] P. Arnoux, C. Mauduit, I. Shiokawa, J.-I. Tamura, Complexity of sequences defined by billiards in the cube. Bull. Soc. Math. France 122 (1994), 1-12. | Numdam | MR | 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] Y. Baryshnikov, Complexity of trajectories in rectangular billiards. Comm. Math. Phys. 174 (1995), 43-56. | MR | Zbl

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

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

[6] S. Ferenczi, Les transformations de Chacon: combinatoire, structure géométrique, lien avec les systèmes de complexité 2n + 1. Bull. Soc. Math. France 123 (1995), 271-292. | Numdam | MR | Zbl

[7] S. Ito, S.-I. Yasutomi, On continued fraction, substitutions and characteristic sequences [nx + y] - [(n - 1)x + y]. Japan. J. Math. 16 (1990), 287-306. | MR | Zbl

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

[9] M. Morse, G.A. Hedlund, Symbolic dynamics. Amer. J. Math. 60 (1938), 815-866. | JFM | MR | Zbl

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

[11] I. Nakashima, J.-I. Tamura, S.-I. Yasutomi, Modified complexity and *-Sturmian word. Proc. Japan Acad. (Ser. A) Math. Sci. 75 (1999), 26-28. | MR | Zbl

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

[13] S.-I. Yasutomi, The continued fraction expansion of α with μ(α) = 3. Acta Arith. 84 (1998), 337-374. | Zbl