# Complement Avoidance in Binary Words

James Currie, Pascal Ochem, Narad Rampersad, Jeffrey Shallit

► To cite this version:

James Currie, Pascal Ochem, Narad Rampersad, Jeffrey Shallit. Complement Avoidance in Binary
Words. 2023. lirmm-03799678

HAL Id: lirmm-03799678

https://hal-lirmm.ccsd.cnrs.fr/lirmm-03799678

Preprint submitted on 17 Oct 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Complement Avoidance in Binary Words

James Currie<fnref n="1" />

L'ubomíra Dvořáková<fnref n="2" />

Pascal Ochem<fnref n="3" />

Daniela Opočenská<fnref n="4" />

Narad Rampersad<fnref n="5" />

Jeffrey Shallit<fnref n="6" />

March 14, 2023

## Abstract

The complement $\bar{x}$ of a binary word $x$ is obtained by changing each 0 in $x$ to 1 and vice versa. We study infinite binary words $w$ that avoid sufficiently large complementary factors; that is, if $x$ is a factor of $w$, then $\bar{x}$ is not a factor of $w$. In particular, we classify such words according to their critical exponents.

## 1 Introduction

Let $x$ be a finite nonempty binary word. We write $\bar{x}$ for the complementary word, image of the morphism that maps $0 \to 1$ and $1 \to 0$, and we write $x^R$ for the reversal (mirror image) of $x$. We say $y$ is a factor of a (one-sided) infinite word $w$ if $w = xyz$ for a finite word $x$ and an infinite word $z$. In this paper, we are interested in the construction of and properties of infinite binary words $w$ avoiding complementary factors: that is, if $x$ is a nonempty factor of $w$, then $\bar{x}$ is not. This is not a new notion; for example, complement avoidance in de Bruijn words was studied by Sawada et al. [20].

Evidently it is impossible for an infinite word to avoid complementary factors of *all* lengths, except in the trivial cases $0^\omega = 000\cdots$ and $1^\omega = 111\cdots$. A natural question then poses itself: are there such infinite words if the set of exceptions is restricted in some way, say by length or by cardinality? And what is the repetition threshold of such infinite words? We now turn to repetitions.

<footnote n="1">¹Department of Math/Stats, University of Winnipeg, 515 Portage Ave., Winnipeg, MB, R3B 2E9, Canada; e-mail j.currie@uwinnipeg.ca.</footnote>

<footnote n="2">²FNSPE Czech Technical University, Prague, Czech Republic; e-mail lubomira.dvorakova@fjfi.cvut.cz.</footnote>

<footnote n="3">³LIRMM, CNRS, Université de Montpellier, France; e-mail ochem@lirmm.fr.</footnote>

<footnote n="4">⁴FNSPE Czech Technical University, Prague, Czech Republic; e-mail opocedan@fjfi.cvut.cz.</footnote>

<footnote n="5">⁵Department of Math/Stats, University of Winnipeg, 515 Portage Ave., Winnipeg, MB, R3B 2E9, Canada; e-mail n.rampersad@uwinnipeg.ca.</footnote>

<footnote n="6">⁶School of Computer Science, University of Waterloo, Waterloo, ON N2L 3G1, Canada; e-mail shallit@uwaterloo.ca.</footnote>
We say that a finite word $w = w[1..n]$ has period $p \ge 1$ if $w[i] = w[i+p]$ for $1 \le i \le n-p$. The smallest period of a word $w$ is called the period, and we write it as $\text{per}(w)$. The exponent of a finite word $w$, written $\text{exp}(w)$ is defined to be $|w|/\text{per}(w)$. For a real number $\alpha$, we say a word (finite or infinite) is $\alpha$-free if the exponent of all its nonempty factors is $< \alpha$. We say a word is $\alpha^+$-free if the exponent of all its nonempty factors is $\le \alpha$. A word that is 2-free is also called squarefree, and a word that is 3-free is also called cubefree. A word that is $2^+$-free is also called overlap-free.

The critical exponent of a finite or infinite word $x$ is the supremum, over all nonempty finite factors $w$ of $x$, of $\text{exp}(w)$; it is written $\text{ce}(x)$. The repetition threshold for a language $L$ of infinite words is defined to be the infimum, over all $x \in L$, of $\text{ce}(x)$.

The repetition thresholds for various classes of words have been studied extensively. To name just a few classes, Dejean [8] determined the repetition threshold for all words over a 3-letter alphabet, and conjectured its value for larger alphabets. Her conjecture attracted a lot of attention, and was finally resolved by Rao [18] and Currie and Rampersad [7], independently.

Other classes that have been studied include the Sturmian words, studied by Carpi and de Luca [4, Prop. 15]; the palindromes, studied in [22]; the rich words, studied by Currie et al. [5]; the balanced words, studied by Rampersad et al. [17] and Dvořáková et al. [11]; and the complementary symmetric Rote words, studied by Dvořáková et al. [10]. Other related works include [13, 1, 12, 19, 16].

In this paper we study the repetition threshold for two classes of infinite words:

* $\text{CAL}_\ell$, the binary words for which there is no length-$\ell$ word $x$ such that both $x$ and $\bar{x}$ appear as factors;

* $\text{CAN}_n$, the binary words for which there are at most $n$ distinct words $x$ such that both $x$ and $\bar{x}$ appear as factors.

It turns out that there is an interesting and subtle hierarchy, depending on the values of $\ell$ and $n$.

Our work is very similar in flavor to that of [21], which found a similar hierarchy concerning critical exponents and sizes of squares avoided. The hierarchy for complementary factors, as we will see, however, is significantly more complex.

We will need the following famous infinite words.

* The Fibonacci word $\mathbf{f} = 0100101001001010010100100\cdots$, fixed point of the morphism $0 \to 01, 1 \to 0$. See, for example, [3].

* The word $\mathbf{p} = 0121021010210121010210121\cdots$, fixed point of the morphism $\varphi$ sending $0 \to 01, 1 \to 21, 2 \to 0$. This is sequence A287072 in the OEIS. Its properties were recently studied in [6].

The paper is organized as follows. In Section 2, we introduce the class $\text{CAL}_\ell$ mentioned above and we establish the hierarchy alluded to previously. Section 3 does the same thing.
for the class CAN$_n$. In both cases we need some critical exponent calculations, which are carried out in Section 4. Finally, in Section 5 we study finite words avoiding complementary factors and determine under what conditions there are exponentially many such words.

## 2 The class CAL$_ℓ$

In this section, we investigate the repetition threshold for the class CAL$_ℓ$, the binary words $\mathbf{w}$ with the property that if $x$ is a length-$ℓ$ factor of $\mathbf{w}$, then $\bar{x}$ is not. We will need two additional morphisms: the Thue-Morse morphism $\mu$, which maps $0 \to 01$ and $1 \to 10$, and the morphism $\psi$, defined as follows:

$$ 
\begin{array}{l}
0 \to 011001 \\
1 \to 0 \\
2 \to 01101.
\end{array}
$$

**Lemma 1.** Suppose $\mathbf{x}$ is an infinite binary word avoiding $(7/3)$-powers. Then $\mathbf{x}$ contains infinitely many (and hence, arbitrarily large) complementary factors.

*Proof.* By a result of Karhumäki and Shallit [14], every infinite binary word avoiding $e$-powers for $e \le \frac{7}{3}$ contains $\mu^n(0)$ as a factor for all $n \ge 1$. Such a word is of the form $\mu^{n-1}(01) = \mu^{n-1}(0)\mu^{n-1}(1)$, and these two terms are complementary factors of length $2^{n-1}$. $\square$

By Lemma 1, the lower limit on the repetition threshold is $\frac{7}{3}$. For $\ell = 1$ the only such words are $0^\omega$ and $1^\omega$. For $\ell = 2$ the only such words are $0^\omega, 1^\omega, 10^\omega$, and $01^\omega$. Larger $\ell$ are handled in Theorem 3 below, but to prove it we first need to provide some terminology and a lemma from [15]. A morphism $f: \Sigma^* \to \Delta^*$ is called *q-uniform* if $|f(a)| = q$ for all $a \in \Sigma$, and is called *synchronizing* if for all $a, b, c \in \Sigma$ and $u, v \in \Delta^*$, if $f(ab) = uf(c)v$, then either $u = \varepsilon$ and $a = c$, or $v = \varepsilon$ and $b = c$. The following result is quoted almost verbatim from [15, Lemma 23]:

**Lemma 2.** Let $a, b \in \mathbb{R}$ satisfy $1 < a < b$. Let $\alpha \in \{a, a^+\}$ and $\beta \in \{b, b^+\}$. Let $h: \Sigma^* \to \Delta^*$ be a synchronizing q-uniform morphism. Set

