Topological factors of rank-one subshifts

Abstract

We study topological factors of rank-one subshifts and prove that those factors that are themselves subshifts are either finite or isomorphic to the original rank-one subshifts. Thus, we completely characterize the subshift factors of rank-one subshifts.

1. Introduction and definitions

In 1965, Chacon 5 introduced the concept of rank-one measure-preserving transformations and constructed the first examples. Since then, rank-one transformations have come up often as important examples and counterexamples in ergodic theory and have been studied extensively by many researchers. Ferenczi 10 was a comprehensive survey summarizing many results and systematically studying several different definitions of rank-one transformations that had appeared in the literature. Many rank-one transformations could be shown to satisfy each of the different definitions. However, the constructive symbolic definition seemed to behave somewhat differently from the other definitions, which led to further research from the perspective of symbolic and topological dynamics, such as in 2, 8, and 9.

Because the constructive symbolic definition works with a shift space, it was natural to study systems coming from the constructive symbolic definition in the setting of topological dynamics. This led to the definition of rank-one subshifts, which was first studied by the first author and Hill in 11, where they gave a characterization for the topological isomorphism relation of rank-one subshifts based on the cutting and spacer parameters. In 12 the current authors studied the topological mixing properties of rank-one subshifts. Because the concept of rank-one subshifts came from rank-one transformations, the study of their topological dynamical properties is often motivated by their ergodic-theoretic counterparts which tend to have a long history. For example, the motivation for the original rank-one transformation constructed by Chacon 5 was to build a measure preserving transformation that is weakly mixing but not mixing. Mixing properties of rank-one transformations were also studied in, e.g., 1, 3, 4, 6, 7, and 13. In 12 we also completely characterized the maximal equicontinuous factors of rank-one subshifts and showed that they can only be finite.

For some readers it might be worth noting that there is another, different notion of rank in topological dynamics, as in the context of finite rank Bratteli–Vershik diagrams. In that context a rank-one Bratteli–Vershik diagram would give rise to an odometer, whereas a rank-one subshift as we define below cannot be an odometer unless it is finite.

In this paper we continue to study the topological dynamical properties of rank-one subshifts. The focus of this paper is the topological factors of rank-one subshifts which are themselves subshifts. We provide a complete characterization as follows.

Theorem.

Let $(X, T)$ be a rank-one subshift and $(Y, S)$ be a subshift. Suppose that $(Y, S)$ is a topological factor of $(X, T)$. Then either $Y$ is finite or $(X, T)$ is isomorphic to $(Y, S)$.

We conjecture that the theorem is still true if we drop the assumption that the factor is itself a subshift.

In this paper, by a subshift we mean a topological dynamical system $(X, T)$ where $X$ is a closed invariant subset of some $b^\mathbb{Z}=\{0, 1, \cdots , b-1\}^\mathbb{Z}$ for a positive integer $b>1$, and $T$ is the shift map defined by $(Tx)(k)=x(k+1)$. Since the shift map is uniformly defined, we sometimes suppress mentioning the shift map and refer to the subshift as $X$.

Fixing a sequence $(q_n)_{n\geq 0}$ of integers $>1$ and a sequence $(a_{n,i})_{n\geq 0, 1\leq i<q_n}$ of non-negative integers, we define a rank-one sequence $(v_n)_{n\geq 0}$ of binary words by setting $v_0=0$ and

$$\begin{equation} v_{n+1}=v_n1^{a_{n,1}}v_n\cdots v_n1^{a_{n, q_n-1}}v_n. {\tag{1}} \end{equation}$$

Note that each $v_n$ is a word that starts and ends with $0$, and each $v_n$ is an initial segment of $v_{n+1}$. This allows us to define a infinite rank-one word $V=\lim _{n\to \infty } v_n$ and a rank-one subshift

$$\begin{equation*} X_V=\{ x\in 2^\mathbb{Z}\,:\, \text{every finite subword of }x\text{ is a subword of }V\}. \end{equation*}$$

The sequence $(q_n)$ is called the cutting parameter and the doubly-indexed sequence $(a_{n,i})$ is called the spacer parameter of the rank-one subshift $(X_V, T)$.

