A word w is a finite sequence of letters from a certain alphabet. The length of a word is the number of letters of the word. Binary words are the words from two-letter alphabet {0, 1}, whereas ternary words are from three-letter alphabet {0, 1, 2}. A word is square-free if it does not contain two identical consecutive subwords, i.e. w cannot be written as axxb where a, b, x are words with x non-empty.

It is easy to see that there are only finitely many binary square-free words. However, there are infinitely many ternary square-free words. The fact was proved by Thue using what is now called the Prouhet-Thue-Morse sequence. Brinkhuis, Brandenburg, Zeilberger and Grimm showed that the numbers of such words of length n are greater than 2n/24, 2n/21, 2n/17, and 65n/40 respectively.

New Lower-Bound On The Number of Ternary Square-Free Words

Journal of Integer Sequences, vol. 6 (2003), Article 03.3.2

The article presents a new lower bound on the number of n-letter ternary square-free words: 110n/42, which improves the previous result of 65n/40 by Uwe Grimm.

The article is available in tex, pdf, dvi, and ps formats. The Maple package (75.3K) and C++ package (252K) are also available. Links to some of the Brinkhuis triples are here: 29, 30, 31, 32, 33, 34, 36, 37, 38, 39, 40, 41, 42, and 43. Click here (3.19M) for the complete result.

References

M. Baake, V. Elaser and U. Grimm, The entropy of square-free words, Math. Comput. Modelling 26 (1997), 13-26. F.-J. Brandenburg, Uniformly growing k-th power-free homorphisms, Theoret. Comput. Sci. 23 (1983), 69-82. J. Brinkhuis, Nonrepetitive sequences on three symbols, Quart. J. Math. Oxford 34 (1983), 145-149. S. B. Ekhad and D. Zeilberger, There are more than 2^(n/17) n-letter ternary square-free words. J. Integer Seq. 1 (1998), Article 98.1.9. S. Finch, Pattern-Free Word Constants Uwe Grimm, Improved Bounds on The Number of Ternary Square-Free Words, J. Integer Seq. 4 (2001), Article 01.2.7. Wolfram Research, Squarefree Word