$$ t = \max \left( \frac{2b}{b-a}, \frac{2(q-1)(2b-1)}{q(b-1)} \right). $$

If $h(w)$ is $\beta$-free for every $\alpha$-free word $w$ with $|w| \le t$, then $h(z)$ is $\beta$-free for every $\alpha$-free word $z \in \Sigma^*$.

We will use this lemma as follows: through an exhaustive search, we find an appropriate uniform morphism from $\{0, 1, 2\}^* \to \{0, 1\}^*$, and then we apply this morphism to an arbitrary ternary squarefree word. Then we use the fact that there are uncountably many infinite ternary squarefree words, and exponentially many finite ternary squarefree words [23].

We are now ready to state and prove our result on avoiding complementary factors.
**Theorem 3.** There exists an infinite $\beta^+$-free binary word containing no complementary factors of length $\ge \ell$, for the following pairs $(\ell, \beta)$. Moreover, this list of pairs is optimal.

(a) $(3, 2 + \alpha)$, where $\alpha = (1 + \sqrt{5})/2$.

(b) $(5, 3)$

(c) $(7, \frac{8}{3})$

(d) $(8, \frac{5}{2})$

(e) $(11, \gamma')$, where $\gamma' \doteq 2.4808627161472369$ is the critical exponent of $\mathbf{p}$.

(f) $(13, \frac{7}{3})$.

*Proof.*

(a) $(3, 2 + \alpha)$ is achieved by any Sturmian word $\mathbf{x}$ with slope $[0, 3, 1, 1, 1, 1, \dots] = (5 - \sqrt{5})/10$. As is well-known, a Sturmian word has exactly $n+1$ factors of length $n$, and these factors are independent of the intercept of the Sturmian word. For intercept 0, the first 6 symbols are 001000, and so the four factors of $\mathbf{x}$ of length 3 are 001, 010, 100, 000, and no complement of these words appears as a factor of $\mathbf{x}$.

On the other hand, we know from the proof of Proposition 15 of [4] that the critical exponent of $\mathbf{x}$ is $2 + \alpha$. Thus, since we can choose the intercept of a Sturmian word to be any real in $[0, 1]$, there are uncountably many binary words in $\mathrm{CAL}_3$ with critical exponent $2 + \alpha$.

This is best possible, as shown in Theorem 16.

(b) $(5, 3)$ is achieved by applying the 17-uniform morphism $h_1$ defined by

$$ 
\begin{array}{l}
0 \to 01000101000101001 \\
1 \to 01000101000100100 \\
2 \to 01000101000100010,
\end{array}
$$

to any ternary squarefree word $\mathbf{w}$. It is easy, by checking all squarefree words of length 5, to ensure that $h_1(\mathbf{w})$ contains no complementary factors of length $\ge 6$. To verify the $3^+$-freeness of these words, we use Lemma 2 with $\alpha = 2$, $\beta = 3^+$, $q = 17$, $t = 6$, and check that the morphism is indeed synchronizing and that the image of every ternary squarefree word of length $\le 6$ is $3^+$-free. This gives uncountably many infinite binary words and exponentially many finite binary words with the desired avoidance property.

We use this same technique to verify the $\beta^+$-freeness of every word in this paper that is obtained with a uniform morphism.

To see that this result is optimal, backtracking easily shows that the longest word that contains no complementary factors of length $\ge 6$ and no cubes is of length 50, and one example is

00101001001101001001101001101001001101001101001001.
(c) $(7, \frac{8}{3})$ is achieved by applying the 36-uniform morphism

$$ 
\begin{aligned}
0 &\to 001001010011001010010011001001010011 \\
1 &\to 001001010010011001010011001010010011 \\
2 &\to 001001010010011001001010011001010011,
\end{aligned}
$$

to any ternary squarefree word. This gives uncountably many infinite binary words and exponentially many finite binary words.

The longest word that contains no complementary factors of length $\ge 7$ and no $\frac{8}{3}$-powers is of length 51 and one example is

$$ 001001100100110010100110010011001010011001010010100. $$

(d) $(8, \frac{5}{2})$ is achieved by applying the morphism $\xi$, defined as follows

$$ 
\begin{aligned}
0 &\to 01 \\
1 &\to 0110 \\
2 &\to 1,
\end{aligned}
$$

to the infinite word $\mathbf{p}$ mentioned above.

The proof that the critical exponent of $\xi(\mathbf{p})$ is $5/2$ is given in Section 4 starting from Section 4.6.

The longest binary word containing no complementary factors of length $\ge 10$ and no $\frac{5}{2}$-powers is of length 75 and one example is

(e) $(11, \gamma')$ is achieved by the word $\psi(\mathbf{p})$. In Section 4 we show that the critical exponent of $\psi(\mathbf{p})$ is the same as that for $\mathbf{p}$.

For $\ell = 12$ and $e = \gamma'$, the optimality is proved as follows. Let $z = 1001011001$. We can check that $\psi(\mathbf{p})$ avoids $z$ and contains $\bar{z}$, $z^R$, and $\bar{z}^R$. Let $x$ be the prefix of length 40 of $\psi(\mathbf{p})$. A computer check shows that there is no infinite $\frac{5}{2}$-free binary word with $\ell \le 12$ that avoids simultaneously $x, \bar{x}, x^R$, and $\bar{x}^R$.

By symmetry, we consider a bi-infinite $\frac{5}{2}$-free binary word $\mathbf{w}$ with $\ell \le 12$ that contains $x$. Let $X$ be the set containing the complements of the factors of length 12 of $x$. Thus $\ell \le 12$ means that $\mathbf{w}$ avoids $X$.

We compute the set $S$ of factors $f$ such that $efg$ is $\frac{5}{2}$-free and avoids $X$ and $|e| = |f| = |g| = 100$. We compute the set $S'$ of factors of $\psi(\mathbf{p})$ of length 100. We verify that $S = S'$. This means that $\mathbf{w} = \psi(\mathbf{v})$ for some bi-infinite ternary word $\mathbf{v}$. Moreover, by considering the pre-images by $\psi$ of $\mathbf{w} = \psi(\mathbf{v})$ and $\psi(\mathbf{p})$, this implies that $\mathbf{v}$ and $\mathbf{p}$ have the same set of factors of length $100/\max(|\psi(0)|, |\psi(1)|, |\psi(2)|) = 16$. In particular, $\mathbf{v}$ avoids the set $\{00, 11, 22, 20, 212, 0101, 02102, 121012, 01021010, 21021012102\}$ mentioned in [6, Theorem 14].
Also, $\mathbf{v}$ is cube-free since $\mathbf{w}$ is $\frac{5}{2}$-free. By [6, Theorem 14], we know that $\mathbf{v}$ has the same set of factors as $\mathbf{p}$. Thus $\mathbf{w}$ has the same set of factors as $\psi(\mathbf{p})$. So, the critical exponent of $\psi(\mathbf{p})$ is optimal for $\ell = 12$.

(f) $(13, \frac{7}{3})$ is achieved by applying the 69-uniform morphism

$$0 \to 001001100101101001100101100100110100110010110100110010011010011001011$$

$$1 \to 001001100101101001100100110100110010110100110010110010011010011001011$$

$$2 \to 001001100101101001100100110100110010110010011010011001011010011001011$$

to any ternary squarefree word. This gives uncountably many infinite binary words and exponentially many finite binary words.

By Proposition 1, if $e = \frac{7}{3}$, then there are arbitrarily long complemented words.

□

### 3 The class $\text{CAN}_n$

One could also try to minimize the total number $n$ of complemented words that appear. Obviously $n$ has to be even. Recall that $\text{CAN}_n$ denotes the set of binary words $\mathbf{w}$ for which there are at most $n$ distinct words $x$ such that both $x$ and $\bar{x}$ appear as factors of $\mathbf{w}$. For $n = 0$ the only such infinite words are $0^\omega$ and $1^\omega$. For $n = 2$ the only such infinite words are $0^\omega$, $1^\omega$, $01^\omega$, and $10^\omega$. For larger $n$ the situation is summed up in the following theorem:

**Theorem 4.** There exists an infinite $\beta^+$-free binary word having at most $n$ complemented words, for the following pairs $(n, \beta)$. Moreover, this list of pairs is optimal.

(a) $(4, 2 + \alpha)$

(b) $(8, 3)$

(c) $(24, \frac{8}{3})$

(d) $(36, \frac{5}{2})$

(e) $(64, \gamma')$, where $\gamma' = 2.4808627161472369$ is the critical exponent of $\mathbf{p}$.

(f) $(90, \frac{7}{3})$.

*Proof.* For the positive part, we use the same words as in Theorem 3. That is, for every $\beta \in \{2 + \alpha, 3, \frac{8}{3}, \frac{5}{2}, \gamma', \frac{7}{3}\}$, the infinite $\beta^+$-free binary words given in Theorem 3 to achieve the pair $(\ell, \beta)$ also achieve the pair $(n, \beta)$ in Theorem 4. It is not hard to count the complemented factors in such words since their length is less than $\ell$. Now let us consider the negative part.
The morphism $\xi$ is defined by

$$ \xi(0) = 01, \xi(1) = 0110, \xi(2) = 1. \qquad (3) $$

Hence, $\xi(\mathbf{p}) = 0101101011001101100101100110110\dots$

In this section, we compute the critical exponents of $\psi(\mathbf{p})$ and $\xi(\mathbf{p})$ using the lengths of their bispecial factors and their shortest return words.

First recall the definitions of bispecial and return word. Let $\mathbf{u}$ be an infinite word and let $\mathcal{L}(\mathbf{u})$ denote the language of all finite factors of $\mathbf{u}$. Then $w \in \mathcal{L}(\mathbf{u})$ is called *left special* if $aw,bw \in \mathcal{L}(\mathbf{u})$ for two distinct letters $a,b$. A *right special* factor is defined analogously. The factor $w$ is called *bispecial* if it is both left special and right special. A factor $r$ of $\mathbf{u}$ is a *return word* to the factor $w$ if $rw \in \mathcal{L}(\mathbf{u})$ and $rw$ contains $w$ exactly twice – once as a prefix and once as a suffix.

For a word $u$ over an ordered $d$-letter alphabet $\Sigma$, we define its *Parikh vector* to be the vector of number of occurrences of each letter in $u$.

**Theorem 5 ([9]).** Let $\mathbf{u}$ be a uniformly recurrent aperiodic sequence. Let $(w_n)$ be a sequence of all bispecial factors ordered by their length. For every $n \in \mathbb{N}$, let $r_n$ be a shortest return word to $w_n$ in $\mathbf{u}$. Then

$$ \mathrm{ce}(\mathbf{u}) = 1 + \sup_{n \in \mathbb{N}} \left\{ \frac{|w_n|}{|r_n|} \right\}. $$

## 4.1 Bispecial factors in p

In order to determine bispecial factors in $\psi(\mathbf{p})$ and in $\xi(\mathbf{p})$, we need to explore bispecial factors in $\mathbf{p}$. First, we will look at the left special factors (LS). Observing the form of $\varphi$, we can see that every LS has left extensions either $\{0,2\}$, or $\{0,1\}$.

**Observation 6.** Let $v \in \mathcal{L}(\mathbf{p})$, $v \neq \varepsilon$. Then

* $v$ is LS such that $0v, 2v \in \mathcal{L}(\mathbf{p})$ if and only if $v$ is a prefix of $1\varphi(w)$, where $w$ is LS such that $0w, 1w \in \mathcal{L}(\mathbf{p})$.

* $v$ is LS such that $0v, 1v \in \mathcal{L}(\mathbf{p})$ if and only if $v$ is a prefix of $\varphi(w)$, where $w$ is LS such that $0w, 2w \in \mathcal{L}(\mathbf{p})$.

Second, we will look at the right special factors (RS). By the definition of $\varphi$, every RS has right extensions either $\{1,2\}$, or $\{0,2\}$.

**Observation 7.** Let $v \in \mathcal{L}(\mathbf{p})$, $v \neq \varepsilon$. Then

* $v$ is RS such that $v1, v2 \in \mathcal{L}(\mathbf{p})$ if and only if $v$ is a suffix of $\varphi(w)0$, where $w$ is RS such that $w0, w2 \in \mathcal{L}(\mathbf{p})$.

* $v$ is RS such that $v0, v2 \in \mathcal{L}(\mathbf{p})$ if and only if $v$ is a suffix of $\varphi(w)$, where $w$ is RS such that $w1, w2 \in \mathcal{L}(\mathbf{p})$.
It follows from the form of left and right special factors that we have at most 4 possible kinds of nonempty bispecial factors in $\mathbf{p}$. The following statements are obtained when combining Observations 6 and 7.

**Corollary 8.** Let $v \in \mathcal{L}(\mathbf{p}) \setminus \{\varepsilon\}$ be a bispecial factor in $\mathbf{p}$.

1. If $0v, 2v, v0, v2 \in \mathcal{L}(\mathbf{p})$, there exists $w$ such that $v = 1\varphi(w)$ and $0w, 1w, w1, w2 \in \mathcal{L}(\mathbf{p})$.

2. If $0v, 1v, v1, v2 \in \mathcal{L}(\mathbf{p})$, there exists $w$ such that $v = \varphi(w)0$ and $0w, 2w, w0, w2 \in \mathcal{L}(\mathbf{p})$.

3. If $0v, 2v, v1, v2 \in \mathcal{L}(\mathbf{p})$, there exists $w$ such that $v = 1\varphi(w)0$ and $0w, 1w, w0, w2 \in \mathcal{L}(\mathbf{p})$.

4. If $0v, 1v, v0, v2 \in \mathcal{L}(\mathbf{p})$, there exists $w$ such that $v = \varphi(w)$ and $0w, 2w, w1, w2 \in \mathcal{L}(\mathbf{p})$.

It follows from Corollary 8 that all bispecial factors may be constructed starting from the shortest ones in the following way: 1 is the shortest bispecial factor with left extensions $\{0, 2\}$ and right extensions $\{0, 2\}$. Applying the morphism $\varphi$, we obtain the bispecial factor $\varphi(1)0$ with left extensions $\{0, 1\}$ and right extensions $\{1, 2\}$. The second application of $\varphi$ gives us the bispecial factor $1\varphi^2(1)\varphi(0)$ with left extensions $\{0, 2\}$ and right extensions $\{0, 2\}$. This process can be iterated infinitely many times

$$1 \to \varphi(1)0 \to 1\varphi^2(1)\varphi(0) \to \varphi(1)\varphi^3(1)\varphi^2(0)0 \to 1\varphi^2(1)\varphi^4(1)\varphi^3(0)\varphi(0) \to \dots$$

Similarly, when starting with the bispecial factor 10 with left extensions $\{0, 2\}$ and right extensions $\{1, 2\}$, we obtain after application of $\varphi$ the bispecial factor $\varphi(10)$ with left extensions $\{0, 1\}$ and right extensions $\{0, 2\}$. After the second application of $\varphi$, we have the bispecial factor $1\varphi^2(10)0$ with left extensions $\{0, 2\}$ and right extensions $\{1, 2\}$. We continue analogously and complete thus the list of all bispecial factors

$$10 \to \varphi(10) \to 1\varphi^2(10)0 \to \varphi(1)\varphi^3(10)\varphi(0) \to 1\varphi^2(1)\varphi^4(10)\varphi^2(0)0 \to \dots$$

The following statement is an immediate consequence of Corollary 8.

**Proposition 9.** Let $w \in \mathcal{L}(\mathbf{p}) \setminus \{\varepsilon\}$. If $w$ is a bispecial factor, then $w$ has one of the following forms:

$$A) \qquad w_A^{(n)} = 1\varphi^2(1)\varphi^4(1)\cdots\varphi^{2n}(1)\varphi^{2n-1}(0)\varphi^{2n-3}(0)\cdots\varphi(0) \quad \text{for } n \ge 1.$$

If $n = 0$, then we set $w_A^{(0)} = 1$.

The Parikh vector of $w_A^{(n)}$ is the same as of the factor $1\varphi(012)\varphi^3(012)\cdots\varphi^{2n-1}(012)$.

$$B) \qquad w_B^{(n)} = \varphi(1)\varphi^3(1)\cdots\varphi^{2n+1}(1)\varphi^{2n}(0)\varphi^{2n-2}(0)\cdots\varphi^2(0)0 \quad \text{for } n \ge 0.$$

The Parikh vector of $w_B^{(n)}$ is the same as of the factor $012\varphi^2(012)\varphi^4(012)\cdots\varphi^{2n}(012)$.
$$ C) \qquad w_C^{(n)} = 1\varphi^2(1)\varphi^4(1)\cdots\varphi^{2n}(1)\varphi^{2n}(0)\varphi^{2n-2}(0)\cdots\varphi^2(0)0 \quad \text{for } n \ge 0. $$

The Parikh vector of $w_C^{(n)}$ is the same as of the factor $01\varphi^2(01)\varphi^4(01)\cdots\varphi^{2n}(01)$.

$$ D) \qquad w_D^{(n)} = \varphi(1)\varphi^3(1)\cdots\varphi^{2n+1}(1)\varphi^{2n+1}(0)\varphi^{2n-1}(0)\cdots\varphi(0) \quad \text{for } n \ge 0. $$

