Hostname: page-component-586b7cd67f-dlnhk Total loading time: 0 Render date: 2024-11-24T14:23:34.413Z Has data issue: false hasContentIssue false
  • English
  • Français

Squares and cubes in Sturmian sequences

Published online by Cambridge University Press:  06 March 2009

Artūras Dubickas
Artūras Dubickas*
Affiliation:
Department of Mathematics and Informatics, Vilnius University, Naugarduko 24, Vilnius 03225, Lithuania; [email protected]
Get access

Abstract

We prove that every Sturmian word ω has infinitely many prefixes of the form UnVn3, where |Un| < 2.855|Vn| and limn→∞|Vn| = ∞. In passing, we give a very simple proof of the known fact that every Sturmian word begins in arbitrarily long squares.

Keywords

Sturmian wordblock-complexitystammering word.
Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 43 , Issue 3 , July 2009 , pp. 615 - 624
Copyright
© EDP Sciences, 2009

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Adamczewski, B. and Bugeaud, Y., On the complexity of algebraic numbers I. Expansion in integer bases. Ann. Math. 165 (2007) 547–565. CrossRef
Adamczewski, B. and Bugeaud, Y., Dynamics for β-shifts and Diophantine approximation. Ergod. Theory Dyn. Syst. 27 (2007) 1695–1711. CrossRef
Adamczewski, B. and Rampersad, N., On patterns occuring in binary algebraic numbers. Proc. Amer. Math. Soc. 136 (2008) 3105–3109. CrossRef
Allouche, J.-P., Davison, J.P., Queffélec, M. and Zamboni, L.Q., Transcendence of Sturmian or morphic continued fractions. J. Number Theory 91 (2001) 39–66. CrossRef
J.-P. Allouche and J. Shallit, Automatic sequences, Theory, applications, generalizations. CUP, Cambridge (2003).
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.
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.
Berthé, V., Holton, C. and Zamboni, L.Q., Initial powers of Sturmian sequences. Acta Arith. 122 (2006) 315–347. CrossRef
Cassaigne, J., On extremal properties of the Fibonacci word. RAIRO-Theor. Inf. Appl. 42 (2008) 701–715. CrossRef
Coven, E. and Hedlund, G., Sequences with minimal block growth. Math. Syst. Theor. 7 (1973) 138–153. CrossRef
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.
De Luca, A., Sturmian words: structure, combinatorics and their arithmetics. Theoret. Comput. Sci. 183 (1997) 45–82. CrossRef
Damanik, D., Killip, R. and Lenz, D., Uniform spectral properties of one-dimensional quasicrystals, III. α-continuity. Commun. Math. Phys. 212 (2000) 191–204. CrossRef
A. Dubickas, Powers of a rational number modulo 1 cannot lie in a small interval (to appear).
Ferenczi, S. and Mauduit, C., Transcendence of numbers with low complexity expansion. J. Number Theory 67 (1997) 146–161. CrossRef
Fraenkel, A.S., Mushkin, M. and Tassa, U., Determination of [nθ] by its sequence of differences. Canad. Math. Bull. 21 (1978) 441–446. CrossRef
Ito, S. and Yasutomi, S., On continued fractions, substitutions and characteristic sequences. Jpn J. Math. 16 (1990) 287–306.
Justin, J. and Vuillon, L., Return words in Sturmian and episturmian words. RAIRO-Theor. Inf. Appl. 34 (2000) 343–356. CrossRef
Krieger, D. and Shallit, J., Every real number greater than 1 is a critical exponent. Theoret. Comput. Sci. 381 (2007) 177–182. CrossRef
M. Lothaire, Algebraic combinatorics on words, Encyclopedia of Mathematics and Its Applications, Vol. 90. CUP, Cambridge (2002).
Mahler, K., An unsolved problem on the powers of 3/2. J. Austral. Math. Soc. 8 (1968) 313–321. CrossRef
Mignosi, F., On the number of factors of Sturmian words. Theoret. Comput. Sci. 82 (1991) 71–84. CrossRef
Morse, M. and Hedlund, G.A., Symbolic dynamics II: Sturmian sequences. Amer. J. Math. 62 (1940) 1–42. CrossRef
N. Pytheas Fogg, Substitutions in dynamics, arithmetics and combinatorics. Lect. Notes Math. 1794 (2002).
Stolarsky, K.B., Beatty sequences, continued fractions, and certain shift operators. Canad. Math. Bull. 19 (1976) 473–482. CrossRef
Vandeth, D., Sturmian words and words with a critical exponent. Theoret. Comput. Sci. 242 (2000) 283–300. CrossRef
Vuillon, L., A characterization of Sturmian words by return words. Eur. J. Combin. 22 (2001) 263–275. CrossRef