Proof. Let $\nu $ be the unique mme of any irreducible component of Z with maximum topological entropy. It is stationary, irreducible, and Markov. Since $\phi \vert _Z$ is finite-to-one and onto Y,

$$ \begin{align*} h(\phi^*(\nu))=h(\nu) =h_{\mathrm{top}} (\mathrm{supp}~ \nu) =h_{\mathrm{top}}(Z) = h_{\mathrm{top}}(Y). \end{align*} $$

Since $\mu _0$ is the unique mme on Y, we have $\phi ^*(\nu )=\mu _0$ .

Proof. (1) $\Rightarrow $ (2): This follows directly from [Reference Lind and MarcusLM95, Corollary 8.1.2].

(2) $\Rightarrow $ (3):

$$ \begin{align*} h_{\mathrm{top}}(Y)= h_{\mathrm{top}}(\mathrm{supp}(\nu)) \ge h(\nu) \ge h(\phi^*(\nu)) = h(\mu_0) = h_{\mathrm{top}}(Y). \end{align*} $$

This yields item (3).

(3) $\Rightarrow $ (1): Apply [Reference ParryPar97, Theorem 2].

((2) and (3)) $\Rightarrow $ (4): The condition that for some $c \ge 0$ , for every periodic point in $\mathrm {supp}(\nu )$ , the $\nu $ -weight per symbol is $e^{-c}$ , is equivalent to the condition that $h(\nu ) = c$ and that $\nu $ is an mme for $\mathrm {supp}(\nu )$ . This is essentially contained in [Reference Petersen, Quas and ShinPT82, Proposition 44].

Proof. The elements of Y are arbitrary concatenations of strings of the form $10^s$ with $s\in S$ such that there exists some allowed block w of length $k+s+1$ satisfying the following:

1. (1) $w_{[1,k]}=D$ ;

2. (2) $w_{[s+2,s+k+1]}=D$ ;

3. (3) for all $2\leq i\leq s+1$ , $w_{[i,k+i-1]}\neq D$ .

Hence, Y is an S-gap shift.

Proof. To prove item (1), first observe that $10^{k-1}1$ is allowed if and only if the image of $DD$ is $10^{k-1}1$ . If $10^{k-1}1$ is not allowed, then the image of $DD$ has a prefix of the form $10^c1$ for some $0\le c \le k-2$ . Let $d = c+1 \le k-1$ . Then for all $0\le i \le k-1$ , $b_i = b_{i+d}$ (here and below in this proof, subscripts are read modulo k). It follows that for all integers $m,n$ and all $0\le i \le k-1$ , $b_i = b_{i+md+nk}$ . Let $e = \gcd (d,k)$ . Then $e = md+nk$ for some $m,n$ . Thus, for all $0\le i \le k-1$ , $b_i = b_{i+e}$ . It follows that $D = b_1 \ldots b_k= (b_1\ldots b_e)^{k/e}$ . Since $e < k$ , $k/e \ge 2$ . So, D is purely periodic.

Conversely, assume that D is purely periodic. Then the image of the block $DD$ is not $10^{k-1}1$ and so $10^{k-1}1$ is not allowed.

We now prove item (2). For $j\geq k$ , we show $10^j1$ is allowed in Y by finding a binary block $x_1x_2\ldots x_{j-k+1}$ such that

(4) $$ \begin{align} \Phi(b_1 \ldots b_k x_1 x_2\ldots x_{j-k+1} b_1 \ldots b_k) =10^j1. \end{align} $$

If $b_1 \ldots b_k=0^k$ , then one immediately verifies that $\Phi (b_1\ldots b_k 1^{j-k+1} b_1\ldots b_k)=10^j1$ . By reversing the roles of $0$ and $1$ in the domain, a similar argument works when $b_1 \ldots b_k=1^k$ .

Now assume that $b_1\ldots b_k\neq 0^k$ and $b_1\ldots b_k\neq 1^k$ . Express $b_1 \ldots b_k$ uniquely by

(5) $$ \begin{align} b_1b_2\ldots b_k =(b_1 \ldots b_m)^s b_1 \ldots b_t \quad (m\geq 2, s\geq 1, 0\leq t<m), \end{align} $$

where $ms+t=k$ and m is the smallest positive integer such that $b_1 \ldots b_k$ can be expressed by equation (5). We consider the following two cases.

Case 1: $j-k+1\geq m$ . In this case, we claim that equation (4) is satisfied by letting $x_1x_2\ldots x_{j-k+1}=1^{j-k+1}$ . To see this, assume to the contrary that

$$ \begin{align*} \Phi((b_1 \ldots b_m)^s b_1 \ldots b_t 1^{j-k+1} (b_1 \ldots b_m)^s b_1 \ldots b_t) \neq 10^j1. \end{align*} $$

This means that there is an extra $1$ in addition to the two $1$ s at the first and the last position in the image. Hence, there is an extra $b_1 \ldots b_k$ in the input in addition to the two at the initial and tail end (these two $b_1 \ldots b_k$ terms will be called the head and the tail, respectively). Since $x_1 \ldots x_{j-k-1} =1^{j-k+1}$ and $b_1 \ldots b_k\neq 1^k$ , this extra $b_1 \ldots b_k$ must start with some $b_1 \ldots b_t$ in the head or end with some $b_1 \ldots b_t$ in the tail. Thus, it must intersect the ‘intermediate’ subblock $x_1 \ldots x_{j-k+1}$ in at least m bits. Therefore, either

(6) $$ \begin{align} x_1 x_2 \ldots x_m= b_{t+1} \ldots b_m b_1 \ldots b_t \end{align} $$

or

(7) $$ \begin{align} x_{j-k-m+2}\ldots x_{j-k+1}=b_1 \ldots b_m. \end{align} $$

Recalling that $x_1 \ldots x_{j-m+1}=1^{j-k+1}$ , either equation (6) or equation (7) implies $b_1 b_2 \ldots b_k=1^k$ , which is a contradiction.

Case 2: $1\leq j-k+1 < m$ . In this case, an extra $b_1 \ldots b_k$ in the input must intersect the head, the tail, and the ‘intermediate’ subblock $x_1 x_2\ldots x_{j-k+1}$ simultaneously. Thus, this extra $b_1 \ldots b_k$ must start with some $b_1 \ldots b_t$ in the head and end with some $b_1 \ldots b_t$ in the tail. Therefore, equation (4) holds as long as

(8) $$ \begin{align} \begin{cases} x_1 \neq b_{t+1} \quad \mbox{and}\quad x_{j-k+1} \neq b_m \quad &\mbox{if }j-k>0,\\ x_1 \neq b_{t+1} &\mbox{if }j-k=0, \end{cases} \end{align} $$

which is always possible for some binary $x_1x_2 \ldots x_{j-k+1}$ .

Proof of Theorem 6.1

Only if part: If S is finite, we are done. So assume that S is infinite. Then $0^\infty \in Y$ . Since there exists a shift space $Z\subset X$ such that $\phi \vert _Z$ is a conjugacy from Z onto Y, Z must have a fixed point z such that $\phi (z)=0^\infty $ . Finally, noting that $D^\infty \notin X$ or $\phi (D^\infty ) \neq 0^\infty $ , we conclude that z must be different from $D^\infty $ .

