# Critical exponent of binary words with few distinct palindromes

L’ubomíra Dvořáková111FNSPE Czech Technical University, Prague, Czech
Republic.
e-mail<EMAIL_ADDRESS>Pascal Ochem222LIRMM, CNRS, Université
de Montpellier, France.
e-mail<EMAIL_ADDRESS>Daniela Opočenská333FNSPE Czech Technical University,
Prague, Czech Republic.
e-mail<EMAIL_ADDRESS>
(2023)

###### Abstract

We study infinite binary words that contain few distinct palindromes. In
particular, we classify such words according to their critical exponents. This
extends results by Fici and Zamboni [TCS 2013]. Interestingly, the words with
18 and 20 palindromes happen to be morphic images of the fixed point of the
morphism $\texttt{0}\mapsto\texttt{01}$, $\texttt{1}\mapsto\texttt{21}$,
$\texttt{2}\mapsto\texttt{0}$.

##  1 Introduction

We consider the trade-off between the number of distinct palindromes and the
critical exponent in infinite binary words. Fici and Zamboni [6] show that the
least number of (possibly empty) distinct palindromes in an infinite binary
word is 9 and this bound is reached by the word $(\texttt{001011})^{\omega}$.
At the other end of the spectrum, the famous Thue-Morse word $TM$, fixed point
of the morphism $\texttt{0}\to\texttt{01}$, $\texttt{1}\to\texttt{10}$, has
the least critical exponent and infinitely many palindromes.

Our results completely answer questions of the form ”Is there an infinite
$\beta^{+}$-free binary word with at most $p$ palindromes?” In each case, we
also determine whether there are exponentially or polynomially many such
words. The results are summarized in Table 1. A green (resp. red) cell means
that there are exponentially (resp. polynomially) many words. We have labelled
the cells that correspond to an item of Theorem 3 or 7. Fici and Zamboni [6]
also show that an aperiodic binary word contains at least 11 distinct
palindromes and this bound is reached by the morphic image of the Fibonacci
word by $\texttt{0}\to\texttt{0}$, $\texttt{1}\to\texttt{01101}$. This word
contains in particular the factor

$(\texttt{00110100011010011010001101000110100110100011010011010001101000110100110100011010001101})^{\tfrac{7}{2}}.$

Theorem 1.(a) improves this exponent to $\tfrac{10}{3}^{+}$.

$\infty$ $TM$ 25 3.h 24 23 22 21 3.g 20 7.b 19 3.f 18 7.a 3.e 17 16 15 3.d 14
13 3.c 12 3.b 11 3.a 10 9 $(\texttt{001011})^{\omega}$ $p$ $\beta^{+}$ $2^{+}$
$\tfrac{7}{3}^{+}$ $\tfrac{5}{2}^{+}$ $\tfrac{28}{11}^{+}$ $\tfrac{13}{5}^{+}$
$\tfrac{8}{3}^{+}$ $3^{+}$ $\tfrac{23}{7}^{+}$ $\tfrac{10}{3}^{+}$ $\infty$

Table 1: Infinite $\beta^{+}$-free binary words with at most $p$ palindromes.

##  2 Preliminaries

An _alphabet_ $\mathcal{A}$ is a finite set and its elements are called
_letters_. A _word_ $u$ over $\mathcal{A}$ of _length_ $n$ is a finite string
$u=u_{0}u_{1}\cdots u_{n-1}$, where $u_{j}\in\mathcal{A}$ for all
$j\in\\{0,1,\dots,n-1\\}$. If ${\mathcal{A}}=\\{\tt 0,\tt 1,\dots,\tt d-1\\}$,
the length of $u$ is denoted $|u|$ and $|u|_{\tt i}$ denotes the number of
occurrences of the letter ${\tt i}\in\mathcal{A}$ in the word $u$. The _Parikh
vector_ $\vec{u}\in\mathbb{N}^{d}$ is the vector defined as
${\vec{u}}=(|u|_{\tt 0},|u|_{\tt 1},\dots,|u|_{\tt d-1})^{T}$. The set of all
finite words over $\mathcal{A}$ is denoted ${\mathcal{A}}^{*}$. The set
${\mathcal{A}}^{*}$ equipped with concatenation as the operation forms a
monoid with the _empty word_ $\varepsilon$ as the neutral element. We will
also consider the set ${\mathcal{A}}^{\omega}$ of infinite words (that is,
right-infinite words) and the set ${}^{\omega}{\mathcal{A}}^{\omega}$ of bi-
infinite words. A word $v$ is an $e$-_power_ of a word $u$ if $v$ is a prefix
of the infinite periodic word $uuu\cdots=u^{\omega}$ and $e=|v|/|u|$. We write
$v=u^{e}$. We also call $u^{e}$ a repetition with period $u$ and exponent $e$.
For instance, the Czech word $kapka$ (drop) can be written in this formalism
as $(kap)^{5/3}$. A word is _$\alpha^{+}$ -free_ (resp. _$\alpha$ -free_) if
it contains no repetition with exponent $\beta$ such that $\beta>\alpha$
(resp. $\beta\geqslant\alpha$).

The _critical exponent_ $E({\bf u})$ of an infinite word ${\bf u}$ is defined
as

$E({\bf u})=\sup\\{e\in\mathbb{Q}:\ u^{e}\ \text{is a factor of }{\bf u}\
\text{for a non-empty word}\ u\\}\,.$

The _asymptotic critical exponent_ $E^{*}(\bf u)$ of an infinite word ${\bf
u}$ is defined as $+\infty$ if $E({\bf u})=+\infty$, and

$E^{*}({\bf u})=\limsup_{n\to\infty}\\{e\in\mathbb{Q}:\ u^{e}\ \text{is a
factor of }{\bf u}\ \text{for some }u\ \text{of length}\ n\\}\,,$

otherwise. If each factor of ${\bf u}$ has infinitely many occurrences in
${\bf u}$, then ${\bf u}$ is _recurrent_. Moreover, if for each factor the
distances between its consecutive occurrences are bounded, then ${\bf u}$ is
_uniformly recurrent_. The _language_ $\mathcal{L}(\bf u)$ is the set of
factors occurring in $\bf u$. The language $\mathcal{L}(\bf u)$ is _closed
under reversal_ if for each factor $w=w_{0}w_{1}\cdots w_{n-1}$, its _reverse_
$w^{R}=w_{n-1}\cdots w_{1}w_{0}$ is also a factor of $\bf u$. A word $w$ is a
_palindrome_ if $w=w^{R}$. Let us denote $\overline{\tt 0}=\tt 1$ and
$\overline{\tt 1}=\tt 0$, then for any binary word $w$ its _bit complement_ is
$\overline{w}=\overline{w_{0}}\ \overline{w_{1}}\cdots\overline{w_{n-1}}$.

Consider a factor $w$ of a recurrent infinite word ${\bf
u}=u_{0}u_{1}u_{2}\cdots$. Let $j<\ell$ be two consecutive occurrences of $w$
in $\bf u$. Then the word $u_{j}u_{j+1}\cdots u_{\ell-1}$ is a  _return word_
to $w$ in $\bf u$.

The _(factor) complexity_ of an infinite word ${\bf u}$ is the mapping
${\mathcal{C}}_{\bf u}:\mathbb{N}\to\mathbb{N}$ defined by ${\mathcal{C}}_{\bf
u}(n)=\\#\\{w\in\mathcal{L}({\bf u}):|w|=n\\}$.

Given a word $w\in\mathcal{L}({\bf u})$, we define the sets of left
extensions, right extensions and bi-extensions of $w$ in ${\bf u}$ over an
alphabet $\mathcal{A}$ respectively as

$L_{{\bf u}}(w)=\\{{\tt i}\in{\mathcal{A}}:{\tt i}w\in\mathcal{L}({\bf
u})\\},\qquad R_{{\bf u}}(w)=\\{{\tt j}\in{\mathcal{A}}:w{\tt
j}\in\mathcal{L}({\bf u})\\}$

and

$B_{{\bf u}}(w)=\\{({\tt i},{\tt j})\in{\mathcal{A}}\times{\mathcal{A}}:{\tt
i}w{\tt j}\in\mathcal{L}({\bf u})\\}.$

If $\\#L_{{\bf u}}(w)>1$, then $w$ is called _left special (LS)_. If
$\\#R_{{\bf u}}(w)>1$, then $w$ is called _right special (RS)_. If $w$ is both
LS and RS, then it is called _bispecial (BS)_. We define $b(w)=\\#B_{{\bf
u}}(w)-\\#L_{{\bf u}}(w)-\\#R_{{\bf u}}(w)+1$ and we distinguish _ordinary BS
factors_ with $b(w)=0$, _weak BS factors_ with $b(w)<0$ and _strong BS
factors_ with $b(w)>0$.

A _morphism_ is a map $\psi:{\mathcal{A}}^{*}\to{\mathcal{B}}^{*}$ such that
$\psi(uv)=\psi(u)\psi(v)$ for all words $u,v\in{\mathcal{A}}^{*}$. The
morphism $\psi$ is _non-erasing_ if $\psi(\tt i)\not=\varepsilon$ for each
${\tt i}\in{\mathcal{A}}$. Morphisms can be naturally extended to infinite
words by setting
$\psi(u_{0}u_{1}u_{2}\cdots)=\psi(u_{0})\psi(u_{1})\psi(u_{2})\cdots\,$. A
_fixed point_ of a morphism $\psi:{\mathcal{A}}^{*}\to{\mathcal{A}}^{*}$ is an
infinite word $\bf u$ such that $\psi(\bf u)=\bf u$. We associate to a
morphism $\psi:{\mathcal{A}}^{*}\to{\mathcal{A}}^{*}$ the _(incidence) matrix_
$M_{\psi}$ defined for each $k,j\in\\{0,1,\dots,d-1\\}$ as
$[M_{\psi}]_{kj}=|\psi(\tt j)|_{\tt k}$.

If there exists $N\in\mathbb{N}$ such that $M_{\psi}^{N}$ has positive
entries, then $\psi$ is a  _primitive_ morphism. By definition, we have for
each $u\in{\mathcal{A}}^{*}$ the following relation for the Parikh vectors
$\vec{\psi(u)}=M_{\psi}\vec{u}$.

Let ${\bf u}$ be an infinite word over an alphabet $\mathcal{A}$. Then the
_uniform frequency_ $f_{\tt i}$ of the letter ${\tt i}\in\mathcal{A}$ is equal
to $\alpha$ if for any sequence $(w_{n})$ of factors of ${\bf u}$ with
increasing lengths

$\alpha=\lim_{n\to\infty}\frac{|w_{n}|_{\tt i}}{|w_{n}|}\,.$

It is known that fixed points of primitive morphisms have uniform letter
frequencies [7].

Let ${\bf u}$ be an infinite word over an alphabet $\mathcal{A}$ and let
$\psi:{\mathcal{A}}^{*}\to{\mathcal{B}}^{*}$ be a morphism. Consider a factor
$w$ of $\psi({\bf u})$. We say that $(w_{1},w_{2})$ is a _synchronization
point_ of $w$ if $w=w_{1}w_{2}$ and for all $p,s\in{\mathcal{L}}(\psi({\bf
u}))$ and $v\in{\mathcal{L}}({\bf u})$ such that $\psi(v)=pws$ there exists a
factorization $v=v_{1}v_{2}$ of $v$ with $\psi(v_{1})=pw_{1}$ and
$\psi(v_{2})=w_{2}s$. We denote the synchronization point by $w_{1}\bullet
w_{2}$.

Given a factorial language $L$ and an integer $\ell$, let $L^{\ell}$ denote
the words of length $\ell$ in $L$. The _Rauzy graph_ of $L$ of order $\ell$ is
the directed graph whose vertices are the words of $L^{\ell-1}$, the arcs are
the words of $L^{\ell}$, and the arc corresponding to the word $w$ goes from
the vertex corresponding to the prefix of $w$ of length $\ell-1$ to the vertex
corresponding to the suffix of $w$ of length $\ell-1$.

Finally, this paper mainly studies properties of the words $\mu(\bf p)$ and
$\nu(\bf p)$ that are morphic images of the word ${\bf
p}=\varphi^{\omega}(\texttt{0})$ studied in [2], where

$\displaystyle\varphi(\texttt{0})$ $\displaystyle=\texttt{01}$
$\displaystyle\varphi(\texttt{1})$ $\displaystyle=\texttt{21}$
$\displaystyle\varphi(\texttt{2})$ $\displaystyle=\texttt{0}$

$\displaystyle\mu(\texttt{0})$ $\displaystyle=\texttt{011001}$
$\displaystyle\mu(\texttt{1})$ $\displaystyle=\texttt{1001}$
$\displaystyle\mu(\texttt{2})$ $\displaystyle=\texttt{0}$

$\displaystyle\nu(\texttt{0})$ $\displaystyle=\texttt{011}$
$\displaystyle\nu(\texttt{1})$ $\displaystyle=\texttt{0}$
$\displaystyle\nu(\texttt{2})$ $\displaystyle=\texttt{01}$

##  3 Fewest palindromes, least critical exponent, and factor complexity

###  3.1 General result

######  Theorem 1.

There exists an infinite binary $\beta^{+}$-free word containing only $p$
palindromes for the following pairs $(p,\beta)$. Moreover, this list of pairs
is optimal.

  1. (a)

$(11,\tfrac{10}{3})$

  2. (b)

$(12,\tfrac{23}{7})$

  3. (c)

$(13,3)$

  4. (d)

$(15,\tfrac{8}{3})$

  5. (e)

$(18,\tfrac{28}{11})$

  6. (f)

$(20,\tfrac{5}{2})$

  7. (g)

$(25,\tfrac{7}{3})$

###### Proof.

The optimality is obtained by bactracking. For example, the step between items
(c) and (d) is obtained by showing that there exists no infinite cubefree word
containing at most $14$ palindromes. The proof of the positive results is
split in two cases, depending on the factor complexity of the considered
words, see Theorems 3 and 7. Let us already remark that, in any case, it is
easy to check that the proposed word does not contain more than the claimed
number of distinct palindromes since it only requires to check the factors up
to some finite length. ∎

###  3.2 Exponential cases

We need some terminology and a lemma from [9]. A morphism
$f:\Sigma^{*}\rightarrow\Delta^{*}$ is _$q$ -uniform_ if $|f(a)|=q$ for every
$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$.

######  Lemma 2.

[9, Lemma 23] Let $a,b\in\mathbb{R}$ satisfy $1<a<b$. Let
$\alpha\in\\{a,a^{+}\\}$ and $\beta\in\\{b,b^{+}\\}$. Let
$h\colon\Sigma^{*}\rightarrow\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|\leq t$,
then $h(z)$ is $\beta$-free for every $\alpha$-free word $z\in\Sigma^{*}$.

