Square-free word
A square is a word of the form XX, where X is not empty.
of ternary square-free words of length n. This number is bounded by
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.
[2] 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 k-ary square-free words, rounded off to 7 digits after the decimal point, for k in the range from 4 to 15:[2] Consider a map
[3] Carpi[4] proves that there exists a 2-dimensional word
A computer search shows that there are no 2-dimensional words
Shur[5] proposes an algorithm called R2F (random-t(w)o-free) that can generate a square-free word of length n 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
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 w. The expected number of random k-ary letters used by Algorithm R2F to construct a
Note that there exists an algorithm that can verify the square-freeness of a word of length n in
Apostolico and Preparata[6] give an algorithm using suffix trees.
Main and Lorentz[8] provide an algorithm based on the divide-and-conquer method.
time to verify the square-freeness of a word of length n. There exist infinitely long square-free words in any alphabet with three or more letters, as proved by Axel Thue.
obtained by taking the first difference of the Thue–Morse sequence.
The resulting square-free word is Another example found by John Leech[10] is defined recursively over the alphabet
be any square-free word starting with the letter 0.
Crochemore[11] proves that a uniform morphism h is square-free if and only if it is 3-square-free.
It is possible to find a square-free morphism by brute-force search.
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.
The resulting words preserve the property of square-freeness.
[12] This can be proved by constructing a square-free word without the two-letter combination ab.
As a result, bcbacbcacbaca is the longest square-free word without the combination ab 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.
[12] However, there are square-free words of any length without the three-letter combination aba.
The density of a letter a in a finite word w is defined as
The density of a letter a in an infinite word is
is the prefix of the word w of length l.[13] The minimal density of a letter a in an infinite ternary square-free word is equal to
[13] The maximum density of a letter a in an infinite ternary square-free word is equal to
