A square is the concatenation of a nonempty word with itself. A word has period p if its letters at distance p match. The exponent of a nonempty word is the quotient of its length over its smallest period. In this article we give a proof of the fact that there exists an infinite binary word which contains finitely many squares and simultaneously avoids words of exponent larger than 7/3. Our infinite word contains 12 squares, which is the smallest possible number of squares to get the property, and 2 factors of exponent 7/3. These are the only factors of exponent larger than 2. The value 7/3 introduces what we call the finite-repetition threshold of the binary alphabet. We conjecture it is 7/4 for the ternary alphabet, like its repetitive threshold.
@article{ITA_2012__46_1_17_0,
author = {Badkobeh, Golnaz and Crochemore, Maxime},
title = {Fewest repetitions in infinite binary words},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
volume = {46},
year = {2012},
pages = {17-31},
doi = {10.1051/ita/2011109},
mrnumber = {2904958},
zbl = {1247.68201},
language = {en},
url = {http://dml.mathdoc.fr/item/ITA_2012__46_1_17_0}
}
Badkobeh, Golnaz; Crochemore, Maxime. Fewest repetitions in infinite binary words. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 46 (2012) pp. 17-31. doi : 10.1051/ita/2011109. http://gdmltest.u-ga.fr/item/ITA_2012__46_1_17_0/
[1] and , An infinite binary word containing only three distinct squares (2010) Submitted.
[2] and , A proof of Dejean's conjecture. Math. Comput. 80 (2011) 1063-1070. | Zbl 1215.68192
[3] , Sur un théorème de Thue. J. Comb. Theory, Ser. A 13 (1972) 90-99. | MR 300959 | Zbl 0245.20052
[4] and , How many squares must a binary sequence contain? Electr. J. Comb. 2 (1995). | MR 1309124 | Zbl 0816.11007
[5] and , Binary words with few squares. Bulletin of the EATCS 89 (2006) 164-166. | MR 2267840 | Zbl 1169.68565
[6] and , Polynomial versus exponential growth in repetition-free binary words. J. Comb. Th. (A) 105 (2004) 335-347. | MR 2046086 | Zbl 1065.68080
[7] M. Lothaire Ed., Combinatorics on Words. Cambridge University Press, 2nd edition (1997). | MR 1475463 | Zbl 0874.20040
[8] , and , Avoiding large squares in infinite binary words. Theoret. Comput. Sci. 339 (2005) 19-34. | MR 2142071 | Zbl 1099.68080
[9] , Last cases of Dejean's conjecture. Theor. Comput. Sci. 412 (2011) 3010-3018. | MR 2830264 | Zbl 1230.68163
[10] , Simultaneous avoidance of large squares and fractional powers in infinite binary words. Int. J. Found. Comput. Sci. 15 (2004) 317-327. | MR 2071461 | Zbl 1067.68119
[11] , Über unendliche Zeichenreihen. Norske Vid. Selsk. Skr. I. Mat. Nat. Kl. Christiana 7 (1906) 1-22. | JFM 37.0066.17