The results in this subsection use the following steps. We find an appropriate
uniform synchronizing morphism $h$ by exhaustive search. We use Lemma 2 to
show that $h$ maps every binary $\tfrac{7}{3}^{+}$-free word (resp. ternary
squarefree word) to a suitable binary $\beta^{+}$-free word. Since there are
exponentially many binary $\tfrac{7}{3}^{+}$-free words [8] (resp. ternary
squarefree words [10]), there are also exponentially many binary
$\beta^{+}$-free words.

######  Theorem 3.

There exist exponentially many infinite binary $\beta^{+}$-free words
containing at most $p$ palindromes for the following pairs $(p,\beta)$.

  1. (a)

$(11,\tfrac{10}{3})$

  2. (b)

$(12,\tfrac{23}{7})$

  3. (c)

$(13,3)$

  4. (d)

$(15,\tfrac{8}{3})$

  5. (e)

$(18,\tfrac{13}{5})$

  6. (f)

$(19,\tfrac{28}{11})$

  7. (g)

$(21,\tfrac{5}{2})$

  8. (h)

$(25,\tfrac{7}{3})$

###### Proof.

  1. (a)

$(11,\tfrac{10}{3})$: Applying the 39-uniform morphism

0 $\displaystyle\rightarrow\texttt{001011001011100101110010110010111001011}$ 1
$\displaystyle\rightarrow\texttt{100101100101100101110010110010111001011}$

to any binary $\tfrac{7}{3}^{+}$-free word gives a $\tfrac{10}{3}^{+}$-free
binary word containing at most $11$ palindromes.

  2. (b)

$(12,\tfrac{23}{7})$: Applying the 45-uniform morphism

0
$\displaystyle\rightarrow\texttt{000101100010111000101110001011000101110001011}$
1
$\displaystyle\rightarrow\texttt{100010110001011000101110001011000101110001011}$

to any binary $\tfrac{7}{3}^{+}$-free word gives a $\tfrac{23}{7}^{+}$-free
binary word containing at most $12$ palindromes.

  3. (c)

$(13,3)$: Applying the 7-uniform morphism

0 $\displaystyle\rightarrow\texttt{0001011}$ 1
$\displaystyle\rightarrow\texttt{1001011}$

to any binary $\tfrac{7}{3}^{+}$-free word gives a cubefree binary word
containing at most $13$ palindromes.

  4. (d)

$(15,\tfrac{8}{3})$: Applying the 3-uniform morphism

0 $\displaystyle\rightarrow\texttt{001}$ 1
$\displaystyle\rightarrow\texttt{101}$

to any binary $\tfrac{7}{3}^{+}$-free word gives a $\tfrac{8}{3}^{+}$-free
binary word containing at most $15$ palindromes.

  5. (e)

$(18,\tfrac{13}{5})$: Applying the 72-uniform morphism

0
$\displaystyle\rightarrow\texttt{001011001100101100101001011001100101100110010100101100101001011001100101}$
1
$\displaystyle\rightarrow\texttt{100110010100101100110010110010100101100110010100101100101001011001100101}$

to any binary $\tfrac{7}{3}^{+}$-free word gives a $\tfrac{13}{5}^{+}$-free
binary word containing at most $18$ palindromes.

  6. (f)

$(19,\tfrac{28}{11})$: Applying the 49-uniform morphism

0
$\displaystyle\rightarrow\texttt{0010110010110101100101001011001010010110101100101}$
1
$\displaystyle\rightarrow\texttt{1010110010100101100101101011001010010110101100101}$

to any binary $\tfrac{7}{3}^{+}$-free word gives a $\tfrac{28}{11}^{+}$-free
binary word containing at most $19$ palindromes.

  7. (g)

$(21,\tfrac{5}{2})$: Applying the 10-uniform morphism

0 $\displaystyle\rightarrow\texttt{0011001101}$ 1
$\displaystyle\rightarrow\texttt{1001011001}$

to any binary $\tfrac{7}{3}^{+}$-free word gives a $\tfrac{5}{2}^{+}$-free
binary word containing at most $21$ palindromes.

  8. (h)

$(25,\tfrac{7}{3})$: Applying the 36-uniform morphism

0 $\displaystyle\rightarrow\texttt{001101100101100110110010011001011001}$ 1
$\displaystyle\rightarrow\texttt{101100100110100110110010011001011001}$ 2
$\displaystyle\rightarrow\texttt{001101100110100110110010011001011001}$

to any ternary squarefree word gives a $\tfrac{7}{3}^{+}$-free binary word
containing at most $25$ palindromes.

∎

###  3.3 Polynomial cases

######  Theorem 4.

[2] Every bi-infinite ternary cubefree word avoiding

$F=\textnormal{\\{{00},{11},{22},{20},{212},{0101},{02102},{121012},{01021010},{21021012102}}\\}$

has the same set of factors as $\bf p$.

######  Lemma 5.

Every bi-infinite cubefree binary word avoiding

$F_{18}=\textnormal{\\{{1101},{00100},{10101},{010011},{1011001011},{110010110011},{1011001010010110010}\\}}$

has the same set of factors as $\mu(\bf p)$.

###### Proof.

Consider a bi-infinite binary cubefree word $\bf w$ avoiding $F_{18}$.
The factors of $\bf w$ of length at least 5 that contain 0101 only as a prefix
and a suffix are 01011001100101, 010100101, and 0101100101. Thus, $\bf w$ is
in
$\left\\{\texttt{0110011001},\texttt{01001},\texttt{011001}\right\\}^{\omega}$.
So, $\bf w$ is in
$\left\\{\texttt{011001},\texttt{1001},\texttt{0}\right\\}^{\omega}$. That is,
$\bf w=\mu(\bf v)$ for some bi-infinite ternary word $\bf v$. Since $\bf w$ is
cubefree, its pre-image $\bf v$ is also cubefree.

To show that $\bf v$ avoids $F$, we consider every $f\in F$ and we show by
contradiction that $f$ is not a factor of $\bf v$.

  1. (a)

If $\bf v$ contains 22, then $\mu(\texttt{220})=\texttt{00011001}$ and
$\mu(\texttt{222})=\texttt{000}$ contain $\texttt{0}^{3}$ and
$\mu(\texttt{221})=\texttt{001001}$ contains $\texttt{00100}\in F_{18}$.

  2. (b)

If $\bf v$ contains 20, then $\bf v$ contains $x\texttt{20}$ for
$x\in\left\\{\texttt{0},\texttt{1}\right\\}$ by (a).
$\mu(x\texttt{20})$ contains 10010011001 as a suffix, which contains
$\texttt{00100}\in F_{18}$.

  3. (c)

If $\bf v$ contains 00, then $\bf v$ contains 100 to avoid the cube 000 and by
(b).
$\mu(\texttt{100})=\texttt{1001011001011001}$ contains $\texttt{1011001011}\in
F_{18}$.

  4. (d)

If $\bf v$ contains 11, then $\mu(\texttt{011})$ and $\mu(\texttt{111})$
contain $(\texttt{1001})^{3}$ and $\mu(\texttt{211})=\texttt{010011001}$
contains $\texttt{010011}\in F_{18}$.

  5. (e)

If $\bf v$ contains 212, then $\bf v$ contains 2121 by (a) and (b).
$\bf v$ contains $x\texttt{2121}y$ with
$x\in\left\\{\texttt{0},\texttt{1}\right\\}$ by (a) and
$y\in\left\\{\texttt{0},\texttt{2}\right\\}$ by (d).
Since $\mu(\texttt{1})$ is a suffix of $\mu(\texttt{0})$ and $\mu(\texttt{2})$
is a prefix of $\mu(\texttt{0})$, then $\mu(x\texttt{2121}y)$ contains the
factor $\mu(\texttt{121212})=\mu\left((\texttt{12})^{3}\right)$.

  6. (f)

If $\bf v$ contains 0101, then
$\mu(\texttt{0101})=\texttt{01100110010110011001}$ contains
$\texttt{110010110011}\in F_{18}$.

  7. (g)

If $\bf v$ contains 02102, then $\bf v$ contains 102102 by (b) and (c).
$\mu(\texttt{102102})=\texttt{1001011001010010110010}$ contains
$\texttt{1011001010010110010}\in F_{18}$.

  8. (h)

If $\bf v$ contains 121012, then $\bf v$ contains 0121012 by (d) and (e).
$\bf v$ contains 10121012 by (b) and (c).
$\bf v$ contains 210121012 by (d) and (f).
$\bf v$ contains 2101210121 by (a) and (b).
$\bf v$ contains 21012101210 by (d) and (e).
$\bf v$ contains $x\texttt{21012101210}$ with
$x\in\left\\{\texttt{0},\texttt{1}\right\\}$ by (a).
Since $\mu(\texttt{1})$ is a suffix of $\mu(\texttt{0})$, then
$\mu(x\texttt{21012101210})$ contains
$\mu(\texttt{121012101210})=\mu\left((\texttt{1210})^{3}\right)$.

  9. (i)

If $\bf v$ contains 01021010, then $\bf v$ contains 010210102 by (c) and (f).
$\bf v$ contains 0102101021 by (a) and (b).
$\bf v$ contains 01021010210 by (d) and (e).
$\bf v$ contains 010210102101 by (c) and (g).
$\bf v$ contains 1010210102101 by (b) and (c).
$\bf v$ contains 21010210102101 by (d) and (f).
$\bf v$ contains 210102101021012 by (d) and to avoid $(\tt 21010)^{3}$.
$\bf v$ contains 1210102101021012 by (a) and to avoid $(\tt 02101)^{3}$.
$\bf w$ contains
$\mu(\texttt{1210102101021012})=\texttt{1001}\mu(\texttt{210})\texttt{1001011001}\mu(\texttt{210})\texttt{1001011001}\mu(\texttt{210})\texttt{10010}$.
To avoid $\texttt{00100}\in F_{18}$, $\bf w$ contains
$\texttt{1001}\mu(\texttt{210})\texttt{1001011001}\mu(\texttt{210})\texttt{1001011001}\mu(\texttt{210})\texttt{100101}=(\texttt{1001}\mu(\texttt{210})\texttt{100101})^{3}$.

  10. (j)

If $\bf v$ contains 21021012102, then $\bf v$ contains 121021012102 by (a) and
(g).
$\bf v$ contains 0121021012102 by (d) and (e).
$\bf v$ contains 10121021012102 by (b) and (c).
$\bf v$ contains 210121021012102 by (d) and (f).
$\bf v$ contains 0210121021012102 by (a) and (h).
$\bf v$ contains 10210121021012102 by (b) and (c).
$\bf v$ contains 102101210210121021 by (a) and (b).
$\bf v$ contains 1021012102101210210 by (d) and (e).
$\bf v$ contains 10210121021012102101 by (c) and (g).
$\bf v$ contains 102101210210121021010 by (d) and to avoid $(\tt
1021012)^{3}$.
$\mu(\texttt{102101210210121021010})=(\mu(\texttt{102101})\texttt{0})^{3}\texttt{11001}$.

∎

######  Lemma 6.

Every bi-infinite cubefree binary word avoiding

$F_{20}=\textnormal{\\{{0101},{1011},{010010},{1100110100110011}\\}}$

has the same set of factors as $\nu(\bf p)$.

###### Proof.

Consider a bi-infinite binary cubefree word $\bf w$ avoiding $F_{20}$. Since
$\bf w$ is cubefree, $\bf w$ is in
$\left\\{\texttt{011},\texttt{0},\texttt{01}\right\\}^{\omega}$. So $\bf
w=\nu(\bf v)$ for some bi-infinite ternary word $\bf v$. Since $\bf w$ is
cubefree, its pre-image $\bf v$ is also cubefree.

To show that $\bf v$ avoids $F$, we consider every $f\in F$ and we show by
contradiction that $f$ is not a factor of $\bf v$.

  1. (a)

If $\bf v$ contains 00, then $\nu(\texttt{00})=\texttt{011011}$ contains
$\texttt{1011}\in F_{20}$.

  2. (b)

If $\bf v$ contains 11, then $\bf v$ contains $\texttt{11}y$ for some letter
$y$.
$\nu(\texttt{11}y)$ contains the cube 000 as a prefix.

  3. (c)

If $\bf v$ contains 22, then $\nu(\texttt{22})=\texttt{0101}\in F_{20}$.

  4. (d)

If $\bf v$ contains 20, then $\nu(\texttt{20})=\texttt{01011}$ contains
$\texttt{0101}\in F_{20}$.

  5. (e)

If $\bf v$ contains 212, then $\bf v$ contains 2121 by (c) and (d).
$\nu(\texttt{2121})=\texttt{010010}\in F_{20}$.

  6. (f)

If $\bf v$ contains 0101, then $\bf v$ contains 10101 by (a) and (d).
$\bf v$ contains 210101 by (b) and to avoid $(\texttt{01})^{3}$.
$\bf v$ contains 2101012 by (b) and to avoid $(\texttt{10})^{3}$.
$\nu(\texttt{2101012})=\texttt{0100110011001}=\texttt{0}(\texttt{1001})^{3}$.

  7. (g)

If $\bf v$ contains 02102, then $\bf v$ contains 102102 by (a) and (d).
$\bf v$ contains 1021021 by (c) and (d).
$\bf v$ contains 10210210 by (b) and (e).
$\bf w$ contains $\nu(\texttt{10210210})=\texttt{0011010011010011}$.
To avoid $\texttt{0}^{3}$ and $\texttt{1}^{3}$, $\bf w$ contains
$\texttt{100110100110100110}=(\texttt{100110})^{3}$.

  8. (h)

If $\bf v$ contains 121012, then $\bf v$ contains 0121012 by (b) and (e).
$\bf v$ contains 10121012 by (a) and (d).
$\bf v$ contains 210121012 by (b) and (f).
$\bf v$ contains 2101210121 by (c) and (d).
$\bf v$ contains 21012101210 by (b) and (e).
$\bf w$ contains $\nu(\texttt{21012101210})=\texttt{01001100100110010011}$.
To avoid $\texttt{1}^{3}$, $\bf w$ contains
$\texttt{010011001001100100110}=(\texttt{0100110})^{3}$.

  9. (i)

If $\bf v$ contains 01021010, then
$\nu(\texttt{01021010})=\texttt{01100110100110011}$ contains
$\texttt{1100110100110011}\in F_{20}$.

  10. (j)

If $\bf v$ contains 21021012102, then $\bf v$ contains 121021012102 by (c) and
(g).
$\bf v$ contains 0121021012102 by (b) and (e).
$\bf v$ contains 10121021012102 by (a) and (d).
$\bf v$ contains 210121021012102 by (b) and (f).
$\bf v$ contains 0210121021012102 by (c) and (h).
$\bf v$ contains 10210121021012102 by (a) and (d).
$\bf v$ contains 102101210210121021 by (c) and (d).
$\bf v$ contains 1021012102101210210 by (b) and (e).
$\bf v$ contains 10210121021012102101 by (a) and (g).
$\bf v$ contains 102101210210121021010 by (b) and to avoid $(\tt
1021012)^{3}$.
$\nu(\texttt{102101210210121021010})=(\texttt{0011010011001})^{3}\texttt{1}$.

