# Substitutions on Compact Alphabets

Neil Mañibo, Dan Rust  School of Mathematics and Statistics, The Open
University,
Walton Hall, Milton Keynes, MK7 6AA, UK<EMAIL_ADDRESS><EMAIL_ADDRESS>and  James J. Walton  School of Mathematical Sciences,
University of Nottingham,
King’s Meadow Campus, Lenton Lane, Nottingham, NG7 2NR, UK
<EMAIL_ADDRESS>Fakultät für Mathematik, Universität Bielefeld,
Postfach 100131, 33501 Bielefeld, Germany<EMAIL_ADDRESS>
###### Abstract.

We develop a general theory of continuous substitutions on compact Hausdorff
alphabets. Focussing on implications of primitivity, we provide a self-
contained introduction to the topological dynamics of their subshifts. We then
reframe questions from ergodic theory in terms of spectral properties of the
corresponding substitution operator. The standard Perron–Frobenius theory in
finite dimensions is no longer applicable. To overcome this, we exploit the
theory of positive operators on Banach lattices. As an application, we
identify computable criteria that guarantee quasi-compactness of the
substitution operator and hence unique ergodicity of the associated subshift.

###### Key words and phrases:

substitutions, infinite alphabets, positive operators, quasi-compactness,
unique ergodicity

###### 2010 Mathematics Subject Classification:

37B10, 47B65, 52C23

##  1\. Introduction

Substitutions on infinite alphabets and tilings with infinite local complexity
(ILC) have been steadily gaining attention in the study of symbolic dynamics
and aperiodic order [10, 16, 19, 34, 28, 35]. Indeed, infinite alphabets must
naturally be considered when recoding non-uniformly recurrent sequences by
return words [11], or when performing the balanced-pair and overlap algorithms
for a non-Pisot substitution [21]. In the context of automatic sequences,
constant-length substitutions on infinite alphabets are the natural setting
for _regular sequences_ —sequences admitting a finitely-generated $k$-kernel
[2, Thm. 11]—as well as profinite automatic sequences e.g., those defined over
the $p$-adic integers ${\mathbb{Z}}_{p}$ [28, Sec. 4]. It has also been shown
that $(X,T)$ is a self-induced minimal Cantor system if and only if it is
conjugate to a substitution subshift on a zero-dimensional alphabet whose
substitution is primitive, recognisable and aperiodic [10, Thms. 24 and 25].

Given their ubiquity, we therefore feel it is important to develop a
comprehensive theory of such substitutions and their subshifts in terms of
their dynamics, ergodic theory and spectral theory. Notable studies in this
direction include those by Queffelec [27], Ferenczi [13], Priebe-Frank and
Sadun [16], and Durand, Ormes and Petite [10]. The aim of this work is both to
establish a framework for further study and to better understand in which ways
the infinite-alphabet landscape differs from the familiar world of finite
alphabets. One novelty of our approach is the incorporation of techniques from
the theory of positive operators on Banach lattices.

In order to begin a general study of substitutions on infinite alphabets, it
is necessary to impose some standing assumptions. We choose to focus on
alphabets equipped with a compact Hausdorff topology and insist that the
substitution is continuous on this alphabet with respect to the topology.
These assumptions are natural ones to impose so as to retain some of the
structure enjoyed in the finite alphabet setting. Interestingly, most of our
results do not require the alphabet to be equipped with a metric, generalising
the results and often making the proofs conceptually simpler.

Many of the above cited works mention the difficult problem of establishing
unique ergodicity for substitution dynamical systems in the infinite alphabet
setting. It is sometimes possible to show this for a particular example, but
finding general sufficient criteria to ensure unique ergodicity is another
matter. Beyond the constant-length setting [27, 28], very little is known. One
of the principal aims of this work is to establish the first general criterion
for unique ergodicity without requiring the substitution to have constant
length. This entails considering the substitution operator $M$ on the space
$C(\mathcal{A})$ of continuous real-valued functions on the alphabet. The
space $C(\mathcal{A})$ is a Banach lattice, allowing us to benefit from known
results on positive, mean ergodic and power convergent operators on Banach
lattices [1, 12, 22, 32, 30]. Even with the abundance of literature on such
operators, we emphasise that the infinite-dimensional situation is far from
straightforward. In particular, primitivity no longer guarantees unique
ergodicity; compare [10, Prop. 31]. Moreover, $M$ is a compact operator
essentially only when the alphabet is finite (Proposition 6.2), and hence the
classical Kreĭn–Rutman theory [24] for compact operators is not applicable.
However, similar results generalise to quasi-compact operators, where the
spectral radius is a pole of the resolvent (see [26, Thm. 4.1.4] and the
following remark). We have the following (see also Theorem 6.12):

######  Theorem 1.1.

Let $\varrho$ be a primitive substitution on a compact Hausdorff alphabet with
corresponding subshift $X_{\varrho}$ and substitution operator $M$. If $T=M/r$
is quasi-compact, then $X_{\varrho}$ is uniquely ergodic.

For large classes of examples, quasi-compactness can be verified by applying a
computable criterion detailed in Theorem 6.3. This condition appears to be
typically satisfied when the substitution is primitive and the alphabet has at
least one isolated point. More generally, in the above we require only that
$T^{n}$ is strongly power convergent (Definition 5.2) and $\varrho$ being
primitive can be weakened to each power $\varrho^{n}$ of the substitution
being irreducible (Definition 4.18). Our examples show that a range of subtle
behaviours can occur in the infinite alphabet setting: whilst some have $T$
quasi-compact and uniformly power convergent, others demonstrate that it is
not uncommon for $T$ to fail to be uniformly power convergent (Example 6.17),
even when $T$ is strongly power convergent so that the associated subshift is
uniquely ergodic.

The structure of this paper is as follows. In Section 2 we present general
properties satisfied by subshifts over compact alphabets. In Section 3 we
define notions related to substitutions and we present immediate consequences
of continuity. We also discuss the associated substitution subshift and
investigate its language. The substitution operator is introduced in Section
4, and its operator-theoretic and spectral properties are discussed. In
Theorem 4.23 we present several conditions on $\varrho$ which guarantee the
existence and uniqueness (up to scaling) of a natural length function, which
allows one to associate a geometric inflation rule to $\varrho$ which
generates tilings of ${\mathbb{R}}$. Section 5 deals with invariant measures
on the subshift and its relation to strong power convergence of the
(normalised) substitution operator $T$. Here, we exploit a correspondence
established in [16] in the fusion tiling formalism. Applications of our
results, including sufficient conditions for unique ergodicity of the subshift
and representative examples are discussed in Section 6. Section 7 deals with
asymptotic behaviour of discrepancy estimates for certain substitutions whose
corresponding operator has a spectral gap. Numerous examples are provided
throughout the text to demonstrate our results.

##  2\. Topology and dynamics

Let $\mathcal{A}$ be a compact Hausdorff space which we call an _alphabet_ and
whose elements we call _letters_. Let $\mathcal{A}^{+}=\bigsqcup_{n\geq
1}\mathcal{A}^{n}$ denote the set of all finite (non-empty) _words_ over the
alphabet $\mathcal{A}$, where $\mathcal{A}^{n}$ has the product topology and
$\mathcal{A}^{+}$ is topologised as the disjoint union. Hence
$\mathcal{A}^{n}$ is a clopen subset of $\mathcal{A}^{+}$ for each $n\geq 1$.
For ease of notation we write

$u_{1}u_{2}\cdots u_{n}\coloneqq(u_{1},u_{2},\ldots,u_{k}).$

Let
$\mathcal{A}^{\ast}=\mathcal{A}^{+}\sqcup\mathcal{A}^{0}=\mathcal{A}^{+}\sqcup\\{\varepsilon\\}$,
where $\varepsilon$ is the _empty word_. _Concatenation_ is a binary operation
$\mathcal{A}^{\ast}\times\mathcal{A}^{\ast}\to\mathcal{A}^{\ast}$ given by
$(\varepsilon,u)\mapsto u$, $(u,\varepsilon)\mapsto u$ and

$(u_{1}\cdots u_{n},v_{1}\cdots v_{m})\mapsto u_{1}\cdots u_{n}v_{1}\cdots
v_{m},$

where $u=u_{1}\cdots u_{n}\in\mathcal{A}^{n}$ and $v=v_{1}\cdots
v_{m}\in\mathcal{A}^{m}$. We write $uv$ as shorthand for the concatenation of
$u$ and $v$, which is a continuous operation. If there is a $j\geq 0$ such
that $u_{i}=v_{j+i}$ for all $1\leq i\leq n$, then we call $u$ a _subword_ of
$v$ and write $u\triangleleft v$. We have the continuous projection map
$p_{i}\colon\mathcal{A}^{n}\to\mathcal{A}$ to the $i$th letter of a word.

Let $\mathcal{A}^{{\mathbb{Z}}}$ denote the set of bi-infinite sequences over
$\mathcal{A}$ with the product topology. The space
$\mathcal{A}^{{\mathbb{Z}}}$ is compact by Tychonoff’s Theorem. We use a
vertical line $|$ to denote the position between the $-1$st and $0$th element
of a bi-infinite sequence, and so we write $w=\cdots
w_{-2}w_{-1}|w_{0}w_{1}\cdots$. For $j\leq k$, we let $w_{[j,k]}$ denote the
subword $w_{j}\cdots w_{k}$. We define the projection
$p_{[j,k]}\colon\mathcal{A}^{\mathbb{Z}}\to\mathcal{A}^{k-j+1}$ by
$p_{[j,k]}(w)=w_{[j,k]}$. This is also clearly a continuous function.

The function
$\sigma\colon\mathcal{A}^{{\mathbb{Z}}}\to\mathcal{A}^{{\mathbb{Z}}}$ given by
$\sigma(x)_{i}=x_{i+1}$ is a homeomorphism and we call $\sigma$ the _(left)
shift_ map. The pair $(\mathcal{A}^{{\mathbb{Z}}},\sigma)$ is called the _full
shift_ over the alphabet $\mathcal{A}$. Let
$|\cdot|\colon\mathcal{A}^{*}\to{\mathbb{N}}_{0}={\mathbb{N}}\cup\\{0\\}$ be
the _length function_ mapping $u\mapsto n$ for every $u\in\mathcal{A}^{n}$.
The length function is continuous because
$|\cdot|^{-1}(\\{n\\})=\left\\{u\in\mathcal{A}^{*}\mid|u|=n\right\\}=\mathcal{A}^{n}$
is open in $\mathcal{A}^{\ast}$ for every $n$.

######  Definition 2.1.

Let $X\subseteq\mathcal{A}^{\mathbb{Z}}$. If $\sigma(X)=X$ then we say $X$ is
_shift-invariant_ or _$\sigma$ -invariant_. If $X$ is a non-empty, closed,
shift-invariant subspace of $\mathcal{A}^{\mathbb{Z}}$ then we call $X$ a
_subshift_. We call $X$ a _minimal_ subshift if $X$ contains no proper
subshift $\varnothing\neq Y\subsetneq X$.

######  Definition 2.2.

Let $\mathcal{L}\subseteq\mathcal{A}^{\ast}$. We let
$\mathcal{L}^{n}=\mathcal{L}\cap\mathcal{A}^{n}$ and
$\mathcal{L}^{+}=\mathcal{L}\cap\mathcal{A}^{+}$. We call $\mathcal{L}$ a
_language_ if each $\mathcal{L}^{n}\subseteq\mathcal{A}^{n}$ is non-empty,
closed (equivalently, $\mathcal{L}\subseteq\mathcal{A}^{\ast}$ is closed), and
$\mathcal{L}$ is closed under taking subwords. The _subshift associated with
$\mathcal{L}$_ is the subset

$X_{\mathcal{L}}\coloneqq\\{\mathcal{A}^{\mathbb{Z}}\mid
w_{[j,k]}\in\mathcal{L}\text{ for all }j\leq k\\}.$

######  Proposition 2.3.

For any language $\mathcal{L}$, we have that $X_{\mathcal{L}}$ is a subshift.

###### Proof.

It is clear that $X_{\mathcal{L}}$ is shift-invariant since the property of a
subword being in the language is invariant under the left and right shift.
Given $j\leq k$, we define $X_{[j,k]}\subseteq\mathcal{A}^{\mathbb{Z}}$ by

$X_{[j,k]}\coloneqq\\{w\in\mathcal{A}^{\mathbb{Z}}\mid
w_{[j,k]}\in\mathcal{L}\\}.$

Equivalently, $X_{[j,k]}=p_{[j,k]}^{-1}(\mathcal{L}^{n})$, where $n=k-j+1$.
Since $\mathcal{L}^{n}$ is closed it follows from continuity that each
$X_{[j,k]}$ is also closed, and hence compact. Since
$\mathcal{L}^{n}\neq\varnothing$ we also have that $X_{[j,k]}\neq\varnothing$,
since we can extend any word of $\mathcal{L}^{n}$ to the left and right
arbitrarily (for example, by repeating an arbitrary $a\in\mathcal{A}$) to
obtain to an infinite word in $X_{[j,k]}$. Since

$X_{\mathcal{L}}=\bigcap_{n\in{\mathbb{N}}}X_{[-n,n]},$

it follows that $X_{\mathcal{L}}$ is closed in $\mathcal{A}^{\mathbb{Z}}$.
This is a nested intersection since $\mathcal{L}$ is closed under taking
subwords, so $X_{\mathcal{L}}$ is non-empty by Cantor’s Intersection Theorem.
∎

######  Definition 2.4.

Let $w\in\mathcal{A}^{\mathbb{Z}}$ and let
$\operatorname{orb}(w)\coloneqq\\{\sigma^{n}(w)\mid n\in{\mathbb{Z}}\\}$
denote the orbit of $w$ under the shift map $\sigma$. We let
$X_{w}\coloneqq\overline{\operatorname{orb}(w)}\subseteq\mathcal{A}^{\mathbb{Z}}$
denote the _orbit closure_ of $w$. Let $\mathcal{W}^{n}(w)$ denote the set of
all $n$-letter subwords appearing in $w$. We write
$\mathcal{W}(w)\coloneqq\bigsqcup_{n\geq 0}\mathcal{W}^{n}(w)$, seen as a
subspace of $\mathcal{A}^{\ast}$. We define
$\mathcal{L}^{n}(w)=\overline{\mathcal{W}^{n}(w)}$ and similarly the
_language_ of $w$ as $\mathcal{L}(w)=\overline{\mathcal{W}(w)}$.

######  Remark 2.5.

Of course, we have that

$\mathcal{L}(w)=\bigsqcup_{n\geq 0}\mathcal{L}^{n}(w)$

and $\mathcal{L}^{n}(w)=\mathcal{L}(w)\cap\mathcal{A}^{n}$, since each of the
$\mathcal{A}^{n}$ are disjoint clopen subsets of $\mathcal{A}^{\ast}$.
$\Diamond$

######  Definition 2.6.

For a subshift $X\subseteq\mathcal{A}^{\mathbb{Z}}$ we let
$\mathcal{L}^{n}(X)$ denote the set of all $n$-letter subwords appearing in
elements of $X$, that is, $\mathcal{L}^{0}(X)=\\{\varepsilon\\}$ and

$\mathcal{L}^{n}(X)\coloneqq\left\\{u\in\mathcal{A}^{n}\mid\exists w\in
X,\>\>j\leq k\ \text{ such that }\ u=w_{[j,k]}\right\\}.$

We write $\mathcal{L}(X)\coloneqq\bigsqcup_{n\geq 0}\mathcal{L}^{n}(X)$, seen
as a subspace of $\mathcal{A}^{\ast}$, and call $\mathcal{L}(X)$ the
_language_ of $X$.

######  Proposition 2.7.

If $w\in\mathcal{A}^{\mathbb{Z}}$ then $\mathcal{L}(w)$ is a language and, for
a subshift $X\subseteq\mathcal{A}^{\mathbb{Z}}$, we have that $\mathcal{L}(X)$
is a language.

###### Proof.

Let us write $\mathcal{W}^{n}(w)=\mathcal{W}^{n}$ and
$\mathcal{L}^{n}(w)=\mathcal{L}^{n}$. Clearly each
$\mathcal{W}^{n}\neq\varnothing$, so by definition each $\mathcal{L}^{n}$ is
closed and non-empty. Let $n<m$, $0\leq i\leq m-n$ be arbitrary and let
$p\colon\mathcal{A}^{m}\to\mathcal{A}^{n}$ denote the projection to the $i$th
subword of length $n$. Then $p(\mathcal{W}^{m})\subseteq\mathcal{W}^{n}$ since
if an $m$-letter word appears in $w$ then so does any $n$-letter subword.
Moreover $p$ is continuous (and closed by compactness) and thus

$p(\mathcal{L}^{m})=p(\overline{\mathcal{W}^{m}})=\overline{p(\mathcal{W}^{m})}=\overline{\mathcal{W}^{n}}=\mathcal{L}^{n},$

so the $i$th $n$-letter subword of an $m$-letter legal word is still legal and
thus $\mathcal{L}(w)$ is a language.

Given a subshift $X$, note that $\mathcal{L}^{0}(X)=\\{\varepsilon\\}$ and
$\mathcal{L}^{n}=p_{[1,n]}(X)$ for $n\geq 1$ by shift-invariance. It follows
from $X\neq\varnothing$ that $\mathcal{L}^{n}(X)\neq\varnothing$ and, from
compactness of $X$ and continuity of $p_{[1,n]}$, that $\mathcal{L}^{n}(X)$ is
closed. Closure under taking subwords is clear. ∎

######  Proposition 2.8.

For $w\in\mathcal{A}^{\mathbb{Z}}$ we have that $X_{w}$ is a subshift with
$\mathcal{L}(X_{w})=\mathcal{L}(w)$.

###### Proof.

As $w\in X_{w}$ and $X_{w}$ is an orbit closure, it is clearly a non-empty,
closed subspace of $\mathcal{A}^{\mathbb{Z}}$. Let $x\in X_{w}$. So, for all
open sets $U\subseteq\mathcal{A}^{\mathbb{Z}}$ containing $x$,
$U\cap\operatorname{orb}(w)$ is non-empty. Let
$V\subseteq\mathcal{A}^{\mathbb{Z}}$ be an open set containing $\sigma(x)$.
Then, as $\sigma$ is a homeomorphism, $\sigma^{-1}(V)$ is open and contains
$x$ and so $\sigma^{-1}(V)\cap\operatorname{orb}(w)\neq\varnothing$. Hence
$V\cap\operatorname{orb}(w)=V\cap\sigma(\operatorname{orb}(w))\neq\varnothing$.
Since $V$ was arbitrary, $\sigma(x)$ is in the closure of
$\operatorname{orb}(w)$. An analogous argument similarly shows that
$\sigma^{-1}(x)\in X_{w}$ and thus $X_{w}$ is shift-invariant, as required.

The function $p_{[1,n]}\colon\mathcal{A}^{\mathbb{Z}}\to\mathcal{A}^{n}$ is
continuous and so

$\mathcal{L}^{n}(X_{w})\stackrel{{\scriptstyle
a}}{{=}}p_{[1,n]}(X_{w})=p_{[1,n]}\left(\overline{\operatorname{orb}(w)}\right)\stackrel{{\scriptstyle
b}}{{=}}\overline{p_{[1,n]}\left(\operatorname{orb}(w)\right)}=\overline{\mathcal{W}^{n}(w)}=\mathcal{L}^{n}(w),$

where the equality at $a$ is due to the shift-invariance of $X_{w}$, and the
equality at $b$ is due to continuity of $p_{[1,n]}$ and compactness of
$\mathcal{A}^{\mathbb{Z}}$. Since $\mathcal{L}^{n}(X_{w})=\mathcal{L}^{n}(w)$
for all $n$ we have that $\mathcal{L}(X_{w})=\mathcal{L}(w)$ (see Remark 2.5).
∎

