Squares and cubes in sturmian sequences

Dubickas, Artūras

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 43 (2009), p. 615-624 / Harvested from Numdam

Access to full text
Full (PDF)
Full (DJVU)

Résumé

We prove that every sturmian word $ω$ has infinitely many prefixes of the form $U_{n} V_{n}^{3},$ where $| U_{n} | < 2.855 | V_{n} |$ and ${lim}_{n \to \infty} | V_{n} | = \infty .$ In passing, we give a very simple proof of the known fact that every sturmian word begins in arbitrarily long squares.

Publié le : 2009-01-01

MR 2541133 | Zbl 1176.68150

DOI : https://doi.org/10.1051/ita/2009005
Classification: 68R15

@article{ITA_2009__43_3_615_0,
     author = {Dubickas, Art\=uras},
     title = {Squares and cubes in sturmian sequences},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {43},
     year = {2009},
     pages = {615-624},
     doi = {10.1051/ita/2009005},
     mrnumber = {2541133},
     zbl = {1176.68150},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_2009__43_3_615_0}
}

Dubickas, Artūras. Squares and cubes in sturmian sequences. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 43 (2009) pp. 615-624. doi : 10.1051/ita/2009005. http://gdmltest.u-ga.fr/item/ITA_2009__43_3_615_0/

Bibliographie

[1] B. Adamczewski and Y. Bugeaud, On the complexity of algebraic numbers I. Expansion in integer bases. Ann. Math. 165 (2007) 547-565. | MR 2299740 | Zbl pre05180742

[2] B. Adamczewski and Y. Bugeaud, Dynamics for $β$ -shifts and Diophantine approximation. Ergod. Theory Dyn. Syst. 27 (2007) 1695-1711. | MR 2371591 | Zbl 1140.11035

[3] B. Adamczewski and N. Rampersad, On patterns occuring in binary algebraic numbers. Proc. Amer. Math. Soc. 136 (2008) 3105-3109. | MR 2407073 | Zbl 1151.11036

[4] J.-P. Allouche, J.P. Davison, M. Queffélec and L.Q. Zamboni, Transcendence of Sturmian or morphic continued fractions. J. Number Theory 91 (2001) 39-66. | MR 1869317 | Zbl 0998.11036

[5] J.-P. Allouche and J. Shallit, Automatic sequences, Theory, applications, generalizations. CUP, Cambridge (2003). | MR 1997038 | Zbl 1086.11015

[6] J. Berstel, On the index of Sturmian words. In Jewels are Forever, Contributions on theoretical computer science in honor of Arto Salomaa, J. Karhumäki et al., eds. Springer, Berlin (1999) 287-294. | MR 1719097 | Zbl 0982.11010

[7] J. Berstel and J. Karhumäki, Combinatorics on words - a tutorial, in Current trends in theoretical computer science, The challenge of the new century, Vol. 2, Formal models and semantics, G. Paun, G. Rozenberg, A. Salomaa, eds. World Scientific, River Edge, NJ (2004) 415-475. | MR 1965433 | Zbl 1065.68078

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

[9] J. Cassaigne, On extremal properties of the Fibonacci word. RAIRO-Theor. Inf. Appl. 42 (2008) 701-715. | Numdam | MR 2458702 | Zbl 1155.68062

[10] E. Coven and G. Hedlund, Sequences with minimal block growth. Math. Syst. Theor. 7 (1973) 138-153. | MR 322838 | Zbl 0256.54028

[11] J.D. Currie and N. Rampersad, For each $α > 2$ there is an infinite binary word with critical exponent $α$ , Electron. J. Combin. 15 (2008) 5 p. | MR 2438590 | Zbl pre05540896

[12] A. De Luca, Sturmian words: structure, combinatorics and their arithmetics. Theoret. Comput. Sci. 183 (1997) 45-82. | MR 1468450 | Zbl 0911.68098

[13] D. Damanik, R. Killip and D. Lenz, Uniform spectral properties of one-dimensional quasicrystals, III 212 (2000) 191-204. | MR 1764367 | Zbl 1045.81024

[14] A. Dubickas, Powers of a rational number modulo $1$ cannot lie in a small interval (to appear). | MR 2496462 | Zbl pre05538708

[15] S. Ferenczi and C. Mauduit, Transcendence of numbers with low complexity expansion. J. Number Theory 67 (1997) 146-161. | MR 1486494 | Zbl 0895.11029

[16] A.S. Fraenkel, M. Mushkin and U. Tassa, Determination of $⌊ n θ ⌋$ by its sequence of differences. Canad. Math. Bull. 21 (1978) 441-446. | MR 523586 | Zbl 0401.10018

[17] S. Ito and S. Yasutomi, On continued fractions, substitutions and characteristic sequences. Jpn J. Math. 16 (1990) 287-306. | MR 1091163 | Zbl 0721.11009

[18] J. Justin and L. Vuillon, Return words in Sturmian and episturmian words. RAIRO-Theor. Inf. Appl. 34 (2000) 343-356. | Numdam | MR 1829231 | Zbl 0987.68055

[19] D. Krieger and J. Shallit, Every real number greater than 1 is a critical exponent. Theoret. Comput. Sci. 381 (2007) 177-182. | MR 2347401 | Zbl pre05186613

[20] M. Lothaire, Algebraic combinatorics on words, Encyclopedia of Mathematics and Its Applications, Vol. 90. CUP, Cambridge (2002). | MR 1905123 | Zbl 1001.68093

[21] K. Mahler, An unsolved problem on the powers of $3 / 2$ . J. Austral. Math. Soc. 8 (1968) 313-321. | MR 227109 | Zbl 0155.09501

[22] F. Mignosi, On the number of factors of Sturmian words. Theoret. Comput. Sci. 82 (1991) 71-84. | MR 1112109 | Zbl 0728.68093

[23] M. Morse and G.A. Hedlund, Symbolic dynamics II: Sturmian sequences. Amer. J. Math. 62 (1940) 1-42. | JFM 66.0188.03 | MR 745

[24] N. Pytheas Fogg, Substitutions in dynamics, arithmetics and combinatorics. Lect. Notes Math. 1794 (2002). | MR 1970385 | Zbl 1014.11015

[25] K.B. Stolarsky, Beatty sequences, continued fractions, and certain shift operators. Canad. Math. Bull. 19 (1976) 473-482. | MR 444558 | Zbl 0359.10028

[26] D. Vandeth, Sturmian words and words with a critical exponent. Theoret. Comput. Sci. 242 (2000) 283-300. | MR 1769782 | Zbl 0944.68148

[27] L. Vuillon, A characterization of Sturmian words by return words. Eur. J. Combin. 22 (2001) 263-275. | MR 1808196 | Zbl 0968.68124