###### Abstract

We study the automorphism group of an infinite minimal shift $(X,\sigma)$ such
that the complexity difference function, $p(n+1)-p(n)$, is bounded. We give
some new bounds on $\mbox{Aut}(X,\sigma)/\langle\sigma\rangle$ and also study
the one-sided case. For a class of Toeplitz shifts, including the class of
shifts defined by constant-length primitive substitutions with a coincidence,
and with height one, we show that the two-sided automorphism group is a cyclic
group. We next focus on shifts generated by primitive constant-length
substitutions. For these shifts, we give an algorithm that computes their two-
sided automorphism group. Finally we show that with the same techniques, we
are able to compute the set of conjugacies between two such shifts.

title = Computing Automorphism Groups of Shifts using Atypical Equivalence
Classes, author = Ethan M. Coven, Anthony Quas, and Reem Yassawi,
plaintextauthor = Ethan M. Coven, Anthony Quas, and Reem Yassawi, runningtitle
= Computing Automorphism Groups, runningauthor = Ethan M. Coven, Anthony Quas,
and Reem Yassawi , keywords = substitution dynamical systems, endomorphisms,
year=2016, number=3, received=14 October 2015, revised=4 January 2016,
published=28 February 2016, doi=10.19086/da.611,

[classification=text]

##  1 Introduction

In this article we study the automorphism groups $\mbox{Aut}(X,\sigma)$ of
some “small” shifts $(X,\sigma)$. All terms are defined as they are needed in
Sections 2 to 3.

In the brief Section 2, we show that for shifts with sublinear complexity,
there are bounds on the orders of $\mbox{Aut}(X,\sigma)$ for one-sided shifts
and $\mbox{Aut}(X,\sigma)/\langle\sigma\rangle$ for two-sided shifts.

In [3], Coven explicitly describes the endomorphism monoid of any non-trivial
two-sided constant-length substitution shift $(X,\sigma)$ on two letters.
Either the shift has a metric discrete spectrum, in which case
$\mbox{Aut}(X,\sigma)$ consists of the powers of the shift, or the shift has a
partly continuous spectrum, in which case the “letter-exchanging” automorphism
is also present. In both cases all endomorphisms are automorphisms. For
constant-length substitutions on larger alphabets, those whose shifts have a
discrete spectrum are precisely those that have coincidences, [9, Thm 7] and
all other constant-length shifts, including the family of bijective
substitutions, have a partly continuous spectrum. (See Section 3.3 for the
definitions of these two terms.)

Primitive substitution shifts are uniquely ergodic [21], and in the measurable
setting Lemanczyk and Mentzen [19] show that any isomorphism of a bijective
substitution is the composition of a shift with a letter-to-letter code. Host
and Parreau [17] extend the results of [19], showing that for the constant-
length substitution shifts which do not have a purely discrete spectrum, maps
in the commutant111The commutant is the measurable analogue of the
endomorphism semigroup. are essentially topological and, up to a shift, have
small radius.

Substitution shifts arising from primitive substitutions are a sub-family of
shifts with sublinear complexity. We use a non-trivial result of Cassaigne [2]
to prove Theorem 2.3, which tells us that for infinite minimal one-sided
shifts $(X,\sigma)$ with sublinear complexity, automorphisms have a bounded
order, and, modulo powers of the shift, the same is true for infinite minimal
two-sided shifts with sublinear complexity. There are more general results,
with similar proofs, in recent articles, by Donoso, Durand, Maass and Petite
in [10, Theorem 1.1], and Cyr and Kra in [8, Theorem 1.4], both for the two-
sided case. In both of these articles, the condition of sublinear complexity
is relaxed ($\liminf p_{X}(n)/n$, rather than $\limsup p_{X}(n)/n$, is
required to be finite). Moreover, Cyr and Kra generalise this theorem to non-
minimal shifts. We prove a related one-sided result. Also, under the
assumption of sublinear complexity, our bound gives sharper bounds in some
cases, but requires finer information about the branch points or asymptotic
orbits. We give a case where the bound is tighter in Example 2.4. We also
mention Olli’s work [23], and also Salo and Törmä’s [24].

In Section 2.3, we use results in the literature to give bounds on the orders
of elements in $\mbox{Aut}(X,\sigma)/\langle\sigma\rangle$ for known families
of shifts with sublinear complexity. We also formulate a notion of one-sided
coalescence in Theorem 2.5: Example 3.23 tell us that not every endomorphism
of a one-sided shift is an automorphism composed with a shift.

The proof of Theorem 2.3 is not constructive. Indeed, for an arbitrary shift
with sublinear complexity, it does not seem to be meaningful to ask for an
algorithm that computes its automorphism group: it is not clear what sort of
data it would take as input. Nevertheless the question of whether there exists
an algorithm to compute $\mbox{Aut}(X,\sigma)$ makes sense for substitution
shifts. In Section 3, we focus on this problem for the family of primitive
constant length $r$ substitutions. There we assume that our substitution
$\theta$ is primitive, constant-length, and generates an infinite shift.

We reprove Theorem 2.3 for these shifts, obtaining finer information. Our
proof techniques are a generalisation of Coven’s strategy in [3] for constant-
length substitutions on a two-letter alphabet. There, the fact that these
shifts are a somewhere one-to-one extension of their maximal equicontinuous
factor $\mathbb{Z}_{r}$ was used to associate to each automorphism a
“fingerprint” in $\mathbb{Z}_{r}$ which must satisfy certain constraints: we
re-state this technique in Theorem 3.3.

We show that for the case of larger alphabets a similar strategy works. Having
transferred our search to $\mathbb{Z}_{r}$, we prove in Lemma 3.14 that the
constraints mentioned above imply that the fingerprints of elements of
$\mbox{Aut}(X_{\theta},\sigma)$ are rational numbers with small denominators.
We use the arithmetic properties of odometers to show in Corollary 3.7 and the
note that follows it, that the automorphism groups of a large family of
Toeplitz shifts, including those generated by constant-length substitutions
with a coincidence, with height one are cyclic. The same arithmetic properties
imply that these shifts have trivial one-sided automorphism groups (Theorem
3.18). A technical detail is that not every rational that satisfies the
desired constraints is the fingerprint of some automorphism in
$\mbox{Aut}(X_{\theta},\sigma)$. In Propositions 3.19 and 3.21, we find
checkable conditions for the existence of an automorphism. Our arguments
culminate in Theorem 3.22, where we describe an algorithm to compute
$\mbox{Aut}(X_{\theta},\sigma)$. We illustrate our constructive methods with
some examples, including one where
$\langle\sigma\rangle\subsetneq\mbox{Aut}(X_{\theta},\sigma)$.

With some minor modifications, we can also describe in Section 3.7 an
algorithm to compute the set of conjugacies between two shifts generated by
constant-length substitutions. We note that Durand and Leroy [14] have
communicated to us that they have a result for arbitrary primitive
substitutions. Coven, Dekking and Keane [4] have an alternative proof of the
decidability of topological conjugacy of constant-length substitution shifts.
When we started the project, their decision procedure for testing conjugacy
was shown to terminate for many, but not all constant-length substitutions.
They have since proved that their procedure always terminates.

We remark that there is a common thread between the arguments in Section 2 and
Section 3, namely that in both cases we study an equivalence relation on the
points of $X$ (asymptotic equivalence and having a common image in the maximal
equicontinuous factor respectively). While most equivalence classes are small
(of size 1 and $c$, the column number, respectively), the larger equivalence
classes have to be mapped to themselves under automorphisms, leading to
restrictions on the collection of possible automorphisms.

##  2 Automorphisms of minimal shifts with sublinear complexity

###  2.1 Notation

Let $\mathcal{A}$ be a finite alphabet, with the discrete topology, and let
$\mathbb{N}_{0}=\\{0,1,2,\ldots\\}$. We endow $\mathcal{A}^{\mathbb{N}_{0}}$
and $\mathcal{A}^{\mathbb{Z}}$ with the product topology, and let
$\sigma:\mathcal{A}^{\mathbb{N}_{0}}\rightarrow\mathcal{A}^{\mathbb{N}_{0}}$
(or $\sigma:\mathcal{A}^{\mathbb{Z}}\rightarrow\mathcal{A}^{\mathbb{Z}}$)
denote the shift map. We consider only infinite minimal shifts $(X,\sigma)$,
which can be either one- or two-sided. An endomorphism of $(X,\sigma)$ is a
map $\Phi:X\rightarrow X$ which is continuous, onto, and commutes with
$\sigma$; if in addition $\Phi$ is one-to-one, then $\Phi$ is called an
automorphism. We say $\Phi$ has finite order m if $m$ is the least positive
integer such that $\Phi^{m}$ is the identity, and that $\Phi$ is a $k$-th root
of a power of the shift if there exists an $n$ such that
$\Phi^{k}=\sigma^{n}$. Let ${\mbox{Aut}}(X,\sigma)$ denote the automorphism
group of $(X,\sigma)$. If $X$ is two-sided, then $\mbox{Aut}(X,\sigma)$
contains the (normal) subgroup generated by the shift, denoted by
$\langle\sigma\rangle$.

The language of a minimal shift $(X,\sigma)$, denoted $\mathcal{L}_{X}$, is
the set of all finite words that occur in points of $X$. We denote by $p(n)$,
$n\geq 1$, the complexity function of $(X,\sigma)$: $p(n)$ is the number of
words (also called blocks) in $\mathcal{L}_{X}$ of length $n$. A symbolic
system $(X,\sigma)$ has sublinear complexity if its complexity function is
bounded by a linear function.

###  2.2  Automorphisms of minimal shifts with sublinear complexity

If $(\bar{X},\bar{\sigma})$ is a one-sided minimal shift, let $(X,\sigma)$
denote the two-sided version of $(\bar{X},\bar{\sigma})$ i.e. $X$ consists of
all bi-infinite sequences whose finite subwords belong to
$\mathcal{L}_{\bar{X}}$. Given a two-sided shift $(X,\sigma)$ we define
similarly its one-sided version. If $(\bar{X},\bar{\sigma})$ is minimal, then
the one-sided version of $(X,\sigma)$ is $(\bar{X},\bar{\sigma})$ itself.
Henceforth $(\bar{X},\bar{\sigma})$ refers to a one-sided shift and
$(X,\sigma)$ refers to a two-sided shift.

For $k>1$, we say that $\bar{x}\in\bar{X}$ is a branch point of order $k$ if
$|\sigma^{-1}(\bar{x})|=k$. If $(X,T)$ is a minimal invertible dynamical
system, we define an equivalence relation $\sim$ on orbits in $X$ as follows:
Two orbits $\mathcal{O}_{x}=\\{T^{n}(x):n\in\mathbb{Z}\\}$ and
$\mathcal{O}_{y}=\\{T^{n}(y):n\in\mathbb{Z}\\}$ in $X$ are right asymptotic,
denoted $\mathcal{O}_{x}\sim\mathcal{O}_{y}$, if there exists $m\in\mathbb{Z}$
such that $d(T^{m+n}x,T^{n}y)\to 0$ as $n\to\infty$. The right asymptotic
equivalence class of $\mathcal{O}_{x}$ will be denoted by $[x]$. A right
asymptotic equivalence class will be said to be non-trivial if it does not
consist of a single orbit. Clearly in the case that $X$ is a shift,
$\mathcal{O}_{x}$ and $\mathcal{O}_{y}$ are right asymptotic if there exists
$m$ such that $x_{m+n}=y_{n}$ for all $n$ sufficiently large.

######  Lemma 2.1.

Let $(\bar{X},\bar{\sigma})$ be an infinite minimal one-sided shift and let
$(X,\sigma)$ be the corresponding two-sided shift. If $(\bar{X},\bar{\sigma})$
has sublinear complexity, then $(\bar{X},\bar{\sigma})$ has finitely many
branch points, and $\\{\mathcal{O}_{x}\colon x\in X\\}$ has finitely many non-
trivial right asymptotic equivalence classes.

###### Proof.

We prove that if $(\bar{X},\bar{\sigma})$ has sublinear complexity, then
$(\bar{X},\bar{\sigma})$ has finitely many branch points, as the latter
implies that $\\{\mathcal{O}_{x}\colon x\in X\\}$ has finitely many non-
trivial right asymptotic equivalence classes.

Define for $n\geq 1$ the complexity difference function $s(n):=p(n+1)-p(n)$.
Since $(\bar{X},\bar{\sigma})$ has sublinear complexity, $s(n)$ is bounded
[2], say $s(n)\leq L$ for all $n\geq 1$. Then there are at most $L$ words of
length $n$ with at least two left extensions, and so there are at most $L$
branch points in $\bar{X}$. ∎

Next we have a basic lemma about automorphisms of minimal (not necessarily
symbolic) dynamical systems.

######  Lemma 2.2.

Let $(X,T)$ be a minimal dynamical system.

  1. 1.

Suppose $T$ is not invertible. If there is a point $x\in X$ and a finite
subset $F$ of $X$ such that $\Phi(x)\in F$ for every automorphism $\Phi$ of
$(X,T)$, then $|\mbox{Aut}(X,T)|\leq|F|$. In particular, every automorphism
has order at most $|F|$.

  2. 2.

Suppose $T$ is invertible. If there is a point $x\in X$ and a finite
collection $\mathcal{F}$ of right asymptotic equivalence classes such that
$[\Phi(x)]\in\mathcal{F}$ for every automorphism $\Phi$ of $(X,T)$, then
$|\mbox{Aut}(X,T)/\langle T\rangle|\leq|\mathcal{F}|$. In particular, the
order of each element of $\mbox{Aut}(X,T)/\langle T\rangle$ is at most
$|\mathcal{F}|$.

###### Proof.

For the first part, notice that an automorphism of a minimal dynamical system
is determined by its action on a single point.

