# Almost automorphic and bijective factors of substitution shifts

Alvaro Bustos-Gajardo  School of Mathematics and Statistics, The Open
University, U.K. & Facultad de Matemáticas, Pontificia Universidad Católica de
Chile, Santiago, Chile<EMAIL_ADDRESS>,  Johannes Kellendonk  Institut
Camille Jordan, Université Lyon-1, France<EMAIL_ADDRESS>and
Reem Yassawi  School of Mathematical Sciences , Queen Mary University of
London, U.K<EMAIL_ADDRESS>
###### Abstract.

In this article we completely characterise constant length substitution shifts
which have an almost automorphic factor, or which have a bijective
substitution factor. Our approach is algebraic: we characterise these
dynamical properties in terms of a finite semigroup defined by the
substitution. We characterise the existence of almost automorphic factors in
terms of Green’s $\mathcal{R}$-relation and the existence of bijective factors
in terms of Green’s ${\mathcal{L}}$-relation. Our results are constructive.

###### 2020 Mathematics Subject Classification:

37B02, 37B10, 37B52, 20M10, 20M35.

This work was supported by the EPSRC grant numbers EP/V007459/2 and
EP/S010335/1. The first author received funding from ANID/FONDECYT
Postdoctorado 3230159 during the final phase of this work.

##  1\. Introduction

In this article we are interested in the existence of certain factors for
substitutional dynamical systems. Factors with a specific spectral behaviour
tell us something about the spectrum of the original system. In particular, we
are interested in characterising when a shift possesses an almost automorphic
factor, or when it possesses factors with a singular component in their
maximal spectral type. We are also interested in factors whose Ellis semigroup
we can describe. We investigate these questions for constant length
substitution shifts.

More specifically, we would like to better understand when a substitution
shift $(X_{\theta},\sigma)$ defined by a primitive aperiodic length-$\ell$
substitution $\theta$ has a factor with the following additional properties.
We say that a map is almost injective  if it is somewhere injective, and a
dynamical system is almost automorphic if it is an almost injective extension
of a group rotation. We are interested in characterising two different
scenarios:

  1. (1)

$(X_{\theta},\sigma)$ has a non-equicontinuous factor, which is almost
automorphic over the maximal equicontinuous factor of $(X_{\theta},\sigma)$,
and

  2. (2)

$(X_{\theta},\sigma)$ is an almost injective extension of a bijective
substitution shift.

In the first scenario, looking for almost automorphic shift factors already
solves the problem. This is because the substitution systems we consider have
odometers as maximal equicontinuous factors, and an almost automorphic
extension of an odometer is necessarily conjugate to a shift [6, Theorem 6.4].
We also note that for the systems we study, we find an almost automorphic
factor $\pi:(X_{\theta},\sigma)\rightarrow(Y,\sigma)$ if and only if the
maximal equicontinuous factor map for $(X_{\theta},\sigma)$ factors through
$\pi$; see Corollary 2.10.

The interest of the second question is twofold. Firstly, although “most”
length-$\ell$ substitution shifts should have a singular component in their
maximal spectral type, it is only for a subfamily of bijective substitutions
that this has been established in some generality; see [1, 17]. Secondly, at
the moment, bijective substitution shifts are one of the few families for
which an explicit description of the Ellis semigroup exists [11].

We answer both questions completely using a combination of two sets of tools.
The first tool is algebraic, the semigroup $S_{\theta}$ of a substitution
$\theta$; see Definition 3.6. This semigroup has been extensively used in the
case when it is a group $G_{\theta}$, i.e., when the substitution is
bijective. For example, $G_{\theta}$ is used to characterise the automorphism
group [12, 15], and, if it is commutative, then $(X_{\theta},\sigma,\mu)$ has
a singular component in its maximal spectral type [1, 17]. Also, it is a
fundamental building block of the Ellis semigroup of a bijective substitution
[11]. It is interesting that we use Green’s $\mathcal{R}$ relation to prove
Theorem 1.1, and Green’s $\mathcal{L}$ relation to prove Theorems 1.2 and 1.3.

The second set of tools is classical and involves building topologically
conjugate versions of $(X_{\theta},\sigma)$ using collaring and k-shifting
(Definitions 2.1 and 2.2). In particular, collaring allows us to control the
radius of a putative factor map $F:X_{\theta}\rightarrow Y$, and $k$-shifting
allows us to compose $F$ with a “translation”. We use both these constructions
to limit and manipulate possible factor maps, and this results in theorem
statements that are constructive, i.e., given a length-$\ell$ substitution
shift, one can explicitly determine whether or not it has an almost
automorphic or bijective shift factor.

Let $\theta^{(-l,r)}$ denote the $(-l,r)$-collaring of $\theta$, which is the
model of $\theta$ that we work with if $F:X_{\theta}\rightarrow Y$ has left
and right radius $l$ and $r$. To state our first result, we distinguish
between different families of factor maps. The simplest factor maps are inner
encodings; see Definition 2.3. Equivalently, a factor map
$F:X_{\theta}\rightarrow Y$ is an inner encoding if it has radius zero, if $Y$
is substitutional, and if fixed points are mapped to fixed points. Inner
encodings arise whenever there is an equivalence relation on the alphabet
$\mathcal{A}_{\theta}$ of the substitution $\theta$ such that if $a\sim b$,
then as words, $\theta(a)\sim\theta(b)$. Thus inner encodings define
partitions $\mathcal{P}$ of $\mathcal{A}_{\theta}$. Conversely, given a
substitution $\theta$, one can define a partition $\mathcal{P}_{\theta}$,
which we call the coincidence partition of $\theta$ (Definition 3.8), and
which yields an inner encoding of $\theta$, called the inner encoding
associated to $\theta$. This inner encoding generates an almost automorphic
shift. However one cannot guarantee that the inner encoding is aperiodic, so
that its shift space is infinite. Our first result is

######  Theorem 1.1.

Let $\theta$ be a length-$\ell$, primitive aperiodic substitution, with pure
base $\tilde{\theta}$. Then $\theta$ has an aperiodic almost automorphic shift
factor if and only if the inner encoding associated to
$\tilde{\theta}^{(-1,1)}$ is aperiodic.

The beauty of this result is that it is quite simple to verify its conditions
for a fixed substitution. Both Martin [14] and later Herning [9] have worked
on this question, but only in the case where $\theta$ is bijective; see below
for a discussion of their results. Note that as a corollary, we can show that
there exist substitution shifts for which the maximal tame factor, [7], equals
the maximal equicontinuous factor. For, a tame factor which is not
equicontinuous must be almost automorphic [10], and with Theorem 1.1, we can
give many examples of substitution shifts with no almost automorphic factor.

Our second result characterises, in terms of the semigroup $S_{\theta}$, when
a substitution has a bijective substitution factor. We make use of the fact
that $S_{\theta}$ admits a kernel, i.e., a minimal bilateral ideal, which is a
union of minimal left ideals. The naïve column number of $\theta$ is the rank
of any element in the kernel of $S_{\theta}$. We first show the following.

######  Theorem 1.2.

Let $\theta$ be constant length substitution with naïve column number $c>1$.
Then $(X_{\theta},\sigma)$ factors almost injectively onto a bijective inner
encoding on a $c$-letter alphabet if and only if $S_{\theta}$ has a unique
minimal left ideal.

Note that an almost injective factor onto a bijective substitution exists if
and only if an almost injective factor onto a bijective substitution on $c$
letters exists. Note also that if $c=1$, there is no such factor.

To drop the condition that the bijective factor comes from an inner encoding,
let $\theta^{(+k)}$ be the $k$-shifted extension of $\theta$. This version of
$\theta$ is especially useful when one considers factor maps $F$ which
translate the fixed points of $\theta$, from one fibre of the maximal
equicontinuous factor to another, i.e., when in Theorem 4.14, $\kappa(F)\neq
0$. We show

######  Theorem 1.3.

Let $\theta$ be an aperiodic primitive constant length-$\ell$ substitution
with naïve column number $c>1$ and trivial height. The following are
equivalent:

  1. (1)

$(X_{\theta},\sigma)$ factors almost injectively onto a bijective substitution
shift on an alphabet with $c$ letters.

  2. (2)

There exist $0\leq n,k\leq C$ such that the semigroup
$S_{(\theta^{n})^{(+k)}}$ contains a unique minimal left ideal.

Moreover, $C$ can be explicitly obtained. In general it is doubly exponential
in $\ell$; see the statement of Theorem 4.21.

We discuss prior work concerning Theorem 1.1. The original result is by Martin
[14]. He couched his work in terms of Veech’s result on almost isometric
systems [18, Theorem 7.2], which roughly speaking, says that any system with a
residual set of distal points can be realised as an inverse limit of
alternating isometric and almost automorphic extensions. Constant length
substitution shifts satisfy the requirements of Veech’s theorem, and given
their low complexity, a first natural question arises, which is whether such a
shift $(X_{\theta},\sigma)$ is already an isometric extension of an almost
automorphic shift. Martin investigated this question with the assumption that
$\theta$ is bijective, i.e., $S_{\theta}=G_{\theta}$ is a group. Inside one of
his proofs ([14, Lemma 8.05]), he made an additional assumption, which is that
any factor map can be assumed to fix fibres with respect to the maximal
equicontinuous factor. This renders his work incomplete. Martin goes on to
give a necessary and sufficient condition for the existence of an almost
automorphic factor for a bijective shift, in [14, Lemma 8.08], and his
condition (A) in fact translates to our condition that the minimal sets for
the collared $\theta^{(0,1)}$ form a partition. This is almost our statement
in Theorem 1.1, although for bijective substitutions the situation may be
simpler.

Later, in his thesis, Herning [9] re-approaches this question; it seems he was
unaware of Martin’s work. He cites a question of Michael Baake, who asks
whether any substitution shift has a subshift factor that is metrically
isomorphic to its Kronecker factor, which for substitutions coincides with the
maximal equicontinuous factor. Herning answers this question in the negative
by finding bijective substitutions that do not have an almost automorphic
shift factor. In [9, Theorem 4.24], Herning characterises bijective length-$p$
substitutions of prime length that have an almost automorphic factor, and his
work, although more restrictive, does not make the omission that Martin does.
Once translated, his characterisation is very similar to ours. Our Theorem 1.1
extends these results to characterise when any primitive length-$\ell$
substitution, not just bijective, has an almost automorphic factor. To
complete the connection to Veech’s theorem, we mention the elegant result of
Lemanczyk and Müllner [13], notably that any constant length substitution
shift has an almost injective extension which has an almost automorphic
factor.

To our knowledge, the question of the existence of bijective factors has not
been addressed in the literature.

We summarise the contents of this paper. In Section 2, we set the background,
fix notation, and define collared, shifted and inner encoded substitutions. We
then limit the radii of factor maps for a length-$\ell$ substitution,
extending techniques that exist in the literature for invertible factor maps.
In Section 3, we set the stage to prove Theorem 1.1. To do this, we define
outer encodings of a substitution. These are substitutions whose semigroup is
an epimorphic image of $S_{\theta}$. As such, they do not necessarily give
rise to dynamical factors. However, we show in Proposition 3.24 that any
automorphic factor must factor through the canonical outer encoding; see
Definition 3.1. This is the key tool to prove Theorem 1.1, once we bound
possible factor maps using the tools from Section 2. In Section 4, we prove
Theorem 1.3 in three successive steps. First we prove Theorem 1.2, which
characterises when a substitution has a bijective factor arising from an inner
encoding, i.e., a radius zero factor map which sends fixed points to fixed
points. Next, in Theorem 4.13, we give a characterisation while relaxing the
condition that the factor map has radius 0. Finally, in Theorem 4.21, we
eliminate the condition that the factor map send fixed points to fixed points.
We strive to isolate the requirements on the substitution, noting that
generally, purely algebraic results do not need the restriction to primitive
aperiodic substitutions. We illustrate with examples throughout.

##  2\. Preliminaries

###  2.1. Constant length substitutions

A length-$\ell$ substitution $\theta$ is an ordered collection of $\ell$ maps,
the so-called column maps $\theta_{m}:{\mathcal{A}}\to{\mathcal{A}}$,
$m=0,\cdots,\ell-1$, on a finite set $\mathcal{A}$, its alphabet.111Since we
do not consider substitutions which are not of constant length, all
substitutions will be understood to have constant length. The substitution
$\theta$ can be understood as a map which associates to a letter
$a\in{\mathcal{A}}$ the word
$\theta(a):=\theta_{0}(a)\cdots\theta_{\ell-1}(a)$ and to a word $a_{1}\cdots
a_{k}$ the word

(2.1) $\theta(a_{1}\cdots a_{k})=\theta(a_{1})\cdots\theta(a_{k}),$

of length $k\ell$, and to the bi-infinite sequences $\cdots
u_{-2}u_{-1}u_{0}u_{1}\cdots$ the bi-infinite sequence

$\theta(\cdots
u_{-2}u_{-1}u_{0}u_{1}\cdots):=\cdots\theta(u_{-2})\theta(u_{-1})\theta(u_{-1})\cdot\theta(u_{0})\theta(u_{1})\cdots\,.$

Here the $\cdot$ indicates the position between the negative indices and the
nonnegative indices. Powers of $\theta$ (iterated compositions of $\theta$
with itself) are again substitutions and we write ${\theta^{k}}_{m}$ for the
$m+1$-st map of $\theta^{k}$.

A bi-infinite sequence $u$ is $\theta$-periodic  if $\theta^{k}(u)=u$ for some
$k\geq 1$. If $k=1$ then we say that $u$ is a fixed point. By taking a power
of $\theta$ if necessary, we will assume that each $\theta$-periodic point is
$\theta$-fixed. We say that a finite word is allowed for $\theta$ if it
appears somewhere in $\theta^{k}(a)$ for some $a\in{\mathcal{A}}$ and some
$k\in\mathbb{N}$. The substitution shift $(X_{\theta},\sigma)$ is the
dynamical system where the space $X_{\theta}$ consists of all bi-infinite
sequences all of whose subwords are allowed for $\theta$. We equip
$X_{\theta}$ with the subspace topology of the product topology on
${\mathcal{A}}^{\mathbb{Z}}$, making the left shift map $\sigma$ a continuous
$\mathbb{Z}$-action.

In this article our techniques are a combination of algebraic arguments
involving finite semigroups, and dynamical techniques applied to the dynamical
system $(X_{\theta},\sigma)$ generated by $\theta$. For the algebraic
arguments, very few constraints are imposed on $\theta$. For the dynamical
arguments, we collect the various properties of substitutions which will play
a role.

  * •

Primitivity. We say that $\theta$ is primitive if there is some
$k\in\mathbb{N}$ such that for any $a,a^{\prime}\in\mathcal{A}$, the word
$\theta^{k}(a)$ contains at least one occurrence of $a^{\prime}$. For
dynamical arguments, substitutions will mostly be assumed primitive.
Primitivity of $\theta$ implies that $X_{\theta}$ is the shift-orbit closure
of any $\theta$-periodic point, and $(X_{\theta},\sigma)$ is minimal. If
$\theta$ is primitive, then $X_{\theta}=X_{\theta^{n}}$ for each
$n\in\mathbb{N}$. Thus, by considering a power of $\theta$ if necessary, we
will assume that all $\theta$-periodic points are $\theta$-fixed.

  * •

Aperiodicity. We say that $\theta$ is aperiodic if $X_{\theta}$ does not
contain any $\sigma$-periodic sequences. This is the case if and only if
$X_{\theta}$ is an infinite space.

  * •

Bijectivity. We say that $\theta$ is bijective if all column maps
$\theta_{m}:{\mathcal{A}}\to{\mathcal{A}}$ are bijective.

###  2.2. The maximal equicontinuous factor of a length-$\ell$ substitution

Let $\mathbb{Z}_{\ell}$ denote the $\ell$-adic integers, i.e., the inverse
limit of cyclic groups $\varprojlim\mathbb{Z}/\ell^{n}\mathbb{Z}$. Let
$\mathbb{Z}_{\bar{\ell},h}:=\varprojlim\mathbb{Z}/\ell^{n}h\mathbb{Z}$ and let
$1:=(\cdots,0,0,1)$; addition in $\mathbb{Z}_{\bar{\ell},h}$ is performed with
carry. If $\theta$ is primitive and aperiodic, then Dekking’s theorem [5]
tells us that $(\mathbb{Z}_{\ell},+1)$ is an equicontinuous factor of
$(X_{\theta},\sigma)$. Furthermore, there is an $h$, with $0<h<\ell$, with $h$
coprime to $\ell$, such that $(\mathbb{Z}_{\bar{\ell},h},+1)$, is the maximal
equicontinuous factor of $(X_{\theta},\sigma)$. The integer $h$ is called the
height of $\theta$, and we say that $\theta$ has trivial height if $h=1$.

We fix the factor map $\pi:X_{\theta}\rightarrow\mathbb{Z}_{\ell}$ from a
primitive aperiodic length-$\ell$ substitution shift $(X_{\theta},\sigma)$ to
$(\mathbb{Z}_{\ell},+1)$ with which we work in this article. We will specify
it by requiring $\pi(u)=0$ if and only if $u$ is a $\theta$-fixed point. We
refer the reader to [5] for details.

Given the substitution $\theta$, the substitution $\theta^{n}$ is a
length-$\ell^{n}$ substitution. If $0\leq j\leq\ell^{n}-1$, we use
${\theta^{n}}_{j}$ to denote its $j$-th column map. The naïve column number of
a substitution $\theta$ is defined as the minimal number of distinct letters
in the image of a column map of $\theta^{n}$, for some $n$. In other words,

(2.2)
$c=c(\theta):=\inf_{j,n}\left\\{\lvert{\theta^{n}}_{j}(\mathcal{A})\rvert:0\leq
j<\ell^{n}\right\\}.$

We say that $\theta$ has a coincidence if $c=h$. In this case,
$(X_{\theta},\sigma)$ is almost automorphic, i.e., an almost injective
extension of its maximal equicontinuous factor. For details, see [5]. We
remark that our notion of column number is different to Dekking’s original
definition; however it is in this paper more useful, as it is also in [13],
where Lemanczyk and Muellner show that $h$ divides $c(\theta)$, and that
$(X_{\theta},\sigma)$ is a somewhere $c(\theta)$-to-one extension of
$(\mathbb{Z}_{\ell},+1)$. Dekking’s definition of the column number of
$\theta$ coincides with our definition of naïve column number if $\theta$ has
trivial height; in this case we will drop the adjective naïve.

###  2.3. Collared and shifted substitutions

It will be necessary to consider collared substitutions and $k$-shifted
substitutions of the substitution $\theta$, which yield shifts that are
topologically conjugate to $(X_{\theta},\sigma)$. The notation we use in the
following definition will be useful when we consider recasting factor maps of
left radius $l\geq 0$ and right radius $r\geq 0$ as codings.

######  Definition 2.1.

Let $n=(-l,r)$ where $l,r\geq 0$. The $n$-collared extension of $\theta$ is
the substitution $\theta^{(n)}$ of the same length whose alphabet consists of
the allowed $r+1+l$-letter words of $\theta$ and which is given as follows.
Given an allowed word $a_{-l}\ldots a_{r}$ compute $a^{\prime}_{-\ell l}\ldots
a^{\prime}_{\ell(r+1)-1}:=\theta(a_{-l}\ldots a_{r})$ and set

${\theta^{(n)}}_{m}(a_{-l}\ldots a_{r}):=a^{\prime}_{m-l}\ldots
a^{\prime}_{m+r}.$

If we take $l=r=0$ then we obtain $\theta^{(n)}=\theta$. If $l=0$ then
$\theta^{(n)}$ is the so-called $r$-sliding block representation of $\theta$;
see [17, Section 5.4].

######  Definition 2.2.

Let $0\leq k\leq\ell-1$. The $k$-shifted extension of $\theta$ is the
substitution $\theta^{(+k)}$ of the same length whose alphabet consists of the
allowed $2$-letter words of $\theta$ and which is given as follows. Given an
allowed word $a_{0}a_{1}$, write $\theta(a_{0}a_{1})=a^{\prime}_{0}\ldots
a^{\prime}_{2\ell-1}$ and set