When the spacer parameter of a rank-one subshift $X$ is bounded, $X$ is a minimal dynamical system, that is, for all $x\in X$, the orbit $\{T^kx\,:\, k\in \mathbb{Z}\}$ is dense in $X$. When the spacer parameter is unbounded, $X$ will contain a unique fixed point $1^\mathbb{Z}$, that is, the constant 1 element. In this case, for every $x\in X-\{1^\mathbb{Z}\}$, the orbit of $x$ is dense in $X$.

Our proof of the main theorem will be split into two cases, according to whether the spacer parameter is bounded. The proofs of the two cases will be presented in Sections 3 and 4. In the case of unbounded spacer parameter, we show a slightly stronger statement that either the factor is trivial (one-element system) or isomorphic to the original rank-one subshift.

2. Preliminaries

If $(v_n)$ is a rank-one sequence, then any subsequence of $(v_n)$ that starts with $v_0=0$ as the first term is also a rank-one sequence and gives rise to the same rank-one subshift. This is because, given any $m>n$, one can write $v_m$ in the format of 1 in terms of $v_n$ with appropriately modified cutting and spacer parameters. We call this procedure of extracting subsequences of a rank-one sequence telescoping. It is clear that telescoping changes the cutting and spacer parameters but does not change the boundedness of the spacer parameter.

We will fix some notation to use in the rest of the paper. If $i\leq j$ are integers we let $[i,j]$ denote the set of integers in between (and including) $i$ and $j$. For a finite word $\alpha$ we let $\mathrm{lh}(\alpha )$ denote the length of $\alpha$, and think of $\alpha$ as a function with domain $[0,\mathrm{lh}(\alpha )-1]$. If $0\leq i\leq j<\mathrm{lh}(\alpha )$, we let $\alpha [i,j]$ denote the word $\beta$ of length $j-i+1$ where $\beta (k)=\alpha (k+i)$ for $k\in [0, j-i]$.

Let $(X, T)$ be a subshift of $2^\mathbb{Z}$ and $(Y, S)$ be a subshift of $b^{\mathbb{Z}}$ for some integer $b\geq 2$. Assume $\varphi : (X, T)\to (Y, S)$ is a factor map, that is, $\varphi$ is surjective and continuous, and for all $x\in X$,

$$\begin{equation*} \varphi (Tx)=S\varphi (x). \end{equation*}$$

It is well-known that, due to the compactness of $X$ and $Y$, there is a sliding block code inducing $\varphi$, that is, there exist integers $r\geq 0$ and $s$, and a partition of $2^{2r+1}$, $\{C_0, \dots , C_{b-1}\}$, such that for all $x\in X$, $k\in \mathbb{Z}$, and $j\in [0,b-1]$,

$$\begin{equation*} \varphi (x)(k)=j \iff x[k+s-r, k+s+r]\in C_j. \end{equation*}$$

Intuitively, the block of $x$ in between (and including) coordinates $k+s-r$ and $k+s+r$ completely determines $\varphi (x)$ at coordinate $k$. Note that the $T^{s-r}$ is an isomorphism from $(X,T)$ to itself, and thus we may assume without loss of generality that $s=r$. Let $R=2r$. Then we have

$$\begin{equation*} \varphi (x)(k)=j \iff x[k, k+R]\in C_j. \end{equation*}$$

In other words, $\varphi (x)$ at coordinate $k$ is completely determined by the block of $x$ of length $R+1$ in between coordinates $k$ and $k+R$.

3. Bounded spacer parameters

Throughout this section we assume $(X, T)$ is a rank-one subshift of $2^\mathbb{Z}$ with bounded spacer parameter. In other words, $X=X_V$, where the infinite rank-one word $V$ is given by a rank-one sequence $(v_n)$, which in turn is determined by a cutting parameter $(q_n)$ and spacer parameter $(a_{n,i})$. Let $B$ be a bound for the spacer parameter. That is, for all $n\geq 0$ and $1\leq i<q_n$, we have $a_{n,i}\leq B$.

Let $(Y, S)$ be a subshift of $b^{\mathbb{Z}}$ for some integer $b\geq 2$. Assume $\varphi$ is a factor map from $(X, T)$ onto $(Y, S)$. Let $\{C_0,\dots , C_{b-1}\}$ be the sliding block code corresponding to $\varphi$. Assume that the sliding block code has window size $R+1$, that is, for any $x\in X$, $k\in \mathbb{Z}$, and $j\in [0,b-1]$,