For the second part, suppose that $\Phi$ and $\Psi$ are automorphisms of
$(X,T)$ such that $\mathcal{O}_{\Phi(x)}\sim\mathcal{O}_{\Psi(x)}$ for some
$x$. Let $m$ be such that $d(T^{n}(\Phi(x)),T^{n+m}(\Psi(x)))\to 0$. Then we
claim that $\Phi=\Psi\circ T^{m}$. For any $x^{\prime}\in X$, let $(n_{i})$ be
an increasing sequence of integers so that $T^{n_{i}}x\to x^{\prime}$. Now we
have

$\displaystyle\Phi(x^{\prime})$
$\displaystyle=\lim_{i\to\infty}\Phi(T^{n_{i}}x)=\lim_{i\to\infty}T^{n_{i}}\Phi(x)$
$\displaystyle=\lim_{i\to\infty}T^{n_{i}+m}\Psi(x)=\lim_{i\to\infty}\Psi(T^{m}(T^{n_{i}}x))=\Psi(T^{m}x^{\prime}),$

where for the third equality, we used that fact that $\mathcal{O}_{\Phi(x)}$
and $\mathcal{O}_{\Psi(x)}$ are right asymptotic. Hence we deduce that an
automorphism of $X$ is determined up to composition with a power of $T$ by the
right asymptotic equivalence class of the image of a single point. ∎

The following result tells us that for infinite minimal shifts with sublinear
complexity, $|\mbox{Aut}(X,\sigma)/\langle\sigma\rangle|$ is bounded by the
number of maximal sets of mutually right asymptotic orbits.

######  Theorem 2.3.

Let $(\bar{X},\bar{\sigma})$ be an infinite minimal one-sided shift and let
$(X,\sigma)$ be the corresponding two-sided shift. For $k>1$, let
$\bar{M}_{k}$ be the number of $k$-branch points in $\bar{X}$, and $M_{k}$ be
the number of $\sim$-equivalence classes of size $k$ in $X$. Suppose that
$(\bar{X},\bar{\sigma})$ has sublinear complexity, so that both $\bar{M}_{k}$
and $M_{k}$ are finite. Then

  1. 1.

$\mbox{Aut}(\bar{X},\bar{\sigma})$ has at most
$\bar{M}:=\min\\{\bar{M}_{k}\colon\bar{M}_{k}>0\\}$ elements, and

  2. 2.

$\mbox{Aut}(X,\sigma)/\langle\sigma\rangle$ has at most $M:=\min\\{M_{k}\colon
M_{k}>0\\}$ elements.

###### Proof.

Using Lemma 2.1, $\bar{X}$ has finitely many branch points and
$\\{\mathcal{O}_{x}\colon x\in X\\}$ has finitely many non-trivial right
asymptotic equivalence classes. The fact that the systems are infinite implies
that $\bar{X}$ (respectively $X$) has at least one branch point (respectively
one non-trivial right asymptotic equivalence class) so that $\bar{M}$ and $M$
are positive and finite.

Let $\bar{M}=\bar{M}_{k}$. Let $\bar{x}$ be a branch point of order $k$. An
automorphism $\bar{\Phi}$ of $(\bar{X},\bar{\sigma})$ must map branch points
of order $k$ to branch points of order $k$, so we apply Lemma 2.2(1), to the
set of branch points of order $k$, to obtain (1).

Similarly, let $M=M_{\ell}$ and let $x$ be such that $\mathcal{O}_{x}$ belongs
to an equivalence class consisting of $\ell$ orbits. If $\Phi$ is an
automorphism $(X,\sigma)$, then $\mathcal{O}_{\Phi(x)}$ must also belong to an
equivalence class consisting of $\ell$ orbits. Hence by Lemma 2.2(2), there
are at most $M_{\ell}$ automorphisms of $(X,\sigma)$ up to composition with a
power of $\sigma$. ∎

As $\mbox{Aut}(\bar{X},\bar{\sigma})$ and
$\mbox{Aut}(X,\sigma)/\langle\sigma\rangle$ are both finite groups, the order
of any element of $\mbox{Aut}(\bar{X},\bar{\sigma})$ divides
$|\mbox{Aut}(\bar{X},\bar{\sigma})|$, and any element of
$\mbox{Aut}(X,\sigma)$ is a $k$-th root of the shift, where $k$ divides
$|\mbox{Aut}(X,\sigma)/\langle\sigma\rangle|$.

###  2.3 Examples and bounds

####  2.3.1 Substitution shifts.

A substitution is a map from $\mathcal{A}$ to the set of nonempty finite words
on $\mathcal{A}$. We use concatenation to extend $\theta$ to a map on finite
and infinite words from $\mathcal{A}$. We say that $\theta$ is primitive if
there is some $k\in\mathbb{N}$ such that for any $a,a^{\prime}\in\mathcal{A}$,
the word $\theta^{k}(a)$ contains at least one occurrence of $a^{\prime}$. By
iterating $\theta$ on any fixed letter in $\mathcal{A}$, we obtain one-sided
(right) infinite points $u=u_{0}\ldots$ such that $\theta^{j}(u)=u$ for some
natural $j$. The pigeonhole principle implies that $\theta$-periodic points
always exist, and, for primitive substitutions, we define $\bar{X}_{\theta}$
to be the shift orbit closure of any one of these $\theta$-periodic points and
call $(\bar{X}_{\theta},\bar{\sigma})$ a one-sided substitution shift. Barge,
Diamond and Holton [1] show that a primitive substitution on $k$ letters has
at most $k^{2}$ right asymptotic orbits, so that we can apply Theorem 2.3 to
deduce that any automorphism of $(X_{\theta},\sigma)$ is a $j$-th root of a
power the shift for some $j\leq k^{2}$.

######  Example 2.4.

Let $\mathcal{A}=\\{a_{n},b_{n},c_{n}:1\leq n\leq N\\}$. Let $W$ be a word
which contains all of the letters in $\mathcal{A}$. Define a substitution,
$\theta$, by $\theta(a_{n})=Wa_{n}a_{n}$, $\theta(b_{n})=Wb_{n}a_{n}$ and
$\theta(c_{n})=Wc_{n}a_{n}$ for $1\leq n\leq N$. Now the one-sided shift
$(\bar{X}_{\theta},\bar{\sigma})$ contains $N$ branch points of order three,
$\\{x^{n}:1\leq n\leq N\\}$, where $x^{n}$ satisfies the equation
$a_{n}\theta(x^{n})=x^{n}$. Also, $\bar{X}_{\theta}$ contains only one other
branch point of order $N$: the unique right-infinite $\theta$-fixed point.
Similarly, in the two-sided shift $(X_{\theta},\sigma)$, there are exactly $N$
distinct right asymptotic equivalence classes of size 3, and one right
asymptotic equivalence class of size $N$. Now our bounds from Theorem 2.3 tell
us that each of $\mbox{Aut}(\bar{X}_{\theta},\bar{\sigma})$ and
$\mbox{Aut}(X_{\theta},\sigma)/\langle\sigma\rangle$ consist of one element.

We compare our bounds to those that would be obtained using the results in [8]
or [10]. In the latter, Theorem 3.1 tells us that
$|\mbox{Aut}(X)/\langle\sigma\rangle|$ divides $3N+1$, the number of non-
trivial right asymptotic equivalence classes. In the former, Theorem 1.4 tells
us that if $\liminf p(n)/n<k$, then $|\mbox{Aut}(X)/\langle\sigma\rangle|<k$.
If one takes the word $W=a_{1}b_{1}c_{1}a_{2}b_{2}c_{2}\dots a_{N}b_{N}c_{N}$,
a crude check shows that $\liminf p(n)/n\geq 3N/2$, so that the upper bound
for $|\mbox{Aut}(X)/\langle\sigma\rangle|$ coming from Theorem 1.4 of [8]
would be at least $3N/2$.

####  2.3.2 Linearly recurrent shifts

The notions below are the same for one-sided and two-sided shifts, so we will
state them only for two-sided shifts, thus avoiding the bars. If
$u,w\in\mathcal{L}_{X}$, we that $w$ is a return word to $u$ if (a) $u$ is a
prefix of $w$, (b) $wu\in\mathcal{L}_{X}$, and (c) there are exactly two
occurrences of $u$ in $wu$. Letting $\ell(u)$ denote the length of $u$, a
minimal shift $(X,\sigma)$ is linearly recurrent if there exists a constant
$K$ such that for any word $u\in\mathcal{L}_{X}$ and any return word (to $u$)
$w$, $\ell(w)\leq K\ell(u)$. Such a $K$ is called a recurrence constant.
Durand, Host and Skau show that if $(X,\sigma)$ has linear recurrence constant
$K$, then its complexity is bounded above by $Kn$ for large $n$ [13, Theorem
23]. Cassaigne [2] shows that if $p(n)\leq Kn+1$, then there are at most
$2K(2K+1)^{2}$ branch points and asymptotic orbits, and we can now apply
Theorem 2.3 to bound $|\mbox{Aut}(\bar{X},\bar{\sigma})|$ and
$|\mbox{Aut}(X,\sigma)/\langle\sigma\rangle|$ above by $2(K+1)(2K+3)^{2}$.

Durand [12, Corollary 18] shows that for linearly recurrent two-sided shifts,
any endomorphism is an automorphism. The corresponding one-sided version of
this is:

######  Theorem 2.5.

Let $(\bar{X},\bar{\sigma})$ be an infinite, minimal, linearly recurrent one-
sided shift with recurrence constant $K$. Then every endomorphism of
$(\bar{X},\bar{\sigma})$ is a $k$-th root of a power of the shift for some
positive $k\leq 2(K+1)(2K+3)^{2}$.

###### Proof.

Any endomorphism $\bar{\Phi}$ of $(\bar{X},\bar{\sigma})$ defines an
endomorphism $\Phi$ of $(X,\sigma)$, which must be an automorphism by [12,
Corollary 18]. By Cassaigne’s result, $\Phi^{k}=\sigma^{n}$ for some positive
$k\leq 2(K+1)(2K+3)^{2}$ and some $n\in\mathbb{Z}$, so
$\bar{\Phi}^{k}=\bar{\sigma}^{n}$. ∎

In Example 3.23 we describe a non-trivial endomorphism of
$(\bar{X},\bar{\sigma})$ which is not a power of the shift.

##  3 Constant length substitutions

Let $\theta$ be a substitution on the alphabet $\mathcal{A}$. The substitution
$\theta$ has (constant) length r if for each $a\in\mathcal{A}$, $\theta(a)$ is
a word of length $r$. In this section we generalise the results of Coven in
[3] to primitive constant-length substitutions on a finite alphabet. We then
provide algorithms to compute the automorphism group of a constant-length
substitution shift, and also the set of conjugacies between two constant-
length substitution shifts.

###  3.1 The $r$-adic integers

Let $\mathbb{Z}_{r}$ denote the set of $r$-adic integers, identified with the
one-sided shift space consisting of sequences $(x_{n})_{n\geq 0}$ with the
$x_{n}$’s taking values in $\\{0,1,\ldots,r-1\\}$. We think of these
expansions as being written from right to left, so that $\mathbb{Z}_{r}$
consists of left-infinite sequences of digits, $x_{0}$ is the rightmost digit
of $x$, and so that addition in $\mathbb{Z}_{r}$ has the carries propagating
to the left in the usual way. Formally $\mathbb{Z}_{r}$ is the inverse limit
of rings $\mathbb{Z}/r^{n}\mathbb{Z}$, and is itself a ring.

We make no assumption about the primality of $r$. If $r$ is not a prime power,
then $\mathbb{Z}_{r}$ has zero divisors. Nevertheless, if $k\in\mathbb{Z}$ and
$\gcd(k,r)=1$, then multiplication by $k$ is an isomorphism of
$\mathbb{Z}_{r}$ as an additive group, so that one can make sense of
expressions such as $m/k$ for $m\in\mathbb{Z}_{r}$ if $\gcd(k,r)=1$. If
$k\in\mathbb{Z}$ and $\gcd(k,r)>1$, then multiplication by $k$ is still an
injection of $\mathbb{Z}_{r}$. A version of the standard argument shows that
if $m$ and $k$ are integers with $\gcd(k,r)=1$, then $m/k$ has an eventually
periodic digit sequence; and conversely any point of $\mathbb{Z}_{r}$ with an
eventually periodic digit sequence can be written in the form $m/k$ for $m$
and $k$ in $\mathbb{Z}$ with $\gcd(k,r)=1$. We may naturally think of
$\mathbb{Z}$ as a subset of $\mathbb{Z}_{r}$: a point $s$ in $\mathbb{Z}_{r}$
whose digits are eventually all 0’s or eventually all $(r-1)$’s is the
$r$-adic expansion of an integer: we write $s\in\mathbb{Z}$. Note also that as
an additive group, $\mathbb{Z}_{r}$ is torsion free.

We need the following fact.

######  Lemma 3.1.

Let $kt\in\mathbb{Z}$ for some $t\in\mathbb{Z}_{r}$ and
$k\in\mathbb{Z}\setminus\\{0\\}$. Then there exists $m|k$ such that
$mt\in\mathbb{Z}$ and $\gcd(m,r)=1$.

###### Proof.

Let $k=lm$, where $\gcd(m,r)=1$ and $l|r^{n}$. Let $p:=r^{n}/l$ and $s:=mt$.
Now $r^{n}s=pkt\in\mathbb{Z}$. However, $r^{n}s\in r^{n}\mathbb{Z}_{r}$, which
is the set of elements of $\mathbb{Z}_{r}$ with at least $n$ trailing 0’s.
Dividing by $r^{n}$ removes these 0’s, showing that $s\in\mathbb{Z}$ as
required. ∎