${\theta^{(+k)}}_{m}(a_{0}a_{1}):=a^{\prime}_{m+k}a^{\prime}_{m+k+1}.$

We have $\theta^{(+0)}=\theta^{(0,1)}$.

###  2.4. Factors, codes and encoded substitutions

We say that a shift $(Y,\sigma)$ is a dynamical factor of the shift
$(X,\sigma)$ if there is a continuous, surjective map $F:X\rightarrow Y$ (the
factor map) which intertwines the shifts, $F\circ\sigma=\sigma\circ F$.

The Curtis-Hedlund-Lyndon theorem states that a factor map $F:X\rightarrow Y$
between two shifts, $X\subset\mathcal{A}^{\mathbb{Z}}$,
$Y\subset\mathcal{B}^{\mathbb{Z}}$ is defined by a local rule, that is, given
integers $l\geq 0$ and $r\geq 0$ there is a a surjective map
$\varphi:\mathcal{A}^{r+1+l}\rightarrow\mathcal{B}$, so that

$(F(x))_{n}=\varphi(x_{n-l},\dots,x_{n+r})$

for each $n\in\mathbb{Z}$. The quantities $l,r$ are called the left and right
radius of $F$ respectively. If $F$ is radius zero, i.e., $l=r=0$, then the
local rule $\varphi:\mathcal{A}\rightarrow\mathcal{B}$ of $F$ is called a
code. We use uppercase letters to denote factor maps, and lowercase greek
letters to denote local rules. If we are given a local rule $\varphi$ which
defines a factor map, we will denote it by $F_{\varphi}$.

######  Definition 2.3.

Let $\eta$ and $\theta$ be length-$\ell$ substitutions. We say that $\eta$ is
an inner encoding of $\theta$ if there exists a surjective map
$\beta:\mathcal{A}_{\theta}\rightarrow\mathcal{A}_{\eta}$ which intertwines
the column maps of the substitutions, i.e.,

${\mathcal{A}_{\theta}}$${\mathcal{A}_{\theta}}$${\mathcal{A}_{\eta}}$${\mathcal{A}_{\eta}\par}$$\scriptstyle{\theta_{m}}$$\scriptstyle{\beta}$$\scriptstyle{\beta}$$\scriptstyle{\eta_{m}}$

commutes.

If we need more precision then we denote the inner encoding also by the pair
$(\eta,\beta)$. If $(\eta,\beta)$ is an inner encoding of $\theta$, then
$\beta$ is the code of a factor map $F_{\beta}:X_{\theta}\rightarrow
X_{\eta}$. However, given an arbitrary code
$\beta:\mathcal{A}_{\theta}\rightarrow\mathcal{A}_{\eta}$ for a factor map
$F_{\beta}:X_{\theta}\rightarrow X_{\eta}$, it will in general not intertwine
the substitutions as above. Indeed, the code

${\mathcal{A}}_{\theta^{(+1)}}\ni
a_{0}a_{1}\stackrel{{\scriptstyle\tau}}{{\mapsto}}a_{1}\in{\mathcal{A}}_{\theta}$

gives rise to a factor map $F_{\tau}:X_{\theta^{(+1)}}\to X_{\theta}$ which is
injective and therefore defines a conjugacy, but $\theta$ is not an inner
encoding of $\theta^{(+1)}$.

######  Lemma 2.4.

Consider a substitution $\theta$ with its $n=(-l,r)$-collaring $\theta^{(n)}$.
Let $\imath:{\mathcal{A}}_{\theta^{(n)}}\to{\mathcal{A}}_{\theta}$ be given by

(2.3) $\displaystyle\imath(a_{-l}\ldots a_{r}):=a_{0}.$

Then $(\theta,\imath)$ is an inner coding of $\theta^{(n)}$, and the factor
map $F_{\imath}$ is injective.

###### Proof.

Direct computation. ∎

We say that a factor map $F:X_{\theta}\to X_{\eta}$ between two substitution
shifts of equal length preserves the fixed point fibre if it maps the fixed
points of $\theta$ to fixed points of $\eta$.

######  Lemma 2.5.

Let $\eta$ and $\theta$ be length-$\ell$ substitutions and let
$\beta:\mathcal{A}_{\theta}\rightarrow\mathcal{A}_{\eta}$ be a code. If
$(\eta,\beta)$ is an inner encoding of $\theta$ then the factor map
$F_{\beta}$ preserves the fixed point fibre. Hence if $(\eta,\beta)$ is an
aperiodic inner encoding of $\theta$, and if $\theta$ has trivial height, then
the maximal equicontinuous factor map of $(X_{\theta},\sigma)$ factors through
$F_{\beta}$. If $\theta$ is primitive then the converse is true as well.

###### Proof.

Recall that we can assume, by going over to a power of the substitution if
needed, that all $\theta$-periodic points of $\theta$ are fixed. Let $v.u$ be
a fixed point of $\theta$ and hence also of $\theta^{m}$ for any $m\geq 1$. We
denote by $u=u_{0}\ldots$ and $\ldots v_{-1}=v$ the right and left infinite
parts.

Suppose that $\eta$ is inner encoded by $\beta$, that is, for each $n$ and
$a$, $\beta(\theta^{n}(a))=\eta^{n}(\beta(a))$. Then

$\displaystyle F_{\beta}(v.u)=\lim_{n}\beta\theta^{n}(v_{-1}.u_{0})$
$\displaystyle=\lim_{n}\eta^{n}(\beta(v_{-1}).\beta(u_{0}))$
$\displaystyle=\eta(\lim_{n}\eta^{n}(\beta(v_{-1}).\beta(u_{0})))=\eta(F_{\beta}(v.u)).$

The second statement is now immediate.

Conversely, suppose that $F_{\beta}$ sends fixed points to fixed points, so
that $F_{\beta}(v.u)$ is a fixed point of $\eta^{n}$ for any $n\geq 1$. If
$m<\ell^{n}$, then $\beta$ maps the $m$-th letter of $u$, which is
${\theta^{n}}_{m}(u_{0})$, to the $m$th letter of $\beta(u)$, which is
${\eta^{n}}_{m}(\beta(u_{0}))$. In particular, $\beta$ maps
$\theta_{m}(\theta_{k}(u_{0}))$ to
$\eta_{m}(\eta_{k}(\beta(u_{0})))=\eta_{m}(\beta(\theta_{k}(u_{0})))$. If
$\theta$ is primitive all letters arise as ${\theta^{N}}_{k}(u_{0})$ for some
$N$ and $k$ showing that $\eta_{n}(\beta(a))=\beta(\theta_{n}(a))$ for all
$a\in{\mathcal{A}}_{\theta}$. ∎

Any map $\beta:\mathcal{A}\rightarrow\mathcal{B}$ between sets defines a
partition ${\mathcal{P}}_{\beta}=\\{\beta^{-1}(b):b\in\mathcal{B}\\}$. We call
${\mathcal{P}}_{\beta}$ the partition associated to $\beta$.

######  Lemma 2.6.

Let $\theta$ be a length-$\ell$ substitution on $\mathcal{A}$.

  1. (1)

If $(\eta,\beta)$ is an inner coding of $\theta$ then the partition
$\mathcal{P}_{\beta}$ associated to $\beta$ satisfies

$\displaystyle\forall m\,\forall A\in{\mathcal{P}}_{\beta}\,\exists
B\in{\mathcal{P}}_{\beta}\mbox{ such that }\theta_{m}(A)\subset B.$

  2. (2)

Conversely, if there is a partition ${\mathcal{P}}$ of ${\mathcal{A}}$ such
that

$\forall m\,\forall A\in{\mathcal{P}}\,\exists B\in{\mathcal{P}}\mbox{ such
that }\theta_{m}(A)\subset B,$

then the canonical projection $\beta:{\mathcal{A}}\to{\mathcal{P}}$ defines an
inner coding $(\eta,\beta)$ of $\theta$ through
$\eta_{m}:=\beta\theta_{m}\beta^{-1}$.

###### Proof.

Suppose that $(\eta,\beta)$ is an inner coding of $\theta$. Then for all $m$
we have $\eta_{m}\circ\beta=\beta\circ\theta_{m}$. This implies that for all
$b\in{\mathcal{B}}$, $\beta\theta_{m}$ has the same value on all elements of
$\beta^{-1}(b)$. In other words for any $A\in{\mathcal{P}}_{\beta}$ we have
that $\beta\theta_{m}(A)$ is a singleton, and this implies that
$\theta_{m}(A)$ must be a subset of a member of ${\mathcal{P}}_{\beta}$.

As for the converse, if ${\mathcal{P}}$ is a partition with the required
property then we can define ${\mathcal{B}}:={\mathcal{P}}$, the code
$\beta:{\mathcal{A}}\to{\mathcal{B}}$ to be the map that sends
$a\in{\mathcal{A}}$ to the member of ${\mathcal{P}}$ to which it belongs and
for $b\in\mathcal{B}$, $\eta_{m}(b)$ is defined to be the member of
${\mathcal{P}}$ which contains $\theta_{m}(b)$, i.e.,
$\eta_{m}:=\beta\theta_{m}\beta^{-1}$. ∎

If $\mathcal{P}$ satisfies (2) of Lemma 2.6, we call the associated inner
encoding the inner encoding defined by the partition ${\mathcal{P}}$.

Although not all codes give rise directly to inner encoded substitutions, they
induce an inner encoded substitution in the following way: Let $\theta$ be a
substitution on the alphabet ${\mathcal{A}}$ and
$\tau:{\mathcal{A}}\to{\mathcal{B}}$ be a code. If ${\mathcal{P}}_{\tau}$ does
not satisfy Condition (2) of Lemma 2.6, we can define a finer partition
$\tilde{\mathcal{P}}_{\tau}$ which has this property, notably through the
equivalence relation $a\sim b$ if $\forall n\geq 0,0\leq m<\ell^{n}$,
$\tau({\theta^{n}}_{m}(a))=\tau({\theta^{n}}_{m}(b))$. We denote the
associated inner encoded system by $(\eta_{\tau},\beta_{\tau})$ and call it
the inner encoding defined by $\tau$. The alphabet of $\eta_{\tau}$ is usually
smaller than ${\mathcal{A}}$ and usually larger than ${\mathcal{B}}$. There is
thus a code $\tau^{\prime}:{\mathcal{A}}_{\eta}\to{\mathcal{B}}$ which
satisfies $\tau=\tau^{\prime}\circ\beta_{\tau}$. This is summarised in the
commuting Figure 1.

${{\mathcal{A}}_{\theta}}$${{\mathcal{A}}_{\eta_{\tau}}}$${{\mathcal{B}}}$$\scriptstyle{\beta_{\tau}}$$\scriptstyle{\tau}$$\scriptstyle{\tau^{\prime}}$
Figure 1. The commuting diagram of codes defined by a code $\tau$ and its
inner encoding $(\eta_{\tau},\beta_{\tau})$ .

###  2.5. Factors of substitution shifts

Our aim is to show that, up to conjugacy, any dynamical factor of any
primitive, aperiodic, constant length substitution ${\theta}$ of trivial
height is an inner encoding of a collaring $\theta^{(n)}$ of $\theta$, where
$n=(-l,r)$ with $l,r\leq 1$. Later we will see using the suspension
construction how the result transposes to the case of any height.

We first state in this context Theorem 2.7, which is [15, Theorem 22], and
which we use extensively. It focuses on shift factors which are given by a
code. Such shift factors are also called $\ell$-automatic. While the statement
of [15, Theorem 22] does not mention inner encoded substitutions, a look at
its proof shows that the substitution referred to in that theorem is exactly
the inner encoded substitution defined by the code. Theorem 2.7 uses the
additional assumption of pair aperiodicity which we explain.

We call the letters $a,b$ a periodic pair if there exists $p=p(a,b)$ and
$\ell^{p}$ such that $0\leq m<\ell^{p}$ such that ${\theta^{p}}_{m}(a)=a$ and
${\theta^{p}}_{m}(b)=b$. We define

(2.4) $p(\theta):=\mbox{lcm}\\{p(a,b):a,b\mbox{ are a periodic pair}\\},$

and call a substitution $\theta$ with $p(\theta)=1$ pair-aperiodic.
$\theta^{p(\theta)}$ is always pair-aperiodic [15].

######  Theorem 2.7.

Let $\theta$ be an aperiodic, pair aperiodic, primitive, length-$\ell$
substitution on $\mathcal{A}_{\theta}$, of trivial height. Let
$F_{\tau}:X_{\theta}\to Y\subset{\mathcal{B}}^{\mathbb{Z}}$ be the factor map
defined by a code $\tau:\mathcal{A}_{\theta}\rightarrow\mathcal{B}$. Consider
the inner coding $(\eta_{\tau},\beta_{\tau})$ of $\theta$ defined by $\tau$
with its accompanying code
$\tau^{\prime}:{\mathcal{A}}_{\eta_{\tau}}\to{\mathcal{B}}$. The induced
shift-commuting map
$F_{\tau^{\prime}}:X_{\eta_{\tau}}\to{\mathcal{B}}^{\mathbb{Z}}$ is injective
and has image $Y$. In other words $F_{\tau^{\prime}}$ is a conjugacy between
$X_{\eta_{\tau}}$ and $Y$.

We have summarise the statement in Figure 2. The diagram follows from Figure
1. The theorem states that $F_{\tau^{\prime}}$ is a conjugacy.

${X_{\theta}}$${X_{\eta_{\tau}}}$${Y}$$\scriptstyle{F_{\beta_{\tau}}}$$\scriptstyle{F_{\tau}}$$\scriptstyle{F_{\tau^{\prime}}}$
Figure 2. The commutative diagram for Theorem 2.7. $F_{\tau^{\prime}}$ is a
conjugacy.

######  Proposition 2.8.

Let $\theta$ be a primitive, aperiodic length-$\ell$ substitution, of trivial
height, and let $F:X_{\theta}\to Y\subset{\mathcal{B}}^{\mathbb{Z}}$ be a
factor map. There exists an $n=(-l,r)$-collaring $\theta^{(n)}$ and a code
$\tau:{\mathcal{A}}_{\theta^{(n)}}\to{\mathcal{B}}$ such that $F=F_{\tau}\circ
F_{\imath}^{-1}$. Also, if $Y=X_{\eta}$ is an aperiodic length-$\ell$
substitution shift and $F$ preserves the fixed point fibre, then $l,r\leqslant
1$.

The statement of this proposition is summarised in Figure 3.

${X_{\theta}}$${X_{\theta^{(n)}}}$${Y}$$\scriptstyle{F}$$\scriptstyle{F_{\iota}}$$\scriptstyle{F_{\tau}}$
Figure 3. The commutative diagram for Prop. 2.8. The composition
$F_{\beta_{\tau}}\circ F_{\imath}^{-1}$ preserves the fixed point fibre.

###### Proof.

Let $l$, $r$ be the left, right radius of $F$ respectively, and let
$n=(-l,r)$. Then there is a code
$\tau:{\mathcal{A}}_{\theta^{(n)}}\to{\mathcal{B}}$ such that
$F_{\tau}:X_{\theta^{(n)}}\rightarrow Y$ is a factor map and such that
$F=F_{\tau}\circ F_{\imath}^{-1}$. Note that by Lemmas 2.4 and 2.5,
$F_{\imath}^{-1}$ maps fixed points to fixed points.

To prove the second statement, suppose that $Y=X_{\eta}$ for some
length-$\ell$ substitution and that $F$ preserves the fibre of fixed points.

Let $R=\max\\{l,r\\}$. We know that $(F(x))_{i}$ is determined by
$x_{[i-R,i+R]}$, and thus $(F(x))_{[0,\ell^{n})}$ is determined by
$x_{[-R,\ell^{n}+R)}$. Thus, if we choose
$n\geqslant\lceil\log_{\ell}R\rceil$, this ensures $R\leqslant\ell^{n}$, hence
$(F(x))_{[0,\ell^{n})}$ is entirely determined by $x_{[-\ell^{n},2\ell^{n})}$.

Fix $n\geqslant\lceil\log_{\ell}R\rceil$. Since $F$ sends fixed points to
fixed points, then $F(\theta^{n}(X_{\theta}))\subseteq\eta^{n}(X_{\eta})$.
Define $G\colon X_{\theta}\rightarrow X_{\eta}$ as $G:=\eta^{-n}\circ
F\circ\theta^{n}$. Note that $F\circ\theta^{n}$ maps $X_{\theta}$ to
$\eta^{n}(X_{\eta})$, and the map
$\eta^{-n}\colon\eta^{n}(X_{\eta})\rightarrow X_{\eta}$ is well-defined by
recognisability of $\eta$, so $G$ is also well-defined. It is not hard to
check that $G$ is continuous and $G\circ\sigma=\sigma\circ G$, so $G$ is also
a factor map.

Given knowledge of $x_{[-1,1]}$, we know
$(\theta^{n}(x))_{[-\ell^{n},2\ell^{n})}$ and hence
$(F\circ\theta^{n}(x))_{[0,\ell^{n})}$ is also determined, as discussed above.

Recall that a substitution $\eta$ is injective if the map
$\eta:{\mathcal{A}}\to{\mathcal{A}}^{\ell}$ is injective. If $\eta$ is
injective, then $(F\circ\theta^{n}(x))_{[0,\ell^{n})}$ determines
$(\eta^{-n}\circ F\circ\theta^{n}(x))_{0}$, and thus $G$ has left and right
radius at most $1$. Also, $G$ must send fixed points to fixed points. If
$\eta$ is non-injective on letters, we can replace it with an injectivisation
$\tilde{\eta}$ of $\eta$, which is the standard example of an inner encoding
of $\eta$, with two letters identified if and only if their images under
$\eta$ are equal, see [2]. As the natural conjugacy $X_{\eta}\rightarrow
X_{\tilde{\eta}}$ has radius $0$, this will not change the desired result,
that $G$ has left and right radius at most $1$.

It remains to show that the radius restriction for $G$ implies the same
restriction for $F$. Minimality implies that any factor map
$X_{\theta}\rightarrow X_{\eta}$ is entirely determined by the image of a
single point. As the fixed point fibres of substitutions are finite, there can
only be finitely many factor maps $F_{i}:X_{\theta}\to X_{\eta}$ which
preserve the fixed point fibre. Let ${\mathcal{F}}:=\\{F_{1},\ldots,F_{k}\\}$
be the collection of those. Let $l_{i},r_{i}$ be the left and right radius of
each $F_{i}$. If we define $R=\max\\{l_{1},r_{1},\ldots,l_{k},r_{k}\\}$ and
take $n\geqslant\lceil\log_{\ell}R\rceil$, then the above argument shows that
$\eta^{-n}\circ F_{i}\circ\theta^{n}$ preserves the fixed point fibre of
$\theta$ and hence the map ${\mathcal{F}}\rightarrow{\mathcal{F}}$ given by
$F_{i}\mapsto\eta^{-n}\circ F_{i}\circ\theta^{n}$ is well-defined. This map is
a bijection. For, if $\eta^{-n}\circ F_{i}\circ\theta^{n}=\eta^{-n}\circ
F_{j}\circ\theta^{n}$, then $F_{i}\circ\theta^{n}(u)=F_{j}\circ\theta^{n}(u)$
for any point $u\in X_{\theta}$, and in particular for any fixed point $u$ of
$\theta$, so that $F_{i}(u)=F_{j}(u)$ for $u$ a fixed point. Now minimality
implies that the map is injective and since ${\mathcal{F}}$ is finite it is
also surjective.

To conclude, we have seen above that every factor map of the form
$\eta^{-n}\circ F_{i}\circ\theta^{n}$ has left and right radius at most $1$
and so the same must hold for all $F_{i}$. ∎

######  Corollary 2.9.

Let $\theta$ be an aperiodic, primitive, length-$\ell$ substitution on
$\mathcal{A}_{\theta}$, of trivial height. Let $F:X_{\theta}\to Y$ be a shift
factor. Then there exists an $n=(-l,r)$-collaring $\theta^{(n)}$ with $l,r\leq
1$, a natural number $p\geq 1$, a length-$\ell^{p}$ substitution $\eta$ and a
code $\beta:{\mathcal{A}}_{{\theta^{(n)}}^{p}}\to{\mathcal{A}}_{\eta}$ such
that $(\eta,\beta)$ is an inner encoding of ${\theta^{(n)}}^{p}$ and
$(X_{\eta},\sigma)$ is conjugate to $(Y,\sigma)$.