$$\begin{equation*} \varphi (x)=j\iff x[k,k+R]\in C_j. \end{equation*}$$

By telescoping, we may assume $\mathrm{lh}(v_1)\gg B+2R$. For each $n\geq 1$, let $\alpha _n$ be the block of length $\mathrm{lh}(v_n)-R$ obtained from the application of the sliding block code to $v_n$, that is, for $k\in [0, \mathrm{lh}(v_n)-R-1]$,

$$\begin{equation*} \alpha _n(k)=j\iff v_n[k,k+R]\in C_j. \end{equation*}$$

For each $a\leq B$, let $\beta _a$ be the block of length $a+R$ obtained from the application of the sliding block code to $v_1[\mathrm{lh}(v_n)-R, \mathrm{lh}(v_n)-1]1^av_1[0,R-1]$. Then we have that, for all $n\geq 1$,

$$\begin{equation*} \alpha _{n+1}=\alpha _n\beta _{a_{n,1}}\alpha _n\dots \alpha _n\beta _{a_{n, q_n-1}}\alpha _n. \end{equation*}$$

Now suppose $x\in X$. Proposition 2.29 of 11 states that, for any $n\geq 1$, $x$ can be written uniquely as

$$\begin{equation} \cdots \cdots v_n 1^{c_{-1}}v_n 1^{c_0} v_n 1^{c_1}v_n \cdots \cdots {\tag{2}} \end{equation}$$

where $c_i\geq 0$ for $i\in \mathbb{Z}$. Recall that these occurrences of $v_n$ are called expected occurrences of $v_n$. It follows that $\varphi (x)$ can be written as

$$\begin{equation*} \cdots \cdots \alpha _n \beta _{c_{-1}} \alpha _n\beta _{c_0} \alpha _n \beta _{c_1}\alpha _n\cdots \cdots \end{equation*}$$

Since $(X, T)$ is minimal when it has bounded spacer parameter, it follows that $(Y, S)$ is also minimal. From now on we assume that $(Y, S)$ is not finite. Our objective is to show that the factor map $\varphi$ is indeed a topological isomorphism. In order to do this, it suffices to show that $\varphi$ is one-to-one, as $\varphi$ is a closed map given that $X$ and $Y$ are compact.

Toward a contradiction, we assume that there are distinct $x, x'\in X$ with $\varphi (x)=\varphi (x')$. Fix such $x, x'$. Since $x$ and $x'$ each has a unique decomposition in the form 2, we have $k, k'\in \mathbb{Z}$ with $0<|k-k'|\leq \frac{1}{2}(\mathrm{lh}(\alpha _n)+B+R)$ such that $x$ has an expected occurrence of $v_n$ at coordinate $k$ and $x'$ has an expected occurrence of $v_n$ at $k'$. To see this, note first that there must be $k\in \mathbb{Z}$ such that $x$ has an expected occurrence of $v_n$ at coordinate $k$ while $x'$ does not, since otherwise $x=x'$. Let $x$ have an expected occurrence of $v_n$ at coordinate $k$ while $x'$ does not. Suppose further that $x'$ does not have an expected occurrence of $v_n$ at $k'$ for any $k'\in [k-\frac{1}{2}(\mathrm{lh}(\alpha _n)+B+R), k+\frac{1}{2}(\mathrm{lh}(\alpha _n)+B+R)]$. Then for an interval of length $\mathrm{lh}(\alpha _n)+R+B=\mathrm{lh}(v_n)+B$ there is no expected occurrence of $v_n$. This violates 2.