######  Lemma 3.2.

Let $H$ be a subgroup of $\mathbb{Z}_{r}$ containing $\mathbb{Z}$ generated by
a collection of elements $(p_{i}/q_{i})_{i=1}^{n}$ with
$\gcd(p_{i},q_{i})=\gcd(q_{i},r)=1$. Then $H$ is generated by a single element
of the form $1/q$.

###### Proof.

Let $\alpha_{i}=p_{i}/q_{i}$ and $q=\mbox{Icm}(q_{1},\ldots,q_{n})$, so that
if $\tilde{p}_{i}:=p_{i}(q/q_{i})$ we have $q\alpha_{i}=\tilde{p}_{i}$ for
$i=1,\ldots,n$. Note that if $m$ is a prime and $m^{\alpha}|q$, with $\alpha$
maximal, then $m^{\alpha}|q_{i}$ for some $i$, so that $m\nmid p_{i}$ and
$m\nmid\tilde{p}_{i}$. Hence $\gcd(q,\tilde{p}_{1},\ldots,\tilde{p}_{n})=1$
and there exist integers $k_{0},k_{1},\ldots,b_{n}$ such that
$k_{0}q+k_{1}\tilde{p}_{1}+\ldots k_{n}\tilde{p}_{n}=1$. Then
$k_{0}+k_{1}\alpha_{1}+\ldots+k_{n}\alpha_{n}=1/q\in H$ and all of the
generators are multiples of $1/q$, so that $H$ is generated by $1/q$. ∎

###  3.2 Maximal equicontinuous factors

If $(X,T)$ is a continuous dynamical system, we say that the dynamical system
$(Y,S)$ is the maximal equicontinuous factor of $(X,T)$ if $(Y,S)$ is an
equicontinuous factor of $(X,T)$ with the property that any other
equicontinuous factor $(Z,R)$ of $(X,T)$ is a factor of $(Y,S)$. The maximal
equicontinuous factor of a minimal transformation is a rotation on a compact
monothetic topological group, that is a group $G$ for which there exists an
element $a$ such that the subgroup generated by $a$ is dense. Such a group is
always abelian [11] and we will write the group operation additively.

The systems we consider will have maximal equicontinuous factor
$(\mathbb{Z}_{r},+1)$ or $(\mathbb{Z}_{r}\times\\{0,\ldots,h-1\\},+1)$, where
the group operation on $\mathbb{Z}_{r}\times\\{0,\ldots,h-1\\}$ is

$(x,i)+(y,j)=\begin{cases}(x+y,i+j)&\text{if $i+j<h$;}\\\
(x+y+1,i+j-h)&\text{otherwise,}\end{cases}$

and where $r$ is not necessarily prime.

Let $\mbox{End}(X,\sigma)$ be the set of endomorphisms of $(X,\sigma)$. Given
two shifts $(X,\sigma)$ and $(Y,\sigma)$, let $\mbox{Conj}(X,Y)$ denote the
(possibly empty) set of topological conjugacies between $(X,\sigma)$ and
$(Y,\sigma)$, and let $\mbox{Fac}(X,Y)$ denote the set of factor maps from
$(X,\sigma)$ to $(Y,\sigma)$. For completeness we prove the following, which
is a straightforward generalization of work done by Coven in [3, §3].

######  Theorem 3.3.

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

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

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

  1. 1.

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

  2. 2.

if $\min_{g\in G}|\pi_{X}^{-1}(g)|=\min_{g\in G}|\pi_{Y}^{-1}(g)|=c<\infty$,
then

    1. (a)

for each $\Phi\in\mbox{Fac}(X,Y)$, we have

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

and

    2. (b)

$\kappa$ is at most $c$-to-one. In particular, if $\pi_{X}$ and $\pi_{Y}$ are
somewhere one-to-one, then $\kappa$ is an injection.

###### Proof.

First we show that given any factor map $\Phi:X\rightarrow Y$, there exists
$\kappa(\Phi)\in\mathbb{Z}_{r}$ such that
$\pi_{X}(x)+\kappa(\Phi)=\pi_{Y}(\Phi(x))$. Fix any $b\in X$, and define
$\kappa(\Phi):=\pi_{Y}(\Phi(b))-\pi_{X}(b)$. Notice that
$f(x)=\pi_{Y}(\Phi(x))-\pi_{X}(x)$ is a $T$-invariant continuous function.
Since $T\colon X\to X$ is minimal, it follows that $f(x)=f(b)=\kappa(\Phi)$
for all $x\in X$.

Thus for each factor mapping $\Phi:(X,\sigma)\rightarrow(Y,\sigma)$ there is a
map $F:G\to G$, namely $F(g):=g+\kappa(\Phi)$, such that
$\pi_{Y}\circ\Phi=F\circ\pi_{X}$. This gives us a map
$\kappa:\mbox{Fac}(X,Y)\rightarrow G$.

With the assumptions of (1), note that
$\pi_{Z}(\Psi\circ\Phi(x))=\kappa(\Psi\circ\Phi)+\pi_{X}(x)$, but also
$\pi_{Z}(\Psi\circ\Phi(x))=\kappa(\Psi)+\pi_{Y}(\Phi(x))=\kappa(\Psi)+\kappa(\Phi)+\pi_{X}(x)$,
and (1) follows.

Suppose that $\Phi\in\mbox{Fac}(X,Y)$. Let $|\pi_{Y}^{-1}(z)|>c$, so that
there exist distinct $y_{1},\ldots,y_{c+1}$ in $Y$ with $\pi_{Y}(y_{i})=z$ for
each $i$. Since $\Phi$ is surjective, there exist $x_{1},\ldots,x_{c+1}$ with
$\Phi(x_{i})=y_{i}$, and we have $\pi_{X}(x_{i})=z-\kappa(\Phi)$ for each
$x_{i}$. Hence $|\pi_{X}^{-1}(z-\kappa(\Phi))|>c$, so
$z\in\\{z^{\prime}\in\mathbb{Z}_{r}\colon|\pi_{X}^{-1}(z^{\prime})|>c\\}+\kappa(\Phi)$.

Let $t$ be in the range of $\kappa$, let $z\in\mathbb{Z}_{r}$ satisfy
$|\pi_{Y}^{-1}(z)|=c$ and let $x\in\pi_{X}^{-1}(z-t)$. Then if
$\kappa(\Phi)=t$, we have $\Phi(x)\in\pi_{Y}^{-1}(z)$. Since a factor map of a
minimal system is determined by its action on a single point, we deduce that
there are at most $c$ factor maps in $\mbox{Fac}(X,Y)$, proving (2b). ∎

###  3.3 Background results on constant-length substitutions

In this section, we collect some results that we use later to reduce the case
of general constant-length substitutions to cases that can be more
straightforwardly handled.

Let $\theta$ be a primitive length $r$ substitution with fixed point $u$, and
with $(X_{\theta},\sigma)$ infinite. The height $h=h(\theta)$ of $\theta$ is
defined as

$h(\theta):=\max\\{n\geq 1:\gcd(n,r)=1,n|\gcd\\{a:u_{a}=u_{0}\\}\\}\,.$

If $h>1$, this means that $\mathcal{A}$ decomposes into $h$ disjoint subsets:
$\mathcal{A}_{1}\cup\ldots\cup\mathcal{A}_{h}$, where a symbol from
$\mathcal{A}_{i}$ is always followed by a symbol from $\mathcal{A}_{i+1}$.
Such a system is a constant height suspension. In fact, as shown in [9, Remark
9, Lemmas 17 and 19], such a system is conjugate to a constant height
suspension of another constant-length substitution.

######  Proposition 3.4.

Let $\theta$ be a primitive, length $r$ substitution defined on $\mathcal{A}$,
such that $(X_{\theta},\sigma)$ is infinite. Then

  1. 1.

$h<|\mathcal{A}|$,

  2. 2.

there is a primitive length $r$ substitution shift
$(X_{\theta^{\prime}},\sigma^{\prime})$ of height one such that
$(X_{\theta},\sigma)\cong(X_{\theta^{\prime}}\times\\{0,\ldots,h-1\\},T)$
where

$T(x,i):=\begin{cases}(x,i+1)&\text{ if }0\leq i<h-1\\\
(\sigma^{\prime}(x),0)&\text{ if }i=h-1\end{cases}$

Furthermore $h$, $\theta^{\prime}$, and the conjugacy between
$(X_{\theta},\sigma)$ and $(X_{\theta^{\prime}}\times\\{0,\ldots,h-1\\},T)$
can be determined algorithmically.

The substitution $\theta^{\prime}$ described in Proposition 3.4 is called a
pure base of $\theta$.

For every $\Psi\in\mbox{Aut}(X_{\theta^{\prime}},\sigma^{\prime})$ and $0\leq
i\leq h-1$ we can define
$\Psi_{i}\in\mbox{Aut}(X_{\theta^{\prime}}\times\\{0,\ldots,h-1\\},T)$ as

$\Psi_{i}(x,j):=\begin{cases}(\Psi(x),j+i)&\text{ if }j+i<h\\\
(\Psi(\sigma^{\prime}(x)),j+i\mod h)&\text{ if }j+i\geq h.\end{cases}$

######  Proposition 3.5.

Let $\theta$ be a primitive, length $r$ substitution, of height $h$, and such
that $(X_{\theta},\sigma)$ is infinite. Let $\theta^{\prime}$ be a pure base
of $\theta$. Then
$\mbox{Aut}(X_{\theta},\sigma)=\\{\Psi_{j}:\Psi\in\mbox{Aut}(X_{\theta^{\prime}},\sigma^{\prime})\mbox{
and }0\leq j<h\\}.$

###### Proof.

By Proposition 3.4, $(X_{\theta},\sigma)$ is conjugate to
$(X_{\theta^{\prime}}\times\\{0,\ldots,h-1\\},T)$, and so
$\mbox{Aut}(X_{\theta},\sigma)$ is group isomorphic to
$\mbox{Aut}(X_{\theta^{\prime}}\times\\{0,\ldots,h-1\\},T)$. By the definition
of $\Psi_{i}$, we see that
$\\{\Psi_{j}:\Psi\in\mbox{Aut}(X_{\theta^{\prime}},\sigma^{\prime})\mbox{ and
}0\leq
j<h\\}\subset\mbox{Aut}(X_{\theta^{\prime}}\times\\{0,\ldots,h-1\\},T)$.

Conversely, given
$\Psi\in\mbox{Aut}(X_{\theta^{\prime}}\times\\{0,\ldots,h-1\\},T)$, suppose
that $\Psi(x,0)\in X_{\theta^{\prime}}\times\\{i\\}$ for some $x\in
X_{\theta^{\prime}}$. Define $f(x)=\pi_{2}(\Psi(x,0))$, where $\pi_{2}$ is the
projection onto the second coordinate and notice that $f$ is a continuous
$\sigma^{\prime}$-invariant function on $X_{\theta^{\prime}}$ and hence is
constant. This, and the fact $\Psi$ commutes with $T$ implies that
$\Psi=\Psi^{\prime}_{i}$ for some
$\Psi^{\prime}\in\mbox{Aut}(X_{\theta^{\prime}},\sigma^{\prime})$. ∎

Proposition 3.5 tells us that in order to compute the automorphism group of a
primitive constant-length substitution, or, as we shall see later, the set of
conjugacies between two such substitutions, it is sufficient to work with with
a pure base $\theta^{\prime}$ of $\theta$. Thus, apart from the statements of
our main results Theorems 3.22 and 3.27, and Corollary 3.7, we henceforth
assume that our substitutions are of height one.

Let $\theta$ be a length $r$ substitution. We write
$\theta(a)=\theta_{0}(a)\ldots\theta_{r-1}(a)$; with this notation we see that
for each $0\leq i\leq r-1$, we have a map
$\theta_{i}:\mathcal{A}\rightarrow\mathcal{A}$ where $\theta_{i}(a)$ is the
$(i+1)$-st letter of $\theta(a)$.

Let $\theta$ have pure base $\theta^{\prime}$. We say that $\theta$ has column
number $c$ if for some $k\in\mathbb{N}$, and some $(i_{1},\ldots,i_{k})$,
$|\theta^{\prime}_{i_{1}}\circ\ldots\circ\theta^{\prime}_{i_{k}}(\mathcal{A})|=c$
and $c$ is the least such number. In particular, if $\theta$ has column number
one, then we will say that $\theta$ has a coincidence. If for each $0\leq
i\leq r-1$ and $a\neq b$, $\theta_{i}(a)\neq\theta_{i}(b)$, we say $\theta$ is
bijective. Henceforth we shall be working with primitive substitutions
$\theta$ which are length $r$ and such that $(X_{\theta},\sigma)$ is infinite.

The following is shown by Dekking [9], with partial results by Kamae [18] and
Martin [20].

######  Theorem 3.6.

Let $\theta$ be a primitive, length $r$ substitution, of height one, and such
that $(X_{\theta},\sigma)$ is infinite. Then the maximal equicontinuous factor
of $(X_{\theta},\sigma)$ is $(\mathbb{Z}_{r},+1)$.

Recall the map $\kappa$ as defined in Theorem 3.3.

######  Corollary 3.7.

Let $\theta$ be a primitive, length $r$ substitution, such that
$(X_{\theta},\sigma)$ is infinite.

  1. 1.

Let $\theta$ have height one. If $\kappa$ is injective (in particular if
$\theta$ has a coincidence), then $\mbox{Aut}(X_{\theta},\sigma)$ is cyclic.

  2. 2.

