Square-free word

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

Finite square-free words

Binary alphabet

Over a binary alphabet $\{0,1\}$, the only square-free words are the empty word $ϵ,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 Template:Mvar.

The number of ternary square-free words of length n

Template:Mvar	0	1	2	3	4	5	6	7	8	9	10	11	12
Template:Tmath	1	3	6	12	18	30	42	60	78	108	144	204	264

This number is bounded by $c(n)=\mathrm{\Theta }({\alpha }^n)$, where $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 Template:Mvar-ary square-free words, rounded off to 7 digits after the decimal point, for Template:Mvar in the range from 4 to 15:

Growth rate of the Template:Mvar-ary square-free words

alphabet size (Template:Mvar)	4	5	6	7	8	9
growth rate	2.6215080	3.7325386	4.7914069	5.8284661	6.8541173	7.8729902
alphabet size (Template:Mvar)	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 $\text{w}$ from ${\mathbb{\mathbb{N}}}^2$ to Template:Mvar, where Template:Mvar is an alphabet and $\text{w}$ is called a 2-dimensional word. Let $w_{m,n}$ be the entry $\text{w}(m,n)$. A word $\text{x}$ is a line of $\text{w}$ if there exists $i_1,i_2,j_1,j_2$such that $\text{gcd}(j_1,j_2)=1$, and for $t\ge 0,x_t=w_{i_1+j_{1}t,i_2+j_{2}t}$.

Carpi proves that there exists a 2-dimensional word $\text{w}$ over a 16-letter alphabet such that every line of $\text{w}$ is square-free. A computer search shows that there are no 2-dimensional words $\text{w}$over a 7-letter alphabet, such that every line of $\text{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 Template:Mvar 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 Template:Tmath-ary square-free word.

algorithm R2F is
    input: alphabet size $k\ge 2$,
           word length $n>1$
    output: a Template:Tmath-ary square-free word Template:Mvar of length Template:Mvar.

    (Note that ${\mathrm{\Sigma }}_{k+1}$ is the alphabet with letters $\{1,...,k+1\}$.)
    (For a word $w\in {\mathrm{\Sigma }}_k$, ${\chi }_w$ is the permutation of ${\mathrm{\Sigma }}_k$ such that Template:Mvar precedes Template:Mvar in ${\chi }_w$ if the 
     right most position of Template:Mvar in Template:Mvar is to the right of the rightmost position of Template:Mvar in Template:Mvar.
     For example,  $w=136263163\in {\mathrm{\Sigma }}_6$ has ${\chi }_w=361245$.)

    choose $w[1]$ in ${\mathrm{\Sigma }}_{k+1}$ uniformly at random 
    set ${\chi }_w$ to $w[1]$ followed by all other letters of ${\mathrm{\Sigma }}_{k+1}$ in increasing order
    set the number Template:Mvar of iterations to 0

    while $|w|<n$ do
        choose Template:Mvar in ${\mathrm{\Sigma }}_k$ uniformly at random
        append $a={\chi }_w[j+1]$ to the end of Template:Mvar
        update ${\chi }_w$ shifting the first Template:Mvar elements to the right and setting ${\chi }_w[1]=a$
        increment Template:Mvar by Template:Mvar
        if Template:Mvar ends with a square of rank Template:Mvar then
            delete the last Template:Mvar letters of Template:Mvar

    return Template:Mvar

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 Template:Mvar.

The expected number of random k-ary letters used by Algorithm R2F to construct a Template:Tmath-ary square-free word of length Template:Mvar is$$N=n(1+\frac{2}{k^2}+\frac{1}{k^3}+\frac{4}{k^4}+O\left(\frac{1}{k^5}\right))+O(1).$$Note that there exists an algorithm that can verify the square-freeness of a word of length Template:Mvar 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 Template:Mvar.

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 Template:Tmath be any square-free word starting with the letter Template:Val. Define the words $\{w_i\mid i\in \mathbb{\mathbb{N}}\}$ recursively as follows: the word $w_{i+1}$ is obtained from Template:Tmath by replacing each Template:Val in Template:Tmath with Template:Val, each Template:Val with Template:Val, and each Template:Val with Template:Val. It is possible to prove that the sequence converges to the infinite square-free word

Template:Math

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 Template:Mvar is square-free if and only if it is 3-square-free. In other words, Template:Mvar is square-free if and only if $h(w)$ is square-free for all square-free Template:Mvar 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 Template:Mvar.

    set $k=3$
    while True do
        set k_sf_words to the list of all square-free words of length Template:Mvar over a ternary alphabet
        for each $h(0)$ in k_sf_words do
            for each $h(1)$ in k_sf_words do
                for each $h(2)$ in k_sf_words do
                    if $h(1)=h(2)$ then
                        break from the current loop (advance to next $h(1)$)
                    if $h(0)\ne h(1)$ and $h(2)\ne h(0)$ then
                        if $h(w)$ is square-free for all square-free Template:Mvar of length Template:Val then
                            return $h(0),h(1),h(2)$
        increment Template:Mvar by Template:Val

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 Template:Val, and successively apply a square-free morphism Template:Mvar to it. The resulting words preserve the property of square-freeness. For example, let Template:Mvar be a square-free morphism, then as $w\to \mathrm{\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

File:Squarefreeness-3--Bound.png

Extending a square-free word to avoid Template:Mvar.

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 Template:Mvar. As a result, Template:MvarTemplate:MvarTemplate:Mvar is the longest square-free word without the combination Template:Mvar 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 Template:Mvar in a finite word Template:Mvar is defined as $\frac{|w{|}_a}{|w|}$ where $|w{|}_a$ is the number of occurrences of Template:Mvar in $w$ and $|w|$ is the length of the word. The density of a letter Template:Mvar in an infinite word is $\underset{l\to \mathrm{\infty }}{\mathrm{lim\; inf}}\frac{|w_l{|}_a}{|w_l|}$ where $w_l$ is the prefix of the word Template:Mvar of length Template:Mvar.

The minimal density of a letter Template:Mvar in an infinite ternary square-free word is equal to $\frac{883}{3215}\approx 0.2747$.

The maximum density of a letter Template:Mvar in an infinite ternary square-free word is equal to $\frac{255}{653}\approx 0.3905$.

References

• .