If part: Assume condition (C2) of the theorem. Up to recoding, we may assume that X is a (1-step) vertex shift $\widehat {X_G}$ , D is a vertex of the graph G, and there is a vertex A in G such that A is distinct from D and G has a self-loop $\tau $ at A. Using irreducibility of X, there are paths in G, $\beta ^+$ from D to A and $\beta ^-$ from A to D, neither of which contains D in its interior. Let $N: =\vert \beta ^+\beta ^-\vert -1$ .

Now Y is a gap shift with gap set of the form $S:= F \cup \{N, N+1, \ldots \}$ , where each element of F is less than N. For each $s\in S$ , choose $\pi ^s$ to be a first-return cycle of length s from D to itself (‘first-return’ means that it does not contain D in its interior). We will assume that for $s\geq N$ , we choose $\pi ^s=\beta ^+ \tau ^{s-N} \beta ^-$ . For $y\in Y$ , let $O_y:= \{j\in \mathbb {Z}: y_j=1\}$ and define $\eta : Y \rightarrow X$ as follows:

1. (D1) if $i\in O_y$ , define $(\eta (y))_i=D$ ;

2. (D2) if $j,j'\in O_y$ and $\{l\in \mathbb {Z}: j<l<j'\}\subset O_y^c$ , define $(\eta (y))_{[j,j']}=V(\pi ^{j'-j})$ ;

3. (D3) if $O_y$ has a maximum element s, define $(\eta (y))_{[s,\infty )}=V(\beta ^+\tau ^{\infty })$ ;

4. (D4) if $O_y$ has a minimum element s, define $(\eta (y))_{(-\infty , s]}=V(\tau ^{\infty } \beta ^-)$ ;

5. (D5) if $O_y=\emptyset $ , define $\eta (y)=A^\infty $ .

Observe that $\eta $ is injective because if $y,y'\in Y$ and $y\neq y'$ , then for some i, without loss of generality, we assume $y_i=1$ and $y_i'=0$ , and so $(\eta (y))_i=D$ and ${(\eta (y'))_i\neq D}$ . Furthermore, we claim that $\eta $ is a sliding block code. To see this, note that $\eta $ is shift-invariant by virtue of its definition, and $(\eta (y))_i$ is a function of $y_{[-N+i, N+i]}$ .

So, $\eta $ is an injective sliding block code from Y into $X=\widehat {X_G}$ . Let Z be its image. Then, $\eta ^{-1}$ is a bijective sliding block code from Z onto Y. Moreover, by the construction of $\eta $ , for every $y\in Y$ ,

(9) $$ \begin{align} \phi \circ \eta(y) =y. \end{align} $$

It follows that $\eta ^{-1} = \phi \vert _Z$ . This completes the proof of the if part assuming condition (C2).

Now assume condition (C1). The proof follows along the same lines except that the definition of $\eta $ is even easier: $S=F$ is a finite set, and we only need the first two cases, definitions (D1) and (D2), of the definition of $\eta $ because for any $y\in Y$ , $O_y$ is a non-empty set with no maximum and no minimum.

Finally, we show that Y must be an SFT (and thus Z must also be an SFT) when condition (C1) or (C2) holds. To see this, first note that an S-gap shift is an SFT if and only if S is either finite or cofinite [Reference Dastjerdi and JangjooDJ12]. If condition (C1) holds, there is nothing to prove. If condition (C2) holds, then the proof of the ‘if part’ above in particular shows that Y is an S-gap shift with $S:=F\cup \{N, N+1, \ldots \}$ , where N is a positive integer and F is a finite subset of non-negative integers. Thus, S is cofinite and therefore Y is an SFT.

Proof. When $k=1$ , $Y=X=X_{[2]}$ and $\phi $ is trivially a conjugacy. Hence, we assume ${k\ge 2}$ throughout the remainder of the proof.

(1) $\Rightarrow $ (2): We consider the following two cases.

Case 1: $b_1 \ldots b_k=0^{k}$ or $b_1 \ldots b_k=1^k$ . Assume $b_1 \ldots b_k=0^{k}$ . Then, Y is an S-gap shift with $S=\{0, k, k+1, \ldots \}$ . Equivalently, Y is an SFT with forbidden set

$$ \begin{align*}\mathcal{F}=\{101,1001, \ldots, 10^{k-1}1\}.\end{align*} $$

Note that any $y\in Y$ can be uniquely expressed by $y=\cdots 1^{m_1}0^{n_1} 1^{m_2}0^{n_2} 1^{m_3} \ldots $ with $m_i\geq 1, n_i\geq k$ . Define

$$ \begin{align*}x:= \cdots 0^{m_1+k-1}1^{n_1-k+1} 0^{m_2+k-1} 1^{n_2-k+1} 0^{m_3+k-1} \ldots.\end{align*} $$

Then, $x\in X_{\mathcal {F}}$ and $\phi (x)=y$ . Hence, $\phi \vert _{X_{\mathcal {F}}}$ is onto.