Let $\theta$ have height $h>1$ and $\theta^{\prime}$ be the pure base of
$\theta$. Suppose that $\kappa:X_{\theta^{\prime}}\rightarrow\mathbb{Z}_{r}$
is injective, so that
$\mbox{Aut}(X_{\theta^{\prime}},\sigma^{\prime})=\langle\Phi\rangle$ with
$\kappa(\Phi)=1/k$. Then $\mbox{Aut}(X_{\theta},\sigma)$ is abelian and
generated by $T$ and $\Phi_{0}$ (in the above notation). Further,
$\mbox{Aut}(X_{\theta},\sigma)$ is cyclic if and only if $\gcd(k,h)=1$.

###### Proof.

Let $\theta$ be as in the statement, and first suppose that $\theta$ has
height one, so that its maximal equicontinuous factor is
$(\mathbb{Z}_{r},+1)$. By the discussion in Section 2.3.1 and Theorem 2.3,
$\mbox{Aut}(X_{\theta},\sigma)$ is finitely generated. Let a set of generators
be $\Phi_{0}=\sigma,\Phi_{1},\ldots,\Phi_{n}$, say. Then Theorem 2.3 implies
$\kappa(\Phi_{0})=1$ and $\kappa(\Phi_{i})=p_{i}/q_{i}$ for each $i$ for some
$p_{i}\in\mathbb{Z}$ and $q_{i}\geq 1$. By Lemma 3.2,
$\kappa(\mbox{Aut}(X_{\theta},\sigma))$ is cyclic. The result follows from the
injectivity of $\kappa$. In particular, since substitutions with coincidences
are precisely those whose shifts are a somewhere one-to-one extension of their
maximal equicontinuous factor [9], we deduce by Theorem 2.3 that if $\theta$
has a coincidence, then $\mbox{Aut}(X_{\theta},\sigma)$ is cyclic.

If $\theta$ has height $h>1$, let $\theta^{\prime}$ be the pure base of
$\theta$. We assume that $\theta^{\prime}$ has a coincidence. By the above,
$\mbox{Aut}(X_{\theta^{\prime}},\sigma^{\prime})$ is cyclic, and generated by
some $\Phi$ with $\kappa(\Phi)=1/k$ for some $k\in\mathbb{N}$. Suppose that
$\gcd(h,k)=1$ and let $ah+bk=1$ with $0\leq b<h$. Then consider the
automorphism $\Psi$ of $X_{\theta^{\prime}}\times\\{0,1,\ldots,h-1\\}$ given
by $\Psi(x,i)=(\Phi^{a}(x),i+b)$ if $i+b<h$ or
$(\Phi^{a}(\sigma^{\prime}(x)),i+b-h)$ otherwise (that is
$\Psi=(\Phi^{a})_{b}$ in the previous notation). Define an equivalence
relation on $X_{\theta^{\prime}}\times\mathbb{Z}$ to be the transitive closure
of $(\sigma^{\prime}(x),i)\sim(x,i+h)$ so that
$X_{\theta^{\prime}}\times\\{0,\ldots,h-1\\}$ is a system of representatives
of the equivalence classes. In this notation, $\Psi(x,i)=(\Phi^{a}(x),i+b)$.
Notice that $\Psi^{k}(x,i)=(\Phi^{ak}(x),i+kb)=(\sigma^{\prime
a}x,i+kb)\sim(x,i+kb+ah)=(x,i+1)=T(x,i)$, so that $T\in\langle\Psi\rangle$.
Since $\gcd(a,k)=1$, some power of $\Phi^{a}$ is of the form
$\Phi\circ{\sigma^{\prime}}^{m}$. Hence $\Phi_{0}\in\langle\Psi\rangle$ also,
so that $\mbox{Aut}(X_{\theta},\sigma)$ is cyclic as required.

Conversely if $\gcd(h,k)=d>1$, then let $\Psi=\Phi_{0}^{k/d}\circ T^{-h/d}$.
We have $\Psi\neq\mbox{Id}$, but $\Psi^{d}=\mbox{Id}$. Since infinite cyclic
groups are torsion-free, we see that $\mbox{Aut}(X_{\theta},\sigma)$ is not
cyclic.

∎

Substitutions for which $\gcd(h,k)>1$ can be constructed. For, starting with a
(primitive, nonperiodic) substitution with a coincidence on two letters, its
automorphism group equals $\mathbb{Z}$ [3]. We can use the techniques in
Example 3.23 to obtain a substitution shift $(X_{\theta}^{\prime},\sigma)$,
the $\kappa$ values of whose automorphism group is
$\langle\frac{1}{k}\rangle$. Now building a tower of height $h$ over
$(X_{\theta}^{\prime},\sigma)$ gives us the desired substitution shift. We
remark also that Part (1) of Corollary 3.7 holds, with essentially the same
proof, for linearly recurrent Toeplitz systems [11] whose maximal
equicontinuous factor is $\mathbb{Z}_{r}$.

A constant-length substitution is called _injective_ if
$\theta(i)\neq\theta(j)$ for any distinct $i$ and $j$ in $\mathcal{A}$. It
will be convenient to deal with injective substitutions in what follows. The
following theorem of Blanchard, Durand and Maass allows us to restrict our
attention to that situation.

######  Theorem 3.8 ([15]).

Let $\theta$ be a constant-length substitution such that $X_{\theta}$ is
infinite. Then there exists an injective substitution $\theta^{\prime}$ such
that $(X_{\theta},\sigma)$ is topologically conjugate to
$(X_{\theta^{\prime}},\sigma)$. Further, the conjugacy and its inverse are
explicitly computable, so that $\mbox{Aut}(X_{\theta},\sigma)$ can be
determined algorithmically from $\mbox{Aut}(X_{\theta^{\prime}},\sigma)$.

###### Proof.

We only sketch the proof that the inverse of the conjugacy is computable, as
this is not described in [15]. There, we see that $(X_{\theta},\sigma)$ is
conjugate to $(X_{\theta^{\prime}},\sigma)$ via $\tau$, which is a composition
of less than $|\mathcal{A}|$ algorithmically-determined letter-to-letter maps,
$\tau=\tau_{1}\circ\ldots\tau_{N}$. By iteration, it suffices to show that a
single one of these maps has a computable inverse, so we assume that $N=1$ and
$\tau_{1}=\tau$.

By definition, $\theta\circ\tau=\theta$, so that to explicitly describe
$\tau^{-1}$, we only need explicitly describe $\theta^{-1}$. If $\theta$ is a
constant-length substitution on $\mathcal{A}$, then there exists
$k\leq|\mathcal{A}|^{2}$ such that if $\theta^{k}(a)=\theta^{k}(b)$, then
$\theta^{k-1}(a)=\theta^{k-1}(b)$. Fix any letter $a$. The bilateral
recognizability of $\theta^{k}$ [22, Definition 1.1 and Theorem 3.1] implies
that there exists an $\ell\geq k$ such that $\theta^{\ell}(a)$ does not appear
starting at the interior of any $\theta^{k}$ word. Such an $\ell$ can be
obtained by a simple algorithm. Uniform recurrence of $(X_{\theta},\sigma)$
implies that if $L$ is large enough, then any word of length $L$ in
$\mathcal{L}_{X_{\theta}}$ contains some $\theta^{\ell}(a)$ as a subword.
Also, this $L$ is computable [13, Proposition 25]. Thus $\theta^{-1}$ can be
explicitly described and the proof of our claim is complete. ∎

###  3.4 The description of $\\{z\in\mathbb{Z}_{r}:|\pi^{-1}(z)|>c\\}$

We continue to assume that $\theta$ is a length $r$ substitution of height
one, so that $\mathbb{Z}_{r}$ is the maximal equicontinuous factor of
$(X_{\theta},\sigma)$. We let $c$ be the column number of $\theta$. We show
that all points of $\mathbb{Z}_{r}$ have at least $c$ preimages and most
points of $\mathbb{Z}_{r}$ have exactly $c$ preimages. We study the structure
of the subset of $\mathbb{Z}_{r}$ having excess preimages.

If $P_{0}:=\theta^{n}(X_{\theta})$, then $P_{0}$ generates a
$\sigma^{r^{n}}$-cyclic partition of size $r^{n}$ [9, Lemma II.7]. We use the
notation of [18], [9], using $\Lambda_{r^{n}}$ to denote the equivalence
relation whose classes are the members of this cyclic
$\sigma^{r^{n}}$-partition, i.e. we write $\Lambda_{r^{n}}(x)=i$ if
$x\in\sigma^{i}(P_{0})$.

Using the maps $\Lambda_{n}$, we can define a maximal equicontinuous factor
map $\pi:X_{\theta}\rightarrow\mathbb{Z}_{r}$. Note that if
$\Lambda_{n}(x)=i$, then $\Lambda_{n+1}(x)\equiv i\mod r^{n}$. Using this we
can define $\pi(x):=\ldots x_{2}\,x_{1}\,x_{0}$ where for each
$n\in\mathbb{N}$, $\Lambda_{n}(x)=\sum_{i=0}^{n-1}r^{i}x_{i}$.

######  Definition 1.

Let $\theta$ be a length $r$ substitution with column number $c$ and of height
one. Let $\Sigma_{\theta}$ be the one-sided shift on $\\{0,1,\ldots,r-1\\}$,
whose points are left-infinite, and whose set of forbidden words is

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

Note that $\mathcal{F}_{\theta}\neq\emptyset$. It can happen that
$\Sigma_{\theta}=\emptyset$: this is the case for the Thue-Morse substitution:
$\theta(0)=01,\theta(1)=10$.

######  Lemma 3.9.

Let $\theta$ be a primitive, length $r$ substitution on $\mathcal{A}$ with
column number $c$, of height one, and such that $(X_{\theta},\sigma)$ is
infinite. Then $\Sigma_{\theta}$ is either empty or a sofic shift.

###### Proof.

Let
$S=\\{\mathcal{A}\\}\cup\\{\theta_{w_{1}}\circ\cdots\circ\theta_{w_{k}}(\mathcal{A})\colon
k\geq 1;\;w_{1},\ldots,w_{k}\in\\{0,1,\ldots,r-1\\}\\}$ and $V=\\{A\in
S\colon|A|>c\\}$. This is the vertex set of a directed labelled graph. If
$A\in V$ and $\theta_{i}(A)\in V$, then we add an edge from $\theta_{i}(A)$ to
$A$ labelled with the symbol $i$. We claim that the set $\Sigma_{\theta}$ is
the set of left-infinite one-sided sequences in
$(\mathbb{Z}/r\mathbb{Z})^{\mathbb{N}}$ such that for every $m<n$ and finite
segment, $w_{n-1}w_{n-2}\ldots w_{m}$, the sequence $(w_{m},w_{m+1},\ldots
w_{n-1})$ is the sequence of labels of a path in the graph. To see this,
notice that $(w_{m},w_{m+1},\ldots,w_{n-1})$ is the sequence of labels of a
path in the graph if and only if there are elements
$A_{m},A_{m+1},\ldots,A_{n}$ of $V$ such that $\theta_{w_{k}}(A_{k+1})=A_{k}$
for each $m\leq k<n$, so that
$|\theta_{w_{m}}\circ\theta_{w_{m+1}}\circ\cdots\theta_{w_{n-1}}(A_{n})|=|A_{m}|>c$
and hence
$|\theta_{w_{m}}\circ\theta_{w_{m+1}}\circ\cdots\theta_{w_{n-1}}(\mathcal{A})|>c$.

The reason for the reversal of the order of the indices is that we want to
maintain compatibility with standard definitions of sofic: $\Sigma_{\theta}$
is a collection of left-infinite sequences, which is precisely the collection
of edge-labellings of infinite paths in the graph _listed in reverse order_.

∎

######  Example 3.10.

[3]. If $|\mathcal{A}|=2$, then any primitive length $r$ substitution
generating an infinite shift has height one, by Proposition 3.4, and for each
$i$, $\theta_{i}(\mathcal{A})=\mathcal{A}$ or $|\theta_{i}(\mathcal{A})|=1$.
If $\mathcal{C}$ is the set of indices $i$ such that
$|\theta_{i}(\mathcal{A})|=1$, we see that
$\mathcal{F}_{\theta}=\\{w=w_{1}\ldots
w_{k}\in(\mathbb{Z}/r\mathbb{Z})^{+}:w_{i}\in\mathcal{C}\text{ for some
}i\in\\{1,\ldots,k\\}\\}$. In this case $\Sigma_{\theta}$ is the full shift on
the alphabet $(\mathbb{Z}/r\mathbb{Z})\backslash\mathcal{C}$.

######  Example 3.11.

Let $\mathcal{A}=\\{a,b,c\\}$, and let $\theta(a)=abbc$, $\theta(b)=cbab$ and
$\theta(c)=cbba$; $\theta$ has a coincidence and is of height one. The
labelled graph that generates $\Sigma_{\theta}$ is shown in Figure 1.

$\\{a,b,c\\}$$\\{a,b\\}$$\\{a,c\\}$$\\{b,c\\}$0032,3220,33 Figure 1: The graph
for Example 3.11.

Depending on $\theta$, we may have to slightly alter the sofic shift that we
work with. We write $\overline{a}$ to denote $\ldots aaa$.

######  Definition 2.

Let $\theta$ be a length $r$ substitution with column number $c$. Let
$\Sigma_{\theta}$ be as above. Let $P=\\{x\in
X_{\theta}\colon\theta^{n}(x)=x\text{ for some $n$}\\}$, that is the set of
(two-sided) periodic points under the substitution.

$\hat{\Sigma}_{\theta}:=\begin{cases}\Sigma_{\theta}\cup\\{\overline{0},\overline{r-1}\\}&\text{
if $|P|>c$}\\\ \Sigma_{\theta}&\text{ otherwise;}\end{cases}$

if $\Sigma_{\theta}$ is sofic, then $\hat{\Sigma}_{\theta}$ is sofic. We shall
show below (in Corollary 3.13) that $\hat{\Sigma}_{\theta}$ is not empty and
hence by the definition above, $\hat{\Sigma}_{\theta}$ is always sofic. Define