∎

######  Theorem 7.

  1. (a)

The word $\mu({\bf p})$ is $\tfrac{28}{11}^{+}$-free and contains $18$
palindromes. Every bi-infinite $\tfrac{13}{5}$-free binary word containing at
most $18$ palindromes has the same set of factors as either $\mu({\bf p})$,
$\overline{\mu({\bf p})}$, $\mu({\bf p})^{R}$, or $\overline{\mu({\bf
p})^{R}}$.

  2. (b)

The word $\nu({\bf p})$ is $\tfrac{5}{2}^{+}$-free and contains $20$
palindromes. Every recurrent $\tfrac{28}{11}$-free binary word containing at
most $20$ palindromes has the same set of factors as either $\nu({\bf p})$,
$\overline{\nu({\bf p})}$, $\nu({\bf p})^{R}$, or $\overline{\nu({\bf
p})^{R}}$.

###### Proof.

  1. (a)

We prove in Section 4.3 that $\mu({\bf p})$ is $\tfrac{28}{11}^{+}$-free.

We construct the set $S_{18}^{20}$ defined as follows: a word $v$ is in
$S_{18}^{20}$ if and only if there exists a $\tfrac{13}{5}$-free binary word
$pvs$ containing at most $18$ palindromes and such that $|p|=|v|=|s|=20$. From
$S_{18}^{20}$, we construct the Rauzy graph $R_{18}^{20}$ such that the
vertices are the factors of length 19 and the arcs are the factors of length
20. We notice that $R_{18}^{20}$ is disconnected. It contains four connected
components that are symmetric with respect to reversal and bit complement. Let
$C_{18}^{20}$ be the connected component which avoids the factor 1101. We
check that $C_{18}^{20}$ is identical to the Rauzy graph of the factors of
length 19 and 20 of $\mu(\bf p)$.

Now we consider a bi-infinite $\tfrac{13}{5}$-free binary word $\bf w$ with
$18$ palindromes. So $\bf w$ corresponds to a walk in one of the connected
components of $R_{18}^{20}$, say $C_{18}^{20}$ without loss of generality. By
the previous remark, $\bf w$ has the same set of factors of length 20 as
$\mu(\bf p)$. Since $\max\left\\{|f|,f\in F_{18}\right\\}=19\leqslant 20$,
$\bf w$ avoids every factor in $F_{18}$. Moreover, $\bf w$ is cubefree since
it is $\tfrac{13}{5}$-free. By Lemma 5, $\bf w$ has the same factor set as
$\mu(\bf p)$.

Then the proof is complete by symmetry by reversal and bit complement.

  2. (b)

We prove in Section 4.2 that $\nu({\bf p})$ is $\tfrac{5}{2}^{+}$-free.

We construct the set $S_{20}^{78}$ defined as follows: a word $v$ is in
$S_{20}^{78}$ if and only if there exists a $\tfrac{28}{11}$-free binary word
$pvs$ containing at most $20$ palindromes and such that $|p|=|v|=|s|=78$. From
$S_{20}^{78}$, we construct the Rauzy graph $R_{20}^{78}$ such that the
vertices are the factors of length 77 and the arcs are the factors of length
78. We notice that $R_{20}^{78}$ is not strongly connected. It contains four
strongly connected components that are symmetric with respect to reversal and
bit complement. Let $C_{20}^{78}$ be the strongly connected component which
avoids the factor 1011. We check that $C_{20}^{78}$ is identical to the Rauzy
graph of the factors of length 77 and 78 of $\nu({\bf p})$.

Now we consider a recurrent $\tfrac{28}{11}$-free binary word $\bf w$ with
$20$ palindromes. Since $\bf w$ is recurrent, $\bf w$ corresponds to a walk in
one of the strongly connected components of $R_{20}^{78}$, say $C_{20}^{78}$
without loss of generality. By the previous remark, $\bf w$ has the same set
of factors of length 78 as $\nu(\bf p)$. Since $\max\left\\{|f|,f\in
F_{20}\right\\}=16\leqslant 78$, $\bf w$ avoids every factor in $F_{20}$.
Moreover, $\bf w$ is cubefree since it is $\tfrac{28}{11}$-free. By Lemma 6,
$\bf w$ has the same factor set as $\nu({\bf p})$.

Then the proof is complete by symmetry by reversal and bit complement.

∎

Notice that item (b) requires recurrent words rather than bi-infinite words.
That is because of, e.g., the bi-infinite word ${\bf x}=\nu({\bf
p})^{R}\texttt{010110}\nu({\bf p})$. Obviously $\nu({\bf p})$ and $\nu({\bf
p})^{R}$ have the same set of 20 palindromes and it is easy to check that
${\bf x}$ contains no additional palindrome. We show that ${\bf x}$ is
$\tfrac{5}{2}^{+}$-free by checking the central factor of ${\bf x}$ of length
200. Then larger repetitions of exponent $>\tfrac{5}{2}$ are ruled out since
the word 110011001001101 is a prefix of $\texttt{110}\nu(\bf p)$ but is
neither a factor of $\nu(\bf p)$ nor $\nu(\bf p)^{R}$. By symmetry, this also
holds for ${\bf x}^{R}=\nu({\bf\bf p})^{R}\texttt{011010}\nu({\bf p})$,
$\overline{\bf x}$, and $\overline{{\bf x}^{R}}$.

##  4 The critical exponent of $\nu(\bf p)$ and $\mu(\bf p)$

Before recalling the definition of the infinite words $\bf p$, $\nu(\bf p)$
and $\mu(\bf p)$, let us underline that all of them are uniformly recurrent
and $\nu(\bf p)$ and $\mu(\bf p)$ are morphic images of $\bf p$. Hence in
order to compute their (asymptotic) critical exponents, we will exploit the
following two useful statements.

######  Theorem 8 ([4]).

Let $\bf{u}$ be a uniformly recurrent aperiodic infinite word. 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
$\bf{u}$. Then

${E}(\mathbf{u})=1+\sup\limits_{n\in\mathbb{N}}\left\\{\frac{|w_{n}|}{|r_{n}|}\right\\}\qquad\text{and}\qquad{E}^{*}(\mathbf{u})=1+\limsup\limits_{n\to+\infty}\frac{|w_{n}|}{|r_{n}|}\,.$
(1)

######  Theorem 9.

Let ${\bf u}$ be an infinite word over an alphabet $\mathcal{A}$ such that the
uniform letter frequencies in ${\bf u}$ exist. Let
$\psi:{\mathcal{A}}^{*}\to{\mathcal{B}}^{*}$ be an injective morphism and let
$L\in\mathbb{N}$ be such that every factor $v$ of $\psi({\bf u})$, $|v|\geq
L$, has a synchronization point. Then $E^{*}({{\bf u}})=E^{*}(\psi({{\bf
u}}))$.

###### Proof.

The inequality $E^{*}(\psi({{\bf u}}))\geq E^{*}({{\bf u}})$ is proven in [5]
for any non-erasing morphism under the assumption of existence of uniform
letter frequencies in ${\bf u}$. Let us prove the opposite inequality.
According to the definition of $E^{*}(\psi({\bf u}))$, there exist sequences
$\bigl{(}w_{n}\bigr{)}$ and $\bigl{(}v_{n}\bigr{)}$ such that

  1. 1.

$\lim\limits_{n\to\infty}|v_{n}|=\infty$;

  2. 2.

$w_{n}$ is a factor of $\psi({\bf u})$ for each $n\in\mathbb{N}$;

  3. 3.

$w_{n}$ is a prefix of the periodic word $\bigl{(}v_{n}\bigr{)}^{\omega}$ for
each $n\in\mathbb{N}$;

  4. 4.

$E^{*}(\psi({{\bf u}}))=\lim\limits_{n\to\infty}\frac{|w_{n}|}{|v_{n}|}$.

If $E^{*}(\psi({{\bf u}}))=1$, then, clearly, $E^{*}(\psi({{\bf u}}))\leq
E^{*}({{\bf u}})$. Assume in the sequel that $E^{*}(\psi({{\bf u}}))>1$, then
we have for large enough $n$ that $|w_{n}|>|v_{n}|$ and moreover, by the first
item, $|v_{n}|\geq L$. By assumption, both $v_{n}$ and $w_{n}$ have
synchronization points and since $v_{n}$ is a prefix of $w_{n}$ for large
enough $n$, we may write

$w_{n}=x_{n}\bullet\psi(w^{\prime}_{n})\bullet y_{n}\quad\text{and}\quad
v_{n}=x_{n}\bullet\psi(v^{\prime}_{n})\bullet z_{n}\,,$

where we highlighted the first and the last synchronization point (not
necessarily distinct) in $w_{n}$ and $v_{n}$ and where $w^{\prime}_{n}$ and
$v^{\prime}_{n}$ are uniquely given factors of ${\bf u}$ and the lengths of
$x_{n}$, $y_{n}$, $z_{n}$ are smaller than $L$.

By the third item, we have

$w_{n}=v_{n}^{k}u_{n}=(x_{n}\psi(v^{\prime}_{n})z_{n})^{k}u_{n}\,,$

where $u_{n}$ is a proper prefix of $v_{n}$ and $k\in\mathbb{N},k\geq 1$.

There are two possible cases for $(u_{n})$.

  1. (a)

Either $(u_{n})$ is bounded, but as $E^{*}(\psi({{\bf u}}))>1$, it follows
that $k\geq 2$ for large enough $n$.

  2. (b)

Or there is a subsequence $(u_{j_{n}})$ of $(u_{n})$ such that for all
$n\in\mathbb{N}$ we have $|u_{j_{n}}|\geq L$. Then by assumption, $u_{j_{n}}$
has a synchronization point and we may write
$u_{j_{n}}=x_{j_{n}}\bullet\psi(u^{\prime}_{j_{n}})\bullet y_{j_{n}}$, where
we highlighted the first and the last synchronization point in $u_{j_{n}}$ and
$u^{\prime}_{j_{n}}$ is a prefix of $v^{\prime}_{j_{n}}$ by injectivity of
$\psi$.

  1. (a)

In the first case, since $k\geq 2$ for large enough $n$, the factor $w_{n}$
starts in $(x_{n}\psi(v^{\prime}_{n})z_{n})^{2}$. By definition of
synchronization points and injectivity of $\psi$, there exists a unique factor
$t_{n}$ of ${\bf u}$ such that $\psi(v^{\prime}_{n})z_{n}x_{n}=\psi(t_{n})$.
Consequently,
$w_{n}=(x_{n}\psi(v^{\prime}_{n})z_{n})^{k}u_{n}=x_{n}\psi(t_{n}^{k-1}v^{\prime}_{n})z_{n}u_{n}$.
Therefore, $t_{n}^{k-1}v^{\prime}_{n}$ is a factor of ${\bf u}$ and it is a
prefix of $(t_{n})^{\omega}$ and

$E^{*}(\psi({{\bf
u}}))=\lim\limits_{n\to\infty}\frac{|w_{n}|}{|v_{n}|}=\lim\limits_{n\to\infty}\frac{|x_{n}\psi({t_{n}}^{k-1}v^{\prime}_{n})z_{n}u_{n}|}{|\psi(t_{n})|}=\lim\limits_{n\to\infty}\frac{|\psi({t_{n}}^{k-1}v^{\prime}_{n})|}{|\psi(t_{n})|}\,,$

where the last equality holds thanks to boundedness of $(x_{n}),(z_{n})$ and
$(u_{n})$.

  2. (b)

In the second case,
$w_{j_{n}}=(x_{j_{n}}\psi(v^{\prime}_{j_{n}})z_{j_{n}})^{k}x_{j_{n}}\psi(u^{\prime}_{j_{n}})y_{j_{n}}$,
where $k\geq 1$. By definition of synchronization points and injectivity of
$\psi$, there exists a unique factor $t_{j_{n}}$ of ${\bf u}$ such that
$\psi(v^{\prime}_{j_{n}})z_{j_{n}}x_{j_{n}}=\psi(t_{j_{n}})$. Consequently,
$(t_{j_{n}})^{k}u^{\prime}_{j_{n}}$ is a factor of ${\bf u}$ and it is a
prefix of $(t_{j_{n}})^{\omega}$ and

$E^{*}(\psi({{\bf
u}}))=\lim\limits_{n\to\infty}\frac{|w_{n}|}{|v_{n}|}=\lim\limits_{n\to\infty}\frac{|x_{j_{n}}\psi\bigl{(}({t_{j_{n}}})^{k}u^{\prime}_{j_{n}}\bigr{)}y_{j_{n}}|}{|\psi(t_{j_{n}})|}=\lim\limits_{n\to\infty}\frac{|\psi\bigl{(}({t_{j_{n}}})^{k}u^{\prime}_{j_{n}}\bigr{)}|}{|\psi(t_{j_{n}})|}\,,$

where the last equality holds thanks to boundedness of $(x_{n})$ and
$(y_{n})$.

Combining two simple facts:

  * •

$\frac{|\psi(u)|}{|u|}={\vec{1}\hskip
0.28436pt}^{T}M_{\psi}\frac{\vec{u}}{|u|}$ for each word $u$ over
$\mathcal{A}$, where $\vec{1}$ is a vector with all coordinates equal to one;

  * •

for each sequence $(s_{n})$ of factors of ${\bf u}$ with
$\lim_{n\to\infty}|s_{n}|=\infty$ we have, by uniform letter frequencies in
${\bf u}$, $\lim\limits_{n\to\infty}\frac{\vec{s_{n}}}{|s_{n}|}=\vec{f}\,$,
where $\vec{f}$ is the vector of letter frequencies in ${\bf u}$,

we obtain

$\lim_{n\to\infty}\frac{|\psi(s_{n})|}{|s_{n}|}={\vec{1}\hskip
0.28436pt}^{T}M_{\psi}\vec{f}\,.$ (2)

Consequently,

  1. (a)

in the first case, since $\lim_{n\to\infty}|t_{n}|=\infty$, we obtain using
(2)

$\begin{array}[]{rcl}E^{*}(\psi({{\bf
u}}))&=&\lim\limits_{n\to\infty}\frac{|\psi({t_{n}}^{k-1}v^{\prime}_{n})|}{|\psi(t_{n})|}\\\
&=&\lim\limits_{n\to\infty}\frac{|\psi({t_{n}}^{k-1}v^{\prime}_{n})|}{|{t_{n}}^{k-1}v^{\prime}_{n}|}\frac{|t_{n}|}{|\psi(t_{n})|}\frac{|{t_{n}}^{k-1}v^{\prime}_{n}|}{|t_{n}|}\\\
&=&\lim\limits_{n\to\infty}\frac{|{t_{n}}^{k-1}v^{\prime}_{n}|}{|t_{n}|}\leq
E^{*}({\bf u})\,,\end{array}$

where the last inequality follows from the fact that
${(t_{n})}^{k-1}v^{\prime}_{n}\in{\mathcal{L}}({\bf u})$ and
${(t_{n})}^{k-1}v^{\prime}_{n}$ is a power of $t_{n}$;

  2. (b)