The Parikh vector of $w_D^{(n)}$ is the same as of the factor $\varphi(01)\varphi^3(01)\cdots\varphi^{2n+1}(01)$.

## 4.2 The shortest return words in p

Let us derive the form of the shortest return words to all bispecial factors in p. We will make use of them when solving the same problem for $\psi(\mathbf{p})$ and $\xi(\mathbf{p})$.

* The return words to $\varepsilon$ are 0, 1, 2.

* The return words to 1 are 12, 102, 10.

* The return words to 10 are 10, 102, 1012. The shortest one is 10 and it is a prefix of all of them.

* The return words to $\varphi(1)0$ are $210 = \varphi(1)0$, $21010$, $2101$. The shortest one is 210 and it is a prefix of all of them.

Using this knowledge and the knowledge of how the bispecial factors can be constructed, we obtain the following observation for the shortest return words:

A) The shortest return words to $w_A^{(0)} = 1$ are 12 and 10. The shortest return word to $w_A^{(n)}$, $n \ge 1$, has the same Parikh vector as the factor $\varphi^{2n-1}(012)$.

B) The shortest return word to $w_B^{(n)}$, $n \ge 0$, has the same Parikh vector as the factor $\varphi^{2n}(012)$.

C) The shortest return word to $w_C^{(n)}$, $n \ge 0$, has the same Parikh vector as the factor $\varphi^{2n}(01)$.