$\tilde{\Sigma}_{\theta}=\\{x:\sigma^{n}(x)\in\hat{\Sigma}_{\theta}\mbox{ for
some }n\geq 0\\}.$

######  Lemma 3.12.

Let $\theta$ be a primitive, length $r$ substitution, with column number $c$,
of height one and such that $(X_{\theta},\sigma)$ is infinite. Then
$\tilde{\Sigma}_{\theta}=\\{z\in\mathbb{Z}_{r}:|\pi^{-1}(z)|>c\\}$.

###### Proof.

We separate the proof into two parts: $z\in\mathbb{Z}$ and
$z\not\in\mathbb{Z}$.

First suppose $z\in\mathbb{Z}$ and $|\pi^{-1}(z)|>c$. Then there are more than
$c$ $\theta$-periodic points, so that
$z\in\mathbb{Z}\subset\tilde{\Sigma}_{\theta}$.

For the converse, notice that if either $0^{j}\not\in\mathcal{F}_{\theta}$ for
all $j$ or $(r-1)^{j}\not\in\mathcal{F}_{\theta}$ for all $j$, then there are
more than $c$ one-sided right- or left- $\theta$-periodic points respectively.
By primitivity, each one-sided $\theta$-periodic point extends to at least one
two-sided $\theta$-periodic point, so that we deduce that if
$\mathbb{Z}\cap\tilde{\Sigma}_{\theta}$ is non-empty then there are more than
$c$ $\theta$-periodic points. Hence if
$z\in\mathbb{Z}\cap\tilde{\Sigma}_{\theta}$, we see $|\pi^{-1}(z)|>c$.

If $z\in\tilde{\Sigma}_{\theta}\setminus\mathbb{Z}$, then there exists $n_{0}$
such that for all $n\geq n_{0}$, $z_{n}\ldots
z_{n_{0}}\not\in\mathcal{F}_{\theta}$. We may assume without loss of
generality (since $|\pi^{-1}(z)|=|\pi^{-1}(z+k)|$ for any $k\in\mathbb{Z}$)
that $z_{n_{0}-1},\ldots,z_{0}$ are all 0. Let
$z^{\prime}=\bar{\sigma}^{n_{0}}z$, so that for all $n\geq 0,$
$z^{\prime}_{n-1}\ldots z^{\prime}_{0}\not\in\mathcal{F}_{\theta}$. This means
that for each $n$ there are distinct letters
$\bar{a}_{n}^{(1)},\ldots,\bar{a}_{n}^{(c+1)}$, and letters
$a_{n}^{(1)},\ldots,a_{n}^{(c+1)}$ such that
$\theta_{z^{\prime}_{0}}\circ\ldots\circ\theta_{z^{\prime}_{n-1}}(a_{n}^{(i)})=\bar{a}_{n}^{(i)}$
for $1\leq i\leq c+1$. By passing to a subsequence we can assume that
$(a_{n}^{(1)},\ldots,a_{n}^{(c+1)})=(a_{1},\ldots,a_{c+1})$ and
$(\bar{a}_{n}^{(1)},\ldots,\bar{a}_{n}^{(c+1)})=(\bar{a}_{1},\ldots,\bar{a}_{c+1})$
for all $n$.

For $i=1,\ldots,c+1$, take $x^{(n),i}\in X$ such that for each $i$,
$x^{(n),i}_{0}=\bar{a}_{i}$, $\pi(x^{(n),i})$ ends with
$z^{\prime}_{n-1}\ldots z^{\prime}_{0}$ and the segment of $x^{(n),i}$ from
coordinate index $-\sum_{i=0}^{n-1}z^{\prime}_{i}r^{i}$ to
$r^{n}-1-\sum_{i=0}^{n-1}z^{\prime}_{i}r^{i}$ agrees with $\theta^{n}(a_{i})$.
Taking limits gives at least $c+1$ distinct points of $\pi^{-1}(z^{\prime})$.
Since $\theta$ is injective and $\theta^{n_{0}}x\in\pi^{-1}(z)$ for any
$x\in\pi^{-1}(z^{\prime})$, applying $\theta^{n_{0}}$ to these points shows
$|\pi^{-1}(z)|\geq c+1$.

If $z\not\in\tilde{\Sigma}_{\theta}\cup\mathbb{Z}$, then for infinitely many
$n$, there exist $k_{n}$ such that $z_{n+k_{n}}\ldots
z_{n}\in\mathcal{F}_{\theta}$. Let $x=(x_{j})$ satisfy $\pi(x)=z$ and fix $n$.
Since $|\theta_{z_{n}}\circ\ldots\circ\theta_{z_{n+k_{n}}}(\mathcal{A})|=c$,
there are $c$ possible choices for the block of $x_{j}$’s for
$j\in[0,r^{n}-1]-\sum_{i=0}^{n-1}r^{i}z_{i}$. Since $z\not\in\mathbb{Z}$, the
union of these intervals exhausts all of $\mathbb{Z}$. ∎

######  Corollary 3.13.

Let $\theta$ be a primitive, length $r$ substitution defined on $\mathcal{A}$
with column number $c$, of height one, and such that $(X_{\theta},\sigma)$ is
infinite. Then the function
$|\pi^{-1}(z)|:\mathbb{Z}_{r}\rightarrow\mathbb{N}$ has minimum value $c$, is
non-constant, and $\hat{\Sigma}_{\theta}$ is a nonempty and proper subset of
$\mathbb{Z}_{r}$.

###### Proof.

Let $z\in\mathbb{Z}_{r}$ and for each $a\in\mathcal{A}$, let $x^{(a)}\in
X_{\theta}$ satisfy $x^{(a)}_{0}=a$. Let
$y^{(n,a)}=\sigma^{m_{n}}\theta^{n}(x^{(a)})$, where
$m_{n}=z_{n-1}r^{n-1}+\ldots+z_{1}r+z_{0}$. Let $Y^{(n)}=\\{y^{(n,a)}\colon
a\in\mathcal{A}\\}$ and let $Y^{(\infty)}$ be the set of accumulation points
of $Y^{(n)}$ as $n\to\infty$. The 0th coordinates of the $y^{(n,a)}$ exhaust
$\theta_{z_{0}}\circ\theta_{z_{1}}\circ\cdots\theta_{z_{n-1}}(\mathcal{A})$,
so that $|Y^{(n)}|\geq c$, and also $|Y^{(\infty)}|\geq c$. Since
$Y^{(\infty)}$ is a subset of $\pi^{-1}(z)$, we conclude $|\pi^{-1}(z)|\geq c$
for each $z\in\mathbb{Z}_{r}$.

Since $\mathcal{F}_{\theta}\neq\emptyset$, we take a word
$w\in\mathcal{F}_{\theta}$, and then a point
$z\in\mathbb{Z}_{r}\backslash\mathbb{Z}$ which contains $w$ infinitely often.
Then $z\not\in\tilde{\Sigma}_{\theta}$, and by Lemma 3.12, $|\pi^{-1}(z)|=c$.

To see that there exist points $z$ with $|\pi^{-1}(z)|>c$, we note that our
shifts will always have at least one non-trivial right asymptotic orbit
equivalence class. This follows from the fact that any continuous, positively
expansive map on an infinite compact metric space cannot be invertible [7]. We
pick $x$ and $x^{\prime}$ that are right asymptotic, and we suppose that
$x_{n}=x^{\prime}_{n}$ for $n\geq 0$. Let $z=\pi(x)=\pi(x^{\prime})$. The sets
$\theta_{z_{0}}\circ\theta_{z_{1}}\ldots\theta_{z_{n}}(\mathcal{A})$ are
decreasing in $n$ and so equal $\mathcal{A}_{0}$, a set of cardinality at
least $c$, for all large $n$. For each $a\in\mathcal{A}_{0}$, there is a $y$
in $\pi^{-1}z$ with $y_{0}=a$. As $x$ and $x^{\prime}$ are two elements in
$\pi^{-1}z$ with the same 0 coordinate, we conclude that $|\pi^{-1}z|\geq
c+1$. ∎

###  3.5 Bounding denominators of $\kappa(\Phi)$

We have established that if $\theta$ has column number $c$, then the set
$\\{z:|\pi^{-1}(z)|>c\\}$ is the set of points whose tail lies in a sofic
shift that is a proper subshift of the full one-sided shift on $r$ letters,
that is $\tilde{\Sigma}_{\theta}$. Although we already know that
$\kappa(\Phi)$ is rational for $\Phi\in\mbox{Aut}(X_{\theta},\sigma)$, Part
(2) of Theorem 3.3 tells us that
$\tilde{\Sigma}_{\theta}\subset\tilde{\Sigma}_{\theta}+\kappa(\Phi)$, which
will allow us to give bounds on the denominator of $\kappa(\Phi)$. We also
recover a special case of a result in [13], namely that for our shifts, all
endomorphisms are automorphisms.

We write $d$ for the $r$-adic metric: $d(x,y)=r^{-k}$, where $k=\min\\{j\colon
x_{j}\neq y_{j}\\}$ (or $d(x,y)=0$ if $x=y$). We also need a metric on the
circle. We identify the circle with $[0,1)$ and define
$d_{\circ}(x,y)=\min_{n\in\mathbb{Z}}|n+(x-y)|$.

If $X$ is a subshift of $\mathbb{Z}_{r}$, we say that $x$ has a _tail_
belonging to $X$ if there exists $k\in\mathbb{N}$ such that $\sigma^{k}(x)\in
X$.

######  Lemma 3.14.

Let $X$ be a proper sofic shift of $\mathbb{Z}_{r}$, so that there is a word
of length $j$ that does not occur in the language of $X$. Suppose that there
exists $t\in\mathbb{Z}_{r}$ such that $x+t$ has a tail belonging to $X$ for
each $x\in X$. Then $nt\in\mathbb{Z}$ for some $n$ satisfying $\gcd(n,r)=1$
and $n\leq r^{j}-1$.

######  Lemma 3.15.

Let $\Omega$ be an infinite subset of $S^{1}$. Then for each $\epsilon>0$,
there exists an $N$ such that $N\star\Omega:=\\{n\omega\colon 1\leq n\leq N;\
\omega\in\Omega\\}$ is $\epsilon$-dense.

###### Proof.

If $\Omega$ contains an irrational point, then its multiples are dense and
we’re done. Otherwise if $\Omega\subset\mathbb{Q}$, given $\epsilon$, since
$\Omega$ is infinite, it must contain a point $\frac{p}{q}$ (in lowest terms)
with $q>1/\epsilon$. Now $\\{j\cdot\frac{p}{q}\bmod 1:j\in\mathbb{N}_{0}\\}$
exhausts $\\{\frac{i}{q}\colon 0\leq i<q\\}$, so that $q\star\Omega$ is
$\epsilon$-dense. ∎

###### Proof of Lemma 3.14.

Define $\psi_{n}\colon\mathbb{Z}_{r}\to S^{1}$ by
$\psi_{n}(x)=\sum_{k=0}^{n-1}x_{k}r^{k-n}$. For $\omega\in S^{1}$, we denote
$r\omega\bmod 1$ by $rs$. Let $\Omega(t)\subset S^{1}$ be the set of limit
points of $\\{\psi_{n}(t):n\in\mathbb{N}_{0}\\}$. Notice that if
$\psi_{n_{i}}(t)\to\omega$, then $\psi_{n_{i}-1}(t)\to r\omega$, so that
$\Omega(t)$ is closed under multiplication by $r$. Also
$\Omega(mt)=m\Omega(t)$ and $\Omega(m+t)=\Omega(t)$ for $m\in\mathbb{Z}$.

We first claim that if $t$ is not rational, or if $t$ is rational with a
denominator exceeding $r^{j}$, then there exists an $m$ such that $\Omega(mt)$
contains an element of $S^{1}$ in $(r^{-j}/2,r^{-j})$.

Suppose first that $\Omega(t)$ is a finite set. Since it is closed under
multiplication by $r$, it must consist of rationals (given
$\omega\in\Omega(t)$, there exist $0\leq m<n\leq|\Omega(t)|$ such that
$r^{m}\omega$ and $r^{n}\omega$ agree modulo 1, so that
$(r^{n}-r^{m})\omega\in\mathbb{Z}$). In particular, by taking a least common
multiple, there exists a $Q\in\mathbb{N}_{0}$ such that $Q\omega=0\bmod 1$ for
all $\omega\in\Omega(t)$. Now as $d_{\circ}(\psi_{n}(t),\Omega(t))\to 0$, we
have $d_{\circ}(\psi_{n}(Qt),0)=d_{\circ}(Q\psi_{n}(t),Q\Omega(t))\to 0$. This
implies $Qt\in\mathbb{Z}$, so that this is the rational case. By assumption,
the denominator of $t$ exceeds $r^{j}$. By Lemma 3.1, we can write $t$ as
$p/q$ with $\gcd(p,q)=\gcd(q,r)=1$. Then there exist $a,m\in\mathbb{Z}$ such
that $mt=a-1/q$ in $\mathbb{Z}_{r}$. Now $\Omega(mt)=\Omega(-1/q)$. Since $q$
is coprime to $r$, there exists a $b$ such that $r^{b}\equiv 1\pmod{q}$ (or
$q|r^{b}-1$). Write $r^{b}-1=sq$ and notice that the expansion of
$-1/q=s/(1-r^{b})$ in $\mathbb{Z}_{r}$ equals $\bar{s}=\ldots sss$ where
$\bar{s}$ has period $b$. Now we see $\psi_{bn}(-1/q)\to s/(r^{b}-1)=1/q$, so
that $1/q\in\Omega(mt)$. There exists an $l\in\mathbb{Z}$ such that
$l/q\in(r^{-j}/2,r^{-j})$ In particular, we have shown the claim above (for
$\Omega(lmt)$) in the case that $t$ is rational.