in the second case, since $\lim|t_{j_{n}}|=\infty$, we obtain using (2)

$\begin{array}[]{rcl}E^{*}(\psi({{\bf
u}}))&=&\lim\limits_{n\to\infty}\frac{|\psi\bigr{(}{(t_{j_{n}})}^{k}u^{\prime}_{j_{n}}\bigl{)}|}{|\psi(t_{j_{n}})|}\\\
&=&\lim\limits_{n\to\infty}\frac{|\psi\bigl{(}{(t_{j_{n}}})^{k}u^{\prime}_{j_{n}}\bigr{)}|}{|{(t_{j_{n}}})^{k}u^{\prime}_{j_{n}}|}\frac{|t_{j_{n}}|}{|\psi(t_{j_{n}})|}\frac{|({t_{j_{n}}})^{k}u^{\prime}_{j_{n}}|}{|t_{j_{n}}|}\\\
&=&\lim\limits_{n\to\infty}\frac{|({t_{j_{n}}})^{k}u^{\prime}_{j_{n}}|}{|t_{j_{n}}|}\leq
E^{*}({\bf u})\,,\par\end{array}$

where the last inequality follows from the fact that
${(t_{j_{n}})}^{k}u^{\prime}_{j_{n}}\in{\mathcal{L}}({\bf u})$ and
${(t_{j_{n}})}^{k}u^{\prime}_{j_{n}}$ is a power of $t_{j_{n}}$.

∎

###  4.1 The infinite word $\bf p$

In order to compute the critical exponent of morphic images of $\bf p$, it is
essential to describe bispecial factors and their return words in $\bf p$ and
to determine the asymptotic critical exponent of $\bf p$.

The infinite word $\bf p$ is the fixed point of the injective morphism
$\varphi$, where

$\displaystyle\varphi(\texttt{0})$ $\displaystyle=\texttt{01},$
$\displaystyle\varphi(\texttt{1})$ $\displaystyle=\texttt{21},$
$\displaystyle\varphi(\texttt{2})$ $\displaystyle=\texttt{0}.$

Therefore, $\bf p$ has the following prefix

${\bf p}=\texttt{01210210102101210102101210210121010}\cdots$

######  Remark 10.

It is readily seen that each non-empty factor of $\bf p$ has a synchronization
point.

The following characteristics of $\bf p$ are known [2]:

  * •

The factor complexity of $\bf p$ is $C(n)=2n+1$.

  * •

The word $\bf p$ is not closed under reversal: $\texttt{02}\in\mathcal{L}(\bf
p)$, but $\texttt{20}\notin\mathcal{L}(\bf p)$.

  * •

The word $\bf p$ is uniformly recurrent and $\bf p$ has uniform letter
frequencies because $\varphi$ is primitive.

####  4.1.1 Bispecial factors in $\bf p$

First, we will examine LS factors. Using the form of $\varphi$, we observe

  * •

0 has only one left extension: 1,

  * •

1 has two left extensions: 0 and 2,

  * •

2 has two left extensions: 0 and 1.

Therefore, every LS factor has left extensions either $\\{\tt 0,2\\}$, or
$\\{\tt 0,1\\}$.

######  Lemma 11.

Let $w\neq\varepsilon$, $w\in\mathcal{L}(\bf p)$.

  * •

If $w$ is a LS factor such that ${\tt{0}}w,{\tt{1}}w\in\mathcal{L}(\bf p)$,
then ${\tt 1}\varphi(w)$ is a LS factor such that ${\tt 01}\varphi(w),{\tt
21}\varphi(w)\in\mathcal{L}(\bf p)$.

  * •

If $w$ is a LS factor such that ${\tt 0}w,{\tt 2}w\in\mathcal{L}(\bf p)$, then
$\varphi(w)$ is a LS factor such that ${\tt 0}\varphi(w),{\tt
1}\varphi(w)\in\mathcal{L}(\bf p)$.

###### Proof.

It follows from the form of $\varphi$ and the fact that $\bf p$ is the fixed
point of the morphism $\varphi$, i.e., if $u\in\mathcal{L}(\bf p)$, then
$\varphi(u)\in\mathcal{L}(\bf p)$. ∎

Second, we will focus on RS factors. We observe

  * •

0 has two right extensions: 1 and 2,

  * •

1 has two right extensions: 0 and 2,

  * •

2 has only one right extension: 1.

Therefore, every RS factor has right extensions either $\\{\tt 1,2\\}$, or
$\\{\tt 0,2\\}$. Using similar arguments as for LS factors, we get the
following statement.

######  Lemma 12.

Let $w\neq\varepsilon$, $w\in\mathcal{L}(\bf p)$.

  * •

If $w$ is a RS factor such that $w{\tt 0},w{\tt 2}\in\mathcal{L}(\bf p)$, then
$\varphi(w){\tt 0}$ is a RS factor such that $\varphi(w){\tt
01},\varphi(w){\tt 02}\in\mathcal{L}(\bf p)$.

  * •

If $w$ is a RS factor such that $w{\tt 1},w{\tt 2}\in\mathcal{L}(\bf p)$, then
$\varphi(w)$ is a RS factor such that $\varphi(w){\tt 2},\varphi(w){\tt
0}\in\mathcal{L}(\bf p)$.

It follows from the form of LS and RS factors that we have at most 4 possible
kinds of non-empty BS factors in $\bf p$.

######  Proposition 13.

Let $v$ be a non-empty BS factor in $\bf p$.

  1. 1.

${\tt 0}v,{\tt 2}v,v{\tt 0},v{\tt 2}\in\mathcal{L}(\bf p)$ if and only if
there exists $w\in\mathcal{L}(\bf p)$ such that $v={\tt 1}\varphi(w)$ and
${\tt 0}w,{\tt 1}w,w{\tt 1},w{\tt 2}\in\mathcal{L}(\bf p)$.

  2. 2.

${\tt 0}v,{\tt 1}v,v{\tt 1},v{\tt 2}\in\mathcal{L}(\bf p)$ if and only if
there exists $w\in\mathcal{L}(\bf p)$ such that $v=\varphi(w){\tt 0}$ and
${\tt 0}w,{\tt 2}w,w{\tt 0},w{\tt 2}\in\mathcal{L}(\bf p)$.

  3. 3.

${\tt 0}v,{\tt 2}v,v{\tt 1},v{\tt 2}\in\mathcal{L}(\bf p)$ if and only if
there exists $w\in\mathcal{L}(\bf p)$ such that $v={\tt 1}\varphi(w){\tt 0}$
and ${\tt 0}w,{\tt 1}w,w{\tt 0},w{\tt 2}\in\mathcal{L}(\bf p)$.

  4. 4.

${\tt 0}v,{\tt 1}v,v{\tt 0},v{\tt 2}\in\mathcal{L}(\bf p)$ if and only if
there exists $w\in\mathcal{L}(\bf p)$ such that $v=\varphi(w)$ and ${\tt
0}w,{\tt 2}w,w{\tt 1},w{\tt 2}\in\mathcal{L}(\bf p)$.

###### Proof.

The implication $(\Leftarrow)$ follows from Lemmata 11 and 12. We will prove
the opposite implication for Item 1, the other cases may be proven
analogously. If $v$ is a non-empty factor such that ${\tt 0}v,{\tt 2}v,v{\tt
0},v{\tt 2}\in\mathcal{L}(\bf p)$, then $v$ necessarily starts and ends with
the letter ${\tt 1}$. By the form of $\varphi$, we have the following
synchronization points $v={\tt 1}\bullet\hat{v}\bullet$ ($\hat{v}$ may be
empty). Hence, by injectivity of $\varphi$, there exists a unique $w$ in $\bf
p$ such that $v={\tt 1}\varphi(w)$. Thus, using again the form of $\varphi$
and the knowledge of possible right extensions, the factor $w$ is BS and ${\tt
0}w,{\tt 1}w,w{\tt 1},w{\tt 2}\in\mathcal{L}(\bf p)$. ∎

We can see that the only BS factor of length one is ${\tt 1}$, it has left
extensions ${\tt 0,2}$ and right extensions ${\tt 0,2}$. Applying Proposition
13 Item 2, we obtain that $\varphi({\tt 1}){\tt 0}$ is BS with left extensions
${\tt 0,1}$ and right extensions ${\tt 1,2}$. Proposition 13 Item 1 gives us
that ${\tt 1}\varphi^{2}({\tt 1})\varphi({\tt 0})$ is BS with left extensions
${\tt 0,2}$ and right extensions ${\tt 0,2}$. This process can be iterated
providing us with infinitely many BS factors:

$\begin{array}[]{l}{\tt 1}\to\varphi({\tt 1}){\tt 0}\to{\tt 1}\varphi^{2}({\tt
1})\varphi({\tt 0})\to\varphi({\tt 1})\varphi^{3}({\tt 1})\varphi^{2}({\tt
0}){\tt 0}\to\\\ \to{\tt 1}\varphi^{2}({\tt 1})\varphi^{4}({\tt
1})\varphi^{3}(\texttt{{\tt 0}})\varphi({\tt 0})\to\varphi({\tt
1})\varphi^{3}({\tt 1})\varphi^{5}({\tt 1})\varphi^{4}({\tt
0})\varphi^{2}({\tt 0}){\tt 0}\dots\end{array}$ (3)

The only BS factor of length two is ${\tt 10}$, it has left extensions ${\tt
0,2}$ and right extensions ${\tt 1,2}$. Applying Proposition 13 Item 4, we
obtain that $\varphi({\tt 1})\varphi({\tt 0})$ is BS with left extensions
${\tt 0,1}$ and right extensions ${\tt 0,2}$. Proposition 13 Item 3 gives us
that ${\tt 1}\varphi^{2}({\tt 1})\varphi^{2}({\tt 0}){\tt 0}$ is BS with left
extensions ${\tt 0,2}$ and right extensions ${\tt 1,2}$. This process can be
iterated providing us again with infinitely many BS factors:

$\begin{array}[]{l}{\tt 10}\to\varphi({\tt 1})\varphi({\tt 0})\rightarrow{\tt
1}\varphi^{2}({\tt 1})\varphi^{2}({\tt 0}){\tt 0}\to\varphi({\tt
1})\varphi^{3}({\tt 1})\varphi^{3}({\tt 0})\varphi({\tt 0})\to\\\ \to{\tt
1}\varphi^{2}({\tt 1})\varphi^{4}({\tt 1})\varphi^{4}({\tt 0})\varphi^{2}({\tt
0}){\tt 0}\to\varphi({\tt 1})\varphi^{3}({\tt 1})\varphi^{5}({\tt
1})\varphi^{5}({\tt 0})\varphi^{3}({\tt 0})\varphi({\tt 0})\dots\end{array}$
(4)

Each BS factor $v$ of length greater than two has at least two synchronization
points and the corresponding BS factor $w$ from Proposition 13 is non-empty.
In other words, the BS factor $v$ makes part of one of the sequences (3) and
(4) of BS factors.

As a consequence of Proposition 13 and the above arguments, we get a complete
description of BS factors in $\bf p$.

######  Corollary 14.

Let $w$ be a non-empty BS factor in $\bf p$. Then it has one of the following
forms:

  * $(\mathcal{A})$

$w_{A}^{(n)}={\tt 1}\varphi^{2}({\tt 1})\varphi^{4}({\tt
1})\cdots\varphi^{2n}({\tt 1})\varphi^{2n-1}({\tt 0})\varphi^{2n-3}({\tt
0})\cdots\varphi({\tt 0})$

for $n\geq 1$. If $n=0$, then we set $w_{A}^{(0)}={\tt 1}$.

The Parikh vector of $w_{A}^{(n)}$ is the same as of the word ${\tt
1}\varphi({\tt 012})\varphi^{3}({\tt 012})\dots\varphi^{2n-1}({\tt 012})$.

  * $(\mathcal{B})$

$w_{B}^{(n)}=\varphi({\tt 1})\varphi^{3}({\tt 1})\cdots\varphi^{2n+1}({\tt
1})\varphi^{2n}({\tt 0})\varphi^{2n-2}({\tt 0})\cdots\varphi^{2}({\tt 0}){\tt
0}$

for $n\geq 0$.

The Parikh vector of $w_{B}^{(n)}$ is the same as of the word ${\tt
012}\varphi^{2}({\tt 012})\varphi^{4}({\tt 012})\dots\varphi^{2n}({\tt 012})$.

  * $(\mathcal{C})$

$w_{C}^{(n)}={\tt 1}\varphi^{2}({\tt 1})\varphi^{4}({\tt
1})\cdots\varphi^{2n}({\tt 1})\varphi^{2n}({\tt 0})\varphi^{2n-2}({\tt
0})\cdots\varphi^{2}({\tt 0}){\tt 0}$

for $n\geq 0$.

The Parikh vector of $w_{C}^{(n)}$ is the same as of the word ${\tt
01}\varphi^{2}({\tt 01})\varphi^{4}({\tt 01})\dots\varphi^{2n}({\tt 01})$.

  * $(\mathcal{D})$

$w_{D}^{(n)}=\varphi({\tt 1})\varphi^{3}({\tt 1})\cdots\varphi^{2n+1}({\tt
1})\varphi^{2n+1}({\tt 0})\varphi^{2n-1}({\tt 0})\cdots\varphi({\tt 0})$

for $n\geq 0$.

The Parikh vector of $w_{D}^{(n)}$ is the same as of the word $\varphi({\tt
01})\varphi^{3}({\tt 01})\dots\varphi^{2n+1}({\tt 01})$.

######  Lemma 15.

All BS factors in $\bf p$ are ordinary.

###### Proof.

The empty word is ordinary because all factors of length two are $\tt
10,01,02,12,21$. Thus $b(\varepsilon)=5-3-3+1=0$. It is easy to verify that
each non-empty BS factor $w$ has three extensions. In particular,

  * •

extensions of $w=w_{A}^{(n)}$ are: ${\tt 0}w{\tt 2},{\tt 2}w{\tt 0},{\tt
0}w{\tt 0}$,

  * •

extensions of $w=w_{B}^{(n)}$ are: ${\tt 2}w{\tt 2},{\tt 2}w{\tt 1},{\tt
0}w{\tt 2}$,

  * •

extensions of $w=w_{C}^{(n)}$ are: ${\tt 0}w{\tt 0},{\tt 0}w{\tt 2},{\tt
1}w{\tt 0}$,

  * •

extensions of $w=w_{D}^{(n)}$ are: ${\tt 1}w{\tt 2},{\tt 0}w{\tt 1},{\tt
1}w{\tt 1}$.

Consequently, $b(w)=3-2-2+1=0$.

∎

####  4.1.2 The shortest return words to bispecial factors in $\bf p$

Each factor of $\bf p$ has 3 return words. This claim follows from the next
theorem.

######  Theorem 16 (Theorem 5.7 in [1]).