D) The shortest return word to $w_D^{(n)}$, $n \ge 0$, has the same Parikh vector as the factor $\varphi^{2n+1}(01)$.
## 4.3 Bispecial factors in $\psi(\mathbf{p})$

Let us start with some simple observations. If a factor $v \in \mathcal{L}(\psi(\mathbf{p}))$ contains the factor 11001 or 1101, then we are able to write $v = x\psi(w)y$ uniquely, where $w \in \mathcal{L}(\mathbf{p})$, and $x$ (resp., $y$) is a proper suffix (resp., proper prefix) of the image of some letter. Moreover, if $v$ is a bispecial factor in $\psi(\mathbf{p})$, then $w$ is a bispecial factor in $\mathbf{p}$.

*Observation 10.* Let $v \in \mathcal{L}(\psi(\mathbf{p}))$ be a bispecial factor in $\psi(\mathbf{p})$ such that it contains 11001 or 1101. Then one of the following items is true.

1. There exists $w \in \mathcal{L}(\mathbf{p})$ such that $v = 01\psi(w)0110$ and $0w, 2w, w0, w2 \in \mathcal{L}(\mathbf{p})$.

2. There exists $w \in \mathcal{L}(\mathbf{p})$ such that $v = \psi(w)0$ and $0w, 1w, w1, w2 \in \mathcal{L}(\mathbf{p})$.

3. There exists $w \in \mathcal{L}(\mathbf{p})$ such that $v = 01\psi(w)0$ and $0w, 2w, w1, w2 \in \mathcal{L}(\mathbf{p})$.

4. There exists $w \in \mathcal{L}(\mathbf{p})$ such that $v = \psi(w)0110$ and $0w, 1w, w0, w2 \in \mathcal{L}(\mathbf{p})$.

**Corollary 11.** Let $v \in \mathcal{L}(\psi(\mathbf{p}))$. If $v$ is a bispecial factor containing 11001 or 1101, then $v$ has one of the following forms:

$$ \mathcal{A}) \qquad v_A^{(n)} = 01\psi(1\varphi^2(1)\varphi^4(1)\cdots\varphi^{2n}(1)\varphi^{2n-1}(0)\varphi^{2n-3}(0)\cdots\varphi(0))0110 \quad \text{for } n \ge 1. $$

The Parikh vector of $v_A^{(n)}$ is the same as that of the factor

$$ 000111\psi(1\varphi(012)\varphi^3(012)\cdots\varphi^{2n-1}(012)). $$

$$ \mathcal{B}) \qquad v_B^{(n)} = \psi(\varphi(1)\varphi^3(1)\cdots\varphi^{2n+1}(1)\varphi^{2n}(0)\varphi^{2n-2}(0)\cdots\varphi^2(0)0)0 \quad \text{for } n \ge 0. $$

The Parikh vector of $v_B^{(n)}$ is the same as that of the factor

$$ 0\psi(012\varphi^2(012)\varphi^4(012)\cdots\varphi^{2n}(012)). $$

$$ \mathcal{C}) \qquad v_C^{(n)} = 01\psi(1\varphi^2(1)\varphi^4(1)\cdots\varphi^{2n}(1)\varphi^{2n}(0)\varphi^{2n-2}(0)\cdots\varphi^2(0)0)0 \quad \text{for } n \ge 0. $$

The Parikh vector of $v_C^{(n)}$ is the same as of the factor $001\psi(01\varphi^2(01)\varphi^4(01)\cdots\varphi^{2n}(01))$.

$$ \mathcal{D}) \qquad v_D^{(n)} = \psi(\varphi(1)\varphi^3(1)\cdots\varphi^{2n+1}(1)\varphi^{2n+1}(0)\varphi^{2n-1}(0)\cdots\varphi(0))0110 \quad \text{for } n \ge 0. $$

The Parikh vector of $v_D^{(n)}$ is the same as of the factor $0011\psi(\varphi(01)\varphi^3(01)\cdots\varphi^{2n+1}(01))$.
## 4.4 The shortest return words in $\psi(\mathbf{p})$

Knowing the Parikh vectors of the shortest return words to bispecial factors in $\mathbf{p}$ and using the unambiguous reconstruction of $w$ from $\psi(w)$ when $\psi(w)$ contains 11001 or 1101, we obtain the following observation for the shortest return words:

A) The shortest return word $r_A^{(n)}$ to $v_A^{(n)}$, $n \ge 1$, has the same Parikh vector as the factor $\psi(\varphi^{2n-1}(012))$.

B) The shortest return word $r_B^{(n)}$ to $v_B^{(n)}$, $n \ge 0$, has the same Parikh vector as the factor $\psi(\varphi^{2n}(012))$.

C) The shortest return word $r_C^{(n)}$ to $v_C^{(n)}$, $n \ge 0$, has the same Parikh vector as the factor $\psi(\varphi^{2n}(01))$.

D) The shortest return word $r_D^{(n)}$ to $v_D^{(n)}$, $n \ge 0$, has the same Parikh vector as the factor $\psi(\varphi^{2n+1}(01))$.

## 4.5 Critical exponent of $\psi(\mathbf{p})$

Having determined the lengths of bispecial factors and of their shortest return words in $\psi(\mathbf{p})$, we can use Theorem 5 to compute the critical exponent of $\psi(\mathbf{p})$:

$$ \mathrm{ce}(\psi(\mathbf{p})) = 1 + \max\{A, B, C, D, E\} $$

$$ A = \sup \left\{ \frac{|v_A^{(n)}|}{|r_A^{(n)}|} : n \ge 1 \right\} = \sup \left\{ \frac{|000111\psi(1\varphi(012)\varphi^3(012)\cdots\varphi^{2n-1}(012))|}{|\psi(\varphi^{2n-1}(012))|} : n \ge 1 \right\}; $$

$$ B = \sup \left\{ \frac{|v_B^{(n)}|}{|r_B^{(n)}|} : n \ge 0 \right\} = \sup \left\{ \frac{|0\psi(012\varphi^2(012)\varphi^4(012)\cdots\varphi^{2n}(012))|}{|\psi(\varphi^{2n}(012))|} : n \ge 0 \right\}; $$

$$ C = \sup \left\{ \frac{|v_C^{(n)}|}{|r_C^{(n)}|} : n \ge 0 \right\} = \sup \left\{ \frac{|001\psi(01\varphi^2(01)\varphi^4(01)\cdots\varphi^{2n}(01))|}{|\psi(\varphi^{2n}(01))|} : n \ge 0 \right\}; $$

$$ D = \sup \left\{ \frac{|v_D^{(n)}|}{|r_D^{(n)}|} : n \ge 0 \right\} = \sup \left\{ \frac{|0011\psi(\varphi(01)\varphi^3(01)\cdots\varphi^{2n+1}(01))|}{|\psi(\varphi^{2n+1}(01))|} : n \ge 0 \right\}; $$

$$ E = \left\{ \frac{|w|}{|r|} : w \text{ bispecial not containing 11001 or 1101, } r \text{ the shortest return word to } w \right\}. $$

### 4.5.1 Computation of $E$

As summarized in Table 4.5.1, for each bispecial $w$ that does not contain 11001 and 1101 and its shortest return word $r$, we have $\frac{|w|}{|r|} \le \frac{4}{3} \doteq 1.333$, therefore $E = 1 + \frac{1}{3}$.
<table><caption>Table 1: Short bispecial factors w and their return words r</caption><tr><td>w</td><td>0</td><td>1</td><td>01</td><td>10</td><td>101</td><td>010</td><td>0110</td><td>1001</td></tr><tr><td>r</td><td>0</td><td>1</td><td>01</td><td>10</td><td>101</td><td>01011</td><td>011001</td><td>100</td></tr></table>