######  Remark 2.9.

We will always assume, without loss of generality, that all letters of
$\mathcal{A}$ appear in some word of a subshift $X$. Indeed, by shift-
invariance, the set of all letters which appear is given by
$\mathcal{L}^{1}(X)=p_{0}(X)\subseteq\mathcal{A}$. Since
$X\subseteq\mathcal{A}^{\mathbb{Z}}$ is closed, we have that $X$ is compact
and thus so is $\mathcal{L}^{1}(X)$ by continuity of $p_{0}$. So we may assume
that all letters appear by restricting the alphabet to $\mathcal{L}^{1}(X)$,
which is still compact and Hausdorff.  $\Diamond$

Recall that a topological dynamical system $(X,f)$ is called _topologically
transitive_ if for all non-empty open sets $U,V\subseteq X$, there exists an
$n\in{\mathbb{Z}}$ such that $f^{n}(U)\cap V\neq\varnothing$.

######  Lemma 2.10.

Let $X\subseteq\mathcal{A}^{\mathbb{Z}}$ be a subshift. If there exists an
element $w\in X$ with a dense orbit, then the subshift $X$ is topologically
transitive.

###### Proof.

Let $w\in X$ be a point with a dense orbit. Let $U,V$ be open subsets of $X$.
Let $n$, $m$ be such that $\sigma^{n}(w)\in U$ and $\sigma^{m}(w)\in V$. Then
$\sigma^{m}(w)=\sigma^{m-n}(\sigma^{n}(w))\in\sigma^{m-n}(U)$ and so
$\sigma^{m-n}(U)\cap V\neq\varnothing$. Hence, $X$ is topologically
transitive. ∎

######  Lemma 2.11.

Let $X\subseteq\mathcal{A}^{\mathbb{Z}}$ be a subshift. If there exists an
element $w\in X$ with dense orbit then $\mathcal{A}$ is separable.

###### Proof.

Define $O\coloneqq\\{p_{i}(w)\mid
i\in{\mathbb{Z}}\\}=p_{0}(\operatorname{orb}(w))$. Let $U\subseteq\mathcal{A}$
be an arbitrary, non-empty open subset. The corresponding cylinder subset
$C\subseteq X$ of words $z$ with $p_{0}(z)\in U$ is open (by the definition of
the product topology on $\mathcal{A}^{\mathbb{Z}}$). Moreover, by Remark 2.9
we have that $C\neq\varnothing$. By density of $\operatorname{orb}(w)$ it
follows that $\operatorname{orb}(w)\cap C\neq\varnothing$, equivalently
$p_{i}(w)\in U$ for some $i$, hence $O\cap U\neq\varnothing$. Since $O$ is
countable and $U$ was an arbitrary open subset, it follows that $\mathcal{A}$
is separable. ∎

Since $X$ is compact Hausdorff, by the Baire Category Theorem we have that $X$
is Baire and thus second category. Thus (by an identical proof to [33, Prop.
1.1]) we have a converse to Lemma 2.10:

######  Proposition 2.12.

Let $X\subseteq\mathcal{A}^{\mathbb{Z}}$ be a subshift. There exists an
element $w\in X$ with a dense orbit if and only if the subshift $X$ is
topologically transitive and $\mathcal{A}$ is separable. ∎

######  Definition 2.13.

Let $w\in\mathcal{A}^{\mathbb{Z}}$ be a bi-infinite sequence over
$\mathcal{A}$. We say that $w$ is _repetitive_ if for all $n\geq 1$ and every
non-empty open set $U\subseteq\mathcal{L}^{n}(w)$, there exists $N=N(n,U)\geq
1$ such every $v\in\mathcal{L}^{N}(w)$ contains a subword in $U$.

The above definition may be interpreted as saying that any given finite word
appears, up to some specified tolerance (determined by the open set $U$), with
uniformly bounded gaps (within any word of size $N$). The lemma below
(properties 2 and 3) says that this is equivalent, for any given tolerance, to
_all_ $n$-letter words being found in all $N$-letter words, for some $N$
depending on the tolerance. Note that here, and elsewhere, we shall always
assume that all elements of open covers are non-empty.

######  Proposition 2.14.

Let $w\in\mathcal{A}^{\mathbb{Z}}$ be a bi-infinite sequence over
$\mathcal{A}$ and let us write $\mathcal{L}^{n}=\mathcal{L}^{n}(w)$. The
following are equivalent:

  1. (1)

$w$ is repetitive;

  2. (2)

for all $n\geq 1$ and every finite open cover
$\mathcal{U}=\\{U_{i}\\}_{i=1}^{\ell}$ of $\mathcal{L}^{n}$, there exists an
$N=N(n,\mathcal{U})\geq 1$ such that for all $v\in\mathcal{L}^{N}$ and for
every $1\leq i\leq\ell$, there is a subword of $v$ in $U_{i}$;

  3. (3)

for all $n\geq 1$ and every open subset
$U\subseteq\mathcal{L}^{n}\times\mathcal{L}^{n}$ containing the diagonal,
there exists some $N=N(n,U)\geq 1$ so that, for every $u\in\mathcal{L}^{n}$
and $v\in\mathcal{L}^{N}$, there is a subword $u^{\prime}\triangleleft v$ with
$(u,u^{\prime})\in U$.

###### Proof.

($1\implies 2$): Let $n\geq 1$ be given and $\\{U_{1},\ldots,U_{\ell}\\}$ be a
finite open cover of $\mathcal{L}^{n}$. By repetitivity, for each $1\leq
i\leq\ell$, let $N_{i}$ be such that for all $u\in\mathcal{L}^{N_{i}}$, there
is a subword of $u$ in $U_{i}$. Let
$N\coloneqq\max\\{N_{1},\ldots,N_{\ell}\\}$ be the maximum of these lengths.
Then, for all $v\in\mathcal{L}^{N}(X_{w})$ and for every $1\leq i\leq\ell$,
there is a subword of $u$ in $U_{i}$.

($2\implies 3$): Let $U\subseteq\mathcal{L}^{n}\times\mathcal{L}^{n}$ be open
and contain the diagonal. It is well known (and not hard to prove) that, by
compactness, we may find $V\subseteq\mathcal{L}^{n}\times\mathcal{L}^{n}$
satisfying the same, with $V=V^{-1}$ (where $V^{-1}$ consists of pairs
$(x,y)$, for $(y,x)\in V$) and $V\circ V\subseteq U$ (where $(u,w)\in V\circ
V$ if there is some $(u,v)\in V$ and $(v,w)\in V$).

For $u\in\mathcal{L}^{n}$ let $V_{u}\subseteq\mathcal{L}^{n}$ denote the set
of $u^{\prime}\in\mathcal{L}^{n}$ with $(u,u^{\prime})\in V$. Then
$\\{V_{u}\\}_{u\in\mathcal{A}}$ provides an open cover of $\mathcal{L}^{n}$.
By compactness we may restrict this to a finite subcover
$\\{V_{u_{i}}\\}_{i=1}^{\ell}$. Take $N\geq 1$ according to property 2 for
this open cover. Let $u\in\mathcal{L}^{n}$ and $v\in\mathcal{L}^{N}$ be
arbitrary and $i$ such that $u\in V_{u_{i}}$. Hence, $(u,u_{i})\in V$, by
symmetry of $V$. By property 2, we may find some $u^{\prime}\in V_{u_{i}}$
with $u^{\prime}\triangleleft v$. Then $(u_{i},u^{\prime})\in V$ so
$(u,u_{i})\circ(u_{i},u^{\prime})=(u,u^{\prime})\in V\circ V\subseteq U$, as
required.

($3\implies 1$): Let $U\subseteq\mathcal{L}^{n}$ be an arbitrary open subset
and $u\in U$ be arbitrary. Let $C=\mathcal{L}^{n}\setminus U$ and consider the
closed subset $C^{\prime}=\\{u\\}\times
C\subseteq\mathcal{L}^{n}\times\mathcal{L}^{n}$. Then
$V=\mathcal{L}^{n}\times\mathcal{L}^{n}\setminus C^{\prime}$ is open and
contains the diagonal. Take $N$ according to property 3 and let
$v\in\mathcal{L}^{N}$ be arbitrary. Then by property 3, there is some
$u^{\prime}\in\mathcal{L}^{n}$ so that $(u,u^{\prime})\in V$ and with
$u^{\prime}\triangleleft v$. But $(u,u^{\prime})\in V$ if and only if
$u^{\prime}\in U$, as required. ∎

######  Remark 2.15.

An alternative characterisation to the above is via open covers of
$\mathcal{A}$ (rather than of $\mathcal{L}^{n}$), or open sets containing the
diagonal in $\mathcal{A}\times\mathcal{A}$, by comparing words letter-by-
letter to define the ‘tolerance’.

In this case, property 3 is easy to interpret when $\mathcal{A}$ has a metric
$d$. Then we can take as $U$ the pairs of words $(u,u^{\prime})$ so that
$d(u_{i},u_{i}^{\prime})<\epsilon$ for each pair of letters
$u_{i}\triangleleft u$ and $u_{i}^{\prime}\triangleleft u^{\prime}$. The
property then says: for every $n\geq 1$ and $\epsilon>0$ there is some
$N=N(n,\epsilon)\geq 1$ so that, for every $u\in\mathcal{L}^{n}$ and
$v\in\mathcal{L}^{N}$, there is some subword $u^{\prime}\triangleleft v$ with
$d(u,u^{\prime})<\epsilon$. This definition in the metric setting has appeared
previously, for instance in the work of Frettlöh and Richard [19].  $\Diamond$

The following is well known for general topological dynamical systems [20,
Rem. 2.12] and so we state it without proof.

######  Proposition 2.16.

Let $X\subseteq\mathcal{A}^{\mathbb{Z}}$ be a subshift. The subshift $X$ is
minimal if and only if every element $w\in X$ has a dense orbit. ∎

######  Lemma 2.17.

Let $X\subseteq\mathcal{A}^{\mathbb{Z}}$ be a subshift. If $X$ is minimal then
every $w\in X$ has the same language and is repetitive, with the same value of
$N=N(n,U)$ for each $n\geq 1$ and non-empty open set
$U\subseteq\mathcal{L}^{n}(w)$.

###### Proof.

Since $X$ is minimal we have that $X=X_{w}$ for each $w\in X$, since each $w$
has dense orbit by Proposition 2.16, and in particular
$\mathcal{L}^{n}(w)=\mathcal{L}^{n}(X_{w})=\mathcal{L}^{n}(X)$ for all $n\geq
1$, by Proposition 2.8. Since repetitivity only depends on this language, we
may work instead with $\mathcal{L}^{n}(X)$ and thus all $w\in X$
simultaneously.

Let $U\subseteq\mathcal{L}^{n}(X)$ be non-empty and open. Let $V_{j}\coloneqq
p^{-1}_{[j,j+n-1]}(U)$, i.e., the elements of the shift whose $n$-letter word
at position $j$ belongs to $U$. By continuity of $p_{[j,j+n-1]}$, each $V_{j}$
is open. By definition, $\sigma(V_{j})=V_{j-1}$. Since each $x\in X$ has dense
orbit, it follows that $x\in V_{j}$ for some $j$ and thus $\\{V_{j}\mid
j\in{\mathbb{Z}}\\}$ is an open cover of $X$. By compactness of $X$, let
$\mathcal{V}\coloneqq\\{V_{j_{1}},\ldots,V_{j_{\ell}}\\}$ be a finite subcover
and $N\coloneqq\max\\{|j_{i}|\mid 1\leq i\leq\ell\\}+(n-1)$.

Let $v\in\mathcal{L}^{2N+1}(X)$ and $y\in X$ be such that $p_{[-N,N]}(y)=v$.
For some $i$, we have $y\in V_{j_{i}}$ because $\mathcal{V}$ is a cover of
$X$. It follows that $u\coloneqq p_{[j_{i},j_{i}+n-1]}(y)\in U$. As
$|j_{i}|,|j_{i}+n-1|\leq N$, we see that $u$ is a subword of $v$, as required.
∎

######  Lemma 2.18.

If $w\in\mathcal{A}^{\mathbb{Z}}$ is repetitive, then $X_{w}$ is minimal.

###### Proof.

Let $Y\neq\varnothing$ be a closed, shift-invariant subset of $X_{w}$. For
$n\geq 1$, define the set
$U_{n}\coloneqq\mathcal{L}^{n}(X_{w})\setminus\mathcal{L}^{n}(Y)$, which is
open. Suppose that $U_{n}\neq\varnothing$. By repetitivity of $w$, there is
some $N$ such that for every $v\in\mathcal{L}^{N}(X_{w})$, there is some
$u\triangleleft v$ with $u\in U_{n}$. In particular, take any
$v\in\mathcal{L}^{N}(Y)\subseteq\mathcal{L}^{N}(X_{w})$. Then, since
$u\triangleleft v$, we have that $u\in\mathcal{L}^{n}(Y)\cap U_{n}$, which is
a contradiction. It follows that each $U_{n}$ is empty. But then
$\mathcal{L}^{n}(X_{w})=\mathcal{L}^{n}(Y)$ for all $n\geq 1$. Since subshifts
are determined by their language, it follows that $Y=X_{w}$ and thus $X_{w}$
is minimal. ∎

Putting together Proposition 2.16, Lemma 2.17 and Lemma 2.18 gives us the
following.

######  Corollary 2.19.

Let $w\in\mathcal{A}^{\mathbb{Z}}$. The following are equivalent:

  1. (1)

$X_{w}$ is minimal;

  2. (2)

every element $x\in X_{w}$ has a dense orbit;

  3. (3)

$w$ is repetitive;

  4. (4)

every element $x\in X_{w}$ is repetitive.

##  3\. Substitutions

Our main focus will be on subshifts coming from substitutions, to which we now
turn. The theory of substitutions on finite alphabets is well developed [4,
14, 27], and the reader is encouraged to familiarise themselves with that
setting in order to compare and contrast our results with the classical
theory. Where appropriate, we highlight these differences and subtleties.

######  Definition 3.1.

Let $\varrho\colon\mathcal{A}\to\mathcal{A}^{+}$ be a continuous function. We
call such a function a _substitution_ on $\mathcal{A}$. We say $\varrho$ is a
substitution of _constant length_ $n$ if
$\varrho(\mathcal{A})\subseteq\mathcal{A}^{n}$.

To give an idea of the variety of substitutions that satisfy this general
definition, consider the following examples on infinite alphabets:

######  Example 3.2.

Take $\mathcal{A}={\mathbb{N}}_{\infty}={\mathbb{N}}_{0}\cup\\{\infty\\}$, the
one point compactification of the natural numbers ${\mathbb{N}}_{0}$, with the
substitution $\varrho\colon\mathcal{A}\to\mathcal{A}^{+}$ given by

