Squares and cubes in sturmian sequences

Dubickas, Artūras

doi:10.1051/ita/2009005

Dubickas, Artūras

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 43 (2009) no. 3, pp. 615-624.

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.

MR Zbl

DOI : 10.1051/ita/2009005

Classification : 68R15
Mots clés : sturmian word, block-complexity, stammering word

@article{ITA_2009__43_3_615_0,
     author = {Dubickas, Art\={u}ras},
     title = {Squares and cubes in sturmian sequences},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {615--624},
     publisher = {EDP-Sciences},
     volume = {43},
     number = {3},
     year = {2009},
     doi = {10.1051/ita/2009005},
     mrnumber = {2541133},
     zbl = {1176.68150},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ita/2009005/}
}

TY  - JOUR
AU  - Dubickas, Artūras
TI  - Squares and cubes in sturmian sequences
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2009
SP  - 615
EP  - 624
VL  - 43
IS  - 3
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita/2009005/
DO  - 10.1051/ita/2009005
LA  - en
ID  - ITA_2009__43_3_615_0
ER  -

%0 Journal Article
%A Dubickas, Artūras
%T Squares and cubes in sturmian sequences
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2009
%P 615-624
%V 43
%N 3
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ita/2009005/
%R 10.1051/ita/2009005
%G en
%F 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) no. 3, pp. 615-624. doi : 10.1051/ita/2009005. http://www.numdam.org/articles/10.1051/ita/2009005/

Bibliographie
Cité par

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

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

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

[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 | Zbl

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

[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 | Zbl

[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 | Zbl

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

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

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

[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

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

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

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

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

[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 | Zbl

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

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

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

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

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

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

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

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

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

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

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

Cité par Sources :