### 4.5.2 Computation of A and B

If we consider $a_n := |\psi(\varphi^n(012))|$, then we can see that $a_n$ satisfies the recurrence relation $a_{n+1} = 2a_n - a_{n-1} + a_{n-2}$ with initial conditions $a_0 = 12, a_1 = 19$, and $a_2 = 32$.

This recurrence relation may be solved and we obtain

$$a_n = A_1\beta_1^n + B_1\lambda_1^n + C_1\lambda_2^n,$$

where

$$\beta_1 \doteq 1.75488, \quad \lambda_1 \doteq 0.12256 + 0.74486i, \quad \lambda_2 = \overline{\lambda_1}$$

are the roots of the polynomial $t^3 - 2t^2 + t - 1$, and

$$A_1 = \frac{12|\lambda_1|^2 - 38 \operatorname{Re}(\lambda_1) + 32}{|\beta_1 - \lambda_1|^2} \doteq 10.6175;$$

$$B_1 = \frac{12\beta_1\lambda_2 - 19(\beta_1 + \lambda_2) + 32}{(\beta_1 - \lambda_1)(\lambda_2 - \lambda_1)} \doteq 0.6912 - 0.1330i;$$

$$C_1 = \overline{B_1}.$$

Let us first determine

$$A' := \limsup_{n \to +\infty} \frac{|v_A^{(n)}|}{|r_A^{(n)}|} = \limsup_{n \to +\infty} \frac{|000111\psi(1\varphi(012)\varphi^3(012)\cdots\varphi^{2n-1}(012))|}{|\psi(\varphi^{2n-1}(012))|}.$$

We have

$$\begin{align*}
A' &= \limsup_{n \to +\infty} \frac{6 + 1 + \sum_{k=1}^{n} a_{2k-1}}{a_{2n-1}} \\
&= \limsup_{n \to +\infty} \frac{7 + A_1 \sum_{k=1}^{n} \beta_1^{2k-1} + B_1 \sum_{k=1}^{n} \lambda_1^{2k-1} + C_1 \sum_{k=1}^{n} \lambda_2^{2k-1}}{A_1 \beta_1^{2n-1} + B_1 \lambda_1^{2n-1} + C_1 \lambda_2^{2n-1}} \\
&= \lim_{n \to +\infty} \frac{7 + A_1 \beta_1 \frac{\beta_1^{2n-1}}{\beta_1^2-1} + B_1 \lambda_1 \frac{\lambda_1^{2n-1}}{\lambda_1^2-1} + C_1 \lambda_2 \frac{\lambda_2^{2n-1}}{\lambda_2^2-1}}{A_1 \beta_1^{2n-1} + B_1 \lambda_1^{2n-1} + C_1 \lambda_2^{2n-1}} = \frac{\beta_1^2}{\beta_1^2-1} \doteq 2.4809.
\end{align*}$$
Next we will show that $A \le A'$ and thus $A = A'$. We want to show for all $n \ge 1$ that

$$ \frac{7 + A_1 \sum_{k=1}^{n} \beta_1^{2k-1} + B_1 \sum_{k=1}^{n} \lambda_1^{2k-1} + C_1 \sum_{k=1}^{n} \lambda_2^{2k-1}}{A_1 \beta_1^{2n-1} + B_1 \lambda_1^{2n-1} + C_1 \lambda_2^{2n-1}} \le \frac{\beta_1^2}{\beta_1^2 - 1} $$

$$ (\beta_1^2 - 1) \left( 7 + 2 \operatorname{Re} \left( B_1 \lambda_1 \frac{\lambda_1^{2n} - 1}{\lambda_1^2 - 1} \right) \right) + A_1 \beta_1^{2n+1} - A_1 \beta_1 \le \beta_1^2 \operatorname{Re}(B_1 \lambda_1^{2n-1}) + A_1 \beta_1^{2n+1} $$

$$ (\beta_1^2 - 1) \left( 7 + 2 \operatorname{Re} \left( B_1 \lambda_1 \frac{\lambda_1^{2n} - 1}{\lambda_1^2 - 1} \right) \right) \le \beta_1^2 \operatorname{Re}(B_1 \lambda_1^{2n-1}) + A_1 \beta_1. $$

Now, on the one hand, for $n \ge 2$, we have

$$ (\beta_1^2 - 1) \left( 7 + 2 \operatorname{Re} \left( B_1 \lambda_1 \frac{\lambda_1^{2n} - 1}{\lambda_1^2 - 1} \right) \right) \le (\beta_1^2 - 1) \left( 7 + 2 |B_1| |\lambda_1| \frac{|\lambda_1|^{2n} + 1}{|\lambda_1^2 - 1|} \right) \\ \le (\beta_1^2 - 1) \left( 7 + 2 |B_1| |\lambda_1| \frac{|\lambda_1|^4 + 1}{|\lambda_1^2 - 1|} \right). $$

On the other hand,

$$ \begin{aligned} 2\beta_1^2 \operatorname{Re}(B_1 \lambda_1^{2n-1}) + A_1 \beta_1 &\ge A_1 \beta_1 - 2\beta_1^2 |B_1| |\lambda_1|^{2n-1} \\ &\ge A_1 \beta_1 - 2\beta_1^2 |B_1| |\lambda_1|^3. \end{aligned} $$

And if we substitute the values, we get

$$ (\beta_1^2 - 1) \left( 7 + 2|B_1||\lambda_1| \frac{|\lambda_1|^4 + 1}{|\lambda_1^2 - 1|} \right) \le A_1\beta_1 - 2\beta_1^2|B_1||\lambda_1|^3. $$

For $n = 1$, we get $\frac{7+a_1}{a_1} = 1 + \frac{7}{19} < A'$. Therefore

$$ A = A' = \frac{\beta_1^2}{\beta_1^2 - 1}. $$

Next, we will use the same procedure for $B$.

$$ \begin{aligned} B' &:= \limsup_{n \to +\infty} \frac{|v_B^{(n)}|}{|r_B^{(n)}|} \\ &= \limsup_{n \to +\infty} \frac{|0\psi(012\varphi^2(012)\varphi^4(012)\cdots\varphi^{2n}(012))|}{|\psi(\varphi^{2n}(012))|} \\ &= \limsup_{n \to +\infty} \frac{1 + \sum_{k=0}^n a_{2k}}{a_{2n}} \\ &= \limsup_{n \to +\infty} \frac{1 + A_1 \sum_{k=0}^n \beta_1^{2k} + B_1 \sum_{k=0}^n \lambda_1^{2k} + C_1 \sum_{k=0}^n \lambda_2^{2k}}{A_1 \beta_1^{2n} + B_1 \lambda_1^{2n} + C_1 \lambda_2^{2n}} \\ &= \frac{\beta_1^2}{\beta_1^2 - 1}. \end{aligned} $$
Now we will show that $B = B'$, because for all $n \ge 0$ we have

$$ 
\begin{aligned}
& \frac{1 + A_1 \sum_{k=0}^{n} \beta_1^{2k} + B_1 \sum_{k=0}^{n} \lambda_1^{2k} + C_1 \sum_{k=0}^{n} \lambda_2^{2k}}{A_1 \beta_1^{2n} + B_1 \lambda_1^{2n} + C_1 \lambda_2^{2n}} \leq? \frac{\beta_1^2}{\beta_1^2 - 1} \\
& (\beta_1^2 - 1) \left( 1 + 2 \operatorname{Re} \left( B_1 \frac{\lambda_1^{2n+2} - 1}{\lambda_1^2 - 1} \right) \right) + A_1 \beta_1^{2n+2} - A_1 \leq? 2\beta_1^2 \operatorname{Re}(B_1 \lambda_1^{2n}) + A_1 \beta_1^{2n+2} \\
& (\beta_1^2 - 1) \left( 1 + 2 \operatorname{Re} \left( B_1 \frac{\lambda_1^{2n+2} - 1}{\lambda_1^2 - 1} \right) \right) \leq? 2\beta_1^2 \operatorname{Re}(B_1 \lambda_1^{2n}) + A_1.
\end{aligned}
$$

Now, on the one hand, for all $n \ge 2$, we have

