Square-free word
From Wikipedia, the free encyclopedia
In combinatorics, a square-free word is a word (a sequence of characters) that does not contain any subword twice in a row.
Thus a square-free word is one that avoids the pattern XX.[1][2]
Contents [hide]
1 Examples
2 Related concepts
3 Notes
4 References
Examples[edit]
Over a two-letter alphabet {a, b} the only square-free words are the empty word and a, b, ab, ba, aba, and bab. However, there exist infinite square-free words in any alphabet with three or more symbols,[3] as proved by Axel Thue.[4][5]
One example of an infinite square-free word over an alphabet of size 3 is the word over the alphabet {0,±1} obtained by taking the first difference of the Thue–Morse sequence.[6][7] That is, from the Thue–Morse sequence
0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, ...
one forms a new sequence in which each term is the difference of two consecutive terms of the Thue–Morse sequence. The resulting square-free word is
1, 0, −1, 1, −1, 0, 1, 0, −1, 0, 1, −1, 1, 0, −1, ... (sequence A029883 in the OEIS).
Another example found by John Leech[8] is defined recursively over the alphabet {a, b, c}. Let {\displaystyle w_{1}} w_{1} be any word starting with the letter a. Define the words {\displaystyle \{w_{i}\mid i\in \mathbb {N} \}} \{w_{i}\mid i\in \mathbb {N} \} recursively as follows: the word {\displaystyle w_{i+1}} w_{{i+1}} is obtained from {\displaystyle w_{i}} w_{i} by replacing each a in {\displaystyle w_{i}} w_{i} with abcbacbcabcba, each b with bcacbacabcacb, and each c with cabacbabcabac. It is possible to check that the sequence converges to the infinite square-free word
abcbacbcabcbabcacbacabcacbcabacbabcabacbcacbacabcacb...