If $\Omega(t)$ is infinite, then by Lemma 3.15, there is an $M$ such that
$\bigcup_{m=1}^{M}\Omega(mt)$ is $1/(2r^{j}+1)$-dense. Hence there is an
$m\leq M$ such that $\Omega(mt)\cap(r^{-j}/2,r^{-j})\neq\emptyset$ completing
the proof of the claim.

There is a natural bijection $\Phi$ between $j$-blocks of $X$ and
$\mathbb{Z}/r^{j}\mathbb{Z}$: given a $j$-block $B=[x_{j-1}\ldots x_{0}]$,
$\Phi(B)=x_{j-1}r^{j-1}+\ldots+x_{0}$. (Recall that we are writing elements of
$\mathbb{Z}_{r}$ from right to left so that $x_{j-1}$ is the “most significant
digit” of $B$).

Hence for a $j$-block $B$, there is a natural notion of its successor $B+1$.
Let $B$ be chosen so that $B$ is a valid $j$-block, but $B+1$ is not. To show
that such a $B$ exists, list the $j$-blocks sequentially, each one the
successor of the previous one. At some point in the sequence there is a valid
$j$-block followed by an invalid one (otherwise all would be valid or all
would be invalid). Since $X$ is sofic, it has dense periodic points. Let $z$
be a periodic point in $X$ containing $B$’s. Let $p$ be the period of $z$.

By the above, there exist $\omega\in\Omega$ and $m$ such that
$\frac{1}{2}r^{-j}<m\omega\bmod 1<r^{-j}$. Since $\omega\in\Omega$, there
exists an increasing sequence $(n_{i})$ such that $\psi_{n_{i}}(t)\to\omega$.
For all sufficiently large $i$, $\frac{1}{2}r^{-j}<\psi_{n_{i}}(mt)<r^{-j}$.
Refine the sequence $(n_{i})$ such that
$\frac{1}{2}r^{-j}<\psi_{n_{i}}(mt)<r^{-j}$ for each $i$ and all of the
$n_{i}$ are congruent modulo $p$ (such a subsequence exists by the pigeonhole
principle: at least one congruence class must contain infinitely many terms of
the original sequence).

Now let $k$ be chosen so that the block $B$ appears in the coordinate range
$n_{i}-j$ to $n_{i}-1$ for each $i$ in $w:=\sigma^{k}(z)$. Let
$\alpha=\Phi(B)/r^{j}$. The fact that $B$ appears in these blocks is
equivalent to the assertion that $\psi_{n_{i}}(w)\in[\alpha,\alpha+r^{-j})$,
while the appearance of $B+1$ in locations $n-j$ to $n-1$ of $x\in X$ is
equivalent to the assertion that
$\psi_{n}(x)\in[\alpha+r^{-j},\alpha+2r^{-j})$.

Now notice that for each $i$, either $\psi_{n_{i}}(w+mt)$ or
$\psi_{n_{i}}(w+2mt)$ lies in $[\alpha+r^{-j},\alpha+2r^{-j})$. In particular,
one of $w+mt$ and $w+2mt$ contains infinitely many $B+1$ blocks, and hence
does not have a tail lying in $X$. Hence we have shown that if $t$ is
irrational, or $t$ is rational with denominator exceeding $r^{j}$, then the
hypotheses of the theorem cannot be satisfied. ∎

######  Theorem 3.16.

Let $\theta$ be a primitive, length $r$ substitution on $\mathcal{A}$, with
column number $c$, of height one, and such that $(X_{\theta},\sigma)$ is
infinite. Then $\mbox{End}(X_{\theta},\sigma)=\mbox{Aut}(X_{\theta},\sigma)$.

If $\mathcal{F}_{\theta}$ contains a word of length $j$, then any
$\Phi\in\mbox{Aut}(X_{\theta},\sigma)$ satisfies $\kappa(\Phi)=\ell/n$ for
some $n\leq r^{j}-1$ with $\gcd(n,r)=1$, and some $\ell\in\mathbb{Z}$, and
$\Phi^{nk}=\sigma^{\ell k}$ for some $1\leq k\leq c$.

###### Proof.

Let $\theta$ be a substitution as in the statement and let $\Sigma_{\theta}$,
$\hat{\Sigma}_{\theta}$ and $\tilde{\Sigma}_{\theta}$ be as constructed above.
Let $\Phi$ be an endomorphism of $X_{\theta}$ and let $t=\kappa(\Phi)$. By
Theorem 3.3, Lemma 3.12 and Corollary 3.13, we have
$t+\tilde{\Sigma}_{\theta}\subset\tilde{\Sigma}_{\theta}$. By Lemma 3.14, we
deduce $t$ is rational, $\ell/n$ say, with denominator coprime to $r$ and at
most $r^{j}-1$.

Now $\kappa(\Phi^{n}\sigma^{-\ell})=0$, so that $\Phi^{n}\sigma^{-\ell}$ is a
self-map of $\pi^{-1}(z)$ for any $z$ in $\mathbb{Z}_{r}$. Choosing $z$ so
that $|\pi^{-1}(z)|=c$, we see that there is a $1\leq k\leq c$ such that
$(\Phi^{n}\sigma^{-\ell})^{k}$ has a fixed point. By minimality of
$X_{\theta}$, $\Phi^{nk}=\sigma^{\ell k}$ and we see that $\Phi$ is bijective,
so $\Phi\in\mbox{Aut}(X_{\theta},\sigma)$. ∎

######  Example 3.17.

We continue with Example 3.11, which we already noted has a coincidence and is
of height one. Since the word 1 belongs to $\mathcal{F}_{\theta}$, Theorem
3.16 implies for any $\Phi\in\mbox{Aut}(X_{\theta})$, $\kappa(\Phi)$ has
denominator 1 or 3. If there were an automorphism with denominator 3, then by
taking powers and composing with a power of the shift, we could find an
automorphism $\Phi$ with $\kappa(\Phi)=-1/3=\bar{1}$. However, from the proof
of Theorem 3.16, this would imply
$\bar{1}+\tilde{\Sigma_{\theta}}\subset\tilde{\Sigma_{\theta}}$, which is
false as $\bar{0}\in\tilde{\Sigma_{\theta}}$, but
$\bar{1}\not\in\tilde{\Sigma_{\theta}}$. Hence $\kappa(\Phi)\in\mathbb{Z}$ for
all $\Phi\in\mbox{Aut}(X_{\theta},\sigma)$ and such $\Phi$ are powers of the
shift by the theorem.

Recall that if $(X_{\theta},\sigma)$ is a two-sided shift, then
$(\bar{X}_{\theta},\bar{\sigma})$ is the corresponding one-sided shift.

######  Theorem 3.18.

Let $\theta$ be a primitive, length $r$ substitution, of height one, and such
that $(X_{\theta},\sigma)$ is infinite. If $\kappa$ is injective (in
particular if $\theta$ has a coincidence), then
$\mbox{Aut}(\bar{X}_{\theta},\bar{\sigma})=\\{\mbox{Id}\\}$.

###### Proof.

Any automorphism $\bar{\Phi}$ of $(\bar{X}_{\theta},\bar{\sigma})$ gives rise
to an endomorphism $\Phi$ of $(X_{\theta},\sigma)$, which satisfies
$\Phi^{n}=\sigma^{k}$ for some $k,n\in\mathbb{N}\cup\\{0\\}$. As $\bar{\Phi}$
is an automorphism, we have $k=0$ and so $\kappa(\Phi)=0$. Now the injectivity
of $\kappa$ implies that $\Phi=\mbox{Id}$, so $\bar{\Phi}=\mbox{Id}$ also. ∎

###  3.6 Computing $\mbox{Aut}(X_{\theta},\sigma)$

In this section, we use the bounds on the denominator appearing in $\kappa$
together with bounds on the radius of the block code to obtain an algorithm to
compute the automorphism group of a constant-length substitution.

Let $\Phi\in\mbox{Aut}(X_{\theta},\sigma)$. By the Curtis–Hedlund–Lyndon
theorem, there exist $l$, $r$, and a map
$f\colon\mathcal{A}^{l+r+1}\to\mathcal{A}$ with the property that
$(\Phi(x))_{n}=f(x_{n-l},\ldots,x_{n},\ldots,x_{n+r})$ for all $x$ and $n$.
Let $l,r$ be the smallest possible integers so that such an $f$ exists. We
call $l$ and $r$ the left and right radius of $\Phi$ respectively. We say
$\Phi$ has radius $R$ if its left radius and right radius are both at most
$R$.

The recognizability of $\theta$ implies that any $x\in X_{\theta}$ can be
written in a unique way as $x=\sigma^{k}(\theta(y))$ where $y\in X_{\theta}$
and, if $\theta$ is length $r$, $0\leq k<r$ (see [16] for a proof in the
injective case, which is all we need). The following proposition tells us that
up to a shift, every automorphism has a small radius, parallel to the case of
reduced constant-length substitutions with partial continuous spectrum in the
work of Host and Parreau [17, Theorem 1.3]. We remark also that Coven,
Dykstra, Keane and LeMasurier have a similar result in [5, Theorem 1].

######  Proposition 3.19.

Let $\theta$ be an injective primitive, length $r$ substitution of height one,
and such that $(X_{\theta},\sigma)$ is infinite. If
$\Phi\in\mbox{Aut}(X_{\theta},\sigma)$ has the property that
$\kappa(\Phi)\in\mathbb{Z}_{r}\setminus\mathbb{Z}$ is periodic, then $\Phi$
has right radius zero and left radius at most 1.

Further, if $\kappa(\Phi)=k/(1-r^{p})$ for $0<k<r^{p}-1$, one has

$\theta^{-c!p}\circ\sigma^{-k(1+r^{p}+r^{2p}+\ldots+r^{(c!-1)p})}\circ\Phi\circ\theta^{c!p}=\Phi,$

where $c$ is the column number.

If $\kappa(\Phi)=0$, then $\Phi$ has left and right radius at most 1 and
$\Phi$ satisfies $\theta^{-c!}\circ\Phi\circ\theta^{c!}=\Phi$.

###### Proof.

We first assume that $\theta$ has a coincidence, so that $\kappa$ is an
injection. Let $R$ be the radius of $\Phi$ and let $t=\kappa(\Phi)$. By
assumption, $t$ is periodic as a point of $\mathbb{Z}_{r}$, with period $p$,
say. Further, the repeating block is not all 0’s or all $r-1$’s. Hence there
exists $n$, a multiple of $p$, such that $t=r^{n}t+w$ and $R<w<r^{n}-R$. Now
$(\Phi(x))_{i}$ is determined by $x_{[i-R,i+R]}$, so that
$(\sigma^{-w}\circ\Phi(x))_{i}$ is determined by $x_{[i-w-R,i-w+R]}$ and in
particular, $(\sigma^{-w}\circ\Phi(x))_{[0,r^{n})}$ is determined by
$x_{[-r^{n},r^{n})}$.

Since $\kappa(\sigma^{-w}\circ\Phi)\in r^{n}\mathbb{Z}_{r}$,
$\sigma^{-w}\circ\Phi$ maps $\theta^{n}(X_{\theta})$ to itself, and since
recognizability tells us that
$\theta^{n}:X_{\theta}\rightarrow\theta^{n}(X_{\theta})$ is invertible, let
$\Psi(y):=\theta^{-n}\circ\sigma^{-w}\circ\Phi\circ\theta^{n}(y)$. The above
ensures that $\Psi$ is an automorphsim of $(X,\sigma)$, and the injectivity of
$\theta$ implies that $(\Psi(y))_{0}$ depends on $y_{[-1,0]}$. Notice that
$\pi(\theta(x))=r\pi(x)$, so that
$\pi(\Phi\circ\theta^{n}x)=r^{n}\pi(x)+\kappa(\Phi)$ and
$\pi(\Psi(x))=\pi(\theta^{-n}\circ\sigma^{-w}\circ\Phi\circ\theta^{n}x)=r^{-n}(-w+r^{n}\pi(x)+\kappa(\Phi))=\pi(x)+t$.
Hence $\kappa(\Psi)=t=\kappa(\Phi)$. By injectivity of $\kappa$ we see that
$\Phi=\Psi$, so that $\Phi$ has left radius 1 and right radius 0 as required.

Suppose now that $\theta$ has column number $c$ and
$t\in\kappa(\mbox{Aut}(X_{\theta},T))\setminus\mathbb{Z}$. Theorem 3.3 tells
us that the group homomorphism $\kappa$ has kernel of size $K\leq c$. Let
$\\{\Phi_{1},\ldots,\Phi_{K}\\}=\kappa^{-1}(t)$. As above, we find $n$ and $w$
that work for all of the $\Phi_{i}$’s, and consider the map which sends
$\Phi\in\\{\Phi_{1},\ldots,\Phi_{K}\\}$ to
$\theta^{-n}\circ\sigma^{-w}\circ\Phi\circ\theta^{n}$. This map is a bijection
of $\\{\Phi_{1},\ldots,\Phi_{K}\\}$, and, since
$\theta^{-n}\circ\sigma^{-w}\circ\Phi\circ\theta^{n}$ has left radius one and
right radius 0, we see that all the maps $\Phi_{i}$ satisfy this property.

If $t=k/(1-r^{p})$, the calculation above shows that
$\Phi\mapsto\theta^{-p}\circ\sigma^{-k}\circ\Phi\circ\theta^{p}$ is a
permutation of $\kappa^{-1}(t)$. Since $|\kappa^{-1}(t)|\leq c$, one sees by
iterating