$$ 
\begin{aligned}
(\beta_1^2 - 1) \left( 1 + 2 \operatorname{Re} \left( B_1 \frac{\lambda_1^{2n+2} - 1}{\lambda_1^2 - 1} \right) \right) &\leq (\beta_1^2 - 1) \left( 1 + 2 \operatorname{Re} \left( \frac{B_1}{1 - \lambda_1^2} \right) - 2 \operatorname{Re} \left( \frac{B_1}{1 - \lambda_1^2} \right) \right) \\
&\leq (\beta_1^2 - 1) \left( 1 + 2 \operatorname{Re} \left( \frac{B_1}{1 - \lambda_1^2} \right) + 2|B_1| \frac{|\lambda_1^{2n+2}|}{|1 - \lambda_1^2|} \right) \\
&\leq (\beta_1^2 - 1) \left( 1 + 2 \operatorname{Re} \left( \frac{B_1}{1 - \lambda_1^2} \right) + 2|B_1| \frac{|\lambda_1|^6}{|1 - \lambda_1^2|} \right).
\end{aligned}
$$

On the other hand,

$$ 2\beta_1^2 \operatorname{Re}(B_1 \lambda_1^{2n}) + A_1 \geq A_1 - 2\beta_1^2 |B_1| |\lambda_1|^4. $$

Substituting the values proves that

$$ (\beta_1^2 - 1) \left( 1 + 2 \operatorname{Re} \left( \frac{B_1}{1 - \lambda_1^2} \right) + 2|B_1| \frac{|\lambda_1|^6}{|1 - \lambda_1^2|} \right) < A_1 - 2\beta_1^2 |B_1| |\lambda_1|^4. $$

For $n = 0$, we get $\frac{1+a_0}{a_0} = \frac{1+12}{12} < B'$. For $n = 1$, we get $\frac{1+a_0+a_2}{a_2} = 1 + \frac{1+12}{32} < B'$. The inequality $B \le B'$ is proven, and therefore $B = B' = \frac{\beta_1^2}{\beta_1^2 - 1}$.

### 4.5.3 Computation of C and D

If we consider $c_n := |\psi(\varphi^n(01))|$, then we can see that $c_n$ satisfies the same recurrence relation as $a_n$, i.e., $c_{n+1} = 2c_n - c_{n-1} + c_{n-2}$ with initial conditions $c_0 = 7$, $c_1 = 13$, and $c_2 = 25$.

This recurrence relation can be solved and we obtain

$$ c_n = A_2 \beta_1^n + B_2 \lambda_1^n + C_2 \lambda_2^n, $$

where

$$ \beta_1 \doteq 1.75488, \quad \lambda_1 \doteq 0.12256 + 0.74486i, \quad \lambda_2 = \overline{\lambda_1} $$

are the roots of the polynomial $t^3 - 2t^2 + t - 1$, and

$$ A_2 = \frac{7|\lambda_1|^2 - 13 \operatorname{Re}(\lambda_1) + 25}{|\lambda_1 - \lambda_1|^2} \doteq 8.0149; $$

$$ B_2 = \frac{7\beta_1\lambda_2 - 13(\beta_1 + \lambda_2) + 25}{(\beta_1 - \lambda_1)(\lambda_2 - \lambda_1)} \doteq -0.5075 + 0.6315i; $$

$$ C_2 = \overline{B_2}. $$
The proof of $C' = D' = \frac{\beta_1^2}{\beta_1^2-1}$ proceeds in a similar fashion as that for $B'$ (resp., $A'$). To complete the proof, we need to show firstly $C \le C'$, i.e., for all $n \ge 0$ that

$$ \frac{3 + A_2 \sum_{k=0}^{n} \beta_1^{2k} + B_2 \sum_{k=0}^{n} \lambda_1^{2k} + C_2 \sum_{k=0}^{n} \lambda_2^{2k}}{A_2 \beta_1^{2n} + B_2 \lambda_1^{2n} + C_2 \lambda_2^{2n}} \le \frac{\beta_1^2}{\beta_1^2 - 1} \\ (\beta_1^2 - 1) \left( 3 + 2 \operatorname{Re} \left( B_2 \frac{\lambda_1^{2n+2} - 1}{\lambda_1^2 - 1} \right) \right) \le \beta_1^2 \operatorname{Re}(B_2 \lambda_1^{2n}) + A_2. $$

Now, we have for all $n \ge 2$

$$ (\beta_1^2 - 1) \left( 3 + 2 \operatorname{Re} \left( B_2 \frac{\lambda_1^{2n+2} - 1}{\lambda_1^2 - 1} \right) \right) \le (\beta_1^2 - 1) \left( 3 + 2 \operatorname{Re} \left( \frac{B_2}{1 - \lambda_1^2} \right) + 2|B_2| \frac{|\lambda_1|^6}{|1 - \lambda_1^2|} \right); \\ 2\beta_1^2 \operatorname{Re}(B_2 \lambda_1^{2n}) + A_2 \ge A_2 - 2\beta_1^2 |B_2| |\lambda_1|^4. $$

Substituting the values proves that

$$ (\beta_1^2 - 1) \left( 3 + 2 \operatorname{Re} \left( \frac{B_2}{1 - \lambda_1^2} \right) + 2|B_2| \frac{|\lambda_1|^6}{|1 - \lambda_1^2|} \right) < A_2 - 2\beta_1^2 |B_2| |\lambda_1|^4. $$

For $n = 0$, we get $\frac{3+c_0}{c_0} = 1 + \frac{3}{7} < C'$. For $n = 1$, we get $\frac{3+c_0+c_2}{c_2} = 1 + \frac{3+7}{25} < C'$. The inequality $C \le C'$ is proven. Hence $C = C' = \frac{\beta_1^2}{\beta_1^2-1}$.

Finally, we need to prove $D \le D'$, i.e., for all $n \ge 1$, that

$$ \frac{4 + A_2 \sum_{k=1}^{n} \beta_1^{2k-1} + B_2 \sum_{k=1}^{n} \lambda_1^{2k-1} + C_2 \sum_{k=1}^{n} \lambda_2^{2k-1}}{A_2 \beta_1^{2n-1} + B_2 \lambda_1^{2n-1} + C_2 \lambda_2^{2n-1}} \le \frac{\beta_1^2}{\beta_1^2 - 1} \\ (\beta_1^2 - 1) \left( 4 + 2 \operatorname{Re} \left( B_2 \lambda_1 \frac{\lambda_1^{2n} - 1}{\lambda_1^2 - 1} \right) \right) \le 2\beta_1^2 \operatorname{Re}(B_2 \lambda_1^{2n-1}) + A_2 \beta_1. $$

Using the same estimates as for $A$ and $n \ge 2$, it remains to check the following inequality

$$ (\beta_1^2 - 1) \left( 4 + 2|B_2||\lambda_1| \frac{|\lambda_1|^4 + 1}{|\lambda_1^2 - 1|} \right) \le A_2\beta_1 - 2\beta_1^2|B_2||\lambda_1|^3. $$

The inequality holds for given values. For $n = 1$, we get $\frac{4+c_1}{c_1} = 1 + \frac{4}{13} < D'$. Consequently, $D = D'$.

We have shown that $A = B = C = D = \frac{\beta_1^2}{\beta_1^2-1}$ and $E = 1 + \frac{1}{3} < A$. In other words, we have proved the following theorem.

**Theorem 12.** The critical exponent of $\psi(\mathbf{p})$ equals

$$ \operatorname{ce}(\psi(\mathbf{p})) = 1 + \frac{\beta_1^2}{\beta_1^2 - 1} = 2 + \frac{1}{\beta_1^2 - 1} \doteq 2.4808627161472369. $$

Let us emphasize that the critical exponents of $\mathbf{p}$ and $\psi(\mathbf{p})$ are the same [6].
## 4.6 Bispecial factors in $\xi(\mathbf{p})$

Now we turn to $\xi(\mathbf{p})$. Let us start with some simple observations. If a factor $v \in \mathcal{L}(\xi(\mathbf{p}))$ contains the factor 00 or 1011 or 11010, then we are able to express $v = x\xi(w)y$ uniquely, where $w \in \mathcal{L}(\mathbf{p})$ and $x$ (resp., $y$) is a proper suffix (resp., proper prefix) of an image of some letter. Moreover, if $v$ is a bispecial factor in $\xi(\mathbf{p})$, then $w$ is a bispecial factor in $\mathbf{p}$.

**Observation 13.** Let $v \in \mathcal{L}(\xi(\mathbf{p}))$ be a bispecial factor such that it contains 00 or 1011 or 11010. Assume $v \neq 1\xi(1) = 10110$ and $v \neq 1\xi(10) = 1011001$. Then there exists $w \in \mathcal{L}(\mathbf{p})$ such that either $v = \xi(w)$ and $w$ is a bispecial factor with left extensions $\{0, 1\}$, or $v = 01\xi(w)$ and $w$ is a bispecial factor with left extensions $\{0, 2\}$. Moreover, the length of the shortest return word to $v$ in $\xi(\mathbf{p})$ equals $|\xi(r)|$, where $r$ is the shortest return word to $w$ in $\mathbf{p}$.