###### Proof.

By Proposition 2.8 there is a factor map $F_{\tau}:X_{\theta^{(n)}}\to Y$ for
some collaring $\theta^{(n)}$ of $\theta$ such that the diagram in Figure 3
commutes.

Let $p$ be such that ${\theta^{(n)}}^{p}$ is pair aperiodic. We apply Theorem
2.7 to $F_{\tau}:X_{{\theta^{(n)}}^{p}}\to Y$ to obtain the inner encoding
$(\eta_{\tau},\beta_{\tau})$ of ${\theta^{(n)}}^{p}$. This situation is
summarised in the following diagram. Note that $X_{{\theta^{(n)}}^{p}}$ is
equal to $X_{{\theta^{(n)}}}$.

${X_{\theta}}$${X_{{\theta^{(n)}}^{p}}}$${X_{\eta_{\tau}}}$${Y}$$\scriptstyle{F_{\iota}^{-1}}$$\scriptstyle{F}$$\scriptstyle{F_{\tau}}$$\scriptstyle{F_{\beta_{\tau}}}$$\scriptstyle{F_{\tau^{\prime}}}$

If $n=(-l,r)$ with $l,r\leq 1$ then we are done, the factor $X_{\theta}\to Y$
is conjugate to the factor $F_{\beta_{\tau}}:X_{{\theta^{(n)}}^{p}}\to
X_{\eta_{\tau}}$ where $(\eta_{\tau},\beta_{\tau})$ is an inner encoding.

If $n=(-l,r)$ with perhaps $l>1$ or $r>1$ then we need one more step. As
$F_{\imath}$ and $F_{\beta_{\tau}}$ are both obtained from inner encodings,
they preserve the fixed point fibres. It follows that the composition
$\tilde{F}:=F_{\beta_{\tau}}\circ F_{\imath}^{-1}:X_{\theta}\to
X_{\eta_{\tau}}$ preserves the fixed point fibre. We repeat the whole argument
above but with $X_{\eta_{\tau}}$ in place of $Y$. We can apply Proposition
2.8, to obtain the commutative diagram

${X_{\theta}}$${X_{{\theta^{(\tilde{n})}}^{\tilde{p}}}}$${X_{\eta_{\tilde{\tau}}}}$${X_{\eta_{\tau}}}$$\scriptstyle{\tilde{F}}$$\scriptstyle{F_{\iota}}$$\scriptstyle{F_{\tilde{\tau}}}$$\scriptstyle{F_{\beta_{\tilde{\tau}}}}$$\scriptstyle{F_{\tilde{\tau}^{\prime}}}$

however this time with $\tilde{n}=(\tilde{l},\tilde{r})$ with
$\tilde{l},\tilde{r}\leq 1$. This gives us a chain of conjugacies, namely
between the factor $F:X_{\theta}\to Y$ and $\tilde{F}:X_{\theta}\to
X_{\eta_{\tau}}$ as we saw above, and then between $\tilde{F}:X_{\theta}\to
X_{\eta_{\tau}}$ and
$F_{\beta_{\tilde{\tau}}}:X_{{\theta^{(\tilde{n})}}^{\tilde{p}}}\to
X_{\eta_{\tilde{\tau}}}$. ∎

We note that the number $p$ in Corollary 2.9 is bounded by $p(\theta^{(n)})$
in (2.4).

Combining Corollary 2.9 and Lemma 2.5, we obtain

######  Corollary 2.10.

Let $\theta$ be an aperiodic, primitive, length-$\ell$ substitution on
$\mathcal{A}_{\theta}$, of trivial height, with maximal equicontinuous factor
map $\pi_{\theta}:X_{\theta}\rightarrow\mathbb{Z}_{\ell}$. If
$(X_{\theta},\sigma)$ has an almost automorphic shift factor, then it has a
shift factor $\pi:X_{\theta}\rightarrow Y$ such that
$\pi_{\theta}=\pi_{Y}\circ\pi$, where $\pi_{Y}:Y\rightarrow\mathbb{Z}_{\ell}$
is an almost injective factor map.

##  3\. The semigroup of a substitution, inner encodings and outer encodings

In this section we completely characterise the length-$\ell$ substitutions
$\theta$ which have a factor that is almost automorphic over the maximal
equicontinuous factor of $(X_{\theta},\sigma)$, in Theorem 3.27 and Corollary
3.31. In Section 2 we have seen that such a factor is conjugate to one which
is obtained by an inner encoding of $\theta$ which has a coincidence, provided
that $\theta$ has trivial height. We will do this here by using the algebraic
structure of the semigroup $S_{\theta}$ which we introduce in Definition 3.6.
We will find that there are always inner encodings of $\theta$ which have a
coincidence, but the desired almost automorphic factor will exist only if the
relevant inner encoding is aperiodic. Finally we explain how to transpose
these results to substitutions with non-trivial height.

###  3.1. Semigroup preliminaries

We need some background material on subsemigroups of the semigroup
${\mathcal{F}}(X)$ of maps from $X$ to itself; see also [3, 8, 16]. Here $X$
is just a set and the semigroup product is composition of functions. For our
purposes $X$ will be a finite set. We denote by ${\mathcal{P}}(X)$ the set of
subsets of $X$.

Let $f:X\to Y$. We denote by $f^{-1}:{\mathcal{P}}(Y)\to{\mathcal{P}}(X)$ the
pre-image map but simply write $f^{-1}(y)$ for $f^{-1}(\\{y\\})$. The map $f$
defines an equivalence relation as $x\sim x^{\prime}$ if $f(x)=f(x^{\prime})$.
We denote the associated partition by ${\mathcal{P}}_{f}$, that is,

${\mathcal{P}}_{f}=\\{f^{-1}(y):y\in Y\\}.$

The cardinality of ${\mathcal{P}}_{f}$ equals the rank of $f$, that is the
cardinality of its image $\mbox{\rm im}f$.

Recall two of Green’s equivalence relations ${\mathcal{L}}$, ${\mathcal{R}}$.
They give a first way to approach and organise a semigroup $S$. We say that
$a,b\in S$ are ${\mathcal{L}}$-related, or ${\mathcal{R}}$-related, if they
generate the same left, or right ideal, respectively. If $S$ is a group, then
these relations coincide with the full relation. Each of the above relations
partition the semigroup. ${\mathcal{R}}$ is a left congruence and therefore
$S/{\mathcal{R}}$ a left-$S$-module. ${\mathcal{L}}$ is a right congruence and
therefore $S/{\mathcal{L}}$ a right-$S$-module.

######  Lemma 3.1.

Let $S$ be a semigroup of ${\mathcal{F}}(X)$. If $f,g\in S$ are
${\mathcal{R}}$-related then $\mbox{\rm im}f=\mbox{\rm im}g$. If $f,g\in S$
are ${\mathcal{L}}$-related then ${\mathcal{P}}_{f}={\mathcal{P}}_{g}$.

###### Proof.

Let $f$ and $g$ be ${\mathcal{R}}$-related, that is, $f=g$ or there is
$f^{\prime},g^{\prime}$ such that $f=gg^{\prime}$, $g=ff^{\prime}$. Then
clearly $\mbox{\rm im}f\subset\mbox{\rm im}g$ and $\mbox{\rm
im}g\subset\mbox{\rm im}f$.

Let $f$ and $g$ be ${\mathcal{L}}$-related, that is, $f=g$ or there is
$f^{\prime},g^{\prime}$ such that $f=g^{\prime}g$, $g=f^{\prime}f$. Then
$f^{-1}(x)=g^{-1}({g^{\prime}}^{-1}(x))$ showing that the members of the
partition ${\mathcal{P}}_{f}$ are unions of members of the partition of
${\mathcal{P}}_{g}$, i.e. the partition ${\mathcal{P}}_{g}$ is finer than
${\mathcal{P}}_{f}$. A symmetric argument shows that
${\mathcal{P}}_{f}={\mathcal{P}}_{g}$. ∎

An element $f\in S\subset{\mathcal{F}}(X)$ is completely regular if it has a
normal inverse, that is, there exists $g\in S$ such that $fgf=f$ and $fg=gf$.
This implies that $fg$ is an idempotent. As normal inverses are unique we call
$fg$ the idempotent associated to $f$ and denote it $f^{0}$.

A completely simple semigroup is a semigroup which has no proper bilateral
ideals and which contains an idempotent. The kernel of a semigroup, if it
exists, is its smallest bilateral ideal. If $X$ is finite then any sub-
semigroup of ${\mathcal{F}}(X)$ admits a kernel. We denote the kernel of $S$
by $\ker S$; if it contains an idempotent it is completely simple, and any
element is completely regular.

######  Lemma 3.2.

Let $X$ be a finite set and $S\subset{\mathcal{F}}(X)$. Then $S$ is completely
simple if and only if all its functions have the same rank. Moreover, if
$f,g\in S$ belong to the same right ideal, then $g^{0}f=f$, while if $f,g$
belong to the same left ideal, then $f=fg^{0}$.

###### Proof.

Given $n\in\mathbb{N}$, the subset of functions of rank $\leq n$ form a
bilateral ideal in $S$. Hence the condition that all functions have the same
rank is necessary for simplicity.

Now suppose that all functions of $S$ have the same rank. Let $f\in S$. Then
$\mbox{\rm im}f=\mbox{\rm im}f^{k}$ for all $k\geq 1$. As $X$ is finite there
must by a $k>0$ such that $f=f^{k+1}$. Hence $f^{k}=f^{0}\in S$. The
restriction of $f^{0}$ to $\mbox{\rm im}f$ is the identity. Let also $g\in S$.
As $fg\in S$ the argument above shows that there is $k>0$ such that the
restriction of $(gf)^{k}$ to $\mbox{\rm im}gf=\mbox{\rm im}g$ is the identity.
It follows that $(gf)^{k}g=g$. Hence $g$ belongs to the bilateral ideal
generated by $f$. Choosing $f\in\ker S$ we see that $S=\ker S$ and so is
simple.

Suppose that $f,g\in S$ belong to the same right ideal. Then $f=gg^{\prime}$
for some $g^{\prime}\in S$. Hence $g^{0}f=g^{0}gg^{\prime}=gg^{\prime}=f$.
Similarily, if $f,g\in S$ belong to the same left ideal. Then $f=g^{\prime}g$
for some $g^{\prime}\in S$. Hence $fg^{0}=g^{\prime}gg^{0}=f$. ∎

######  Corollary 3.3.

Let $X$ be a finite set and $S\subset{\mathcal{F}}(X)$. The kernel of $S$ is
given by its functions of minimal rank. It is completely simple.

The Rees structure theorem ([3, Theorem 3.5] or [11, Theorem 2.1]) tells us
that a completely simple semigroup (without zero) is isomorphic to a matrix
semigroup $S\cong I\times G\times\Lambda$ where $I$ indexes the right ideals
of $S$, $\Lambda$ indexes the left ideals of $S$, $G$ is a group and there is
an $I\times\Lambda$ matrix $M$ such that multiplication in $I\times
G\times\Lambda$ is defined as

$(i,g,\lambda)(i^{\prime},g^{\prime},\lambda^{\prime})=(i,gM_{\lambda,i^{\prime}}g^{\prime},\lambda^{\prime})$

The right ideals are given by $\\{i\\}\times G\times\Lambda$, $i\in I$, and
the left ideals by $I\times G\times\\{\lambda\\}$, $\lambda\in\Lambda$. In
particular one sees that any right ideal intersects any left ideal non-
trivally.

######  Proposition 3.4.

Let $S\subset{\mathcal{F}}(X)$ be a completely simple semigroup and $f,g,\in
S$. The following are equivalent.

  1. R1

$f$ and $g$ are ${\mathcal{R}}$-related.

  2. R2

$f$ and $g$ belong to the same right ideal.

  3. R3

$f$ and $g$ have the same image.

Moreover, the following are equivalent.

  1. L1

$f$ and $g$ are ${\mathcal{L}}$-related.

  2. L2

$f$ and $g$ belong to the same left ideal.

  3. L3

$f$ and $g$ define the same partition.

###### Proof.

A completely simple semigroup (without zero) is the disjoint union of its
right ideals and all the right ideals are simple. As the ${\mathcal{R}}$-class
of any element of a simple right ideal is that right ideal, we have
equivalence between R1 and R2. It remains to show that R3 implies R2: Suppose
that $f$ and $g$ belong to the same left ideal. Then $fg^{0}=f$. If also
$\mbox{\rm im}f=\mbox{\rm im}g$ then $g^{0}f=f$, hence $f$ and $g$ belong to
the same right ideal. Now suppose that $f$ and $g$ are arbitrary elements
satisfying $\mbox{\rm im}f=\mbox{\rm im}g$. Then there is $h\in S$ which is in
the same right ideal as $g$ and the same left ideal as $f$. The first property
implies $\mbox{\rm im}h=\mbox{\rm im}g$ and, by the above, $h$ is also in the
same right ideal as $f$. Hence $f$ and $g$ belong to the same right ideal.

The equivalence between L1 and L2 is shown as for right ideals. We show that
L3 implies L2: Suppose that $f$ and $g$ belong to the same right ideal. Then
$g^{0}f=f$. If also ${\mathcal{P}}_{f}={\mathcal{P}}_{g}$ then $fg^{0}=f$,
hence $f$ and $g$ belong to the same left ideal. The rest of the argument is
as for right ideals. ∎

######  Lemma 3.5.

Let $S$ be a semigroup which admits a kernel. Let $\Phi:S\to T$ be an
epimorphism onto another semigroup $T$. The restriction of $\Phi$ to the
kernel of $S$ is an epimorphism onto the kernel of $T$. Morever, if $S$ has a
unique minimal left ideal then also $T$ has a unique minimal left ideal.

###### Proof.

Any epimorphism preserves ideals: We show this for left ideals. Let $I$ be a
left ideal of $S$ and $t\in T$; we ought to show that
$t\Phi(I)\subset\Phi(I)$. Since $\Phi$ is onto there is $s\in S$ such that
$\Phi(s)=t$. Then $t\Phi(I)=\Phi(sI)\subset\Phi(I)$.

Furthermore, the preimage of an ideal is an ideal: We show this for left
ideals. Let $I$ be a left ideal of $T$ and $s\in S$; we ought to show that
$s\Phi^{-1}(I)\subset\Phi^{-1}(I)$. Indeed, $\Phi(s\Phi^{-1}(I))=tI\subset I$.

Now the above implies that $I:=\Phi(\ker S)$ is the kernel of $T$: Indeed, by
the first paragraph it is a bilateral ideal. Let $J\subset I$ be a bilateral
ideal of $T$. Then $\Phi^{-1}(J)$ is a bilateral ideal in $S$ by the second
paragraph. $\Phi^{-1}(J)$ thus contains $\ker S$. Hence $\Phi(\ker S)\subset
J$ showing that $J=I$.

Suppose now that $\ker S$ is left simple and that $L_{1},L_{2}$ are left
ideals of $\ker T$. Then $\Phi^{-1}(L_{1})\cap\ker S$ and
$\Phi^{-1}(L_{2})\cap\ker S$ belong to the same left ideal. As epimorphisms
preserve ideals their image under $\Phi$ belongs to the same left ideal. Hence
$L_{1}$ and $L_{2}$ belong to the same left ideal. Hence $L_{1}=L_{2}$. ∎

###  3.2. The semigroup of a length-$\ell$ substitution

Let ${\mathcal{A}}$ be a finite set. Let $S\subset\mathcal{F}(\mathcal{A})$.
For $n\in\mathbb{N}$ we define $S^{(n)}$ to be the family of maps which have
rank smaller or equal $n$. If $S^{(n)}$ is not empty then it is a two-sided
ideal of $S$.

######  Definition 3.6.

The semigroup $S_{\theta}$ of a length-$\ell$ substitution $\theta$ over the
alphabet ${\mathcal{A}}$ is the subsemigroup of $\mathcal{F}(\mathcal{A})$
generated by the column maps $\theta_{i}$, $i=0,\cdots,\ell-1$.

Recall from (2.2) that the naïve column number of $\theta$ is the smallest
rank of a product of column maps. From Corollary 3.3 we obtain the following.

######  Lemma 3.7.

Let $\theta$ be a constant length substitution. The kernel of $S_{\theta}$ is
$S_{\theta}^{(c)}$, where $c$ is the naïve column number of $\theta$.

######  Definition 3.8.

The minimal sets of the substitution $\theta$ are the images of the maps of
$S_{\theta}$ of minimal rank. We denote the family of minimal sets by
$U_{\theta}$, i.e.,

$U_{\theta}:=\\{\mbox{\rm im}f:f\in\ker S_{\theta}\\}.$

If $U_{\theta}$ is a cover of ${\mathcal{A}}$, that is,
${\mathcal{A}}=\bigcup_{f\in\ker S_{\theta}}\mbox{\rm im}f$, then we call the
substitution essentially surjective. Given $U_{\theta}$ we define a relation
on the members by $A\sim B$ if $A\cap B\neq\emptyset$. The transitive closure
of this relation is an equivalence relation on $\bigcup_{f\in\ker
S_{\theta}}\mbox{\rm im}f$ which defines a partition which we call the
coincidence partition and denote by ${\mathcal{P}}_{\theta}$.

Note that while $S_{\theta^{N}}\subset S_{\theta}$ , for any $N\geq 1$, the
inclusion may be strict. However their kernels are always equal, by the next
lemma.

######  Lemma 3.9.

Let $\theta$ be a substitution and $N\geq 1$. Then $\ker S_{\theta^{N}}=\ker
S_{\theta}$. In particular $U_{\theta}$ and $U_{\theta^{N}}$ coincide.

###### Proof.

By definition of the column rank, $\theta$ and $\theta^{N}$ have the same
column rank. Clearly $S_{\theta^{N}}^{(c)}\subset S_{\theta}^{(c)}$. To see
that the inclusion is surjective, recall that any element $f$ of $\ker
S_{\theta}$ is completely regular and hence we can factorise
$f=f{f^{0}}^{N-1}$, where we recall that $f^{0}$ is the idempotent generated
by $f$. This shows that $\ker S_{\theta}=\ker S_{\theta^{N}}$ and immediately
implies $U_{\theta}=U_{\theta^{N}}$. ∎

######  Lemma 3.10.

A primitive substitution is essentially surjective.

###### Proof.

Suppose that $\theta$ is primitive. Let $a\in{\mathcal{A}}$ and $b\in\mbox{\rm
im}f$ for some $f\in\ker S_{\theta}$. By primitivity $a$ occurs in
$\theta^{N}(b)$ for some $N$. Hence $a\in\mbox{\rm im}gf$ for some $g\in
S_{\theta}$. Clearly $gf\in\ker S_{\theta}$. Hence $a\in\bigcup_{f\in\ker
S_{\theta}}\mbox{\rm im}f$. ∎

The condition of primitivity is sufficient but not necessary: the length $2$
substitution on $\\{a,b\\}$, $\theta(a)=aa$, $\theta(b)=ab$ is not primitive
and $b$ does not belong to a minimal set. The converse need not be true: the
length $1$ substitution $\theta={\mathbf{1}}$, where ${\mathbf{1}}$ is the
identity map, is not primitive, but $U_{\theta}=\\{{\mathcal{A}}\\}$.

######  Lemma 3.11.

Let $\theta$ be an essentially surjective substitution. Then
${\mathcal{P}}_{\theta}$ is a partition of ${\mathcal{A}}$ which satisfies
Condition (2) of Lemma 2.6. Its associated inner encoding
$(\eta_{{\mathcal{P}}_{\theta}},\beta_{{\mathcal{P}}_{\theta}})$ has naïve
column number $c=1$.

###### Proof.