Without loss of generality, we may assume $k<k'$. Moreover, the expected occurrence of $v_n$ in $x$ at coordinate $k$ is followed by a spacer $1^a$ and then followed by another expected occurrence of $v_n$. Similarly, the expected occurrence of $v_n$ in $x'$ at coordinate $k'$ is followed by a spacer $1^{a'}$ and then followed by another expected occurrence of $v_n$. Without loss of generality, we may assume $a\neq a'$. This is because, if $a=a'$, then instead of considering the expected occurrence of $v_n$ at $k$ in $x$ and that at $k'$ in $x'$, which we call the first expected occurrences of $v_n$, we may consider the second expected occurrences of $v_n$ which follow the spacers specified above, and note that the difference of their beginning coordinates will still be $k'-k$. If the spacers following them are of different lengths, then we are done. Otherwise, we can repeat and consider the next expected occurrences of $v_n$ in $x$ and $x'$. By repeating, we may thus find expected occurrences of $v_n$ in $x$ and $x'$ respectively which satisfy the assumption that the spacers following them are of different lengths. If we fail to find such expected occurrences of $v_n$ to the right of the first expected occurrences of $v_n$, we may in a similar fashion search for expected occurrences that satisfy the assumption to the left of the first expected occurrences. If finally we fail to find such occurrences on both sides of the first expected occurrences, then we have that

