Square-free word

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 .
 
     set 
     while True do
         set k_sf_words to the list of all squarefree words of length  over a ternary alphabet
         for each  in k_sf_words do
             for each  in k_sf_words do
                 for each  in k_sf_words do
                     if  then
                         break from the current loop (advance to next )
                     if  and  then
                         if  is squarefree for all squarefree  of length  then
                             return 
         increment  by 
Over a ternary alphabet, there are exactly 144 uniform squarefree morphisms of rank 11 and no uniform squarefree morphisms with a lower rank than 11.

To obtain an infinite squarefree words, start with any squarefree word such as , and successively apply a squarefree morphism  to it. The resulting words preserve the property of squarefreeness.  For example, let  be a squarefree morphism, then as ,  is an infinite squarefree word.

Note that, if a morphism over a ternary alphabet is not uniform, then this morphism is squarefree if and only if it is 5-squarefree.

Letter combinations in squarefree words

Avoid two-letter combinations 
Over a ternary alphabet, a squarefree word of length more than 13 contains all the squarefree two-letter combinations.

This can be proved by constructing a squarefree word without the two-letter combination . As a result,  is the longest squarefree word without the combination  and its length is equal to 13.

Note that over a more than three-letter alphabet there are squarefree words of any length without an arbitrary two-letter combination.

Avoid three-letter combinations 
Over a ternary alphabet, a squarefree word of length more than 36 contains all the squarefree three-letter combinations.

However, there are squarefree words of any length without the three-letter combination .

Note that over a more than three-letter alphabet there are squarefree words of any length without an arbitrary three-letter combination.

Density of a letter 
The density of a letter  in a finite word  is  defined as  where  is the number of occurrences of  in  and  is the length of the word. The density of a letter  in an infinite word is  where  is the prefix of the word  of length .

The minimal density of a letter  in an infinite ternary squarefree word is equal to .

The maximum density of a letter  in an infinite ternary squarefree word is equal to .

Notes

References 

 
 .
 
 

Formal languages
Combinatorics on words