In combinatorics, a square-free 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 square-free word can also be defined as a word that avoids the pattern .
Over a binary alphabet , the only square-free words are the empty word , and .
Over a ternary alphabet ', there are infinitely many square-free words. It is possible to count the number of ternary square-free 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 square-freeness.
Since there are infinitely many square-free words over three-letter alphabets, this implies there are also infinitely many square-free words over an alphabet with more than three letters.
The following table shows the exact growth rate of the -ary square-free words, rounded off to 7 digits after the decimal point, for in the range from 4 to 15:
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 square-free. A computer search shows that there are no 2-dimensional words over a 7-letter alphabet, such that every line of is square-free.
Shur proposes an algorithm called R2F (random-t(w)o-free) that can generate a square-free 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 square-free word. algorithm R2F is input: alphabet size , word length ' output: a -ary square-free 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 square-free 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 square-free word of length isNote that there exists an algorithm that can verify the square-freeness 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 square-freeness of a word of length .
There exist infinitely long square-free words in any alphabet with three or more letters, as proved by Axel Thue.
One example of an infinite square-free 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 square-free word is
Another example found by John Leech is defined recursively over the alphabet . Let be any square-free 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 square-free word
Infinite square-free words can be generated by square-free morphism. A morphism is called square-free if the image of every square-free word is square-free. A morphism is called kâÂÂsquare-free if the image of every square-free word of length k is square-free.
Crochemore proves that a uniform morphism is square-free if and only if it is 3-square-free. In other words, is square-free if and only if is square-free for all square-free of length 3. It is possible to find a square-free morphism by brute-force search. algorithm square-free_morphism is output: a square-free morphism with the lowest possible rank .
set while True do set k_sf_words to the list of all square-free 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 square-free for all square-free of length then return increment by Over a ternary alphabet, there are exactly 144 uniform square-free morphisms of rank 11 and no uniform square-free morphisms with a lower rank than 11.
To obtain an infinite square-free words, start with any square-free word such as , and successively apply a square-free morphism to it. The resulting words preserve the property of square-freeness. For example, let be a square-free morphism, then as , is an infinite square-free word.
Note that, if a morphism over a ternary alphabet is not uniform, then this morphism is square-free if and only if it is 5-square-free.
Over a ternary alphabet, a square-free word of length more than 13 contains all the square-free two-letter combinations.
This can be proved by constructing a square-free word without the two-letter combination . As a result, ' is the longest square-free word without the combination and its length is equal to 13.
Note that over a more than three-letter alphabet there are square-free words of any length without an arbitrary two-letter combination.
Over a ternary alphabet, a square-free word of length more than 36 contains all the square-free three-letter combinations.
Note that over a more than three-letter alphabet there are square-free words of any length without an arbitrary three-letter combination.
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 square-free word is equal to .
The maximum density of a letter in an infinite ternary square-free word is equal to .