Square-Free Words
A square word is a string of letters that consists of two identical adjacent subwords. For example, “abab” is square word because the subword “ab” is adjacently repeated.
A square-free word is a string of letters that contains no square words as subwords. For example, “aba” is a square-free word because there are no subwords that are adjacently repeated.
What is the minimum number of different letters needed to be able to make an infinite number of square-free words?
The answer is 3.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
See square-free word .
When there are only two different letters a and b, there are a finite number of square-free words: "a", "b", "ab", "ba", "aba", and "bab". In this alphabet, it is not possible to make a square-free word with more than three letters, because adding any letter to a three letter square-free word makes a square word. For example, using "aba" and adding a letter gives either "abaa" (but "a" is repeated) or "abab" (but "ab" is repeated), or using "bab" and adding a letter gives "baba" (but "ba" is repeated) or "babb" (but "b" is repeated).
However, when there are three different letters a, b, and c, there are an infinite number of square-free words. Axel Thue proved that if you start with Thue-Morse sequence (0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0 ...), find the difference between each consecutive term (1, 0, -1, 1, -1, 0, 1, 0, -1, 0, 1, -1, 1, 0, -1, ...) and assign letters to each number (a = 1, b = 0, c = -1), the result is an infinite square-free word (abcacbabcbacabc...)
Therefore, the minimum number of different letters needed to be able to make an infinite number of square-free words is 3 .