Let $\bf{u}$ be a uniformly recurrent infinite word. Then each factor of
$\bf{u}$ has exactly 3 return words if and only if $C(n)=2n+1$ and $\bf{u}$
has no weak BS factors.

Let us first comment on return words to the shortest BS factors – observe the
prefix of $\bf p$ at the beginning of this section.

  * •

The return words to $\varepsilon$ are ${\tt 0,1,2}$.

  * •

The return words to ${\tt 1}$ are ${\tt 12,102,10}$.

  * •

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

  * •

The return words to ${\tt 10}$ are ${\tt 10}$, ${\tt 102}$, ${\tt 1012}$. The
shortest one is ${\tt 10}$ and it is a prefix of all of them.

######  Lemma 17.

If $w$ is a non-empty BS factor of $\bf p$ and $v$ is its return word, then
$\varphi(v)$ is a return word to $\varphi(w)$.

###### Proof.

On one hand, since $vw$ contains $w$ as a prefix and as a suffix,
$\varphi(v)\varphi(w)$ contains $\varphi(w)$ as a prefix and as a suffix, too.
On the other hand, $w$ starts in ${\tt 1}$ or ${\tt 2}$ and ends in ${\tt 0}$
or ${\tt 1}$, thus $\varphi(w)$ starts in ${\tt 0}$ or ${\tt 2}$ and ends in
${\tt 1}$, therefore it has the following synchronization points
$\bullet\varphi(w)\bullet$. Consequently, $\varphi(v)\varphi(w)$ cannot
contain $\varphi(w)$ somewhere in the middle because in such a case, by
injectivity of $\varphi$, $vw$ would contain $w$ also somewhere in the middle.
∎

The following observation is an immediate consequence of the definition of
return words.

######  Observation 18.

Let $w$ be a factor of $\bf p$ and let $v$ be its return word. If $w$ has a
unique right extension $a$, then $v$ is a return word to $wa$, too. If $w$ has
a unique left extension $b$, then $bvb^{-1}$ is a return word to $bw$. In
particular, the Parikh vectors of the corresponding return words are the same.

######  Example 19.

Consider the BS factor ${\tt 10}$ with the shortest return word ${\tt 10}$
(being a prefix of the other two return words), then by Lemma 17 the BS factor
$\varphi({\tt 1})\varphi({\tt 0})$ has the shortest return word equal to
$\varphi({\tt 10})$. By Lemma 17, the factor $\varphi^{2}({\tt
1})\varphi^{2}({\tt 0})$ has the shortest return word equal to
$\varphi^{2}({\tt 10})$ and by Observation 18, the shortest return word to the
BS factor ${\tt 1}\varphi^{2}({\tt 1})\varphi^{2}({\tt 0}){\tt 0}$ has the
same Parikh vector as $\varphi^{2}({\tt 10})$.

Using Lemma 17, Observation 18 and the knowledge of how the BS factors are
constructed, as illustrated in Example 19, we obtain the following statement
about the shortest return words to BS factors in $\bf p$.

######  Corollary 20.

The shortest return words to BS factors in $\bf p$ have the following
properties.

  * $(\mathcal{A})$

The shortest return words to $w_{A}^{(n)}$ are

    * (i)

${\tt 12}$ and ${\tt 10}$ for $n=0$,

    * (ii)

$r_{A}^{(n)}$ with the same Parikh vector as $\varphi^{2n-1}({\tt 012})$ for
$n\geq 1$.

  * $(\mathcal{B})$

The shortest return word $r_{B}^{(n)}$ to $w_{B}^{(n)}$ has the same Parikh
vector as $\varphi^{2n}({\tt 012})$.

  * $(\mathcal{C})$

The shortest return word to $w_{C}^{(n)}$ is

    * (i)

${\tt 10}$ for $n=0$

    * (ii)

$r_{C}^{(n)}$ with the same Parikh vector as $\varphi^{2n}({\tt 01})$ for
$n\geq 1$.

  * $(\mathcal{D})$

The shortest return word $r_{D}^{(n)}$ to $w_{D}^{(n)}$ has the same Parikh
vector as $\varphi^{2n+1}({\tt 01})$.

####  4.1.3 The asymptotic critical exponent of $\bf p$

Let us determine the asymptotic critical exponent of $\bf p$ using Theorem 8.
We use the form of BS factors and their shortest return words determined
above. We get $E^{*}({\bf
p})=1+\max\\{A^{\prime},B^{\prime},C^{\prime},D^{\prime}\\}$, where

$\displaystyle A^{\prime}$
$\displaystyle=\limsup_{n\to\infty}\frac{|w_{A}^{(n)}|}{|{r}_{A}^{(n)}|}=\limsup_{n\to\infty}\frac{|{\tt
1}\varphi({\tt 012})\varphi^{3}({\tt 012})\dots\varphi^{2n-1}({\tt
012}))|}{|\varphi^{2n-1}({\tt 012})|}\,;$ $\displaystyle B^{\prime}$
$\displaystyle=\limsup_{n\to\infty}\frac{|w_{B}^{(n)}|}{|{r}_{B}^{(n)}|}=\limsup_{n\to\infty}\frac{|{\tt
012}\varphi^{2}({\tt 012})\varphi^{4}({\tt 012})\dots\varphi^{2n}({\tt
012}))|}{|\varphi^{2n}({\tt 012})|}\,;$ $\displaystyle C^{\prime}$
$\displaystyle=\limsup_{n\to\infty}\frac{|w_{C}^{(n)}|}{|{r}_{C}^{(n)}|}=\limsup_{n\to\infty}\frac{|{\tt
01}\varphi^{2}({\tt 01})\varphi^{4}({\tt 01})\dots\varphi^{2n}({\tt
01})|}{|\varphi^{2n}({\tt 01})|}\,;$ $\displaystyle D^{\prime}$
$\displaystyle=\limsup_{n\to\infty}\frac{|w_{D}^{(n)}|}{|{r}_{D}^{(n)}|}=\limsup_{n\to\infty}\frac{|\varphi({\tt
01})\varphi^{3}({\tt 01})\dots\varphi^{2n+1}({\tt 01})|}{|\varphi^{2n+1}({\tt
01})|}\,.$

By the Hamilton-Cayley theorem, we have
$M_{\varphi}^{3}-2M_{\varphi}^{2}+M_{\varphi}-I=0$. Consequently, for each
$w\in\\{{\tt 0,1,2}\\}^{*}$, if we denote
$\ell_{n}:=|\varphi^{n}(w)|=(1,1,1)M_{\varphi}^{n}\vec{w}$, then $\ell_{n}$
satisfies the recurrence relation
$\ell_{n+3}-2\ell_{n+2}+\ell_{n+1}-\ell_{n}=0$. Denote $\beta$ the largest
root of the characteristic polynomial $t^{3}-2t^{2}+t-1$; $\beta\doteq
1.75488$. By the Perron-Frobenius theorem, $\beta$ is strictly larger than the
modulus of the other roots of the characteristic polynomial. We thus obtain:

$\begin{array}[]{rcl}A^{\prime}&=&\lim\limits_{n\to\infty}\cfrac{\sum_{k=1}^{n}\beta^{2k-1}}{\beta^{2n-1}}=\frac{\beta^{2}}{\beta^{2}-1};\\\
&&\\\
B^{\prime}=C^{\prime}&=&\lim\limits_{n\to\infty}\cfrac{\sum_{k=0}^{n}\beta^{2k}}{\beta^{2n}}=\frac{\beta^{2}}{\beta^{2}-1};\\\
&&\\\
D^{\prime}&=&\lim\limits_{n\to\infty}\cfrac{\sum_{k=0}^{n}\beta^{2k+1}}{\beta^{2n+1}}=\frac{\beta^{2}}{\beta^{2}-1}.\\\
\end{array}$

Consequently, $E^{*}({\bf p})=1+\frac{\beta^{2}}{\beta^{2}-1}\doteq 2.48$.

###  4.2 The infinite word $\nu(\bf p)$

The morphism $\nu$ has the form:

$\displaystyle\nu({\tt 0})$ $\displaystyle={\tt 011},$ $\displaystyle\nu({\tt
1})$ $\displaystyle={\tt 0},$ $\displaystyle\nu({\tt 2})$ $\displaystyle={\tt
01}.$

Therefore,

$\nu({\bf p})={\tt 011001001101001100110100110010011}\cdots$

and $\nu$ is injective.

######  Remark 21.

The reader may easily check that any factor of $\nu(\bf p)$ of length at least
two has a synchronization point.

Using the above remark and Theorem 9, we deduce that

$E^{*}(\nu({\bf p}))=E^{*}(\bf p).$

####  4.2.1 Bispecial factors in $\nu(\bf p)$

######  Lemma 22.

Let $v\in\mathcal{L}(\nu(\bf p))$ be a BS factor of length at least two. Then
one of the items holds.

  1. 1.

There exists $w\in\mathcal{L}(\bf p)$ such that $v={\tt 1}\nu(w){\tt 01}$ and
${\tt 0}w,{\tt 2}w,w{\tt 0},w{\tt 2}\in\mathcal{L}(\bf p)$.

  2. 2.

There exists $w\in\mathcal{L}(\bf p)$ such that $v=\nu(w){\tt 0}$ and ${\tt
0}w,{\tt 1}w,w{\tt 1},w{\tt 2}\in\mathcal{L}(\bf p)$.

  3. 3.

There exists $w\in\mathcal{L}(\bf p)$ such that $v={\tt 1}\nu(w){\tt 0}$ and
${\tt 0}w,{\tt 2}w,w{\tt 1},w{\tt 2}\in\mathcal{L}(\bf p)$.

  4. 4.

There exists $w\in\mathcal{L}(\bf p)$ such that $v=\nu(w){\tt 01}$ and ${\tt
0}w,{\tt 1}w,w{\tt 0},w{\tt 2}\in\mathcal{L}(\bf p)$.

###### Proof.

The statement follows from Remark 21 and from the possible left and right
extensions of factors in $\bf p$. ∎

Combining Lemma 22 and Corollary 14, we get a complete description of BS
factors in $\nu(\bf p)$.

######  Corollary 23.

Let $v$ be a non-empty BS factor in $\nu(\bf p)$ of length at least two. Then
$v={\tt 01}$ or $v={\tt 10}$ or $v$ has one of the following forms:

  * $(\mathcal{A})$

$v_{A}^{(n)}={\tt 1}\nu({\tt 1}\varphi^{2}({\tt 1})\varphi^{4}({\tt
1})\cdots\varphi^{2n}({\tt 1})\varphi^{2n-1}({\tt 0})\varphi^{2n-3}({\tt
0})\cdots\varphi({\tt 0})){\tt 01}$

for $n\geq 1$ and $v_{A}^{(0)}={\tt 1}\nu({\tt 1}){\tt 01}={\tt 1001}$.

The Parikh vector of $v_{A}^{(n)}$ is the same as of the word ${\tt
011}\nu({\tt 1}\varphi({\tt 012})\varphi^{3}({\tt
012})\dots\varphi^{2n-1}({\tt 012}))$.

  * $(\mathcal{B})$

$v_{B}^{(n)}=\nu(\varphi({\tt 1})\varphi^{3}({\tt 1})\cdots\varphi^{2n+1}({\tt
1})\varphi^{2n}({\tt 0})\varphi^{2n-2}({\tt 0})\cdots\varphi^{2}({\tt 0}){\tt
0}){\tt 0}$

for $n\geq 0$.

The Parikh vector of $v_{B}^{(n)}$ is the same as of the word ${\tt 0}\nu({\tt
012}\varphi^{2}({\tt 012})\varphi^{4}({\tt 012})\dots\varphi^{2n}({\tt
012}))$.

  * $(\mathcal{C})$

$v_{C}^{(n)}={\tt 1}\nu({\tt 1}\varphi^{2}({\tt 1})\varphi^{4}({\tt
1})\cdots\varphi^{2n}({\tt 1})\varphi^{2n}({\tt 0})\varphi^{2n-2}({\tt
0})\cdots\varphi^{2}({\tt 0}){\tt 0}){\tt 0}$

for $n\geq 0$.

The Parikh vector of $v_{C}^{(n)}$ is the same as of the word ${\tt
01}\nu({\tt 01}\varphi^{2}({\tt 01})\varphi^{4}({\tt
01})\dots\varphi^{2n}({\tt 01}))$.

  * $(\mathcal{D})$

$v_{D}^{(n)}=\nu(\varphi({\tt 1})\varphi^{3}({\tt 1})\cdots\varphi^{2n+1}({\tt
1})\varphi^{2n+1}({\tt 0})\varphi^{2n-1}({\tt 0})\cdots\varphi({\tt 0})){\tt
01}$

for $n\geq 0$.

The Parikh vector of $v_{D}^{(n)}$ is the same as of the word ${\tt
01}\nu(\varphi({\tt 01})\varphi^{3}({\tt 01})\dots\varphi^{2n+1}({\tt 01}))$.

####  4.2.2 The shortest return words to bispecial factors in $\nu(\bf p)$

######  Lemma 24.

If $w$ is a non-empty BS factor in $\bf p$ and $v$ is its return word, then
$\nu(v)$ is a return word to $\nu(w){\tt 0}$.

###### Proof.

On one hand, consider any occurrence of $vw$ and denote $a$ the following
letter, then $\nu(v)\nu(w){\tt 0}$ is a prefix of $\nu(vwa)$. Since $vw$
contains $w$ as a prefix and as a suffix, then $\nu(v)\nu(w){\tt 0}$ contains
$\nu(w){\tt 0}$ as a prefix and as a suffix, too. On the other hand, $w$
starts in ${\tt 1}$ or ${\tt 2}$ and ends in ${\tt 0}$ or ${\tt 1}$, thus
$\nu(w){\tt 0}$ starts in ${\tt 0}$ and ends in ${\tt 0110}$ or ${\tt 00}$,
therefore $\nu(w){\tt 0}$ has the following synchronization points
$\bullet\nu(w)\bullet{\tt 0}$. Consequently, $\nu(v)\nu(w){\tt 0}$ cannot
contain $\nu(w){\tt 0}$ somewhere in the middle because in such a case, by
injectivity of $\nu$, $vw$ would contain $w$ also somewhere in the middle. ∎

Applying Lemma 24 and Observation 18, we have the following description of the
shortest return words to BS factors.

######  Corollary 25.

The shortest return words to BS factors of length at least three in $\nu(\bf
p)$ have the following properties.

  * $(\mathcal{A})$

The shortest return word $\hat{r}_{A}^{(n)}$ to $v_{A}^{(n)}$ has the same
Parikh vector as $\nu(\varphi^{2n-1}({\tt 012}))$ for $n\geq 1$ and ${\tt
100}$ is the shortest return word to $v_{A}^{(0)}={\tt 1001}$.

  * $(\mathcal{B})$

The shortest return word $\hat{r}_{B}^{(n)}$ to $v_{B}^{(n)}$ has the same
Parikh vector as $\nu(\varphi^{2n}({\tt 012}))$.

  * $(\mathcal{C})$