## 4.7 Critical exponent of $\xi(\mathbf{p})$

Using Observation 13, the lengths of bispecial factors and their shortest return words in $\xi(\mathbf{p})$ may be derived in an analogous way as in the case of $\psi(\mathbf{p})$. Next, we can use Theorem 5 to compute the critical exponent of $\xi(\mathbf{p})$:

$$ 
\begin{aligned}
\mathrm{ce}(\xi(\mathbf{p})) &= 1 + \max\{A, B, C, D, E\} \\
A &= \sup \left\{ \frac{|01\xi(1\varphi(012)\varphi^3(012)\cdots\varphi^{2n-1}(012))|}{|\xi(\varphi^{2n-1}(012))|} : n \ge 1 \right\}; \\
B &= \sup \left\{ \frac{|\xi(012\varphi^2(012)\varphi^4(012)\cdots\varphi^{2n}(012))|}{|\xi(\varphi^{2n}(012))|} : n \ge 0 \right\}; \\
C &= \sup \left\{ \frac{|01\xi(01\varphi^2(01)\varphi^4(01)\cdots\varphi^{2n}(01))|}{|\xi(\varphi^{2n}(01))|} : n \ge 0 \right\}; \\
D &= \sup \left\{ \frac{|\xi(\varphi(01)\varphi^3(01)\cdots\varphi^{2n+1}(01))|}{|\xi(\varphi^{2n+1}(01))|} : n \ge 0 \right\}; \\
E &= \max \left\{ \frac{|w|}{|r|} : w \text{ short bispecial and } r \text{ the shortest return word to } w \right\},
\end{aligned}
$$

where we say that $w$ is a short bispecial factor if $w$ does not contain 00, 1011, 11010 or $w = 1\xi(1)$ or $w = 1\xi(10)$.

### 4.7.1 Computation of $E$

<table><tr><td>w</td><td>0</td><td>1</td><td>01</td><td>10</td><td>101</td><td>0110</td><td>01101</td><td>1ξ(1)</td><td>1ξ(10)</td></tr><tr><td>r</td><td>0</td><td>1</td><td>01</td><td>10</td><td>10</td><td>011</td><td>011010110</td><td>1ξ(1)</td><td>1ξ(10)1<sup>-1</sup></td></tr></table>

Thus, we have $E = \frac{3}{2}$.
### 4.7.2 Computation of A, B, C, D

If we consider $x_n := |\xi(\varphi^n(012))|$, then we can see that $x_n$ satisfies the recurrence relation $x_{n+1} = 2x_n - x_{n-1} + x_{n-2}$ with initial conditions $x_0 = 7, x_1 = 13$, and $x_2 = 24$.

This recurrence relation may be solved and we obtain

$$x_n = X_1\beta_1^n + Y_1\lambda_1^n + Z_1\lambda_2^n,$$

where

$$\beta_1 \doteq 1.75488, \quad \lambda_1 \doteq 0.12256 + 0.74486i, \quad \lambda_2 = \overline{\lambda_1}$$

are the roots of the polynomial $t^3 - 2t^2 + t - 1$, and

$$X_1 = \frac{7|\lambda_1|^2 - 26 \operatorname{Re}(\lambda_1) + 24}{|\lambda_1 - \lambda_1|^2} \doteq 7.704;$$

$$Y_1 = \frac{7\beta_1\lambda_2 - 13(\beta_1 + \lambda_2) + 24}{(\beta_1 - \lambda_1)(\lambda_2 - \lambda_1)} \doteq -0.352 + 0.291i;$$

$$Z_1 = \overline{Y_1}.$$

We want to show for all $n \ge 1$ that

$$\frac{6 + X_1 \sum_{k=1}^{n} \beta_1^{2k-1} + Y_1 \sum_{k=1}^{n} \lambda_1^{2k-1} + Z_1 \sum_{k=1}^{n} \lambda_2^{2k-1}}{X_1\beta_1^{2n-1} + Y_1\lambda_1^{2n-1} + Z_1\lambda_2^{2n-1}} \le \beta_1^2 \frac{\beta_1^2}{\beta_1^2 - 1} < \frac{3}{2}.$$

$$(\beta_1^2 - 1) \left( 6 + 2 \operatorname{Re} \left( Y_1 \lambda_1 \frac{\lambda_1^{2n} - 1}{\lambda_1^2 - 1} \right) \right) + X_1 \beta_1^{2n+1} - X_1 \beta_1 \le \beta_1^2 \operatorname{Re}(Y_1 \lambda_1^{2n-1}) + X_1 \beta_1^{2n+1}$$

$$(\beta_1^2 - 1) \left( 6 + 2 \operatorname{Re} \left( Y_1 \lambda_1 \frac{\lambda_1^{2n} - 1}{\lambda_1^2 - 1} \right) \right) \le \beta_1^2 \operatorname{Re}(Y_1 \lambda_1^{2n-1}) + X_1 \beta_1.$$

Now, on one hand, for $n \ge 7$ we have

$$(\beta_1^2 - 1) \left( 6 + 2 \operatorname{Re} \left( Y_1 \lambda_1 \frac{\lambda_1^{2n} - 1}{\lambda_1^2 - 1} \right) \right) \le (\beta_1^2 - 1) \left( 6 + 2|Y_1||\lambda_1| \frac{|\lambda_1|^{14} + 1}{|\lambda_1^2 - 1|} \right).$$

On the other hand, we have

$$2\beta_1^2 \operatorname{Re}(Y_1 \lambda_1^{2n-1}) + X_1 \beta_1 \ge X_1 \beta_1 - 2\beta_1^2 |Y_1||\lambda_1|^{13}.$$

And if we substitute the values, we get

$$(\beta_1^2 - 1) \left( 6 + 2|Y_1||\lambda_1| \frac{|\lambda_1|^{14} + 1}{|\lambda_1^2 - 1|} \right) \le X_1 \beta_1 - 2\beta_1^2 |Y_1||\lambda_1|^{13}.$$
<table><caption>Table 2: The first 6 elements of A.</caption><thead><tr><th>n</th><th>1</th><th>2</th><th>3</th><th>4</th><th>5</th><th>6</th></tr></thead><tbody><tr><th>A<sub>n</sub></th><td>1.4615</td><td>1.4524</td><td>1.4766</td><td>1.4785</td><td>1.4803</td><td>1.4806</td></tr></tbody></table>

The first 6 values from the set A are given in Table 2. We can see that they are all smaller than $\frac{3}{2}$. The inequality therefore holds for all $n \ge 1$.

We have shown that $A < \frac{3}{2} = E$. Using the same estimates, we can show that also the remaining values B, C, D are smaller than $\frac{3}{2}$. In other words, we have proved the following theorem.

**Theorem 14.** The critical exponent of $\xi(\mathbf{p})$ equals $\frac{5}{2}$.

# 5 Complexity threshold

Notice that we used two different constructions of infinite words in the proof of Theorem 3. When possible, that is in cases (b), (c), and (f), we use morphic images of arbitrary ternary square-free words, thus showing that exponentially many binary words have the considered property. Otherwise, in cases (a), (d), and (e), every bi-infinite binary word with the considered property has the same set of factors as one or a few morphic words.

In this section, we consider the latter case and we relax the constraints on the critical exponent or the complementary factors in order to get exponential factor complexity.

Let $h$ be the morphism that maps $0 \mapsto 0$ and $1 \mapsto 01$.

**Lemma 15.** Every bi-infinite binary 4-free word avoiding pairs of complementary factors of length 4 and $\{1001001, 0110110\}$ has the same set of factors as either $h(\mathbf{f})$ or $\overline{h}(\mathbf{f})$.

*Proof.* We compute the set $S$ of factors $y$ such that there exists a binary 4-free word $xyz$ avoiding pairs of complementary factors of length 4 and $\{1001001, 0110110\}$ and such that $|x| = |y| = |z| = 100$. We observe that $S$ consists of the (disjoint) union of the factors of length 100 of $h(\mathbf{f})$ and $\overline{h}(\mathbf{f})$. Let $\mathbf{w}$ be a bi-infinite binary 4-free word avoiding pairs of complementary factors of length 4 and $\{1001001, 0110110\}$. By symmetry, we suppose that $\mathbf{w}$ contains 00, so that $\mathbf{w}$ has the same factors of length 100 as $h(\mathbf{f})$. So $\mathbf{w} \in \{0, 01\}^\omega$, that is, $\mathbf{w} = h(\mathbf{v})$ for some bi-infinite binary word $\mathbf{v}$. Since $\mathbf{w}$ is 4-free, so is $\mathbf{v}$. Moreover, by considering the pre-images by $h$ of $\mathbf{w} = h(\mathbf{v})$ and $h(\mathbf{f})$, this implies that $\mathbf{v}$ and $\mathbf{f}$ have the same set of factors of length $100/\max(|h(0)|, |h(1)|) = 50$. In particular, $\mathbf{v}$ avoids $\{11, 000, 10101\}$. By [2, Thm. 8], $\mathbf{v}$ has the same set of factors as $\mathbf{f}$. Thus $\mathbf{w}$ has the same set of factors as $h(\mathbf{f})$. $\square$