$\varrho\colon\left\\{\begin{array}[]{rl}0\ \mapsto&0\ 0\ 0\ 1\\\ n\
\mapsto&0\ n\\!-\\!1\ n\\!+\\!1\\\ \infty\ \mapsto&0\ \infty\
\infty.\end{array}\right.$

$\Diamond$

######  Example 3.3.

Take $\mathcal{A}=S^{1}=\\{z\in{\mathbb{C}}\mid|z|=1\\}$ as the the unit
circle in the complex numbers, with substitution
$\varrho\colon\mathcal{A}\to\mathcal{A}^{+}$

$\varrho\colon z\mapsto z\ \alpha z$

for a fixed $\alpha\in\mathcal{A}$.  $\Diamond$

######  Example 3.4.

For an iterated function system $\\{f_{1},\ldots,f_{d}\\}$ on a space $X$ with
attractor $Y$, let $\mathcal{A}=Y$, with the substitution
$\varrho\colon\mathcal{A}\to\mathcal{A}^{+}$ given by

$\varrho\colon a\mapsto f_{w_{1}(a)}(a)\ \cdots\ f_{w_{k}(a)}(a),$

where the word $w_{1}(a)\cdots w_{k}(a)\in\\{1,\ldots,d\\}^{+}$ is locally
constant on $Y$.  $\Diamond$

The second example above is a constant-length substitution because
$|\varrho(z)|=2$ for all $z\in\mathcal{A}$. In fact, we shall see that we have
no choice but to make the substitution constant-length when the alphabet
$\mathcal{A}=S^{1}$. The next result shows that topological properties of the
alphabet, namely connectedness, can heavily restrict properties of the
associated substitutions. We see also that, even though our alphabets are
potentially infinite, continuity of the substitution and compactness of the
alphabet ensure that the images of letters under substitution are uniformly
bounded in length.

######  Proposition 3.5.

Let $\varrho\colon\mathcal{A}\to\mathcal{A}^{+}$ be a substitution. There
exists $k\geq 1$ such that for all $a\in\mathcal{A}$, $|\varrho(a)|\leq k$. If
the alphabet $\mathcal{A}$ is connected, then
$\varrho\colon\mathcal{A}\to\mathcal{A}^{+}$ is constant-length.

###### Proof.

The function $|\cdot|\circ\varrho\colon\mathcal{A}\to{\mathbb{N}}$ is
continuous as it is the composition of two continuous functions. It follows
that $|\varrho(\mathcal{A})|$ is compact by the compactness of $\mathcal{A}$
and so is bounded. If $\mathcal{A}$ is connected, then so is
$|\varrho(\mathcal{A})|$ and hence there exists an $n\geq 1$ such that for all
$a\in\mathcal{A}$, $|\varrho(a)|=n$. ∎

Similarly, a substitution is of course constant-length on any connected subset
of the alphabet. Given Proposition 3.5, we may define the _length_ of a
substitution by
$\displaystyle|\varrho|\coloneqq\max_{a\in\mathcal{A}}|\varrho(a)|\in{\mathbb{N}}$.

It is often the case that checking continuity of a substitution is easier if
one can do it component-wise. Indeed, Durand, Ormes and Petite gave an
alternative definition of a substitution [10] (there called a _generalised
substitution_), which we show to be equivalent to ours. Recall that
$p_{i}\colon\mathcal{A}^{n}\to\mathcal{A}$ is the canonical projection
function onto the $i$th component of the product $\mathcal{A}^{n}$.

######  Proposition 3.6.

A function $\varrho\colon\mathcal{A}\to\mathcal{A}^{+}$ is continuous if and
only if for every $n\geq 1$ the subspace
$\varrho^{-1}(\mathcal{A}^{n})\subseteq\mathcal{A}$ is open, and for every
$1\leq i\leq n$, the composition of functions
$p_{i}\circ\varrho\colon\varrho^{-1}(\mathcal{A}^{n})\to\mathcal{A}$ is
continuous.

###### Proof.

Suppose that $\varrho\colon\mathcal{A}\to\mathcal{A}^{+}$ is continuous. As
$\mathcal{A}^{n}$ is an open subset of $\mathcal{A}^{+}$, and $\varrho$ is
continuous, it follows that $\varrho^{-1}(\mathcal{A}^{n})$ is open in
$\mathcal{A}$. Then, as $p_{i}$ is continuous for every $1\leq i\leq n$, and
restricting continuous functions to subspaces preserves continuity, it follows
that $p_{i}\circ\varrho\colon\varrho^{-1}(\mathcal{A}^{n})\to\mathcal{A}$ is
continuous.

For the other direction, it is enough to show that

$\varrho|_{\varrho^{-1}(\mathcal{A}^{n})}\colon\varrho^{-1}(\mathcal{A}^{n})\to\mathcal{A}^{+}$

is continuous for every $n\geq 1$, as the (disjoint) sets
$\varrho^{-1}(\mathcal{A}^{n})$ are open in $\mathcal{A}$. For any particular
$n$, the universal property of products says that
$\varrho|_{\varrho^{-1}(\mathcal{A}^{n})}$ is continuous if and only if
$p_{i}\circ\varrho\colon\varrho^{-1}(\mathcal{A}^{n})\to\mathcal{A}$ is
continuous for every $1\leq i\leq n$ and so we are done. ∎

By Proposition 3.5, one is then only required to check the compositions
$p_{i}\circ\varrho$ for a finite number of the subalphabets
$\varrho^{-1}(\mathcal{A}^{n})$ in order to confirm continuity of $\varrho$.

A substitution naturally extends to a continuous function
$\varrho\colon\mathcal{A}^{\ast}\to\mathcal{A}^{\ast}$. We define
$\varrho(\varepsilon)\coloneqq\varepsilon$ and for $u=u_{1}\cdots
u_{n}\in\mathcal{A}^{n}\subseteq\mathcal{A}^{+}$, we define

$\varrho(u)\coloneqq\varrho(u_{1})\cdots\varrho(u_{n})$

by concatenation. Since $\varrho\colon\mathcal{A}^{*}\to\mathcal{A}^{*}$ has
the same domain and codomain it may be iterated. By continuity of $\varrho$,
all iterates $\varrho^{k}$ for $k\in{\mathbb{N}}$ are also continuous and so
are also substitutions. We call words of the form $\varrho^{k}(a)$ level-$k$
_supertiles_.

######  Definition 3.7.

Let $\varrho\colon\mathcal{A}\to\mathcal{A}^{+}$ be a substitution. We say a
word $u\in\mathcal{A}^{n}$ is _generated_ by $\varrho$ if there exist
$a\in\mathcal{A}$, $k\geq 0$ such that $\varrho^{k}(a)$ contains $u$ as a
subword. The _language_ of $\varrho$ is

$\mathcal{L}(\varrho)=\overline{\\{u\in\mathcal{A}^{\ast}\mid u\text{ is
generated by }\varrho\\}}.$

and we call words in $\mathcal{L}(\varrho)$ _legal_. The legal words of length
$n$ are denoted by $\mathcal{L}^{n}(\varrho)$. The _subshift associated with
$\varrho$_ is $X_{\varrho}\coloneqq X_{\mathcal{L}(\varrho)}$.

Note that the language includes closure points of words generated by
$\varrho$. If closure points were not included, then the following proposition
stating that $X_{\varrho}$ is a subshift would fail.

######  Proposition 3.8.

Let $\varrho\colon\mathcal{A}\to\mathcal{A}^{+}$ be a substitution which
generates arbitrarily large words. The associated space
$X_{\varrho}\subseteq\mathcal{A}^{\mathbb{Z}}$ is a subshift. Conversely, if
for all $a\in\mathcal{A}$ and some $k\geq 1$, we have that
$|\varrho^{n}(a)|<k$ for all $n\in{\mathbb{N}}$, then
$X_{\varrho}=\varnothing$.

###### Proof.

If $|\varrho^{n}(a)|<k$ for all $a\in\mathcal{A}$ and $n\in{\mathbb{N}}$ then
$\mathcal{L}^{k}(\varrho)=\varnothing$ and hence $X_{\varrho}=\varnothing$. So
suppose that $\varrho$ generates arbitrarily large words. Then
$\mathcal{L}^{n}(\varrho)\neq\varnothing$ for all $n\in{\mathbb{N}}$, and is
closed by definition. Clearly any subword or a word generated by $\varrho$ is
still generated by $\varrho$, so by a continuity argument similar to the proof
of Proposition 2.7, subwords of legal words are legal. Hence,
$\mathcal{L}(\varrho)$ is a language. Then $X_{\varrho}$ is a subshift by
Proposition 2.3. ∎

######  Corollary 3.9.

Let $\varrho\colon\mathcal{A}\to\mathcal{A}^{+}$ be a substitution with
associated subshift $X_{\varrho}$. If there exists a letter $a\in\mathcal{A}$
such that $\lim_{n\to\infty}|\varrho^{n}(a)|=\infty$, then the subshift
$X_{\varrho}$ is non-empty.

One might expect the converse of the above to hold by some compactness
argument; it of course holds for finite or connected alphabets $\mathcal{A}$.
However, it is possible to engineer an example where this is not the case:

######  Example 3.10.

Let $\mathcal{A}={\mathbb{N}}_{\infty}\times{\mathbb{N}}_{\infty}$ where
${\mathbb{N}}_{\infty}={\mathbb{N}}_{0}\cup\\{\infty\\}$ is the one-point
compactification of ${\mathbb{N}}_{0}$. Define a substitution
$\varrho\colon\mathcal{A}\to\mathcal{A}^{+}$ by

$\varrho(n,m)=\begin{cases}(0,0),&\text{if }n=0,m=0,\\\ (n,m-1),&\text{if
}m>0,\\\ (n-1,n)(0,n),&\text{if }n>0\text{ and }m=0,\\\ \end{cases}$

where $\infty-1\coloneqq\infty$.

By Proposition 3.6, $\varrho$ is continuous. One quickly sees that

$\begin{array}[]{lcll}{\displaystyle\lim_{i\to\infty}\varrho^{i}(n,m)}&=&(0,0)^{n+1}&\text{
if }n,m\neq\infty;\\\
{\displaystyle\lim_{i\to\infty}\varrho^{i}(\infty,m)}&=&(\infty,\infty)(0,\infty)&\text{
if }m\neq\infty;\\\
{\displaystyle\lim_{i\to\infty}\varrho^{i}(n,\infty)}&=&(n,\infty).&\end{array}$

For every $k\in{\mathbb{N}}$, the letter $(k,0)$ eventually grows to length
$k+1$ under iterated substitution, meaning that $X_{\varrho}$ is non-empty by
Proposition 3.8. In fact,

$X_{\varrho}=\\{\cdots(0,0)(0,0)|(0,0)(0,0)\cdots\\}.$

However, every letter is eventually constant under substitution, so no letter
grows without bound.  $\Diamond$

######  Example 3.11.

It may be that not all letters of $\mathcal{A}$ appear in
$X_{\varrho}=X(\mathcal{L}(\varrho))$, even if $\\#\mathcal{A}<\infty$ and the
alphabet cannot be reduced to give the same subshift. Indeed, consider the
substitution

$\varrho\colon\begin{cases}a\mapsto a,\\\ b\mapsto ab.\end{cases}$

It is easy to see that $\mathcal{L}(\varrho)=\\{a^{n},a^{n}b\mid
n\in{\mathbb{N}}_{0}\\}$. The only bi-infinite element generated by this
language is the periodic word containing only $a$, and the substitution cannot
be restricted to a smaller alphabet which gives the same.

We see that $\mathcal{L}(X_{\varrho})=\\{\varepsilon,a^{n}\mid
n\in{\mathbb{N}}_{0}\\}$ and (as also for the previous example) it is possible
for $\mathcal{L}(X_{\varrho})\subseteq\mathcal{L}(\varrho)$ to be a strict
inclusion. However, for the sufficiently well behaved substitutions of main
interest here (such as primitive substitutions, but also see Proposition 3.16)
the full language, and in particular the full alphabet, is realised by
$X_{\varrho}$.  $\Diamond$

######  Remark 3.12.

For $U\subseteq\mathcal{A}$, let $s(U)$ be the set of letters in substitutes
of elements of $U$. So,

$s(U)\coloneqq\\{a\triangleleft\varrho(u)\mid u\in U,a\in\mathcal{A}\\}.$

One may always restrict to a _letter surjective_ substitution, in the sense
that $\mathcal{A}=s(\mathcal{A})$. Indeed, otherwise, consider the eventual
range

$\mathcal{B}=\bigcap_{n\in{\mathbb{N}}}s^{n}(\mathcal{A}).$

This is a nested intersection of non-empty compact sets and thus
$\mathcal{B}\neq\varnothing$. Since $s(\mathcal{B})=\mathcal{B}$, the
substitution is well defined and letter surjective on $\mathcal{B}$. All
elements of the shift $X_{\varrho}$ contain only letters in $\mathcal{B}$.
Indeed, let $a\triangleleft w\in X_{\varrho}$ for $a\in\mathcal{A}$ and let
$Y_{n}$ be the set of words of length $n$ generated by $\varrho$. Since
$a\triangleleft v$ for $v\in\mathcal{L}(\varrho)$ and $v$ arbitrarily large,
we have that $a\triangleleft v\in\overline{Y_{n}}$ for $n$ arbitrarily large.
Since the length of the substitution is bounded (Proposition 3.5) we have that
all letters of $Y_{n}$ are in $s^{k}(\mathcal{A})$, where $k$ can be made
arbitrarily large by choosing $n$ sufficiently large. It follows that
$a\in\overline{s^{k}(\mathcal{A})}=s^{k}(\mathcal{A})$ for $k$ arbitrarily
large and hence $a\in\mathcal{B}$, so all elements of the shift contain only
letters of $\mathcal{B}$. This does not mean, however, that restricting the
substitution to $\mathcal{B}$ does not give a smaller subshift, as seen in the
next example.  $\Diamond$

######  Example 3.13.

Consider the finite substitution

$\varrho\colon\begin{cases}a\mapsto bc,\\\ b\mapsto bb,\\\ c\mapsto
cc.\end{cases}$

One may restrict the substitution to its eventual range
$\mathcal{B}=\\{b,c\\}$, which generates the subshift of two periodic
elements, of all $b$s and all $c$s. However,
$\varrho^{n+1}(a)=b^{2^{n}}c^{2^{n}}$ and thus we have the non-periodic
element $\cdots bbbccc\cdots\in X_{\varrho}$ in the subshift of the original
substitution.  $\Diamond$

######  Lemma 3.14.

Let $v\in\mathcal{L}(\varrho)$. Then $\varrho(v)\in\mathcal{L}(\varrho)$ and
$u\in\mathcal{L}(\varrho)$ for any $u\triangleleft v$.

###### Proof.

Let $Y$ be the set of generated words, so that
$\mathcal{L}(\varrho)=\overline{Y}$. By continuity of $\varrho$ we have that
$\varrho(\mathcal{L}(\varrho))=\varrho(\overline{Y})\subseteq\overline{\varrho(Y)}$.
If $u\in Y$ then $u\triangleleft\varrho^{n}(a)$ for some $a\in\mathcal{A}$ and
$n\in{\mathbb{N}}_{0}$ and thus $\varrho(u)\triangleleft\varrho^{n+1}(a)$ so
that $\varrho(Y)\subseteq Y$. Hence
$\overline{\varrho(Y)}\subseteq\overline{Y}=\mathcal{L}(\varrho)$ and thus
$\varrho(\mathcal{L}(\varrho))\subseteq\mathcal{L}(\varrho)$, as required.

The proof for closure under subwords is similar. Let $Y_{n}$ and $Y_{m}$
denote the set of generated words of length $n>m$. Given some $0\leq j\leq
n-m$, let $p\colon\mathcal{A}^{n}\to\mathcal{A}^{m}$ be the continuous map
which takes the $j$th subword of length $m$. Then
$p(\mathcal{L}^{n}(\varrho))=p(\overline{Y_{n}})\subseteq\overline{p(Y_{n})}$
by continuity. Clearly a subword of a generated word is generated, so
$\overline{p(Y_{n})}\subseteq\overline{Y_{m}}=\mathcal{L}^{m}(\varrho)$ and
thus $p(\mathcal{L}^{n}(\varrho))\subseteq\mathcal{L}^{m}(\varrho)$. Since
$n>m$ and $j$ were arbitrary, we see that $\mathcal{L}(\varrho)$ is closed
under taking subwords. ∎

######  Corollary 3.15.

Let $\varrho\colon\mathcal{A}\to\mathcal{A}^{+}$ be a substitution. Then
$\varrho(X_{\varrho})\subseteq X_{\varrho}$.

###### Proof.

Let $w\in X_{\varrho}$, so every subword of $w$ is legal. Let
$u\triangleleft\varrho(w)$. Then $u\triangleleft\varrho(v)$ for some
$v\triangleleft w$, the latter implying $v\in\mathcal{L}(\varrho)$. By Lemma
3.14 we have $\varrho(v)\in\mathcal{L}(\varrho)$. By the same lemma, since
$u\triangleleft\varrho(v)$, we have $u\in\mathcal{L}(\varrho)$. Since
$u\triangleleft\varrho(w)$ was arbitrary, we see that $\varrho(w)\in
X_{\varrho}$, as required. ∎

The following identifies those substitutions whose languages (and in
particular full alphabets) are fully realised in the subshift:

######  Proposition 3.16.

The following are equivalent:

  1. (1)

for every $n\in{\mathbb{N}}$ and non-empty open subset
$U\subseteq\mathcal{A}$, there is some word generated by $\varrho$ of length
$2n+1$ whose central letter is in $U$;

  2. (2)

for all $a\in\mathcal{A}$ and $n\in{\mathbb{N}}$, there is a legal word of
length $2n+1$ whose central letter is $a$;

  3. (3)

$\mathcal{L}^{1}(X_{\varrho})=\mathcal{L}^{1}(\varrho)=\mathcal{A}$;

  4. (4)

$\mathcal{L}(X_{\varrho})=\mathcal{L}(\varrho)$.

###### Proof.

($1\implies 2$): Let $a\in\mathcal{A}$ be arbitrary. By assumption, for each
open set $U\subseteq\mathcal{A}$ containing $a$ we may construct a word
$v_{U}$ of length $2n+1$ that is generated by $\varrho$ and has a letter of
$U$ at its centre. By compactness of $\mathcal{A}^{2n+1}$ there is a subnet of
$(v_{U})$ which converges to some word $v$. By construction $v$ has $2n+1$
letters, contains $a$ at its centre and is the limit of a net of words
generated by $\varrho$. Thus $v$ is in the closure of the generated words, so
is legal, as required.

($2\implies 3$): By definition, $\mathcal{L}^{1}(\varrho)=\mathcal{A}$ (since
$a\triangleleft\varrho^{0}(a)=a$). To see that every letter $a\in\mathcal{A}$
appears in $X_{\varrho}$, by using the assumption we may find a sequence
$(v_{n})$ of legal words of length $2n+1$ whose central letters are all $a$.
By compactness of $\mathcal{A}$ we may choose a subsequence $S_{1}$ of
$(v_{n})$ which converges at positions $-1$ and $+1$, say to $a_{-1}$ and
$a_{1}$, respectively. Similarly, we may find a subsequence $S_{2}$ of $S_{1}$
which also converges at positions $a_{-2}$ and $a_{2}$. Continuing in this
way, we construct an infinite word $w=\\{a_{i}\\}_{i\in{\mathbb{Z}}}$ and
subsequences $S_{n}$ of legal words which converge to $w_{[-n,n]}$ when
restricted to the word of length $2n+1$ about the origin. Since
$\mathcal{L}(\varrho)$ is closed we see that
$w_{[-n,n]}\in\mathcal{L}(\varrho)$. Since these cover all of $w$, it follows
that $w\in X_{\varrho}$, since then any finite subword of $w$ is a subword of
some $w_{[-n,n]}$, which is legal. As $a=w_{0}$ we have that
$a\in\mathcal{L}^{1}(X_{\varrho})$, as required.

($3\implies 4$): We show that $\varrho^{n}(a)$ is legal for each
$a\in\mathcal{A}$ and $n\in{\mathbb{N}}_{0}$. Indeed, by assumption, for each
$a\in\mathcal{A}$ there is some $w\in X_{\varrho}$ so that $a\triangleleft w$.
Then $\varrho^{n}(a)\triangleleft\varrho^{n}(w)$, and $\varrho^{n}(w)\in
X_{\varrho}$ by Corollary 3.15. We see that $\mathcal{L}(X_{\varrho})$
contains all generated words. Since languages are always closed (Proposition
2.7) we see that $\mathcal{L}(X_{\varrho})\subseteq\mathcal{L}(\varrho)$. The
reverse inclusion is trivial, by definition of $X_{\varrho}$.

($4\implies 1$): Let $U\subseteq\mathcal{A}$ be non-empty and open and
$n\in{\mathbb{N}}$ arbitrary. Take any $a\in U$. Choose any $w\in X_{\varrho}$
with $w_{0}=a$, which we may do using shift-invariance and the fact that, in
particular, our assumption implies that
$\mathcal{L}^{1}(X_{\varrho})=\mathcal{L}^{1}(\varrho)=\mathcal{A}$. Then
$w_{[-n,n]}$ is legal, of length $2n+1$ and has $w_{0}=a$. Since the legal
words are in the closure of the generated words, it follows that we may find a
generated word $v$ with $v_{0}\in U$. ∎

######  Remark 3.17.

If the equivalent conditions of the above result are satisfied then $\varrho$
is letter surjective. Indeed, in this case any given $a\in\mathcal{A}$ is
legal, so for arbitrary open $U\subseteq\mathcal{A}$ containing $a$ we can
find some supertile $\varrho^{k}(b)=\varrho(\varrho^{k-1}(b))$ containing a
letter of $U$. In particular, there is some $b_{U}\in\mathcal{A}$ with
$\varrho(b_{U})_{i}\in U$. By compactness of $\mathcal{A}$, there is a
convergent subnet of $(b_{U})$, which by continuity has limit $b$ satisfying
$a\triangleleft\varrho(b)$. However, being letter surjective is not
sufficient, as demonstrated by Example 3.11.  $\Diamond$

######  Remark 3.18.

Note that, in the case that $\mathcal{A}$ is infinite, it is not necessarily
the case that we may find any given $a\in\mathcal{A}$ in the interior of a
word generated by $\varrho$ in the above result. For example, consider
$\mathcal{A}={\mathbb{N}}_{0}\cup\\{\infty\\}$ and

$\varrho\colon\left\\{\begin{array}[]{rl}n\ \mapsto&0\ n\\!+\\!1\\\ \infty\
\mapsto&0\ \infty.\end{array}\right.$

It is not hard to see that every letter of $\mathcal{A}$ appears in some word
of $X_{\varrho}$. In particular, we have the fixed point
$\varrho^{\infty}(\infty\mid 0)\in X_{\varrho}$. However, $\infty$ appears
only as the final term of a supertile $\varrho^{n}(\infty)$.  $\Diamond$

The above proposition gives necessary and sufficient conditions for the
language of the subshift to agree with the legal words. The next result
concerns this set of legal words which, a priori, requires taking a closure of
the generated words for each $\mathcal{L}^{n}$. Fortunately, as long as all
letters grow without bound under substitution, then once we know the 2-letter
legal words we can construct all other legal words by substituting these and
the letters $\mathcal{A}$.

######  Lemma 3.19.

Let $\varrho\colon\mathcal{A}\to\mathcal{A}^{+}$ be a substitution such that
$|\varrho^{n}(a)|\to\infty$ as $n\to\infty$ for every $a\in\mathcal{A}$. For a
subset $U\subseteq\mathcal{A}^{\ast}$, let $S_{n}(U)\subseteq\mathcal{A}^{n}$
denote the subwords of words from $U$ of length $n$. Then

$\mathcal{L}^{n}(\varrho)=\bigcup_{j=0}^{P}S_{n}(\varrho^{j}(\mathcal{A}\cup\mathcal{L}^{2}(\varrho)))$
(1)

where $P$ may be taken as any number with $|\varrho^{P}(a)|\geq n$ for all
$a\in\mathcal{A}$.

###### Proof.

Firstly, there exists some $P\in{\mathbb{N}}$ with $|\varrho^{P}(a)|\geq n$
for all $a\in\mathcal{A}$. Indeed, consider

$\mathcal{A}_{m}=\\{a\in\mathcal{A}\mid|\varrho^{m}(a)|\leq
n-1\\}\subseteq\mathcal{A}.$

Then $\mathcal{A}_{m}=(|\,\cdot\,|\circ\varrho^{m})^{-1}\\{1,\ldots,n-1\\}$
and hence is compact. Since words grow under application of $\varrho$, we have
that $\mathcal{A}_{m}\supseteq\mathcal{A}_{m+1}$. If each
$\mathcal{A}_{m}\neq\varnothing$, then by Cantor’s Intersection Theorem there
is some $x\in\mathcal{A}_{m}$ for each $m$. This contradicts the substitution
growing on $x$. It follows that some $\mathcal{A}_{P}=\varnothing$ or,
equivalently, $|\varrho^{P}(a)|\geq n$ for each $a\in\mathcal{A}$.

We define

$Z=\bigcup_{j=0}^{\infty}S_{n}(\varrho^{j}(\mathcal{A}\cup\mathcal{L}^{2}(\varrho))),$

which agrees with the union of the lemma except that we take an infinite
union. Clearly $Z$ contains all length $n$ words generated by $\varrho$.
Moreover, since the substitution of a legal word is legal (Lemma 3.14), we
have that $Z\subseteq\mathcal{L}$. It follows that $\overline{Z}=\mathcal{L}$.

We claim that the above union does not change by truncating at $j=P$. Indeed,
suppose that $v\in\mathcal{L}^{n}(\varrho)$ with
$v\triangleleft\varrho^{k}(u)$ for $k>P$ and
$u\in\mathcal{A}\cup\mathcal{L}^{2}(\varrho)$. Then
$v\triangleleft\varrho^{P}(\varrho^{k-P}(u))$. As any word of the form
$\varrho^{P}(a)$ has length at least $n$, it follows that there is some $1$ or
$2$-letter subword $u^{\prime}\triangleleft\varrho^{k-P}(u)$ with
$v\triangleleft\varrho^{P}(u^{\prime})$. Since substitutions and subwords of
legal words are legal, we have that
$u^{\prime}\in\mathcal{A}\cup\mathcal{L}^{2}(\varrho)$ and thus $v\in
S_{n}(\varrho^{P}(\mathcal{A}\cup\mathcal{L}^{2}(\varrho)))$.

It follows that $Z$ is the finite union in the statement of the lemma. Since
$\mathcal{A}\cup\mathcal{L}^{2}(\varrho)$ is compact, the same follows for $Z$
which is thus closed. Hence $\mathcal{L}=\overline{Z}=Z$, as required. ∎

######  Remark 3.20.

Technically the $\mathcal{A}$ term of Equation 1 needs to be included in
general, since it is possible that a letter does not appear in any $2$-letter
legal word. However, in examples where the substitution grows without bound,
if every legal letter appears also in the subshift (i.e., it satisfies the
equivalent conditions of Proposition 3.16) then it must appear in a legal
$2$-letter word and thus we may simplify the statement to

$\mathcal{L}^{n}(\varrho)=\bigcup_{j=0}^{P}S_{n}(\varrho^{j}(\mathcal{L}^{2}(\varrho))).$

In fact, it may be simplified further in this case. In Proposition 3.21 we
will see that every element of $X_{\varrho}$ is the image under substitution
of another, up to a shift. It easily follows that every legal $1$ or
$2$-letter word is a subword of the substitute of another. Hence the above is
a nested union and so we may write instead:

$\mathcal{L}^{n}(\varrho)=S_{n}(\varrho^{P}(\mathcal{L}^{2}(\varrho))).$

$\Diamond$

The following result shows that for every element of $X_{\varrho}$, there is a
corresponding ‘supertiling’ decomposition (substitutive preimage up to an
appropriate shift):

######  Proposition 3.21.

Let $\varrho\colon\mathcal{A}\to\mathcal{A}^{+}$ be a substitution with
associated subshift $X_{\varrho}$. For every $w\in X_{\varrho}$, there exists
an element $x\in X_{\varrho}$ and an integer $0\leq i\leq|\varrho(x_{0})|-1$
such that $\sigma^{i}(\varrho(x))=w$.

###### Proof.

We present an analogue of the usual proof from the finite alphabet setting.
Let $w\in X_{\varrho}$ and $v_{n}=w_{[-n,n]}$. Since $v_{n}$ is legal there is
a net of generated words converging to $v_{n}$. Thus, for each $n$ we have a
directed set $\Lambda_{n}$, supertiles $\varrho^{k(n,m)}(t(n,m))$ for
$k(n,m)\in{\mathbb{N}}$ and $t(n,m)\in\mathcal{A}$ and subwords
$u(n,m)\triangleleft\varrho^{k(n,m)}(t(n,m))$ so that $u(n,m)\to v_{n}$ as
$m\to\infty$ in $\Lambda_{n}$.

We may consider the patches $u(n,m)$ as centred over the origin, so that
convergence $u(n,m)\to v_{n}$ as $m\to\infty$ holds letter-wise, at each
position. Similarly, we may position the patches
$q(n,m)\coloneqq\varrho^{k(n,m)-1}(t(n,m))$ over the origin so that
$u(n,m)\triangleleft\sigma^{i(n,m)}\varrho(q(n,m))$, for $0\leq i<\ell$, where
$\ell$ is the number of tiles in the substitute of the origin tile of
$q(n,m)$. Indeed, we may shift $q(n,m)$ so that $u(n,m)_{0}$ is in the image
of the origin tile of $q(n,m)$ after substitution. We may pass to subnets of
each $\Lambda_{n}$ so that $i(n,m)=i_{n}$ is constant in $m$, and then
restrict to values of $n\in{\mathbb{N}}_{0}$ so that all remaining $i_{n}=i$
are constant.

We thus construct patches $q(n,m)$ so that tiles at positions $[-n,n]$ of
$\sigma^{i}\varrho(q(n,m))$ converge to those of $w$. Using compactness,
choose a subnet $S_{0}$ of $q(n,m)$ which converges at position $0$, say to
$x_{0}$. By continuity we have that $0\leq i\leq|\varrho(x_{0})|-1$.
Similarly, we may choose a subnet $S_{1}$ of $S_{0}$ which also converges at
positions $-1$ and $1$, say to tiles $x_{-1}$ and $x_{1}$, respectively.
Inductively define subnets in this way so that $S_{n}$ converges at all
positions $j\in[-n,n]$ to letters $x_{j}$.

By construction (and continuity), the infinite word
$w^{\prime}=\\{x_{j}\\}_{j\in{\mathbb{Z}}}$ satisfies
$\sigma^{i}(\varrho(w^{\prime}))=w$. We now need to show that every subword of
$w^{\prime}$ is legal. Since, by Lemma 3.14, subwords of legal words are
legal, it suffices to show that $w^{\prime}_{[-n,n]}$ is legal for each $n$.
By construction we have the net $S_{n}$ which converges letter-wise on
positions $[-n,n]$ to $w_{[-n,n]}$. This net consists of subwords of
supertiles $\varrho^{k(n,m)-1}(t(n,m))$, so it follows that $w_{[-n,n]}$ is in
the closure of the generated words and thus is legal, as required. ∎

###  3.1. Primitivity

The following definition is adapted from the work of Durand, Ormes and Petite
[10], modified so that the condition only needs to be checked for a single
power $p$. This definition is essentially the same as the one given by Priebe-
Frank and Sadun [16], just in a slightly different setting.

######  Definition 3.22.

Let $\varrho\colon\mathcal{A}\to\mathcal{A}^{+}$ be a substitution. We say
$\varrho$ is _primitive_ if for every non-empty open set
$U\subseteq\mathcal{A}$, there exists a $p=p(U)\geq 0$ such that for all
$a\in\mathcal{A}$, some letter of $\varrho^{p}(a)$ is in $U$.

This is easily seen to be equivalent to the definition in [10]:

######  Lemma 3.23.

The substitution $\varrho$ is primitive if and only if for every non-empty
open set $U\subseteq\mathcal{A}$, there exists a $p=p(U)\geq 0$ such that for
all $a\in\mathcal{A}$ and for all $j\geq p$, some letter of $\varrho^{j}(a)$
is in $U$.

###### Proof.

Suppose $\varrho$ is primitive and let $U\subseteq\mathcal{A}$ be a given open
set. Let $p$ be such that for all $a\in\mathcal{A}$, some letter of
$\varrho^{p}(a)$ is in $U$ and let $j\geq p$. Let $a$ be a letter in
$\mathcal{A}$ and let $b$ be the first letter of $\varrho^{j-p}(a)$. Then
$\varrho^{p}(b)\triangleleft\varrho^{p}(\varrho^{j-p}(a))=\varrho^{j}(a)$. By
primitivity, $\varrho^{p}(b)\triangleleft\varrho^{j}(a)$ contains a letter in
$U$. The other direction is trivial. ∎

The following is an analogue of Proposition 2.14 on repetitivity, in the sense
that it gives an equivalent primitivity condition described by finding _all_
letters of $\mathcal{A}$ within _all_ level-$p$ supertiles, up to some given
tolerance:

######  Proposition 3.24.

The following are equivalent:

  1. (1)

$\varrho$ is primitive;

  2. (2)

for every finite open cover $\mathcal{U}=\\{U_{i}\\}_{i=1}^{\ell}$ of
$\mathcal{A}$, there exists a $p=p(\mathcal{U})\geq 0$ such that for all
$a\in\mathcal{A}$ and $1\leq i\leq\ell$, some letter of $\varrho^{p}(a)$ is in
$U_{i}$;

  3. (3)

for every open $U\subseteq\mathcal{A}\times\mathcal{A}$ containing the
diagonal, there is some $p\geq 0$ so that, for all $a$, $b\in\mathcal{A}$, we
have that $b^{\prime}\triangleleft\varrho^{p}(a)$ for some
$b^{\prime}\in\mathcal{A}$ with $(b,b^{\prime})\in U$.

###### Proof.

(1 $\implies$ 2): If $\varrho$ is primitive, then for each $1\leq i\leq\ell$,
let $p_{i}\geq 0$ be the power such that for all $a\in\mathcal{A}$,
$\varrho^{p_{i}}(a)$ contains a letter in $U_{i}$. Take $p$ to be the maximum
of these $p_{i}$. Then by Lemma 3.23, for all $a\in\mathcal{A}$ and $1\leq
i\leq\ell$, $\varrho^{p}(a)$ contains a letter in $U_{i}$. The other direction
is trivial by taking the open cover $\\{U,\mathcal{A}\\}$.

(2 $\implies$ 3): Let $U\subseteq\mathcal{A}\times\mathcal{A}$ be open and
contain the diagonal and take $V\subseteq\mathcal{A}\times\mathcal{A}$ with
$V=V^{-1}$ and $V\circ V\subseteq U$. Similarly to before we take the open
cover $\\{V_{a}\\}_{a\in\mathcal{A}}$ of $\mathcal{A}$, where $a^{\prime}\in
V_{a}$ if $(a,a^{\prime})\in V$. By compactness we may find a finite subcover
$\\{V_{a_{i}}\\}_{i=1}^{\ell}$. Take $p\geq 0$ according to property 2 and let
$a$, $b\in\mathcal{A}$. We have that $a\in V_{a_{i}}$ for some $i$, so
$(a_{i},a)\in V$ and thus also $(a,a_{i})\in V$. By property 2, we have that
$a^{\prime}\triangleleft\varrho^{p}(b)$ for some $a^{\prime}\in V_{a_{i}}$ so
that $(a_{i},a^{\prime})\in V$. We have that
$(a,a^{\prime})=(a,a_{i})\circ(a_{i},a^{\prime})\in V\circ V\subseteq U$, as
required.

(3 $\implies$ 1): Let $U\subseteq\mathcal{A}$ be an arbitrary, non-empty open
subset and let $V=\mathcal{A}\setminus(\\{a\\}\times(\mathcal{A}\setminus
U))$, where $a\in U$ is arbitrary. Then
$V\subseteq\mathcal{A}\times\mathcal{A}$ is open and contains the diagonal.
Take $p\geq 0$ according to property 3 and let $b\in\mathcal{A}$ be arbitrary.
Then there is some $a^{\prime}\triangleleft\varrho^{p}(b)$ with
$(a,a^{\prime})\in V$. The latter implies that $a^{\prime}\in U$, as required.
∎

######  Remark 3.25.

Similar to Remark 2.15, property 3 above has an intuitive interpretation when
$\mathcal{A}$ is a metric space: for all $\epsilon>0$ there is some
$p=p(\epsilon)\geq 0$ so that, for all $a\in\mathcal{A}$, every letter
$b\in\mathcal{A}$ is $\epsilon$-close to a letter of $\varrho^{p}(a)$.
$\Diamond$

In the following result (and elsewhere), to avoid trivialities, we assume that
$\varrho$ is not the trivial substitution $\varrho(a)=a$ on a one-letter
alphabet, which technically would be primitive according to Definition 3.22.

######  Proposition 3.26.

Let $\varrho\colon\mathcal{A}\to\mathcal{A}^{+}$ be a primitive substitution.
For all $n\geq 1$, there exists a $p\geq 0$ such that for all
$a\in\mathcal{A}$, $|\varrho^{p}(a)|\geq n$. Hence, for all $a\in\mathcal{A}$,
${\displaystyle\lim_{i\to\infty}|\varrho^{i}(a)|=\infty}$.

###### Proof.

If $\mathcal{A}$ is finite we can take the open cover of singletons, so that
$\varrho^{p}(a)$ contains each letter of $\mathcal{A}$ for some $p\geq 0$.
Since $\varrho$ is not the trivial substitution, we must have that
$|\varrho(a)|\geq 2$. Since $a\triangleleft\varrho^{p}(a)$, it follows that
$|\varrho^{kp}(a)|\geq 2k$, as required.

If $\mathcal{A}$ is infinite then (since $\mathcal{A}$ is Hausdorff)
$\mathcal{A}$ admits finite open covers $\mathcal{U}$ with arbitrarily many
mutually disjoint subsets, say
$\mathcal{U}=\\{U_{1},\ldots,U_{n},\mathcal{A}\\}$ where $U_{i}\cap
U_{j}\neq\varnothing$ for all $1\leq i,j\leq n$. By Proposition 3.24(2), we
have that $\varrho^{p}(a)$ contains a letter in each $U_{i}$ for some $p\geq
0$. Then $|\varrho^{p}(a)|\geq n$. Since $|\varrho^{i}(a)|$ is monotonic, we
see that $|\varrho^{i}(a)|\to\infty$ as $i\to\infty$. ∎

As a consequence of Corollary 3.9, $X_{\varrho}$ must then also be non-empty.

######  Corollary 3.27.

If $\varrho$ is primitive, then $X_{\varrho}\neq\varnothing$ is a subshift.

It is worth mentioning that, from the proof of Proposition 3.26, it is enough
to show that a single letter $a\in\mathcal{A}$ ‘densely fills $\mathcal{A}$
under substitution’ in the sense of satisfying condition 2 of Proposition 3.24
in order for $\lim_{i\to\infty}|\varrho^{i}(a)|=\infty$, and this is often the
easiest way to show that $X_{\varrho}$ is non-empty.

It is clear that property 1 of Proposition 3.16 holds for primitive
substitutions. Indeed, take an arbitrary non-empty open subset
$U\subseteq\mathcal{A}$ and $a\in\mathcal{A}$. For some $n\geq 1$ we have
$|\varrho^{n}|\geq 3$, so $\varrho^{n}(a)=xvy$ for $x$, $y\in\mathcal{A}$ and
$v\in\mathcal{A}^{+}$. Consider $j\geq p$ and
$\varrho^{n+j}(a)=\varrho^{j}(x)\varrho^{j}(v)\varrho^{j}(y)$. By primitivity,
$\varrho^{j}(v)$ contains a letter $u\in U$. By taking $j$ sufficiently large,
we may ensure that $|\varrho^{j}(x)|$, $|\varrho^{j}(y)|\geq n$, so that there
is a word $v^{\prime}\triangleleft\varrho^{j}(a)$ of length $2n+1$ centred
around $u$ and is generated by $\varrho$, as required. Since all letters grow
without bound, by Remark 3.20 we have the following:

######  Corollary 3.28.

Let $\varrho$ be a primitive substitution. Then for all
$n\in{\mathbb{N}}_{0}$,

$\mathcal{L}^{n}(\varrho)=\mathcal{L}^{n}(X_{\varrho})=S_{n}(\varrho^{P}(\mathcal{L}^{2}(\varrho))),$

where $S_{n}(U)$ denotes the $n$-letter subwords of words from
$U\subseteq\mathcal{A}^{\ast}$ and $P$ is any number satisfying
$|\varrho^{P}(a)|\geq n$ for all $a\in\mathcal{A}$.

For any non-empty open set of legal _words_ $U$ (rather than just a set of
letters), it will be useful to find a power $p$ such that every level-$p$
supertile $\varrho^{p}(a)$ contains a word in $U$ as a subword.

######  Proposition 3.29.

Let $\varrho$ be primitive and $U\subseteq\mathcal{L}^{n}(\varrho)$ be non-
empty and open. There exists a power $p\geq 0$ such that, for every
$a\in\mathcal{A}$, there is a subword of $\varrho^{p}(a)$ in $U$.

###### Proof.

Since $U$ is open, we can find a generated word $u\in U$ so that
$u=p_{i}(\varrho^{k}(b))$, where $p_{i}$ is the projection to the length $n$
subword beginning at the index $i$. Again using that $U$ is open, and
continuity of $p_{i}\circ\varrho^{k}$ (which is well defined on an open subset
of $\mathcal{A}$), we have an open subset $V\subseteq\mathcal{A}$ for which
$p_{i}\circ\varrho^{k}(v)\in U$ for all $v\in V$. By primitivity, there is
some $p\geq 0$ so that $\varrho^{p}(a)$ contains an element of $V$ for all
$a\in\mathcal{A}$. Then, for arbitrary $a\in\mathcal{A}$, we have
$\varrho^{p+k}(a)$ contains a word of $\varrho^{k}(V)$, whose $i$th subword of
length $n$ belongs to $U$, as required. ∎

Primitivity of $\varrho$ is a strong condition and gives us that $X_{\varrho}$
is minimal, hence every element has a dense orbit and is repetitive.

######  Theorem 3.30.

Let $\varrho\colon\mathcal{A}\to\mathcal{A}^{+}$ be a substitution with
associated subshift $X_{\varrho}$. If $\varrho$ is primitive, then
$X_{\varrho}$ is a minimal subshift.

###### Proof.

Let $U\subseteq\mathcal{L}^{n}(\varrho)$ be any open subset. By Proposition
3.29, there is some $p\geq 0$ such that, for all $a\in\mathcal{A}$, there is a
subword of $\varrho^{p}(a)$ in $U$. Take any $w\in X_{\varrho}$. By
Proposition 3.21, there exists some $w^{\prime}\in X_{\varrho}$ such that
$\varrho^{p}(w^{\prime})=\sigma^{i}(w)$, where $0\leq i\leq|\varrho^{p}|-1$.
So the word $\varrho^{p}(w_{0})$, and hence a word in $U$, appears within a
uniformly bounded distance of the origin in $w$ and hence $w$ is repetitive.
Thus, by Corollary 2.19, $X_{w}$ is minimal. It is clear that
$X_{w}=X_{\varrho}$, since the above shows that any non-empty open
$U\subseteq\mathcal{L}^{n}(\varrho)$ contains a subword of any $w\in
X_{\varrho}$. ∎

It is interesting to note, therefore, that by the above and Propositions 2.12
and 2.16, if the alphabet $\mathcal{A}$ is non-separable, then all
substitutions on $\mathcal{A}$ are non-primitive.

######  Corollary 3.31.

If $\varrho$ is primitive, then $\mathcal{A}$ is separable.

###  3.2. Realising set substitutions with compact alphabets

Suppose that $S$ is a set, and we have a function $\varrho\colon S\to S^{+}$.
It is natural to ask whether we may extend $\varrho$ to a continuous
substitution on a compact, Hausdorff alphabet. In the finite case this is
clear, by using the discrete topology on $S$. Combinatorial substitutions with
$S$ countable have already been studied, for example in the work of Ferenczi
[13]. As we have seen, such a substitution on a compact alphabet would
necessarily be of bounded length. Given this necessary restriction, we may in
fact always find such a compactification:

######  Theorem 3.32.

Let $\varrho\colon S\to S^{+}$ with $|\varrho|<\infty$. Then there is a
compact, Hausdorff alphabet $\mathcal{A}$, a dense inclusion $\iota\colon
S\hookrightarrow\mathcal{A}$ and a substitution
$\overline{\varrho}\colon\mathcal{A}\to\mathcal{A}^{+}$ so that
$\overline{\varrho}(\iota a)=\iota\varrho(a)$ for all $a\in S$. Moreover, we
may choose $\iota$ so that $\iota(S)$ is the set of isolated points of
$\mathcal{A}$.

###### Proof.

Since $L\coloneqq|\varrho|<\infty$, we may write $\varrho\colon S\to S\sqcup
S^{2}\sqcup\cdots\sqcup S^{L}$. Equip $S$ with the discrete topology and let
$\iota\colon S\hookrightarrow\beta S$ be its Stone–Čech compactification. Then
$\iota$ naturally embeds $S^{n}$ into $(\beta S)^{n}$ for each
$n\in{\mathbb{N}}$, so we may regard $\varrho$ as a map

$\varrho\colon S\to\beta S\sqcup(\beta S)^{2}\sqcup\cdots\sqcup(\beta S)^{L}.$

This is continuous, since all maps from discrete spaces are. As a finite
disjoint union of compact Hausdorff spaces, we have that $K\coloneqq\beta
S\sqcup(\beta S)^{2}\sqcup\cdots\sqcup(\beta S)^{L}$ is compact Hausdorff.
Hence, by the universal property of the Stone–Čech compactification, we may
extend $\varrho$ to a continuous map

$\overline{\varrho}\colon\beta S\to\beta S\sqcup(\beta
S)^{2}\sqcup\cdots\sqcup(\beta S)^{L}.$

This is nothing other than a continuous substitution of maximal length $L$ on
the compact, Hausdorff alphabet $\beta S$. This compactification makes
$\iota(S)\subseteq\beta S$ a dense subspace of isolated points, as required. ∎

Note that the above construction in fact allows us to compactify any
continuous substitution on a topologised alphabet which is Hausdorff but non-
compact (which will contain the original alphabet as a dense subspace).
Although the above answers our question on realising arbitrary (infinite) set
substitutions with continuous, compact substitutions, it is far from ideal,
since the Stone–Čech compactification is usually unwieldy. For example,
$\beta{\mathbb{N}}_{0}$ has cardinality $2^{\mathfrak{c}}$, where
$\mathfrak{c}$ is the cardinality of the continuum. It is also non-separable.
This rules out the substitution being primitive by Corollary 3.31.

In practice there are often more obvious compactifications. As an example, the
substitution $\varrho\colon n\mapsto 0\,(n+1)$ on ${\mathbb{N}}_{0}$ may be
clearly extended to the one-point compactification, by defining $\infty\mapsto
0\,\infty$, and it is easily checked that this is primitive; see [13, 16].

##  4\. The substitution operator and natural length functions

We say that the substitution $\varrho$ has a _natural length function_ with
_inflation factor $\lambda\geq 1$_ if there is a continuous _length function_
$\ell\colon\mathcal{A}\to{\mathbb{R}}_{\geq 0}$ such that, for all
$a\in\mathcal{A}$, we have

$\sum_{b\triangleleft\varrho(a)}\ell(b)=\lambda\cdot\ell(a),$ (2)

where the notation $\sum_{b\triangleleft\varrho(a)}$ enumerates over each
$b$-entry of $\varrho(a)$, including multiplicities.

In other words, we have an associated geometric substitution where all letters
$a$ in $\mathcal{A}$ are assigned a corresponding tile of some fixed length
$\ell(a)$, depending continuously on their location in $\mathcal{A}$, and
where these tiles are inflated by a factor of $\lambda$ and then dissected
into other tiles according to the rule determined by $\varrho$, each with a
corresponding fixed length.

###  4.1. The substitution operator

######  Definition 4.1.

We let $E=C(\mathcal{A},{\mathbb{R}})$ denote the Banach space of continuous
functions $f\colon\mathcal{A}\to{\mathbb{R}}$, which is equipped with norm
$\|f\|\coloneqq\sup\\{f(a)\mid a\in\mathcal{A}\\}$. Call an element $f\in E$
_positive_ (resp.  _strictly positive_) if $f(a)\geq 0$ (resp. $f(a)>0$) for
all $a\in\mathcal{A}$. Let $K$ denote the _positive cone_ of positive
elements, and $K_{>0}$ denote the set of strictly positive elements. Given
$f$, $g\in E$, we write $f\leq g$ if $f(a)\leq g(a)$ for all $a\in A$. That
is, if $g-f\in K$. Given this partial order, $E$ is a Banach lattice; see
[32]. We have the _order interval_ $[f,g]=\\{z\in E\mid f\leq z\leq g\\}$.

The dual $E^{\prime}$ of $E$ is the Banach space of continuous homomorphisms
$\phi\colon E\to{\mathbb{R}}$, which has norm
$\|\phi\|\coloneqq\sup_{\|f\|\leq 1}|\phi(f)|$. We sometimes write
$\langle\phi,f\rangle\coloneqq\phi(f)$. For an operator $M\colon E\to E$, the
dual operator $M^{\prime}$ is defined by
$(M^{\prime}\phi)(f)\coloneqq\langle\phi,Mf\rangle$. The dual cone
$K^{\prime}\subset E^{\prime}$ is defined as the set of $\phi\in E$ for which
$\phi(f)\geq 0$ whenever $f\in K$.

By the Riesz–Markov–Kakutani Representation Theorem, there is a bijection
between continuous linear functionals $\phi$ on
$E=C(\mathcal{A},{\mathbb{R}})$ and regular signed finite Borel measures $\mu$
on $\mathcal{A}$, where we identify

$\langle\phi,f\rangle\leftrightarrow\int_{\mathcal{A}}f\mathrm{d}\mu,$

for continuous ‘test functions’ $f\in E$. Positive functionals on $E$ (which
are necessarily continuous) i.e., the elements of $K^{\prime}$, may be
identified with the (unsigned) regular finite Borel measures on $\mathcal{A}$.

######  Remark 4.2.

Because of the above correspondence, all measures here will be assumed to be
regular. For example, when we speak of _unique ergodicity_ in Section 6.1, it
is meant that there is a unique _regular_ Borel probability measure. Note that
a Borel probability measure on a compact Hausdorff alphabet $\mathcal{A}$ is
automatically regular in most cases of interest, including when $\mathcal{A}$
has a countable base for its topology, or when $\mathcal{A}$ is metrisable.
$\Diamond$

Given any ‘length function’ $f\in E$ (not necessarily one which satisfies
Equation (2)), it is still meaningful to talk of the ‘length’ of the
substitute of a tile $a\in\mathcal{A}$, by summing the lengths of the letters
of $\varrho(a)$. So we define

$M\colon E\to
E,\quad\quad(Mf)(a)\coloneqq\sum_{b\triangleleft\varrho(a)}f(b),$

where $\varrho(a)$ is seen as a multiset (so we sum including multiplicities
as in Equation (2)).

To find a natural length function is thus to find a positive eigenvector of
$M$, which we call the _substitution operator_. Note that $M$ only depends on
the substitution considered as a multi-valued map, i.e., it does not depend on
the order of letters of each supertile.

######  Remark 4.3.

We note that an analogous operator called the _transition map_ was introduced
in [15, 16] in the geometric setting for fusion tilings. Before this, such an
operator has already been used to determine statistical properties of
generalised pinwheel tilings in [29].  $\Diamond$

######  Example 4.4.

Let $\mathcal{A}$ be finite and with the discrete topology. A basis for $E$ is
given by the indicator functions $\mathds{1}_{a}$ for $a\in\mathcal{A}$, where
$\mathds{1}_{a}(a)=1$ and $\mathds{1}_{a}(b)=0$ for $a\neq b\in\mathcal{A}$.
Then

$(M\mathds{1}_{a})(b)=\sum_{c\triangleleft\varrho(b)}\mathds{1}_{a}(c)=\sum_{a\triangleleft\varrho(b)}\mathds{1}_{a}(a)=M_{ab}$

where $M_{ab}$ is the number of occurrences of $a$ in $\varrho(b)$. So we may
write

$M\mathds{1}_{a}=\sum_{b\triangleleft\mathcal{A}}M_{ab}\cdot\mathds{1}_{b}$

and hence, with respect to this basis, $M$ is represented by the matrix
$(M)_{ba}$. This is the transpose of $(M)_{ab}$, often called the
_Abelianisation_ or _population matrix_ of the substitution in the finite
letter setting.  $\Diamond$

It is easy to see that $M^{n}$ is the operator which replaces a length
function $f$ with its sum over level $n$-supertiles:

######  Lemma 4.5.

For $n\in{\mathbb{N}}$ we have
$\displaystyle(M^{n}f)(a)=\sum_{b\triangleleft\varrho^{n}(a)}f(b)$.

###### Proof.

The above is true for $n=1$ by definition of $M$. Suppose that it holds for
$n\in{\mathbb{N}}$. Then

$(M^{n+1}f)(a)=M\left(b\mapsto\sum_{c\triangleleft\varrho^{n}(b)}f(c)\right)(a)=\sum_{b\triangleleft\varrho(a)}\sum_{c\triangleleft\varrho^{n}(b)}f(c)=\sum_{c\triangleleft\varrho^{n+1}(a)}f(c),$

so the result also holds for $n+1$ and thus for all $k\in{\mathbb{N}}$ by
induction. ∎

Clearly $M$ is linear and _positive_ , which is to say that $M(K)\subseteq K$.
Moreover $M$ is a bounded operator, since for all $a\in\mathcal{A}$ we have
$|M(f)(a)|=|\sum_{b\triangleleft\varrho(a)}f(b)|\leq
N\cdot\max|f|=|\varrho|\cdot\|f\|$, where the length $|\varrho|$ of the
substitution is bounded by Proposition 3.5. In fact, we have the following
formula for the operator norm of $M^{n}$. Let $\mathbbm{1}$ be the constant
function $a\mapsto 1$.

######  Corollary 4.6.

For $n\in{\mathbb{N}}$, the operator norm of $M^{n}$ is given by

$\|M^{n}\|=\|M^{n}(\mathbbm{1})\|=|\varrho^{n}|.$

###### Proof.

It follows easily from the previous lemma that, for $\|f\|\leq 1$, the norm
$\|M^{n}f\|$ is maximised by the constant function $\mathbbm{1}$, for which
$(M^{n}\mathbbm{1})(a)=|\varrho^{n}(a)|$. ∎

In the finite setting, the existence of a positive non-zero length function
follows from Perron–Frobenius Theory. Surprisingly, this does not hold for all
substitutions on compact alphabets:

######  Example 4.7.

Consider again the substitution of Example 3.10 on the alphabet
$\mathcal{A}={\mathbb{N}}_{\infty}\times{\mathbb{N}}_{\infty}$, for which
$(n,m)\mapsto(n,m-1)$ for $m>0$, $(n,0)\mapsto(n-1,n)(0,n)$ for $n>0$ and
$(0,0)\mapsto(0,0)$. It is not hard to show that this substitution has no
continuous, positive, non-zero length function $\ell$. Dropping the
requirement that $\ell$ is continuous, it is not hard to show that
$M\ell=\lambda\ell$ implies that $\lambda=1$ and

$\ell(n,m)=\begin{cases}(n+1)\alpha_{1},&\mbox{if }n,m\neq\infty,\\\
\alpha_{2},&\mbox{if }n=\infty,m=0,\\\ \alpha_{3},&\mbox{if }n=0,m=\infty,\\\
\alpha_{2}-\alpha_{3},&\mbox{if }n=m=\infty,\\\ \beta_{n},&\mbox{if
}m=\infty,\end{cases}$

where $\alpha_{1}$, $\alpha_{2}\geq\alpha_{3}$ and $\beta_{n}$ are arbitrary
non-negative numbers, with at least one strictly positive. Note that $\ell$ is
unbounded if $\alpha_{1}\neq 0$, and if $\alpha_{1}=0$ then $\ell=0$ on a
dense subset of $\mathcal{A}$.  $\Diamond$

######  Example 4.8.

The substitution in the above example was primarily motivated by its
pathological non-growth property, perhaps making it less surprising that it
does not have a continuous length function. However, it can be easily modified
to be growing in length on all letters but still admitting no continuous
length function. We double up the substitution on $(0,0)$ and triple it on all
other letters: for $(n,m)\in{\mathbb{N}}_{0}\times{\mathbb{N}}_{0}$ we define

$\varrho\colon\left\\{\begin{array}[]{rll}(0,0)\ \mapsto&(0,0)(0,0),&\\\
(n,m)\ \mapsto&(n,m-1)(n,m-1)(n,m-1)&\text{ for }m>0,\\\ (n,0)\
\mapsto&(n-1,n)(n-1,n)(n-1,n)(0,n)(0,n)(0,n)&\text{
otherwise,}\end{array}\right.$

which uniquely defines the substitution $\varrho$ on
$\mathcal{A}={\mathbb{N}}_{\infty}\times{\mathbb{N}}_{\infty}$ by continuity.
Since all letters in ${\mathbb{N}}_{0}\times{\mathbb{N}}_{0}$ eventually map
to $(0,0)$, it is clear that $\ell(0,0)\neq 0$, otherwise $\ell=0$ by
continuity, so also $\ell(n,m)\neq 0$ for all
$(n,m)\in{\mathbb{N}}_{0}\times{\mathbb{N}}_{0}$. Since
$(0,0)\mapsto(0,0)(0,0)$, the inflation constant must be $\lambda=2$. But for
$(n,m)\in{\mathbb{N}}_{0}\times{\mathbb{N}}_{0}$, with $m>0$, we have

$\lambda\ell(n,m)=2\ell(n,m)=\ell(n,m-1)+\ell(n,m-1)+\ell(n,m-1)\implies\ell(n,m)=\frac{3}{2}\ell(n,m-1)\neq
0,$

so $\ell$ is unbounded, contradicting continuity. Thus, this substitution
admits no continuous and non-zero length function.  $\Diamond$

Although the above shows that not all substitutions have a length function, it
seems reasonable to conjecture this for primitive substitutions:

######  Question 4.9.

Let $\varrho$ be a primitive substitution on a compact, Hausdorff alphabet.
Does $\varrho$ admit a continuous, positive, non-zero, natural length
function?

We are not currently able to resolve the above question in full generality.
However, we will find some conditions under which this holds. In the remainder
of this subsection we will consider general properties of the Banach space
$E$, the operator $M$ and implications of primitivity.

######  Remark 4.10.

Because $\mathcal{A}$ is compact Hausdorff it is Tychonoff, i.e., Hausdorff
and completely regular. This means that for any closed set $C$ and $u\notin
C$, there exists a continuous function $f\colon\mathcal{A}\to[0,1]$ with
$f(u)=1$ and $f(C)=\\{0\\}$, which will be used in several proofs below.
$\Diamond$

######  Proposition 4.11.

The substitution $\varrho$ is primitive if and only if for all non-zero $f\in
K$ there exists some $p\in{\mathbb{N}}$ with $M^{p}(f)\in K_{>0}$.

###### Proof.

Let $\varrho$ be primitive and $0\neq f\geq 0$. Let $U=f^{-1}(0,\infty)$,
which is open and non-empty. By primitivity, there exists some
$p\in{\mathbb{N}}$ so that for any $a\in\mathcal{A}$ we have that
$\varrho^{p}(a)$ contains some $b\in U$, which is to say that $f(b)>0$. Since
$f\geq 0$ and $f(b)>0$ for some $b\in\varrho^{n}(a)$, it follows from Lemma
4.5 that $(M^{p}f)(a)>0$ for all $a\in\mathcal{A}$.

Conversely, suppose the given condition on $M$ holds and that
$U\subset\mathcal{A}$ is open and non-empty. Let $C=\mathcal{A}\setminus U$,
$u\in U$ be arbitrary and $f\colon\mathcal{A}\to[0,1]$ be continuous with
$f(u)=1$ and $f(C)=\\{0\\}$ (Remark 4.10). By assumption there exists some
$p\in{\mathbb{N}}$ so that $M^{p}(f)>0$. By Lemma 4.5, for every
$a\in\mathcal{A}$ we have that

$\sum_{b\triangleleft\varrho^{p}(a)}f(b)>0.$

Since $f\geq 0$ and $f(b)=0$ for all $b\notin U$, this implies that $b\in U$
for some $b\in\varrho^{p}(a)$, as required. ∎

We recall [30] that a positive cone $K\subset E$ is called _proper_ if
$K\cap(-K)=\\{0\\}$, _generating_ if $E=K-K$ and _normal_ if
$\|x+y\|\geq\|y\|$ for all $x$, $y\in K$. The ordered Banach space $(E,K)$ is
said to have the _decomposition property_ [1] if, for all $x$, $y$ and $z\in
K$ with $z\leq x+y$, there exist $b_{1}$, $b_{2}\in K$, with $z=b_{1}+b_{2}$
and $b_{1}\leq x$, $b_{2}\leq y$. The proof of the following is routine, so we
omit it:

######  Lemma 4.12.

We have that $K\subset E$ is a closed, proper, generating and normal cone,
with interior $\mathrm{int}(K)=K_{>0}$. The Banach space $(E,K)$ has the
decomposition property. ∎

######  Definition 4.13.

A subset $A\subset E$ is called _total_ if the linear span of $A$ is dense in
$E$.

######  Definition 4.14.

A point $f\in E$ is called _quasi-interior_ to $K$ if the order interval
$[0,f]$ is a total subset of $E$.

Every interior point of $K$ is quasi-interior [30], and the converse holds if
$\mathrm{int}(K)\neq 0$, which is clearly the case here by Lemma 4.12. For a
proof of the following lemma, we refer the reader to [32].

######  Lemma 4.15.

A point $f\in E$ is quasi-interior to $K$ if and only if
$f\in\mathrm{int}(K)$.

######  Corollary 4.16.

The substitution $\varrho$ is primitive if and only if for every non-zero
$f\in K$ one has that $M^{p}(f)$ is quasi-interior to $K$ for some
$p\in{\mathbb{N}}$.

We recall from [30] that an operator $M$ is _strongly positive_ if for each
$0\neq x\in K$, there is some $n=n(x)\in{\mathbb{N}}$ such that $M^{n}(x)$ is
quasi-interior to $K$. Then Proposition 4.11 may be restated as follows.

######  Corollary 4.17.

The substitution $\varrho$ is primitive if and only if $M$ is strongly
positive.

The strongly positive condition implies the weaker property of the operator
$M$ (and every power $M^{n}$) being _(ideal) irreducible_ , meaning that for
every ideal $I$ of $E$ with $M(I)\subseteq I$, we have that $I=\\{0\\}$ or
$I=E$. For the notion of an ideal of a Banach lattice, we refer the reader to
[32, II.2], although note [32, III.1 Exp. 1] that for $E=C(X)$, with $X$ a
compact Hausdorff space, we have a bijective correspondence

$\text{closed subsets }C\text{ of }X\longleftrightarrow\text{ideals
}I_{C}=\\{f\in E\mid f(C)=\\{0\\}\\}.$

######  Definition 4.18.

Let $\varrho$ be a substitution on a compact alphabet $\mathcal{A}$. We say
that $\varrho$ is irreducible if it cannot be restricted to a strictly smaller
closed and non-empty subset of $\mathcal{A}$.

######  Proposition 4.19.

A substitution $\varrho$ is irreducible if and only if the substitution
operator $M$ is irreducible.

###### Proof.

Suppose that $\varrho(c)\subseteq C^{+}$ for all $c\in C$, for some closed
subset $C\subseteq\mathcal{A}$. Let $f\in I_{C}$, so that $f(c)=0$ for all
$c\in C$. Then $(Mf)(c)=f(c_{1})+\cdots+f(c_{n})=0$, where $c_{1}\cdots
c_{n}=\varrho(c)\in C^{+}$ for $c\in C$. Thus $M(I_{C})\subseteq I_{C}$. If
$M$ is irreducible, we must have that $I_{C}=\\{0\\}$ or $E$, so that
$C=\mathcal{A}$ or $\varnothing$, as required.

Conversely, suppose that $M(I_{C})\subseteq I_{C}$. We claim that $\varrho$
may be restricted to $C$. Indeed, if we have $b\triangleleft M^{n}(c)$, for
$c\in C$ but $b\in\mathcal{A}\setminus C$, then consider a function
$f\colon\mathcal{A}\to[0,1]$ with $f(c)=0$ for all $c\in C$ and $f(b)=1$
(Remark 4.10). Then $f\in I_{C}$ but $M(f)\notin I_{C}$, since
$(Mf)(c)=f(c_{1})+\cdots+f(c_{n})\geq 1$, where $c_{1}\cdots c_{n}=\varrho(c)$
contains a copy of $b$. It follows that $\varrho$ restricts to $C$. If
$\varrho$ is irreducible, it then follows that $I_{C}=\\{0\\}$ or $E$, as
required. ∎

###  4.2. The spectrum of $M$

The spectrum of the operator $M$ is the set

$\sigma(M)=\left\\{\lambda\in{\mathbb{C}}\mid\lambda\mathbb{I}-M\text{ is not
invertible}\right\\}.$

We call $R(\lambda)=(\lambda\mathbb{I}-M)^{-1}$ the resolvent operator, which
is a holomorphic (operator-valued) function on
${\mathbb{C}}\setminus\sigma(M)$. We call $\lambda_{0}\in\sigma(M)$ a _pole of
the resolvent_ (of order $p\in{\mathbb{N}}$) if there exists a punctured
neighbourhood of $\lambda_{0}$ such that the coefficient corresponding to $-p$
of the Laurent expansion of $R(\lambda)$ is non-zero and all other
coefficients for $n<-p$ are zero [36, Sec. 8]. A pole is called simple if it
is of order $p=1$. It is often very useful to know that $\lambda\in\sigma(M)$
is a pole of the resolvent; in particular, this implies $\lambda$ is an
eigenvalue (see, for instance [36, Thm. 5.8-A]):

######  Lemma 4.20.

If $\lambda\in\sigma(M)$ is a pole of the resolvent then $\lambda$ is isolated
in $\sigma(M)$ and is an eigenvalue of $M$.

For the rest of the paper, we let $r=r(M)$ denote the _spectral radius_ of
$M$, defined as $r=\sup\\{|\lambda|\mid\lambda\in\sigma(M)\\}$. This is the
natural generalisation of the Perron–Frobenius leading eigenvalue in the
finite alphabet setting. Gelfand’s formula gives us that

$r=\lim_{n\to\infty}\sqrt[n]{\|M^{n}\|}\ \text{ and }\
r\leq\sqrt[n]{\|M^{n}\|}\ \text{ for all }n\in{\mathbb{N}}.$ (3)

######  Lemma 4.21.

We have the following for all $n\in{\mathbb{N}}$:

$\min_{a\in\mathcal{A}}|\varrho^{n}(a)|\leq
r^{n}\leq\max_{b\in\mathcal{A}}|\varrho^{n}(b)|.$

###### Proof.

The upper bound follows from Equation (3) and Corollary 4.6. For the lower
bound, suppose that $c\coloneqq\min_{a\in\mathcal{A}}|\varrho^{n}(a)|$. We
claim that $c^{k}\leq\|M^{kn}\|$ for all $k\in{\mathbb{N}}$, which is to say
that each level $kn$-supertile contains at most $c^{k}$ letters. By definition
this holds for $k=1$. Suppose it holds for some given $k$. We have
$|\varrho^{(k+1)n}(a)|=|\varrho^{n}(\varrho^{kn}(a))|$ for all
$a\in\mathcal{A}$ so, since $\varrho^{kn}$ contains at least $c^{k}$ letters,
each of which substitutes under $\varrho^{n}$ to at least $c$ letters (by the
definition of $c$), we obtain the claimed upper bound for all $k$ by
induction. Applying Equation 3:

$r=\lim_{k\to\infty}\sqrt[k]{\|M^{k}\|}=\lim_{k\to\infty}\sqrt[kn]{\|M^{kn}\|}\geq\sqrt[kn]{c^{k}}=\sqrt[n]{c}.$

∎

Note, in particular, that $r\geq 1$ for any substitution. The _peripheral
spectrum_ of $M$ is the subset of the spectrum of maximum modulus:

$\sigma_{\mathrm{per}}(M)=\\{\lambda\in\sigma(M)\mid|\lambda|=r\\}.$

We say that $\lambda\in\sigma(M)$ is in the _point spectrum_ if $\lambda$ is
an eigenvalue of $M$ and let $\sigma^{\mathrm{p}}_{\mathrm{per}}(M)$ denote
the set of elements in the peripheral point spectrum. Since $M$ is a positive
operator, the spectral radius $r$ will always belong to the peripheral
spectrum [30, Prop. 1], although it is not always in the peripheral point
spectrum (Example 4.7). For the rest of the paper, we let $T$ denote the
operator

$T\coloneqq M/r.$

Likewise, its dual operator is denoted by $T^{\prime}=M^{\prime}/r$. Such
normalisation is typical in operator theory, as many spectral and convergence
results require $r(T)=1$.

######  Definition 4.22.

We say that $\phi\in E^{\prime}$ is an _eigenmeasure_ if $T^{\prime}\phi=\phi$
with $\phi\in K^{\prime}$ and $\|\phi\|=1$.

###  4.3. Consequences of a natural length function

The theorem below shows that in many cases of interest (such as for primitive
substitutions), natural length functions are essentially unique, when they
exist:

######  Theorem 4.23.

Let $\varrho$ be irreducible. Suppose one of the following holds:

  1. (A)

$T^{\prime}$ admits an eigenmeasure $\phi$ satisfying $\phi(f)>0$ for all
$f\in K$ with $f\neq 0$ and $\sigma_{\mathrm{per}}^{p}(T)\neq\varnothing$;

  2. (B)

$\varrho$ is constant length;

  3. (C)

$r$ is a pole of the resolvent of $T$;

  4. (D)

$\varrho$ is primitive and $\sigma_{\mathrm{per}}^{p}(T)\neq\varnothing$.

Then the following hold:

  1. (1)

$\varrho$ admits a natural length function $\ell\in K$ with stretching factor
$\lambda=r$;

  2. (2)

$\ell(a)>0$ for all $a\in\mathcal{A}$;

  3. (3)

up to scalar multiplication, $\ell$ is the only eigenvector of $M$ with
eigenvalue $r$;

  4. (4)

up to scalar multiplication, $\ell$ is the only eigenvector of $M$ in $K$.

Moreover, if D holds then $r$ is the only element in the peripheral point
spectrum of $M$.

###### Proof.

Note that $T$ is irreducible if and only if $\varrho$ is (Proposition 4.19),
as irreducibility is preserved under normalisation. Condition A implies the
result directly by [32, Thm. V.5.2]. We have that $T$ is a _Markov operator_
(that is, $T(\mathbbm{1})=\mathbbm{1}$) if and only if $\varrho$ is constant
length. Then B and C imply the result, by cases (i) and (ii) of the corollary
following [32, Thm. V.5.2].

Suppose that $\varrho$ is primitive. The positive cone $K$ is normal and has
non-empty interior. It then follows from [30, Cor., pg. 1015] that the dual
$T^{\prime}\colon E^{\prime}\to E^{\prime}$ of $T$ admits an eigenmeasure
$\phi\in K^{\prime}$; see also [31]. By Proposition 4.11 and compactness, for
any non-zero $f\geq 0$ there is some $p\in{\mathbb{N}}$ and $c>0$ for which
$(T^{p}f)(a)>c$ for all $a\in\mathcal{A}$. Then

$\langle\phi,f\rangle=\langle(T^{\prime})^{p}\phi,f\rangle=\langle\phi,T^{p}f\rangle>0,$

since $\phi\neq 0$ and hence is non-trivial on $\mathds{1}$, and thus on any
$f\in K_{>0}$, since each such function has $f\geq\kappa\mathds{1}$ for some
$\kappa>0$. Supposing that $\sigma_{\mathrm{per}}^{p}(T)\neq\varnothing$, we
have that A holds, as required. Moreover, $1$ is then the only element of the
peripheral point spectrum by [32, Prop. V.5.6]. ∎

######  Remark 4.24.

Note that primitivity cannot be dropped in the final statement of the above
theorem, as demonstrated by the irreducible substitution $\varrho(a)=bb$,
$\varrho(b)=aa$ on the finite alphabet $\mathcal{A}=\\{a,b\\}$.  $\Diamond$

######  Remark 4.25.

By the proof of Theorem 4.23, every substitution $\varrho$ admits at least one
eigenmeasure $\phi$. It is easily seen from the proof of Theorem 4.23 that
$\phi>0$ (that is, $\phi(f)>0$ for all non-zero $f\in K$) if $\varrho$ is
primitive.  $\Diamond$

######  Lemma 4.26.

Suppose that $\varrho$ is primitive and admits some natural length function
$\ell$ (necessarily with inflation constant $\lambda=r>1$). There are
constants $\alpha$, $\beta>0$ so that, for all $a\in\mathcal{A}$,

$\alpha\lambda^{n}\leq|\varrho^{n}(a)|\leq\beta\lambda^{n}.$

More generally, for any open subset $U\subset\mathcal{A}$, there exist
$\alpha(U)$, $\beta(U)>0$ and $p\in{\mathbb{N}}$ so that, for all
$a\in\mathcal{A}$,

$\alpha(U)\lambda^{n}\leq\\#\\{b\triangleleft\varrho^{n}(a)\mid b\in
U\\}\leq\beta(U)\lambda^{n}\ \text{ for all }n>p.$ (4)

###### Proof.

By Theorem 4.23, we have that $\ell>0$ has inflation constant $\lambda=r$. We
have that $r>1$ by Lemma 4.21, since $|\varrho^{n}(a)|>2$ for sufficiently
large $n$ by primitivity.

By compactness we have constants $c$, $C>0$ so that $c\mathbbm{1}\leq\ell\leq
C\mathbbm{1}$. Thus,

$c|\varrho^{n}(a)|=M^{n}(c\cdot\mathbbm{1})(a)\leq
M^{n}(\ell)(a)=\lambda^{n}\ell(a)\leq\lambda^{n}C,\ \mathrm{hence}\
|\varrho^{n}(a)|\leq\left(\frac{C}{c}\right)\lambda^{n}.$

Analogously we have an upper bound of
$\left(\frac{c}{C}\right)\lambda^{n}\leq|\varrho^{n}(a)|$, as required.

Now suppose that $U\subset\mathcal{A}$ is open. There exists a function $f\in
E$ with $f\geq 0$, $\|f\|=1$ and $f(b)=0$ for all $b\notin U$ (Remark 4.10).
By Proposition 4.11, $h\coloneqq M^{p}(f)\in K_{>0}$ for some
$p\in{\mathbb{N}}$. So, by compactness, $h\geq\kappa\mathbbm{1}$ for some
constant $\kappa>0$. Hence, for all $a\in\mathcal{A}$,

$\\#\\{b\in\varrho^{n+p}(a)\mid b\in
U\\}\geq(M^{n+p}(f))(a)=(M^{n}(h))(a)\geq\kappa
M^{n}(\mathbbm{1})(a)\geq\kappa\alpha\lambda^{n},$

where the first inequality again follows from Lemma 4.5. The lower bound of
Equation 4 follows, whilst the upper bound follows trivially from that for
$|\varrho^{n}(a)|$. ∎

We get the following immediate consequence.

######  Corollary 4.27.

Let $\varrho$ be primitive and suppose it admits a natural length function to
$\lambda=r$. Then the operator $T$ is power bounded, i.e., for some $\beta>0$,
$\|T^{n}\|\leqslant\beta$ for all $n\in\mathbb{N}$.

######  Remark 4.28.

Whilst we are not always assured the existence of a natural length function,
there is always at least a system of approximate length functions. For any
substitution $\varrho$, there exists a sequence $(x_{n})_{n\in{\mathbb{N}}}$
of $x_{n}\in K$, with each $\|x_{n}\|=1$, for which $(T-rI)x_{n}\to 0$
uniformly as $n\to\infty$ (i.e., $\|(T-rI)x_{n}\|\to 0$ as $n\to\infty$). This
result follows from [26, Prop. 4.1.1] (see, for instance, the proof of [9,
Prop. 1], which also applies to Banach lattices).  $\Diamond$

##  5\. Invariant measures on $(X_{\varrho},\sigma)$

In this section, we assume that the substitution $\varrho$ admits a natural
length function $\ell>0$, and that every letter of $\mathcal{A}$ appears in
some element of the subshift (see Proposition 3.16). We then build the
corresponding geometric hull $\Omega$ (also known as the tiling space) and
equip it with the continuous translation action by ${\mathbb{R}}$. The goal is
to relate translation-invariant measures on $(\Omega,{\mathbb{R}})$ to
sequences of measures on the alphabet $\mathcal{A}$ which are compatible with
the dual operator $T^{\prime}$. These can then be related to shift-invariant
measures on $X_{\varrho}$ by viewing $(\Omega,{\mathbb{R}})$ as a suspension
flow.

###  5.1. Power convergent operators and eigenmeasures

We wish to consider measures on $\mathcal{A}$ and the corresponding
substitution action on $\mathcal{A}$ induced by $M$. As already noted in
Remark 4.2, all measures will be assumed to be regular and we identify them
with elements of $K^{\prime}$ by the Riesz–Markov–Kakutani Representation
Theorem.

######  Remark 5.1.

In the finite alphabet case, the measures $\mu$ here are in correspondence
with row vectors, with one coordinate for each element of $\mathcal{A}$, which
‘integrate’ a weighted sum of letters by the inner product. Then
$\mu(Mf)=\lambda\mu(f)$ just means that $\mu$ is a left eigenvector of $M$. In
the uniquely ergodic case, the entries of this row vector may be considered as
the respective frequencies of each tile.  $\Diamond$

######  Definition 5.2.

Given a bounded linear operator $T\colon E\to E$ with $r(T)=1$ we define its
$n$th Cesàro mean as

$A_{n}(f)=\frac{1}{n}\sum_{i=0}^{n-1}T^{i}(f).$

We call $T$ _mean ergodic_ if

$Pf\coloneqq\lim_{n\to\infty}(A_{n}T)(f)\in E$

exists for every $f\in E$. We say that $T$ is _uniformly ergodic_ if the above
sequence of operators converges in the uniform operator topology [12]. That
is, for every $\epsilon>0$, for sufficiently large $n\in{\mathbb{N}}$ we have
$\|A_{n}(f)-P(f)\|<\epsilon$ for every $f\in E$ with $\|f\|\leq 1$;
equivalently111By the Uniform Boundedness Principle, $P$ is also a bounded
operator on $E$., $A_{n}\to P$ in the Banach space of bounded operators on
$E$.

Similarly, we say that $T$ is _strongly power convergent_ if
$\lim_{n\to\infty}T^{n}f\coloneqq Pf$ exists for all $f\in E$. We call $T$
_uniformly power convergent_ [23] if $T^{n}$ converges (necessarily to $P$) in
the uniform operator topology.

######  Remark 5.3.

It is not hard to see that if $T$ is uniformly (strongly) power convergent
then it is uniformly (mean) ergodic. It is also not difficult to show that
$P\colon E\to E$ is a projection to the subspace of $E$ fixed by $T$.
$\Diamond$

The result below follows directly from [32, Prop. III.8.5]:

######  Proposition 5.4.

Let $\varrho$ be an irreducible substitution on a compact Hausdorff alphabet.
Suppose that $T$ is mean ergodic and has a non-zero fixed vector. Then the
fixed subspace of $T$ is one-dimensional and spanned by some $\ell\in K_{>0}$.
Moreover, the fixed subspace of $T^{\prime}$ is one-dimensional and spanned by
some $\phi\in K^{\prime}_{>0}$.

###  5.2. Invariant measures and power convergence

Priebe-Frank and Sadun’s notion of _fusion tilings_ allows for a generalised
setting in which we can see that invariant measures on the geometric hull
$(\Omega,{\mathbb{R}})$ are in correspondence with sequences
$(\mu_{n})_{n=0}^{\infty}$ of elements in $K^{\prime}$ with
$T^{\prime}\mu_{n}=\mu_{n-1}$. Thus, unique ergodicity of
$(\Omega,{\mathbb{R}})$ is equivalent to the existence of a unique sequence of
_volume-normalised_ and _transition-consistent_ measures, which we define
below. We show that a sufficient condition for this is strong power
convergence of $T$ and irreducibility. We will see examples that demonstrate
the subtle relation between eigenmeasures and invariant measures.

This extends the classical result for primitive substitutions over finite
alphabets and primitive fusion tilings with finite local complexity; see [16,
Cor. 3.12]. Below, we recall some notions regarding fusion rules. We refer the
reader to [15, 16] for the general fusion framework.

Let $\varrho$ be a substitution on the compact Hausdorff alphabet
$\mathcal{A}$ with a natural length function $\ell>0$ and inflation constant
$r>1$ given by the spectral radius of $M$. Since sizes of supertiles grow
without bound, the associated geometric rule is automatically van Hove, i.e.,
the ratio of the measure of the boundaries of supertiles and the volume of the
supertile goes to zero as $n\to\infty$. Let $\mathcal{P}_{n}$ denote the set
of all supertiles of level $n$, i.e.,
$\mathcal{P}_{n}\coloneqq\left\\{\varrho^{n}(a)\mid a\in\mathcal{A}\right\\}$,
which means that each $\mathcal{P}_{n}$ can be tacitly identified with
$\mathcal{A}$, and any measurable subset $I\subseteq\mathcal{A}$ can be seen
as a subset of $\mathcal{P}_{n}$ for any $n$. A substitution $\varrho$ is
called _recognisable_ if every element in $\Omega$ admits a _unique_
decomposition into supertiles in $\mathcal{P}_{n}$ for all $n\in{\mathbb{N}}$
(note that all tilings have _some_ such decomposition, by Proposition 3.21).

A regular Borel measure $\mu_{n}$ on $\mathcal{P}_{n}$ (which we may identify
with a (positive) element of $K^{\prime}\subset C(\mathcal{P}_{n})^{\prime}$)
is called _volume-normalised_ if one has

$\int_{\mathcal{A}}\ell^{(n)}(a)\,{\mathrm{d}}\mu_{n}(a)\coloneqq\mu_{n}(\ell^{(n)})=1,$
(5)

where $\ell^{(n)}(a)\coloneqq M^{n}\ell(a)=r^{n}\ell(a)$ is simply the
geometric length of the level-$n$ supertile corresponding to
$a\in\mathcal{A}$. Let $\mathcal{M}^{(n)}$ be the set of volume-normalised
measures on $\mathcal{P}_{n}$. A pair
$(\mu_{n},\mu_{N})\in\mathcal{M}^{(n)}\times\mathcal{M}^{(N)}$ is called
_transition consistent_ if one has

$\mu_{n}=(M^{\prime})^{N-n}(\mu_{N}),\ \text{ equivalently }\
\mu_{n}=\mu_{N}\circ M^{N-n},$ (6)

where $M$ and $M^{\prime}$ are the substitution and the dual substitution
operators, respectively. Using instead notation similar to [16], for any
continuous function $f\in C(\mathcal{A})\cong E$,

$\mu_{n}(f)=\int_{\mathcal{A}}f(a)\,{\mathrm{d}}\mu_{n}(a)=\int_{\mathcal{A}}M^{N-n}f(a)\,{\mathrm{d}}\mu_{N}(a)=(\mu_{N}\circ
M^{N-n})(f).$

Note that $\mu_{N}(M^{N-n}f)$, for $f\colon\mathcal{P}_{n}\to{\mathbb{R}}$, is
simply given by considering $f$ as a function defined over $N$-supertiles, by
first taking the function $\mathcal{P}_{N}\to{\mathbb{R}}$ which, on an
$N$-supertile $a$, sums $f$ over $a$’s constituent $n$-supertiles (which
follows from the definition of $M^{N-n}$), and then integrating this with
$\mu_{N}$. Again, we may identify each $\mathcal{P}_{n}$ with $\mathcal{A}$,
which rescales $n$-supertiles by $r^{-n}$. Let us identify a continuous
function $f\colon\mathcal{P}_{n}\to{\mathbb{R}}$ with the function
$\widetilde{f}\colon\mathcal{A}\to{\mathbb{R}}$, where
$\widetilde{f}(a)\coloneqq r^{-n}f(a)$ (again, for $f(a)$, we are in fact
identifying $a$ with its $n$-supertile), and similarly identify a measure
$\mu_{n}$ on $\mathcal{P}_{n}$ with
$\widetilde{\mu}_{n}=r^{-n}\mu_{n}=f\mapsto\widetilde{\mu}_{n}(f)$. Then
volume normalisation and transition consistency become the conditions

$\widetilde{\mu}_{n}(\ell)=1\text{ and
}\widetilde{\mu}_{n}=(T^{\prime})^{N-n}(\widetilde{\mu}_{N})\text{ for all
}n<N.$

Note that, since $T(\ell)=\ell$, volume normalisation follows from
$\widetilde{\mu}_{0}(\ell)=1$ and transition consistency. Let
$\widetilde{\mathcal{M}}^{(n)}$ denote the measures on $\mathcal{P}_{n}$ which
are volume normalised with the above identification, i.e., those measures
$\mu\in K^{\prime}$ with $\mu(\ell)=1$. For a fixed $n<N$ the following is
defined in [16]:

$\Delta_{n,N}=(M^{\prime})^{N-n}\mathcal{M}^{(N)}.$

Then by the above renormalisation, we may identify this with

$\widetilde{\Delta}_{n,N}=(T^{\prime})^{N-n}\widetilde{\mathcal{M}}^{(N)}=\\{\widetilde{\mu}\in(T^{\prime})^{N-n}(K^{\prime})\mid\widetilde{\mu}(\ell)=1\\}.$
(7)

Let us now drop the tildes and use the above as our definition of
${\Delta}_{n,N}$:

$\Delta_{n,N}\coloneqq\\{\mu\in(T^{\prime})^{N-n}(K^{\prime})\mid\mu(\ell)=1\\}.$

We then define

$\Delta_{n}\coloneqq\cap_{N}\Delta_{n,N}\ \text{ and }\
\Delta_{\infty}\coloneqq\varprojlim\Delta_{n}.$

The next result then follows from [16, Thm. 4.2]:

######  Theorem 5.5.

For $\varrho$ recognisable there is a bijection between the set of
translation-invariant Borel probability measures on $\Omega$ and elements of
$\Delta_{\infty}$.

######  Theorem 5.6.

For $\varrho$ recognisable, the tiling dynamical system
$(\Omega,{\mathbb{R}})$ is uniquely ergodic if and only if $\Delta_{\infty}$
is a singleton. If $\varrho$ is not recognisable, then $(\Omega,{\mathbb{R}})$
is uniquely ergodic if $\Delta_{\infty}$ is a singleton.

###### Proof.

The first statement follows trivially from Theorem 5.5 in the recognisable
case. If $\varrho$ is not recognisable, we may consider an abstract hull where
recognisability is forced, as follows. In defining $\Omega$, one may modify
the definition of tilings in the geometric hull to be instead hierarchies of
tilings $\mathcal{T}=(\mathcal{T}_{n})_{n=0}^{\infty}$, where each
$\mathcal{T}_{n}\in\Omega$ and $\varrho(\mathcal{T}_{n})=\mathcal{T}_{n-1}$.
In other words, we define elements of the hull as instead sequences of
tilings, supertilings, level $2$-supertilings, and so on, so that the tiles of
$\mathcal{T}_{n}$ may be grouped into those of $\mathcal{T}_{n+1}$
consistently with respect to the substitution. So we consider the ‘extended
geometric hull’ $\Omega^{\prime}$ of such elements, which we may identify with

$\Omega^{\prime}=\varprojlim(\Omega\xleftarrow{\varrho}\Omega\xleftarrow{\varrho}\cdots),$

which also provides the topology on $\Omega^{\prime}$; translation acts in the
obvious way. Substitution
$(\mathcal{T}_{n})_{n=0}^{\infty}\mapsto(\varrho(\mathcal{T}_{n}))_{n=0}^{\infty}=(\mathcal{T}_{n+1})_{n=0}^{\infty}$
then acts as a homeomorphism on $\Omega^{\prime}$, building recognisability
into the system. The proof of Theorem 5.5 from [16] essentially only requires
recognisability to identify elements of the hull with consistent supertiling
sequences, so Theorem 5.5 applies to $\Omega^{\prime}$ and we may identify its
invariant measures with $\Delta_{\infty}$. But $\Omega^{\prime}$ naturally
factors onto $\Omega$, by the map $(\mathcal{T}_{n})\mapsto\mathcal{T}_{0}$,
and factors of uniquely ergodic dynamical systems are still uniquely ergodic,
so the result follows. ∎

######  Remark 5.7.

In Theorem 5.5 it is assumed that each $\mathcal{P}_{n}$ is a compact metric
space, equivalently here that $\mathcal{A}$ is metrisable. We note that the
same correspondence result easily extends to the case when $\mathcal{A}$ is
compact and Hausdorff.  $\Diamond$

######  Remark 5.8.

Clearly each $\Delta_{n}=\Delta_{0}$ is the eventual range of $K^{\prime}$
under the map $T^{\prime}$, restricted to $\mu\in K^{\prime}$ with
$\mu(\ell)=1$. Since $T^{\prime}$ must be surjective on this eventual range,
we have that $\Delta_{\infty}$ is a singleton if and only if $\Delta_{0}$ is.
Then if $(\Omega,{\mathbb{R}})$ is uniquely ergodic, the unique invariant
measure corresponds to a unique volume normalised eigenmeasure of
$T^{\prime}$. However, the converse is not true:  $\Diamond$

######  Example 5.9.

Consider the irreducible (but non-primitive) substitution

$\varrho\colon\begin{cases}a\mapsto bb,\\\ b\mapsto aa.\end{cases}$

The corresponding operator is $T\colon(x,y)\mapsto(y,x)$. Then the fixed
subspace of $T^{\prime}$ is one-dimensional and generated by
$(\frac{1}{2},\frac{1}{2})$. However, $\Delta_{\infty}$ is 2-dimensional,
consisting of the sequences
$(\alpha,\beta)\leftarrow(\beta,\alpha)\leftarrow(\alpha,\beta)\leftarrow\cdots,$
where $\alpha+\beta=1$ for $\alpha$, $\beta\geq 0$ (note that $X$ consists of
two periodic points, of all $a$s and all $b$s). The operator $T$ is
irreducible and mean ergodic but is not strongly power convergent since
$T^{2n}=I$ and $T^{2n+1}=T$.  $\Diamond$

We have the following sufficient condition for unique ergodicity in terms of
$T$.

######  Theorem 5.10.

Let $\varrho$ be an irreducible substitution on a compact Hausdorff alphabet
$\mathcal{A}$ which admits a natural length function $\ell>0$ with inflation
factor $r=r(M)>1$. Suppose further that $T$ is strongly power convergent. Then
$(\Omega,\mathbb{R})$ is uniquely ergodic.

###### Proof.

Since $\varrho$ is irreducible, $T$ is also irreducible by Proposition 4.19.
Strong power convergence of $T$ implies that $T$ is mean ergodic. By
Proposition 5.4, the fixed space of $T$ must be one-dimensional and $\ell>0$.
This also means the projection operator $P$, to which $T^{n}$ converges
strongly (though not necessarily uniformly), must be of rank $1$.

Suppose that a volume normalised and transition consistent sequence
$\\{\mu_{n}\\}$ is given and let $f\in E=C(\mathcal{A})$ be arbitrary. From
transition consistency,

$\mu_{0}(f)=(T^{\prime})^{n}(\mu_{n})(f)=\mu_{n}(T^{n}f).$

Since $T$ is strongly power convergent, $\lim_{n\to\infty}T^{n}f\to Pf=c\ell$
for some $c\in\mathbb{R}$. It follows that

$\mu_{0}(f)=\mu_{n}(T^{n}f)=\mu_{n}(c\ell+v_{n})=c\mu_{n}(\ell)+\mu_{n}(v_{n})=c+\mu_{n}(v_{n}),$

where $v_{n}\to 0$ as $n\to\infty$. Since $\ell>0$ we have that
$\ell\geq\kappa\mathds{1}$ for some $\kappa>0$, and since each $\mu_{n}$ is
positive we have that
$\|\mu_{n}\|=\mu_{n}(\mathds{1})\leq\kappa\mu_{n}(\ell)=\kappa$ for all $n$.
Thus, since $v_{n}\to 0$ as $n\to\infty$ and the norms of the $\mu_{n}$ are
bounded, it follows that $\mu_{n}(v_{n})\to 0$ as $n\to\infty$ and
$\mu_{0}(f)=c$. Therefore, $\Delta_{0}$ is a singleton, so $\Delta_{\infty}$
is too (Remark 5.8), thus $(\Omega,{\mathbb{R}})$ is uniquely ergodic by
Theorem 5.6. ∎

There is an explicit form for the measures of cylinder sets in $\Omega$ in
terms of a sequence $\left\\{\mu_{n}\right\\}\in\Delta_{\infty}$ which is
given in terms of measures on sets of patches which generate the topology on
$\Omega$. For the exact formulation, we refer the reader to [16, Sec. 4].

###  5.3. Invariant measures and suspension flows

To end this section, we briefly mention the well known correspondence between
$\sigma$-invariant measures on a subshift $X$ and ${\mathbb{R}}$-invariant
measures on the associated geometric hull $\Omega$, where each letter $a$
identified with an interval of some length $\ell(a)$. When the subshift comes
from a finite, primitive substitution, $\ell$ is given by the left
Perron–Frobenius eigenvector of the substitution matrix; see [8, 7], which
extends to our setting when there exists a natural length function $\ell$ with
$\ell(a)>0$ for all $a\in\mathcal{A}$.

For completeness, we provide here the definition of the suspension flow of a
subshift over a compact alphabet associated with a continuous length function.
Let $(X,\sigma)$ be a subshift and $\ell\colon\mathcal{A}\to{\mathbb{R}}_{>0}$
be continuous. The geometric hull $(\Omega,{\mathbb{R}})$ can be identified
with $(Y,{\mathbb{R}})$, where $Y=(X_{\varrho}\times{\mathbb{R}})/\sim$ and
the equivalence relation is generated by $(x,\ell(x_{0}))\sim(\sigma(x),0)$.
We call $(Y,{\mathbb{R}})$ the _suspension flow_ over $(X_{\varrho},\sigma)$
with continuous roof function $f(x)\coloneqq\ell(x_{0})$.

Let $\mathcal{M}(Y)$ be the set of ${\mathbb{R}}$-invariant probability
measures on $Y$ and let $\mathcal{M}(X)$ be the set of $\sigma$-invariant
measures on the subshift. Since the roof function is bounded away from zero,
it is well known [3, 5] that there is a one-to-one correspondence
$L\colon\mathcal{M}(X)\to\mathcal{M}(Y)$, given by

$\widetilde{\mu}\coloneqq
L(\mu)=\frac{(\mu\times\mu_{\text{Leb}})|_{Y}}{\int_{X}f(x)\,{\mathrm{d}}\mu(x)}.$

This leads to the following immediate consequence.

######  Corollary 5.11.

Let $\varrho$ be a substitution on a compact Hausdorff alphabet which is
recognisable and admits a natural length function $\ell$ which is strictly
positive. Then there is a one-to-one correspondence between the elements of
$\Delta_{\infty}$ and the set $\mathcal{M}(X_{\varrho})$ of $\sigma$-invariant
probability measures on $X_{\varrho}$. If $\varrho$ is not recognisable then
$X_{\varrho}$ is uniquely ergodic if $\Delta_{\infty}$ is a singleton.

##  6\. Applications

Using the operator-theoretic perspective above, we will establish two classes
of substitutions which are uniquely ergodic. We begin with examples which have
a type of quantitative coincidence property, which appears to apply very
generally to primitive substitutions on alphabets $\mathcal{A}$ containing an
isolated point. Afterwards, we will consider constant-length substitutions
whose columns generate uniformly equicontinuous semigroups.

###  6.1. Quasi-compact substitutions and unique ergodicity

In this section we will give a simple condition on $\varrho$ which ensures the
operator $T$ is _quasi-compact_ , allowing us to deduce strong properties of
the substitution.

######  Definition 6.1.

An operator $C\colon E\to E$ is called _compact_ if the image of the unit ball
under $C$ is relatively compact. An operator $T$ with $r(T)=1$ is called
_quasi-compact_ if there exists some compact operator $C$ and power
$n\in{\mathbb{N}}$ for which $\|T^{n}-C\|<1$.

######  Proposition 6.2.

If $\\#\mathcal{A}=\infty$ and $\varrho$ is letter surjective then $M$ is not
compact.

###### Proof.

Since $\mathcal{A}$ is Hausdorff and $\\#\mathcal{A}=\infty$ there exists an
infinite sequence $U_{1}$, $U_{2}$, …of non-empty, disjoint open subsets of
$\mathcal{A}$. Since $\varrho$ is letter surjective, for each $U_{i}$ we may
pick some $p_{i}\in U_{i}$ and $a_{i}\in\mathcal{A}$ with
$p_{i}\triangleleft\varrho(a_{i})$. For each $i\in{\mathbb{N}}$ we may find a
continuous map $g_{i}\colon\mathcal{A}\to[0,1]$ with $g_{i}(p_{i})=1$ and
$g_{i}(a)=0$ for $a\notin U_{i}$ (Remark 4.10). For $n\in{\mathbb{N}}$, define
$f_{n}\colon\mathcal{A}\to[0,1]$ by $f_{n}(a)\coloneqq
g_{1}(a)+\cdots+g_{n}(a)$. Then each $f_{n}$ belongs to the unit ball of $E$
but we claim that $(M(f_{n}))_{n}$ has no convergent subsequence. Indeed,
given arbitrary $n\in{\mathbb{N}}$, we note that $\|M(f_{n})-M(f_{i})\|\geq 1$
for $i<n$, since

$|(M(f_{n})-M(f_{i}))(a_{n})|=M(f_{n}-f_{i})(a_{n})=M(g_{i+1})(a_{n})+\cdots+M(g_{n})(a_{n})\geq
M(g_{n})(a_{n})\geq 1.$

The last inequality follows from the fact that we have
$p_{n}\triangleleft\varrho(a_{n})$, so that
$M(g_{n})(a_{n})=g_{n}(x_{1})+\cdots+g_{n}(x_{k})\geq 1$, where
$\varrho(a_{n})=x_{1}x_{2}\cdots x_{k}$ and $g_{n}(x_{i})=1$ for
$x_{i}=p_{n}$. ∎

Recall from Remark 3.12 that any substitution can be restricted to a letter
surjective substitution (although perhaps not without reducing the subshift),
and from Remark 3.17 that any substitution which realises the whole alphabet
in the subshift is letter surjective. So essentially all infinite
substitutions of interest here have non-compact substitution operator.
However, we are able to identify cases where $T$ is quasi-compact:

######  Theorem 6.3.

Let $\varrho$ be an arbitrary substitution. For $P\subseteq\mathcal{A}$ and
$k\in{\mathbb{N}}$ we define

$C_{k}(P)\coloneqq\max_{a\in\mathcal{A}}\\#\\{b\triangleleft\varrho^{k}(a)\mid
b\notin P\\}.$

