Another Solution to the Thue Problem

of Non-Repeating Words

Boris Zolotov (Saint-Petersburg, Russia)

Abstract

> In this work we consider morphisms that preserve well-known non-repeating
> properties: squarefreeness, cubefreeness, overlap-freeness and weak
> squarefreeness. Up to the present moment only the morphisms preserving three
> out of four non-repeating properties have been known. The problem of the
> existence of weakly squarefree morphisms was open.
>
> The essential result of this work is the positive solution to this problem.
> An example of the morphism preserving all four properties is provided. Also,
> it is proved that there are no morphisms with the same properties and a
> lower rank.

##  1 Introduction. The Problem

The problem was raised at the beginning of XX century by a Norwegian
mathematician Axel Thue. He wondered if it was possible to construct an
infinite word over the least possible alphabet such as no finite factors of it
repeat twice or three times. Such words were called squarefree or cubefree,
respectively. Thue [1] proved that such words exist and provided corresponding
examples.

An English mathematician John Leech [3] worked on the same problem. He found
an example of an infinite squarefree word, and this word was constructed using
an uniform morphism with the rank 13. An uniform morphism is a morphism such
as all the letters have images of the same length, and a rank of the morphism
is the length of the images of the letters.

In 1982 Max Crochemore [4] found an algorithmically verifiable criterion of
squarefreeness of a morphism.

In this work new results are obtained that allow us to optimize Thue’s and
Leech’s results and construct new sets of infinite non-repeating words.

##  2 Known Results

Let us provide Thue’s, Leech’s and Crochemore’s Results.

  1. 1)

The first example of an infinite cubefree word (Thue [1], 1906).

Let $\mathfrak{A}=\\{0;1\\}$; $A_{0}=1$; $\varphi:1\longrightarrow
10,0\longrightarrow 01$;

$A_{0}=1$

$\varphi(A_{0})=1\ 0$

$\varphi^{2}(A_{0})=10\ 01$

$\varphi^{3}(A_{0})=1001\ 0110$

$.\ .\ .\ .$

$\varphi^{\infty}(A_{0})=1001011001101001...$ is an infinite cubefree word,
which is also called the Thue-Morse sequence.

For the morphism $\varphi$ some other properties were also proved. Thue [1]
showed that the fixed point $\varphi^{\infty}(A_{0})$ did not contain any
factors of the form $aXaXa$, which are called overlaps. Furthermore,
$\varphi(W\\!)$ is cubefree when $W\\!$ is cubefree, and morphisms with this
property are called cubefree. Then, the image of any overlap-free word is
overlap-free, so $\varphi$ is also overlap-free. Morphisms with such
properties are called Thue morphisms.

  2. 2)

An example of morphism that generates an infinite squarefree word. (Thue [2],
1912).

Let $\mathfrak{A}=\\{1;2;3\\}$; $A_{0}=1$; $\varphi:1\longrightarrow
12312,2\longrightarrow 131232,3\longrightarrow 1323132$.

  3. 3)

An uniform morphism that generates an infinite squarefree word (Leech [3],
1957).

Let $\mathfrak{A}=\\{1;2;3\\}$; $A_{0}=1$;
$\varphi:1\longrightarrow 1232132312321,2\longrightarrow
2313213123132,3\longrightarrow 3121321231213$.

  4. 4)

The characterization of squarefreeness of a morphism (Crochemore [4], 1982).

A morphism defined on a three letter alphabet is squarefree iff the images of
the squarefree words of length 5 are squarefree.

  5. 5)

The characterization of squarefreeness of an uniform morphism (Crochemore [4],
1982).

An uniform morphism defined on a three letter alphabet is squarefree iff the
images of the squarefree words of length 3 are squarefree.

##  3 Definitions

Alphabet, Word, Morphism

An alphabet is a finite set, and its elements are called letters. A word upon
the alphabet is a sequence of this alphabet’s letters. The number of letters
in the word $W\\!$ is called the length of $W\\!$ and denoted by $|W\\!|$. The
$i$–th letter in the word $W\\!$ is denoted by $W\\![i]$.

The set of all the words upon the alphabet $\mathfrak{A}$ is denoted by
$\overline{\mathfrak{A}}$. The concatenation operation makes it be a free
monoid with an empty word as a neutral element.

A morphism is a function
$\varphi\colon\overline{\mathfrak{A}}\mapsto\overline{\mathfrak{A}}$ that
preserves the concatenation:

$\forall\,u,v\in\overline{\mathfrak{A}}\quad\varphi(uv)=\varphi(u)\varphi(v).$

Let $L$ be a positive integer. A morphism $\varphi$ is called $L$–uniform if
for every $a\in\mathfrak{A}$ we have $|\varphi(a)|=L$. In this case, $L$ is
called the rank of the morphism $\varphi$.

Morphism and fixed point

As long as $\varphi$ is an automorphism of a free monoid
$\overline{\mathfrak{A}}$, it is sufficient to define images of the elements
of $\mathfrak{A}$ to entirely describe $\varphi$.

An example:

Let $\mathfrak{A}=\\{1;2;3\\}$ and let $X=1231$ be a word upon $\mathfrak{A}$.

$\varphi:1\longrightarrow 1231,2\longrightarrow 3112,3\longrightarrow 1132$.

Then
$\varphi(1231)=\varphi(1)\varphi(2)\varphi(3)\varphi(1)=1231\,3112\,1132\,1231$.

When $r$–uniform morphism $\varphi$ is applied to a word $W\\!$, the length of
$\varphi(W\\!)$ is divisible by $r$. So, we can define canonical fragments,
which are non-crossing factors of length $r$ in $\varphi(W\\!)$ that cover
$\varphi(W\\!)$ and are images of the letters of $W\\!$.

Let us consider an iterational sequence of words $A_{n}$ such as
$A_{n+1}=\varphi(A_{n})$. If it is known that for any integer $n$
$A_{n+1}=A_{n}V_{n}$ then there exists an infinite word $A$ such as:

  1. 1)

for every integer $n$ it is true that $A=A_{n}W\\!_{n}$;

  2. 2)

$\varphi(A)=A$.

$A$ is called the fixed point of the morphism $\varphi$ and denoted by
$\varphi^{\infty}(A_{1})$.

Increasing and Decreasing, Cyclic Morphisms

Let us consider the ternary alphabet $\mathfrak{A}=\\{1;2;3\\}$. We will
define operations ‘$\oplus 1$’ and ‘$\ominus 1$’ upon it, such as:

$\begin{array}[]{l}1\oplus 1=2\\\ 2\oplus 1=3\\\ 3\oplus 1=1\\\ \end{array}$
$\begin{array}[]{l}1\ominus 1=3\\\ 2\ominus 1=1\\\ 3\ominus 1=2\\\
\end{array}$.

Given a word $T$ upon a ternary alphabet, we can define words $T\oplus 1$ and
$T\ominus 1$.

$T\oplus 1$ is a word such that

$\forall i=\overline{1,|T|}$ $(T\oplus 1)[i]=(T[i])\oplus 1$;

$T\ominus 1$ is a word such that

$\forall i=\overline{1,|T|}$ $(T\ominus 1)[i]=(T[i])\ominus 1$.

$r$–uniform morphism $\varphi$ is called cyclic if

$\forall\,p\in\mathfrak{A}$ $\varphi(p\oplus 1)=(\varphi(p))\oplus 1$.

A word $W\\!$ of length $l$ is called increasing if

$\forall\,i=\overline{1,l-1}$ $W\\![i+1]=W\\![i]\oplus 1$.

A word $W\\!$ of length $l$ is called decreasing if

$\forall\,i=\overline{1,l-1}$ $W\\![i+1]=W\\![i]\ominus 1$.

Properties of words and morphisms

A square is a word of the form $X\\!X$, where $X$ is not empty. Example —
$123\,123$.

A word is called squarefree if it does not contain any squares.

A morphism is called squarefree if image of every squarefree word is
squarefree. A morphism is called $k$–squarefree if image of every squarefree
word of length $k$ is squarefree.

A cube is a word of the form $X\\!X\\!X$, where $X$ is not empty. Example —
$123\,123\,123$.

A word is called cubefree if it does not contain any cubes.

A morphism is called cubefree if the image of every cubefree word is cubefree.

An overlap is a word of the form $aX\\!aX\\!a$, $X$ can be empty. Example —
$2\,123\,2\,123\,2$.

A word is called overlap-free if it does not contain any overlaps.

A morphism is called overlap-free if the image of every overlap-free word is
overlap-free.

A weak square is a word of the form $aX\\!X\\!a$, $X$ can be empty. Example —
$3\,123\,123\,3$.

A word is called weakly squarefree if it does not contain any weak squares.

A morphism is called weakly squarefree if the image of every weakly squarefree
word is weakly squarefree.