$\theta^{-c!p}\circ\sigma^{-k(1+r^{p}+r^{2p}+\ldots+r^{(c!-1)p})}\circ\Phi\circ\theta^{c!p}=\Phi.$

The properties of $\Phi$ such that $\kappa(\Phi)=0$ are established similarly.
∎

If $t\in\mathbb{Z}_{r}$ is such that $nt=:k\in\mathbb{Z}$ for some $n$, then
we define $\lfloor t\rfloor=\lfloor k/n\rfloor\in\mathbb{Z}$. We define
$\lceil t\rceil$ similarly as $\lceil k/n\rceil$. We can now rephrase the
radius of $\Phi$ in terms of $\kappa(\Phi)$.

######  Corollary 3.20.

Let $\theta$ be an injective, primitive, length $r$ substitution of height
one, such that $(X_{\theta},\sigma)$ is infinite. Then for each
$\Phi\in\mbox{Aut}(X_{\theta},\sigma)$ such that
$\kappa(\Phi)\not\in\mathbb{Z}$, one has that $\Phi(x)_{0}$ depends only on
$x_{[\lfloor\kappa(\Phi)\rfloor,\lceil\kappa(\Phi)\rceil]}$.

###### Proof.

Let $n$ be chosen so that $\kappa(\Phi)-n$ is periodic in $\mathbb{Z}_{r}$
with some period $p$, and let $\Psi=\Phi\circ\sigma^{-n}$. If the periodic
block is the base $r$ representation of a number $a$, we have
$\kappa(\Psi)=a/(1-r^{p})$ with $0<a<r^{p}-1$, so that
$(r^{p}-1)\kappa(\Psi)=-a$. Hence $\kappa(\Phi)=n-a/(r^{p}-1)$. In particular,
$\lfloor\kappa(\Phi)\rfloor=n-1$ and $\lceil\kappa(\Phi)\rceil=n$. By
Proposition 3.19, $\Psi(x)_{0}$ depends on $x_{[-1,0]}$, and the result
follows. ∎

We remark that a version of Corollary 3.20 exists for integral values of
$\kappa(\Phi)$ also. If $\theta$ has a coincidence, then integral values of
$\kappa(\Phi)$ only arise from powers of the shift. Otherwise, if
$\kappa(\Phi)=n$, then $\Phi(x)_{0}$ is determined by $x_{n-1}$, $x_{n}$ and
$x_{n+1}$. If $\theta$ has the property that for each pair $a$ and
$a^{\prime}$ of distinct elements of $\mathcal{A}$, there is a $k$ such that
$\theta^{k}(a)$ and $\theta^{k}(a^{\prime})$ differ in some coordinate that is
neither the first nor the last of the block, then one can prove that
$\Phi(x)_{0}$ is determined by $x_{n}$. A natural question is whether this is
the case for all primitive constant-length substitutions.

Given left and right radii $m$ and $n$ and a map
$f\colon\mathcal{A}^{m+n+1}\to\mathcal{A}$, we write $\Phi^{f}_{m,n}$ for the
map $\mathcal{A}^{\mathbb{Z}}\to\mathcal{A}^{\mathbb{Z}}$ given by
$\Phi^{f}_{m,n}(x)_{i}=f(x_{i-m},\ldots,x_{i+n})$.

######  Proposition 3.21.

Let $\theta$ be an injective primitive, length $r$ substitution on
$\mathcal{A}$, with column number $c$, of height one, and such that
$(X_{\theta},\sigma)$ is infinite. Let $p\geq 1$ and $0<k<r^{p}-1$.

Let $f\colon\mathcal{A}^{2}\to\mathcal{A}$. Then $\Phi:=\Phi^{f}_{1,0}$
satisfies $\Phi\in\mbox{Aut}(X_{\theta},\sigma)$ and
$\kappa(\Phi)=k/(1-r^{p})$ if and only if:

  1. 1.

if $x_{0}x_{1}x_{2}\in\mathcal{L}_{X_{\theta}}$, then
$f(x_{0},x_{1})f(x_{1},x_{2})\in\mathcal{L}_{X_{\theta}}$; and

  2. 2.

For each $x_{-1}x_{0}x_{1}\in\mathcal{L}(X_{\theta})$ and $0\leq i<r^{c!p}$

$f(\theta^{c!p}(x_{-1}\cdot x_{0})_{i-1},\theta^{c!p}(x_{-1}\cdot
x_{0})_{i})=\theta^{c!p}(f(x_{-1},x_{0})f(x_{0},x_{1}))_{N+i},$

where $N=k(1+r^{p}+\ldots+r^{(c!-1)p})$ and $x_{-1}\cdot x_{0}$ denotes a
finite segment of a bi-infinite sequence with $x_{-1}$ in the $-1$st
coordinate and $x_{0}$ in the 0th coordinate.

Similarly given $g\colon\mathcal{A}^{3}\to\mathcal{A}$, $\Phi^{g}_{1,1}$
satisfies $\Phi^{g}_{1,1}\in\mbox{Aut}(X_{\theta},\sigma)$ and
$\kappa(\Phi^{g}_{1,1})=0$ if and only if

  1. 3.

$g(x_{0},x_{1},x_{2})g(x_{1},x_{2},x_{3})\in\mathcal{L}_{X_{\theta}}$ whenever
$x_{0}x_{1}x_{2}x_{3}\in\mathcal{L}_{X_{\theta}}$; and

  2. 4.

For any $x_{-1}x_{0}x_{1}\in\mathcal{L}_{X_{\theta}}$ and $0\leq i<r^{c!}$,

$g(u_{i-1},u_{i},u_{i+1})=(\theta^{c!}g(x_{-1},x_{0},x_{1}))_{i}\,,$

where $u=u_{-r^{c!}}u_{-r^{c!}+1}\ldots u_{-1}\cdot u_{0}\ldots u_{2r^{c!}-1}$
is the word obtained by applying $\theta^{c!}$ to the word $x_{-1}\cdot
x_{0}x_{1}$.

###### Proof.

First suppose that there exists $\Phi\in\mbox{Aut}(X_{\theta},\sigma)$ such
that $\kappa(\Phi)=t:=k/(1-r^{p})$. By Proposition 3.19, $\Phi=\Phi^{f}_{1,0}$
for a map $f\colon\mathcal{A}^{2}\to\mathcal{A}$. Condition (1) is obviously
satisfied and condition (2) is the commutation relation of Proposition 3.19
expressed in terms of $f$.

Conversely, suppose $f$ has satisfies Conditions (1) and (2). Let
$\Phi=\Phi^{f}_{1,0}$. Condition (2) implies
$\Phi(\theta^{c!p}x)_{i}=(\sigma^{N}\circ\theta^{c!p}\circ\Phi(x))_{i}$ for
$0\leq i<r^{c!p}$. The same equation applied to iterates of $x$ under $\sigma$
yields $\Phi\circ\theta^{c!p}=\sigma^{N}\circ\theta^{c!p}\circ\Phi$. Iterating
this equality and using the relation $\sigma^{r}\circ\theta=\theta\circ\sigma$
gives

$\Phi\circ\theta^{nc!p}=(\sigma^{N}\circ\theta^{c!p})^{n}\circ\Phi=\sigma^{N(1+r^{c!p}+\ldots+r^{(n-1)c!p})}\circ\theta^{nc!p}\circ\Phi.$

We let $x\in X_{\theta}$ and show that $\Phi(x)\in X_{\theta}$. For any $n$,
we can write $x=\sigma^{-j}\circ\theta^{npc!}(y)$ for some $y\in X_{\theta}$
and $0\leq j<r^{npc!}$. Now applying the above, we have

$\Phi(x)=\sigma^{-j}\circ\Phi(\theta^{npc!}(y))=\sigma^{l}(\theta^{npc!}(\Phi(y))),$

where

$l=-j+N(1+r^{c!p}+\ldots+r^{(n-1)c!p}).$

Since by (1) all 2-words of $\Phi(y)$ belong to $\mathcal{L}_{X_{\theta}}$, we
deduce all subwords of $\theta^{npc!}(\Phi(y))$ of size $1+r^{npc!}$ belong to
$\mathcal{L}_{X_{\theta}}$. Since $n$ is arbitrary, we deduce $\Phi(x)\in
X_{\theta}$.

Since $\Phi$ is shift-commuting by construction, we have
$\Phi\in\mbox{End}(X_{\theta},\sigma)$ and hence
$\Phi\in\mbox{Aut}(X_{\theta},\sigma)$ by Theorem 3.16. In particular,
$t:=\kappa(\Phi)$ is now defined. Now
$\pi(\Phi(\theta^{pc!}(x)))=t+r^{pc!}\pi(x)$ and
$\pi(\sigma^{N}(\theta^{pc!}(\Phi(x))))=k(1+r^{p}+\ldots+r^{(c!-1)p})+r^{pc!}(\pi(x)+t)$.
Since these agree, we have $t(1-r^{p})=k$ as required.

The argument that Conditions (3) and (4) characterize elements of $\ker\kappa$
is similar. ∎

We can now deduce

######  Theorem 3.22.

Let $\theta$ be a primitive, length $r$ substitution on $\mathcal{A}$ such
that $(X_{\theta},\sigma)$ is infinite. Then there is an algorithm to compute
$\mbox{Aut}(X_{\theta},\sigma)$.

###### Proof.

If $\theta$ does not have height one, we use Proposition 3.4 to compute a pure
base of $\theta$. Proposition 3.5 tells us how to retrieve
$\mbox{Aut}(X_{\theta},\sigma)$ from the automorphism group of its pure base.
Similarly, if the pure base is not injective, we use Theorem 3.8 to compute
its automorphism group from the automorphism group of a conjugate injective
substitution shift. Hence it suffices to give an algorithm for injective
substitutions of height one.

We can algorithmically compute the column number, $c$ and also $j$, the length
of the shortest word in $\mathcal{F}_{\theta}$ from the transition graphs
described in Section 3.4. Recall from Lemma 3.2 that
$\kappa(\mbox{Aut}(X_{\theta},T))$ is a cyclic subgroup of $\mathbb{Z}_{r}$
generated by $1/d$ for some integer $d$. By Theorem 3.16, $d$ satisfies
$\gcd(d,r)=1$ and $d\leq r^{j}-1$. Now $\mbox{Aut}(X_{\theta},T)$ is the semi-
direct product of $\ker\kappa$ with the cyclic subgroup generated by any
element of $\kappa^{-1}(-1/d)$.

To find $\ker\kappa$, one applies Proposition 3.21 to test all of the finitely
many 3-block maps. Note that one can algorithmically list the words of length
two and three that belong to $\mathcal{L}_{X_{\theta}}$. One then needs to
find an element of $\kappa^{-1}(-1/d)$ for the largest $d$ so that this set is
non-empty. By the above, there are finitely many values of $d$ to check. Since
$\gcd(d,r)=1$, we see $d|r^{p}-1$ for some $p$ and then $-1/d$ can be
expressed as $k/(1-r^{p})$ for some $0<k<r^{p}-1$. By Proposition 3.21, there
are finitely many 2-block maps to check for each potential $d$. ∎

We do not address the question of efficiency.

From Corollary 3.7, we know that for substitutions with a coincidence,
$\mbox{Aut}(X_{\theta},\sigma)/\langle\sigma\rangle$ is a finite cyclic group.
In Example 3.17, this group was trivial, and it is natural to wonder if this
is always the case. The following example shows that the quotient can indeed
be non-trivial.

######  Example 3.23.

Let $\mathcal{A}=\\{a,b,c\\}$, $\theta(a)=aba$, $\theta(b)=cba$ and
$\theta(c)=ccb$. This example appears in Dekking’s article [9] just after
Theorem 14. He describes how $(X_{\theta},\sigma)$ is a relabelling of the
second power shift of the substitution $\theta^{\prime}$ where
$\theta^{\prime}(0)=011$ and $\theta^{\prime}(1)=101$. That is, the shift with
symbols  01 ,  11 and  10 with
$\theta(\,\scalebox{0.9}{\framebox{01}}\,)=\scalebox{0.9}{\framebox{01}\,\framebox{11}\,\framebox{01}}$,
$\theta(\,\scalebox{0.9}{\framebox{11}}\,)=\scalebox{0.9}{\framebox{10}\,\framebox{11}\,\framebox{01}}$
and
$\theta(\,\scalebox{0.9}{\framebox{10}}\,)=\scalebox{0.9}{\framebox{10}\,\framebox{10}\,\framebox{11}}$.
Then $(X_{\theta},\sigma)$ is conjugate to
$(X_{\theta^{\prime}},\sigma^{\prime 2})$ (where we use $\sigma^{\prime}$ to
denote the shift on $X_{\theta^{\prime}}$). As a consequence, the map
$\sigma^{\prime}$ is conjugate to an automorphism $\Phi$ of
$(X_{\theta},\theta)$ satisfying $\Phi^{2}=\sigma$. Using the techniques we
have developed, it can be verified that $t=\overline{1}$ is the only non-
trivial periodic 3-adic integer such that
$\tilde{\Sigma}_{\theta}+t=\tilde{\Sigma}_{\theta}$. Since $\Phi^{2}=\sigma$,
we have $\kappa(\Phi)=\overline{1}2$ and we have shown that
$\mbox{Aut}(X_{\theta},\sigma)=\langle\Phi\rangle$.

###  3.7 Computing $\mbox{Conj}(X_{\theta},X_{\theta^{\prime}})$.

The techniques of Section 3.6 can be generalized to compute the set of
conjugacies between two substitution shifts generated by primitive constant-
length substitutions, one of which generates an infinite shift. We use
$\kappa$ to also denote the restriction to
$\mbox{Conj}(X_{\theta},X_{\theta^{\prime}})$ of the map in Theorem 3.3. We
continue to assume that our maximal equicontinuous factor mappings are those
that were defined in Section 3.4, so that $r^{n}|\pi(x)$ if and only if
$x\in\theta^{n}(X_{\theta})$.