The shortest return word $\hat{r}_{C}^{(n)}$ to $v_{C}^{(n)}$ has the same
Parikh vector as $\nu(\varphi^{2n}({\tt 01}))$.

  * $(\mathcal{D})$

The shortest return word $\hat{r}_{D}^{(n)}$ to $v_{D}^{(n)}$ has the same
Parikh vector as $\nu(\varphi^{2n+1}({\tt 01}))$.

####  4.2.3 The critical exponent of $\nu(\bf p)$

Using Theorem 8 and the description of BS factors from Corollary 23 and of
their shortest return words from Corollary 25, we obtain the following formula
for the critical exponent of $\nu(\bf p)$.

$E(\nu({\bf p}))=1+\max\left\\{A,B,C,D,F\right\\}\,,$

where

$\displaystyle A$
$\displaystyle=\sup\left\\{\frac{|v_{A}^{(n)}|}{|\hat{r}_{A}^{(n)}|}:n\geq
1\right\\}=\sup\left\\{\frac{|{\tt 011}\nu({\tt 1}\varphi({\tt
012})\varphi^{3}({\tt 012})\dots\varphi^{2n-1}({\tt
012}))|}{|\nu(\varphi^{2n-1}({\tt 012}))|}:n\geq
1\right\\}\cup\left\\{\frac{|{\tt 1001}|}{|{\tt 100}|}\right\\}\,;$
$\displaystyle B$
$\displaystyle=\sup\left\\{\frac{|v_{B}^{(n)}|}{|\hat{r}_{B}^{(n)}|}:n\geq
0\right\\}=\sup\left\\{\frac{|{\tt 0}\nu({\tt 012}\varphi^{2}({\tt
012})\varphi^{4}({\tt 012})\dots\varphi^{2n}({\tt
012}))|}{|\nu(\varphi^{2n}({\tt 012}))|}:n\geq 0\right\\}\,;$ $\displaystyle
C$ $\displaystyle=\sup\left\\{\frac{|v_{C}^{(n)}|}{|\hat{r}_{C}^{(n)}|}:n\geq
0\right\\}=\sup\left\\{\frac{|{\tt 01}\nu({\tt 01}\varphi^{2}({\tt
01})\varphi^{4}({\tt 01})\dots\varphi^{2n}({\tt 01}))|}{|\nu(\varphi^{2n}({\tt
01}))|}:n\geq 1\right\\}\cup\left\\{\frac{|{\tt 1}\nu({\tt 10}){\tt
0}|}{|\nu({\tt 10})|}\right\\}\,;$ $\displaystyle D$
$\displaystyle=\sup\left\\{\frac{|v_{D}^{(n)}|}{|\hat{r}_{D}^{(n)}|}:n\geq
0\right\\}=\sup\left\\{\frac{|{\tt 01}\nu(\varphi({\tt 01})\varphi^{3}({\tt
01})\dots\varphi^{2n+1}({\tt 01}))|}{|\nu(\varphi^{2n+1}({\tt 01}))|}:n\geq
0\right\\}\,;$ $\displaystyle F$
$\displaystyle=\max\left\\{\frac{|w|}{|r|}:w\text{\ BS in $\nu(\bf p)$ of
length one or two and $r$ its shortest return word}\right\\}\,.$

######  Theorem 26.

The critical exponent of $\nu({\bf p})$ equals

$E(\nu({\bf p}))=\frac{5}{2}.$

###### Proof.

To evaluate the critical exponent of $\nu(\bf p)$ using the above formula, we
have to do several steps.

  1. 1.

Determining the shortest return words of BS factors of length one and two in
$\nu(\bf p)$:

     * •

0 is a BS factor with the shortest return word 0.

     * •

1 is a BS factor with the shortest return word 1.

     * •

01 is a BS factor with the shortest return words 010, 011.

     * •

10 is a BS factor with the shortest return word 10.

Thus for each BS factor $w$ of length one or two and its shortest return word
$r$ we have $\frac{|w|}{|r|}\leq 1$ and $F=1$.

  2. 2.

Computation of $A$ and $B$.

Denote $c_{n}:=|\nu(\varphi^{n}(012))|$, then it satisfies the recurrence
relation $c_{n+1}=2c_{n}-c_{n-1}+c_{n-2}$ with initial conditions
$c_{0}=6,c_{1}=10$ and $c_{2}=17$.

The explicit solution reads

$c_{n}=A_{1}\beta^{n}+B_{1}\lambda_{1}^{n}+C_{1}\lambda_{2}^{n},$

where

$\beta\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

$\displaystyle A_{1}$
$\displaystyle=\frac{6|\lambda_{1}|^{2}-20\operatorname{Re}(\lambda_{1})+17}{|\beta-\lambda_{1}|^{2}}\doteq
5.581308964\,;$ $\displaystyle B_{1}$
$\displaystyle=\frac{6\beta\lambda_{2}-10(\beta+\lambda_{2})+17}{(\beta-\lambda_{1})(\lambda_{2}-\lambda_{1})}\doteq
0.209345518-0.103481025i\,;$ $\displaystyle C_{1}$
$\displaystyle=\overline{B_{1}}\,.$

Let us show that $A\leq\frac{3}{2}$. Since $\frac{|\tt 1001|}{|\tt
100|}=\frac{4}{3}<\frac{3}{2}$, it remains to show for all $n\geq 1$ that