A morphism is called a Thue morphism if it is cubefree, overlap-free and
generates a fixed point $\varphi^{\infty}(a)$, where $a$ is a letter.

##  4 Objectives

In this research we are addressing the following questions:

  1. 1)

Is Leech’s result optimal? Are there any uniform squarefree morphisms with a
lower rank?

  2. 2)

Are there any uniform Thue morphisms over the ternary alphabet?

  3. 3)

Are there any weakly squarefree Thue morphisms over the ternary alphabet?

  4. 4)

How is weak squarefreeness connected with other properties, for example, with
usual squarefreeness?

  5. 5)

Which combinations of letters are necessary in squarefree words? What is the
necessary length for these combinations?

##  5 Main Results

The main results of this work are the following:

Newly Created Morphisms

The following morphisms were considered, and their properties were studied:

  * 1)

A morphism $\varphi:1\longrightarrow 12321,2\longrightarrow
23132,3\longrightarrow 31213$ is a cubefree and weakly squarefree morphism
over the ternary alphabet. It also generates a fixed point.

  * 2)

A morphism $\varphi:1\longrightarrow 1221,2\longrightarrow
2332,3\longrightarrow 3113$ is a Thue morphism over the ternary alphabet.

  * 3)

A morphism $\varphi:1\longrightarrow 121,2\longrightarrow 232,3\longrightarrow
313$ is a cubefree morphism over the ternary alphabet. It also generates a
fixed point.

Low-Rank Morphisms

The following theorems were proved for the low-rank morphisms:

  * 4)

Over the ternary alphabet there are no uniform weakly squarefree Thue
morphisms with a rank lower than 5.

  * 5)

Over the binary alphabet there are no weakly squarefree Thue morphisms.

Weak Squarefreeness A theorem on connection between non-repeating properties
was proved:

  * 6)

An uniform and cyclic squarefree morphism is weakly-squarefree.

Leech’s Morphism and Optimal Ranks

The following results were obtained:

  * 7)

There are exactly 144 uniform squarefree morphisms of rank 11; there are no
uniform squarefree morphisms with a lower rank.

  * 8)

The Leech’s morphism is cyclic; there are no cyclic squarefree morphisms with
a rank lower than 13.

  * 9)

The Leech’s morphism is squarefree, cubefree, overlap-free and weakly
squarefree. There are no morphisms with such properties and a lower rank.

Letter combinations in squarefree words

Letter combinations over the ternary were considered, and the following
results were obtained:

  * 10)

Each squarefree word of length more than 13 over the ternary alphabet contains
all the two-letter combinations of distinct letters.

  * 11)

Each squarefree word of length more than 36 over the ternary alphabet contains
all the three-letter combinations of distinct letters (of the form $abc$).

Summary

All the questions addressed were answered. What was found is the lower bound
of the rank of uniform squarefree morphisms over the ternary alphabet. All the
morphisms having such a rank were provided.

Furthermore, it was shown that there exist weakly squarefree Thue morphisms
over the ternary alphabet. The lower bound of the rank of such morphisms was
provided. Also, we provided low-rank morphisms over the ternary alphabet that
have only a few of the considered properties. It proves that the properties
are independent from each other.

On the other hand, it was proved that cyclicness and squarefreeness result in
weak squarefreeness. Also, the properties of the letter combinations were
examined.

There remains the open problem of the existence of uniform weakly squarefree
Thue morphisms of rank between 5 and 13.

##  6 Proofs of the main results.
Newly created morphisms

Lemma (0): A morphism $\varphi$ has a fixed point $\varphi^{\infty}(u)$ (where
$u$ is a letter) iff there exists a word $V$ such as $\varphi(u)=uV$.

We will use the induction method to prove the lemma. Let us construct a
sequence of words $A_{n}$ such as $A_{0}=u$ and $A_{k+1}=\varphi(a_{k})$. It
is necessary to show that for any $k\in\mathbb{N}_{0}$ there exists a word
$W\\!$ such as $A_{k+1}=A_{k}W\\!$.

For $k=0$ the statement is true, because it is given in the wording. Now let
us assume that for an integer $k$ we have $A_{k+1}=A_{k}W\\!$.

Then
$A_{k+2}=\varphi(A_{k+1})=\varphi(A_{k}W\\!)=\varphi(A_{k})\varphi(W\\!)=A_{k+1}W^{\prime}\\!$.
As a result, we obtain that each word in the sequence $A_{n}$ is a prefix of
the next one. Consequently, the morphism $\varphi$ has a fixed point
$\varphi^{\infty}(u)$.

Theorem 1: The morphism $\varphi:1\longrightarrow 12321,2\longrightarrow
23132,3\longrightarrow 31213$ is a cubefree morphism over the ternary
alphabet.

a canonical fragment of the morphism $\varphi$,
increasing and decreasing factors of it

We need a series of lemmas to prove this theorem.

Lemma (1): When morphism $\varphi$ is applied to a cubefree word, the image of
this word does not contain any cubes of letters (of the form $aaa$).

Let the image of a cubefree word have a cube of the letter $aaa$. Then two of
these three letters belong to one canonical fragment. On the other hand, it is
easy to see that inside the canonical fragments the letters that are next to
each other are different.

Lemma (2): When morphism $\varphi$ is applied to a cubefree word, the image of
this word does not contain any cubes of the form $X\\!X\\!X$, where $|X|=2$.

Let us notice that in the canonical fragment $a_{1}a_{2}a_{3}a_{4}a_{5}$ the
following equations are true:

$a_{1}=a_{5}$;

$a_{2}=a_{4}$;

$a_{2}=a_{1}\oplus 1$;

$a_{3}=a_{2}\oplus 1$.

Now let us denote the cube $X\\!X\\!X$ by $c_{1}c_{2}c_{3}c_{4}c_{5}c_{6}$.
Two canonical fragments are sufficient to cover the cube; we will denote these
canonical fragments by $a_{1}a_{2}a_{3}a_{4}a_{5}$ and
$b_{1}b_{2}b_{3}b_{4}b_{5}$.

Finally, we are to consider all the possible cases of the position of the
letter $c_{1}$ inside the first canonical fragment.

  1. 1)

$c_{1}=a_{1}$. Then $c_{3}=(c_{1}\oplus 1)\oplus 1=c_{1}\ominus 1$. This
contradicts the fact that $c_{3}=c_{1}$.

  2. 2)

$c_{1}=a_{2}$. Then the word $c_{1}c_{2}$ is increasing, whereas $c_{3}c_{4}$
is decreasing. This contradicts the fact that these words are equal.

  3. 3)

$c_{1}=a_{3}$. Then the word $c_{1}c_{2}$ is decreasing, whereas $c_{5}c_{6}$
is increasing. This contradicts the fact that these words are equal.

  4. 4)

$c_{1}=a_{4}$. Then the word $c_{1}c_{2}$ is decreasing, whereas $c_{3}c_{4}$
is increasing. This contradicts the fact that these words are equal.

  5. 5)

$c_{1}=a_{5}$. Then the word $c_{3}c_{4}$ is increasing, whereas $c_{5}c_{6}$
is decreasing. This contradicts the fact that these words are equal.

As a result, the cube of length 6 can not begin with any letter inside the
canonical fragment. The Lemma is proved.

Lemma (3): When morphism $\varphi$ is applied to a cubefree word, the image of
this word does not contain any cubes of the form $X\\!X\\!X$, where $|X|=3$.

Several cases are possible of how the cube $X\\!X\\!X$ lies inside the
sequence of canonical fragments. The first one is when the second occurence of
$X$ consists of the 2-nd, the 3-rd and the 4-th letter of a canonical
fragment. Then the word made of two last letters of $X$ is increasing and
decreasing at the same time; this case is impossible.

In other cases the following fact is easy to check: two words $X$ out of three
must lie inside canonical fragments without crossing the borders. These two
words will begin at different positions inside the canonical fragments,
because the length of the cube is not divisible by 5.

Now let us notice that all the distinct factors of length 3 inside the
canonical fragment are different if increasing / decreasing is considered.
This fact makes the existence of the cube $X\\!X\\!X$ impossible, if $|X|=3$.

Lemma (4): When morphism $\varphi$ is applied to a cubefree word, the image of
this word does not contain any cubes of the form $X\\!X\\!X$, where $|X|=4$.

To prove this Lemma it is also needed to consider five cases of the position
of the first letter of the cube inside the canonical fragment. In each case it
is easy to obtain that a factor of $X$ is increasing and decreasing at the
same time.

Lemma (5): When morphism $\varphi$ is applied to a cubefree word, the image of
this word does not contain any cubes of the form $X\\!X\\!X$, where $|X|$ is
divisible by 5.

Let us notice that the morpism $\varphi$ is cyclic. For a cyclic morphism it
is true that the canonical fragment can be determined by a letter inside it
and the position of this letter inside the fragment.

