In combinatorics, a squarefree word is a word (a sequence of symbols) that does not contain any squares. A square is a word of the form , where is not empty. Thus, a squarefree word can also be defined as a word that avoids the pattern .
Finite squarefree words
Binary alphabet
Over a binary alphabet , the only squarefree words are the empty word , and .
Ternary alphabet
Over a ternary alphabet , there are infinitely many squarefree words. It is possible to count the number of ternary squarefree words of length .
This number is bounded by , where . The upper bound on can be found via Fekete's Lemma and approximation by automata. The lower bound can be found by finding a substitution that preserves squarefreeness.
Alphabet with more than three letters
Since there are infinitely many squarefree words over three-letter alphabets, this implies there are also infinitely many squarefree words over an alphabet with more than three letters.
The following table shows the exact growth rate of the -ary squarefree words:
2-dimensional words
Consider a map from to , where is an alphabet and is called a 2-dimensional word. Let be the entry . A word is a line of if there exists such that , and for .
Carpi proves that there exists a 2-dimensional word over a 16-letter alphabet such that every line of is squarefree. A computer search shows that there are no 2-dimensional words over a 7-letter alphabet, such that every line of is squarefree.
Generating finite squarefree words
Shur proposes an algorithm called R2F (random-t(w)o-free) that can generate a squarefree word of length over any alphabet with three or more letters. This algorithm is based on a modification of entropy compression: it randomly selects letters from a k-letter alphabet to generate a -ary squarefree word. algorithm R2F is input: alphabet size , word length output: a -ary squarefree word of length .
choose in uniformly at random
set to followed by all other letters of in increasing order
set the number of iterations to 0
while do
choose in uniformly at random
append to the end of
update shifting the first elements to the right and setting
increment by
if ends with a square of rank then
delete the last letters of
return
Every (k+1)-ary squarefree word can be the output of Algorithm R2F, because on each iteration it can append any letter except for the last letter of .
The expected number of random k-ary letters used by Algorithm R2F to construct a -ary squarefree word of length isNote that there exists an algorithm that can verify the squarefreeness of a word of length in time. Apostolico and Preparata give an algorithm using suffix trees. Crochemore uses partitioning in his algorithm. Main and Lorentz provide an algorithm based on the divide-and-conquer method. A naive implementation may require time to verify the squarefreeness of a word of length .
Infinite squarefree words
There exist arbitrarily long squarefree words in any alphabet with three or more letters, as proved by Axel Thue.
Examples
First difference of the Thue–Morse sequence
One example of an infinite squarefree word over an alphabet of size 3 is the word over the alphabet obtained by taking the first difference of the Thue–Morse sequence. That is, from the Thue–Morse sequence
one forms a new sequence in which each term is the difference of two consecutive terms of the Thue–Morse sequence. The resulting squarefree word is
.
Leech's morphism
Another example found by John Leech is defined recursively over the alphabet . Let be any squarefree word starting with the letter . Define the words recursively as follows: the word is obtained from by replacing each in with , each with , and each with . It is possible to prove that the sequence converges to the infinite squarefree word
Generating infinite squarefree words
Infinite squarefree words can be generated by squarefree morphism. A morphism is called squarefree if the image of every squarefree word is squarefree. A morphism is called k–squarefree if the image of every squarefree word of length k is squarefree.
Crochemore proves that a uniform morphism is squarefree if and only if it is 3-squarefree. In other words, is squarefree if and only if is squarefree for all squarefree of length 3. It is possible to find a squarefree morphism by brute-force search. algorithm squarefree_morphism is output: a squarefree morphism with the lowest possible rank .