Suppose there is some $P\subseteq\mathcal{A}$ and $k\in{\mathbb{N}}$ such that
either

  1. (1)

$P$ is finite, consists of only isolated points and $C_{k}(P)<r^{k}$ or

  2. (2)

$P$ is finite and $2C_{k}(P)<r^{k}$.

Then $T$ is quasi-compact.

###### Proof.

We first consider the case that $P$ is a finite set of isolated points.
Consider the operator $V\colon E\to E$ given by

$(Vf)(a)=\begin{cases}f(a)&\text{ if }a\in P,\\\ 0&\text{
otherwise.}\end{cases}$

Clearly $V$ is a compact operator, since it maps onto the subspace of
functions supported on $P$, which is of finite dimension equal to $\\#P$. We
define $C\coloneqq T^{k}\circ V$. This is a compact operator, since the
composition of any bounded operator with a compact operator is compact. Then

$((T^{k}-C)(f))(a)=(T^{k}(I-V)(f))(a)=\frac{1}{r^{k}}\left(\sum_{b\triangleleft\varrho^{k}(a)\text{
with }b\notin P}f(b)\right).$

Then over all $\|f\|=1$, the norm of $(T^{k}-C)(f)$ clearly maximised by the
constant function $f=\mathbbm{1}$, for which