Let $A\in U_{\theta}$, that is, $A=\mbox{\rm im}g$ for some $g\in\ker
S_{\theta}$. Let $f\in S_{\theta}$. Then $f(A)\in U_{\theta}$ as $fg\in\ker
S_{\theta}$. Now if $A\cap A^{\prime}\neq\emptyset$ then also $f(A)\cap
f(A^{\prime})\neq\emptyset$. Thus if two members $A,A^{\prime}$ of the cover
$U_{\theta}$ belong to the same member of $\mathcal{P}_{\theta}$ then also
$f(A)$ and $f(A^{\prime})$ belong to the same member of
$\mathcal{P}_{\theta}$. This implies Condition (2) of Lemma 2.6 for
$\mathcal{P}_{\theta}$. Furthermore, if $f$ belongs to the kernel of
$S_{\theta}$ then $f(A)=\mbox{\rm im}fg=\mbox{\rm im}f$ and so $f(A)$ is the
same for all $A\in U_{\theta}$. Hence
$\beta_{{\mathcal{P}}_{\theta}}f\beta_{{\mathcal{P}}_{\theta}}^{-1}$ has rank
$1$, and so $\eta_{{\mathcal{P}}_{\theta}}$ has naïve column number $1$. ∎

######  Definition 3.12.

Let $\theta$ be an essentially surjective substitution with coincidence
partition ${\mathcal{P}}_{\theta}$. We call the inner encoding defined by
${\mathcal{P}}_{\theta}$ the inner encoding associated to $\theta$. We denote
this inner encoding
$(\eta_{{\mathcal{P}}_{\theta}},\beta_{{\mathcal{P}}_{\theta}})$ by
$(\eta_{\theta},\beta_{\theta})$.

As $\eta_{\theta}$ has column number $1$, then since $h$ divides $c(\theta)$,
it has a coincidence and trivial height. Its associated dynamical system is
thus almost automorphic. However, it need not be aperiodic, nor, if it is
aperiodic, does it have to have the same maximal equicontinuous factor as
$\theta$. Indeed, if $\theta$ has non-trivial height then the maximal
equicontinuous factor of $\eta_{\theta}$ is strictly smaller than the MEF of
$\theta$. In the rest of this section we will show two things: if
$\eta_{\theta^{(n)}}$ is periodic for all the collared versions of $\theta$
(we only need $n=(l,r)$ with $l,r\leq 1$) then $X_{\theta}$ does not admit an
aperiodic almost automorphic factor, and if the height is non-trivial we can
reduce the task to working with the pure base of $\theta$.

######  Lemma 3.13.

Let $\theta$ be an essentially surjective substitution and $N\geq 1$. The
inner encodings $(\eta_{\theta^{N}},\beta_{\theta^{N}})$ and
$(\eta_{\theta},\beta_{\theta})$ associated to $\theta^{N}$ and $\theta$
satisfy $\eta_{\theta^{N}}={\eta_{\theta}}^{N}$ and
$\beta_{\theta^{N}}=\beta_{\theta}$.

###### Proof.

The statement about the codes, $\beta_{\theta^{N}}=\beta_{\theta}$, follows
directly from Lemma 3.9. Let $0\leq j\leq\ell^{N}-1$. There are
$j_{1},\cdots,j_{N}$ such that
${\theta^{N}}_{j}=\theta_{j_{1}}\cdots\theta_{j_{N}}$. Hence
${\eta_{\theta^{N}}}_{j}=\beta_{\theta}\theta_{j_{1}}\cdots\theta_{j_{N}}\beta_{\theta}^{-1}={\eta_{\theta}}_{j_{1}}\cdots{\eta_{\theta}}_{j_{N}}$.
∎

We provide an algebraic property of $S_{\theta}$ characterising column number
$1$. A semigroup is left zero if every element acts as a zero element when
multiplying from the left, i.e. $xy=x$ for all $x,y\in S$. If $S$ is
completely simple, then it is left zero if and only if the
${\mathcal{R}}$-relation is trivial (equal to the diagonal relation).

######  Lemma 3.14.

A constant length substitution has naïve column number $1$ if and only if
$\ker S_{\eta}$ is a left zero semigroup. If this is the case and if $\theta$
is essentially surjective then $\ker S_{\eta}\ni x\mapsto\mbox{\rm
im}x\in{\mathcal{A}}$ is a bijection.

###### Proof.

$\theta$ has naïve column number $1$ if and only if $S_{\theta}$ contains an
element of rank $1$ which is equivalent to saying that $\ker S_{\theta}$
contains exactly the maps of rank $1$ of $S_{\theta}$. Any collection of rank
1 maps from ${\mathcal{F}}({\mathcal{A}})$ forms a left zero semigroup.

Now, suppose that the naïve column number is $c>1$. If $S_{\theta}$ has more
than one minimal left ideal, then $\ker S_{\theta}$ is not a left zero
semigroup. If $S_{\theta}$ has a unique minimal left ideal, then, as we will
see in Theorem 4.1, $\theta$ inner encodes a substitution $\eta$ such that
$S_{\eta}$ is a non-trivial group. In particular $\ker S_{\eta}=S_{\eta}$ and
since an inner encoding induces an epimorphism from $\ker S_{\theta}$ to $\ker
S_{\eta}$, $\ker S_{\theta}$ cannot be left zero.

Any rank $1$ map can be identified with the unique element in its image. Hence
$\ker S_{\eta}\ni x\mapsto\mbox{\rm im}x\in{\mathcal{A}}$ is injective and, if
$U_{\theta}$ is a cover, also surjective. ∎

###  3.3. The canonical outer encoding

######  Definition 3.15.

Let $\theta$ and $\eta$ be length-$\ell$ substitutions. We say that $\eta$ is
outer encoded by $\theta$ if there is an epimorphism
$\Phi:S_{\theta}\rightarrow S_{\eta}$ such that $\eta_{m}=\Phi(\theta_{m})$
for $0\leq m\leq\ell-1$.

We may also say that $(\eta,\Phi)$ is outer encoded by $\theta$, that $\eta$
is an outer encoded substitution of $\theta$, or that $\eta$ is an outer
encoding of $\theta$. Note that if $(\eta,\beta)$ is inner encoded by
$\theta$, then $\eta$ is outer encoded with epimorphism

$\Phi_{\beta}(f)=\beta f\beta^{-1}.$

However an outer encoding does not necessarily define an inner encoding or
indeed a dynamical factor; see Example 3.22.

######  Corollary 3.16.

If $(\eta,\Phi)$ is outer encoded by $\theta$, then the restriction of $\Phi$
to $\ker S_{\theta}$ is an epimorphism onto $\ker S_{\eta}$.

###### Proof.

This follows from Lemma 3.5 as $S_{\theta}$ is finite and hence admits a
kernel. ∎

######  Definition 3.17.

Let $\theta$ be a length-$\ell$ substitution with naïve column number $c$. Let
${\mathcal{B}}=\ker(S_{\theta})/{\mathcal{R}}$, and
${}^{c}\Phi:S_{\theta}\rightarrow\mathcal{F}(\mathcal{B})$ be the morphism
defined by

(3.1) $\displaystyle{}^{c}\Phi(f)([x]_{\mathcal{R}}):=[fx]_{\mathcal{R}}.$

The canonical outer encoding of $\theta$ is the substitution
${}^{c}\theta:{\mathcal{B}}\rightarrow{\mathcal{B}}^{\ell}$ defined by

(3.2) $\displaystyle{}^{c}\theta_{m}:={}^{c}\Phi(\theta_{m}).$

The semigroup of a bijective substitution is a group. Therefore
$S_{\theta}=\ker S_{\theta}$ and $S_{\theta}/{\mathcal{R}}$ consists of a
single point. Hence the canonical outer encoding of $\theta$ is the one letter
periodic substitution, which is, of course, a trivial inner encoding.

######  Example 3.18.

The canonical outer encoded substitution of the collared Thue-Morse system
$\theta^{(0,1)}$ is the period doubling substitution, and it is also an inner
encoding, see Section 3.6. Note that we must take a collared version of
$\theta$, as the canonical outer encoding of any bijective substitution is
trivial.

We are interested in finding almost automorphic factors. The following lemma
explains our interest in canonical outer encodings. Note there is no need to
assume that $\theta$ is primitive.

######  Lemma 3.19.

The canonical outer encoding $({}^{c}\theta,{}^{c}\Phi)$ of $\theta$ is
primitive and has column number $1$, i.e., has trivial height and a
coincidence.

###### Proof.

We will show that there is an element $f\in S_{{}^{c}\theta}$ whose image
contains only one letter; this implies that ${}^{c}\theta$ has column number
$1$ and therefore a coincidence and trivial height. By Lemma 3.5, ${}^{c}\Phi$
restricts to an epimorphism from $\ker S_{\theta}$ to $\ker S_{{}^{c}\theta}$.
Given $f\in\ker S_{\theta}$ and $[y]_{\mathcal{R}}\in\ker
S_{\theta}/{\mathcal{R}}$ we have
${}^{c}\Phi(f)([y]_{\mathcal{R}})=[fy]_{\mathcal{R}}=[f]_{\mathcal{R}}$. We
thus see that the image of ${}^{c}\Phi(f)$ contains only the letter
$[f]_{\mathcal{R}}$. Hence the column number is $1$.

To see that ${}^{c}\theta$ is primitive, we need to show that for any two
letters $[x],[y]\in\ker S_{{}^{c}\theta}/{\mathcal{R}}$, there is an $f\in
S_{{}^{c}\theta}$ such that $[fx]=[y]$. As any left ideal of $\ker S_{\theta}$
intersects any right ideal of $\ker S_{\theta}$, any two classes
$[x],[y]\in\ker S_{{}^{c}\theta}/{\mathcal{R}}$ have representatives $x,y$
which belong to the same ${\mathcal{L}}$-class. This means that there is $f\in
S_{{}^{c}\theta}$ such that $y=fx$. ∎

######  Proposition 3.20.

Let $\theta$ be an essentially surjective substitution and
$({}^{c}\theta,{}^{c}\Phi)$ be the canonical outer encoding of $\theta$. Then
${}^{c}\theta$ is an inner encoding of $\theta$ if and only if $U_{\theta}$ is
a partition of ${\mathcal{A}}$. In this case, and upon identifying $\ker
S_{\theta}/{\mathcal{R}}$ with $U_{\theta}$, we have
${}^{c}\theta=\eta_{\theta}$, the inner encoding associated with $U_{\theta}$.

###### Proof.

Recall that the alphabet of ${}^{c}\theta$ is $\ker S_{\theta}/{\mathcal{R}}$.
By Lemma 3.2 the map $\ker
S_{\theta}/{\mathcal{R}}\ni[x]_{\mathcal{R}}\mapsto\mbox{\rm im}x\in
U_{\theta}$ is a bijection.

If $U_{\theta}$ is a partition of ${\mathcal{A}}$ then it coincides with the
coincidence partition ${\mathcal{P}}_{\theta}$ and hence we may identify
$\beta_{\theta}:{\mathcal{A}}\to{\mathcal{P}}_{\theta}$ with the code
$a\mapsto[x]_{\mathcal{R}}$ where $x$ is any function from $\ker S_{\theta}$
which contains $a$ in its image. Say $a=x(b)$. We then have
${}^{c}\theta_{m}(\beta_{\theta}(a))=[\theta_{m}x]_{\mathcal{R}}$ while
$\beta_{\theta}(\theta_{m}(a))=\beta_{\theta}(\theta_{m}x(b))=[\theta_{m}x]_{\mathcal{R}}$.
Hence ${}^{c}\theta=\eta_{\theta}$.

Suppose that ${}^{c}\theta$ is an inner encoding of $\theta$, i.e. there is a
code $\beta:{\mathcal{A}}\to\ker S_{\theta}/{\mathcal{R}}$ such that
$\beta\theta_{m}={}^{c}\theta_{m}\beta$. By Lemma 3.19, ${}^{c}\theta$ has
column number $1$ and so $\ker S_{{}^{c}\theta}$ contains only rank 1 maps.
Hence, for $g_{1},g_{2}\in\ker S_{{}^{c}\theta}$ the condition $g_{1}\neq
g_{2}$ is equivalent to $\mbox{\rm im}g_{1}\cap\mbox{\rm im}g_{2}=\emptyset$.
Let $f_{i}\in({}^{c}\Phi)^{-1}(g_{i})\cap\ker S_{\theta}$. If $\mbox{\rm
im}f_{1}\cap\mbox{\rm im}f_{2}\neq\emptyset$ then there are
$a_{1},a_{2}\in{\mathcal{A}}$ such that $f_{1}(a_{1})=f_{2}(a_{2})$. It
follows that $g_{1}(\beta(a_{1}))=\beta f(a_{1})=\beta
f(a_{2})=g_{2}(\beta(a_{2}))$, hence $\mbox{\rm im}g_{1}\cap\mbox{\rm
im}g_{2}\neq\emptyset$, hence $g_{1}=g_{2}$. Thus $\mbox{\rm
im}f_{1}\cap\mbox{\rm im}f_{2}\neq\emptyset$ implies
${}^{c}\Phi(f_{1})={}^{c}\Phi(f_{2})$ which means that $f_{1}$ and $f_{2}$ are
${\mathcal{R}}$-related. By Lemma 3.1 they then have the same image. Thus the
elements of $U_{\theta}$ either coincide or do not intersect. As we assumed
that $U_{\mathcal{A}}$ covers ${\mathcal{A}}$ it is a partition of
${\mathcal{A}}$. ∎

######  Example 3.21.

Let

$\displaystyle\theta:a$ $\displaystyle\mapsto abcc$ $\displaystyle b$
$\displaystyle\mapsto badd$ $\displaystyle c$ $\displaystyle\mapsto cacd$
$\displaystyle d$ $\displaystyle\mapsto dbdc.$

This example has $U_{\theta}=\\{\\{a,b\\},\\{c,d\\}\\}$; thus
$U_{\theta}=\mathcal{P}_{\theta}$ and ${}^{c}\theta=\eta_{\theta}$ is inner
encoded. Setting $A=\\{a,b\\}$ and $C=\\{c,d\\}$ we obtain

$\displaystyle\eta_{\theta}:A$ $\displaystyle\mapsto AACC$ $\displaystyle C$
$\displaystyle\mapsto CACC.$

$X_{\eta_{\theta}}$ is an aperiodic almost automorphic factor of $X_{\theta}$.

######  Example 3.22.

Consider the substitution

$\displaystyle\theta:a$ $\displaystyle\mapsto acaef$ $\displaystyle b$
$\displaystyle\mapsto bdbde$ $\displaystyle c$ $\displaystyle\mapsto ceccg$
$\displaystyle d$ $\displaystyle\mapsto dfbde$ $\displaystyle e$
$\displaystyle\mapsto egaef$ $\displaystyle f$ $\displaystyle\mapsto dfbfg$
$\displaystyle g$ $\displaystyle\mapsto cecge.$

Its minimal sets are
$U_{\theta}=\\{A=\\{a,b,c\\},B=\\{c,d,e\\},C=\\{e,f,g\\}\\}$. The canonical
outer encoding is $A\mapsto ABABC,B\mapsto BCABC,C\mapsto BCACC.$ The cover
$U_{\theta}$ does not form a partition. It generates the partition
$\mathcal{P}_{\theta}=\\{\\{a,b,c,d,e,f,g\\}\\}$ which leads to the periodic
substitution

$\displaystyle\eta_{\theta}:D$ $\displaystyle\mapsto DDDDD$

######  Lemma 3.23.

Any inner encoding of an essentially surjective substitution is essentially
surjective.

###### Proof.

Let $(\eta,\beta)$ be inner encoded by $\theta$,
$\beta:{\mathcal{A}}\to{\mathcal{B}}$. Let $b\in{\mathcal{B}}$. As
$U_{\theta}$ covers ${\mathcal{A}}$ there is $a\in{\mathcal{A}}$ and $f\in\ker
S_{\theta}$ such that $\beta(f(a))=b$. Hence $\beta f\beta^{-1}(\beta(a))=b$.
Moreover, $\beta f\beta^{-1}\in\ker S_{\eta}$. Hence $b\in U_{\eta}$. ∎

######  Proposition 3.24.

Let $\theta$ be a substitution which is essentially surjective. Let
${}^{c}\theta$ be the canonical outer encoding of $\theta$. If $(\eta,\Phi)$
is outer encoded by $\theta$, and $\eta$ is essentially surjective and has
column number $1$, then $(\eta,\Phi)$ is outer encoded by ${}^{c}\theta$.

###### Proof.

Let $({}^{c}\eta,{}^{c}\Phi_{\eta})$ be the canonical outer encoding of
$\eta$. We claim that there is a morphism $\varphi:S_{{}^{c}\theta}\to
S_{{}^{c}\eta}$ such that the diagram

${S_{\theta}}$${S_{{}^{c}\theta}}$${S_{\eta}}$${S_{{}^{c}\eta}\par}$$\scriptstyle{{}^{c}\Phi}$$\scriptstyle{\Phi}$$\scriptstyle{\varphi}$$\scriptstyle{{}^{c}\Phi_{\eta}}$

is commutative. By Lemma 3.5 $\Phi(\ker S_{\theta})=\ker S_{\eta}$ and $\Phi$
preserves the ${\mathcal{R}}$-relation. Therefore, given $t,s\in S_{\theta}$
and $x\in\ker S_{\theta}$,
$[tx]_{{\mathcal{R}}_{\theta}}=[sx]_{{\mathcal{R}}_{\theta}}$ implies
$[\Phi(t)\Phi(x)]_{{\mathcal{R}}_{\eta}}=[\Phi(s)\Phi(x)]_{{\mathcal{R}}_{\eta}}$
(here ${\mathcal{R}}_{\theta}$ is the ${\mathcal{R}}$-relation on $S_{\theta}$
and ${\mathcal{R}}_{\eta}$ is the ${\mathcal{R}}$-relation on $S_{\eta}$).
Also by Lemma 3.5, any $y\in\ker S_{\eta}$ has a pre-image under $\Phi$ in
$\ker S_{\theta}$, so we see that ${}^{c}\Phi(t)={}^{c}\Phi(s)$, which is
$[tx]_{{\mathcal{R}}_{\theta}}=[sx]_{{\mathcal{R}}_{\theta}}$ for all
$x\in\ker S_{\theta}$, implies
${}^{c}\Phi_{\eta}(\Phi(t))={}^{c}\Phi_{\eta}(\Phi(s))$, which is
$[\Phi(t)y]_{{\mathcal{R}}_{\eta}}=[\Phi(s)y]_{{\mathcal{R}}_{\eta}}$ for all
$y\in S_{\eta}$. Thus $\varphi$ is well defined through the formula
$\varphi({}^{c}\Phi(t))={}^{c}\Phi_{\eta}(\Phi(t))$.

As $\eta$ has column number $1$ and is essentially surjective, $\ker S_{\eta}$
can be identified with the alphabet of $\eta$ and therefore
${}^{c}\Phi_{\eta}:S_{\eta}\to{\mathcal{F}}(\ker S_{\eta})$ is injective.
Hence $\Phi(t)=(^{c}\Phi_{\eta})^{-1}(\varphi({}^{c}\Phi(t)))$ showing that it
factors through ${}^{c}\Phi$. ∎

######  Definition 3.25.

Let $\theta$ be an essentially surjective substitution. Its maximal inner
encoding with column number $1$ $\eta$ is an inner encoded substitution of
$\theta$, such that any other inner encoding of $\theta$ which has column
number $1$ factors, via an inner encoding, through $\eta$.

We now show that maximal inner encodings with column number $1$ exist.

######  Theorem 3.26.

Let $\theta$ be an essentially surjective substitution. Its maximal inner
encoding with column number $1$ is the inner encoding $\eta_{\theta}$
associated to $\theta$. In particular, $\theta$ admits an aperiodic inner
encoding with column number $1$ if and only if the inner coding associated to
$\theta$ is aperiodic.

###### Proof.

