# Square-free word

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 XX, where X is not empty. Thus, a square-free word can also be defined as a word that avoids the pattern XX.

## Finite square-free words
### Binary alphabet

Over a binary alphabet $\{0,1\}$, the only square-free words are the empty word $\epsilon ,0,1,01,10,010$, and $101$.

### Ternary alphabet

Over a ternary alphabet $\{0,1,2\}$, there are infinitely many square-free words. It is possible to count the number $c(n)$ of ternary square-free words of length n.
The number of ternary square-free words of length n :
| n | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| ⁠$c(n)$⁠ | 1 | 3 | 6 | 12 | 18 | 30 | 42 | 60 | 78 | 108 | 144 | 204 | 264 |
This number is bounded by $c(n)=\Theta (\alpha ^{n})$, where 1.3017597<α<1.3017619{\textstyle 1.3017597<\alpha <1.3017619}. The upper bound on $\alpha$ 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.

### Alphabet with more than three letters

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:
Growth rate of the k-ary square-free words :
| alphabet size (k) | 4 | 5 | 6 | 7 | 8 | 9 |
| growth rate | 2.6215080 | 3.7325386 | 4.7914069 | 5.8284661 | 6.8541173 | 7.8729902 |
| alphabet size (k) | 10 | 11 | 12 | 13 | 14 | 15 |
| growth rate | 8.8874856 | 9.8989813 | 10.9083279 | 11.9160804 | 12.9226167 | 13.9282035 |

#### 2-dimensional words

Consider a map ${\textbf {w}}$ from $\mathbb {N} ^{2}$ to A, where A is an alphabet and ${\textbf {w}}$ is called a 2-dimensional word. Let $w_{m,n}$ be the entry ${\textbf {w}}(m,n)$. A word ${\textbf {x}}$ is a line of ${\textbf {w}}$ if there exists $i_{1},i_{2},j_{1},j_{2}$such that ${\text{gcd}}(j_{1},j_{2})=1$, and for $t\geq 0,x_{t}=w_{{i_{1}}+{j_{1}t},{i_{2}}+{j_{2}t}}$.
Carpi proves that there exists a 2-dimensional word ${\textbf {w}}$ over a 16-letter alphabet such that every line of ${\textbf {w}}$ is square-free. A computer search shows that there are no 2-dimensional words ${\textbf {w}}$over a 7-letter alphabet, such that every line of ${\textbf {w}}$ is square-free.

### Generating finite square-free words

Shur 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 ⁠$(k+1)$⁠-ary square-free word.
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 ⁠$(k+1)$⁠-ary square-free word of length n is$N=n\left(1+{\frac {2}{k^{2}}}+{\frac {1}{k^{3}}}+{\frac {4}{k^{4}}}+O\left({\frac {1}{k^{5}}}\right)\right)+O(1).$Note that there exists an algorithm that can verify the square-freeness of a word of length n in $O(n\log n)$ 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 $O(n^{2})$ time to verify the square-freeness of a word of length n.

## Infinite square-free words

There exist infinitely long square-free 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 square-free word over an alphabet of size 3 is the word over the alphabet $\{-1,0,+1\}$ obtained by taking the first difference of the Thue–Morse sequence. 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).

#### Leech's morphism

Another example found by John Leech is defined recursively over the alphabet $\{0,1,2\}$. Let ⁠$w_{1}$⁠ be any square-free word starting with the letter 0. Define the words $\{w_{i}\mid i\in \mathbb {N} \}$ recursively as follows: the word $w_{i+1}$ is obtained from ⁠$w_{i}$⁠ by replacing each 0 in ⁠$w_{i}$⁠ with 0121021201210, each 1 with 1202102012021, and each 2 with 2010210120102. It is possible to prove that the sequence converges to the infinite square-free word
    0121021201210120210201202120102101201021202102012021...

### Generating infinite square-free words

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 h is square-free if and only if it is 3-square-free. In other words, h is square-free if and only if $h(w)$ is square-free for all square-free w of length 3. 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.
To obtain an infinite square-free words, start with any square-free word such as 0, and successively apply a square-free morphism h to it. The resulting words preserve the property of square-freeness. For example, let h be a square-free morphism, then as $w\to \infty$, $h^{w}(0)$ 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.

## Letter combinations in square-free words
### Avoid two-letter combinations

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 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.

### Avoid three-letter combinations

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.

### Density of a letter

The density of a letter a in a finite word w is defined as ${\frac {|w|_{a}}{|w|}}$ where $|w|_{a}$ is the number of occurrences of a in $w$ and $|w|$ is the length of the word. The density of a letter a in an infinite word is $\liminf _{l\to \infty }{\frac {|w_{l}|_{a}}{|w_{l}|}}$ where $w_{l}$ is the prefix of the word w of length l.
The minimal density of a letter a in an infinite ternary square-free word is equal to ${\frac {883}{3215}}\approx 0.2747$.
The maximum density of a letter a in an infinite ternary square-free word is equal to ${\frac {255}{653}}\approx 0.3905$.