$\|(T^{k}-C)(\mathbbm{1})\|=\frac{1}{r^{k}}\max_{a\in\mathcal{A}}\left(\sum_{b\triangleleft\varrho^{k}(a)\text{
with }b\notin P}1\right)=\frac{C_{k}(P)}{r^{k}}.$

Then, assuming $C_{k}(P)<r^{k}$, we have that $T$ is quasi-compact.

Now suppose that $P$ is finite but contains non-isolated points. Then the
operator $V$ above is not continuous and needs to be adjusted. Choose open
sets $U_{p}$, one for each $p\in P$, so that $p\in U_{p}$ and $U_{p}\cap
U_{q}=\varnothing$ for $p\neq q$. For each $p\in P$, there exists a continuous
function $\psi_{p}\colon\mathcal{A}\to[0,1]$ for which $\psi_{p}(p)=1$ and
$\psi_{p}(a)=0$ for $a\notin U_{p}$ (Remark 4.10). We define $V\colon E\to E$
by

$(Vf)(a)=\sum_{p\in P}f(p)\cdot\psi_{p}(a)=\begin{cases}f(p)\cdot\psi_{p}(a)&\
\text{ for }\ a\in U_{p},\\\ 0&\ \text{ if }\ a\notin\bigcup_{p\in
P}U_{p},\end{cases}$