Furthermore, the corresponding letters in the words $X$ are located on the
same positions inside canonical fragments. It leads to the fact that the
corresponding canonical fragments are identical. Finally, we can say that the
original word contained a cube, which contradicts the wording.

Lemma (6): A sequence of canonical fragments of the morphism $\varphi$ does
not contain any squares $X\\!X$ such that $|X|$ is greater than 5 and not
divisible by 5.

Let such a square exist inside the sequence of fragments. Then each word $X$
contains a border between two canonical fragments next to each other.
Furthermore, if we compare these two words $X$, we will see that the borders
of the canonical fragments are shifted in the second one.

On the other hand, it can be noticed that any shift of the canonical fragment
of the morphism $\varphi$ has increases / decreases differently from the
original one. Finally, it means that one factor of $X$ has to be increasing
and decreasing at the same time, which is impossible.

The Lemma is now proved.

Now let the image of a cubefree word contain a cube. Lemmas 1–6 consider all
the cases of the length of $X$, and for each case it is proved that cubes with
this length do not exist.

The theorem is proved.

Theorem 2: The morphism $\varphi:1\longrightarrow 12321,2\longrightarrow
23132,3\longrightarrow 31213$ is a weakly squarefree morphism over the ternary
alphabet.

Lemma (7): When morphism $\varphi$ is applied to a weakly squarefree word, the
image of this word does not contain any squares of a letter.

Let a square of a letter exist inside the image of a weakly squarefree word.
Two identical successive letters can not lie inside one canonical fragment,
because inside the canonical fragment all successive letters are different. It
means that equal letters lie on the edges of two successive canonical
fragments. As a result, these fragments are the same, and in the original word
there was a square of a letter, which is also a weak square. This contradicts
the wording.

Lemma (8): When morphism $\varphi$ is applied to a weakly squarefree word, the
image of this word does not contain any weak squares of the form $abba$, where
$a$, $b$ are letters.

Let us notice that the factor $bb$ can not lie inside a canonical fragment,
because successive letters inside the canonical fragment are different. It
means that the weak square $abba$ lies on the border of two canonical
fragments, one of which ends with $b$, and the other one starts with $b$.

Now let us note that the only canonical fragment can start with $b$, and it is
$\varphi(b)$. Also, $\varphi(b)$ is the only canonical fragment that ends with
$b$. It means that the original word contained the weak square $bb$, which
contradicts the wording.

Lemma (9): When morphism $\varphi$ is applied to a weakly squarefree word, the
image of this word does not contain any weak squares of the form $aX\\!Xa$,
where $|X|=2$.

We will prove that image of the weakly squarefree word can not contain a
square $X\\!X$, where $|X|=2$. If such a square lies inside the image, then
two canonical fragments are sufficient to cover it. Let us denote the first
canonical fragment by $a_{1}a_{3}a_{3}a_{4}a_{5}$ and consider the cases of
the position of the first letter of the square inside it.

  1. 1)

If the first letter of the square is the first or the second letter of the
canonical fragment, then the word $X$ is increasing and decreasing at the same
time, which is impossible.

  2. 2)

If the first letter of the square is the third letter of the canonical
fragment, then the first letters of two words $X$ are different, which is
impossible.

  3. 3)

If the first letter of the square is the fourth letter of the canonical
fragment, then the word $X$ is increasing and decreasing at the same time,
which is impossible.

  4. 4)

If the first letter of the square is the fifth letter of the canonical
fragment, then the last letters of two words $X$ are different, which is
impossible.

Now the Lemma is proved.

Lemma (10): When morphism $\varphi$ is applied to a weakly squarefree word,
the image of this word does not contain any weak squares of the form
$aX\\!Xa$, where $|X|=3$.

We will prove that image of the weakly squarefree word can not contain a
square $X\\!X$, where $|X|=3$. If such a square exists then the first or the
last letters of two words $X$ lie in one canonical fragment.

Now let us notice that two letters inside one canonical fragment are not
identical if the difference between their positions is equal to 3. It means
that the first or the last letters of $X$ are different, which is impossible.

Lemma (11): When morphism $\varphi$ is applied to a weakly squarefree word,
the image of this word does not contain any weak squares of the form
$aX\\!Xa$, where $|X|=4$.

In the beginning, let us notice that the image of a weakly squarefree word can
contain a square $X\\!X$, $|X|=4$. For example,
$\varphi(212)=231\,3212\,3212\,3132$. This square is not weak, though.

To prove this lemma it is sufficient to consider five cases of the position of
the first letter of the weak square inside the canonical framgment, and for
each case easily obtain the contradiction: corresponding letters of the weak
square will not match, or increasing / decreasing on the same word will be
different.

Lemma (12): When morphism $\varphi$ is applied to a weakly squarefree word,
the image of this word does not contain any weak squares of the form
$aX\\!Xa$, where $|X|$ is divisible by 5.

The two cases of the position of $X\\!X$ inside the sequence of canonical
fragments are possible.

The first one: $X$ is an image of several letters — $X=\varphi(W)$. We
consider the weak square $a\,\varphi(W)\varphi(W)\,a$. It means that the first
letter $a$ is the last in the canonical fragment, and the second letter $a$ is
the first in the canonical fragment. As a consequence, these canonical
fragments are both equal to $\varphi(a)$. Finally, the original word must
contain the weak square $aW\\!Wa$, which is impossible.

The second one: the words $X$ begin at the same positions inside different
canonical fragments. Then these fragments are identical, and the word $X$ must
end with the $a$ letter. It means that inside the canonical fragment two
successive letters are both equal to $a$, which is impossible.

Now let the image of a weakly squarefree word contain a weak square $aX\\!Xa$.
Lemmas 6–12 consider all the cases of the length of $X$, and for each case it
is proved that weak squares with this particular length of $X$ do not exist in
the image.

The Theorem is proved.

Theorem 3: The morphism $\varphi:1\longrightarrow 12321,2\longrightarrow
23132,3\longrightarrow 31213$ over the ternary alphabet has a fixed point
$\varphi^{\infty}(1)$.

Indeed, $\varphi(1)=1\,2321=1W$, and by Lemma (0) the fixed point
$\varphi^{\infty}(1)$ exists.

Remark: The morphism $\varphi:1\longrightarrow 12321,2\longrightarrow
23132,3\longrightarrow 31213$ over the ternary alphabet is not squarefree and
not overlap-free.

Indeed, $\varphi(212)=231\ 3\,212\,3\,212\,3\ 132$ contains an overlap, and,
consequently, a square.

Theorem 4: The morphism $\varphi:1\longrightarrow 1221,2\longrightarrow
2332,3\longrightarrow 3113$ over the ternary alphabet is a Thue morphism.

a canonical fragment of the morphism $\varphi$,
increasing and decreasing factors of it

We need a series of lemmas to prove this theorem.

It is necessary to show that the morphism $\varphi$ is cubefree, overlap-free
and has a fixed point. The morphism $\varphi$ that we consider has a fixed
point — $\varphi^{\infty}(1)$ — because $\varphi(1)=1221=1W$, and this is
exactly what the wording of Lemma (0) requires.

Lemmas (13)–(15) consider a generalized form of cubefreeness and overlap-
freeness. They prove that when the morphism $\varphi$ is applied to a cubefree
word the image of it does not contain any overlaps of the corresponding
length.

We can consider this form generalized as long as an overlap-free word is
always cubefree.

Lemma (13): When morphism $\varphi$ is applied to a cubefree word, the image
of this word does not contain any cubes of a letter.

Let the image of the word contain a cube of a letter $aaa$. Then two of these
three letters belong to a canonical fragment’s edge. On the other hand,
letters on the edge of the canonical fragments are different if the morphism
$\varphi$ is considered.

Lemma (14): When morphism $\varphi$ is applied to a cubefree word, the image
of this word does not contain any overlaps of the form $aX\\!aX\\!a$, where
$|X|=1$.

Let the image of the word contain such an overlap. The length of this overlap
is equal to 5. Two successive canonical fragments are sufficient to cover this
overlap.

Let us now notice that for any canonical fragment $abcd$ the following
equation takes place:

$b=c=a\oplus 1=d\oplus 1$.

Two $a$ letters out of three in the overlap belong to one canonical fragment.
The difference between the position of these letters is equal to 2. However,
in the canonical fragment $abcd$ we have $a\not=c$ and $b\not=d$.

As a consequence, we can not have an overlap of length 5 in the image of a
cubefree word.

Lemma (15): When morphism $\varphi$ is applied to a cubefree word, the image
of this word does not contain any overlaps of the form $aX\\!aX\\!a$, where
$|X|=2$.