By Lemma 3.11 $\eta_{\theta}$ is an inner encoding with column number $1$.
Suppose that $\eta$ is an inner encoding of $\theta$ with column number $1$.
We saw in Proposition 3.24 that it must be an outer encoding of the canonical
outer encoding ${}^{c}\theta$. Furthermore the epimorphism
$\Phi:S_{{}^{c}\theta}\to S_{\eta}$ restricts to an epimorphism from $\ker
S_{{}^{c}\theta}$ to $\ker S_{\eta}$. Since both have column number $1$, this
restriction of $\Phi$ is an epimorphism between left zero semigroups, hence a
surjective map from the alphabet of ${}^{c}\theta$, which is $U_{\theta}$, to
the alphabet of $\eta$. On the other hand, the code from ${\mathcal{A}}$ to
the alphabet of $\eta$ is given by a partition ${\mathcal{P}}$. Any member of
$U_{\theta}$ must be a subset of an element of ${\mathcal{P}}$. Thus any
element of ${\mathcal{P}}_{\theta}$ is a subset of an element of
${\mathcal{P}}$, and $\eta$ is a inner encoding of the inner encoding
$\eta_{\theta}$ defined by ${\mathcal{P}}_{\theta}$. ∎

###  3.4. Trivial height

Recall that a substitution has a coincidence if and only if its height
coincides with its naïve column number. In this subsection we consider the
case in which $\theta$ has height $1$. This allows us to exploit the above
results about inner encoded substitutions with column number $1$ for the
analysis of factors which are almost automorphic.

######  Theorem 3.27.

Let $\theta$ be a primitive substitution of trivial height. Then $X_{\theta}$
has an aperiodic almost automorphic shift factor over its maxmal
equicontinuous factor if and only if one of the inner encodings associated to
$\theta^{(n)}$, $n=(-l,r)$, $0\leq l,r\leq 1$, is aperiodic.

Note that Theorem 3.27 and Lemma 2.5 imply that if $X_{\theta}$ has an
aperiodic almost automorphic factor, then its maximal equicontinuous factor
map factors through this almost automorphic factor.

We remark that it is sufficient to check whether the inner encoding associated
$\theta^{(-1,1)}$ is aperiodic, as all other $\theta^{(n)}$ are inner
encodings of $\theta^{(-1,1)}$. However if one suspects that $X_{\theta}$ has
an almost automorphic factor, in practice it is easier to check whether
$X_{\theta}$ or $X_{\theta^{(0,1)}}$ give almost automorphic factors,
especially if doing these computations by hand.

###### Proof.

By Cor. 2.9 any factor $X_{\theta}\to Y$ is conjugate to an inner encoding of
${\theta^{(n)}}^{p}$ for some $|n|\leq 1$ and $p\geq 1$. By Theorem 3.26 the
maximal inner encoding of $(\theta^{(n)})^{p}$ with column number $1$ is the
inner encoding defined by ${\mathcal{P}}_{(\theta^{(n)})^{p}}$. By Lemma 3.13
the inner encoding of $(\theta^{(n)})^{p}$ defined by
${\mathcal{P}}_{(\theta^{(n)})^{p}}$ is the $p$-th power of the inner encoding
of $\theta^{(n)}$ defined by ${\mathcal{P}}_{\theta^{(n)}}$. We can therefore
conclude that $X_{\theta}$ has an aperiodic almost automorphic shift factor
over its maximal equicontinuous factor if and only if one of the inner
encodings defined by $\mathcal{P}_{\theta^{(n)}}$, $n=(-l,r)$, $l,r\leq 1$,
has maximal equicontionuous factor $(\mathbb{Z}_{\ell},(+1))$. Indeed, as the
inner encoding has column number $1$ its shift is almost automorphic, but if
it is periodic, its maximal equicontinuous factor is finite, whereas if it is
aperiodic its maximal equicontinuous factor must be
$(\mathbb{Z}_{\ell},(+1))$, which coincides with the maximal equicontinuous
factor of $\theta^{(n)}$, as $\theta^{(n)}$ has trivial height. ∎

######  Example 3.28.

We return to Example 3.22 which has height $1$. We saw that $\theta$ has no
nontrivial inner encoding with a coincidence. By the comment after Theorem
3.27, it is enough to check whether $X_{\theta^{(-1,1)}}$ has an almost
automorphic factor. We find

$\displaystyle\theta^{(-1,1)}\colon 0$ $\displaystyle\mapsto W7I68$
$\displaystyle 1$ $\displaystyle\mapsto YSf1Q$ $\displaystyle 2$
$\displaystyle\mapsto LFU3C$ $\displaystyle 3$ $\displaystyle\mapsto LFU3E$
$\displaystyle 4$ $\displaystyle\mapsto LFV4b$ $\displaystyle 5$
$\displaystyle\mapsto e051R$ $\displaystyle 6$ $\displaystyle\mapsto h7I69$
$\displaystyle 7$ $\displaystyle\mapsto oSf1P$ $\displaystyle 8$
$\displaystyle\mapsto h7KAj$ $\displaystyle 9$ $\displaystyle\mapsto h7KAl$
$\displaystyle A$ $\displaystyle\mapsto h7KAn$ $\displaystyle B$
$\displaystyle\mapsto H2B3D$ $\displaystyle C$ $\displaystyle\mapsto MSf1O$
$\displaystyle D$ $\displaystyle\mapsto MSf1Q$ $\displaystyle E$
$\displaystyle\mapsto MSf1R$ $\displaystyle F$ $\displaystyle\mapsto LFV4a$
$\displaystyle G$ $\displaystyle\mapsto T051P$ $\displaystyle H$
$\displaystyle\mapsto U2B3D$ $\displaystyle I$ $\displaystyle\mapsto W7I69$
$\displaystyle J$ $\displaystyle\mapsto W7I6A$ $\displaystyle K$
$\displaystyle\mapsto W7I69$ $\displaystyle L$ $\displaystyle\mapsto XFU3D$
$\displaystyle M$ $\displaystyle\mapsto YSf1P$ $\displaystyle N$
$\displaystyle\mapsto XFV4Z$ $\displaystyle O$ $\displaystyle\mapsto XFV4a$
$\displaystyle P$ $\displaystyle\mapsto XFV4b$ $\displaystyle Q$
$\displaystyle\mapsto XFV4c$ $\displaystyle R$ $\displaystyle\mapsto XFV4d$
$\displaystyle S$ $\displaystyle\mapsto W7KAj$ $\displaystyle T$
$\displaystyle\mapsto e051P$ $\displaystyle U$ $\displaystyle\mapsto g2B3D$
$\displaystyle V$ $\displaystyle\mapsto g2B3D$ $\displaystyle W$
$\displaystyle\mapsto h7I6A$ $\displaystyle X$ $\displaystyle\mapsto iFU3D$
$\displaystyle Y$ $\displaystyle\mapsto oSf1P$ $\displaystyle Z$
$\displaystyle\mapsto h7KAj$ $\displaystyle a$ $\displaystyle\mapsto h7KAk$
$\displaystyle b$ $\displaystyle\mapsto h7KAl$ $\displaystyle c$
$\displaystyle\mapsto h7KAm$ $\displaystyle d$ $\displaystyle\mapsto h7KAn$
$\displaystyle e$ $\displaystyle\mapsto G051P$ $\displaystyle f$
$\displaystyle\mapsto G051R$ $\displaystyle g$ $\displaystyle\mapsto H2B3D$
$\displaystyle h$ $\displaystyle\mapsto J7I6A$ $\displaystyle i$
$\displaystyle\mapsto LFU3D$ $\displaystyle j$ $\displaystyle\mapsto MSf1N$
$\displaystyle k$ $\displaystyle\mapsto MSf1O$ $\displaystyle l$
$\displaystyle\mapsto MSf1P$ $\displaystyle m$ $\displaystyle\mapsto MSf1Q$
$\displaystyle n$ $\displaystyle\mapsto MSf1R$ $\displaystyle o$
$\displaystyle\mapsto MSf1P.$

Furthermore, $\mathcal{P}_{\theta^{(-1,1)}}=\\{\alpha,\beta,\gamma\\}$ where

$\displaystyle\alpha=\\{1,3,4,6,8,9,A,C,D,E,N,O,P,Q,R,Z,a,b,c,d,j,k,l,m,n\\},$
$\displaystyle\beta=\\{5,B,G,H,I,J,K,L,M,T,U,V,W,X,Y,e,f,g,h,i,o\\},\mbox{ and
}$ $\displaystyle\gamma=\\{0,2,7,F,S\\}.$

The maximal inner encoding with a coincidence is the substitution

$\displaystyle\eta_{\theta^{(-1,1)}}:\alpha$
$\displaystyle\mapsto\beta\gamma\beta\alpha\alpha$ $\displaystyle\beta$
$\displaystyle\mapsto\beta\gamma\beta\alpha\alpha$ $\displaystyle\gamma$
$\displaystyle\mapsto\beta\gamma\beta\alpha\alpha$

which is periodic. We conclude that $X_{\theta}$ does not have an almost
automorphic factor.

###  3.5. Non-trivial height

Suppose that our substitution $\theta$ has non-trivial height. While we can
still apply Theorem 3.26 to find the maximal encoded substitution with column
number $1$, and this one will give an almost automorphic factor of
$X_{\theta}$, the resulting substitution $\eta_{\theta}$ must have height $1$
and thus its MEF is strictly smaller than that of $\theta$, as Example 3.29
shows. This is not what we are after.

######  Example 3.29.

To highlight the difference between working with or without the pure base,
consider

$\displaystyle\theta:a$ $\displaystyle\mapsto aba$ $\displaystyle b$
$\displaystyle\mapsto bac$ $\displaystyle c$ $\displaystyle\mapsto cab$

which has height $2$. Its semigroup is

$S_{\theta}=\\{{\mathbf{1}},\tau_{bc}\\}\sqcup\\{p_{b},p_{c},\bar{p}_{b},\bar{p}_{c}\\}$

where $\tau_{bc}$ exchanges $b$ with $c$ and leaves $a$ fixed, $p_{b}$ is the
idempotent of rank $2$ mapping $c$ to $b$, $p_{c}$ is the idempotent of rank
$2$ mapping $b$ to $c$, $\bar{p}_{b}$ is $p_{b}$ followed by an exchange of
$a$ and $b$ and $\bar{p}_{c}$ is $p_{c}$ followed by an exchange of $a$ and
$c$. The kernel $\ker S_{\theta}$ is thus given by rank $2$ maps $\ker
S_{\theta}=LZ_{2}\times\mathbb{Z}/2\mathbb{Z}$, where $LZ_{2}$ is the left
zero semigroup on two letters. We see that $\theta$’s height equals its naïve
column number and hence the substitution shift is a somewhere injective
extension of its maximal equicontinuous factor. So in principle we don’t need
to look at an almost automorphic factor, as the substitution shift already is
almost automorphic. But it is instructive to apply the construction of the
canonical outer encoding, as the result is a primitive almost automorphic
substitution with trivial height. Indeed, if we denote ${}^{c}b=[p_{b}]$, the
${\mathcal{R}}$-class of $p_{b}$ and ${}^{c}c=[p_{c}]$ that of $p_{c}$ we find
that the canonical outer encoded substitution is given by

$\displaystyle{}^{c}\theta:{}^{c}b$
$\displaystyle\mapsto{}^{c}b{}^{c}b{}^{c}c$ $\displaystyle{}^{c}c$
$\displaystyle\mapsto{}^{c}c{}^{c}b{}^{c}b$

Furthermore, the cover $U_{\theta}$ is given by $\\{\mbox{\rm
im}p_{b},\mbox{\rm im}p_{c}\\}=\\{\\{a,b\\},\\{a,c\\}\\}$ which is not a
partition, hence the canonical outer encoded substitution is not inner
encoded. The coincidence partition is trivial
${\mathcal{P}}_{\theta}={\mathcal{A}}$.

Thus instead we will work with the pure base of $\theta$.

We recall from [5] the following results: If $\theta$ is primitive and has
height $h$, then there exists a $\sigma^{h}$-periodic clopen partition of
$X_{\theta}$,
$X_{\theta}=\bigsqcup_{k\in\mathbb{Z}/h\mathbb{Z}}X_{\theta}^{k}$, and
$\sigma(X_{\theta}^{k})=X_{\theta}^{k+1}$. Moreover, $X_{\theta}^{0}$ is
invariant under $\theta$ and there exists a subset
${\mathcal{A}}^{\prime}\subset{\mathcal{A}}^{h}$ such that $X_{\theta}^{0}$
consists precisely of the sequences $x\in X_{\theta}$ for which $x_{0}\dots
x_{h-1}\in{\mathcal{A}}^{\prime}$. Define a substitution $\theta^{\prime}$ on
${\mathcal{A}}^{\prime}$ as follows: Given $a_{0}\dots
a_{h-1}\in{\mathcal{A}}^{\prime}$ compute $\theta(a_{0}\dots
a_{h-1})=a^{\prime}_{0}\dots a^{\prime}_{h\ell-1}$ and set

$\theta^{\prime}_{k}(a_{0}\dots a_{h-1})=a^{\prime}_{kh}\dots
a^{\prime}_{(k+1)h-1}.$

$\theta^{\prime}$ is called the pure base of $\theta$. It corresponds to the
restriction of $\theta$ to $X_{\theta}^{0}$ but expressed in the alphabet
${\mathcal{A}}^{\prime}$.

The suspension of a $\mathbb{Z}$-action $(X,\varphi)$ with
$\mathbb{Z}/h\mathbb{Z}$ is the space $X\times\mathbb{Z}/h\mathbb{Z}$ equipped
with the $\mathbb{Z}$-action

(3.3) $T_{\varphi}(x,i):=\begin{cases}(x,i+1)&\text{ if }0\leq i<h-1\\\
(\varphi(x),0)&\text{ if }i=h-1\end{cases}$

The shift $(X_{\theta},\sigma)$ is, for a substitution of height $h$,
topologically conjugate to a suspension of the substitution shift
$(X_{\theta^{\prime}},\sigma)$ with the finite group $\mathbb{Z}/h\mathbb{Z}$.
Here we have denoted the shift action on $X_{\theta^{\prime}}$ by
$\sigma^{\prime}$ in order to distinguish it from the shift action $\sigma$ on
$X_{\theta}$. The conjugacy is given by

$X_{\theta^{\prime}}\times\mathbb{Z}/h\mathbb{Z}\ni(x^{\prime},i)\mapsto\sigma^{i}(x)\in
X_{\theta},$

where on the left hand side $x^{\prime}$ is a sequence of letters from
${\mathcal{A}}^{\prime}$, that is, a sequence of allowed (for $\theta$) words
of length $h$ whereas on the right hand side $x$ is the sequence of letters
from ${\mathcal{A}}$ that one obtains when one interprets $x^{\prime}$ as a
sequence of letters in ${\mathcal{A}}$. Note that
$(x^{\prime},i)\mapsto(\sigma^{\prime}(x^{\prime}),i)$ on the left corresponds
to $\sigma^{i}(x)\mapsto\sigma^{h+i}(x)$ on the right. The suspension
construction is functorial and immediately implies:

  * •

If $F:(X_{\theta^{\prime}},\sigma^{\prime})\to(Y,\varphi)$ is a factor map
then
$F\times{\mathbf{1}}:(X_{\theta^{\prime}}\times\mathbb{Z}/h\mathbb{Z},T_{\sigma^{\prime}})\to(Y\times\mathbb{Z}/h\mathbb{Z},T_{\varphi})$
is a factor map and any factor map of
$(X_{\theta^{\prime}}\times\mathbb{Z}/h\mathbb{Z},T_{\sigma^{\prime}})$, up to
a rotation, arises in this way. In particular the MEF of $(X_{\theta},\sigma)$
is conjugate to $(\mathbb{Z}_{\ell}\times\mathbb{Z}/h\mathbb{Z},T_{+1})$.

  * •

$(Y,\varphi)$ is almost automorphic if and only if
$(Y\times\mathbb{Z}/h\mathbb{Z},T_{\varphi})$ is almost automorphic.

Recall that a topological dynamical system $(X,T)$ is a minimal almost
automorphic extension of an odometer if and only if it is topologically
conjugate to a shift [6, Theorem 6.4]. Combining this with the remarks above,
we obtain the following.

######  Proposition 3.30.

Let $\theta$ be a length-$\ell$, primitive aperiodic substitution, with pure
base $\theta^{\prime}$. Then $(X_{\theta},\sigma)$ has an aperiodic almost
automorphic shift factor above its maximal equicontinuous factor if and only
if $(X_{\theta^{\prime}},\sigma^{\prime})$ has an aperiodic almost automorphic
shift factor above its maximal equicontinuous factor.

We describe how to construct the desired almost automorphic factor of
$X_{\theta}$ when $X_{\theta^{\prime}}$ has an aperiodic almost automorphic
shift factor $X_{\eta^{\prime}}$ via the map
$F^{\prime}:X_{{\theta^{\prime}}}\rightarrow X_{\eta^{\prime}}$.
$\eta^{\prime}$ necessarily has height $1$. Define a new length-$\ell$
substitution $\eta$ with alphabet
$\mathcal{A}_{\eta}=\\{a_{j}\>:\>a\in\mathcal{A}_{\eta^{\prime}},1\leq j\leq
h\\}$ as follows. Define
$\mathfrak{i}:\mathcal{A}_{\eta^{\prime}}\rightarrow\mathcal{A}_{\eta}^{h}$ by
$\mathfrak{i}(a)=a_{1}\dots a_{h}$. Now let $\eta$ be the unique length-$\ell$
substitution which satisfies
$\eta\circ\mathfrak{i}=\mathfrak{i}\circ\eta^{\prime}$. That is, we “split”
each $a\in\mathcal{A}_{\eta^{\prime}}$ into $h$ different letters
$a_{1},\dotsc,a_{h}$ in such a way that the concatenation of the length $\ell$
words $\eta(a_{1})\cdots\eta(a_{h})$ is the word obtained from
${\eta^{\prime}}(a)$ by splitting every letter. As defined, $\eta$ has height
$h$ and pure base ${\eta^{\prime}}$. Thus, $X_{\eta}$ is also a suspension of
$X_{\eta^{\prime}}$ over $\mathbb{Z}/h\mathbb{Z}$. It can be seen that
$X_{\eta}$ is almost automorphic over $(\mathbb{Z}_{\bar{\ell},h},+1)$. See
Example 3.33 for such a construction.

######  Corollary 3.31.

Let $\theta$ be a length-$\ell$, primitive aperiodic substitution, with pure
base $\tilde{\theta}$. Then $X_{\theta}$ has an aperiodic almost automorphic
shift factor if and only if the inner encoding defined by
$\mathcal{P}_{\tilde{\theta}^{(-1,1)}}$ is aperiodic.

###  3.6. Two-letter substitutions of bijective substitutions and their
canonical outer encodings

In this section we apply our results above to study when a bijective
substitution shift has an almost automorphic factor. In the process we revisit
the work in [11, Section 4]. We start with bijective substitutions of trivial
height. Remember that for bijective substitutions, $S_{\theta}$ is a group and
so ${}^{c}\theta$ is trivial, being defined on a one letter alphabet. This
does not mean that a bijective substitution shift does not admit an almost
automorphic substitutional factor, but only that these may only be seen when
working with the collared versions of the substitution. We will work with
$\theta^{(0,1)}$ and, in case that $X_{\theta^{(0,1)}}$ does not have an
almost automorphic factor, verify whether or not $\theta^{(-1,1)}$ does.

For $\theta$ a bijective substitution on ${\mathcal{A}}$ let
${\mathcal{A}}^{(2)}$ be the set of allowed two-letter words for $\theta$.
Recall that the 2-collared substitution $\theta^{(0,1)}$ associated to
$\theta$ is the substitution on ${\mathcal{A}}^{(2)}$ of the same length given
by

$\theta^{(0,1)}_{m}(a,b)=(\theta_{m}(a),\theta_{m+1}(a)),\quad 0\leq
m<\ell-1,\quad\theta^{(0,1)}_{\ell-1}(a,b)=(\theta_{\ell-1}(a),\theta_{0}(b))$