where in the latter formula we use that the $U_{p}$ are disjoint. It is easy
to see that $V$ is continuous, and it is compact since $V(E)$ is contained in
the $\\#P$-dimensional subspace spanned by the functions $\psi_{p}$. Thus,
$C\coloneqq T^{k}\circ V$ is also a compact operator and $T^{k}-C$ is given
by:

$((T^{k}-C)(f))(a)=(T^{k}(I-V)(f))(a)=\frac{1}{r^{k}}\sum_{b\triangleleft\varrho^{k}(a)}(f(b)-(Vf)(b)\cdot\psi_{b^{\prime}}(b)).$

Notice that for $b\in P$ we have $Vf(b)=f(b)$ so that $f(b)-(Vf)(b)=0$ and
thus the above sum may be taken over $b\notin P$. For $b\notin P$ and
$\|f\|\leq 1$, we have that $|f(b)-Vf(b)|\leq|f(b)|+|Vf(b)|\leq 2$. Hence,

$\|(T^{k}-C)(f)\|\leq\frac{1}{r^{k}}\max_{a\in\mathcal{A}}\left(\sum_{b\triangleleft\varrho^{k}(a)\text{
with }b\notin P}2\right)=\frac{2C_{k}(P)}{r^{k}}.$

Thus, $T$ is quasi-compact if $2C_{k}(P)<r^{k}$. ∎