Let the image of the word contain such overlap. The length of this overlap is
equal to 7. Three successive canonical fragments are sufficient to cover this
overlap. Let us denote these fragments by $a_{1}a_{2}a_{3}a_{4}$,
$b_{1}b_{2}b_{3}b_{4}$ and $c_{1}c_{2}c_{3}c_{4}$.

Let us now consider the cases of location of two $X$ words inside the three
canonical fragments.

  1. 1)

$a_{2}a_{3}=b_{1}b_{2}$. These words can not be equal, because $a_{2}=a_{3}$,
whereas $b_{2}=b_{1}\oplus 1$.

  2. 2)

$a_{3}a_{4}=b_{2}b_{3}$. These words can not be equal, because $b_{2}=b_{3}$,
whereas $a_{3}=a_{4}\oplus 1$.

  3. 3)

$a_{4}b_{1}=b_{3}b_{4}$. Now let us consider the $a$ letters preceding the $X$
words. Therefore, $a=a_{3}=a_{4}\ominus 1$, and $a=b_{2}=b_{3}$. On the other
hand, these equations can not be true at the same time, because $b_{3}=a_{4}$.

  4. 4)

$b_{1}b_{2}=b_{4}c_{1}$. Now let us consider the $a$ letters following the $X$
words. Therefore, $a=b_{3}=b_{2}$, and $a=c_{2}=c_{1}\oplus 1$. On the other
hand, these equations can not be true at the same time, because $b_{2}=c_{1}$.

As a result, there are no overlaps of length 7 in the image of a cubefree
word.

Lemma (16): When morphism $\varphi$ is applied to a cubefree word, the image
of this word does not contain any overlaps of the form $aX\\!aX\\!a$, where
$|aX|$ is divisible by 4.

Because the morphism $\varphi$ is cyclic, its canonical fragment can be
determined by a letter and its position inside the fragment. Furthermore, it
is obvious that the $a$ letters lie on the same positions inside the
corresponding canonical fragments. The reason for this is that the global
positions of the $a$ letters in the image of the word have the same ramainder
of the division by 4.

Furthermore, the corresponding letters of the $X$ words lie on the same
positions in the canonical fragments and are equal to each other. Therefore,
the corresponding canonical fragments are equal, and there was an overlap in
the original word. It contradicts the wording.

The proof of the fact that the image of a cubefree word does not contain any
cubes of the form $X\\!X\\!X$, where $|X|$ is divisible by $4$, is absolutely
the same.

Lemma (17): In a sequence of canonical fragments of the morphism $f$ a factor
of length more than 4 and not divisible by 4 can not repeat twice.

Let the sequence of canonical fragments contain a square $X\\!X$. Then each
word $X$ contains a border between two canonical fragments next to each other.
Furthermore, if we compare these two words $X$, we will see that the borders
of canonical fragments are shifted in the second one.

On the other hand, it can be noticed that any shift of canonical fragment of
the morphism $\varphi$ has increasing / decreasing different from original
one. Finally, it means that one factor of $X$ must be increasing and
decreasing at the same time, which is impossible.

The Lemma is now proved.

As a result, the morphism $\varphi$ is a Thue morphism. If the image of a
cubefree word contains a cube, or the image of an overlap-free word contains
an overlap, the corresponding lemma proves that there can not be any cubes and
overlaps of the corresponding length.

The theorem is proved.

Remark: The morphism $\varphi:1\longrightarrow 1221,2\longrightarrow
2332,3\longrightarrow 3113$ over the ternary alphabet is not squarefree and
not weakly squarefree.

Indeed, the image of each letter contains a square and is a weak square.

Theorem 5: The morphism $\varphi:1\longrightarrow 121,2\longrightarrow
232,3\longrightarrow 313$ over the ternary alphabet is cubefree and has a
fixed point.

a canonical fragment of the morphism $\varphi$,
increasing and decreasing factors of it

Lemma (18): When morphism $\varphi$ is appliaed to a cubefree word, the image
of this word does not contain any cubes of letters (of the form $aaa$).

Let the image of the word contain a cube of a letter $aaa$. At least two out
of three letters given belong to a common canonical fragment. However, inside
the canonical fragment of the morphism $\varphi$ successive letters are
different.

Lemma (19): When morphism $\varphi$ is applied to a cubefree word, the image
of this word does not contain any cubes of the form $X\\!X\\!X$, where
$|X|=2$.

Let the image of the word contain such a cube. Its length is equal to 6. Three
successive canonical fragments are sufficient to cover it. Let us denote these
canonical fragments by $a_{1}a_{2}a_{3}$, $b_{1}b_{2}b_{3}$ and
$c_{1}c_{2}c_{3}$.

Let us consider the cases of the position of the cube inside these canonical
fragments.

  1. 1)

$a_{1}a_{2}=a_{3}b_{1}=b_{2}b_{3}$. This is impossible because the word
$a_{1}a_{2}$ is increasing, whereas the word $b_{2}b_{3}$ is decreasing.

  2. 2)

$a_{2}a_{3}=b_{1}b_{2}=b_{3}c_{1}$. This is impossible because the word
$b_{1}b_{2}$ is increasing, whereas the word $a_{2}a_{3}$ is decreasing.

  3. 3)

$a_{3}b_{1}=b_{2}b_{3}=c_{1}c_{2}$. This is impossible because the word
$c_{1}c_{2}$ is increasing, whereas the word $b_{2}b_{3}$ is decreasing.

As a result, there are no cubes of length 6 in the image of a cubefree word.

Lemma (20): When morphism $\varphi$ is applied to a cubefree word, the image
of this word does not contain any cubes of the form $X\\!X\\!X$, where $|X|$
is divisible by 3.

The proof of this lemma is similar to the proofs of lemmas (5) and (16).
Indeed, a canonical fragment can be determined by a letter and its position in
the fragment, and the corresponding letters of the words $X$ have the same
positions in the corresponding canonical fragments.

As a result, we obtain that the original word contain a cube.

Lemma (21): When morphism $\varphi$ is applied to a cubefree word, the image
of this word does not contain any cubes of the form $X\\!X\\!X$, where $|X|$
is greater than 3 and not divisible by 3.

As long as the canonical fragment of the morphism $\varphi$ has length 3, and
$|X|$ is not divisible by 3, one of the $X$ words begins with the first letter
of a canonical fragment, and another one begins with the second letter of a
canonical fragment.

This fact can be proved using different methods. For example, it is known that
$\\{1;2\\}$ is the generating set of the group $\mathbb{Z}/3\mathbb{Z}$.

The fact that one of the $X$ words begins with the first letter of a canonical
fragment makes $X\\![1]X\\![2]$ an increasing word. On the other hand,
$X\\![1]X\\![2]$ must be decreasing, because another $X$ word begins with the
second letter of a canonical fragment.

As a result, $X\\![1]X\\![2]$ must be increasing and decreasing at the same
time, which is impossible.

Lemma (22): The morphism $\varphi$ has a fixed point $\varphi^{\infty}(1)$.

We can use lemma (0) to prove it. Indeed, $\varphi(1)=121=1W$.

Therefore, the theorem is proved. Lemmas (18)–(21) consider all the cases of
the length of the cube and show that the image of a cubefree word can not
contain any cubes of such length.

Remark: The morphism $\varphi$ is neither squarefree nor weakly squarefree nor
overlap-free.

  1. 1)

$\varphi(12)=12\,12\,32$ contains a square;

  2. 2)

$\varphi(123)=12\,1\,23\,23\,1\,3$ contains a weak square;

  3. 3)

$\varphi(212)=23\,2\,1\,2\,1\,2\,31$ contains an overlap.

##  7 Low-rank morphisms

Lemma (23): If $\varphi$ is a weakly squarefree Thue morphism over the ternary
alphabet, then all the first characters of the images of the letters are
different; all the last characters of the images of the letters are also
different.

Let us assume that there exist two letters $a$, $b$ such as

$\varphi(a)=xU$, $\varphi(b)=xW$.

Then $\varphi(aab)$ contains an overlap $xUxUx$, which contradicts the
wording.

Similarly, if $\varphi(a)=Ux$, $\varphi(b)=Wx$, then $\varphi(abb)$ contains
an overlap $xWxWx$.

Let us now notice that we appealed only to the fact that a Thue morphism is
always overlap-free. Thus, it can be said that if $\varphi$ is an overlap-free
morphism over the ternary alphabet, then all the first characters of the
images of the letters are different; all the last characters of the images of
the letters are also different.

Lemma (24): If $\varphi$ is a weakly squarefree Thue morphism over the ternary
alphabet, then for each $a\in\mathfrak{A}$ the first and the second letters of
$\varphi(a)$ are different, the last and the penultimate letters of
$\varphi(a)$ are also different.

Lemma (23) implies that for every $a\in\mathfrak{A}=\\{1,2,3\\}$ there is a
canonical fragment beginning with it. Therefore, if $\varphi(a)=Uxx$, then
there exists $b$ such as $\varphi(b)=xW$. As a result, $\varphi(ab)$ contains
a cube, which contradicts the wording.