######  Proposition 3.24.

Let $\theta$ and $\theta^{\prime}$ be primitive, length $r$ substitutions,
both with column number $c$ and of height one, and such that
$(X_{\theta},\sigma)$ and $(X_{\theta^{\prime}},\sigma)$ are infinite. Suppose
that $\Phi\in\mbox{Conj}(X_{\theta},X_{\theta^{\prime}})$. Then $\kappa(\Phi)$
is rational, and if $\mathcal{F}_{\theta}$ contains a word of length $j$, then
$n\kappa(\Phi)\in\mathbb{Z}$ for some $0\leq n\leq(r-1)(r^{j}-1)$.

###### Proof.

Let $\pi:X_{\theta}\rightarrow\mathbb{Z}_{r}$ and
$\pi^{\prime}:X_{\theta^{\prime}}\rightarrow\mathbb{Z}_{r}$ denote the
relevant maximal equicontinuous factor mappings, and suppose that
$\Phi\in\mbox{Conj}(X_{\theta},X_{\theta^{\prime}}).$ Since
$\kappa(\Phi\circ\sigma^{n})=\kappa(\Phi)+n$, we can assume, by composing
$\Phi$ with a power of the shift if necessary, that $\kappa(\Phi)\equiv 0\mod
r$, i.e. that $\kappa(\Phi)\in r\mathbb{Z}_{r}$. In this case, noting that
$\pi(\theta(x))=r\pi(x)$, we have
$\pi^{\prime}(\Phi(\theta(x)))=\kappa(\Phi)+\pi(\theta(x))=\kappa(\Phi)+r\pi(x)\equiv
0\mod r$. Since recognizability tells us that
$\theta:X_{\theta}\rightarrow\theta(X_{\theta})$ and
$\theta^{\prime}:X_{\theta^{\prime}}\rightarrow{\theta^{\prime}}(X_{\theta^{\prime}})$
are invertible, then $\Psi:=\theta^{\prime-1}\circ\Phi\circ\theta$ is a well
defined conjugacy. Also,

$\pi(x)+\kappa(\Psi)=\pi^{\prime}(\theta^{\prime-1}\circ\Phi\circ\theta(x))=\frac{1}{r}(\pi(\theta(x))+\kappa(\Phi))=\pi(x)+\frac{\kappa(\Phi)}{r},$

so that $\kappa(\Psi)=\kappa(\Phi)/r$. Finally, (1) of Theorem 3.3 tells us
that

$\kappa(\Psi\circ\Phi^{-1})=\kappa(\Psi)-\kappa(\Phi)=\kappa(\Phi)(\tfrac{1}{r}-1),$

and since $\Psi\circ\Phi^{-1}\in\mbox{Aut}(X_{\theta^{\prime}},\sigma)$, so
that $\kappa(\Psi\circ\Phi^{-1})$ is rational, we deduce our first claim. By
Theorem 3.16, $n\kappa(\Psi\circ\Phi^{-1})\in\mathbb{Z}$ for some $0\leq n\leq
r^{j}-1$, and our second claim follows. ∎

The proofs of the following two propositions are a straightforward
generalization of those of Propositions 3.19 and 3.21.

######  Proposition 3.25.

Let $\theta$ and $\theta^{\prime}$ be injective primitive, length $r$
substitutions, both with column number $c$ and of height one, and such that
$(X_{\theta},\sigma)$ and $(X_{\theta^{\prime}},\sigma)$ are infinite. If
$\Phi\in\mbox{Conj}(X_{\theta},X_{\theta^{\prime}})$ has the property that
$\kappa(\Phi)\in\mathbb{Z}_{r}\setminus\mathbb{Z}$ is periodic, then $\Phi$
has right radius zero and left radius at most $1$. Further, one has

$\theta^{\prime-c!p}\circ\sigma^{-k(1+r^{p}+r^{2p}+\ldots+r^{(c!-1)p})}\circ\Phi\circ\theta^{c!p}=\Phi,$

where $c$ is the column number and $\kappa(\Phi)=k/(1-r^{p})$ with
$0<k<r^{p}-1$.

If $\kappa(\Phi)=0$, then $\Phi$ has left and right radius at most $1$, and

$\theta^{\prime-c!}\circ\Phi\circ\theta^{c!}=\Phi.$

######  Proposition 3.26.

Let $\theta$ and $\theta^{\prime}$ be injective primitive, length $r$
substitutions on $\mathcal{A}$ and $\mathcal{A}^{\prime}$ respectively, both
with column number $c$ and of height one, and such that $(X_{\theta},\sigma)$
and $(X_{\theta^{\prime}},\sigma)$ are infinite. Let $p\geq 1$ and suppose
that $0<k<r^{p}-1$.

Let $f\colon\mathcal{A}^{2}\to\mathcal{A}^{\prime}$. Then
$\Phi:=\Phi^{f}_{1,0}$ satisfies
$\Phi\in\mbox{Conj}(X_{\theta},X_{\theta^{\prime}})$ and
$\kappa(\Phi)=k/(1-r^{p})$ if and only if:

  1. 1.

if $x_{0}x_{1}x_{2}\in\mathcal{L}_{X_{\theta}}$, then
$f(x_{0},x_{1})f(x_{1},x_{2})\in\mathcal{L}_{X_{\theta^{\prime}}}$; and

  2. 2.

For each $x_{-1}x_{0}x_{1}\in\mathcal{L}(X_{\theta})$ and $0\leq i<r^{c!p}$

$f(\theta^{c!p}(x_{-1}\cdot x_{0})_{i-1},\theta^{c!p}(x_{-1}\cdot
x_{0})_{i})=\theta^{\prime c!p}(f(x_{-1},x_{0})f(x_{0},x_{1}))_{N+i},$

where $N=k(1+r^{p}+\ldots+r^{(c!-1)p})$ and $x_{-1}\cdot x_{0}$ denotes a
finite segment of a bi-infinite sequence with $x_{-1}$ in the $-1$st
coordinate and $x_{0}$ in the 0th coordinate.

Similarly given $g\colon\mathcal{A}^{3}\to\mathcal{A}^{\prime}$,
$\Phi^{g}_{1,1}$ satisfies
$\Phi^{g}_{1,1}\in\mbox{Conj}(X_{\theta},X_{\theta^{\prime}})$ and
$\kappa(\Phi^{g}_{1,1})=0$ if and only if

  1. 3.

$g(x_{0},x_{1},x_{2})g(x_{1},x_{2},x_{3})\in\mathcal{L}_{X_{\theta^{\prime}}}$
whenever $x_{0}x_{1}x_{2}x_{3}\in\mathcal{L}_{X_{\theta}}$; and

  2. 4.

For any $x_{-1}x_{0}x_{1}\in\mathcal{L}_{X_{\theta}}$ and $0\leq i<r^{c!}$,

$g(u_{i-1},u_{i},u_{i+1})=(\theta^{\prime c!}g(x_{-1},x_{0},x_{1}))_{i}\,,$

where $u$ is the block of length $3r^{c!}$ given by
$u_{-r^{c!}}u_{-r^{c!}+1}\ldots u_{-1}\cdot u_{0}\ldots
u_{2r^{c!}-1}=\theta^{c!}(x_{-1}\cdot x_{0}x_{1})$.

Let $\theta^{\prime}$ be a primitive length $r$ substitution with column
number $c$, such that $(X_{\theta^{\prime}},\sigma)$ is infinite. Let $\theta$
be another constant-length substitution. If $(X_{\theta},\sigma)$ and
$(X_{\theta^{\prime}},\sigma)$ were topologically conjugate, then both systems
would be infinite, and both would have the same maximal equicontinuous factor.
Thus, conjugacy of the two systems implies that $\theta$ and $\theta^{\prime}$
have the same height, and the appropriate dynamical formulation of Cobham’s
theorem [6] tells us that the lengths of $\theta$ and $\theta^{\prime}$ are
powers of the same integer. Corollary 3.13 implies that both have column
number $c$. By taking a power of $\theta^{\prime}$ or $\theta$ if necessary,
and by considering the pure bases of our two substitutions, we are in a
position to apply Propositions 3.24, 3.25 and 3.26, to conclude:

######  Theorem 3.27.

Let $\theta$ and $\theta^{\prime}$ be primitive, constant-length
substitutions. Suppose further $(X_{\theta},\sigma)$ is infinite. Then there
is an algorithm to decide whether $(X_{\theta},\sigma)$ and
$(X_{\theta^{\prime}},\sigma)$ are topologically conjugate. In the case that
they are topologically conjugate, the algorithm yields a topological conjugacy
and hence one can algorithmically determine
$\mbox{Conj}(X_{\theta},X_{\theta^{\prime}})$.

## Acknowledgments

We thank Michel Dekking, Bryna Kra, Alejandro Maass, Samuel Petite and Marcus
Pivato for helpful comments. We also thank the referee for a thorough reading
and many helpful comments. The third author thanks LIAFA, Université Paris-7
for its hospitality and support.

## References

  * [1] M. Barge, B. Diamond, and C. Holton.  Asymptotic orbits of primitive substitutions.  Theoret. Comput. Sci., 301(1-3):439–450, 2003.
  * [2] J. Cassaigne.  Special factors of sequences with linear subword complexity.  In Developments in language theory, II (Magdeburg, 1995), pages 25–34. World Sci. Publ., River Edge, NJ, 1996.
  * [3] E. M. Coven.  Endomorphisms of substitution minimal sets.  Z. Wahrscheinlichkeitstheorie und Verw. Gebiete, 20:129–133, 1971/72.
  * [4] E. M. Coven, M. Dekking, and M. Keane.  Topological conjugacy of constant length substitution dynamical systems.  Indag. Math. (N.S.), 28 (2017), no. 1, 91–107.
  * [5] E. M. Coven, A. Dykstra, M. Keane, and M. LeMasurier.  Topological conjugacy to given constant length substitution minimal systems.  Indag. Math. (N.S.), 25(4):646–651, 2014.
  * [6] E. M. Coven, A. Dykstra, and M. Lemasurier.  A short proof of a theorem of Cobham on substitutions.  Rocky Mountain J. Math., 44(1):19–22, 2014.
  * [7] E. M. Coven and M. Keane.  Every compact metric space that supports a positively expansive homeomorphism is finite.  In Dynamics & stochastics, volume 48 of IMS Lecture Notes Monogr. Ser., pages 304–305. Inst. Math. Statist., Beachwood, OH, 2006.
  * [8] V. Cyr and B. Kra.  The automorphism group of a shift of linear growth: beyond transitivity.  Forum Math. Sigma, 3:e5, 27, 2015.
  * [9] F. M. Dekking.  The spectrum of dynamical systems arising from substitutions of constant length.  Z. Wahrscheinlichkeitstheorie und Verw. Gebiete, 41(3):221–239, 1977/78.
  * [10] S. Donoso, F. Durand, A. Maass, and S. Petite.  On automorphism groups of low complexity minimal subshifts.  Ergodic Theory Dynam. Systems, 36(1):64–95, 2016.
  * [11] T. Downarowicz.  Survey of odometers and Toeplitz flows.  In Algebraic and topological dynamics, volume 385 of Contemp. Math., pages 7–37. Amer. Math. Soc., Providence, RI, 2005.
  * [12] F. Durand.  Linearly recurrent subshifts have a finite number of non-periodic subshift factors.  Ergodic Theory Dynam. Systems, 20(4):1061–1078, 2000.
  * [13] F. Durand, B. Host, and C. Skau.  Substitutional dynamical systems, Bratteli diagrams and dimension groups.  Ergodic Theory Dynam. Systems, 19(4):953–993, 1999.
  * [14] F. Durand and J. Leroy.  Personal communication.
  * [15] F. D. F. Blanchard and A. Maass.  Nonlinearity, 17:817–833, 2005.
  * [16] B. Host.  Valeurs propres des systèmes dynamiques définis par des substitutions de longueur variable.  Ergodic Theory Dynam. Systems, 6(4):529–540, 1986.
  * [17] B. Host and F. Parreau.  Homomorphismes entre systèmes dynamiques définis par substitutions.  Ergodic Theory Dynam. Systems, 9(3):469–477, 1989.
  * [18] T. Kamae.  A topological invariant of substitution minimal sets.  J. Math. Soc. Japan, 24:285–306, 1972.
  * [19] M. Lemańczyk and M. K. Mentzen.  On metric properties of substitutions.  Compositio Math., 65(3):241–263, 1988.
  * [20] J. C. Martin.  Substitution minimal flows.  Amer. J. Math., 93:503–526, 1971.
  * [21] P. Michel.  Stricte ergodicité d’ensembles minimaux de substitution.  C. R. Acad. Sci. Paris Sér. A, 278:811–813, 1974.
  * [22] B. Mossé.  Puissances de mots et reconnaissabilité des points fixes d’une substitution.  Theoret. Comput. Sci., 99(2):327–334, 1992.
  * [23] J. Olli.  Endomorphisms of Sturmian systems and the discrete chair substitution tiling system.  Discrete Contin. Dyn. Syst., 33(9):4173–4186, 2013.
  * [24] V. Salo and I. Törmä.  Block maps between primitive uniform and Pisot substitutions.  Ergodic Theory Dynam. Systems, 35(7):2292–2310, 2015.

[ethan] Ethan M. Coven
Department of Mathematics
Wesleyan University
U.S.A.
ecovenwesleyanedu
[anthony] Anthony Quas
Department of Mathematics and Statistics
University of Victoria
Canada
aquasuvicca
[reem] Reem Yassawi
Department of Mathematics
Trent University
Canada
ryassawitrentuca