Recall that we have the bound
$r\geq\min_{a\in\mathcal{A}}\sqrt[n]{|\varrho^{n}(a)|}$ for all
$n\in{\mathbb{N}}$, which makes the above checkable for many interesting
examples:

######  Example 6.4.

Consider the substitution

$\varrho\colon\begin{cases}0\mapsto 0\ 1,\\\ n\mapsto 0\ n\\!-\\!1\
n\\!+\\!1,\end{cases}$

defined on $\mathcal{A}={\mathbb{N}}_{\infty}$. Let $P=\\{0\\}$. Then every
$1$-supertile contains at most $2$ letters not in $P$. However, it is clear
that $r=r^{1}>2$. Indeed, $|\varrho^{2}(0)|=|01002|=5$,
$|\varrho^{2}(1)|=|0101013|=7$ and $|\varrho^{2}(n)|=|010(n-2)(n+1)0n(n+2)|=8$
for $n>1$, so that $\min_{a\in\mathcal{A}}|\varrho^{2}(a)|=5$ and hence
$r\geq\sqrt{5}>2$, by Lemma 4.21. It follows that $T$ is quasi-compact. For
illustrative purposes, we also note that one could take $P=\\{0,1\\}$ and
$k=2$. We have that each $\varrho^{2}(a)$ contains at most $4$ elements not in
$P$, and $4<5\leq r^{2}$.  $\Diamond$