**Theorem 16.** Every bi-infinite binary $\frac{11}{3}$-free word that contains no pair of complementary factors of length 4 has the same set of factors as $h(\mathbf{f})$ or the same set of factors as $\overline{h}(\mathbf{f})$.

*Proof.* Suppose that such a word $\mathbf{w}$ contains 1001001.
First, suppose that $\mathbf{w}$ contains 11. Since $\mathbf{w}$ avoids $0110 = \overline{1001}$, $\mathbf{w}$ contains 111. Since $\mathbf{w}$ avoids the 4-power $1111$, $\mathbf{w}$ contains $01110$. Since $\mathbf{w}$ avoids $1101 = \overline{0010}$, $\mathbf{w}$ contains $011100$. Symmetrically, since $\mathbf{w}$ avoids $1011 = \overline{0100}$, $\mathbf{w}$ contains $0011100$. So $\mathbf{w}$ contains both $0011$ and $1100$, a contradiction. Thus, $\mathbf{w}$ avoids 11.

Now, suppose that $\mathbf{w}$ contains 101. Since $\mathbf{w}$ avoids 11, $\mathbf{w}$ contains $01010$. So $\mathbf{w}$ contains both $0101$ and $1010$, a contradiction. Thus, $\mathbf{w}$ avoids 101.

Since $\mathbf{w}$ contains $1001001$ and avoids 11, $\mathbf{w}$ contains $010010010$. Since $\mathbf{w}$ contains $010010010$ and avoids 101, $\mathbf{w}$ contains $00100100100$. This is a contradiction, since $00100100100 = (001)^{11/3}$.

So $\mathbf{w}$ avoids $1001001$. By symmetry, $\mathbf{w}$ avoids $0110110$.

By Lemma 15, $\mathbf{w}$ has the same set of factors as either $h(\mathbf{f})$ or $\overline{h(\mathbf{f})}$. $\square$

By contrast, there exist exponentially many binary $\frac{11}{3}$-free words with no pair of complementary factors of length 4.

**Theorem 17.** *The image of any ternary squarefree word by the 31-uniform morphism*

$$ 
\begin{aligned}
0 &\rightarrow 0010001001001000100100100010010 \\
1 &\rightarrow 0010001001001000100100100010001 \\
2 &\rightarrow 0010001001001000100100010010010
\end{aligned}
 $$

is a $\frac{11}{3}$-free word containing only 0, 1, 01, and 10 as complementary factors.

Let $\rho$ be the morphism defined as follows

$$ 
\begin{aligned}
0 &\rightarrow 01100101101 \\
1 &\rightarrow 0110010 \\
2 &\rightarrow 011001.
\end{aligned}
 $$

Using the technique of Theorem 3 (d), we can show that $\rho(\mathbf{p})$ is a $\frac{5}{2}$-free word with no pair of complementary factors of length 8 and exactly 40 complementary factors.

**Theorem 18.** *Every bi-infinite binary $\frac{29}{11}$-free word that contains no pair of complementary factors of length 8 has the same set of factors as either $\xi(\mathbf{p})$, $\overline{\xi(\mathbf{p})}$, $\xi(\mathbf{p})^R$, $\overline{\xi(\mathbf{p})}^R$, $\rho(\mathbf{p})$, $\overline{\rho(\mathbf{p})}$, $\rho(\mathbf{p})^R$, or $\overline{\rho(\mathbf{p})}^R$.*

*Proof.* First, we show the following. If $\mathbf{w}$ is a bi-infinite cube-free binary word and every factor of length 21 of $\mathbf{w}$ is also a factor of $\xi(\mathbf{p})$, then $\mathbf{w}$ has the same set of factors as $\xi(\mathbf{p})$.

We compute the set $S$ of factors $f$ such that there exists $u = efg$, where $u$ is cube-free, every factor of length 21 of $u$ is a factor of $\xi(\mathbf{p})$, and $|e| = |f| = |g| = 500$. We verify that every factor $f \in S$ is a factor of $\xi(\mathbf{p})$.

This means that $\mathbf{w} = \xi(\mathbf{v})$ for some bi-infinite ternary word $\mathbf{v}$. Moreover, by considering the pre-images by $\xi$ of $\mathbf{w} = \xi(\mathbf{v})$ and $\xi(\mathbf{p})$, this implies that $\mathbf{v}$ and $\mathbf{p}$ have the same set of
[4] A. Carpi and A. de Luca. Special factors, periodicity, and an application to Sturmian words. *Acta Informatica* **36** (2000), 983–1006.

[5] J. D. Currie, L. Mol, and N. Rampersad. The repetition threshold for binary rich words. *Discrete Math. & Theoret. Comput. Sci.* **22**(1) (2020), DMTCS-22-1-6 (electronic), https://dmtcs.episciences.org/6082

[6] J. D. Currie, P. Ochem, N. Rampersad, and J. Shallit. Properties of a ternary infinite word. Arxiv preprint arXiv:2206.01776 [cs.DM], available at https://arxiv.org/abs/2206.01776, 2022. To appear, *RAIRO Inform. Théor. App.* **57** (2023).

[7] J. Currie and N. Rampersad. A proof of Dejean's conjecture. *Math. Comp.* **80** (2011), 1063–1070.

[8] F. Dejean. Sur un théorème de Thue. *J. Combin. Theory. Ser. A* **13** (1972), 90–99.

[9] F. Dolce, L. Dvořáková, and E. Pelantová. On balanced sequences and their critical exponent. *Theoret. Comput. Sci.* **939** (2023), 18–47.

[10] L. Dvořáková, K. Medková, and E. Pelantová. Complementary symmetric Rote sequences: the critical exponent and the recurrence function. *Discrete Math. & Theoret. Comput. Sci.* **22**(1) (2020), DMTCS-22-1-20 (electronic), https://dmtcs.episciences.org/6519/

[11] L. Dvořáková, D. Opočenská, E. Pelantová, and A. M. Shur. On minimal critical exponent of balanced sequences. *Theoret. Comput. Sci.* **922** (2022), 158–169.

[12] F. Fiorenzi, P. Ochem, and E. Vaslet. Bounds for the generalized repetition threshold. *Theoret. Comput. Sci.* **412** (2011), 2955–2963.

[13] L. Ilie, P. Ochem, and J. Shallit. A generalization of repetition threshold. *Theoret. Comput. Sci.* **345** (2005), 359–369.

[14] J. Karhumäki and J. Shallit. Polynomial versus exponential growth in repetition-free binary words. *J. Combin. Theory. Ser. A* **105**(2) (2004), 335–347.

[15] L. Mol, N. Rampersad, and J. Shallit. Extremal overlap-free and extremal $\beta$-free binary words. *Electronic J. Combinatorics* **27**(4) (2020), #P4.42 (electronic).

[16] H. Mousavi and J. Shallit. Repetition avoidance in circular factors. In M.-P. Béal and O. Carton, editors, *DLT 2013*, Vol. 7907 of Lecture Notes in Computer Science, pp. 384–395. Springer-Verlag, 2013.

[17] N. Rampersad, J. Shallit, and É. Vandomme. Critical exponents of infinite balanced words. *Theoret. Comput. Sci.* **777** (2019), 454–463.

[18] M. Rao. Last cases of Dejean's conjecture. *Theoret. Comput. Sci.* **412** (2011), 3010–3018.
[19] A. V. Samsonov and A. M. Shur. On Abelian repetition threshold. *RAIRO Inform. Théor. App.* **46** (2012), 147-163.

[20] J. Sawada, B. Stevens, and A. Williams. De Bruijn sequences for the binary strings with maximum density. In N. Katoh and A. Kumar, editors, *WALCOM 2011*, Vol. 6552 of *Lecture Notes in Computer Science*, pp. 182-190. Springer-Verlag, 2011.

[21] J. Shallit. Simultaneous avoidance of large squares and fractional powers in infinite binary words. *Internat. J. Found. Comp. Sci.* **15** (2004), 317-327.

[22] J. Shallit. Minimal critical exponents for palindromes. ArXiv preprint, arXiv:1612.05320 [cs.FL]. Available at https://arxiv.org/abs/1612.05320, 2016.

[23] A. Shur. Growth properties of power-free languages. *Comput. Sci. Rev.* **6** (2012), 187-208.