$\displaystyle\frac{4+A_{1}\sum_{k=1}^{n}\beta^{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^{2n-1}+B_{1}\lambda_{1}^{2n-1}+C_{1}\lambda_{2}^{2n-1}}\quad$
$\displaystyle\leq^{?}\quad\frac{3}{2},$ $\displaystyle
8+2A_{1}\sum_{k=1}^{n}\beta^{2k-1}+4\operatorname{Re}\left(B_{1}\sum_{k=1}^{n}\lambda_{1}^{2k-1}\right)\quad$
$\displaystyle\leq^{?}\quad
3A_{1}\beta^{2n-1}+6\operatorname{Re}(B_{1}\lambda_{1}^{2n-1}),$
$\displaystyle
8+2A_{1}\sum_{k=1}^{n-1}\beta^{2k-1}+4\operatorname{Re}\left(B_{1}\sum_{k=1}^{n-1}\lambda_{1}^{2k-1}\right)\quad$
$\displaystyle\leq^{?}\quad
A_{1}\beta^{2n-1}+2\operatorname{Re}(B_{1}\lambda_{1}^{2n-1}),$ $\displaystyle
8+2A_{1}\left(\frac{\beta^{2n-1}}{\beta^{2}-1}-\frac{\beta}{\beta^{2}-1}\right)+4\operatorname{Re}\left(B_{1}\lambda_{1}\frac{1-\lambda_{1}^{2n-2}}{1-\lambda_{1}^{2}}\right)\quad$
$\displaystyle\leq^{?}\quad
A_{1}\beta^{2n-1}+2\operatorname{Re}(B_{1}\lambda_{1}^{2n-1}).$

Since

$\displaystyle\frac{2}{\beta^{2}-1}$ $\displaystyle\leq 1,$

we need to prove the inequality in the form

$\displaystyle
8+4\operatorname{Re}\left(B_{1}\lambda_{1}\frac{1-\lambda_{1}^{2n-2}}{1-\lambda_{1}^{2}}\right)\quad$
$\displaystyle\leq^{?}\quad
2A_{1}\frac{\beta}{\beta^{2}-1}+2\operatorname{Re}(B_{1}\lambda_{1}^{2n-1}).$

For the left side, we can write for $n\geq 1$

$\displaystyle
8+4\operatorname{Re}\left(B_{1}\lambda_{1}\frac{1-\lambda_{1}^{2n-2}}{1-\lambda_{1}^{2}}\right)\quad$
$\displaystyle\leq\quad
8+4|B_{1}||\lambda_{1}|\frac{|\lambda_{1}|^{2n-2}+1}{|\lambda_{1}^{2}-1|}$
$\displaystyle\leq\quad 8+4|B_{1}||\lambda_{1}|\frac{2}{|\lambda_{1}^{2}-1|}.$

For the right side, we can write for $n\geq 1$

$\displaystyle\quad
2A_{1}\frac{\beta}{\beta^{2}-1}+2\operatorname{Re}(B_{1}\lambda_{1}^{2n-1})\quad$
$\displaystyle\geq\quad
2A_{1}\frac{\beta}{\beta^{2}-1}-2|B_{1}||\lambda_{1}|^{2n-1}$
$\displaystyle\geq\quad
2A_{1}\frac{\beta}{\beta^{2}-1}-2|B_{1}||\lambda_{1}|.$

Since the inequality

$8+4|B_{1}||\lambda_{1}|\frac{2}{|\lambda_{1}^{2}-1|}\quad\leq\quad
2A_{1}\frac{\beta}{\beta^{2}-1}-2|B_{1}||\lambda_{1}|$

holds true for the given values, we obtain $A\leq\frac{3}{2}$.

Next, we will show that $B\leq\frac{3}{2}$.

For all $n\geq 0$ we have to show that

$\displaystyle\frac{1+A_{1}\sum_{k=0}^{n}\beta^{2k}+B_{1}\sum_{k=0}^{n}\lambda_{1}^{2k}+C_{1}\sum_{k=0}^{n}\lambda_{2}^{2k}}{A_{1}\beta^{2n}+B_{1}\lambda_{1}^{2n}+C_{1}\lambda_{2}^{2n}}\quad$
$\displaystyle\leq^{?}\quad\frac{3}{2},$ $\displaystyle
2+2A_{1}\sum_{k=0}^{n-1}\beta^{2k}+4\operatorname{Re}\left(B_{1}\sum_{k=0}^{n-1}\lambda_{1}^{2k}\right)\quad$
$\displaystyle\leq^{?}\quad
A_{1}\beta^{2n}+2\operatorname{Re}\left(B_{1}\lambda_{1}^{2n}\right),$
$\displaystyle
2+2A_{1}\frac{\beta^{2n}-1}{\beta^{2}-1}+4\operatorname{Re}\left(B_{1}\frac{\lambda_{1}^{2n}-1}{\lambda_{1}^{2}-1}\right)\quad$
$\displaystyle\leq^{?}\quad
A_{1}\beta^{2n}+2\operatorname{Re}\left(B_{1}\lambda_{1}^{2n}\right).$

Since

$\displaystyle\frac{2}{\beta^{2}-1}$ $\displaystyle\leq 1,$

we need to prove the inequality in the form

$\displaystyle
2+4\operatorname{Re}\left(B_{1}\frac{\lambda_{1}^{2n}-1}{\lambda_{1}^{2}-1}\right)\quad$
$\displaystyle\leq^{?}\quad
A_{1}\frac{2}{\beta^{2}-1}+2\operatorname{Re}\left(B_{1}\lambda_{1}^{2n}\right).$

For the left side, we can write for $n\geq 0$

$\displaystyle
2+4\operatorname{Re}\left(B_{1}\frac{\lambda_{1}^{2n}-1}{\lambda_{1}^{2}-1}\right)\quad$
$\displaystyle\leq\quad
2+4|B_{1}|\frac{|\lambda_{1}|^{2n}+1}{|\lambda_{1}^{2}-1|}$
$\displaystyle\leq\quad 2+4|B_{1}|\frac{2}{|\lambda_{1}^{2}-1|}.$

For the right side, we can write for $n\geq 0$

$\displaystyle
A_{1}\frac{2}{\beta^{2}-1}+2\operatorname{Re}\left(B_{1}\lambda_{1}^{2n}\right)\quad$
$\displaystyle\geq\quad A_{1}\frac{2}{\beta^{2}-1}-2|B_{1}||\lambda_{1}|^{2n}$
$\displaystyle\geq\quad A_{1}\frac{2}{\beta^{2}-1}-2|B_{1}|.$

Since the inequality

$2+4|B_{1}|\frac{2}{|\lambda_{1}^{2}-1|}\quad\leq\quad
A_{1}\frac{2}{\beta^{2}-1}-2|B_{1}|$

holds true for given values, we obtain $B\leq\frac{3}{2}$.

  3. 3.

Computation of $C$ and $D$.

Denote $d_{n}:=|\nu(\varphi^{n}(01))|$, then it satisfies the same recurrence
relation as $c_{n}$, i.e., $d_{n+1}=2d_{n}-d_{n-1}+d_{n-2}$, with initial
conditions $d_{0}=4,d_{1}=7$ and $d_{2}=13$.

The explicit solution reads

$d_{n}=A_{2}\beta^{n}+B_{2}\lambda_{1}^{n}+C_{2}\lambda_{2}^{n},$

where

$\beta\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

$\displaystyle A_{2}$
$\displaystyle=\frac{4|\lambda_{1}|^{2}-14\operatorname{Re}(\lambda_{1})+13}{|\beta-\lambda_{1}|^{2}}\doteq
4.213205567\,;$ $\displaystyle B_{2}$
$\displaystyle=\frac{4\beta\lambda_{2}-7(\beta+\lambda_{2})+13}{(\beta-\lambda_{1})(\lambda_{2}-\lambda_{1})}\doteq-0.106602784+0.24671731i\,;$
$\displaystyle C_{2}$ $\displaystyle=\overline{B_{2}}\,.$

First, we will show that $C=\frac{3}{2}$. Recall that

$C=\sup\left\\{\frac{|01\nu(01\varphi^{2}(01)\varphi^{4}(01)\dots\varphi^{2n}(01))|}{|\nu(\varphi^{2n}(01))|}:n\geq
1\right\\}\cup\left\\{\frac{|1\nu(10)0|}{|\nu(10)|}\right\\}\,,$

consequently, $C\geq\frac{|1\nu(10)0|}{|\nu(10)|}=\frac{3}{2}$.

It suffices to show for all $n\geq 1$ that

$\displaystyle\frac{2+A_{2}\sum_{k=0}^{n}\beta^{2k}+B_{2}\sum_{k=0}^{n}\lambda_{1}^{2k}+C_{2}\sum_{k=0}^{n}\lambda_{2}^{2k}}{A_{2}\beta^{2n}+B_{2}\lambda_{1}^{2n}+C_{2}\lambda_{2}^{2n}}\quad$
$\displaystyle\leq^{?}\quad\frac{3}{2},$ $\displaystyle
4+2A_{2}\sum_{k=0}^{n-1}\beta^{2k}+4\operatorname{Re}\left(B_{2}\sum_{k=0}^{n-1}\lambda_{1}^{2k}\right)\quad$
$\displaystyle\leq^{?}\quad
A_{2}\beta^{2n}+2\operatorname{Re}\left(B_{2}\lambda_{1}^{2n}\right),$
$\displaystyle
4+2A_{2}\frac{\beta^{2n}-1}{\beta^{2}-1}+4\operatorname{Re}\left(B_{2}\frac{\lambda_{1}^{2n}-1}{\lambda_{1}^{2}-1}\right)\quad$
$\displaystyle\leq^{?}\quad
A_{2}\beta^{2n}+2\operatorname{Re}\left(B_{2}\lambda_{1}^{2n}\right).$

Since

$\displaystyle\frac{2}{\beta^{2}-1}$ $\displaystyle\leq 1,$

we need to prove the inequality in the form

$\displaystyle
4+4\operatorname{Re}\left(B_{2}\frac{\lambda_{1}^{2n}-1}{\lambda_{1}^{2}-1}\right)\quad$
$\displaystyle\leq^{?}\quad
A_{2}\frac{2}{\beta^{2}-1}+2\operatorname{Re}\left(B_{2}\lambda_{1}^{2n}\right).$

Now, we need to be more careful with the approximations. For the left side, we
can write for $n\geq 2$

$\displaystyle
4+4\operatorname{Re}\left(B_{2}\frac{\lambda_{1}^{2n}-1}{\lambda_{1}^{2}-1}\right)\quad$
$\displaystyle\leq\quad
4+4\operatorname{Re}\left(\frac{B_{2}}{1-\lambda_{1}^{2}}\right)+4|B_{2}|\frac{|\lambda_{1}|^{2n}}{|1-\lambda_{1}^{2}|}$
$\displaystyle\leq\quad
4+4\operatorname{Re}\left(\frac{B_{2}}{1-\lambda_{1}^{2}}\right)+4|B_{2}|\frac{|\lambda_{1}|^{4}}{|1-\lambda_{1}^{2}|}.$

For the right side, we can write for $n\geq 2$

$\displaystyle
A_{2}\frac{2}{\beta^{2}-1}+2\operatorname{Re}\left(B_{2}\lambda_{1}^{2n}\right)\quad$
$\displaystyle\geq\quad A_{2}\frac{2}{\beta^{2}-1}-2|B_{2}||\lambda_{1}|^{2n}$
$\displaystyle\geq\quad A_{2}\frac{2}{\beta^{2}-1}-2|B_{2}||\lambda_{1}|^{4}.$

Since the inequality

$4+4\operatorname{Re}\left(\frac{B_{2}}{1-\lambda_{1}^{2}}\right)+4|B_{2}|\frac{|\lambda_{1}|^{4}}{|1-\lambda_{1}^{2}|}\quad\leq\quad
A_{2}\frac{2}{\beta^{2}-1}-2|B_{2}||\lambda_{1}|^{4}$

holds true for given values, it remains to check the case for $n=1$.

If $n=1$, we get

$\frac{2+d_{0}+d_{2}}{d_{2}}=\frac{19}{13}<\frac{3}{2}.$

Therefore, we have proven that $C=\frac{3}{2}$.

It remains to prove $D\leq\frac{3}{2}$, however, the steps are the same as in
the proof of the inequality $A\leq\frac{3}{2}$. Thus, we dare to skip it.

We have shown that $\max\\{A,B,C,D\\}=\frac{3}{2}$, and $F=1$. Consequently,
$E(\nu({\bf p}))=1+\max\\{A,B,C,D,F\\}=\frac{5}{2}$.

∎

###  4.3 The infinite word $\mu(\bf p)$

The morphism $\mu$ has the form:

$\displaystyle\mu({\tt 0})$ $\displaystyle={\tt 011001},$
$\displaystyle\mu({\tt 1})$ $\displaystyle={\tt 1001},$ $\displaystyle\mu({\tt
2})$ $\displaystyle={\tt 0}.$

$\mu({\bf p})={\tt
0110011001010010110010100101100110010110010100101100110010100101100110010110010}\dots$

and $\mu$ is injective.

######  Remark 27.

The reader may easily check that any factor of $\mu(\bf p)$ of length at least
six has a synchronization point.

Using the above remark and Theorem 9, we deduce that

$E^{*}(\mu({\bf p}))=E^{*}(\bf p).$

####  4.3.1 Bispecial factors in $\mu(\bf p)$

######  Lemma 28.

Let $v\in\mathcal{L}(\mu(\bf p))$ be a BS factor of length at least six. Then
one of the items holds.

  1. 1.

There exists $w\in\mathcal{L}(\bf p)$ such that $v=\mu(w){\tt 01}$ and ${\tt
0}w,{\tt 2}w,w{\tt 0},w{\tt 2}\in\mathcal{L}(\bf p)$.

  2. 2.

There exists $w\in\mathcal{L}(\bf p)$ such that $v={\tt 011001}\mu(w)$ and
${\tt 0}w,{\tt 1}w,w{\tt 1},w{\tt 2}\in\mathcal{L}(\bf p)$.

  3. 3.

There exists $w\in\mathcal{L}(\bf p)$ such that $v=\mu(w)$ and ${\tt 0}w,{\tt
2}w,w{\tt 1},w{\tt 2}\in\mathcal{L}(\bf p)$.

  4. 4.

There exists $w\in\mathcal{L}(\bf p)$ such that $v={\tt 011001}\mu(w){\tt 01}$
and ${\tt 0}w,{\tt 1}w,w{\tt 0},w{\tt 2}\in\mathcal{L}(\bf p)$.

We would like to point out that in this section, we use the same notation for
BS factors and their shortest return words as in Section 4.2. We are persuaded
that no confusion arises since we do not refer here to the BS factors and
their shortest return words from Section 4.2.

######  Corollary 29.

Let $v$ be a BS factor in $\mu(\bf p)$ of length at least six. Then $v={\tt
011001}$ or $v={\tt 100101}$ or $v={\tt 01100101}$ or $v$ has one of the
following forms:

  * $(\mathcal{A})$

$v_{A}^{(n)}=\mu({\tt 1}\varphi^{2}({\tt 1})\varphi^{4}({\tt
1})\cdots\varphi^{2n}({\tt 1})\varphi^{2n-1}({\tt 0})\varphi^{2n-3}({\tt
0})\cdots\varphi({\tt 0})){\tt 01}$

for $n\geq 1$.

The Parikh vector of $v_{A}^{(n)}$ is the same as of the word ${\tt
01}\mu({\tt 1}\varphi({\tt 012})\varphi^{3}({\tt 012})\dots\varphi^{2n-1}({\tt
012}))$.

  * $(\mathcal{B})$

$\displaystyle v_{B}^{(n)}$ $\displaystyle={\tt 011001}\mu(\varphi({\tt
1})\varphi^{3}({\tt 1})\cdots\varphi^{2n+1}({\tt 1})\varphi^{2n}({\tt
0})\varphi^{2n-2}({\tt 0})\cdots\varphi^{2}({\tt 0}){\tt 0})$
$\displaystyle=\mu({\tt 0}\varphi({\tt 1})\varphi^{3}({\tt
1})\cdots\varphi^{2n+1}({\tt 1})\varphi^{2n}({\tt 0})\varphi^{2n-2}({\tt
0})\cdots\varphi^{2}({\tt 0}){\tt 0})$

for $n\geq 0$.

The Parikh vector of $v_{B}^{(n)}$ is the same as of the word ${\tt
000111}\mu({\tt 012}\varphi^{2}({\tt 012})\varphi^{4}({\tt
012})\dots\varphi^{2n}({\tt 012}))$.

  * $(\mathcal{C})$

$v_{C}^{(n)}=\mu({\tt 1}\varphi^{2}({\tt 1})\varphi^{4}({\tt
1})\cdots\varphi^{2n}({\tt 1})\varphi^{2n}({\tt 0})\varphi^{2n-2}({\tt
0})\cdots\varphi^{2}({\tt 0}){\tt 0})$

for $n\geq 0$.

The Parikh vector of $v_{C}^{(n)}$ is the same as of the word $\mu({\tt
01}\varphi^{2}({\tt 01})\varphi^{4}({\tt 01})\dots\varphi^{2n}({\tt 01}))$.

  * $(\mathcal{D})$

$v_{D}^{(n)}={\tt 011001}\mu(\varphi({\tt 1})\varphi^{3}({\tt
1})\cdots\varphi^{2n+1}({\tt 1})\varphi^{2n+1}({\tt 0})\varphi^{2n-1}({\tt
0})\cdots\varphi({\tt 0})){\tt 01}$

for $n\geq 0$.

The Parikh vector of $v_{D}^{(n)}$ is the same as of the word ${\tt
00001111}\mu(\varphi({\tt 01})\varphi^{3}({\tt 01})\dots\varphi^{2n+1}({\tt
01}))$.

####  4.3.2 The shortest return words to bispecial factors in $\mu(\bf p)$

######  Lemma 30.

If $w$ is a BS factor of $\bf p$, $|w|\geq 2$, and $v$ is its return word,
then $\mu(v)$ is a return word to $\mu(w)$.

###### Proof.

On one hand, since $vw$ contains $w$ as a prefix and as a suffix, then
$\mu(v)\mu(w)$ contains $\mu(w)$ as a prefix and as a suffix, too. On the
other hand, $w$ starts in ${\tt 10}$ or ${\tt 21}$ and ends in ${\tt 0}$ or
${\tt 1}$, therefore $\mu(w)$ has the following synchronization points
$\bullet\mu(w)\bullet$. Consequently, $\mu(v)\mu(w)$ cannot contain $\mu(w)$
somewhere in the middle because in such a case, by injectivity of $\mu$, $vw$
would contain $w$ also somewhere in the middle.

∎

Applying Lemma 30 and Observation 18, we have the following description of the
shortest return words to BS factors.

######  Corollary 31.

The shortest return words to BS factors of length greater than eight in
$\mu(\bf p)$ have the following properties.

  * $(\mathcal{A})$

The shortest return word $\hat{r}_{A}^{(n)}$ to $v_{A}^{(n)}$ has the same
Parikh vector as $\mu(\varphi^{2n-1}({\tt 012}))$ for $n\geq 1$.

  * $(\mathcal{B})$

The shortest return word $\hat{r}_{B}^{(n)}$ to $v_{B}^{(n)}$ has the same
Parikh vector as $\mu(\varphi^{2n}({\tt 012}))$.

  * $(\mathcal{C})$

The shortest return word $\hat{r}_{C}^{(n)}$ to $v_{C}^{(n)}$ has the same
Parikh vector as $\mu(\varphi^{2n}({\tt 01}))$.

  * $(\mathcal{D})$

The shortest return word $\hat{r}_{D}^{(n)}$ to $v_{D}^{(n)}$ has the same
Parikh vector as $\mu(\varphi^{2n+1}({\tt 01}))$.

####  4.3.3 The critical exponent of $\mu(\bf p)$

Using Theorem 8 and the description of BS factors from Corollary 29 and of
their shortest return words from Corollary 31, we obtain the following formula
for the critical exponent of $\mu(\bf p)$.

$E(\mu({\bf p}))=1+\max\left\\{A,B,C,D,F\right\\}\,,$

where

$\displaystyle A$
$\displaystyle=\sup\left\\{\frac{|v_{A}^{(n)}|}{|\hat{r}_{A}^{(n)}|}:n\geq
1\right\\}=\sup\left\\{\frac{|{\tt 01}\mu({\tt 1}\varphi({\tt
012})\varphi^{3}({\tt 012})\dots\varphi^{2n-1}({\tt
012}))|}{|\mu(\varphi^{2n-1}({\tt 012}))|}:n\geq 1\right\\}\,;$ $\displaystyle
B$ $\displaystyle=\sup\left\\{\frac{|v_{B}^{(n)}|}{|\hat{r}_{B}^{(n)}|}:n\geq
0\right\\}=\sup\left\\{\frac{|{\tt 000111}\mu({\tt 012}\varphi^{2}({\tt
012})\varphi^{4}({\tt 012})\dots\varphi^{2n}({\tt
012}))|}{|\mu(\varphi^{2n}({\tt 012}))|}:n\geq 0\right\\}\,;$ $\displaystyle
C$ $\displaystyle=\sup\left\\{\frac{|v_{C}^{(n)}|}{|\hat{r}_{C}^{(n)}|}:n\geq
0\right\\}=\sup\left\\{\frac{|\mu({\tt 01}\varphi^{2}({\tt
01})\varphi^{4}({\tt 01})\dots\varphi^{2n}({\tt 01}))|}{|\mu(\varphi^{2n}({\tt
01}))|}:n\geq 1\right\\}\,;$ $\displaystyle D$
$\displaystyle=\sup\left\\{\frac{|v_{D}^{(n)}|}{|\hat{r}_{D}^{(n)}|}:n\geq
0\right\\}=\sup\left\\{\frac{|{\tt 00001111}\mu(\varphi({\tt
01})\varphi^{3}({\tt 01})\dots\varphi^{2n+1}({\tt
01}))|}{|\mu(\varphi^{2n+1}({\tt 01}))|}:n\geq 0\right\\}\,;$ $\displaystyle
F$ $\displaystyle=\max\left\\{\frac{|w|}{|r|}:w\text{\ BS in $\mu(\bf p)$ of
length at most 8 and $r$ its shortest return word}\right\\}\,.$

######  Theorem 32.

The critical exponent of $\mu({\bf p})$ equals

$E(\mu({\bf p}))=\frac{28}{11}.$

###### Proof.

To evaluate the critical exponent of $\mu(\bf p)$ using the above formula, we
have to do several steps.

  1. 1.

Determining the shortest return words of BS factors of length at most 8 in
$\mu(\bf p)$:

     * •

0 is a BS factor with the shortest return word 0.

     * •

1 is a BS factor with the shortest return word 1.

     * •

01 is a BS factor with the shortest return word 01.

     * •

10 is a BS factor with the shortest return word 10.

     * •

010 is a BS factor with the shortest return word 01.

     * •

1001 is a BS factor with the shortest return word 1001.

     * •

011001 is a BS factor with the shortest return word 0110.

     * •

100101 is a BS factor with the shortest return word 10010.

     * •

01100101 is a BS factor with the shortest return word 011001.

Therefore,
$F=\max\left\\{1,\frac{3}{2},\frac{6}{5},\frac{8}{6}\right\\}<\frac{17}{11}$.

  2. 2.

Computation of $A$ and $B$.

Denote $e_{n}:=|\mu(\varphi^{n}(012))|$, then it satisfies the recurrence
relation $e_{n+1}=2e_{n}-e_{n-1}+e_{n-2}$ with initial conditions
$e_{0}=11,e_{1}=21$ and $e_{2}=36$.

The explicit solution reads

$e_{n}=A_{3}\beta^{n}+B_{3}\lambda_{1}^{n}+C_{3}\lambda_{2}^{n},$

where

$\beta\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

$\displaystyle A_{3}$
$\displaystyle=\frac{11|\lambda_{1}|^{2}-42\operatorname{Re}(\lambda_{1})+36}{|\beta-\lambda_{1}|^{2}}\doteq
11.530751580\,;$ $\displaystyle B_{3}$
$\displaystyle=\frac{11\beta\lambda_{2}-21(\beta+\lambda_{2})+36}{(\beta-\lambda_{1})(\lambda_{2}-\lambda_{1})}\doteq-0.265375790-0.557144391i\,;$
$\displaystyle C_{3}$ $\displaystyle=\overline{B_{3}}\,.$

Let us show that $A\leq\frac{17}{11}$. We have to show for all $n\geq 1$ that

$\displaystyle\frac{6+A_{3}\sum_{k=1}^{n}\beta^{2k-1}+B_{3}\sum_{k=1}^{n}\lambda_{1}^{2k-1}+C_{3}\sum_{k=1}^{n}\lambda_{2}^{2k-1}}{A_{3}\beta^{2n-1}+B_{3}\lambda_{1}^{2n-1}+C_{3}\lambda_{2}^{2n-1}}\quad$
$\displaystyle\leq^{?}\quad\frac{17}{11},$ $\displaystyle
66+11A_{3}\sum_{k=1}^{n}\beta^{2k-1}+22\operatorname{Re}\left(B_{3}\sum_{k=1}^{n}\lambda_{1}^{2k-1}\right)\quad$
$\displaystyle\leq^{?}\quad
17A_{3}\beta^{2n-1}+34\operatorname{Re}(B_{2}\lambda_{1}^{2n-1}),$
$\displaystyle
66+11A_{3}\sum_{k=1}^{n-1}\beta^{2k-1}+22\operatorname{Re}\left(B_{3}\sum_{k=1}^{n-1}\lambda_{1}^{2k-1}\right)\quad$
$\displaystyle\leq^{?}\quad
6A_{3}\beta^{2n-1}+12\operatorname{Re}(B_{3}\lambda_{1}^{2n-1}),$
$\displaystyle
66+11A_{3}\left(\frac{\beta^{2n-1}}{\beta^{2}-1}-\frac{\beta}{\beta^{2}-1}\right)+22\operatorname{Re}\left(B_{3}\lambda_{1}\frac{1-\lambda_{1}^{2n-2}}{1-\lambda_{1}^{2}}\right)\quad$
$\displaystyle\leq^{?}\quad
6A_{3}\beta^{2n-1}+12\operatorname{Re}(B_{3}\lambda_{1}^{2n-1}).$

Since

$\displaystyle\frac{11}{\beta^{2}-1}$ $\displaystyle\leq 6,$

we need to prove the inequality in the form

$\displaystyle
66+22\operatorname{Re}\left(B_{3}\lambda_{1}\frac{1-\lambda_{1}^{2n-2}}{1-\lambda_{1}^{2}}\right)\quad$
$\displaystyle\leq^{?}\quad
11A_{3}\frac{\beta}{\beta^{2}-1}+12\operatorname{Re}(B_{3}\lambda_{1}^{2n-1}).$

For the left side, we can write for $n\geq 1$

$\displaystyle
66+22\operatorname{Re}\left(B_{3}\lambda_{1}\frac{1-\lambda_{1}^{2n-2}}{1-\lambda_{1}^{2}}\right)\quad$
$\displaystyle\leq\quad
66+22|B_{3}||\lambda_{1}|\frac{|\lambda_{1}|^{2n-2}+1}{|\lambda_{1}^{2}-1|}$
$\displaystyle\leq\quad
66+22|B_{3}||\lambda_{1}|\frac{2}{|\lambda_{1}^{2}-1|}.$

For the right side, we can write for $n\geq 1$

$\displaystyle\quad
11A_{3}\frac{\beta}{\beta^{2}-1}+12\operatorname{Re}(B_{3}\lambda_{1}^{2n-1})\quad$
$\displaystyle\geq\quad
11A_{3}\frac{\beta}{\beta^{2}-1}-12|B_{3}||\lambda_{1}|^{2n-1}$
$\displaystyle\geq\quad
11A_{3}\frac{\beta}{\beta^{2}-1}-12|B_{3}||\lambda_{1}|.$

Since the inequality

$66+22|B_{3}||\lambda_{1}|\frac{2}{|\lambda_{1}^{2}-1|}\quad\leq\quad
11A_{3}\frac{\beta}{\beta^{2}-1}-12|B_{1}||\lambda_{1}|$

holds true for the given values, we obtain $A\leq\frac{17}{11}$.

Next, we will show that $B\leq\frac{17}{11}$.

Since for $n=0$ we have
$\frac{|v_{B}^{(0)}|}{|\hat{r}_{B}^{(0)}|}=\frac{6+11}{11}=\frac{17}{11}$, it
remains to show that for all $n\geq 1$

$\displaystyle\frac{6+A_{3}\sum_{k=0}^{n}\beta^{2k}+B_{3}\sum_{k=0}^{n}\lambda_{1}^{2k}+C_{3}\sum_{k=0}^{n}\lambda_{2}^{2k}}{A_{3}\beta^{2n}+B_{3}\lambda_{1}^{2n}+C_{3}\lambda_{2}^{2n}}\quad$
$\displaystyle\leq^{?}\quad\frac{17}{11},$ $\displaystyle
66+11A_{3}\sum_{k=0}^{n-1}\beta^{2k}+22\operatorname{Re}\left(B_{3}\sum_{k=0}^{n-1}\lambda_{1}^{2k}\right)\quad$
$\displaystyle\leq^{?}\quad
6A_{3}\beta^{2n}+12\operatorname{Re}\left(B_{3}\lambda_{1}^{2n}\right),$
$\displaystyle
66+11A_{3}\frac{\beta^{2n}-1}{\beta^{2}-1}+22\operatorname{Re}\left(B_{3}\frac{\lambda_{1}^{2n}-1}{\lambda_{1}^{2}-1}\right)\quad$
$\displaystyle\leq^{?}\quad
6A_{3}\beta^{2n}+12\operatorname{Re}\left(B_{3}\lambda_{1}^{2n}\right).$

Now, we need to be more careful with the approximations, we will therefore
prove the inequality in the form

$\displaystyle
66+22\operatorname{Re}\left(B_{3}\frac{\lambda_{1}^{2n}-1}{\lambda_{1}^{2}-1}\right)\quad$
$\displaystyle\leq^{?}\quad
11A_{3}\frac{1}{\beta^{2}-1}+A_{3}\beta^{2n}\left(6-\frac{11}{\beta^{2}-1}\right)+12\operatorname{Re}\left(B_{3}\lambda_{1}^{2n}\right).$

For the left side, we can write for $n\geq 1$

$\displaystyle
66+22\operatorname{Re}\left(B_{3}\frac{\lambda_{1}^{2n}-1}{\lambda_{1}^{2}-1}\right)\quad$
$\displaystyle\leq\quad
66+22|B_{3}|\frac{|\lambda_{1}|^{2n}+1}{|\lambda_{1}^{2}-1|}$
$\displaystyle\leq\quad
66+22|B_{3}|\frac{1+|\lambda_{1}|^{2}}{|\lambda_{1}^{2}-1|}.$

For the right side, we can write for $n\geq 1$

$\displaystyle
A_{3}\frac{11}{\beta^{2}-1}+A_{3}\beta^{2n}\left(6-\frac{11}{\beta^{2}-1}\right)+12\operatorname{Re}\left(B_{3}\lambda_{1}^{2n}\right)\quad$
$\displaystyle\geq\quad
A_{3}\frac{11}{\beta^{2}-1}+A_{3}\beta^{2}\left(6-\frac{11}{\beta^{2}-1}\right)-12|B_{3}||\lambda_{1}|^{2n}$
$\displaystyle\geq\quad
A_{3}\frac{11}{\beta^{2}-1}+A_{3}\beta^{2}\left(6-\frac{11}{\beta^{2}-1}\right)-12|B_{3}||\lambda_{1}|^{2}.$

Since the inequality

$66+22|B_{3}|\frac{1+|\lambda_{1}|^{2}}{|\lambda_{1}^{2}-1|}\quad\leq\quad
A_{3}\frac{11}{\beta^{2}-1}+A_{3}\beta^{2}\left(6-\frac{11}{\beta^{2}-1}\right)-12|B_{3}||\lambda_{1}|^{2}$

holds true for the given values, we conclude $B=\frac{17}{11}$.

  3. 3.

Computation of $C$ and $D$. Denote $f_{n}:=|\mu(\varphi^{n}(01))|$, then it
satisfies the recurrence relation $f_{n+1}=2f_{n}-f_{n-1}+f_{n-2}$ with
initial conditions
$f_{0}=10,f_{1}=15$ and $f_{2}=26$.

The explicit solution reads

$f_{n}=A_{4}\beta^{n}+B_{4}\lambda_{1}^{n}+C_{4}\lambda_{2}^{n},$

where

$\beta\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

$\displaystyle A_{4}$
$\displaystyle=\frac{10|\lambda_{1}|^{2}-30\operatorname{Re}(\lambda_{1})+26}{|\beta-\lambda_{1}|^{2}}\doteq
8.704306843\,;$ $\displaystyle B_{4}$
$\displaystyle=\frac{10\beta\lambda_{2}-15(\beta+\lambda_{2})+26}{(\beta-\lambda_{1})(\lambda_{2}-\lambda_{1})}\doteq
0.647846579+0.291191845i\,;$ $\displaystyle C_{4}$
$\displaystyle=\overline{B_{4}}\,.$

The computation for $C\leq\frac{17}{11}$ is the same as for $B$. Let us show
that $D\leq\frac{17}{11}$. We have to show for $n\geq 1$ that

$\displaystyle\frac{8+A_{4}\sum_{k=1}^{n}\beta^{2k-1}+B_{4}\sum_{k=1}^{n}\lambda_{1}^{2k-1}+C_{4}\sum_{k=1}^{n}\lambda_{2}^{2k-1}}{A_{4}\beta^{2n-1}+B_{4}\lambda_{1}^{2n-1}+C_{4}\lambda_{2}^{2n-1}}\quad$
$\displaystyle\leq^{?}\quad\frac{17}{11},$ $\displaystyle
88+11A_{4}\left(\frac{\beta^{2n-1}}{\beta^{2}-1}-\frac{\beta}{\beta^{2}-1}\right)+22\operatorname{Re}\left(B_{4}\lambda_{1}\frac{1-\lambda_{1}^{2n-2}}{1-\lambda_{1}^{2}}\right)\quad$
$\displaystyle\leq^{?}\quad
6A_{4}\beta^{2n-1}+12\operatorname{Re}(B_{4}\lambda_{1}^{2n-1}).$

Since

$\displaystyle\frac{11}{\beta^{2}-1}$ $\displaystyle\leq 6,$

we need to prove the inequality in the form

$\displaystyle
88+22\operatorname{Re}\left(B_{4}\lambda_{1}\frac{1-\lambda_{1}^{2n-2}}{1-\lambda_{1}^{2}}\right)\quad$
$\displaystyle\leq^{?}\quad
11A_{4}\frac{\beta}{\beta^{2}-1}+12\operatorname{Re}(B_{4}\lambda_{1}^{2n-1}).$

For the left side, we can write for $n\geq 1$

$\displaystyle
88+22\operatorname{Re}\left(B_{4}\lambda_{1}\frac{1-\lambda_{1}^{2n-2}}{1-\lambda_{1}^{2}}\right)\quad$
$\displaystyle\leq\quad
88+22\operatorname{Re}\left(\frac{B_{4}\lambda_{1}}{1-\lambda_{1}^{2}}\right)+22|B_{4}|\frac{|\lambda_{1}|^{2n-1}}{|1-\lambda_{1}^{2}|}$
$\displaystyle\leq\quad
88+22\operatorname{Re}\left(\frac{B_{4}\lambda_{1}}{1-\lambda_{1}^{2}}\right)+22|B_{4}|\frac{|\lambda_{1}|}{|1-\lambda_{1}^{2}|}.$

For the right side, we can write for $n\geq 1$

$\displaystyle\quad
11A_{4}\frac{\beta}{\beta^{2}-1}+12\operatorname{Re}(B_{4}\lambda_{1}^{2n-1})\quad$
$\displaystyle\geq\quad
11A_{4}\frac{\beta}{\beta^{2}-1}-12|B_{4}||\lambda_{1}|^{2n-1}$
$\displaystyle\geq\quad
11A_{4}\frac{\beta}{\beta^{2}-1}-12|B_{4}||\lambda_{1}|.$

Since the inequality

$88+22\operatorname{Re}\left(\frac{B_{4}\lambda_{1}}{1-\lambda_{1}^{2}}\right)+22|B_{4}|\frac{|\lambda_{1}|}{|1-\lambda_{1}^{2}|}\quad\leq\quad
11A_{4}\frac{\beta}{\beta^{2}-1}-12|B_{4}||\lambda_{1}|$

holds true for the given values, we obtain $D\leq\frac{17}{11}$.

We have shown that $\max\\{A,B,C,D\\}=B=\frac{17}{11}$, and $F<\frac{17}{11}$.
Consequently, $E(\mu({\bf p}))=1+\max\\{A,B,C,D,F\\}=\frac{28}{11}$.

∎

## References

  * [1] L. Balková, E. Pelantová, W. Steiner. Sequences with Constant Number of Return Words. _Monatshefte für Mathematik_ 155(3-4) (2008), 251–263.
  * [2] J. Currie, P. Ochem, N. Rampersad, and J. Shallit. Properties of a ternary infinite word. _RAIRO-Theor. Inf. Appl._ 57 (2023), #1.
  * [3] J. Currie, L. Dvořaková, P. Ochem, D. Opočenská, N. Rampersad, and J. Shallit. Complement avoidance in binary words. arXiv:2209.09598
  * [4] F. Dolce, F., L. Dvořáková, E. Pelantová. On balanced sequences and their critical exponent. _Theoretical Computer Science_ 939 (2023), 18–47.
  * [5] L. Dvořáková, E. Pelantová. The repetition threshold of episturmian sequences. arXiv:2309.00988 (2023).
  * [6] G. Fici and L.Q. Zamboni. On the least number of palindromes contained in an infinite word. _Theoretical Computer Science_ 481 (2013), 1–8.
  * [7] Queffélec, M. Substitution Dynamical Systems — Spectral Analysis, vol. 1294 of Lecture Notes in Mathematics. Springer-Verlag, 1987.
  * [8] J. Karhumäki and J. O. Shallit. Polynomial versus exponential growth in repetition-free binary words, _J. Combinatorial Theory Ser. A_ 105 (2004), 335–347.
  * [9] L. Mol and N. Rampersad, and J. Shallit. Extremal overlap-free and extremal $\beta$-free binary words. _Electron. J. Combin._ , 27(4):#P4.42, 2020.
  * [10] A. Shur. Growth properties of power-free languages. _Computer Science Review_ 6 (2012), 187–208.
  * [11] A. Thue. Über unendliche Zeichenreihen. _Norske Vid. Selsk. Skr. I. Mat. Nat. Kl. Christiania_ , 7 (1906), 1–22.
  * [12] A. Thue. Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen. _Norske vid. Selsk. Skr. Mat. Nat. Kl._ 1 (1912), 1–67. Reprinted in _Selected Mathematical Papers of Axel Thue_ , T. Nagell, editor, Universitetsforlaget, Oslo, (1977), 413–478.