We assume that all $\theta$-periodic points are fixed, so that
$\theta_{0}=\theta_{\ell-1}={\mathbf{1}}$; thus all maps $\theta^{(0,1)}_{m}$
with $m<\ell-1$ have rank $c=|{\mathcal{A}}|$ while $\theta^{(0,1)}_{\ell-1}$
is equal to the identity on ${\mathcal{A}}^{(2)}$ and hence has rank equal to
$|{\mathcal{A}}^{(2)}|$. We know that the naïve column number of a
substitution is a conjugacy invariant and so the naïve column number of
$\theta^{(0,1)}$ must also be $c$. Hence we see that the kernel of
$S_{\theta^{(0,1)}}$ is generated by
$\theta_{m}\mathrm{pr_{1}}\times\theta_{m+1}\mathrm{pr_{1}}$, $m<\ell-1$,
where $\mathrm{pr_{1}}:{\mathcal{A}}^{(2)}\to{\mathcal{A}}$ is the projection
onto the first factor. Recall that the right ideals of $\ker
S_{\theta^{(0,1)}}$ are in one-to-one correspondence to the images of these
maps. As $\theta_{m}$ is bijective, the image of
$\theta_{m}\mathrm{pr_{1}}\times\theta_{m+1}\mathrm{pr_{1}}$ coincides with
that of $\mathrm{pr_{1}}\times\theta_{m+1}\theta_{m}^{-1}\mathrm{pr_{1}}$ and
so uniquely is determined by the map $\theta_{m+1}\theta_{m}^{-1}$. We thus
see that the set of right ideals is in one-to-one correspondence the set

$I_{\theta}:=\\{\theta_{m+1}\theta_{m}^{-1}|m=0,\cdots,\ell-2\\}$

which plays a prominent role in the description of the Ellis semigroup of the
substitution shift $(X_{\theta},\sigma)$ and is also called the $R$-set of the
substitution [11]. We have shown the first part of

######  Corollary 3.32.

The alphabet of the canonical outer encoding ${}^{c}\theta^{(0,1)}$ of
$\theta^{(0,1)}$ can be identified with $I_{\theta}$. Under this
identification it is given by

${{}^{c}\theta^{(0,1)}}_{m}(\theta_{i}\theta_{i-1}^{-1})=\theta_{m+1}\theta_{m}^{-1},\quad
0\leq
m<\ell-1,\quad{{}^{c}\theta^{(0,1)}}_{\ell-1}(\theta_{i}\theta_{i-1}^{-1})=\theta_{i}\theta_{i-1}^{-1}$

It is an inner encoding of $\theta^{(0,1)}$ if and only if for all $f,g\in
I_{\theta}$ and $\forall a\in{\mathcal{A}}$: $f(a)\neq g(a)$. Thus the
following is a necessary condition for ${}^{c}\theta^{(0,1)}$ to be an inner
encoding:

(3.4) $|I_{\theta}|\times|{\mathcal{A}}|=|{\mathcal{A}}^{(2)}|$

and so the code of the inner encoding is a $|{\mathcal{A}}|$-to-1 map.

###### Proof.

Recall that the canonical outer encoding is an inner encoding if the images of
the maps $\theta_{m}\mathrm{pr_{1}}\times\theta_{m+1}\mathrm{pr_{1}}$,
$m<\ell-1$, either coincide or do not overlap. As the images of
$\theta_{m}\mathrm{pr_{1}}\times\theta_{m+1}\mathrm{pr_{1}}$ and
$\theta_{m^{\prime}}\mathrm{pr_{1}}\times\theta_{m^{\prime}+1}\mathrm{pr_{1}}$
coincide if and only if
$\theta_{m}\theta_{m-1}^{-1}=\theta_{m^{\prime}}\theta_{m^{\prime}-1}^{-1}$
this is exactly the condition stated. If this is the case, then the number of
letters of $\theta^{(0,1)}$ is equal to the maximal choice of distinct maps
$\theta_{m}\mathrm{pr_{1}}\times\theta_{m+1}\mathrm{pr_{1}}$, $1\leq m<\ell-1$
(the size of $I_{\theta}$) times the size of the image of one of them, which
is $|{\mathcal{A}}|$. ∎

We go through the examples in [11].

The canonical outer encoding of any $2$-letter bijective substitution is an
inner encoded substitution, because for those
$I_{\theta}=\\{{\mathbf{1}},\mathfrak{f}\\}$, where $\mathfrak{f}$
interchanges $a$ with $b$. The simplest example is the Thue-Morse substitution

$\displaystyle\theta:a$ $\displaystyle\mapsto abba$ $\displaystyle b$
$\displaystyle\mapsto baab$

whose semigroup is $S_{\theta}=\mathbb{Z}/2\mathbb{Z}$. The alphabet of
$\theta^{(0,1)}$ is

${\mathcal{A}}^{(2)}=\\{o=ab,\bar{o}=ba,e=aa,\bar{e}=bb\\}$

and

$S_{\theta^{(0,1)}}=\\{{\mathbf{1}},\omega\\}\sqcup\\{\Pi_{0},\bar{\Pi}_{0},\Pi_{e},\bar{\Pi}_{e}\\}$

where $\omega$ is the order $2$ symmetry exchanging $o$ with $\bar{e}$ and $e$
with $\bar{o}$, $\Pi_{o}$ the rank $2$ idempotent mapping $e$ to $o$ and
$\bar{e}$ to $\bar{o}$, $\Pi_{e}$ the rank $2$ idempotent mapping $o$ to $e$
and $\bar{o}$ to $\bar{e}$, and $\bar{\Pi}_{\bullet}$ is $\Pi_{\bullet}$
followed by barring the letter. The kernel contains the four maps of rank $2$
and is isomorphic to $\ker S_{\theta^{(0,1)}}\cong
LZ_{2}\times\mathbb{Z}/2\mathbb{Z}$, the left zero semigroup of two elements
times the group $\mathbb{Z}/2\mathbb{Z}$. We denote by $[o]$ the
${\mathcal{R}}$-class of $\Pi_{0}$ and by $[e]$ the ${\mathcal{R}}$-class of
$\Pi_{e}$. It is now easily seen that ${}^{c}\phi({\mathbf{1}})={\mathbf{1}}$,
${}^{c}\phi(\omega)=\mathfrak{f}$, ${}^{c}\phi(\Pi_{o})$ the projection onto
$[o]$, ${}^{c}\phi(\Pi_{e})$ the projection onto $[e]$, and
${}^{c}\phi(\bar{\Pi}_{\bullet})=\mathfrak{f}\,{}^{c}\phi(\Pi_{\bullet})$.
With this we find that the column maps of ${}^{c}\theta^{(0,1)}$ are given by

$\displaystyle{}^{c}\theta^{(0,1)}:o$ $\displaystyle\mapsto oeoo$
$\displaystyle e$ $\displaystyle\mapsto oeoe$

This result is well known, ${}^{c}\theta^{(0,1)}$ is the period doubling
substitution.

Our next example has three letters,

$\displaystyle\theta:a$ $\displaystyle\mapsto abcca$ $\displaystyle b$
$\displaystyle\mapsto babab$ $\displaystyle c$ $\displaystyle\mapsto ccabc$

It does not satisfy (3.4), as ${\mathcal{A}}^{(2)}$ has five letters and five
is a prime number. A further investigation of $\theta^{(-1,1)}$ shows, that
also its canonical outer encoding has a trivial coincidence partition. Thus
the substitution shift does not have an aperiodic almost automorphic factor.

In our second example222This example has generalised height equal to 2 but
trivial classical height.

$\displaystyle\theta:a$ $\displaystyle\mapsto abacaaa$ $\displaystyle b$
$\displaystyle\mapsto babbbcb$ $\displaystyle c$ $\displaystyle\mapsto
cccacbc$

we have $I_{\theta}=\\{\theta_{1},\theta_{3},\theta_{5}\\}$ with
$\theta_{1}=\begin{pmatrix}b\\\ a\\\ c\end{pmatrix}$,
$\theta_{3}=\begin{pmatrix}c\\\ b\\\ a\end{pmatrix}$, and
$\theta_{5}=\begin{pmatrix}a\\\ c\\\ b\end{pmatrix}$. We see that the
partition of ${\mathcal{A}}^{(2)}={\mathcal{A}}^{2}$ is given by
$A=\\{ab,bc,cc\\}$, $B=\\{ac,bb,ca\\}$, $C=\\{aa,bc,cb\\}$ leading to the
inner encoded substitution

$\displaystyle\eta:A$ $\displaystyle\mapsto AABBCCA$ $\displaystyle B$
$\displaystyle\mapsto AABBCCB$ $\displaystyle C$ $\displaystyle\mapsto
AABBCCC.$

which is hence an almost automorphic substitutional shift factor of
$X_{\theta}$.

In our third example $\theta$ is the substitution

$\displaystyle\theta:a$ $\displaystyle\mapsto abc$ $\displaystyle b$
$\displaystyle\mapsto bca$ $\displaystyle c$ $\displaystyle\mapsto cab$

has $\theta^{3}$-fixed points, so we consider the third power $\theta^{3}$. We
have $I_{\theta}=\\{{\mathbf{1}},\omega,\omega^{2}\\}$ leading to the
partition of ${\mathcal{A}}^{(2)}=\\{ab,bc,ca,ac,ba,cb\\}$ given by
$A=\\{ab,bc,ca\\}$, $B=\\{ac,ba,cb\\}$. This yields the substitution $\eta$

$\displaystyle\eta:A$ $\displaystyle\mapsto AABAABAAA$ $\displaystyle B$
$\displaystyle\mapsto AABAABAAB,$

so that $X_{\eta}$ is an almost automorphic factor of $X_{\theta}.$

As our last example from [11] has nontrivial height, we go through the
required details carefully.

######  Example 3.33.

This substitution has four letters and $G_{\theta}$ equals the dihedral group
$D_{4}$:

$\displaystyle\theta:a$ $\displaystyle\mapsto abadcba$ $\displaystyle b$
$\displaystyle\mapsto badcbab$ $\displaystyle c$ $\displaystyle\mapsto
cdcbadc$ $\displaystyle d$ $\displaystyle\mapsto dcbadcd$

and it has height 2. We have $I_{\theta}=\\{\theta_{1},\rho\\}$ where
$\rho=\theta_{2}\theta_{1}^{-1}$ (This corrects the mistake in [11] which
stated that $\rho=\theta_{1}\theta_{2}$). The alphabet of the canonical outer
encoding ${}^{c}\theta^{(0,1)}$ thus has $2$ letters. But
${\mathcal{A}}^{(2)}$ contains only $6$ letters. Therefore (3.4) tells us that
${}^{c}\theta^{(0,1)}$ cannot be an inner encoded substitution.

To find out whether the shift generated by this substitution has an almost
automorphic factor, then, as it has height 2, we move to its pure base by
Lemma 3.30. This is given by:

$\displaystyle\tilde{\theta}\colon 0$ $\displaystyle\mapsto 3010102$
$\displaystyle 1$ $\displaystyle\mapsto 2101013$ $\displaystyle 2$
$\displaystyle\mapsto 2102102$ $\displaystyle 3$ $\displaystyle\mapsto
3013013$

where each of the four symbols in the new substitution represents a two-
letter-word from the original (respectively, $0,1,2,3$ correspond to
$[ad],[cb],[cd],[ab]$). By inspection, we see that the minimal sets of this
new substitution are disjoint, and thus its coincidence partition is given by
$\mathcal{P}_{\tilde{\theta}}=\\{\\{0,1\\},\\{2,3\\}\\}$, which means that the
map $\tilde{F}\colon X_{\tilde{\theta}}\to X_{\tilde{\eta}}$, whose local rule
is a code and sends $0,1$ to $A$ and $2,3$ to $B$, is a factor map to the
aperiodic, primitive, almost automorphic substitution shift given by:

$\displaystyle\tilde{\eta}\colon A$ $\displaystyle\mapsto BAAAAAB$
$\displaystyle B$ $\displaystyle\mapsto BAABAAB$

As in the construction description after Proposition 3.30, because the
original substitution $\theta$ has height $2$, to find an almost automorphic
factor of $X_{\theta}$ we introduce a height-2 suspension $\eta$ of
$\tilde{\eta}$ by “splitting” each symbol into two, moving from e.g. $A\mapsto
BAAAAAB$ to $Aa\mapsto BbAaAaAaAaAaBb$, which is a concatenation of two length
$7$ words. The new substitution, almost automorphic by construction, is given
by:

$\displaystyle\eta\colon A$ $\displaystyle\mapsto BbAaAaA$ $\displaystyle B$
$\displaystyle\mapsto BbAaAaB$ $\displaystyle a$ $\displaystyle\mapsto
aAaAaBb$ $\displaystyle b$ $\displaystyle\mapsto bAaAaBb.$

The previously defined map $\tilde{F}$ induces a factor map $F\colon
X_{\theta}\to X_{\eta}$. To define it explicitly, we use the fact that each
element of $\\{0,1,2,3\\}$ corresponds to a two-letter word in $X_{\theta}$
and is mapped to either $A$ or $B$, which also corresponds to the two-letter
words $Aa$ or $Bb$ in $X_{\eta}$, so we expect $F$ to map any instance of,
say, $ad$ in some $x\in X_{\theta}$ to the word $Aa$ in the corresponding
$F(x)\in X_{\eta}$. We can accomplish this by giving $F$ left- and right-
radius $1$; accordingly, its local rule will be:

$\displaystyle aba$ $\displaystyle\mapsto b$ $\displaystyle adc$
$\displaystyle\mapsto a$ $\displaystyle bab$ $\displaystyle\mapsto B$
$\displaystyle bad$ $\displaystyle\mapsto A$ $\displaystyle cba$
$\displaystyle\mapsto a$ $\displaystyle cdc$ $\displaystyle\mapsto b$
$\displaystyle dcb$ $\displaystyle\mapsto A$ $\displaystyle dcd$
$\displaystyle\mapsto B.$

##  4\.  Factoring onto a bijective substitution

In this section, we characterise, using the semigroup $S_{\theta}$, when a
substitution shift has a bijective substitution shift as a factor. First we
restrict to the case where the factor map preserves the fixed point fibre. As
some of our results require trivial height, while others don’t, we continue to
specify what is needed at each step.

######  Theorem 4.1.

Let $\theta$ be a constant length substitution with naïve column number $c$.
The following are equivalent:

  1. (1)

$S_{\theta}$ has a unique minimal left ideal.

  2. (2)

There is a bijective substitution $\eta$ on a $c$-letter alphabet which is an
inner encoding of $\theta$.

The above result is obvious in the case that the column number $c$ of $\theta$
equals $1$, because then $\eta$ is the unique length-$\ell$ substitution on a
one-letter alphabet, and $S_{\theta}$ always has a unique minimal left ideal.

######  Definition 4.2.

Let $(X,\sigma)$ and $(Y,\sigma)$ be two shifts with a common rotation factor
$(\mathcal{G},R)$. Let $\pi_{X}:X\rightarrow\mathcal{G}$ and
$\pi_{Y}:Y\rightarrow\mathcal{G}$ be respective equicontinuous factor maps. We
say that the factor map $F:X\rightarrow Y$ is almost injective for
$(\mathcal{G},R)$, if there is $g\in\mathcal{G}$ such that the restriction of
$F$ to the fibre ${\pi_{X}}^{-1}(g)$ is injective. If we don’t specify the
equicontinuous factor then we take it to be the maximal common one.

The following result shows that the bijective substitution $\eta$ of the last
theorem has to be aperiodic and that the factor map between
$(X_{\theta},\sigma)$ and $(X_{\eta},\sigma)$ has to be almost injective if
$\theta$ has naïve column number $c>1$. While we do not need any assumptions
on height in Theorem 4.1, we do assume that $\theta$ has trivial height for
Theorems 4.3 and 4.21. This is because in general the existence of a bijective
factor for a substitution is not linked to the existence of a bijective factor
for its pure base; see Example 4.24. The issue here is that we characterise
the existence of a bijective factor in terms of the semigroup
$\mathcal{S}_{\theta}$, and the relationship between this semigroup and that
of the pure base of $\theta$ is not clear.

######  Theorem 4.3.

Let $\theta$ be a primitive, aperiodic length-$\ell$ substitution over the
alphabet ${\mathcal{A}}$, of trivial height. Suppose that $\theta$ has naïve
column number $c>1$, and that $(\eta,\beta)$ is inner encoded by $\theta$,
with $\eta$ bijective. Then $\eta$ is primitive and aperiodic, and the factor
map induced by $\beta:X_{\theta}\to X_{\eta}$ is almost injective.

###  4.1. More preliminaries from semigroup theory

In order to prove the above theorems we need we analyse further sub-semigroups
of the semigroup ${\mathcal{F}}(X)$ of maps from $X\to X$. Recall that the
partition defined by a map $f:X\to Y$ is ${\mathcal{P}}_{f}=\\{f^{-1}(y)|y\in
Y\\}$.

######  Definition 4.4.

We say that a map $g:X\to X$ preserves a partition
${\mathcal{P}}\subset{\mathcal{P}}(X)$ if
$g^{-1}({\mathcal{P}})\subset{\mathcal{P}}$.

Stated differently, let ${\mathcal{P}}=\\{A_{i}|i\in I\\}$, then $g$ preserves
${\mathcal{P}}$ if for all $i\in I$ there is a unique $j\in I$ such that
$g^{-1}(A_{i})=A_{j}$. Note that $g$ does not necessarily preserve
${\mathcal{P}}_{g}$.

######  Lemma 4.5.

Let $g:X\to X$ preserve a partition ${\mathcal{P}}$. Then
$\left.g^{-1}\right|_{{\mathcal{P}}}$ is injective and hence bijective if
${\mathcal{P}}$ is finite.

###### Proof.

Let $A,B\in{\mathcal{P}}$. Suppose $g^{-1}(A)=g^{-1}(B)$ which means
$A\cap\mbox{\rm im}g=B\cap\mbox{\rm im}g$. Since $A$ and $B$ are either equal
or have empty intersection, $A\cap\mbox{\rm im}g=B\cap\mbox{\rm im}g$ is the
case if $A=B$ or $A\cap\mbox{\rm im}g=B\cap\mbox{\rm im}g=\emptyset$. But
$A\cap\mbox{\rm im}g=\emptyset$ means $g^{-1}(A)=\emptyset$, a possibility
which is excluded, as a partition does not contain the empty set. ∎

######  Lemma 4.6.

Let $g:X\to X$ and $f:X\to Y$. If ${\mathcal{P}}_{f}={\mathcal{P}}_{f\circ g}$
then $g$ preserves ${\mathcal{P}}_{f}$.

###### Proof.

By assumption

$\\{f^{-1}(y)|y\in Y\\}=\\{g^{-1}(f^{-1}(y))|y\in Y\\}$

which says exactly that $g^{-1}({\mathcal{P}}_{f})={\mathcal{P}}_{f}$. ∎

A map $p:X\to X$ is an idempotent if and only if it preserves its partition
and maps each member $A\in{\mathcal{P}}_{p}$ to a single point in $A$.

######  Lemma 4.7.

Let $p:X\to X$ be an idempotent. If $p$ preserves ${\mathcal{P}}$ and
$|{\mathcal{P}}|=|{\mathcal{P}}_{p}|<+\infty$ then
${\mathcal{P}}_{p}={\mathcal{P}}$.

###### Proof.

As $p$ maps each member $A\in{\mathcal{P}}_{p}$ to a single point in $A$,
${\mathcal{P}}_{p}$ is the finest partition preserved by $p$. Hence if $p$
preserves ${\mathcal{P}}$ then it preserves the partition generated by
${\mathcal{P}}$ and ${\mathcal{P}}_{p}$ which can’t be finer than
${\mathcal{P}}_{p}$. Therefore $|{\mathcal{P}}|=|{\mathcal{P}}_{p}|<+\infty$
implies ${\mathcal{P}}_{p}={\mathcal{P}}$. ∎

######  Lemma 4.8.

Let $p,q:X\to X$ two idempotents. If $p$ preserves ${\mathcal{P}}_{q}$ then
$qp=q$.

###### Proof.

Suppose $p$ preserves ${\mathcal{P}}_{q}$. Then it also preserves the
partition generated by ${\mathcal{P}}_{p}$ and ${\mathcal{P}}_{q}$. As
${\mathcal{P}}_{p}$ is the finest partition preserved by $p$,
${\mathcal{P}}_{q}$ must be coarser than ${\mathcal{P}}_{p}$ or
${\mathcal{P}}_{q}={\mathcal{P}}_{p}$ . It follows that
$\left.p^{-1}\right|_{{\mathcal{P}}_{q}}$ is the identity map from
${\mathcal{P}}_{q}$ to itself. This implies $q^{-1}=p^{-1}q^{-1}$ hence
$qp=q$. ∎