Another proposition of the lemma can be proved similarly.

Lemma (25): If $\varphi$ is a weakly squarefree Thue morphism over the ternary
alphabet, then for each $a\in\mathfrak{A}$ the first character of $\varphi(a)$
is equal to the last character of $\varphi(a)$.

Let there be a letter $a$ such as $\varphi(a)=xWy$. Then there exists a letter
$b$ such as $\varphi(b)=yU$, and $b\neq a$. As a result, $\varphi(ab)=xWyyU$
contains a weak square $yy$.

Theorem 6: Over the ternary alphabet there are no uniform weakly squarefree
Thue morphisms with a rank lower than 5.

Proposition 1: Over the ternary alphabet there are no uniform overlap-free
morphisms with rank 2.

Let there be an overlap-free morphism $\varphi:a_{1}\longrightarrow
ab,a_{2}\longrightarrow cd,a_{3}\longrightarrow ef$. Lemma (23) implies that
$a\neq c\neq e$ and $b\neq d\neq f$.

Let us now consider the image of an overlap-free word $a_{1}a_{1}$:
$\varphi(a_{1}a_{1})=abab$. In order that $aba$ is not an overlap, $b\neq a$
is necessary. Similarly it can be proved that $d\neq c$ and $f\neq e$.

Only two types of morphisms satisfy the listed properties:

$\varphi_{1}:a_{1}\longrightarrow 12,a_{2}\longrightarrow
23,a_{3}\longrightarrow 31$;

$\varphi_{2}:a_{1}\longrightarrow 13,a_{2}\longrightarrow
21,a_{3}\longrightarrow 32$.

Let us now show that $\varphi_{1}$ and $\varphi_{2}$ are not overlap-free.

  1. 1)

$\varphi_{1}(a_{1}a_{3}a_{2}a_{1}a_{3}a_{2})=123123123123$ contains a cube
and, consequently, an overlap.

  2. 2)

$\varphi_{2}(a_{1}a_{2}a_{3}a_{1}a_{2}a_{3})=132132132132$ contains a cube
and, consequently, an overlap.

Proposition 2: Over the ternary alphabet there are no uniform overlap-free
morphisms with rank 3.

Let there be a weakly squarefree Thue morphism $\varphi$ with rank 3. The
morphism $\varphi$ has a fixed point, therefore, image of one of the letters
begins with this letter. For example, let $\varphi(1)$ begin with 1. Lemma
(24) implies that $\varphi(1)=12u$ or $\varphi(1)=13u$; these cases are
equivalent, let us consider the first one.

Lemma (25) implies that $\varphi(1)=121$. Therefore, the canonical fragment
that begins with 2 can not have 2 nor 1 in its midde. As a consequence,
$\varphi(a_{2})=232$. Similarly, $\varphi(a_{3})=313$. As a result,

$\varphi(1)=121$

$\varphi(a_{2})=232$

$\varphi(a_{3})=313$.

However, $\varphi(a_{3}1a_{2})=31\,3\,12\,12\,3\,2$ contains a weak square.

Finally, the proposition is proved.

Proposition 3: Over the ternary alphabet there are no uniform overlap-free
morphisms with rank 4.

Let there be a weakly squarefree Thue morphism $\varphi$ with rank 4.
Similarly to the previous proposition, only the case $\varphi(1)=12mn$ may be
considered. This time, by lemma (25), $\varphi(1)=1231$.

It is easy to see that $\varphi(a_{2})$ is equal to 2132 or to 2312;
$\varphi(a_{3})$ is equal to 3123 or to 3213.

The case $\varphi(a_{2})=2312$ is impossible:
$\varphi(1a_{2})=1\,2\,31\,2\,31\,2$ contains an overlap. Therefore,
$\varphi(a_{2})=2132$. Let us notice that now $\varphi(a_{3})=3213$ is
impossible, because $\varphi(a_{3}a_{2})=3\,21\,3\,21\,3\,2$ contains an
overlap.

As a result, we have the only possible morphism:

$\varphi(1)=1231$

$\varphi(a_{2})=2132$

$\varphi(a_{3})=3123$.

However, in this case $\varphi(a_{3}1)=3\,1\,23\,1\,23\,1$ contains an
overlap.

As a result, the cases of ranks $2$, $3$, $4$ are considered, and the theorem
is proved.

Lemma (26): Over the binary alphabet there are no cubefree and weakly
squarefree words of length greater than 5.

Indeed, if the word is weakly squarefree, that it does not contain any squares
of letters. It means that after the letter 1 it is always 0, and after 0 it is
always 1.

As a result, when the length is equal to 6, we will have a cube 101010 or
010101.

Theorem 7: There are no weakly squarefree Thue morphisms over the binary
alphabet.

Let there be a weakly squarefree Thue morphism $\varphi$ over the binary
alphabet. It has a fixed point $A=\varphi^{\infty}(a)$. Let us denote the
sequence that generates this fixed point by $A_{n}$.

The limit of $|A_{n}|$ is equal to infinity. This implies that at some point
$|A_{N}|$ will be greater than 6.

The word $a$ is weakly squarefree and overlap-free. However, a word $A_{N}$
contains a weak square or an overlap. Therefore, $\varphi$ is not weakly
squarefree or cannot be viewed as a Thue morphism.

##  8 Weak squarefreeness

Theorem 8: A cyclic squarefree morphism over the ternary alphabet is always
weakly squarefree.

To prove this theorem we need a number of lemmas.

Lemma (27): If a squarefree morphism is applied to a word and if the image of
this word contains a weak square, then the original word contains a square.

Indeed, a word containing a weak square contains a square. However, if
squarefree morphism is applied to a squarefree word, then the image must be
squarefree, but it is not.

Lemma (28): If the morphism $\varphi$ is cyclic and squarefree, then for each
letter $a\in\mathfrak{A}$ the first and the last letters of $\varphi(a)$ are
equal.

Let there be $a\in\mathfrak{A}$ such that its image begins with the letter $x$
and ends with the letter $y$. Arising from the properties of the ternary
alphabet, $y$ is equal to $x\oplus 1$ or $x\ominus 1$.

Let us consider the case when $y=x\oplus 1$. As long as the morphism $\varphi$
is cyclic, the image of $a\oplus 1$ begins with the letter $y$. Therefore, the
image of a squarefree word $\varphi(a(a\oplus 1))$ contains a square.

On the other hand, $\varphi$ is squarefree.

Lemma (29): If the morphism $\varphi$ is squarefree and cyclic, then the image
of a weakly squarefree word cannot contain a square $W\\!W$ such as $|W\\!|$
is not divisible by the rank of the morphism $\varphi$.

Let us denote the rank of the morphism $\varphi$ by $L$.

Let the image of a weakly squarefree word contain such square. Then $|W\\!|$
can be greater or lower than $L$. Let us consider these cases separately.

  1. 1)

If $|W\\!|<L$, then the square $W\\!W\\!$ can be covered with three successive
canonical fragments. Indeed, if this square cannot be covered with three
canonical fragments, then its length must exceed the length of two canonical
fragments, which is equal to $2L$. As a consequence, we have $2|W\\!|>2L$
$\Longrightarrow$ $|W\\!|>L$. Hovewer, we consider the case when $|W\\!|<L$.

Let us now notice that if a word has the length lower or equal to 3, then weak
squarefreeness implies squarefreeness. As long as the morphism $\varphi$ is
squarefree, the image of a weakly squarefree word of length 3 can not contain
the square $W\\!W\\!$, which contradicts the assumption.

  2. 2)

Let now $|W\\!|$ be greater than $L$. We are going to show that the increasing
and decreasing on the canonical fragment is equivalent to the increasing and
decreasing on a shift of the canonical fragment. We need to prove that:

$\exists h:\ \ \forall\,i=\overline{1,L-1}\ \ \forall\,a\in A$

$\bigl{(}\varphi(a)\bigr{)}[i+1]=\bigl{(}\varphi(a)\bigr{)}[i]\oplus 1\ \
\Longrightarrow$

$\Longrightarrow\ \ \bigl{(}\varphi(a)\bigr{)}[(i+h+1)\ \mathrm{mod}\
L]=\bigl{(}\varphi(a)\bigr{)}[(i+h)\ \mathrm{mod}\ L]\oplus 1$;

and, similarly,

$\bigl{(}\varphi(a)\bigr{)}[i+1]=\bigl{(}\varphi(a)\bigr{)}[i]\ominus 1\ \
\Longrightarrow$

$\Longrightarrow\ \ \bigl{(}\varphi(a)\bigr{)}[(i+h+1)\ \mathrm{mod}\
L]=\bigl{(}\varphi(a)\bigr{)}[(i+h)\ \mathrm{mod}\ L]\ominus 1$.