$$\begin{equation*} T^{k-k'}x=x' \end{equation*}$$

and so

$$\begin{equation*} \varphi (x)=\varphi (x')=\varphi (T^{k-k'}x)=S^{k-k'}(\varphi (x)). \end{equation*}$$

This means that $\varphi (x)$ is periodic, and so $Y$ is finite, a contradiction.

For the rest of the proof, we fix $k<k'$ and $a\neq a'$ such that

(i)

$x$ has an expected occurrence of $v_n$ at $k$, followed by a spacer $1^a$, followed by another expected occurrence of $v_n$ at $k+\mathrm{lh}(v_n)+a$;

(ii)

$x'$ has an expected occurrence of $v_n$ at $k'$, followed by a spacer $1^{a'}$, followed by another expected occurrence of $v_n$ at $k'+\mathrm{lh}(v_n)+a'$;

(iii)

$k'-k\leq \frac{1}{2}(\mathrm{lh}(v_n)+B)=\frac{1}{2}(\mathrm{lh}(\alpha _n)+R+B)$.

Let $y=\varphi (x)=\varphi (x')$. Then we have

(i’)

$y$ has an occurrence of $\alpha _n$ at $k$, followed by an occurrence of $\beta _a$, followed by another occurrence of $\alpha _n$ at $k+\mathrm{lh}(\alpha _n)+R+a$;

(ii’)

$y$ has an occurrence of $\alpha _n$ at $k'$, followed by an occurrence of $\beta _{a'}$, followed by another occurrence of $\alpha _n$ at $k'+\mathrm{lh}(\alpha _n)+R+a'$.

Since $k'-k\leq \frac{1}{2}(\mathrm{lh}(\alpha _n)+R+B)$, the two occurrences of $\alpha _n$ in $y$ which occur at $k$ and $k'$ overlap for at least $\frac{1}{2}(\mathrm{lh}(\alpha _n)-R-B)$ coordinates.

We use the following concept and general lemma.

Definition 3.1.

Let $\eta$ be a finite string and $0<p<\mathrm{lh}(\eta )$. Suppose $\mathrm{lh}(\eta )=lp+q$ where $0\leq q<p$. We say that $\eta$ has period $p$ (or $p$ is a period for $\eta$) if $(\eta [0,p-1])^l$ is an initial segment of $\eta$ and $\eta$ is an initial segment of $(\eta [0,p-1])^{l+1}$.

Lemma 3.2.

Let $\eta$ be a finite word and $0<p<\mathrm{lh}(\eta )$. Suppose $\eta$ occurs at both coordinates $0$ and $p$ in some sufficiently long string $\xi$. Then $p$ is a period for $\eta$.

Proof.

Since $\eta$ occurs at $p$ in $\xi$, we have $\xi [p,2p-1]=\eta [0,p-1]=\xi [0,p-1]$. If $\mathrm{lh}(\eta )<2p$, we have that $\eta$ is an initial segment of $\xi [0,2p-1]=(\eta [0, p-1])^2$, and so $p$ is a period of $\eta$. Otherwise, $\mathrm{lh}(\eta )>2p$, we have that $\xi [0,2p-1]=(\eta [0,p-1])^2$ is an initial segment of the occurrence of $\eta$ at $0$. Considering the occurrence of $\eta$ at $p$, we have that $\xi [2p,3p-1]=\eta [p,2p-1]=\eta [0,p-1]$. It follows that $\xi [0,3p-1]=(\eta [0,p-1])^3$. Now, if $\mathrm{lh}(\eta )<3p$, we have that $\eta$ is an initial segment of $\xi [0,3p-1]=(\eta [0,p-1])^3$, and so $p$ is a period of $\eta$. Otherwise, the lemma is proved by repeating this argument.

■

Applying Lemma 3.2 to the occurrences of $\alpha _n$ at $k$ and $k'$, we obtain that $k'-k$ is a period of $\alpha _n$. Again, applying Lemma 3.2 to the occurrences of $\alpha _n$ at $k+\mathrm{lh}(\alpha _n)+R+a$ and $k'+\mathrm{lh}(\alpha _n)+R+a'$, we obtain that $k'-k+a'-a$ is also a period of $\alpha _n$.

If either $0<k'-k\leq B$ or $0<k'-k+a'-a\leq B$, then we conclude that $\alpha _n$ has a period $p\leq B$. Otherwise, let $q=\min (k'-k,k'-k+a'-a)$ and $r=\max (k'-k,k'-k+a'-a)$. Then $0<r-q\leq B$. Also $r\leq \frac{1}{2}(\mathrm{lh}(\alpha _n)+R+3B)$. Let $\gamma _n=\alpha _n[r,\mathrm{lh}(\alpha _n)-1]$. Then $\mathrm{lh}(\gamma _n)\geq \frac{1}{2}(\mathrm{lh}(\alpha _n)-R-3B)$. Since $r$ is a period of $\alpha _n$, $\gamma _n$ is an initial segment of $\alpha _n$. Since $q$ is also a period of $\alpha _n$, we also have that $\gamma _n$ occurs at coordinate $q$ in $\alpha _n$. Applying Lemma 3.2 to the occurrences of $\gamma _n$ at coordinates $q$ and $r$ in $\alpha _n$, we obtain that $r-q$ is a period of $\gamma _n$. In other words, $r-q$ is a period of $\alpha _n[0,\mathrm{lh}(\gamma _n)-1]$. In all cases we have that for some $l_n\geq \frac{1}{2}(\mathrm{lh}(\alpha _n)-R-3B)$, $\alpha _n[0,l_n-1]$ has a period $p\leq B$.

By telescoping, we may assume that $l_n\geq \mathrm{lh}(\alpha _{n-1})$, and it follows that $\alpha _{n-1}$ has a period $p\leq B$. Again by telescoping, we may assume that there is $p\leq B$ such that for all sufficiently large $n$, $\alpha _n$ has a period $p$. It then follows that $y$ has period $p$, and that $Y$ is finite, a contradiction.

We have thus proved

Theorem 3.3.

Let $(X, T)$ be a rank-one subshift with bounded spacer parameter and let $(Y,S)$ be a subshift. Suppose $(Y,S)$ is a topological factor of $(X, T)$. Then either $Y$ is finite or else $(X, T)$ is isomorphic to $(Y, S)$.

4. Unbounded spacer parameters

In this section we prove

Theorem 4.1.

Let $(X, T)$ be a rank-one subshift with unbounded spacer parameter and let $(Y,S)$ be a subshift. Suppose $(Y,S)$ is a topological factor of $(X, T)$. Then either $Y$ is trivial (that is, a singleton) or else $(X, T)$ is isomorphic to $(Y, S)$.

The rest of this section is devoted to a proof of Theorem 4.1. Throughout this section we assume $(X, T)$ is a rank-one subshift of $2^\mathbb{Z}$ with unbounded spacer parameter. We continue to use $(q_n), (a_{n,i})$, and $(v_n)$, respectively, to denote the cutting parameter, the space parameter, and the induced rank-one sequence.

We first analyze the forms of elements of $X$ as bi-infinite words. In particular, we identify all elements of $X$ with an infinite string of 1s. First, $1^\mathbb{Z}\in X$ and is a unique fixed point. Next, we recall Lemma 3.12 of 11, which states that, given any $K\in \mathbb{Z}$, there is a unique $z\in X$ so that $z$ has a first occurrence of $0$ at coordinate $K$ (i.e., $z(K)=0$ and $z(k)=1$ for all $k<K$); similarly, there is also a unique $z\in X$ so that $z$ has a last occurrence of $0$ at coordinate $K$ (i.e., $z(K)=0$ and $z(k)=1$ for all $k>K$). Recall that $V=\lim _{n\to \infty } v_n$ is the infinite rank-one word which has each $v_n$ as its initial segment. For each $K\in \mathbb{Z}$, define

$$\begin{equation*} z_K(k)=\left\{\begin{array}{ll}1, & \text{ if }k<K,\\V(k-K), &\text{ if }k\geq K. \end{array}\right. \end{equation*}$$

Then $z_K$ is of the form $1^{-\mathbb{N}}V$ with the occurrence of $V$ starting at coordinate $K$. It is easy to verify that $z_K\in X$, and therefore it is the unique $z\in X$ with a first occurrence of $0$ at coordinate $K$.

To describe the unique $z\in X$ so that $z$ has a last occurrence of $0$ at coordinate $K$, we consider a dual infinite rank-one word $V^*$. To define $V^*$, note that each $v_n$ is also an end segment of $v_{n+1}$. This allows us to take a dual limit and obtain $V^*$, where $V^*$ has all $v_n$ as its end segment. More formally, we can define $V^*$ as an infinite word with domain $-\mathbb{N}$, where for each $k\in \mathbb{N}$,

$$\begin{equation*} V^*(-k)=v_n(\mathrm{lh}(v_n)-k-1) \end{equation*}$$

for any $n$ such that $\mathrm{lh}(v_n)>k$. Then for any $K\in \mathbb{Z}$, define

$$\begin{equation*} z^*_K(k)=\left\{\begin{array}{ll}1, & \text{ if }k>K,\\V^*(k-K), &\text{ if }k\leq K. \end{array}\right. \end{equation*}$$

Then $z^*_K$ is the unique $z\in X$ with the last occurrence of $0$ at coordinate $K$. Each $z^*_K$ is of the form $V^*1^\mathbb{N}$.

In summary, the set

$$\begin{equation*} Z=\{ 1^\mathbb{Z}, z_K, z^*_K\,:\, K\in \mathbb{Z}\} \end{equation*}$$

consists precisely of all elements of $X$ which contain an infinite string of 1s. If $x\in X-Z$, then again by Proposition 2.29 of 11, for any $n\geq 1$, $x$ can be written uniquely as

$$\begin{equation*} \cdots \cdots v_n 1^{c_{-1}}v_n 1^{c_0} v_n 1^{c_1}v_n \cdots \cdots \end{equation*}$$

where $c_i\geq 0$ for $i\in \mathbb{Z}$. Once again these occurrences of $v_n$ are called expected occurrences of $v_n$.

Let $(Y, S)$ be a subshift of $b^{\mathbb{Z}}$ for some integer $b\geq 2$. Assume that $Y$ is not a singleton. Assume $\varphi$ is a factor map from $(X, T)$ onto $(Y, S)$. We will show that $\varphi$ is a topological isomorphism. Again, it suffices to show that $\varphi$ is one-to-one.

Let $\{C_0,\dots , C_{b-1}\}$ be the sliding block code corresponding to $\varphi$. Assume that the sliding block code has window size $R+1$, that is, for any $x\in X$, $k\in \mathbb{Z}$, and $j\in [0,b-1]$,

$$\begin{equation*} \varphi (x)=j\iff x[k,k+R]\in C_j. \end{equation*}$$

Applying the sliding block code to $1^\mathbb{Z}$, we obtain a constant element of $Y$ as $\varphi (1^\mathbb{Z})$. Without loss of generality, we assume $\varphi (1^\mathbb{Z})=1^\mathbb{Z}$. Thus, for any $l>R$, an application of the sliding block code to the string $1^l$ results in the string $1^{l-R}$.

By telescoping, we may assume $\mathrm{lh}(v_1)\gg R$. For each $n\geq 1$, let $\alpha _n$ be the block of length $\mathrm{lh}(v_n)-R$ obtained from the application of the sliding block code to $v_n$, that is, for $k\in [0, \mathrm{lh}(v_n)-R-1]$,

$$\begin{equation*} \alpha _n(k)=j\iff v_n[k,k+R]\in C_j. \end{equation*}$$

It is clear that each $\alpha _n$ is an initial segment as well as an end segment of $\alpha _{n+1}$. We let $W$ be the infinite word taken as a limit of $\alpha _n$, that is, so that every $\alpha _n$ is an initial segment of $W$. Similarly, let $W^*$ be the dual limit of $\alpha _n$, that is, $W^*$ is an infinite word with domain $-\mathbb{N}$ so that every $\alpha _n$ is an end segment of $W^*$. Then each $\varphi (z_K)$ is of the form $1^{-\mathbb{N}}W$ and each $\varphi (z^*_K)$ is of the form $W^*1^\mathbb{N}$.

Note that for every $x\in X$, every finite subword of $x$ is a subword of $v_n$ for some $n\geq 1$. It follows that, for every $y\in Y$, every finite subword of $y$ is a subword of $\alpha _n$ for some $n\geq 1$. This implies that $\alpha _n$ cannot be constant for all $n\geq 1$, or else $Y$ would be a singleton. By telescoping, we may assume $\alpha _1$ is not constant. Without loss of generality, we may assume $\alpha _1$ contains an occurrence of $0$.

Let $i_0$ be the first occurrence of 0 in $\alpha _1$ and $i_1$ be the last occurrence of $0$ in $\alpha _1$. Then $\varphi (z_K)$ has its first occurrence of $0$ at $K+i_0$ and $\varphi (z^*_K)$ has its last occurrence of $0$ at $K-\mathrm{lh}(\alpha _1)-i_1-1$. This implies that $\varphi \upharpoonright Z$ is one-to-one. For any $x\in X-Z$, $\varphi (x)$ contains infinitely many $0$s in both directions. Thus $\varphi (Z)\cap \varphi (X-Z)=\emptyset$. To finish our proof, it remains to show that $\varphi \upharpoonright (X-Z)$ is one-to-one.

For this we use the following lemma.

Lemma 4.2.

Let $L\geq \mathrm{lh}(v_1)$. Let $x, x'\in X-Z$ be such that for any $l\geq L$, any spacer of length $l$ in between expected occurrences of $v_1$ in $x$ occurs at the same position as a spacer of the same length in between expected occurrences of $v_1$ in $x'$. Then $x=x'$.

Proof.

First note that, since $X$ has unbounded spacer parameter, there are spacers of length $\geq L$ in between expected occurrences of $v_1$ in $x$. By telescoping, we can assume such spacers occur in $v_2$, that is, for some $1\leq j<q_1$, $a_{1,j}\geq L$. Let $j_1< \dots < j_M$ enumerate all $j\in [1,q_1-1]$ such that $a_{1,j}\geq L$. Note that $x$ can be uniquely written as a concatenation of expected occurrences of $v_2$ with spacers in between:

$$\begin{equation} \cdots \cdots v_2 1^{t_{-1}}v_2 1^{t_0} v_2 1^{t_1}v_2 \cdots \cdots {\tag{3}} \end{equation}$$

where $t_i\geq 0$ for $i\in \mathbb{Z}$. Expanding the expression using

$$\begin{equation*} v_2=v_11^{a_{1,1}}v_1\dots v_11^{a_{1,q_1-1}}v_1, \end{equation*}$$

we obtain the unique expression of $x$ as a concatenation of expected occurrences of $v_1$ with spacers in between, as follows:

$$\begin{equation} \cdots \cdots v_1 1^{c_{-1}}v_1 1^{c_0} v_1 1^{c_1}v_1 \cdots \cdots {\tag{4}} \end{equation}$$

where $c_j\geq 0$ for all $j\in \mathbb{Z}$. Without loss of generality, assume that $1^{c_0}$ in the above expression 4 is a spacer in between expected occurrences of $v_2$ in $x$. Then we have, for all $1\leq j<q_1$, $c_j=a_{1, j}$. Furthermore, we have that for any $k\in \mathbb{Z}$ and $1\leq j<q_1$,

$$\begin{equation*} c_{j+kq_1}=a_{1,j}. \end{equation*}$$

Thus, all spacers $1^{c_j}$ in the above expression 4, except for those corresponding to $j\equiv 0\ (\mathrm{mod}\ q_1)$, exhibit a periodic structure with period $q_1$. In contrast, the spacers $1^{c_j}$ for $j\equiv 0\ (\mathrm{mod}\ q_1)$ do not exhibit a periodic structure with period $q_1$, since their lenghs are unbounded. Among all the spacers demonstrated in 4, the ones with lengths $\geq L$ correspond to $1^{c_j}$ for all $j\equiv j_1, \dots , j_M\ (\mathrm{mod}\ q_1)$ and some $j\equiv 0\ (\mathrm{mod}\ q_1)$.

Now all these observations about $x$ hold similarly for $x'$. In particular, if we similarly express $x'$ as

$$\begin{equation} \cdots \cdots v_1 1^{c'_{-1}}v_1 1^{c'_0} v_1 1^{c'_1}v_1 \cdots \cdots {\tag{5}} \end{equation}$$

with $c'_j\geq 0$ for $j\in \mathbb{Z}$, there are also exactly $M$ many periodic classes of spacers $1^{c'_j}$ with $c'_j\geq L$ and one aperiodic class of spacers.

By our assumption, any spacer of length $\geq L$ in 4 occurs at the same position as a spacer of the same length in 5. Thus the spacers in 4 corresponding to $j\equiv j_1, \dots , j_M\ (\mathrm{mod}\ q_1)$ must align with the corresponding spacers in 5. It follows that any expected occurrence of $v_2$ in $x$ occurs at the same position as an expected occurrence of $v_2$ in $x'$. By Proposition 2.29 of 11, we conclude that $x=x'$.

■

We are now ready to show that $\varphi \upharpoonright (X-Z)$ is one-to-one. Let $x, x'\in X-Z$ and assume that $\varphi (x)=\varphi (x')$. Consider a subword of $x$ of the form $v_11^cv_1$ where $c\geq R$. An application of the sliding block code to $v_11^cv_1$ results in a word of the form

$$\begin{equation*} \alpha _1\eta 1^{c-R}\epsilon \alpha _1 \end{equation*}$$

for some words $\eta$ and $\epsilon$ with $\mathrm{lh}(\eta )=\mathrm{lh}(\epsilon )=R$. Therefore, whenever $v_11^cv_1$ occurs in $x$, there is an occurrence of $\alpha _1\eta 1^{c-R}\epsilon \alpha _1$ in $\varphi (x)$ at the same position.

Let $L=\mathrm{lh}(v_1)+2R$. We now verify that the condition for Lemma 4.2 holds for $x$ and $x'$. For this, suppose $l\geq L$ and $v_11^lv_1$ occurs in $x$ at position $k$, with both ocurrences of $v_1$ expected. As discussed above, there is an occurrence of $\beta =\alpha _1\eta 1^{l-R}\epsilon \alpha _1$ in $\varphi (x)$ at position $k$. Since $\varphi (x)=\varphi (x')$, we get an occurrence of $\beta$ in $\varphi (x')$ at the same position. Note that there are at least $\mathrm{lh}(v_1)+R$ many consecutive 1s in $\beta$. It follows that the occurrence of $\beta$ in $\varphi (x')$ must be induced by an occurrence of $v_11^c v_1$ in $x'$ where $c\geq R$. To see this, assume $c<R$ and that an occurrence of $v_11^cv_1$ induces $\beta$. Then an application of the sliding block code gives an occurrence of $\alpha _1$ at each of the occurrences of $v_1$. Since $\alpha _1$ contains at least one occurrence of $0$, the number of consecutive 1s is bounded by $\mathrm{lh}(v_1)+c<\mathrm{lh}(v_1)+R$, a contradiction.

Since $c\geq R$, an application of the sliding block code yields $\alpha _1\eta 1^{c-R}\epsilon \alpha _1$. We claim $c=l$. To see this, we consider four cases depending on whether $\eta =1^R$ and whether $\epsilon =1^R$. We only argue for the case in which both $\eta \neq 1^R$ and $\epsilon \neq 1^R$, and the other cases are similar. In this case both $\eta$ and $\epsilon$ contain occurrences of symbols other than 1. It is clear that the number of consecutive 1s in $\eta 1^{l-R} \epsilon$ and in $\eta 1^{c-R}\epsilon$ would be different if $l\neq c$.

We have seen that the occurrence of $\beta$ in $\varphi (x')$ is uniquely determined by an occurrence of $v_11^lv_1$ in $x'$. Thus, for every occurrence of a spacer of length $l\geq L$ in $x$, there is an occurrence of a spacer of the same length at the same position in $x'$. By Lemma 4.2, $x=x'$.