The condition of the following lemma is satisfied for all compact right
topological semigroups and so in particular for any finite semigroup.

######  Lemma 4.9.

Let $S$ be a sub-semigroup of ${\mathcal{F}}(X)$ which admits a kernel which
contains an idempotent. The following are equivalent.

  1. (1)

All elements of $S$ preserve the partition defined by the idempotent.

  2. (2)

$S$ has a unique minimal left ideal, i.e., the kernel is left simple.

###### Proof.

$1\Rightarrow 2$. Let $q\in S$ be a minimal idempotent such that all elements
of $S$ preserve ${\mathcal{P}}_{q}$. Let $p\in S$ be another minimal
idempotent. By assumption $p$ preserves ${\mathcal{P}}_{q}$. By Lemma 4.8 we
have $qp=q$. Hence $q$ lies in the minimal left ideal generated by $p$. Since
all idempotents of a minimal left ideal generate the same left ideal,
therefore $S$ has a unique minimal left ideal.

$2\Rightarrow 1$. Let $p$ be an idempotent in the unique minimal left ideal
$L$. Let $s\in S$. Then $ps$ lies in the kernel of $S$ which coincides with
$L$. By Lemma 3.1, ${\mathcal{P}}_{ps}={\mathcal{P}}_{p}$. By Lemma 4.6, $s$
preserves ${\mathcal{P}}_{p}$. ∎

###### Proof of Theorem 4.1.

Suppose first that ${\mathcal{S}}_{\theta}$ contains a unique minimal left
ideal. By Lemma 4.9 all its elements preserve a partition
${\mathcal{B}}=\\{A_{1},\cdots,A_{k}\\}$ defined by any element of that ideal.
Note that $k$ must be the naïve column number $c$. Define the length-$\ell$
substitution $\eta$ on the alphabet ${\mathcal{B}}$ through
$\eta=\eta_{0}|\cdots|\eta_{\ell-1}$ where

$\eta^{-1}_{m}:=\left.\theta^{-1}_{m}\right|_{{\mathcal{B}}}\,,$

in other words, $\eta_{m}(A_{i})$ is the unique $A_{j}$ which contains
$\theta_{m}(a_{i})$ for some $a_{i}\in A_{i}$. This is well-defined as
$\theta_{m}$ preserves the partition ${\mathcal{B}}$. By Lemma 4.5 $\eta$ is
bijective. The code $\beta$ is given by $a\mapsto A_{i}$ for all $a\in A_{i}$.

To prove the converse of the statement, suppose now there is a bijective
substitution $\eta=\eta_{0}|\cdots|\eta_{\ell-1}$ on a $c$-letter alphabet
${\mathcal{B}}$ and a map $\beta:{\mathcal{A}}\to{\mathcal{B}}$ such that

$\eta_{m}\circ\beta=\beta\circ\theta_{m}$

for all $m=0,\cdots,\ell-1$. Since $\eta$ is bijective this implies that the
partition ${\mathcal{P}}_{\beta}$ defined by $\beta$ must be the same as that
defined by each $\beta\circ\theta_{m}$ and then also the same as that defined
by any $\beta\circ f$ for any $f\in S_{\theta}$. By Lemma 4.6 all elements of
$S_{\theta}$ must preserve ${\mathcal{P}}_{\beta}$. Let $p$ be a minimal
idempotent of $S_{\theta}$. By definition of the naïve column rank its rank is
$c$, which is also the rank of $\beta$. Lemma 4.7 implies therefore that
${\mathcal{P}}_{p}={\mathcal{P}}_{\beta}$. Now, we conclude with Lemma 4.9
that ${\mathcal{S}}_{\theta}$ has a unique minimal left ideal. ∎

###### Proof of Theorem 4.3.

Primitivity of $\eta$ follows directly from the primitivity of $\theta$.

We show that $\eta$ is aperiodic. We may assume that $\eta_{0}={\mathbf{1}}$
(otherwise, we take a power of $\eta$). Assume, by contradiction, that $h$ is
the period of $\eta$, i.e. all $x\in X_{\eta}$ satisfy $x_{n+h}=x_{n}$. This
is only possible if $\eta^{N}_{kh}=\eta_{0}$ for all $k\geq 0$ and $N$ large
enough such that $kh<\ell^{N}$. Furthermore, $\frac{1}{h}$ must be an
eigenvalue of the dynamical system defined by $\eta$ and therefore also an
eigenvalue of the dynamical system defined by $\theta$. As $\theta$ has
trivial height this means that $h$ must divide $\ell^{N}$ for some $N$.
However, as $\eta^{N}_{kh}=\eta_{0}={\mathbf{1}}$ we then have, for all $0\leq
k<\ell$

${\mathbf{1}}={\eta^{N+1}}_{k\ell^{N}}={\eta^{N}}_{0}\eta_{k}=\eta_{k}$

which contradicts the primitivity of $\eta$, as $c>1$.

We show that the factor map $F_{\beta}$ induced by $\beta$ is almost
injective. The common maximal equicontinuous factor is $\mathbb{Z}_{\ell}$, as
the height of $\theta$ is trivial. The regular fibres of $\theta$ have the
same size as those of $\eta$. The factor map induced by $\eta$ maps fibres
surjectively onto fibres. Also, it must map at least one regular fibre to a
regular fibre. This is because these fibres are a set of Haar probability
measure one in $\mathbb{Z}_{\ell}$. Thus the restriction of $F_{\beta}$ to
that fibre must be bijective. ∎

Remark. The following shows that our characterisation of when a substitution
allows for an inner encoded bijective substitution is stable under taking
powers.

######  Lemma 4.10.

Let $\theta$ be a constant length substitution. Then $S_{\theta^{n}}$ has a
unique minimal left ideal if and only if $S_{\theta}$ has a unique minimal
left ideal.

###### Proof.

We have $S_{\theta^{n}}\subset S_{\theta}$, and also, since $\theta$ and
$\theta^{n}$ have the same column number $c$, $S_{\theta^{n}}^{(c)}\subset
S_{\theta}^{(c)}$. If $S_{\theta}$ has two (disjoint) minimal left ideals
$L_{1}$ and $L_{2}$, then $L_{1}\cap S_{\theta^{n}}$ and $L_{2}\cap
S_{\theta^{n}}$ are disjoint minimal left ideals of $S_{\theta^{n}}$. This
shows the direction $\Rightarrow$. The other direction is actually a
consequence of Theorem 4.1. If $S_{\theta}$ has a unique minimal left ideal
then there is a bijective substitution $\eta$ and a code $\beta$ such that
$\beta\circ\theta_{m}=\eta_{m}\circ\beta$. This implies
$\beta\circ{\theta^{n}}_{m}={\eta^{n}}_{m}\circ\beta$ for any $n$ and any
$m\leq\ell^{n}-1$. Hence $\eta^{n}$ is a bijective substitution which is an
inner encoding of $\theta^{n}$. Clearly $\eta^{n}$ is bijective and hence by
Theorem 4.1, $S_{\theta^{n}}$ must have a unique minimal left ideal. ∎

######  Example 4.11.

Bijective substitution shifts have a single irregular fibre modulo
$\mathbb{Z}$, with respect to their maximal equicontinuous factor. Thus, it is
natural to ask if a substitutive subshift with a bijective factor has only
finitely many singular fibres. This is false. Consider

$\displaystyle\theta\colon 0$ $\displaystyle\mapsto 021$ $\displaystyle 1$
$\displaystyle\mapsto 130$ $\displaystyle 2$ $\displaystyle\mapsto 201$
$\displaystyle 3$ $\displaystyle\mapsto 310$

which is easily checked to be primitive, aperiodic and of height $1$. Let
$\pi$ be the code

$\displaystyle\pi\colon 0,2$ $\displaystyle\mapsto a$ $\displaystyle 1,3$
$\displaystyle\mapsto b$

It is not hard to see that $(\eta,\pi)$ is an inner encoding of $X_{\theta}$
where $\eta$ is the bijective, aperiodic substitution given by:

$\displaystyle\eta\colon a$ $\displaystyle\mapsto aab$ $\displaystyle b$
$\displaystyle\mapsto bba.$

By Theorem 4.1, $S_{\theta}$ has a unique minimal left ideal. Indeed, all
elements of this minimal left ideal have the common partition
$\\{\\{0,2\\},\\{1,3\\}\\}$. Note that any element from $\mathbb{Z}_{3}$ which
does not contain the digit $2$ is an irregular fibre.

###  4.2. Factors which preserve the fixed point fibre

In Theorem 4.1, we characterised the substitution shifts which admit a
bijective inner encoding. In this section, we extend this to characterising
substitution shifts which admit a bijective substitution shift as a factor via
a factor map which preserves the fixed point fibre.

######  Lemma 4.12.

Let $n=(-l,r)$. If $S_{\theta^{(n)}}$ has a unique minimal left ideal then
$S_{\theta}$ has a unique minimal left ideal.

###### Proof.

As $\theta$ is an inner encoding of the collared substitution $\theta^{(n)}$,
the semigroup of the collared substitution $S_{\theta}$ is a homomorphic image
of $S_{\theta^{(n)}}$. Now Lemma 3.5 implies the result.

∎

######  Theorem 4.13.

Let $\theta$ be a primitive aperiodic length-$\ell$ substitution with naïve
column number $c$. The following are equivalent.

  1. (1)

$(X_{\theta},\sigma)$ factors onto a bijective substitution shift
$(X_{\eta},\sigma)$ via a factor map $F$ which preserves the fixed point
fibre.

  2. (2)

$S_{\theta}$ has a unique minimal left ideal.

###### Proof.

First suppose that $F:X_{\theta}\rightarrow X_{\eta}$ is a factor map which
preserves the fixed point fibre and with $\eta$ bijective. By Proposition 2.8
there is an $n=(-l,r)$, with $0\leq l,r\leq 1$ such that $(X_{\eta},\sigma)$
is a factor of $(X_{\theta^{(n)}},\sigma)$ via a radius zero factor map
$F_{\tau}:X_{\theta^{(n)}}\rightarrow X_{\eta}$ where $F=F_{\tau}\circ
F_{\imath}^{-1}$. Now by Lemma 2.4, $F_{\imath}$ preserves the fixed point
fibre, and by assumption, so does $F$. Hence $F_{\tau}$ preserves the fixed
point fibre. Finally by Lemma 2.5 $\eta$ is an inner encoding of
$\theta^{(n)}$. By Theorem 4.1, $S_{\theta^{(n)}}$ has a unique minimal left
ideal. By Lemma 4.12, $S_{\theta}$ has a unique minimal left ideal.

The converse follows directly from Theorem 4.1. ∎

We remark that Theorems 4.1 and 4.13 imply that all factor maps to a bijective
substitution which fix the fixed point fibre must have radius zero.

###  4.3. Bijective factors which do not preserve the fixed point fibre

In this section we extend Theorem 4.13 to substitutions which have a bijective
substitution factor via a factor map which does not send fixed points to fixed
points. To do this we need to recall a little more information on the
arithmetic information that factor maps encode.

###  4.4. Factors of substitution shifts and their $\kappa$-values

We describe factor maps $F$ of substitution shifts by associating to each of
them an $\ell$-adic integer which describes how $F$ translates fibres of an
equicontinuous factor. This element of $\mathbb{Z}_{\ell}$ is determined by
where $F$ sends fixed points.

Let $X$, $Y$ be minimal shift spaces with a common equicontinuous factor
$(\mathcal{G},R)$. Let $\pi_{X}:X\rightarrow\mathcal{G}$ and
$\pi_{Y}:Y\rightarrow\mathcal{G}$ be corresponding equicontinuous factor maps.
Let $\mathrm{Fac}(X,Y)$ be the collection of factor maps from $(X,\sigma)$ to
$(Y,\sigma)$, and let $\mathrm{Conj}(X,Y)$ be the set of injective factor maps
from $(X,\sigma)$ to $(Y,\sigma)$.

######  Theorem 4.14.

[4, Theorem 3.3]. Let $(X,\sigma)$ and $(Y,\sigma)$ be infinite minimal
shifts. Suppose that the group rotation $(\mathcal{G},R)$ is the maximal
equicontinuous factor of both $(X,\sigma)$ and $(Y,\sigma)$ and fix the factor
maps $\pi_{X}:X\rightarrow\mathcal{G}$ and $\pi_{Y}:Y\rightarrow\mathcal{G}$.
Then there is a map $\kappa:\mbox{Fac}(X,Y)\rightarrow\mathcal{G}$ such that

$\pi_{Y}(F(x))=\kappa(F)+\pi_{X}(x)$

for all $x\in X$ and $F\in\mbox{Fac}(X,Y)$. Also

  1. (1)

if $(Z,\sigma)$ is another shift which satisfies the assumptions on
$(X,\sigma)$, then $\kappa(G\circ F)=\kappa(G)+\kappa(F)$ for
$F\in\mbox{Fac}(X,Y)$, $G\in\mbox{Fac}(Y,Z)$, and

  2. (2)

if
$\min_{g\in\mathcal{G}}|\pi_{X}^{-1}(g)|=\min_{g\in\mathcal{G}}|\pi_{Y}^{-1}(g)|=c<\infty$,
then for each $F\in\mbox{Fac}(X,Y)$, we have

$\\{z\in\mathbb{Z}_{r}:|\pi_{Y}^{-1}(z)|>c\\}\subset\\{z\in\mathbb{Z}_{r}:|\pi_{X}^{-1}(z)|>c\\}+\kappa(F),$

and $\kappa$ is at most $c$-to-one.

We call $\kappa(F)$ the $\kappa$-value of $F$. In fact
$\kappa:\mathrm{Fac}(X,Y)\rightarrow\mathcal{G}$ is defined by
$\kappa(F):=\pi_{Y}(F(x))-\pi_{X}(x)$, where this quantity does not depend on
$x$ for minimal systems. It is important to note that the $\kappa$-value of a
map depends on the choice of maximal equicontinuous factor maps.

If $F:X_{\theta}\rightarrow X_{\eta}$ is a factor map between two
length-$\ell$ substitution shifts, then $\kappa(F)=0$ if and only if
$\theta$-fixed points are mapped to $\eta$-fixed points, i.e., if $F$
preserves the fixed point fibre.

The following tells us that $\kappa$-values of conjugacies between two
length-$\ell$ shifts are constrained. We say that $z\in\mathbb{Z}_{\ell}$ is
rational if it is eventually periodic. This naming follows from the fact that
if $z\in\mathbb{Z}_{\ell}$ is eventually periodic, then it is the $\ell$-adic
expansion of a rational number.

######  Proposition 4.15.

Let $\theta$ and $\theta^{\prime}$ be primitive, aperiodic length-$\ell$
substitutions, with $\theta$ of trivial height. If
$F\in\mbox{Fac}(X_{\theta},X_{\theta^{\prime}})$, then $\kappa(F)$ is
rational.

###### Proof.

In the case where the factor map is a conjugacy, the statement is [4,
Proposition 3.24]. We will suppose that $F=F_{\tau}$ where
$\tau:\mathcal{A}_{\theta}\rightarrow\mathcal{A}_{\theta^{\prime}}$, as
otherwise the usual combination of Proposition 2.8 and Theorem 2.7 allows us
to reduce to this case.

Theorem 2.7 tells us that there is a pair $(\eta,\beta)$ which is inner
encoded by $\theta$, and a code
$\tau^{\prime}:\mathcal{A}_{\eta}\rightarrow\mathcal{A}_{\theta^{\prime}}$
such that $F_{\tau^{\prime}}:X_{\eta}\rightarrow X_{\theta^{\prime}}$ is a
conjugacy. Again by [4, Proposition 3.24], $\kappa(F_{\tau^{\prime}})$ is
rational. But also, $\tau=\tau^{\prime}\circ\beta$, and since
$(\theta^{\prime},\beta)$ is inner encoded by $\theta$, then by Lemma 2.5,
$\kappa(F_{\beta})=0$. Thus $\kappa(F_{\tau})=\kappa(F_{\tau^{\prime}})$ is
also rational.

∎

If $F:X_{\theta}\to X_{\eta}$ is a factor map onto a bijective substitution
shift with $\kappa(F)=m\in\mathbb{Z}$, then $\tilde{F}:=\sigma^{-m}\circ
F:X_{\theta}\to X_{\eta}$ is also a factor map onto a bijective substitution
and, as $\kappa(\tilde{F})=0$, we can apply Theorem 4.13 to conclude that
$S_{\theta}$ has a unique left minimal ideal. In other words, Theorem 4.13
extends verbatim to the case in which the kappa-value of the factor map is an
integer.

The following example shows that there exist factor maps $F$ where
$\kappa(F)\not\in\mathbb{Z}$.

######  Example 4.16.

Take the following two substitutions:

$\displaystyle\eta\colon a$ $\displaystyle\mapsto abcba,$
$\displaystyle\theta\colon 0$ $\displaystyle\mapsto 35203$ $\displaystyle b$
$\displaystyle\mapsto bcacb,$ $\displaystyle 1$ $\displaystyle\mapsto 35214$
$\displaystyle c$ $\displaystyle\mapsto cabac,$ $\displaystyle 2$
$\displaystyle\mapsto 41520$ $\displaystyle 3$ $\displaystyle\mapsto 41534$
$\displaystyle 4$ $\displaystyle\mapsto 02140$ $\displaystyle 5$
$\displaystyle\mapsto 02153$

The words of length two in $\mathcal{L}_{\eta}$ are

$\\{ab,ac,ba,bc,ca,cb\\},$

and by mapping $(ab),(ac),(ba),(bc),(ca),(cb)$ to $0,1,2,3,4,5$, respectively,
it can be verified that $\theta=\eta^{(+1)}$. Thus $X_{\theta}$ factors
bijectively onto the bijective substitution shift $X_{\eta}$. However, it can
be verified that ${\mathcal{S}}_{\theta}$ does not have a unique minimal left
ideal. Indeed, it has two minimal idempotents, one generated by the partition
$\\{\\{0,1\\},\\{2,3\\},\\{4,5\\}\\}$, and the other generated by the
partition $\\{\\{0,5\\},\\{1,3\\},\\{2,4\\}\\}$; see Lemma 3.1. This does not
contradict Theorem 4.13 because we will see that the radius zero conjugacy
$F_{\tau}:X_{\theta}\rightarrow X_{\eta}$, which is given by the local rule
$\tau$:

$\displaystyle\tau:0,1$ $\displaystyle\mapsto a,$ $\displaystyle 2,3$
$\displaystyle\mapsto b,$ $\displaystyle 4,5$ $\displaystyle\mapsto c$

is a factor map with nonzero $\kappa$-value. In particular, Lemma 4.17 will
tell us that $\kappa(F_{\tau})=-1/4=-1/(\ell-1)$.

We now show how to “correct” such factor maps to obtain factor maps with
$\kappa$-value $0$.

Recall the $k$-shifted extension of $\theta$ from Definition 2.2.

######  Lemma 4.17.

Let $\theta:\mathcal{A}\rightarrow\mathcal{A}^{\ell}$ be an aperiodic
primitive length-$\ell$ substitution of trivial height, and let
$\zeta:=\theta^{(+k)}$ be its $k$-shifted extension, with $0\leqslant k<\ell$.
Then there is a conjugacy given by a code $F:X_{\zeta}\rightarrow X_{\theta}$
and $\kappa(F)=\frac{k}{1-\ell}$.

###### Proof.

Let $F^{-1}:X_{\theta}\rightarrow X_{\zeta}$ be the natural conjugacy with
right radius $1$ and left radius $0$, where the valid word $ab$ is mapped to
the letter $(a,b)$. Then iteration of

$\zeta\circ F^{-1}=F^{-1}\circ\sigma^{k}\circ\theta$

gives

$\zeta^{n}\circ
F^{-1}=F^{-1}\circ(\sigma^{k}\circ\theta)^{n}=F^{-1}\circ\sigma^{k\frac{1-\ell^{n}}{1-\ell}}\circ\theta^{n}.$

Applying this identity to a word of length $2$, and letting
$n\rightarrow\infty$, we obtain, for some fixed points $u$ and $v$ of $\theta$
and $\zeta$ respectively,