(in other words, in the canonical fragment the relation between two letters

is equivalent to the relation between the letters that are shifted by $h$
positions)

(by $U[p]$ we denote the $p$–th letter of the word $U$)

To prove lemma it is sufficient to provide the $h$ number. Let $h$ be equal to
$(|W\\!|\ \mathrm{mod}\ L)$.

Let us denote the square $W\\!W$ by $W_{1}W_{2}$, $W_{1}=W_{2}=W\\!$. And let
us consider the relation between $i$–th and $i+1$–th letters of the canonical
fragment. Let

$\bigl{(}\varphi(a_{j})\bigr{)}[i+1]=\bigl{(}\varphi(a_{j})\bigr{)}[i]\oplus
1$.

As long as $|W_{1}|>L$, for each $i$ it is true that $i$–th and $i+1$–th
letters of some canonical fragment will be successive in $W_{1}$ or $W_{2}$.
In other words,

$\exists\,j,k:\ \ W_{1}[k]\equiv\bigl{(}\varphi(a_{j})\bigr{)}[i],\ \
W_{1}[k+1]\equiv\bigl{(}\varphi(a_{j})\bigr{)}[i+1]$;

$W_{1}[k+1]=W_{1}[k]\oplus 1$.

Furthermore, if $k$–th and $k+1$–th letters of the word $W_{2}$ belong to one
canonical fragment, then they have the same relation:
$W_{2}[k+1]=W_{2}[k]\oplus 1$. However, the positions of $W_{2}[k]$ and
$W_{2}[k]$ in the canonical fragment will be different from $i$ and $i+1$.

Finally, this difference will be equal to the remainder of the division
$|W\\!|$ by $L$ — which is equal to $h$. We have:

$\bigl{(}\varphi(a_{m})\bigr{)}[(i+h+1)\ \mathrm{mod}\
L]=\bigl{(}\varphi(a_{m})\bigr{)}[(i+h)\ \mathrm{mod}\ L]\oplus 1$.

(we need the eternal $\mathrm{mod}\ L$ in case the numbers

$i$ or $i+h$ are greater than $L$)

Now let us notice that the relations of the form $\oplus 1\ /\ \ominus 1$ on
the same positions take place in all the canonical fragments of the cyclic
morphism. Therefore, if what we need is true in the canonical fragments
$\varphi(a_{j})$ or $\varphi(a_{m})$, then it is true in the canonical
fragment $\varphi(a)$ for any $a$.

The preservation of the increasing / decreasing for the shift is shown.

Now we know that the relation between $i$–th letter of the canonical fragment
and the next one is the same for the $(i+h)$–th letter of the canonical
fragment and the next one. So, it is the same for $(i+2h)$, $(i+3h)$, …,
$(i+kh)$–th letters of the canonical fragment and the next ones.

In other words, it is sufficient to define the segment of the first
$h^{\prime}$ letters of the canonical fragment to know that on other segments
of this length the increasing / decreasing is similar to the increasing /
decreasing on the first one.

From the number theory, $h^{\prime}$ is equal to the greatest common divisor
of $h$ and $L$. We know that $h<L$, so $h^{\prime}$ is the divisor of $L$
lower than $L$.

Now the canonical fragment is divided into segments of length $h^{\prime}$,
and monotony on all this segments is similar. Furthermore, the next segment is
always connected to the previous one with one relation $\oplus 1\ /\ \ominus
1$, which is also similar everywhere. It is easy to determine this relation by
the first, $h^{\prime}$–th and $h^{\prime}+1$–th letters of the canonical
fragment.

Let us only notice that two successive segments can not be equal, because in
this case the image of a letter will contain a square.

Now let us consider the canonical fragment $\varphi(a)$.

     * (a)

Let the canonical fragment be divided into two segments. Let them be equal to
$S$ and $S\oplus 1$. Then the images of two other letters have forms
$f(a^{\prime})=(S\oplus 1)(S\ominus 1)$ and
$\varphi(a^{\prime\prime})=(S\ominus 1)S$. In this case
$\varphi(a^{\prime}aa^{\prime\prime})=(S\oplus 1)(S\ominus 1)S\,(S\oplus
1)(S\ominus 1)S$ contains a square. On the other hand, the morphism $\varphi$
is squarefree.

     * (b)

Let us now have more than two segments — three, at least. Furthermore, let the
next segment always be equal to the previous one increased by 1.

Let us now consider a canonical fragment, and let us now take another fragment
such that the sequence of segments in it continues the sequence of segments in
the first one. It will be another canonical fragment, because the last letter
of the first canonical fragment and the first letter of the second canonical
fragment will be different, and we have the lemma (28).

Then, on the border of two canonical fragments we have

$...\ S(S\oplus 1)(S\ominus 1)\ S(S\oplus 1)(S\ominus 1)\ ...$,

which is a square. On the other hand, the morphism $\varphi$ is squarefree.

The lemma is now proved.

Lemma (30): If the morphism $\varphi$ is squarefree and cyclic, then the image
of any word does not contain any weak squares of the form $aX\\!Xa$, where
$|X|$ is divisible by $L$, and the borders of $X$ are not borders of any
canonical fragment.

We already know that the canonical fragment of a cyclic morphism can be
determined by a letter and its position in the canonical fragment. So, if two
edges and the border between the $X$ words belong to the canonical fragments
$\varphi(a_{i})$, $\varphi(a_{j})$ and $\varphi(a_{k})$, then these borders
lie on the same positions, and the canonical fragments are similar.

It means that the $X$ word ends with the $a$ letter, because the end of $X$
and $a$ have the same positions in similar canonical fragments. Therefore, $X$
also begins with the $a$ letter.

As a result, there is a square $aa$ inside the canonical fragments, which
contradicts squarefreeness of $\varphi$. The lemma is proved.

Finally, if $\varphi$ is a cyclic squarefree morphism, than the square in the
image of a weakly squarefree word can only be the image of a square. Let us
now consider two canonical fragments next to the square. If the square is
weak, then the last letter of the first of these fragment is equal to the
first letter of the second one.

So, these fragments are similar. Consequently, there was a weak square in the
original word, which contradicts the wording.

Corollary: As long as the Leech morphism is cyclic and squarefree, it is also
weakly squarefree.

As a result, the Leech morphism has all the considered properties: it is
cubefree, overlap-free, squarefree and weakly squarefree. It is also cyclic
and has a fixed point.

Remark: There is a weakly squarefree morphism over the binary alphabet:

$\varphi:0\longrightarrow 01,1\longrightarrow 01$.

The norphism $\varphi:0\longrightarrow 01,1\longrightarrow 10$ is not weakly
squarefree: $\varphi(10)$ contains a weak square. The theorem 7 proves that
there are no weakly squarefree Thue morphisms over the binary alphabet.

The theorem is now proved.

##  9 Leech’s morphism and optimal ranks

Theorem 9: Over the ternary alphabet there are exactly 144 unifrom squarefree
morphisms of rank 11; there are no uniform squarefree morphisms with a lower
rank.

This result was obtained using a program written in the Objective Caml
language. In the paper [4] there is a criterion of squarefreeness of an
uniform morphism over the ternary alphabet. The criterion says that for a
morphism to be squarefree it is sufficient to have squarefree images of the
squarefree words of length 3.

Squarefreeness of a word is examined using the function squarefree_check. The
computational complexity of it is equal to $O(n^{2})$, but it is insignificant
for us.

    let squarefree_check str =
      let res = [|true|] in
      let l = String.length str in
        for i=0 to l-2 do (
          for m=1 to (l-i)/2 do (
          if (String.sub str i m = String.sub str (i+m) m)
            then (res.(0) <- false)
          ) done
        ) done;
      res.(0);;

The array res contains the intermediate result, and the line

if (String.sub str i m = String.sub str (i+m) m)

then (res.(0) <\- false)

checks if there is a square of length $2m$ beginning at the $i$–th position.

The array of all the squarefree words of length 11 was created, and the images
of letters were take nfrom this array. Then the squarefreeness check was made,
and if the morphism happened to be squarefree, the images of letters were
printed on the screen.

The source code can be seen in the Appendix.

Proposition: Over the ternary alphabet there are exactly 2 unifrom squarefree
morphisms of rank 11 such that all the other squarefree morphisms of rank 11
can be obtained from them using the natural operations. Namely:

$\varphi_{1}:1\longrightarrow 12131232123,2\longrightarrow
13212321323,3\longrightarrow 13213121323$;

$\varphi_{2}:1\longrightarrow 12313231213,2\longrightarrow
12321231213,3\longrightarrow 23132123213$.