######  Example 6.5.

Let $\varrho$ be any substitution of constant length $L$ for which
$\varrho^{k}(a)$ contains a letter in some finite subset
$P\subseteq\mathcal{A}$, for any $a\in\mathcal{A}$. If $P$ consists of
isolated points then $\varrho$ satisfies the conditions of Theorem 6.3.
Indeed, in this case $r=L$, and $|\varrho^{k}(a)|=r^{k}$ for all
$a\in\mathcal{A}$. Since, by assumption, each such $\varrho^{k}(a)$ contains
at least one occurrence of a letter in $P$, we have that $C_{k}(P)\leq
r^{k}-1<r^{k}$.

In fact, the same criterion may be used even if $P$ has non-isolated points in
the constant length case. Indeed, suppose each $\varrho^{k}(a)$ contains a
letter of $P$, for some finite $P$ and $k\in{\mathbb{N}}$. Define

$P(N)=P\cup\varrho^{k}(P)\cup\varrho^{2k}(P)\cup\cdots\cup\varrho^{Nk}(P).$

Suppose a given word $w$ contains at least $p$ letters in $P(N)$ and at most
$n$ letters in its complement, where $|w|=p+n$. Then $\varrho^{k}(w)$ contains
at least $rp+n$ letters in $P(N+1)$, since it has $rp$ from applying
$\varrho^{k}$ to letters of $P(N)$, and at least one contribution in
$P=P(0)\subseteq P(N+1)$ by applying $\varrho^{k}$ to each of the $n$ letters
not in $P(N)$. So at most $r(p+n)-(rp+n)=(r-1)n$ letters of $\varrho^{k}(w)$
are not in $P(N+1)$, since $w$ has $p+n$ letters. In matrix form,

$v\mapsto Av\ \text{ with }\ A=\begin{pmatrix}r&1\\\ 0&r-1\end{pmatrix}$

where $v=(p,n)^{T}$ and $Av$ has first coordinate a lower bound for the number
of elements in $P(N+1)$, and second coordinate an upper bound for the number
of elements not in $P(N+1)$. It follows that, for each $a\in\mathcal{A}$ and
$N\in{\mathbb{N}}$, the supertile $\varrho^{Nk}(a)$ contains at least
$(A^{N}(0,1)^{T})_{1}$ letters in $P(N)$ and at most $(A^{N}(0,1)^{T})_{2}$
not in $P(N)$. The matrix $A$ has leading Perron–Frobenius eigenvector
$(1,0)$, with eigenvalue $r$, and $1/r^{N}A^{N}(0,1)^{T}\to(1,0)$ as
$n\to\infty$; that is, the ratio of letters of $\varrho^{Nk}(a)$ in $P(N)$
converges to $1$ as $N\to\infty$. In particular, for some $N>0$, at least half
of the letters of each $\varrho^{Nk}(a)$ belong to $P(N)$. Since $P(N)$ is a
finite set, it follows from Theorem 6.3 that $T$ is quasi-compact.  $\Diamond$

######  Example 6.6.

Let $\mathcal{A}=S^{1}$ and consider the substitution $\varrho(x)=1\ \alpha
x$. Then we may take $P=\\{1\\}$ and every $\varrho^{1}(x)$ contains a letter
of $P$, so $T$ is quasi-compact by Example 6.5.  $\Diamond$

######  Example 6.7.

Suppose that $\varrho\colon\mathcal{A}\to\mathcal{A}^{*}$ is primitive and
that $\mathcal{A}$ contains at least one isolated point. Then if $\varrho$ is
constant length, it satisfies the conditions of Theorem 6.3. Indeed, if
$a\in\mathcal{A}$ is isolated, then $P\coloneqq\\{a\\}$ is open, so by
primitivity each $\varrho^{p}(b)$ contains at least one occurrence of $a$.
Then $\varrho$ is again covered by Example 6.5.

If $\varrho$ is primitive (but not necessarily constant length), then it is
similarly easy to show that, for every $b\in\mathcal{A}$, there are at least
$\alpha_{a}\cdot|\varrho^{k}(b)|$ occurrences of any given isolated point
$a\in\mathcal{A}$ in each $\varrho^{k}(b)$, for $k$ sufficiently large
(depending on $a$) and $\alpha_{a}>0$ not depending on $k$. However, it is not
clear that the condition of Theorem 6.3 is satisfied, since a priori it may
happen that $|\varrho^{k}(b)|/r^{k}$ is unbounded. In fact, even if
$|\varrho^{k}(b)|<Cr^{k}$ for all $k\in{\mathbb{N}}$ and $b\in\mathcal{A}$, it
is not immediately clear that there exists a finite subset
$P\subset\mathcal{A}$ so that each $\varrho^{k}(b)$ contains sufficiently many
occurrences in $P$ so as to apply Theorem 6.3. This raises the following:
$\Diamond$

######  Question 6.8.

Suppose that $\varrho$ is primitive and that $\mathcal{A}$ contains at least
one isolated point. Is $T$ power bounded? Is $T$ quasi-compact?

One simplification of the above question is to restrict to primitive
substitutions for which the isolated points are dense in $\mathcal{A}$, and
$\varrho$ sends isolated points to words of isolated points. Such
substitutions are natural to consider: they arise, for instance, from some
combinatorial substitutions on ${\mathbb{N}}_{0}$ which admit a
compactification to a primitive substitution.

Let $\mathcal{B}(E)$ be the Banach algebra of bounded linear operators on $E$.
We have the Banach subalgebra $\mathcal{K}(E)\leqslant\mathcal{B}(E)$ of
compact operators and the _Calkin algebra_ $\mathcal{B}(E)/\mathcal{K}(E)$.
The _essential spectral radius_ $r_{\mathrm{ess}}(T)$ of an operator
$T\in\mathcal{B}(E)$ is the operator norm of the image of $T$ in the Calkin
algebra. Equivalently, $r_{\mathrm{ess}}(T)$ is the supremum of moduli of
elements of the essential spectrum of $T$; the essential spectrum has various
inequivalent definitions (one being the _Browder spectrum_ [6]) but
$r_{\mathrm{ess}}(T)$ does not depend on which is taken. It is not hard to see
that for $r(T)=1$, we have that $T$ is quasi-compact if and only if
$r_{\mathrm{ess}}(T)<1$. Quasi-compactness is a very powerful property here,
since it ensures the existence of a continuous length function and unique
ergodicity in the primitive case. From [6, Lem. 17] (see also [25, Thm. 1]) we
have:

######  Lemma 6.9.

We have that $\lambda\in\sigma(T)$ lies outside the Browder spectrum if and
only if $\lambda$ is a pole of the resolvent $(\lambda\mathbb{I}-T)^{-1}$ of
finite rank.

######  Lemma 6.10.

Let $T$ be a positive, quasi-compact operator with $r(T)=1$. Then
$1\in\sigma(T)$ is a pole of the resolvent of $T$ of finite rank and thus $T$
has a non-trivial fixed vector.

###### Proof.

Since $T$ is positive, $r(T)=1\in\sigma(T)$, which cannot be in the Browder
spectrum because $r_{\mathrm{ess}}(T)<1$ by quasi-compactness. By Lemma 6.9,
$1$ is a pole of the resolvent of finite rank, which is an eigenvalue by Lemma
4.20. ∎

In the above, note that the fixed subspace of $T$ is one-dimensional and
spanned by some $\ell>0$ in our setting of $E=C(\mathcal{A})$, if $T$ is
additionally irreducible, [32, Thm. V.5.2] (see Proposition 4.23). If each
power $\varrho^{k}$ is irreducible, which includes the case that $\varrho$ is
primitive, then we have the following stronger result:

######  Proposition 6.11.

Suppose that $\varrho^{k}$ is irreducible for each $k\in{\mathbb{N}}$ (for
example, $\varrho$ is primitive) and that $T$ is quasi-compact. Then
$\\{r\\}=\sigma_{\mathrm{per}}(T)=\sigma_{\mathrm{per}}^{p}(T)$ and $T$ is
uniformly power convergent. If $\varrho$ is primitive then $r$ is a simple
pole of the resolvent.

###### Proof.

As discussed above, $T$ admits a fixed vector in $K_{>0}$. Then $1$ is the
only element of the peripheral spectrum, and $T$ is uniformly power
convergent, by [1, Prop. 5], whose results apply since $(E,K)$ has the
decomposition property (Lemma 4.12). If $\varrho$ is primitive then $1$ is a
simple pole of the resolvent, by [22, Thm. 11]: the results of [22, Sec. 5]
are given for ‘strictly positive operators’, but all hold more generally for
strongly positive operators (which holds for $\varrho$ primitive, by
Proposition 4.11), as stated in the introduction of that section. ∎

######  Theorem 6.12.

Suppose that $\varrho$ is primitive or, more generally, that $\varrho^{k}$ is
irreducible for all $k\in{\mathbb{N}}$. If $T$ is quasicompact then

  1. (1)

$\\{r\\}=\sigma_{\mathrm{per}}(T)=\sigma_{\mathrm{per}}^{p}(T)$;

  2. (2)

$T$ is uniformly power convergent;

  3. (3)

$M$ admits a unique (up to scaling) eigenfunction in $K$, which is a strictly
positive natural length function with stretching factor $\lambda=r>1$;

  4. (4)

the tiling dynamical system $(\Omega,{\mathbb{R}})$ is uniquely ergodic.

  5. (5)

the subshift $(X_{\varrho},\sigma)$ is uniquely ergodic.

###### Proof.

The statements (1), (2) follow from Proposition 6.11, whereas (3) follows from
Theorem 4.23. The statement (4) follows from (2),(3) and Theorem 5.10 and then
(5) follows from (4) and Corollary 5.11. ∎

Below, we give an example of a primitive substitution which satisfies the
conditions of Theorem 6.12 and compute the corresponding length function.

######  Example 6.13.

Let $\mathcal{A}={\mathbb{N}}_{\infty}$ and consider the substitution defined
in Example 3.2:

$\varrho\colon\left\\{\begin{array}[]{rl}0\ \mapsto&0\ 0\ 0\ 1,\\\ n\
\mapsto&0\ n\\!-\\!1\ n\\!+\\!1,\\\ \infty\ \mapsto&0\ \infty\
\infty.\end{array}\right.$

One can easily see that $\varrho$ is primitive. Using the same arguments as in
Example 6.4, one can show that the operator $T$ is quasi-compact. Here, we
give closed formulas for the letter frequencies and for the natural length
function. Let $\nu=(\nu_{0},\nu_{1},\ldots)^{T}$ be the frequency vector. Note
that the letter frequencies satisfy the linear recurrence relation
$\nu_{j}=\lambda\nu_{j-1}-\nu_{j-2}$, for $j\geqslant 2$ with
$\nu_{1}=(\lambda-2)\nu_{0}-1$. From the equation
$\sum_{j=0}^{\infty}\nu_{j}=1$, one gets $\lambda=3+\nu_{0}$. This implies
$\nu_{1}=\nu_{0}^{2}+\nu_{0}-1$. The recurrence relation is homogeneous with
characteristic polynomial $p(x)=x^{2}-\lambda x+1$. This means the solution of
the recurrence relation is of the form

$\nu_{j}=C_{+}\left(\frac{\lambda+\sqrt{\lambda^{2}-4}}{2}\right)^{j}+C_{-}\left(\frac{\lambda-\sqrt{\lambda^{2}-4}}{2}\right)^{j}$

for some constants $C_{-},C_{+}$. Since the frequencies satisfy
$\nu_{j}\leqslant 1$, we immediately get that $C_{+}=0$. From the initial
conditions, we get $C_{-}=\nu_{0}$ and
$C_{-}\left(\frac{\lambda-\sqrt{\lambda^{2}-4}}{2}\right)=\nu^{2}_{0}+\nu_{0}-1$.
Solving these two equations simultaenously yields $\nu_{0}=-1$ or
$\nu_{0}=\frac{1}{\sqrt{2}}$, where the first is obviously an extraneous
solution. This then yields $\lambda=3+\frac{1}{\sqrt{2}}$ and

$\nu_{j}=\frac{1}{\sqrt{2}}\left(1-\frac{1}{\sqrt{2}}\right)^{j}$

for $j\geqslant 0$ with $\nu_{\infty}=0$.

Next we solve for the lengths $\ell_{j}$. They satisfy the non-homogeneous
linear recurrence relation $\ell_{j}=\lambda\ell_{j-1}-\ell_{j-2}-\ell_{0}$.
If we fix $\ell_{\infty}=1$, we get that
$\ell_{0}=\lambda-2=1+\frac{1}{\sqrt{2}}$. Note that the non-homogeneous term
is $-\ell_{0}=-\ell_{0}\cdot 1^{j}$, and since $1$ is not a root of
$x^{2}-\lambda x-1$, and the two roots are distinct, we have a particular
solution given by some constant $C_{p}$. Solving for $C_{p}$ yields
$C_{p}=\frac{\ell_{0}}{\lambda-2}=1$. Combining this to the solution of the
associated homogeneous recurrence relation leads to

$\ell_{j}=1+\frac{1}{\sqrt{2}}\left(1-\frac{1}{\sqrt{2}}\right)^{j}\ \ \text{
for all }j\geq 0.$

$\Diamond$

######  Remark 6.14.

Recent work of Frettlöh, Garber, and Mañibo [17] has shown that there exists a
certain family of substitutions on appropriate compactifications of
${\mathbb{N}}_{0}$, which are generalisations of the example above, so that
Theorem 6.12 applies, making the subshifts $X_{\varrho}$ uniquely ergodic. By
primitivity, quasi-compactness and Theorem 4.23 these substitutions have a
uniquely defined natural length function, and the family is large enough to
realise any inflation factor $\lambda\in(2,\infty)$. This is in contrast to
the finite case, where inflation factors necessarily have to be algebraic
integers.  $\Diamond$

######  Example 6.15.

This example satisfies the conditions of Theorem 6.3 whilst being non-constant
length and with $\mathcal{A}$ uncountable. Give a different compactification
of ${\mathbb{N}}_{0}$ by embedding it in the cylinder by the map

$f\colon{\mathbb{N}}_{0}\to[0,1]\times S^{1},\
f(n)\coloneqq(1/(n+1),[n\alpha]).$

Then each $n\in{\mathbb{N}}_{0}$ is isolated in
$\mathcal{A}=\overline{f({\mathbb{N}}_{0})}\subset[0,1]\times S^{1}$, where we
add accumulation points $A=\\{0\\}\times S^{1}\subset\mathcal{A}$. Identify
the isolated points $(1/(n+1),[n\alpha])$ with $n\in{\mathbb{N}}_{0}$ and the
accumulation points $(0,x)\in\\{0\\}\times S^{1}$ with $x\in S^{1}$. Then

$\varrho\colon\begin{cases}0\mapsto 0\;\,0\;\,0\;\,1,\\\ n\mapsto
0\;\,n\\!-\\!1\;\,n\\!+\\!1\text{ for }n\in{\mathbb{N}}_{0},\\\ x\mapsto
0\;\,x\\!-\\!\alpha\;\,x\\!+\\!\alpha\text{ for }x\in S^{1}.\end{cases}$

It is not hard to check again that this is primitive. Theorem 6.3 applies just
as before, so $T$ is quasi-compact.  $\Diamond$

###  6.2. Constant length substitutions

Queffelec has already considered substitutions of constant length in compact
metrisable alphabets in [27], which she called _compact automata_. In this
subsection we let $\varrho(a)=L$ for all $a\in\mathcal{A}$. This greatly
simplifies matters, owing to the following:

  1. (1)

$\|M\|=r=L$ and $\|T\|=1$, that is, $T$ is a contraction;

  2. (2)

$M(\mathds{1})=L\mathds{1}$, so $\mathds{1}$ is a natural length function of
$\varrho$;

  3. (3)

$\varrho(a)=\varrho_{1}(a)\varrho_{2}(a)\cdots\varrho_{L}(a)$ for continuous
functions $\varrho_{i}\colon\mathcal{A}\to\mathcal{A}$, which we call
_columns_.

The last property means that the substitution operator is defined by

$M(f)=f\circ\varrho_{1}+f\circ\varrho_{2}+\cdots+f\circ\varrho_{L}.$

Let $\Phi$ be the semigroup generated by the columns $\\{\varrho_{i}\\}$. We
call $\Phi$ _equicontinuous_ if this set of functions is uniformly
equicontinuous (note that this notion does not require $\mathcal{A}$ to be
metrisable, since $\mathcal{A}$ carries a uniformity, as a compact Hausdorff
space). The following results are similar to those obtained in [27, Thm. 12.1,
Cor. 12.2].

######  Theorem 6.16.

Suppose that $\varrho$ is primitive, constant length and generates an
equicontinuous semigroup $\Phi$. Then $T$ is strongly power convergent and,
for $\varrho$ recognisable, the tiling dynamical system associated with
$\varrho$ is uniquely ergodic.

###### Proof.

Let $f\in K$ be arbitrary. First, note that

$T^{n}(f)=\frac{1}{L^{n}}\sum_{i=1}^{L^{n}}f\circ\phi^{(n)}_{i},$

where the sum is over all possible $n$-fold compositions
$\phi^{(n)}_{i}\in\Phi$ of columns. Since $\mathcal{A}$ is compact, $f$ is
equicontinuous and thus the maps $\\{f\circ\phi_{i}^{(n)}\\}$ are uniformly
equicontinuous. Since $T^{n}(f)$ is a convex combination of these maps, it