$v=F^{-1}\circ\lim_{n\rightarrow\infty}\sigma^{k\frac{1-\ell^{n}}{1-\ell}}(u),$

so that $\kappa(F^{-1})=\frac{-k}{1-\ell}$. The result follows. ∎

Remember that $F^{-1}$ is not necessarily a radius zero factor map.

######  Corollary 4.18.

Let $\theta:\mathcal{A}\rightarrow\mathcal{A}^{\ell}$ be an aperiodic
primitive length-$\ell$ substitution of trivial height, and let
$\frac{p}{q}\in\mathbb{Z}_{\ell}$ be irreducible. Then there exists some
substitution $\zeta$ and a conjugacy $F:X_{\zeta}\rightarrow X_{\theta}$ that
satisfies $\kappa(F)=\frac{p}{q}$.

###### Proof.

As shown in Lemma 4.17, if $0\leq k<\ell$ and $\zeta=\theta^{(+k)}$, then
$\kappa(F)=\frac{k}{1-\ell}$. Similarly, if we replace $\theta$ by
$\theta^{m}$ for some value of $m$ and take $\zeta=(\theta^{m})^{(+k)}$, the
corresponding factor map has $\kappa$-value $\frac{k}{1-\ell^{m}}$, where we
can take $k$ to be any value between $0$ and $\ell^{m}-1$.

To prove the general statement, suppose first that $-q<p\leqslant 0$, and that
$p$ and $q$ have no common divisors. As we assume that
$p/q\in\mathbb{Z}_{\ell}$, then $q$ and $\ell$ are coprime, so that
$\ell^{\varphi(q)}\equiv 1\pmod{q}$, where $\varphi$ is Euler’s totient
function. Thus $\ell^{\varphi(q)}-1=hq$ for some $h>0$. Since $-q<p\leqslant
0$, we have $0\leqslant-hp<hq<\ell^{\varphi(q)}$, so we can take
$\zeta=(\theta^{\varphi(q)})^{(+(-hp))}$, and the natural conjugacy
$F:X_{\zeta}\rightarrow X_{\theta}$ will satisfy:

$\kappa(F)=\frac{-hp}{1-\ell^{\varphi(q)}}=\frac{-hp}{-hq}=\frac{p}{q},$

as desired.

For the general case, it is enough to note that
$\frac{p}{q}=M+\frac{p_{0}}{q}$ for some integer $M$ and $-q<p_{0}\leqslant
0$, where $p_{0}$ will also be coprime to $q$, so it suffices to take
$\zeta=(\theta^{\varphi(q)})^{(+(-hp_{0}))}$, as above, and $\sigma^{M}\circ
F$ as the desired conjugacy. ∎

Define, for a substitution of trivial height with column number $c$,

$\mathcal{F}_{\theta}:=\\{w=w_{k}\ldots
w_{1}\in(\mathbb{Z}/\ell\mathbb{Z})^{+}:|\theta_{w_{1}}\circ\ldots\circ\theta_{w_{k}}(\mathcal{A})|=c\\}.$

Note that if $\mathcal{F}_{\theta}$ contains a length $k$ word, then
$\theta^{k}$ has a column with $c$ elements.

######  Lemma 4.19.

Let $\theta$ be a constant length substitution. Let $(\eta,\beta)$ be an inner
encoding of $\theta$. The length $j(\eta)$ of the smallest word in
${\mathcal{F}}_{\eta}$ is bounded by the length $j(\theta)$ of the smallest
word in ${\mathcal{F}}_{\theta}$.

###### Proof.

Let $U_{\theta}=\\{\mbox{\rm im}f:f\in\ker S_{\theta}\\}$. We first show that
$U_{\eta}=\beta(U_{\theta})$. Indeed, by Lemma 3.5 we have $\ker
S_{\eta}=\beta(\ker S_{\theta})\beta^{-1}$ and hence

$U_{\eta}=\\{\mbox{\rm im}f:f\in\ker S_{\eta}\\}=\\{\mbox{\rm im}\beta\circ
g:g\in\ker S_{\theta}\\}.$

By definition, $w_{k}\ldots w_{1}$ is a word in ${\mathcal{F}}_{\theta}$ if
and only if $\theta_{w_{1}}\circ\ldots\circ\theta_{w_{k}}(\mathcal{A})\in
U_{\theta}$. Now, by the above,

$\eta_{w_{1}}\circ\ldots\circ\eta_{w_{k}}(\mathcal{B})=\beta\circ\theta_{w_{1}}\circ\ldots\circ\theta_{w_{k}}(\mathcal{A})\in\beta(U_{\theta})=U_{\eta}.$

This implies ${\mathcal{F}}_{\theta}\subset{\mathcal{F}}_{\eta}$ and hence
$j(\eta)\leq j(\theta)$. ∎

######  Lemma 4.20.

Let $\theta:\mathcal{A}\rightarrow\mathcal{A}^{\ell}$ be an aperiodic
primitive length-$\ell$ substitution of trivial height, and let
$F:X_{\theta}\rightarrow X_{\zeta}$ be a factor map. If $\mathcal{F}_{\theta}$
contains a word of length $j$, then $n\kappa(F)\in\mathbb{Z}$ for some $0\leq
n\leq(\ell-1)(\ell^{j}-1)$.

###### Proof.

In the case where the factor map is a conjugacy, the statement is [4,
Proposition 3.24]. Otherwise, we can suppose that $F=F_{\tau}$ where
$\tau:\mathcal{A}_{\theta}\rightarrow\mathcal{A}_{\zeta}$ (invoking the usual
combination of Proposition 2.8 and Theorem 2.7 to reduce to this case).

Theorem 2.7 tells us that there is a pair $(\eta,\beta)$ which is inner
encoded by $\theta$, and a code
$\tau^{\prime}:\mathcal{A}_{\eta}\rightarrow\mathcal{A}_{\zeta}$ such that
$F_{\tau^{\prime}}:X_{\eta}\rightarrow X_{\zeta}$ is a conjugacy, and
$\kappa(F_{\tau})=\kappa(F_{\tau^{\prime}})$. Then again by [4, Proposition
3.24], the denominator of the reduced form of $\kappa(F_{\tau^{\prime}})$ is
at most $(\ell-1)(\ell^{j}-1)$, where $j=j(\eta)$ is the length of the
smallest word in $\mathcal{F}_{\eta}$. Now by Lemma 4.19, we have that
$j(\eta)\leq j(\theta)$ . Thus the denominator of $\kappa(F_{\tau^{\prime}})$
is at most $(\ell-1)(\ell^{j(\theta)}-1)$. Since
$\kappa(F_{\tau^{\prime}})=\kappa(F_{\tau})$, the result follows. ∎

######  Theorem 4.21.

Let $\theta$ be an aperiodic primitive constant length-$\ell$ substitution
with column number $c>1$ and trivial height. The following are equivalent:

  1. (1)

$X_{\theta}$ factors onto an aperiodic bijective length-$\ell$ substitution
shift whose alphabet has c letters and such that the factor map is almost
everywhere one-to-one.

  2. (2)

There exists $0\leq n,k$ such that the semigroup $S_{(\theta^{n})^{(+k)}}$
contains a unique minimal left ideal.
Moreover, if $j$ is the length of the smallest word in $\mathcal{F}_{\theta}$,
then $n\leq(\ell-1)(\ell^{j}-1)-1$ and $0\leq k\leq\ell^{n}$.

###### Proof.

Let $F:(X_{\theta},\sigma)\to(X_{\eta},\sigma)$ where $\eta$ is bijective,
defined on a $c$-letter alphabet. By Proposition 4.15, $\kappa(F)$ is
rational, and by Lemma 4.20, $\kappa(F)=p/q$ where $1\leq
q\leq(\ell-1)(\ell^{j}-1)$, where $j$ is the length of the smallest word in
$\mathcal{F}_{\eta}$. Using $\varphi(q)\leq(\ell-1)(\ell^{j}-1)-1$, and taking
a shift if necessary, Corollary 4.18 tells us that there is
$n\leq(\ell-1)(\ell^{j}-1)-1$ and $0\leq k\leq\ell^{n}$, and a conjugacy
$\tilde{F}:(X_{(\theta^{n})^{(+k)}},\sigma)\to(X_{\theta},\sigma)$ such that
$\kappa(F)+\kappa(\tilde{F})\in\mathbb{Z}$. As
$\kappa(F\circ\tilde{F})\in\mathbb{Z}$, then $S_{(\theta^{n})^{(+k)}}$ must
have a unique minimal left ideal by Theorem 4.13.

For the converse, if $S_{(\theta^{n})^{(+k)}}$ has a unique minimal left
ideal, then by Theorem 4.13, $(X_{(\theta^{n})^{(+k)}},\sigma)$ factors
dynamically onto a bijective substitution shift. As
$(X_{(\theta^{n})^{(+k)}},\sigma)$ is conjugate to $(X_{\theta},\sigma)$, the
result follows. ∎

######  Example 4.22.

We return to Example 4.16, with $\theta$ and $\eta$ defined there. We take
$\zeta:=\theta^{(+3)}$, and we claim that $\zeta$ has a unique minimal ideal.
The reason why we make this choice $\theta^{(+3)}$ is that, by Lemma 4.17, the
natural conjugacy $G:X_{\zeta}\rightarrow X_{\theta}$ satisfies
$\kappa(G)=-3/4$. Then $\kappa(\sigma\circ F)=3/4$, and $F\circ\sigma\circ
G:X_{\zeta}\rightarrow X_{\eta}$ has $\kappa$-value zero. Note though that
$F\circ\sigma\circ G$ has right radius one, so we will need to work with
$X_{\zeta^{(2)}}$. Theorem 4.13 guarantees that $\mathcal{S}_{\zeta^{(2)}}$
has a unique minimal left ideal, and Lemma 4.12 guarantees that so also does
$\mathcal{S}_{\zeta}$.

To define $\zeta$, we simultaneously list and code the words of length two in
$\mathcal{L}_{\theta}$:

$\displaystyle A$ $\displaystyle=02,\hskip 50.00008ptB=03,$ $\displaystyle C$
$\displaystyle=14,\hskip 50.00008ptD=15,$ $\displaystyle E$
$\displaystyle=20,\hskip 50.00008ptF=21,$ $\displaystyle G$
$\displaystyle=34,\hskip 50.00008ptH=35,$ $\displaystyle I$
$\displaystyle=40,\hskip 50.00008ptJ=41,$ $\displaystyle K$
$\displaystyle=52,\hskip 50.00008ptL=53;$

it then can be verified that the 3-shifted extension $\zeta:=\theta^{(+3)}$ of
$\theta$ is given by

$\displaystyle\zeta:A$ $\displaystyle\mapsto BGJDK$ $\displaystyle B$
$\displaystyle\mapsto BGJDL$ $\displaystyle C$ $\displaystyle\mapsto CIAFC$
$\displaystyle D$ $\displaystyle\mapsto CIAFD$ $\displaystyle E$
$\displaystyle\mapsto EBHKE$ $\displaystyle F$ $\displaystyle\mapsto EBHKF$
$\displaystyle G$ $\displaystyle\mapsto GIAFC$ $\displaystyle H$
$\displaystyle\mapsto GIAFD$ $\displaystyle I$ $\displaystyle\mapsto IBHKE$
$\displaystyle J$ $\displaystyle\mapsto IBHKF$ $\displaystyle K$
$\displaystyle\mapsto LGJDK$ $\displaystyle L$ $\displaystyle\mapsto LGJDL$

######  Example 4.23.

Consider the following length $3$ substitution:

$\displaystyle\theta\colon a$ $\displaystyle\mapsto abf$ $\displaystyle b$
$\displaystyle\mapsto aef$ $\displaystyle c$ $\displaystyle\mapsto abf$
$\displaystyle d$ $\displaystyle\mapsto dec$ $\displaystyle e$
$\displaystyle\mapsto dbc$ $\displaystyle f$ $\displaystyle\mapsto dec.$

This substitution has column number $2$, trivial height, is primitive, and it
has two left minimal ideals, associated to the partitions
$\mathcal{P}_{\theta_{0}}=\mathcal{P}_{\theta_{2}}=\\{\\{a,b,c\\},\\{d,e,f\\}\\}$
and $\mathcal{P}_{\theta_{1}}=\\{\\{a,c,e\\},\\{b,d,f\\}\\}$. In fact, this
substitution is _quasi-bijective_ (see [13]) in the sense that every element
in $S_{\theta}$ (bar the identity map) has rank $2$, and thus the only
irregular fibre of this substitution corresponds to the set of fixed points.
Thus there are forbidden words of length one, and $j=1$.

Theorem 4.21 tells us that, if for every $0\leq n\leq(\ell-1)(\ell^{j}-1)-1$
and $0\leq k<\ell^{n}$ the semigroup $S_{(\theta^{n})^{(+k)}}$ has more than
one left minimal ideal, then the shift $X_{\theta}$ has no non-trivial
bijective factors; here, $j=1$, so the bounds for $n$ and $k$ are $3$ and
$27$, respectively.

Via automated computation, we can determine each of the finitely many
substitutions $(\theta^{n})^{(+k)}$, e.g. for $n=3$ and $k=11$ we get the
following:

$\displaystyle a_{b}$ $\displaystyle\mapsto
f_{d}d_{b}b_{c}c_{d}d_{e}e_{c}c_{d}d_{e}e_{c}c_{d}d_{b}b_{c}c_{a}a_{b}b_{f}f_{a}a_{b}b_{f}f_{a}a_{e}e_{f}f_{d}d_{e}e_{c}c_{d}d_{e}e_{c}$
$\displaystyle a_{e}$ $\displaystyle\mapsto
f_{d}d_{b}b_{c}c_{d}d_{e}e_{c}c_{d}d_{e}e_{c}c_{d}d_{b}b_{c}c_{a}a_{b}b_{f}f_{d}d_{e}e_{c}c_{d}d_{b}b_{c}c_{a}a_{b}b_{f}f_{a}a_{b}b_{f}$
$\displaystyle b_{c}$ $\displaystyle\mapsto
c_{a}a_{e}e_{f}f_{a}a_{b}b_{f}f_{d}d_{e}e_{c}c_{d}d_{b}b_{c}c_{a}a_{b}b_{f}f_{a}a_{b}b_{f}f_{a}a_{e}e_{f}f_{d}d_{e}e_{c}c_{a}a_{b}b_{f}$
$\displaystyle b_{f}$ $\displaystyle\mapsto
c_{a}a_{e}e_{f}f_{a}a_{b}b_{f}f_{d}d_{e}e_{c}c_{d}d_{b}b_{c}c_{a}a_{b}b_{f}f_{d}d_{e}e_{c}c_{d}d_{b}b_{c}c_{a}a_{b}b_{f}f_{d}d_{e}e_{c}$
$\displaystyle c_{a}$ $\displaystyle\mapsto
f_{d}d_{b}b_{c}c_{d}d_{e}e_{c}c_{d}d_{e}e_{c}c_{d}d_{b}b_{c}c_{a}a_{b}b_{f}f_{a}a_{b}b_{f}f_{a}a_{e}e_{f}f_{d}d_{e}e_{c}c_{a}a_{b}b_{f}$
$\displaystyle c_{d}$ $\displaystyle\mapsto
f_{d}d_{b}b_{c}c_{d}d_{e}e_{c}c_{d}d_{e}e_{c}c_{d}d_{b}b_{c}c_{a}a_{b}b_{f}f_{d}d_{e}e_{c}c_{d}d_{b}b_{c}c_{a}a_{b}b_{f}f_{d}d_{e}e_{c}$
$\displaystyle d_{b}$ $\displaystyle\mapsto
c_{a}a_{e}e_{f}f_{a}a_{b}b_{f}f_{a}a_{b}b_{f}f_{a}a_{e}e_{f}f_{d}d_{e}e_{c}c_{a}a_{b}b_{f}f_{a}a_{e}e_{f}f_{d}d_{e}e_{c}c_{d}d_{e}e_{c}$
$\displaystyle d_{e}$ $\displaystyle\mapsto
c_{a}a_{e}e_{f}f_{a}a_{b}b_{f}f_{a}a_{b}b_{f}f_{a}a_{e}e_{f}f_{d}d_{e}e_{c}c_{d}d_{e}e_{c}c_{d}d_{b}b_{c}c_{a}a_{b}b_{f}f_{a}a_{b}b_{f}$
$\displaystyle e_{c}$ $\displaystyle\mapsto
f_{d}d_{b}b_{c}c_{d}d_{e}e_{c}c_{a}a_{b}b_{f}f_{a}a_{e}e_{f}f_{d}d_{e}e_{c}c_{a}a_{b}b_{f}f_{a}a_{e}e_{f}f_{d}d_{e}e_{c}c_{a}a_{b}b_{f}$
$\displaystyle e_{f}$ $\displaystyle\mapsto
f_{d}d_{b}b_{c}c_{d}d_{e}e_{c}c_{a}a_{b}b_{f}f_{a}a_{e}e_{f}f_{d}d_{e}e_{c}c_{d}d_{e}e_{c}c_{d}d_{b}b_{c}c_{a}a_{b}b_{f}f_{d}d_{e}e_{c}$
$\displaystyle f_{a}$ $\displaystyle\mapsto
c_{a}a_{e}e_{f}f_{a}a_{b}b_{f}f_{a}a_{b}b_{f}f_{a}a_{e}e_{f}f_{d}d_{e}e_{c}c_{a}a_{b}b_{f}f_{a}a_{e}e_{f}f_{d}d_{e}e_{c}c_{a}a_{b}b_{f}$
$\displaystyle f_{d}$ $\displaystyle\mapsto
c_{a}a_{e}e_{f}f_{a}a_{b}b_{f}f_{a}a_{b}b_{f}f_{a}a_{e}e_{f}f_{d}d_{e}e_{c}c_{d}d_{e}e_{c}c_{d}d_{b}b_{c}c_{a}a_{b}b_{f}f_{d}d_{e}e_{c}$

where each symbol $u_{v}$ corresponds to a $2$-letter word in $\theta$.
Computing the corresponding semigroup for each, we observe that in every case
it has between $2$ and $4$ minimal left ideals; for example, in the above case
there are four minimal left ideals given by the following partitions:

$\displaystyle\mathcal{P}_{1}$
$\displaystyle=\\{\\{b_{f},e_{f},e_{c},f_{a},c_{d},c_{a}\\},\\{f_{d},d_{b},d_{e},b_{c},a_{b},a_{e}\\}\\}$
$\displaystyle\mathcal{P}_{2}$
$\displaystyle=\\{\\{b_{f},f_{d},d_{e},e_{c},f_{a},a_{e}\\},\\{d_{b},e_{f},b_{c},a_{b},c_{d},c_{a}\\}\\}$
$\displaystyle\mathcal{P}_{3}$
$\displaystyle=\\{\\{b_{f},e_{f},e_{c},a_{b},a_{e},c_{a}\\},\\{f_{d},d_{b},d_{e},b_{c},f_{a},c_{d}\\}\\}$
$\displaystyle\mathcal{P}_{4}$
$\displaystyle=\\{\\{b_{f},e_{f},d_{e},b_{c},a_{b},c_{d}\\},\\{f_{d},d_{b},e_{c},f_{a},a_{e},c_{a}\\}\\}.$

Hence, $X_{\theta}$ cannot factor onto any bijective substitution.

We end with an example that shows that if a substitution shift has a bijective
shift factor, this does not imply that its pure base has a bijective shift
factor.

######  Example 4.24.

Consider the following substitution on $\\{a,\bar{a},b,c,d,e,f\\}$:

$\displaystyle\theta\colon a$ $\displaystyle\mapsto adc$
$\displaystyle\bar{a}$ $\displaystyle\mapsto\bar{a}dc$ $\displaystyle b$
$\displaystyle\mapsto bea$ $\displaystyle c$ $\displaystyle\mapsto cfb$
$\displaystyle d$ $\displaystyle\mapsto d\bar{a}e$ $\displaystyle e$
$\displaystyle\mapsto ebf$ $\displaystyle f$ $\displaystyle\mapsto fcd.$

It is routine to check that this substitution is primitive and has height $2$.