Let us prove this fact. We denote a arbitrary permutation of the set
$\\{1,2,3\\}$ by $\sigma$, and let $\overline{\sigma}$ be the morphism induced
by this permutation. Furthermore, let the inversion — the function that
returns the word in reverse — be denoted by $\iota$.

If the morphism $\varphi$ is uniform and squarefree, then the morphisms
$\iota\circ\varphi$, $\varphi\circ\overline{\sigma}$ and
$\overline{\sigma}\circ\varphi$ are also uniform and squarefree.

For a particular morphism $\varphi$ there are exactly $6\cdot 6=36$ morphisms
of the form $\overline{\sigma_{1}}\circ\varphi\circ\overline{\sigma_{2}}$ and
36 morphisms of the form
$\iota\circ\overline{\sigma_{1}}\circ\varphi\circ\overline{\sigma_{2}}$.

It is shown manually that for two uniform squarefree morphisms of rank 11:

$\varphi_{1}:1\longrightarrow 12131232123,2\longrightarrow
13212321323,3\longrightarrow 13213121323$;

$\varphi_{2}:1\longrightarrow 12313231213,2\longrightarrow
12321231213,3\longrightarrow 23132123213$,

all the other uniform squarefree morphisms of rank 11 have the form
$\overline{\sigma_{1}}\circ\varphi_{i}\circ\overline{\sigma_{2}}$ or
$\iota\circ\overline{\sigma_{1}}\circ\varphi_{i}\circ\overline{\sigma_{2}}$.

Remark: The lower bound for the rank of the squarefree morphisms over the
ternary alphabet is also provided in the article [8].

In the article [8] a morphism obtained by inversion of $\varphi_{2}$, is also
provided. We have to remark that in this article the result is obtained
independently. Here we also list all the morphisms that reach the lower bound
of the rank.

Theorem 10: Over the ternary alphabet there are no cyclic squarefree morphisms
of a rank lower than 13.

The Proposition shows that an uniform squarefree morphism of rank 11 over the
ternary alphabet is not cyclic. For the morphisms of rank 12 we can also list
all the squarefree ones and check their cyclicness.

Theorem 11: Over the ternary alphabet there are no morphisms of a rank lower
than 13 that are squarefree, cubefree and overlap-free at the same time.

In the aricles [6]–[8] the criteria of overlap- and cubefreeness of a morphism
over the ternary alphabet are provided. The author created the programs
similar to those for squarefreeness that prove the given fact.

##  10 Letter combinations in squarefree words

Let two-letter combination be an arbitrary word of length 2. Over the ternary
alphabet there are 6 squarefree two-letter combinations: $ab$, $ac$, $ba$,
$bc$, $ca$ and $cb$. Let us try to answer the following question: can we do
without one of squarefree two-letter combinations while constructing a
squarefree word?

Theorem 12: Over the ternary alphabet a squarefree word of length more than 13
contains all the squarefree two-letter combinations.

Let us prove the theorem. We will try to construct a squarefree word without
the two-letter combination $ab$.

Let us notice that it is impossible to construct a squarefree word of length
more than three using only letters $b$ and $c$. It means that not later than
in the 4–th position there will be an $a$ letter. We know that after the $a$
letter there can be only $c$, and after $b$ or $c$ — any letter but the given
one. Guided by this rules, let us construct all the squarefree words until we
obtain words with squares.

As a result, $bcba\,cbca\,cbaca$ is the longest squarefree word without the
combination $ab$. Its length is equal to thirteen.

The theorem is proved.

Remark: Over a more than three - letter alphabet there are squarefree words of
any length without an arbitrary two-letter combination.

Let us show that there exist squarefree words of any length without the
combination $ab$.

The given alphabet without the letter $a$ is not less than ternary. Therefore,
we can construct squarefree words of any length over it. These words will not
contain the $a$ letter, and, consequently, all the combinations with it.

The remark is proved.

Similarly to the two-letter combinations we will define the three-letter
combinations. A three-letter combination is an arbitrary word of lenth 3. Let
us try to answer the following question: which three-letter combinations are
necessary to exist inside squarefree words?

Theorem 13: Over the ternary alphabet a squarefree word of length more than 36
contains all the squarefree three-letter combinations of different letters (of
the form $abc$).

Let us again try to construct a squarefree word without the combination $abc$.
The theorem 12 implies that not later than in the 12–th position there will be
the two–letter combination $ab$. We know that after it there can be only the
letter $a$. Now let us continue constructing a squarefree word.

As a result, now we know that a squarefree word beginning with $ab$ and not
containing the combination $abc$ can only have forms $abacbcabac..$ or
$abacbcacba..$ . Let us consider these cases separately.

In the first case we always obtain a square:

Now the second case is left.

Let us notice that the only long squarefree word ends with $abacb$. Going back
to the main tree of cases, we can see that from $abacb$ we always obtain words
with squares or the word we are considering.

The longest squarefree word obtained from $abacb$ is $aba\,cbc\,aba\,cbab$
with its length being equal to 13. Adding 13 to the length of the word
$abacb\,cacbac$ we get 24. Finally, before the first $ab$ there can be up to
12 letters.

As a result, we have the upper bound, which is equal to 36.

Proposition: Over the ternary alphabet there are squarefree words of any
length without the three-letter combination $aba$.

Let us provide an example of an infinite squarefree word without the factor
$aba$. The known Thue result [2] which is the infinite word generated by the
morphism

$\varphi:a\longrightarrow abcab,b\longrightarrow acabcb,c\longrightarrow
acbcacb$

does not contain the three-letter combination $cbc$. Indeed, this factor
cannot appear inside the images of the letters nor on their borders.

Furthermore, we provide a squarefree word of length 718 without two three-
letter combinations: $aba$ and $bab$:

abcbacbcacbacabcbacbcacbabcbacbcabcbacabcacbcabcbacbcacbacab
---
cbacbcabcbacabcacbcabcbacbcacbabcbacbcabcbacabcacbcabcbabcac
bacabcbacbcacbacabcbabcacbcabcbacbcacbacabcbacbcabcbacabcacb
cabcbacbcacbacabcbacbcabcbabcacbcabcbacbcacbacabcbabcacbcabc
bacabcacbcabcbabcacbacabcbacbcacbacabcbabcacbcabcbacbcacbaca
bcbacbcabcbacabcacbcabcbacbcacbacabcbacbcabcbabcacbcabcbacbc
acbacabcacbcabcbacbcacbabcbacbcabcbacabcacbcabcbacbcacbacabc
bacbcabcbacabcacbcabcbacbcacbabcbacbcabcbacabcacbcabcbabcacb
acabcbacbcacbacabcbabcacbcabcbacbcacbacabcbacbcabcbacabcacbc
abcbacbcacbacabcbacbcabcbabcacbcabcbacbcacbacabcbabcacbcabcb
acabcacbcabcbabcacbacabcbacbcacbacabcbabcacbcabcbacbcacbacab
cbacbcabcbacabcacbcabcbacbcacbacabcbacbcabcbabcacbcabcbaca

Remark: Over a more than three - letter alphabet there are squarefree words of
any length without an arbitrary three-letter combination.

Indeed, we can construct a squarefree word without the combination $abc$ or
$aba$ just constructing a squarefree word over a not less than ternary
subalphabet without the $a$ letter.

Remark: Finiteness of the trees of cases can be checked using the computer,
but the manual check is more of interest.

##  11 The applications of theory and the results

The theory of non-repeating words found its applications in many branches of
mathematics and other sciences. In the XX century mathematicians Novikov and
Adyan solved the Burnside problem of local finiteness of the variety of
periodical groups.

Furthermore, Max Euwe, who is a mathematician and an ex – world champion in
chess, rediscovered the Thue-Morse sequence and provided the example of an
infinite chess game that cannot be flattened draw. This led to a change to the
rules.

Non-repeating sequences can be applied in the game theory, the number theory,
cryptography, symbol dynamics (the theory of billiards, for example) and even
in genetics. The evidence that combinatorics on words is important is that the
Thue-Morse sequence had been rediscovered several times before the Thue works
were publishid in Europe. Many articles are published in this field these days
as well.

In this work the questions we addressed have been answered. New sets of non-
repeating words and morphisms are obtained. Also, the optimal evaluations of
the ranks of the morphisms were provided.

##  12 References

  * [1]

Axel Thue, Uber unendliche Zeichenreihen; Norske Vid. Selsk Skr. I Mat.-Nat.
Kl.; Christiania; 1906 — 1–22.

  * [2]

Axel Thue, Uber die gegenseitige Lage gleicher Teile gewisser Zeichenreihen;
Norske Vid. Skrifter I Mat.-Nat. Kl.; Christiania; 1912 — 1–67.

  * [3]

John Leech, A problem on strings of beads; Math. Gazette 41; 1957 — 277–278.

  * [4]

Max Сrochemore, Sharp characterizations of squarefree morphisms; Theor.
Comput. Sci.; 18 (1982) — 221–226.

  * [5]

