Richomme asked the following question: what is the infimum of the real numbers α > 2 such that there exists an infinite word that avoids α-powers but contains arbitrarily large squares beginning at every position? We resolve this question in the case of a binary alphabet by showing that the answer is α = 7/3.
@article{ITA_2010__44_1_113_0,
author = {Currie, James and Rampersad, Narad},
title = {Infinite words containing squares at every position},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
volume = {44},
year = {2010},
pages = {113-124},
doi = {10.1051/ita/2010007},
mrnumber = {2604937},
zbl = {1184.68370},
language = {en},
url = {http://dml.mathdoc.fr/item/ITA_2010__44_1_113_0}
}
Currie, James; Rampersad, Narad. Infinite words containing squares at every position. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 44 (2010) pp. 113-124. doi : 10.1051/ita/2010007. http://gdmltest.u-ga.fr/item/ITA_2010__44_1_113_0/
[1] , , and , Transcendence of Sturmian or morphic continued fractions. J. Number Theory 91 (2001) 39-66. | Zbl 0998.11036
[2] , Axel Thue's work on repetitions in words. In Séries formelles et combinatoire algébrique, edited by P. Leroux and C. Reutenauer. Publications du LaCIM, UQAM (1992) 65-80.
[3] , A rewriting of Fife's theorem about overlap-free words. In Results and Trends in Theoretical Computer Science, edited by J. Karhumäki, H. Maurer, and G. Rozenberg. Lect. Notes Comput. Sci. 812 (1994) 19-29.
[4] , Enumeration of factors in the Thue-Morse word. Discrete Appl. Math. 24 (1989) 83-96. | Zbl 0683.20045
[5] , , and , Squares and overlaps in the Thue-Morse sequence and some variants. RAIRO-Theor. Inf. Appl. 40 (2006) 473-484. | Numdam | Zbl 1110.68117
[6] , and , Binary words containing infinitely many overlaps. Electron. J. Combin. 13 (2006) #R82. | Zbl 1108.68094
[7] , Binary sequences which contain no BBb. Trans. Amer. Math. Soc. 261 (1980) 115-136. | Zbl 0464.05018
[8] , A note on the number of squares in a word. Theoret. Comput. Sci. 380 (2007) 373-376. | Zbl 1119.68141
[9] and , Polynomial versus exponential growth in repetition-free binary words. J. Combin. Theory Ser. A 104 (2004) 335-347. | Zbl 1065.68080
[10] , A linear time algorithm to decide whether a binary word contains an overlap. RAIRO-Theor. Inf. Appl. 22 (1988) 135-145. | Numdam | Zbl 0645.68087
[11] , Enumeration of irreducible binary words. Discrete Appl. Math. 20 (1988) 221-232. | Zbl 0673.68046
[12] , and , On repetition-free binary words of minimal density, WORDS (Rouen, 1997). Theoret. Comput. Sci. 218 (1999) 161-175. | Zbl 0916.68118
[13] , On critical exponents in fixed points of non-erasing morphisms. Theoret. Comput. Sci. 376 (2007) 70-88. | Zbl 1111.68058
[14] and , Repetitions in the Fibonacci infinite word. RAIRO-Theor. Inf. Appl. 26 (1992) 199-204. | Numdam | Zbl 0761.68078
[15] , The Morse sequence and iterated morphisms. Inform. Process. Lett. 12 (1981) 68-70. | Zbl 0464.68075
[16] and , Overlap free words on two symbols, in Automata on Infinite Words, edited by M. Nivat and D. Perrin. Lect. Notes. Comput. Sci. 192 (1984) 198-206. | Zbl 0572.20038
[17] , Private communication (2005).
[18] , Everywhere α-repetitive sequences and Sturmian words, in Proc. CSR 2007. Lect. Notes. Comput. Sci. 4649 (2007) 362-372. | Zbl 1188.68218
[19] and , Chains and fixing blocks in irreducible sequences. Discrete Math. 54 (1985) 93-99. | Zbl 0561.05015
[20] , Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen. Kra. Vidensk. Selsk. Skrifter. I. Math. Nat. Kl. 1 (1912) 1-67. | JFM 44.0462.01