We then claim that $\phi \vert _{X_{\mathcal {F}}}$ is one-to-one. To see this, consider $x, x'\in X_{\mathcal {F}}$ and $x\neq x'$ . Then, for some i, without loss of generality, we assume $x_i=1, x_i'=0.$ Now, $x_i=1$ implies $(\phi (x))_{[i, i+k-1]}=0^k$ ; however, recalling that $\mathcal {F}=\{101,1001, \ldots , 1{0}^{k-1}1\}$ , we deduce from $x^{\prime }_i=0$ that there is an $i\leq l\leq i+k-1$ such that $x^{\prime }_{[l-k+1, l]}=0^k$ and therefore $(\phi (x'))_l=1$ . Thus, $\phi (x)\neq \phi (x')$ and $\phi \vert _{X_{\mathcal {F}}}$ is one-to-one.

By reversing the roles of $0$ and $1$ in the domain, it follows that $\phi \vert _{X_{\overline {\mathcal {F}}}}: X_{\overline {\mathcal {F}}} \rightarrow X_{\mathcal {F}}$ is also one-to-one and onto when $b_1 \ldots b_k={1}^{k}$ .

Case 2: There is only one $0$ or only one $1$ in $b_1 b_2 \ldots b_k$ . We first assume that $b_j=1$ for some $1\leq j\leq k$ and $b_i=0$ for any $1\leq i\leq k$ and $i\neq j$ . Let $M:=\max \{j-1, k-j\}$ . Then Y is an S-gap shift with $S=\{M, M+1, \ldots \}$ . Equivalently, Y is an SFT with the forbidden set $\mathcal {F}=\{11, 101, \ldots , 10^{M-1} 1\}$ . Expressing any $x\in X_{\mathcal {F}}$ by

$$ \begin{align*} x=\cdots 1 0^{m_{-1}} 1 0^{m_0} 1 0^{m_1} 1 \ldots \end{align*} $$

with $m_l\geq M$ for all $l\in \mathbb {Z}$ , one directly verifies that $\phi (x) = \sigma ^{j-k} (x)$ . Thus, $\phi \vert _{X_{\mathcal {F}}}$ must be one-to-one and onto Y.

By reversing the roles of $0$ and $1$ in the domain, it follows that $\phi \vert _{X_{\overline {\mathcal {F}}}}\rightarrow X_{\mathcal {F}}$ is also one-to-one and onto when there is only one $0$ in $b_{[1,k]}$ .

(2) $\Rightarrow $ (3): Obvious.

(3) $\Rightarrow $ (4): Obvious.

(4) $\Rightarrow $ (1): We prove by way of contradiction. Suppose there are at least two $1$ s and at least two $0$ s in $b_{[1,k]}$ . Then, $k\geq 4$ and $11\in \mathcal {F}$ . We will show that both $\phi \vert _{X_{\mathcal {F}}}$ and $\phi \vert _{X_{\overline {\mathcal {F}}}}$ are not onto by finding a $y\in Y$ and two blocks $B_1\in \mathcal {F}$ and $B_2\in \overline {\mathcal {F}}$ such that any ${x\in \phi ^{-1}(y)}$ contains $B_1$ and $B_2$ . Indeed, if such a y exists, then $y\notin \phi (X_{\mathcal {F}})$ and $y\notin \phi (X_{\overline {\mathcal {F}}})$ , and therefore both $\phi \vert _{X_{\mathcal {F}}}$ and $\phi \vert _{X_{\overline {\mathcal {F}}}}$ are not onto, contradicting item (4).

We consider the following cases.

Case 1: Both $00$ and $11$ are subblocks of $b_1 b_2 \ldots b_k$ . Choose $y\in Y$ with $y_0=1$ . Then, for any $x\in \phi ^{-1}(y)$ , $x_{[-k+1,0]}=b_{[1,k]}$ . Since $11\in \mathcal {F}$ , $00\in \overline {\mathcal {F}}$ , and they are both subblocks of x, we conclude that $\phi \vert _{X_{\mathcal {F}}}$ and $\phi \vert _{X_{\overline {\mathcal {F}}}}$ are not onto.

Case 2: Neither $00$ nor $11$ is a subblock of $b_1 b_2 \ldots b_k$ . In this case, $b_1 b_2 \ldots b_k$ is a binary block with $0$ and $1$ occurring alternately. We assume without loss of generality that $b_1b_2\ldots b_k=010101\ldots $ .

If k is odd, one verifies that $b_1=b_k=0$ , $\mathcal {F}=\{10^j1: j\in \{0, 2, 3, \ldots k-2\}\}$ , and $\overline {\mathcal {F}}=\{01^j0: j\in \{0, 2, 3, \ldots , k-2\}\}$ . Consider $y\in Y$ such that $y_{[0, k]}=1 0^{k-1} 1$ . For any $x\in \phi ^{-1}(y)$ , $x_{[-k+1, k]}=(b_1 b_2 \ldots b_k)^2$ ; in particular, $x_{[-1, 2]}=b_{k-1}b_kb_1b_2=1001\in \mathcal {F}$ and $x_{[0,1]}=b_kb_1=00 \in \overline {\mathcal {F}}$ . Thus, both $\phi \vert _{X_{\mathcal {F}}}$ and $\phi \vert _{X_{\overline {\mathcal {F}}}}$ are not onto.

If k is even, $\mathcal {F}=\{10^j1: j\in \{0, 2, 3, \ldots , k-1\}\}$ and $\overline {\mathcal {F}}=\{01^j0: j\in \{0, 2, 3, \ldots , k-1\}\}$ . Consider $y\in Y$ such that $y_{[0,k+1]}=10^k1$ . Then for any $x\in \phi ^{-1}(y)$ , either $x_{[-k+1, k+1]}=b_1b_2\ldots b_k 0 b_1 b_2\ldots b_k$ or $x_{[-k+1, k+1]}=b_1b_2\ldots b_k 1 b_1 b_2\ldots b_k$ . In the former case, $x_{[0,3]}=1001\in \mathcal {F}$ and $x_{[0,1]}=00\in \overline {\mathcal {F}}$ ; in the latter case, $x_{[0,1]}=11\in \mathcal {F}$ and $x_{[-1,2]}=0110\in \overline {\mathcal {F}}$ . Therefore, $\phi \vert _{X_{\mathcal {F}}}$ and $\phi \vert _{X_{\overline {\mathcal {F}}}}$ are not onto in both cases.

Case 3: Exactly one of $00$ or $11$ is a subblock of $b_1b_2\ldots b_k$ . We assume without loss of generality that $11$ is a subblock of $b_1b_2\ldots b_k$ yet $00$ is not. If for any $2\leq j\leq k-2$ , $01^j0$ is not a subblock of $b_1b_2 \ldots b_k$ , then $b_1b_2 \ldots b_k=1^{m_1} (01)^{m_2} 1^{m_3}$ , where either $m_1\geq 2, m_2 \geq 2, m_3 \geq 0$ or $m_1\geq 0, m_2 \geq 2, m_3 \geq 1$ . In either case, one directly verifies that $11\in \mathcal {F}$ , $010\in \overline {\mathcal {F}}$ . Consider any $y\in Y$ with $y_0=1$ . Then, any $x\in \phi ^{-1} (y)$ satisfies $x_{[-k+1, 0]}= b_1 b_2 \ldots b_k$ , and therefore it contains both $11$ and $010$ . Thus, both $\phi \vert _{X_{\mathcal {F}}}$ and $\phi \vert _{X_{\overline {\mathcal {F}}}}$ are not onto.

Otherwise, there exists $2\leq j\leq k-2$ such that $01^{j}0$ is a subblock of $b_1 b_2 \ldots b_k$ . If $b_1 b_2\ldots b_{k-j-1}\neq b_{j+2}\ldots b_k$ , then $10^j1 \in \mathcal {F}$ and therefore $01^j0 \in \overline {\mathcal {F}}$ . Let $y\in Y$ be such that $y_0=1$ . Then, for any $x\in \phi ^{-1}(y)$ , $x_{[-k+1, 0]}=b_1 b_2 \ldots b_k$ , and therefore x contains both $11\in \mathcal {F}$ and $01^j0 \in \overline {\mathcal {F}}$ . Hence, both $\phi \vert _{X_{\mathcal {F}}}$ and $\phi \vert _{X_{\overline {\mathcal {F}}}}$ are not onto.

If $b_1 b_2\ldots b_{k-j-1}= b_{j+2}\ldots b_k$ , then

$$ \begin{align*} b_1 b_2 \ldots b_k= \begin{cases} 1^{s_1} (01^j)^{m_1}& \mbox{with } 0\leq s_1\leq j, m_1\geq 2\\ &\mbox{and } s_1+m_1(j+1)=k \\ \mbox{ or } \\ 1^{s_2} (01^j)^{m_2} 01^{t_2} & \mbox{with } 0\leq s_2 \leq j, m_2\geq 1, 0\leq t_2\leq j-1\\ &\mbox{and } s_2+m_2(j+1)+t_2+1=k, \end{cases} \end{align*} $$

and $10^{i}1\in \mathcal {F}$ for any $j+1\leq i\leq 2j$ .

Subcase 3.1: $b_1 b_2 \ldots b_k=1^{s_1} (01^j)^{m_1}$ for some $0\leq s_1\leq j$ and $m_1\geq 2$ . If $s_1=0$ , $b_1b_2\ldots b_k=(01^j)^{m_1}$ and it is purely periodic. In this case, we infer from Proposition 5.2(1) that $10^{k-1}1$ is not allowed in Y but $10^{k}1$ is. Consider $y\in Y$ with $y_{[0,k+1]}=10^k1$ . For any $x\in \phi ^{-1}(y)$ , either $x_{[-k+1, k+1]}=b_1 b_2\ldots b_k 0 b_1 b_2\ldots b_k = (01^j)^{m_1} 0 (01^j)^{m_1}$ or $x_{[-k+1, k+1]}=b_1 b_2\ldots b_k 1 b_1 b_2\ldots b_k = (01^j)^{m_1} 1 (01^j)^{m_1}$ . In the former case, $x_{[0,1]}=00\in \overline {\mathcal {F}}$ ; in the latter case, $x_{[-j-1,1]}=01^{j+1}0 \in \overline {\mathcal {F}}$ . Since $b_1 b_2 \ldots b_k$ contains $11\in \mathcal {F}$ , we conclude that both $\phi \vert _{X_{\mathcal {F}}}$ and $\phi \vert _{X_{\overline {\mathcal {F}}}}$ are not onto.

If $s_1\neq 0$ , $b_1b_2\ldots b_k$ is not purely periodic. Hence, we infer from Proposition 5.2(1) that $10^{k-1}1$ is allowed in Y. A similar argument as in Case 2 for odd k implies that both $\phi \vert _{X_{\mathcal {F}}}$ and $\phi \vert _{X_{\overline {\mathcal {F}}}}$ are not onto.

Subcase 3.2: $b_1 b_2 \ldots b_k=1^{s_2} (01^j)^{m_2}01^{t_2}$ for some $0\leq s_2\leq j$ , $m_2\geq 1$ , and $0\leq t_2 \leq j-1$ . If $s_2=j$ and $t_2=0$ , $b_1b_2\ldots b_k=(1^j0)^{m_2}$ . By reversing the roles of $0$ and $1$ , a similar argument as in Subcase 3.1 for $s_1=0$ implies that both $\phi \vert _{X_{\mathcal {F}}}$ and $\phi \vert _{X_{\overline {\mathcal {F}}}}$ are not onto.

If $s_2\neq j$ or $t_2\neq 0$ , a similar argument as in Subcase 3.1 for $s_1 \neq 0$ again implies that both $\phi \vert _{X_{\mathcal {F}}}$ and $\phi \vert _{X_{\overline {\mathcal {F}}}}$ are not onto.

Proof. (1) $\Rightarrow $ (2): Suppose there is a set $W\subseteq T_1$ such that $\bigcup _{i \in W} K_i = \bigcup _{i \in T_1} K_i$ and $\{K_i: i \in W\}$ are pairwise disjoint.

Denote

$$ \begin{align*} S^{(0)}&=\bigcup_{i\in W} \{n \in \mathbb{Z}_{\geq 0}: n\in K_i \bmod D, n\geq m_i \}, \\ S^{(1)}&=\bigcup_{i\in T_1} \{n \in \mathbb{Z}_{\geq 0}: n\in K_i \bmod D, n\geq m_i \},\\ S^{(2)}&=\{\vert C_i \vert -1: i\in T_0\}. \end{align*} $$

We first construct a new graph H from the graph G through the following three steps:

1. (A) let H be the graph consisting of the central state $B\in \mathcal {V}(G)$ and all the spokes $U_i\subset G$ with $i\in W$ ;

2. (B) for each $r\in S^{(1)} \setminus S^{(0)}$ , add to H a simple cycle, denoted $C(r)$ , of length $r+1$ starting and ending with B;

3. (C) for each $s\in S^{(2)} \setminus S^{(1)}$ , choose an $i(s)\in T_0$ such that $\vert C_i \vert = s+1$ . Add the degenerate spoke $U_{i(s)}$ to H.

See Figure 2 for an example of the construction of H.

Figure 2 An example of G and H, where dots denote vertices, and $U_i$ terms and $U_i'$ terms are spokes in G and H, respectively. For this example, $T_0=\{3,4\}, T_1=\{1,2\}, W=\{2\}$ and $H_1=U_2', H_2=U_1'\cup U_3', H_3=U_4'$ .

Let $H_1, H_2, H_3$ denote subgraphs consisting of spokes added to H in steps (A), (B), and (C), respectively. It is worth noting that any $r\in S^{(1)}\setminus S^{(0)}$ corresponds to a ‘gap’ in regular spokes of G that is missing from $\{U_i: i\in W\}$ , and any $s\in S^{(2)}\setminus S^{(1)}$ corresponds to a ‘gap’ in degenerate spokes of G that is missing from $\{U_i: i\in T_1\}$ .

The following properties are immediate from the construction of H.

1. (a) H is a spoke graph. It consists of the central state B and several spokes intersecting at B, where spokes in $H_1$ are regular spokes and spokes in $H_2\cup H_3$ are degenerate spokes.

2. (b) $H_1\cup H_3$ is a subgraph of G.

3. (c) If $\eta _1$ and $\eta _2$ are two different simple cycles at B in H, then $\vert \eta _1\vert \neq \vert \eta _2\vert .$

Now, define a one-block map $\Psi : \mathcal {V}(H)\rightarrow \mathcal {V}(G)$ as follows:

• • for $v\in \mathcal {V}(H_1\cup H_3)$ , let $\Psi (v)=v$ ;

• • for any $r\in S^{(1)}\setminus S^{(0)}$ , choose a cycle $\widetilde {C}(r)$ in G starting and ending with B with no B in its interior such that $\vert \widetilde {C}(r) \vert = \vert C(r) \vert $ . Define

  $$ \begin{align*} \Psi(V(C(r))):= V(\widetilde{C}(r)). \end{align*} $$

Note that for any two distinct vertices $v_1, v_2\in \mathcal {V}(H)$ , $\Psi (v_1)=\Psi (v_2)$ only if there exist $r_1, r_2\in S^{(1)}\setminus S^{(0)}$ with $r_1 \neq r_2$ such that $v_1\in V(C(r_1))$ and $v_2\in V(C(r_2))$ , where $C(r_1)$ and $C(r_2)$ are constructed in step (B).

Let $\psi :\widehat {X_H}\rightarrow \widehat {X_G}$ be the sliding block code induced by $\Psi $ and define $Z: =\psi (\widehat {X_H})$ . Note that any point $z\in Z$ is a concatenation of strings of the form

(11) $$ \begin{align} Bu_1 u_2 \ldots u_k B,\quad \ldots v_{-3}v_{-2}v_{-1} B,\quad Bw_1w_2w_3\ldots,\quad \ldots i_{-2} i_{-1} i_0 i_1 i_2 \ldots, \end{align} $$

where $u_j$ terms, $v_j$ terms, $w_{j}$ terms, and $i_j$ terms are vertices in G distinct from B. Thus, to show that $\psi $ is one-to-one, it suffices to show that any string in equation (11) has a unique $\Psi $ -pre-image, and we prove this by considering the following cases.

1. (1) Any allowed block of the form $Bu_1 u_2 \ldots u_k B$ in $\widehat {X_G}$ must be the $\Psi $ -image of some block of the form $B x_1 x_2 \ldots x_k B$ with $x_i\in \mathcal {V}(H)$ for any $1\leq i\leq k$ . Noting from property (c) that each $B x_1 x_2 \ldots x_k B$ is uniquely determined by its length, we conclude that the $\Psi $ -pre-image of $Bu_1 u_2 \ldots u_k B$ is unique.

2. (2) For simplicity, among the infinite paths in equation (11), we consider only those of the form $\ldots v_{-3}v_{-2}v_{-1} B$ in $\widehat {X_G}$ . Such a string must be the $\Psi $ -image of some string of the form $\ldots x_{-3} x_{-2} x_{-1} B$ with $x_i\in \mathcal {V}(H_1)$ . Since $\Psi $ is the identity map on $\mathcal {V}(H_1\cup H_3)$ , $\ldots v_{-3}v_{-2}v_{-1} B$ has a unique $\Psi $ -pre-image.

Let $Z:=\psi (\widehat {X_H})$ . Then Z is an irreducible SFT because it is conjugate to $\widehat {X_H}$ . We now prove that $\phi \vert _Z$ is almost invertible and onto Y. Note that by definition, $\Phi \circ \Psi $ maps the central state B to $1$ and maps all other vertices in H to $0$ . So $\phi \circ \psi $ is the standard factor code on the spoke graph H.

To see that $\phi \circ \psi $ is onto, first note that the image $(\phi \circ \psi )(\widehat {X_{H}})$ is a gap shift with gaps of the form

$$ \begin{align*} S' &:= S^{(0)} \cup (S^{(1)} \setminus S^{(0)}) \cup (S^{(2)}\setminus S^{(1)}) \\ &=S^{(0)} \cup S^{(1)} \cup S^{(2)}\\ &=S^{(1)} \cup S^{(2)}, \end{align*} $$

where we use the fact that $S^{(0)}\subset S^{(1)}$ in the last equation. Since $\bigcup _{i \in W} K_i = \bigcup _{i \in T_1} K_i$ , we have $S' =S$ , where S is such that Y is an S-gap shift. Therefore, $\phi \circ \psi $ is onto.

We now show that $\phi \circ \psi $ is finite-to-one. We first note from the construction of H that for any $t\in S$ , there is a unique cycle of length $t+1$ in H starting and ending with B, whose interior does not contain B. Hence, for any $t\in S$ , there is a unique path in H whose image under $\Phi \circ \Psi $ is $10^t1$ . This implies that $\phi \circ \psi $ has no graph diamond and therefore it is finite-to-one.

Since the central state B is the only vertex in H whose $(\Phi \circ \Psi )$ -image is $1$ , and since $\phi \circ \psi $ is a finite-to-one 1-block code on a 1-step SFT, its degree is $1$ (by [Reference Lind and MarcusLM95, Theorem 9.1.11(3) and Proposition 9.1.12]) and therefore it is almost invertible.

Finally, since $\phi \circ \psi $ is almost invertible and onto Y, and $\psi $ is a conjugacy from $\widehat {X_H}$ to Z, we conclude that $\phi \vert _{Z}: Z\rightarrow Y$ is almost invertible and onto.

(2) $\Rightarrow $ (3): As we said in §2, any almost invertible factor code on an irreducible SFT is finite-to-one [Reference Lind and MarcusLM95, Proposition 9.2.2].

(3) $\Rightarrow $ (1): Suppose that there is an irreducible SFT $Z\subset X$ such that $\phi \vert _{Z}$ is finite-to-one and onto. Let k be the degree of $\phi \vert _{Z}$ and L be the maximum length of words in a forbidden list of blocks from X that defines Z. Then, it follows from our definition of the degree of finite-to-one codes in §2 that there exist a word of the form $u:=0^{e_1}10^{e_2}1\ldots 10^{e_n}$ with $e_i \in S$ , an integer $L\leq M\leq \vert u\vert $ , and an index $1\leq j\leq \vert u \vert -M+1$ such that the set

$$ \begin{align*} E:=\{v_{[j, j+M-1]}: v\in\mathcal{B}(Z), \Phi(v) =u\} \end{align*} $$

has cardinality k. Note that u is a magic word and $u_{[j, j+M-1]}$ is the corresponding magic block.

For notational convenience, in the remainder of this proof, for any block w with length $\vert u \vert $ , we use the following notation:

$$ \begin{align*} \overline{w}:= w_{[1, j-1]}, \quad \widetilde{w}:=w_{[j, j+M-1]}, \quad \widehat{w}:=w_{[j+M, \vert u\vert]}, \end{align*} $$

where u, j, and M are defined as above.

Denote elements in E by $a^{(1)}, a^{(2)}, \ldots , a^{(k)}$ and for any $1\leq l \leq k$ , define

$$ \begin{align*} B^{(l)}:=\{v\in \mathcal{B}(Z): \Phi(v)=u, \widetilde{v}=a^{(l)}\} \quad \mbox{and} \quad R:=\bigcup_{1\leq l\leq k} B^{(l)}. \end{align*} $$

Note that R is the set of all $\phi \vert _{Z}$ -pre-images of u. By a higher block recoding similar to [Reference Lind and MarcusLM95, Proposition 9.1.7], the following observation follows from [Reference Lind and MarcusLM95, Proposition 9.1.9 (part 2)].

For any $1\leq l\leq k$ , define

$$ \begin{align*} F^{(l)}:=\{i\in T_1: &vV(\gamma_i^+ (C_i)^L \gamma_i^-)w \in \mathcal{B}(Z) \mbox{ for some }v\in B^{(l)}\mbox{ and some }w\in R \} \end{align*} $$

to be the index set of regular spokes that can follow some pre-images of u in $B^{(l)}$ and precede some pre-images of u in R. We claim that for any $1\leq l\leq k$ , $\{K_i: i\in F^{(l)}\}$ are pairwise disjoint and $\bigcup _{i\in F^{(l)}} K_i =\bigcup _{i\in T_1} K_i.$ We assume without loss of generality that $l=1$ in the following.

To show $\{K_i: i\in F^{(1)}\}$ are pairwise disjoint, we suppose to the contrary that there exists $f\in K_{i_1} \cap K_{i_2}$ for some $i_1, i_2\in F^{(1)}$ with $i_1\neq i_2$ . Choose $n(f)= f (\bmod \ D)$ such that $n(f)\geq \max \{d_{i_1} L+m_{i_1}, d_{i_2} L+m_{i_2}\}$ . Then, $n(f)\in S$ and according to the definition of $F^{(1)}$ , there are $v, x\in B^{(1)}$ , $w\in B^{(l_1)}$ , $y\in B^{(l_2)}$ for some $1\leq l_1, l_2 \leq k$ such that

$$ \begin{align*} \Phi(vV(\gamma_{i_1}^+ (C_{i_1})^{(n(f)-m_{i_1})/d_{i_1}}\gamma_{i_1}^- )w)&=\Phi(xV( \gamma_{i_2}^+ (C_{i_2})^{(n(f)-m_{i_2})/d_{i_2}}\gamma_{i_2}^- )y)=u10^{n(f)}1 u, \notag \\ \mbox{and} \quad \widetilde{v}=\widetilde{x}=a^{(1)}&, \quad \widetilde{w}=a^{(l_1)}, \quad \widetilde{y}=a^{(l_2)}. \notag \end{align*} $$

Then, we infer from Observation 1 that $l_1=l_2$ and therefore $\widetilde {w}=\widetilde {y}=a^{(l_1)}$ . Now, the two words

(12) $$ \begin{align} \widetilde{v} \widehat{v}V( \gamma_{i_1}^+ (C_{i_1})^{(n(f)-m_{i_1})/d_{i_1}}\gamma_{i_1}^-) \overline{w} \widetilde{w} \quad \mbox{and} \quad \widetilde{x} \widehat{x} V(\gamma_{i_2}^+ (C_{i_2})^{(n(f)-m_{i_2})/d_{i_2}}\gamma_{i_2}^-) \overline{y} \widetilde{y} \end{align} $$

are both $\phi \vert _{Z}$ -pre-images of $\widetilde {u} \widehat {u}1 0^{n(f)}1 \overline {u}\widetilde {u}$ , and they both start with $a^{(1)}$ and end with $a^{(l_1)}$ . Since $a^{(1)}$ and $a^{(l_1)}$ both have length M, which is no less than L, we deduce that the two words in equation (12) can be extended to a point diamond, contradicting the fact that $\phi \vert _Z$ is finite-to-one.

To show $\bigcup _{i\in F^{(1)}} K_i =\bigcup _{i\in T_1} K_i,$ assume to the contrary that there is a $g\in \bigcup _{i\in T_1} K_i$ but $g\notin \bigcup _{i\in F^{(1)}} K_i$ . Choose $n(g):= g\ (\bmod \ D)$ such that $n(g)> \max \{ d_i: i\in T_0\} $ and $n(g)\geq \max \{d_i L + m_i: i\in T_1\}$ . Then, $n(g)\in S$ and we deduce from the definition of $F^{(1)}$ that the set

$$ \begin{align*} Q:=\{z_{[j, j+M-1]}: z\in \mathcal{B}(Z), \Phi(z)= u 10^{n(g)}1 u\} \end{align*} $$

does not contain $a^{(1)}$ . Noting that $Q\subset \{a^{(1)}, a^{(2)}, \ldots , a^{(k)}\}$ , since u is a magic word, the cardinality of Q is at most $k-1$ . This contradicts the fact that $\phi \vert _{Z}$ has degree k, and therefore $\bigcup _{i\in F^{(1)}} K_i =\bigcup _{i\in T_1} K_i$ .

Now let $W= F^{(1)}$ . Then, we immediately infer from above that W is the desired set and therefore complete the proof.

Proof. For any $1\leq i<j\leq k$ , let $g_{i,j}=gcd(d_i, d_j)$ . Then $g_{i,j}$ divides $x_{i,j}-a_i$ and $x_{i,j}-a_j$ so $g_{i,j}$ divides $a_i-a_j$ . Hence, the generalized Chinese remainder theorem [Reference LeVequeLe56, Theorem 3-12] asserts that there is a common solution to $x=a_i \ (\bmod \ d_i), i=1,2,\ldots , k$ .

Proof. Fix a congruence class $0\le j < D$ and let $\mu _0$ be the unique mme on Y.

Since $\phi (\nu ) = \mu _0$ , for all $n\ge \max _{i\in T} m_i/D$ ,

$$ \begin{align*} \mu_0(10^{Dk + j + Dn}1) = \sum_{i \in R_j} \nu(V(\gamma_i^+ (C_i)^{(1/d_i)(Dk + j + Dn - m_i)}\gamma_i^-)). \end{align*} $$

Let

$$ \begin{align*} Q_i := \nu(V(C_i) \vert V(\gamma_i^+(C_i)^{(1/d_i)Dk})). \end{align*} $$

Since $\mu _0(1) = \nu (B)$ , using the formula for the unique mme $\mu _0$ , we have

$$ \begin{align*} Q^{-(Dk + j + Dn + 1)} &= \sum_{i \in R_j} \Pi_i (Q_i^{1/d_i})^{-m_i} (Q_i^{1/d_i})^{Dn+j}(1-Q_i) \\ &= \sum_{i \in R_j\cap P} \Pi_i (Q_i^{1/d_i})^{-m_i} (Q_i^{1/d_i})^{Dn+j}(1-Q_i) \end{align*} $$

and so

$$ \begin{align*} Q^{-(Dk + 1)} = \sum_{i \in R_j\cap P} \Pi_i (Q_i^{1/d_i})^{-m_i} \left(\frac{Q_i^{1/d_i}}{Q^{-1}}\right)^{Dn+j}(1-Q_i). \end{align*} $$

Letting $n \rightarrow \infty $ , we have for all $i \in R_j \cap P$ ,

(14) $$ \begin{align} \frac{Q_i^{1/d_i}}{Q^{-1}} = 1. \end{align} $$

This yields equation (13) and proves item (a).

Since Y is a gap shift, $\mu _0$ is fully supported and so gives positive measure to each allowed gap. Thus, $\bigcup _{i \in T_1 \setminus P} K_i \subset \bigcup _{i \in P} K_i$ , proving item (b).

To see item (c), we first derive from equation (13) that

$$ \begin{align*} \sum_{i \in R_{j'}\cap P} \Pi_iQ^{m_i+1}(1 - Q^{-d_i}) = Q^{-Dk} = \sum_{i \in R_j\cap P} \Pi_iQ^{m_i+1}(1 - Q^{-d_i}). \end{align*} $$

Thus,

$$ \begin{align*} \sum_{i \in (R_{j}\cap P) \setminus (R_{j'} \cap P)} \Pi_iQ^{m_i + 1}(1 - Q^{-d_i}) =0, \end{align*} $$

which immediately implies $ (R_{j}\cap P) \setminus (R_{j'} \cap P) = \emptyset $ .

Proof. For notational convenience, we rewrite j by $j_1$ and define $\small S(i_1, i_2, j_1)\kern1.3pt{:=}\kern1.3pt(R_{j_1} \kern1.3pt{\cap}\kern1.3pt P) \kern1.2pt{\setminus} \{i_1, i_2\}$ , where $R_{j_1}$ is defined in Lemma 9.4.

We first show that $S(i_1, i_2, j_1)\neq \emptyset $ . Suppose to the contrary that $S(i_1, i_2, j_1)= \emptyset $ . Then, $R_{j_1}\cap P=\{i_1\}$ . Since $K_{i_1} \cap K_{i_2}\neq \emptyset $ , there exists $j_2\in K_{i_1} \cap K_{i_2}$ and therefore $R_{j_2}\cap P \supset \{i_1, i_2\}$ . Hence, $R_{j_1}\cap P\subsetneq R_{j_2} \cap P$ , contradicting Lemma 9.4(c).

We then claim that there exists $i_3\in S(i_1, i_2, j_1)$ such that $K_{i_2} \cap K_{i_3}=\emptyset $ . If not, then

$$ \begin{align*} K_{i_2} \cap K_i\neq \emptyset \quad \mbox{ for any }i\in S(i_1, i_2, j_1). \end{align*} $$

Recalling that $j_2\in K_{i_1}\cap K_{i_2}$ and $j_1\in K_{i_1} \cap (\bigcap _{i\in S(i_1, i_2, j_1)}K_i)$ , we derive from Lemma 9.3 that there exists $j_4\in K_{i_1} \cap K_{i_2} \cap (\bigcap _{i\in S(i_1, i_2, j_1)} K_i).$ Hence,

$$ \begin{align*}R_{j_1}\cap P =\{i_1\}\cup S(i_1, i_2, j_1) \subsetneq \{i_1, i_2\}\cup S(i_1, i_2, j_1) \subset R_{j_4}\cap P,\end{align*} $$

contradicting Lemma 9.4(c).

Proof. According to Theorem 8.1, it suffices to show that there is a $W\subset T_1$ such that $\bigcup _{i\in W} K_i = \bigcup _{i\in T_1} K_i$ and $\{K_i: i\in W\}$ are pairwise disjoint.

Proof of item $(a)$ : Let $A:= \bigcup _{i\in P} K_i$ . Note that $P \ne \emptyset $ by the existence of $\nu $ . Let ${j\in \bigcap _{i\in P} K_i}$ . Apply Lemma 9.4(c) to this j and an arbitrary $j' \in A$ to get that for all $i \in P$ , $i \in \bigcap _{j'\in A} R_{j'}$ and so each $K_i = A$ . By Lemma 9.4(b), $A = \bigcup _{i \in T_1} K_i$ . Hence, W can be taken to consist of only one element, namely any element of P.

Proof of item $(b)$ : Since $K_i$ terms are pairwise intersecting, an application of Lemma 9.3 to $\{K_i: i\in P\}$ implies that $\bigcap _{i\in P} K_i\neq \emptyset $ which is item (a).

Proof of item $(c)$ : We assume without loss of generality that the $K_i$ terms are distinct. Denote

(15) $$ \begin{align} F:= \{i\in E_1: K_i\cap K_{i'} = \emptyset \mbox{ for all } i'\in E_2\}. \end{align} $$

We claim that for any $i\in E_1 \setminus F$ , $K_i\subset \bigcup _{i'\in E_2} K_{i'}$ . To see this, assume to the contrary that there are $i_1 \in E_1 \setminus F$ and $j\in K_{i_1}$ such that $j \notin \bigcup _{ i' \in E_2} K_{i'}$ . Recalling that $K_{i_1} \cap K_{i_2} =\emptyset $ for $i_1, i_2\in E_1$ with $i_1\neq i_2$ , we have $R_{j}\cap P=\{i_1\}$ . However, $i_1 \in E_1 \setminus F$ implies that there exists $j'\in K_{i_1}$ and $i_3\in E_2$ such that $j'\in K_{i_1} \cap K_{i_3}$ . Hence, $R_{j'}\cap P\supset \{i_1, i_3\} \supsetneq \{i_1\}=R_{j} \cap P$ , which contradicts Lemma 9.4(c).

Now let $W:= F \cup E_2$ . Clearly $\{K_i: i\in W\}$ are pairwise disjoint by the definition of F. Since $K_i\subset \bigcup _{i'\in E_2} K_{i'}$ for any $i\in E_1 \setminus F$ , $\bigcup _{i\in W} K_i=\bigcup _{i\in P} K_i=\bigcup _{i\in T_1} K_i$ , proving item (c).

Proof of item $(d)$ : By adding repeated spokes (for which the choice of the set W is not affected), we can regard the cases $\vert P\vert <5$ as special cases of $\vert P \vert =5$ . Hence, we assume $\vert P \vert =5$ in the following.

Let $P=\{1,2,3,4,5\}$ . A pair $i,i'\in P$ is called an intersecting pair if $K_i \ne K_{i'}$ and $K_i \cap K_{i'} \ne \emptyset $ . We consider the following cases.

Case 1: For any intersecting pair $i, i'\in P$ , either $K_{i}\subset K_{i'}$ or $K_{i'}\subset K_{i}$ .

In this case, we define a partial order $\preccurlyeq $ in the following way: if $i,i'$ is an intersecting pair and $K_i \subset K_{i'}$ , then $K_i\preccurlyeq K_{i'}$ ; if $i ,i'$ is not a intersecting pair, then $K_i$ and $K_{i'}$ are incomparable.

The partial order $\preccurlyeq $ partitions the set $\{K_i: i\in P\}$ into several classes such that:

1. (1) each class is a chain with a unique maximal element (under $\preccurlyeq $ );

2. (2) if $K_i$ and $K_{i'}$ are from different classes, then $K_{i} \cap K_{i'}=\emptyset $ .

Hence, letting W be the indices of all the maximal elements, we have $\{K_i: i\in W\}$ are pairwise disjoint and $\bigcup _{i\in W} K_i = \bigcup _{i\in P} K_i =\bigcup _{i\in T_1} K_i$ .

Case 2: There exists an intersecting pair $i, i'\in P$ such that both $K_{i} \nsubseteq K_{i'}$ and ${K_{i'} \nsubseteq K_{i}}$ .

First note that in this case, we necessarily have $d_i\neq d_{i'}$ . We may assume that $i=1$ , $i'=2$ , and ${l.c.m.(d_1, d_2)}/{d_1} \geq 3$ . Let $j_1\in K_1\cap K_2$ , $j_2\triangleq (j_1+d_1) \bmod (l.c.m.(d_1, d_2))$ , and $j_3\triangleq (j_2+ d_1) \bmod (l.c.m.(d_1, d_2))$ , where $0\leq j_2,j_3 < l.c.m.(d_1, d_2)$ . Then $j_2, j_3\in K_1\setminus K_2$ . Furthermore, there is also a $j_4\in K_2 \setminus K_1$ . Applying Lemma 9.5 to $j_2, j_3, j_4$ , we deduce that there exist $l_1, l_2, l_3\in \{3,4,5\}$ such that

(16) $$ \begin{align} j_2\in K_1 \cap K_{l_1}, \quad K_{l_1} \cap K_2 =\emptyset, \end{align} $$

(17) $$ \begin{align} j_3\in K_1 \cap K_{l_2}, \quad K_{l_2} \cap K_2 =\emptyset, \notag \\ j_4\in K_2 \cap K_{l_3}, \quad K_{l_3} \cap K_1 =\emptyset. \end{align} $$

Note that we necessarily have $l_3\neq l_1$ and $l_3\neq l_2$ . We now claim that $l_1\neq l_2$ . To see this, suppose that $l_1=l_2=l$ . Then $j_2\in K_l, j_3\in K_l$ . Since $ j_3=(j_2+d_1) \bmod (l.c.m.(d_1, d_2))$ and $j_2\in K_1, j_3\in K_1$ , we have $K_l\subset K_1$ . Hence, $j_1\in K_1 \cap K_2 \cap K_l$ , contradicting the fact that $K_2\cap K_l=\emptyset $ . (See Figure 4, where for any $r,s$ , a $\bullet $ (respectively, a $\times $ ) on the $(r,s)$ position means that $j_r\in K_s$ (respectively, $j_r\notin K_s$ )).

Figure 4 Relationship between $K_1, K_2$ , and $K_l$ if $l_1=l_2=l$ .

Hence, $l_1, l_2$ , and $l_3$ are distinct. We may assume that $l_1=3, l_2=4$ , and $l_3=5$ . The current relation between $\{K_1, K_2 ,K_3, K_4,K_5\}$ is given in Figure 5, where $?$ means that whether this position is $\bullet $ or $\times $ is unknown up to now.

Figure 5 Relationship between $K_1, K_2 ,K_3, K_4, K_5$ with some unknowns.

We then claim that $j_3\notin K_3$ and $j_2\notin K_4$ (that is, $?_1=?_2=\times $ in Figure 5). To verify this claim, assume without loss of generality that $j_3\in K_3$ . Then $j_2\in K_1\cap K_3$ and ${j_3\in K_1 \cap K_3}$ . Noting that $j_3-j_2=d_1 \bmod (l.c.m.(d_1, d_2))$ , we must have $K_3\supset K_1$ , which contradicts the fact that $j_1\in K_1 \setminus K_3$ . Hence, $j_3\notin K_3$ . A similar argument shows that $j_2\notin K_4$ , proving the claim.

Now the relationship between $\{K_1, K_2, K_3, K_4, K_5\}$ is partially characterized in Figure 6.

Figure 6 Relationship between $K_1, K_2 ,K_3, K_4, K_5$ .

We then claim that $K_3\cap K_4=\emptyset $ . To see this, suppose to the contrary that there is a $j_5\in K_3\cap K_4$ . Since $j_2\in K_1\cap K_3$ , $j_3\in K_1\cap K_4$ , we infer from Lemma 9.3 that there is a $j_6\in K_1\cap K_3 \cap K_4$ , contradicting Lemma 9.4(c).

Now let $E_1:=\{1,5\}, E_2:=\{2,3,4\}$ . Since $\{K_i: i\in E_1\}$ and $\{K_i: i\in E_2\}$ are both pairwise disjoint, the desired result follows from item (c).

Proof. We first show that equation (18) has a solution. Suppose $n=s\cdot d_1+t\cdot d_2$ for some $s,t\in \mathbb {Z}_{\geq 0}$ . If $t< u$ , then $x=s, y=t$ is a solution to equation (18); otherwise, if $t\geq u$ , then there exist non-negative integers $k,r$ with $0\leq r< u$ such that $t=k u +r$ . Hence, we have

(19) $$ \begin{align} n&= s \cdot d_1 + t \cdot d_2 \notag \\ &=s\cdot d_1+(ku+r) d_2 \notag \\ &= s \cdot d_1 + k \cdot (l.c.m.(d_1 ,d_2))+r d_2 \notag \\ &= \bigg(s+ k\cdot \frac{l.c.m. (d_1, d_2)}{d_1}\bigg) d_1 + r d_2. \end{align} $$

Since $d_1 \mid l.c.m. (d_1, d_2)$ and $0\leq r<u$ , we conclude from equation (19) that $x=s+ k\cdot {l.c.m. (d_1, d_2)}/{d_1}, y=r$ is a solution to equation (18).

We now prove that equation (18) has no more than one solution. Suppose to the contrary that there exist two different pairs of integers $(x_1, y_1)$ and $(x_2, y_2)$ that satisfy equation (18) and without loss of generality $y_1<y_2$ . Now we have $ x_1 \cdot d_1 + y_1 \cdot d_2 = x_2 \cdot d_1 + y_2 \cdot d_2=n, $ which implies $ (y_2-y_1) d_2 = (x_1-x_2) d_1$ . Hence, $d_1 \mid (y_2-y_1) d_2$ and it follows that

(20) $$ \begin{align} (y_2-y_1) d_2\geq l.c.m. (d_1, d_2), \end{align} $$

since $d_2 \mid (y_2-y_1) d_2$ . However, recalling that $y_1, y_2<u$ , we have $y_2-y_1<u$ and

$$ \begin{align*} (y_2-y_1) d_2< u\cdot d_2 = \frac{l.c.m.(d_1, d_2)}{d_2}\cdot d_2 = l.c.m. (d_1, d_2), \end{align*} $$

contradicting equation (20).

Proof of Proposition 10.1

We first note that the image Y of $\phi $ is a gap shift with gap set

$$ \begin{align*} S:= \{n \in \mathbb{Z}_{\geq 0}: n=m+s \cdot d_1 +t\cdot d_2 \mbox{ with } s,t \in \mathbb{Z}_{\geq 0}\}, \end{align*} $$

where $m = |\gamma ^+| + |\gamma ^-|-1$ and $d_i = |C_i|$ for $i=1,2$ .

Let $u:= l.c.m.(d_1, d_2)/d_2$ and denote the vertices on the cycle $C_2$ and path $\gamma ^+$ by

$$ \begin{align*} V(C_2)&=f_1 f_2\ldots f_{d_2}, \\ V(\gamma^+)&=B g_1 g_2 \ldots g_{\vert \gamma^+\vert-1} f_1, \end{align*} $$

where $f_1=B'$ . We then construct a new graph H from G through the following steps:

1. (A) let H be the graph obtained from G by deleting the cycle $C_2$ ;

2. (B) if $u> 1$ , add to H a simple path $\beta $ from B to $B'$ such that

   $$ \begin{align*} \vert\beta \vert &= \vert\gamma^+ \vert + (u-1) d_2,\\ V(\beta)&=Bg_1' g_2' \ldots g_{\vert \gamma^+\vert-1}' f_1^{(1)} f_2^{(1)}\ldots f_{d_2}^{(1)} \ldots \ldots f_1^{(u-1)} f_2^{(u-1)}\ldots f_{d_2}^{(u-1)} B'; \end{align*} $$

3. (C) for each $1\leq j\leq u-2$ , add to H an edge from $f_{d_2}^{(j)}$ to $B'$ .

See Figure 7 for an example of G and H when $m=3$ , $\vert C_1 \vert =4$ , and $\vert C_2 \vert =3$ .

Figure 7 An example of G and H with $m=3$ , $\vert C_1 \vert =4, \vert C_2 \vert =3$ .

We now construct a sliding block code $\psi :X_H \rightarrow X_G$ such that $\psi $ is one-to-one and $\phi \circ \psi $ is finite-to-one and onto. It will follow that $Z:= \psi (X_H$ ) is an SFT and $\phi |_Z$ is finite-to-one and onto.

Let $\Psi : \mathcal {V}(H)\rightarrow \mathcal {V}(G)$ be the 1-block map defined by:

1. (a) for any vertex v on $\gamma ^+, \gamma ^-$ or $C_1$ , $\Psi (v)=v$ ;

2. (b) for any $1\leq i\leq \vert \gamma ^+\vert -1$ , $\Psi (g_i')=g_i$ ; for any $1\leq j\leq d_2$ and $1\leq k\leq u-1$ , $\Psi (f_{j}^{(k)})=f_j$ .

Let $\psi $ be the sliding block code induced by $\Psi $ . To show that $\psi $ is one-to-one, it suffices to show that there exists some M such that whenever $\psi (x) = y$ , then $x_0$ can be uniquely determined from $y_{[-M,M]}$ . We show this by considering the following possibilities for $y_0$ :

1. (1) if $y_0$ is on $\gamma _-$ or $C_1$ and $y_0\neq B'$ , then $x_0 = y_0$ ;

2. (2) if $y_0 = g_i$ for some i, let

   $$ \begin{align*}N_1: =\min\{l\geq 0: y_l=g_{\vert \gamma^+\vert-1}\}\leq \vert \gamma^+ \vert-2.\end{align*} $$
   Then $x_0 = g_i'$ if $y_{N_1+2}=f_2$ and $x_0=g_i$ otherwise;

3. (3) if $y_0 = f_j$ for some j, let

   $$ \begin{align*} N_2:= \min \{ \ell \ge 0: y_{-\ell} = g_{|\gamma^+|}\} \leq (u-1)d_2. \end{align*} $$
   If $y_1\neq f_l$ for any $1\leq l\leq d_2$ , then $x_0=f_1$ ; otherwise, $x_0 = f_j^{(k)}$ where $k = \lceil N_2/d_2 \rceil $ .