Jean Berstel, Some recent results on squarefree words; Lecture Notes in
Computer Science; 166(1984) — 14–25.

  * [6]

G. Richomme, F. Wlazinski, Existance of finite test-sets for k-power-freeness
of uniform morphisms — arxiv.org/pdf/cs/0512051.

  * [7]

Christopher R. Tompkins, Overlap-free Morphisms; University of South Carolina;
Mathematics; 2009 — 1–67.

  * [8]

F. Brandenburg, Uniformly growing k-th powerfree homomorphisms; Theor. Comput.
Sci.; 23(1983) — 69–82.

##  13 Appendix (A). The source code

Let us provide the source code of the program, obtaining all the squarefree
morphisms of rank 11.

    (* Objective Caml v 4.00.1 *)
    let int_of_bool b = if b=true then 1 else 0;;

    let squarefree_check str =
      let res = [|true|] in
      let l = String.length str in
        for i=0 to l-2 do (
          for m=1 to (l-i)/2 do (
          if (String.sub str i m = String.sub str (i+m) m)
            then (res.(0) <- false)
          ) done
        ) done;
      res.(0);;

    let printl lis = List.iter (fun x -> print_string (x^" ")) lis;;
    let extend str = [str^"1"; str^"2"; str^"3"];;
    let step lis = List.flatten (List.map extend lis);;
    let rec nextend n = if n=0 then [""] else step (nextend (n-1));;
      (* Generating the list of all the words of length n *)

    let main = Array.of_list (List.filter squarefree_check (nextend 11));;
      (* The array of all the squarefree words of length 11 *)

    let morphism_application str q w e =
      let apply_morphism t = match t with
        ’1’ -> main.(q) |
        ’2’ -> main.(w) |
        ’3’ -> main.(e) |
        q -> "" in
      let to_flatten = List.map apply_morphism str in
      String.concat "" to_flatten;;
      (* Function  applying a morphism to a word; the images of the letters are taken from the array *)

    let ternary = [[’1’;’2’;’1’];[’1’;’2’;’3’];[’1’;’3’;’1’];[’1’;’3’;’2’];
      [’2’;’1’;’2’];[’2’;’1’;’3’];[’2’;’3’;’2’];[’2’;’3’;’1’];
      [’3’;’1’;’3’];[’3’;’1’;’2’];[’3’;’2’;’3’];[’3’;’2’;’1’]];;
      (* All the squarefree words of length 3 over the ternary alphabet *)

    let morphism_check q w e =
      let after_apply = List.filter squarefree_check
        (List.map (fun x -> morphism_application x q w e) ternary) in
      if (List.length after_apply) = 12
        then Printf.printf "%s %s %s \n" main.(q) main.(w) main.(e)
        else ();;
      (* The check of the squarefreeness of the morphism *)

    let l = Array.length main;;
    for q=0 to l-1 do (
      for w=0 to l-1 do (
        for e=0 to l-1 do (
          morphism_check q w e;
      ) done  ) done ) done;;

##  14 Appendix (B). Squarefree morphisms of Rank 11

Let us provide the list of squarefree morphisms of rank 11 obtained using the
written program.

$\varphi(1)$ $\varphi(2)$ $\varphi(3)$ $\varphi(1)$ $\varphi(2)$ $\varphi(3)$
12131232123 13212321323 13213121323 12131232123 13213121323 13212321323
12132123213 12132313213 12321231323 12132123213 12321231323 12132313213
12132313213 12132123213 12321231323 12132313213 12321231323 12132123213
12312131232 12313231232 13121323132 12312131232 13121323132 12313231232
12313231213 12321231213 23132123213 12313231213 12321312132 12321323132
12313231213 12321323132 12321312132 12313231213 23132123213 12321231213
12313231232 12312131232 13121323132 12313231232 13121323132 12312131232
12321231213 12313231213 23132123213 12321231213 23132123213 12313231213
12321231323 12132123213 12132313213 12321231323 12132313213 12132123213
12321312132 12313231213 12321323132 12321312132 12321323132 12313231213
12321312132 31213123132 31232123132 12321312132 31232123132 31213123132
12321323132 12313231213 12321312132 12321323132 12321312132 12313231213
13121323132 12312131232 12313231232 13121323132 12313231232 12312131232
13123132312 13123212312 13231321232 13123132312 13231321232 13123212312
13123212312 13123132312 13231321232 13123212312 13231321232 13123132312
13212321312 13231213123 13231232123 13212321312 13231232123 13231213123
13212321312 13231321312 32123132312 13212321312 32123132312 13231321312
13212321323 12131232123 13213121323 13212321323 13213121323 12131232123
13213121323 12131232123 13212321323 13213121323 13212321323 12131232123
13231213123 13212321312 13231232123 13231213123 13231232123 13212321312
13231213123 21312132123 21323132123 13231213123 21323132123 21312132123
13231232123 13212321312 13231213123 13231232123 13231213123 13212321312
13231321232 13123132312 13123212312 13231321232 13123212312 13123132312
13231321312 13212321312 32123132312 13231321312 32123132312 13212321312
21231213123 21231323123 21312132313 21231213123 21312132313 21231323123
21231323123 21231213123 21312132313 21231323123 21312132313 21231213123
21232131213 23121312313 23123212313 21232131213 23123212313 23121312313
21312132123 13231213123 21323132123 21312132123 21323132123 13231213123
21312132313 21231213123 21231323123 21312132313 21231323123 21231213123
21312313231 21312321231 21323132123 21312313231 21323132123 21312321231
21312321231 21312313231 21323132123 21312321231 21323132123 21312313231
21312321231 32123213231 32131213231 21312321231 32131213231 32123213231
21321232131 21323132131 23212313231 21321232131 23212313231 21323132131
21323132123 13231213123 21312132123 21323132123 21312132123 13231213123
21323132123 21312313231 21312321231 21323132123 21312321231 21312313231
21323132131 21321232131 23212313231 21323132131 23212313231 21321232131
23121312313 21232131213 23123212313 23121312313 23123212313 21232131213
23121312321 23132123213 23132131213 23121312321 23132131213 23132123213
23121312321 23132312321 31213231321 23121312321 31213231321 23132312321
23123212313 21232131213 23121312313 23123212313 23121312313 21232131213
23132123213 12313231213 12321231213 23132123213 12321231213 12313231213
23132123213 23121312321 23132131213 23132123213 23132131213 23121312321
23132131213 23121312321 23132123213 23132131213 23132123213 23121312321
23132312131 23213121321 23213231321 23132312131 23213231321 23213121321
23132312321 23121312321 31213231321 23132312321 31213231321 23121312321
23212313231 21321232131 21323132131 23212313231 21323132131 21321232131
23213121321 23132312131 23213231321 23213121321 23213231321 23132312131
23213231321 23132312131 23213121321 23213231321 23213121321 23132312131

$\varphi(1)$ $\varphi(2)$ $\varphi(3)$ $\varphi(1)$ $\varphi(2)$ $\varphi(3)$
31213123132 12321312132 31232123132 31213123132 31232123132 12321312132
31213123212 31321232132 31321312132 31213123212 31321312132 31321232132
31213212321 31213231321 31232123132 31213212321 31232123132 31213231321
31213231321 23121312321 23132312321 31213231321 23132312321 23121312321
31213231321 31213212321 31232123132 31213231321 31232123132 31213212321
31231323121 31232123121 32313212321 31231323121 32313212321 31232123121
31232123121 31231323121 32313212321 31232123121 32313212321 31231323121
31232123132 12321312132 31213123132 31232123132 31213123132 12321312132
31232123132 31213212321 31213231321 31232123132 31213231321 31213212321
31321232132 31213123212 31321312132 31321232132 31321312132 31213123212
31321312132 31213123212 31321232132 31321312132 31321232132 31213123212
31323121312 32131213212 32132313212 31323121312 32132313212 32131213212
32123121312 32123132312 32131213231 32123121312 32131213231 32123132312
32123132312 13212321312 13231321312 32123132312 13231321312 13212321312
32123132312 32123121312 32131213231 32123132312 32131213231 32123121312
32123213121 32312131231 32312321231 32123213121 32312321231 32312131231
32123213231 21312321231 32131213231 32123213231 32131213231 21312321231
32131213212 31323121312 32132313212 32131213212 32132313212 31323121312
32131213231 21312321231 32123213231 32131213231 32123121312 32123132312
32131213231 32123132312 32123121312 32131213231 32123213231 21312321231
32132313212 31323121312 32131213212 32132313212 32131213212 31323121312
32312131231 32123213121 32312321231 32312131231 32312321231 32123213121
32312321231 32123213121 32312131231 32312321231 32312131231 32123213121
32313212321 31231323121 31232123121 32313212321 31232123121 31231323121