# Encoding subshifts through sliding block codes

Sophie MacDonald

###### Abstract

We prove a generalization of Krieger’s embedding theorem, in the spirit of
zero-error information theory. Specifically, given a mixing shift of finite
type $X$, a mixing sofic shift $Y$, and a surjective sliding block code
$\pi:X\to Y$, we give necessary and sufficient conditions for a subshift $Z$
of topological entropy strictly lower than that of $Y$ to admit an embedding
$\psi:Z\to X$ such that $\pi\circ\psi$ is injective.

##  1 Introduction

In a foundational paper [10] in information theory, Shannon introduced a model
of a noisy communication channel, in which the input and output are modeled by
stationary probability measures on a space of sequences of symbols. Shannon
gave conditions under which the input can be recovered from the output, at
least with an acceptable rate of error or ambiguity, in the case of a
Bernoulli source, and this work has since been extended to more general
sources [5].

This paper is motivated by the particular question of when one can ensure zero
error, not just almost surely as in information theory but in fact
deterministically. A deterministic channel can be modeled by a sliding block
code, i.e. a continuous, shift-commuting map on a subshift, on which a
stationary process could be supported. In this model, we can apply techniques
of symbolic dynamics to investigate the effects of deterministic noise [9],
also called distortion [10], which we can interpret as a failure of
injectivity of the sliding block code representing the channel, even in the
absence of random errors.

The main result of this paper, 1.1, determines the extent to which the non-
injectivity of a sliding block code on a mixing shift of finite type (SFT) can
be avoided by restricting to a subshift of the domain. Interpreting the
sliding block code as a channel with deterministic noise, 1.1 characterizes
the sources with entropy strictly lower than that of the output which can be
transmitted without error or ambiguity.

######  Theorem 1.1.

Let $X$ be a mixing SFT, $Y$ a mixing sofic shift, and $\pi:X\to Y$ a factor
code. Let $Z$ be a subshift with topological entropy strictly less than that
of $Y$. Then there exists a subshift $Z^{\prime}$ of $X$ conjugate to $Z$ such
that $\pi|_{Z^{\prime}}$ is injective, if and only if for every $n\geq 1$, the
number of periodic points of least period $n$ in $Z$ is at most the number of
periodic points of least period $n$ in $Y$ with a $\pi$-preimage of equal
least period.

1.1 is a generalization of the following theorem of Krieger in the case of
unequal entropy; in particular, 1.1 reduces to 1.2 in the case that $Y=X$ and
$\pi$ is the identity.

######  Theorem 1.2 (Theorem 2 in [6]).

Let $Y$ be a mixing shift of finite type and $Z$ a subshift. Then there is a
subshift $Z^{\prime}\subseteq Y$ conjugate to $Z$ if and only if $Z$ and $Y$
are conjugate or the (topological) entropy of $Z$ is less than that of $Y$
and, for every $n\geq 1$, the number of periodic points of least period $n$ in
$Z$ is at most the corresponding number in $Y$.

We note that with $X,Y,Z,\pi$ as in the statement of 1.1, clearly there exists
a subshift $Z^{\prime}$ of $X$ conjugate to $Z$ such that $\pi|_{Z^{\prime}}$
is injective if and only if there exists a sliding block code $\psi:Z\to X$
such that $\pi\circ\psi$ is injective, in which case
$Z^{\prime}=\psi(Z)\subset X$. To verify the “only if” statement in 1.1,
suppose that there is a subshift $Z^{\prime}$ of $X$ conjugate to $Z$ such
that $\pi|_{Z^{\prime}}$ is injective. Let $y\in\pi(Z^{\prime})$ be periodic.
Let $x=\pi|_{Z^{\prime}}^{-1}(y)$ be the unique preimage of $y$ in
$Z^{\prime}$. Then the orbit of $x$ is in bijection with the orbit of $y$;
otherwise, $\pi$ would fail to be injective on the orbit of $x$, which is
contained in $Z^{\prime}$. In particular, $x$ has finite orbit, so $x$ is
periodic, moreover with $\mathrm{per}(x)=\mathrm{per}(y)$. Thus, every
periodic point in $\pi(Z^{\prime})\subset Y$ has a periodic preimage in
$Z^{\prime}\subset X$ of equal least period, which shows the necessity of the
stated condition.

Both 1.1 and 1.2 give conditions for the existence of an embedding in terms of
entropy and a periodic point condition. The following corollary, which we
prove in Section 5, shows that the periodic point condition can be removed in
exchange for a small loss of injectivity.

######  Corollary 1.3.

Let $X$ be a mixing SFT, $Y$ a mixing sofic shift, and $\pi:X\to Y$ a factor
code. Let $Z$ be a subshift with topological entropy strictly less than that
of $Y$. Then there exist a subshift $Z^{\prime}$, a finite-to-one factor code
$\chi:Z^{\prime}\to Z$, and a sliding block code $\psi:Z^{\prime}\to X$ such
that $\pi\circ\chi$ is injective. Moreover, if $Z$ is mixing sofic with
positive entropy (i.e. not a single fixed point), then $Z^{\prime}$ can be
taken to be a mixing SFT and $\chi$ can be taken to be almost invertible.

The code $\chi$ is in fact injective except on points in $Z^{\prime}$ whose
images in $Z$ are backward-asymptotic to one of finitely many periodic points
in $Z$. See Lemma 2.2 and 2.3. From 1.3, we can immediately conclude the
following, with $h$ denoting the topological entropy of a subshift.

######  Corollary 1.4.

Let $X$ be a mixing SFT, $Y$ a mixing sofic shift, and $\pi:X\to Y$ a factor
code. For any $\varepsilon>0$, there exists a mixing SFT $Z\subset X$ with
$h(Z)>h(Y)-\varepsilon$ such that $\pi|_{Z}$ is injective.

The proof of 1.1 adapts the strategy used to prove 1.2 in [6, 7] and related
results in [1]. The outline of the proof is as follows. We use a marker set,
as in the proof of 1.2, to break points in $Z$ into moderate blocks and long
periodic blocks, separated by marker coordinates. We code these separately
using certain “data blocks” in $Y$, some of moderate length and some long and
periodic, where the long periodic data blocks come from periodic points with
$\pi$-preimages of equal least period in $X$. A block in $Z$ between marker
coordinates is coded to a data block in $Y$ which is shorter by an additive
constant, so that there are gaps between the data blocks, filled with
repetitions of a “blank” symbol. We then lift the data blocks from $Y$ to data
blocks from $X$, then replace the blanks with a “stamp” block from $X$ to form
a valid point in $X$. The stamp block is chosen to ensure that once the point
in $X$ is coded into $Y$ by $\pi$, the locations of the stamp, and thus of the
marker coordinates, can be recognized. These manipulations of markers, blanks,
and stamps are presented in detail in Section 3, while the quantitative
arguments required to construct the data blocks and stamps are given in
Section 4.

The statement of 1.2 is false for $X$ merely mixing sofic, and to date there
is no known characterization of the subshifts that embed into a given mixing
sofic shift, though some sufficient conditions are known [1, 11]. 1.1 sheds
some light on this problem, without resolving it. Salo-Törmä have answered [4]
the following related question: let $Y$ be a mixing sofic shift and $Z\subset
Y$ a mixing SFT. For which such $Y,Z$ do there exist a mixing SFT extension
$\pi:X\to Y$ and a (mixing SFT) $Z^{\prime}\subset X$ such that
$\pi|_{Z^{\prime}}:Z^{\prime}\to Z$ is a conjugacy? However, it is unclear how
the conditions given in that answer compare to those in 1.1, or to the results
given in [11]. As a final related question, when $Y$ is an SFT and $Z$ is
conjugate to $Y$, the existence of an SFT $Z^{\prime}\subset X$ conjugate to
$Z$ such that $\pi|_{Z^{\prime}}:Z^{\prime}\to Y$ is a conjugacy, i.e. is
surjective as well as injective, has been studied in [3], continuing work from
[9].

##  2 Conventions, definitions, and background on symbolic dynamics

###  2.1 Subshifts and sliding block codes

Let $\mathcal{A}$ be a finite set with the discrete topology, which we will
call an alphabet. The set $\mathcal{A}^{\mathbb{Z}}$ of bi-infinite sequences
over $\mathcal{A}$, equipped with the product topology, is called the full
shift over $\mathcal{A}$, so called because the shift action
$\sigma:\mathcal{A}^{\mathbb{Z}}\to\mathcal{A}^{\mathbb{Z}}$, given by
$(\sigma x)_{i}=x_{i+1}$, is a homeomorphism. A closed, shift-invariant subset
of the full shift is called a subshift. The topology on
$\mathcal{A}^{\mathbb{Z}}$ is generated by cylinders, which are sets of the
form

$[w]_{i}:=\\{x\in\mathcal{A}^{\mathbb{Z}}\,|\,x_{i+j}=w_{j},\,0\leq j\leq
n-1\\},$

where $w\in\mathcal{A}^{n}$ is a block or word of length $n\in\mathbb{N}$, and
$i\in\mathbb{Z}$. Note that by shift-invariance, for any subshift
$X\subset\mathcal{A}^{\mathbb{Z}}$ and any block $w\in\mathcal{A}^{*}$, we
have $X\cap[w]_{i}\neq\emptyset$ for some $i\in\mathbb{Z}$ if and only if
$X\cap[w]_{i}\neq\emptyset$ for all $i\in\mathbb{Z}$.

A subshift $X\subset\mathcal{A}^{\mathbb{Z}}$ is characterized by the set
$\mathcal{B}(X)$ of blocks $w\in\mathcal{A}^{*}$ such that
$X\cap[w]\neq\emptyset$, called the language of $X$. When the intended
subshift $X$ is clear, we write $[w]_{i}$ for $X\cap[w]_{i}$. We write
$\mathcal{B}_{n}(X)=\mathcal{B}(X)\cap\mathcal{A}^{n}$. We can equivalently
characterize a subshift by a set of forbidden words
$\mathcal{F}\subset\mathcal{A}^{*}$, writing
$\mathsf{X}_{\mathcal{F}}:=\overline{\mathcal{A}^{\mathbb{Z}}\setminus\bigcup_{w\in\mathcal{F}}\bigcup_{i\in\mathbb{Z}}[w]_{i}}$.
Note that in general
$\mathcal{F}\subsetneq\mathcal{A}^{*}\setminus\mathcal{B}(\mathsf{X}_{\mathcal{F}})$.
For a given subshift $X\subset\mathcal{A}^{\mathbb{Z}}$, there may be several
different sets of forbidden words $\mathcal{F}\subset\mathcal{A}^{*}$ such
that $X=\mathsf{X}_{\mathcal{F}}$. A shift of finite type (SFT) is a subshift
$X$ such that $X=\mathsf{X}_{\mathcal{F}}$ for some finite set $\mathcal{F}$.
A $k$-step SFT over $\mathcal{A}$ is an SFT of the form
$X=\mathsf{X}_{\mathcal{F}}$ for some set
$\mathcal{F}\subset\mathcal{A}^{k+1}$.

It is a theorem (the Curtis-Hedlund-Lyndon theorem) that, for subshifts $X,Y$,
a function $\phi:X\to Y$ is continuous and shift-equivariant if and only if it
is a sliding block code, which means that there exist $m,n\geq 0$ and
$\Phi:\mathcal{B}_{m+n+1}(X)\to\mathcal{B}_{1}(Y)$ such that for every $x\in
X$ and every $i\in\mathbb{Z}$, $\phi(x)_{i}=\Phi(x_{[i-m,i+n]})$. We say that
$\phi$ is a $k$-block code if $m+n+1=k$. A factor code is a surjective sliding
block code, and for a sliding block code $\phi$ defined on a subshift $X$, we
say that the image $\phi(X)$ is a factor of $X$, and that $X$, or more
properly $\phi:X\to\phi(X)$, is an extension of $\phi(X)$. A sofic shift (from
the Hebrew swpy¿, “sofi”, meaning “finite”) is any factor of a shift of finite
type. An injective sliding block code is called an embedding, and a bijective
sliding block code is called a conjugacy. The properties of being sofic and of
finite type are both invariant under conjugacy.

A subshift $X$ is said to be irreducible if for all $u,w\in\mathcal{B}(X)$,
there exists $v\in\mathcal{B}(X)$ such that $uvw\in\mathcal{B}(X)$, and
strongly irreducible with gap $g\geq 1$ if, for any $u,w$, we can take always
take $v\in\mathcal{B}_{g}(X)$. Any factor of an irreducible (resp. strongly
irreducible) subshift is irreducible (resp. strongly irreducible). A periodic
point in a subshift $X$ is a point $x\in X$ with $x=\sigma^{n}x$ for some
$n\geq 1$—we say that $x$ has period $n$. The least period $\mathrm{per}(x)$
of a periodic point $x$ is the least $n$ such that $\sigma^{n}x=x$. Note that
$|\\{\sigma^{n}x\,|\,n\in\mathbb{Z}\\}|=\mathrm{per}(x)$. We write $P(X)$ for
the set of periodic points in a subshift $X$, $Q_{n}(X)$ for the set of
periodic points of least period $n$, and $q_{n}(X)=|Q_{n}(X)|$. The number of
periodic points of a given least period is a conjugacy invariant.

It is a theorem that periodic points are dense in any irreducible shift of
finite type. The period $\mathrm{per}(X)$ of an irreducible shift of finite
type $X$ is the gcd of the periods of the periodic points of $X$. An
irreducible SFT with period $1$ is said to be aperiodic. An irreducible SFT is
strongly irreducible if and only if it is aperiodic, if and only if has
periodic points of all sufficiently high periods. For irreducible sofic
shifts, strong irreducibility is equivalent to having periodic points of all
sufficiently high periods, which clearly implies that the periods have gcd
$1$, but the reverse implication fails. For example, consider the odd shift
over $\\{0,1\\}$, in which the block $10^{n}1$ is permitted only for odd $n$.
This is an irreducible sofic shift which contains the fixed point
$0^{\infty}$, so the periods of periodic points trivially have gcd $1$.
However, the odd shift has no other periodic points of odd period. We follow
the convention of the literature in referring to strongly irreducible sofic
shifts (in particular SFTs) as mixing sofic shifts (mixing SFTs), because they
are also characterized by a topological mixing property, but we will not use
that property explicitly, so we do not define it here.

The following definition is new, and we use it extensively.

######  Definition 2.1.

Let $X$ and $Y$ be subshifts and let $\pi:X\to Y$ be a factor code. We write
$R_{n}(\pi)$ for the set of periodic points $y\in Y$ such that $y=\pi(x)$ for
some periodic point $x\in X$ with $\mathrm{per}(x)=\mathrm{per}(y)$. We write
$r_{n}(\pi)=|R_{n}(\pi)|$.

For a subshift $X$, the (topological) entropy of $X$ is the value
$h(X)=\inf_{n\geq 1}\frac{1}{n}\log|\mathcal{B}_{n}(X)|$; in fact, the limit
$\lim_{n\to\infty}\frac{1}{n}\log|\mathcal{B}_{n}(X)|$ exists and is equal to
$h(X)$. For a mixing sofic shift (in particular, a mixing SFT) $X$, we also
have $h(X)=\lim_{n\to\infty}\frac{1}{n}\log q_{n}(X)$. Entropy is non-
increasing under factor codes and is thus a conjugacy invariant, though
certainly not a complete invariant. For any irreducible sofic shift $X$, and
any proper subshift $V\subset X$, we have $h(V)<h(X)$. In Section 4, we use
the following lemma of Marcus, which allows us to approximate a sofic shift
from the inside by SFTs in terms of entropy.

######  Lemma 2.1 (Proposition 3 in [8]).

Let $Y$ be a sofic shift. For every $\varepsilon>0$, there exists an
irreducible SFT $U\subseteq Y$ with $h(U)>h(Y)-\varepsilon$.

For any subshift $X$ and any $k\geq 1$, we can form the $k$th higher block
shift $X^{[k]}$ with alphabet $\mathcal{B}_{k}(X)$, where

$w=(a_{1,1}a_{1,2}\dots a_{1,k})(a_{2,1}a_{2,2}\dots
a_{2,k})\dots(a_{\ell,1}a_{\ell,2}\dots a_{\ell,k})\in\mathcal{B}(X^{[k]})$

if any only if for each $i,j$ we have $a_{i,j}=a_{i+1,j-1}$, so that

$w=(a_{1}a_{2}\dots a_{k})(a_{2}a_{3}\dots
a_{k+1})\dots(a_{\ell+1}a_{\ell+2}\dots a_{\ell+k}),$

and $a_{1}a_{2}\dots a_{k+\ell}\in\mathcal{B}(X)$. Observe that $X$ and
$X^{[k]}$ are conjugate for any subshift $X$ and any $k\geq 1$. Moreover, if
$X$ is an $m$-step SFT and $k\leq m-1$, then $X^{[k]}$ is an $(m-k)$-step SFT.
In particular, every SFT is conjugate to a $1$-step SFT, and every sliding
block code on an SFT can be written as a composition of a conjugacy and a
$1$-block code. We will therefore frequently assume WLOG that a given sliding
block code on an SFT is a $1$-block code on a $1$-step SFT.

For a sliding block code on an irreducible shift of finite type, either every
fiber is a finite set (indeed, of bounded cardinality), in which case the code
is said to be finite-to-one and the entropy of the image is equal to that of
the domain, or almost every fiber is uncountable, and the entropy of the image
is strictly less than that of the domain. In the finite-to-one case, the
minimum fiber cardinality is generic and is known as the degree. In
particular, a code (on an irreducible SFT) with degree $1$ is said to be
almost invertible. It is a theorem that every irreducible (resp. mixing) sofic
shift is an almost invertible factor of an irreducible (resp. mixing) SFT. We
use the following construction of almost invertible codes, known as the
“blowing-up lemma”, in the proof of 1.3 in Section 5.

######  Lemma 2.2 (Lemma 10.3.2, [7]).

Let $Z$ be a mixing SFT and let $z\in Z$ be a periodic point with least period
$p$. Let $M\geq 1$. Then there exist a mixing SFT $Z^{\prime}$ and an almost
invertible factor code $\chi:Z^{\prime}\to Z$ such that the preimage of the
orbit of $z$ under $\chi$ is a single orbit of length $Mp$.

######  Remark 2.3.

Note that in [7], the extension $\chi$ in Lemma 2.2 is only stated to be
finite-to-one, but the existence of periodic points having unique preimage
already implies almost invertibility. Indeed, the construction in [7], based
on work in [1], in fact shows that $\chi$ is injective except on the points
that are backward-asymptotic to points in the preimage of the orbit of $z$,
where we say that two points $z,z^{\prime}$ are backward-asymptotic if
$d(\sigma^{n}z,\sigma^{n}z^{\prime})\to 0$ as $n\to-\infty$.

###  2.2 Markers and Markov approximations

We now recall the constructions with markers and long periodic blocks that are
at the heart of the proof of 1.1. For an alphabet $\mathcal{A}$, we say that a
block $w=w_{1}\dots w_{n}\in\mathcal{A}^{n}$ is $k$-periodic, or has self-
overlap of $n-k$, if $w_{[k+1,n]}=w_{[1,n-k]}$, i.e. for $1\leq i\leq n-k$ we
have $w_{i}=w_{i+k}$. A given block may be $k$-periodic for several different
$k$.

######  Lemma 2.4 (Lemma 2.3 in [1]).

Let $Z$ be a subshift, let $N\geq 1$, and $a,b\in\mathbb{Z}$ with $b-a\geq
2N$. Let $z\in Z$. If for every $i\in[a+N,b-N]$ there exists $p\leq N-1$ such
that $z_{[i-N,i+N]}$ is $p$-periodic, then there is at most one periodic point
$\zeta\in Z$ with $\mathrm{per}(\zeta)\leq N-1$ and $\zeta_{[a,b]}=z_{[a,b]}$.
If $Z$ is a $1$-step SFT, then such a $\zeta$ exists.

######  Lemma 2.5 (Lemma 2 in [6]).

Let $Z$ be a subshift. For any $N\geq 1$, there exists a subset $F\subset Z$,
which can be taken to be a finite union of cylinders, such that:

  1. 1.

the sets $\sigma^{i}F$, $0\leq i\leq N-1$, are all disjoint, and

  2. 2.

if $z\notin\sigma^{i}F$ for all $-(N-1)\leq i\leq(N-1)$, then $z_{[-N,N]}$ is
$p$-periodic for some $p\leq N-1$.

For any subshift $X$ and any $n\geq 1$, we can form the $n$th Markov
approximation $X_{n}$, which is the SFT defined by allowing precisely the
blocks of length $n$ which appear in $X$. Clearly $X_{n+1}\subset X_{n}$. It
is an exercise to show that for any $\varepsilon>0$ and any $N\geq 1$, there
exists $N^{\prime}\geq N$ such that $h(X_{N^{\prime}})<h(X)+\varepsilon$ and
$q_{n}(X_{N^{\prime}})=q_{n}(X)$ for all $n\leq N$. In Lemma 2.6, we use the
Markov approximation, together with higher block shifts, to show that in the
proof of 1.1, we can assume WLOG that $Z$ is a $1$-step SFT, which allows us
to apply Lemma 2.4.

We remark that there are versions of Lemma 2.5 which obviate the need for
Lemma 2.4. However, for our purposes in this paper, embedding $Z$ into an SFT
has the additional benefit that the rate of convergence of $\frac{1}{n}\log
q_{n}(Z)$ to $h(Z)$ can be easily estimated when $Z$ is an SFT (see e.g. [7],
pp. 349-351), which gives a procedure for deciding whether a given $X,Y,\pi,Z$
satisfy the periodic point condition in 1.1, assuming that $h(Z)<h(Y)$
(namely, compute $N\geq 1$ such that for all $n\geq N$, $q_{n}(Z)<r_{n}(\pi)$,
then check all $n\leq N$ to determine whether $q_{n}(Z)\leq r_{n}(\pi)$).

######  Lemma 2.6.

Let $X$ be a mixing SFT, $Y$ a mixing sofic shift, and $\pi:X\to Y$ a factor
code. Let $Z$ be a subshift with $h(Z)<h(Y)$ and $q_{n}(Z)\leq r_{n}(\pi)$ for
all $n\geq 1$. Then there exists a $1$-step SFT $Z^{\prime}$ such that $Z$
embeds into $Z^{\prime}$, $h(Z^{\prime})<h(Y)$, and $q_{n}(Z^{\prime})\leq
r_{n}(\pi)$ for all $n\geq 1$.

We defer the proof of Lemma 2.6 to Section 5.

##  3 Coding

In Section 3.1, we introduce two coding constructions, namely subshifts with
blanks adjoined, 3.1, and stamps, 3.2, then use them to create one side of an
interface between $Z$ on the one hand and $\pi:X\to Y$ on the other. In
Section 3.2, we use markers in $Z$ to construct the other side of this
interface. In Section 3.3, we use stamps to give a construction of SFTs
analogous to $S$-gap shifts. We use this construction in Section 4.2 to
construct the shifts that are used in Section 3.1 and Section 3.2.

###  3.1 Blanks and stamps

As outlined in Section 1, the proof of 1.1 involves coding $Z$ into $X$ via
certain intermediate subshifts which consist of long “data” blocks separated
by blanks. We now define this construction precisely.

######  Definition 3.1 (subshift with blanks adjoined).

Let $W$ be a subshift and let $N,\ell\geq 1$ with $\ell<N$. Let $*$ be a
symbol not appearing in the alphabet of $W$. Let
$M\subset\bigcup_{n=1}^{2N}\mathcal{B}(W)$ be a set of blocks and let
$Q\subset\cup_{n=1}^{2N-1}Q_{n}(W)$ be a set of periodic points. Denote by
$\mathrm{Blanks}(M,Q,N,*,\ell)$ the subshift in which each point is of the
form $\dots w_{-1}*^{\ell}w_{0}*^{\ell}w_{1}\dots$ where either $w_{i}\in M$
or $w_{i}=y_{T}$ where $y\in Q$ and
$T=(-\infty,0],[0,+\infty),(-\infty,\infty)$, or $[0,m]$ with $m\geq 2N$.

The purpose of the $\mathrm{Blanks}$ construction is to provide an interface
between the channel $\pi:X\to Y$ and the subshift $Z$ to be embedded. One side
of this interface, namely the embedding of a $\mathrm{Blanks}$ subshift into
$X$, is specified in 3.4. The construction involves particular blocks, which
we call stamps, that can be unambiguously recognized in the following sense:

######  Definition 3.2 (stamp).

Let $Y$ be a subshift, $W\subset Y$ a proper subshift, and $k\geq 1$. We say
that $\mu\in\mathcal{B}(Y)\setminus\mathcal{B}(W)$ is a $(Y,W,k)$ stamp if for
all $u_{1},u_{2}\in\mathcal{B}(W)$ and $v_{1},v_{2}\in\mathcal{B}_{k}(Y)$,
$\mu$ appears exactly once in $u_{1}v_{1}\mu v_{2}u_{2}$.

######  Remark 3.1.

In 3.2, continuing with the notation there, we do not explicitly require
$u_{1}v_{1}\mu v_{2}u_{2}$ to be legal in $X$. Doing so would neither affect
the results nor simplify the proofs. In all of the examples we consider, such
blocks will in fact be legal in $X$.

######  Proposition 3.2.

Let $Y$ be a strongly irreducible subshift with gap $g$ and $W\subset Y$ a
proper subshift. For every $k\geq g$ and every sufficiently large $n$, there
exists a $(Y,W,k)$ stamp of length $n$.

We defer the proof of 3.2 to Section 4.1, but before applying stamps in 3.4,
we prove a lemma that expresses how stamps are actually used in our
constructions.

######  Lemma 3.3.

Let $Y$ be a subshift, $W\subset Y$ a proper subshift, $k\geq 1$, and
$\mu\in\mathcal{B}(Y)\setminus\mathcal{B}(W)$ a $(Y,W,k)$ stamp. Let
$N\geq|\mu|$. Then for any $\gamma^{\pm}\in\mathcal{B}_{k}(Y)$, and any
$w\in\mathcal{B}(W)$ with $|w|\geq N$, the stamp $\mu$ appears exactly twice
in the block $\mu\gamma^{-}w\gamma^{+}\mu$.

###### Proof.

By the hypotheses on $\mu$, $\gamma^{\pm}$, and $w$, and 3.2, $\mu$ appears
exactly once in each subblock $\mu\gamma^{-}w$, $w\gamma^{+}\mu$. An
appearance of $\mu$ other than at the positions explicitly indicated must
therefore overlap both of these subblocks. Since $|w|\geq|\mu|$, $\mu$ must
therefore be a subblock of $w$, contradicting the hypothesis that
$w\in\mathcal{B}(W)$ and $\mu\in\mathcal{B}(Y)\setminus\mathcal{B}(W)$. ∎

We now give one of the main coding constructions (3.4), embedding a subshift
with blanks adjoined, and with blocks from a subshift $V\subset X$, into $X$
via a sliding block code $\gamma$, such that $\pi\circ\gamma$ is injective.
The large amount of data in the statement is representative of the complexity
of the construction and the modular nature of the proof.

######  Proposition 3.4.

Let $X$ be a mixing SFT with gap $g$, let $Y$ be a mixing sofic shift, and let
$\pi:X\to Y$ be a $1$-block factor code.

Let $V\subset X$, $W=\pi(V)\subset Y$ be proper subshifts. Let $*$ be a symbol
not appearing in the alphabets of $X,Y$. Let $N\geq 1$. Let
$M\subset\bigcup_{n=1}^{2N-1}\mathcal{B}_{n}(W)$ be a collection of blocks,
and let $R\subset\bigcup_{n=1}^{N-1}R_{n}(\pi|_{V})$ be a union of finite
(i.e. periodic) orbits in $W$ with $\pi$-preimages of equal cardinality in
$V$. Let $\kappa:M\to\mathcal{B}(V)$ be an injection such that
$\pi\circ\kappa(w)=w$ for each $w\in M$, and let $\hat{M}=\kappa(M)$.
Similarly, let $\lambda:R\to P(V)$ be a shift-commuting injection such that
$\pi\circ\lambda(y)=y$ for each $y\in R$, and let $\hat{R}=\lambda(R)$. Then
for any $\ell\geq 1$, $\mathrm{Blanks}(M,R,N,*,\ell)$ and
$\mathrm{Blanks}(\hat{M},\hat{R},N,*,\ell)$ are conjugate.

Moreover, let $\mu\in\mathcal{B}(Y)\setminus\mathcal{B}(W)$ be a $(Y,W,g)$
stamp such that $|\mu|\leq N$, and suppose that
$M\subset\bigcup_{n=N}^{2N-1}\mathcal{B}_{n}(W)$, i.e. $M$ contains no blocks
of length less than $N$. Then there exists a sliding block code
$\gamma:\mathrm{Blanks}(\hat{M},\hat{R},N,*,|\mu|+2g)\to X$ such that
$\pi\circ\gamma$ is injective.

###### Proof.

First, the conjugacy. Let $W[*]=\mathrm{Blanks}(M,R,N,*,\ell)$ and
$V[*]=\mathrm{Blanks}(\hat{M},\hat{R},N,*,\ell)$. Consider the $1$-block code
$\pi[*]$ defined on $V[*]$ by the block map $\pi[*](a)=\pi(a)$ for $a$ in the
alphabet of $V$ and $\pi[*](*)=*$. We claim that $W[*]=\pi[*](V[*])$ and that
$\pi[*]:V[*]\to W[*]$ is a conjugacy. To see that $W[*]\subseteq\pi[*](V[*])$,
note that any $\xi\in V[*]$ is of the form

$\xi=\dots w_{-1}*^{\ell}w_{0}*^{\ell}w_{1}\dots$

where either $w_{i}\in\hat{M}$ or $w_{i}=x_{T}$ for some $x\in\hat{R}$ and $T$
an interval with $2N+1\leq|T|$. If $w_{i}\in\hat{M}$, then $\pi(w_{i})\in M$;
if $w_{i}=x_{T}$ for some $x\in\hat{R}$, then $\pi(w_{i})=\pi(x)_{T}$, and
$\pi(x)\in R$. Therefore

$\pi[*](\xi)=\dots\pi(w_{-1})*^{\ell}\pi(w_{0})*^{\ell}\pi(w_{1})\dots\in
W[*]$

This shows that indeed $W[*]\subset\pi[*](V[*])$. Similarly, any $\eta\in
W[*]$ is of the form

$\eta=\dots w_{-1}*^{\ell}w_{0}*^{\ell}w_{1}\dots$

where either $w_{i}\in M$ or $w_{i}=y_{T}$ for some $y\in R$ and $T$ an
interval with $2N+1\leq|T|\leq\infty$. For $\eta$ of this form, using Lemma
2.4, we can use the injections $\kappa$, $\lambda$ to reconstruct a unique
$\xi\in V[*]$ such that $\pi[*](\xi)=\eta$.

We now suppose that each block in $M$ has length at least $N$ and that we have
a $(Y,W,g)$ stamp $\mu\in\mathcal{B}(Y)\setminus\mathcal{B}(W)$ such that
$|\mu|\leq N$. Under these assumptions, we construct a sliding block code
$\gamma:V[*]\to X$ and show that $\pi\circ\gamma$ is injective. Fix a
$\pi$-preimage $\hat{\mu}$ of $\mu$, and let $\ell=|\mu|+2g$. Using the
hypothesis that $X$ is a mixing $1$-step SFT, define maps
$\gamma^{\pm}:\mathcal{B}_{1}(V)\to\mathcal{B}_{g}(X)$ such that, for
$a,b\in\mathcal{B}_{1}(V)$, we have
$\hat{\mu}\gamma^{-}(a)a,b\gamma^{+}(b)\hat{\mu}\in\mathcal{B}(X)$. We then
have a sliding block code $\gamma:V[*]\to X$, given by replacing each block
$b*^{\ell}a$ by $b\gamma^{+}(b)\hat{\mu}\gamma^{-}(a)a$, and leaving the non-
blank symbols unchanged.

Let

$\xi=\dots*^{\ell}v_{-1}*^{\ell}v_{0}*^{\ell}v_{1}*^{\ell}\dots\in V[*]$

Then

$\gamma(\xi)=\dots\hat{\mu}\gamma^{-}(a_{0})v_{0}\gamma^{+}(b_{0})\hat{\mu}\dots$

where $a_{i},b_{i}$ are, respectively, the initial and terminal symbols of
$v_{i}$. In turn, we have

$\pi\circ\gamma(\xi)=\dots\mu(\pi\circ\gamma^{-}(a_{0}))\pi(v_{0})(\pi\circ\gamma^{+}(b_{0}))\mu\dots$

Moreover, by Lemma 3.3 and the lower bound on lengths of blocks in $M$, it
follows that $\mu$ appears in $\pi\circ\gamma(\xi)$ only where $\hat{\mu}$
appears at the same position in $\gamma(\xi)$. By replacing, in
$\pi\circ\gamma(\xi)$, each appearance of $\mu$, and the blocks of length $k$
to the left and right of $\mu$, with $*^{\ell}$, we obtain the point
$\dots*^{\ell}\pi(v_{0})*^{\ell}\dots=\pi[*](\xi)\in\mathrm{Blanks}(M,R,N,*,\ell)$,
from which $\xi$ can be recovered since $\pi[*]$ is a conjugacy. ∎

###  3.2 Blanks and markers

We now prove a lemma that encapsulates the use of marker constructions in our
proof of 1.1.

######  Lemma 3.5.

Let $Z,W$ be subshifts with $Z$ a $1$-step SFT. Let $N,\ell\geq 1$ be such
that $q_{n}(Z)\leq q_{n}(W)$ for $n\leq N-1$ and
$|\mathcal{B}_{n}(Z)|\leq|\mathcal{B}_{n-\ell}(W)|$ for $N+\ell\leq n\leq
2N+\ell-1$. Let $M\subset\bigcup_{n=N}^{2N-1}\mathcal{B}_{n}(W)$ and
$Q\subset\bigcup_{n=1}^{N-1}Q_{n}(W)$ be a union of finite (i.e. periodic)
orbits such that $|\mathcal{B}_{n}(Z)|\leq|M\cap\mathcal{B}_{n-\ell}(W)|$ for
$N+\ell\leq n\leq 2N+\ell-1$, and $q_{n}(Z)\leq|Q\cap Q_{n}(W)|$ for $n\leq
N-1$. Then $Z$ embeds into $\mathrm{Blanks}(M,Q,N,*,\ell)$.

######  Remark 3.6.

The lower bound on the length of blocks in $M$ is not in fact needed for Lemma
3.5, but it is needed in order to apply Lemma 3.5 in conjunction with 3.4 in
the proof of 1.1 below.

###### Proof.

Let $F$ be a marker set for $Z$ with parameter $N$. For $z\in Z$, let
$A(z)=\\{i\in\mathbb{Z}\,|\,\sigma^{i}z\in F\\}$. Enumerate each $A(z)$ as
$\\{a_{j}(z)\\}_{j\in J(z)}$ where the index set $J(z)$ may be the empty set,
or a finite set, or the integers, or the positive or negative natural numbers,
and where $a_{j}(z)<a_{j+1}(z)$ for each $j$. We refer to the elements of
$A(z)$ as marker coordinates for $z$. Say that $T$ is a marker interval for
$z$ if: $T=[a_{j}(z),a_{j+1}(z))$ where $a_{j}(z),a_{j+1}(z)$ are both
defined; or $T=[a_{0}(z),\infty)$ if $a_{0}(z)=\max A(z)<\infty$; or
$T=(-\infty,a_{0}(z)]$ if $a_{0}(z)=\min A(z)>-\infty$; or
$T=(-\infty,\infty)$ if $A(z)=\emptyset$.

We construct an embedding of $Z$ into $\mathrm{Blanks}(M,Q,N,*,\ell)$ by
constructing a function $\Phi$ that maps a block occurring between marker
coordinates to a data block padded with $*^{\ell}$. Let $c_{n}:Q_{n}(Z)\to
Q_{n}(W)$ be shift-commuting injections for $n\leq N-1$. Let
$d_{n}:\mathcal{B}_{n}(Z)\to\mathcal{B}_{n-\ell}(W)$ be injections for
$N+\ell\leq n\leq 2N+\ell-1$. For a block $w\in\mathcal{B}_{n}(Z)$ with
$N+\ell\leq n\leq 2N+\ell-1$, let $\Phi(w)=*^{\ell}d_{n}(w)$. For $z\in Z$
periodic with $n=\mathrm{per}(z)\leq N-1$, if $m\geq 2N+\ell$, let
$\Phi(z_{[0,m]})=*^{\ell}c_{n}(z)_{[\ell,m]}$. Similarly, let
$\Phi(z_{[0,\infty)})=*^{\ell}c_{n}(z)_{[\ell,\infty)}$. Finally, let
$\Phi(z_{(-\infty,0]})=c_{n}(z)_{(-\infty,0]}$ and let $\Phi(z)=c_{n}(z)$.
Observe that $\Phi$ is injective, by Lemma 2.4.

Define $\phi:Z\to W$ by declaring that $\phi(z)_{T}=\Phi(z_{T})$ whenever $T$
is a marker interval for $z$. We need to show that $\phi$ is an embedding.
Certainly $\phi$ is shift-commuting, since, if $T$ is a marker interval for
$z$, then $T-1$ is a marker interval for $\sigma z$, so

$\phi(\sigma z)_{T-1}=\Phi((\sigma
z)_{T-1})=\Phi(z_{T})=\phi(z)_{T}=(\sigma\phi(z))_{T-1}$

Thus indeed $\phi(\sigma z)=\sigma\phi(z)$. Moreover, $\phi$ is injective
because the appearances of $\beta$ in $\phi(z)$ allow us to reconstruct the
marker coordinates, and then the injectivity of $\Phi$ allows us to
reconstruct $z_{T}$ for each marker interval $T$ for $z$.

We need to show finally that $\phi$ is continuous, i.e. that for $z\in Z$,
$\phi(z)_{0}$ depends only on $z_{[-L,L]}$ for some finite $L$ independent of
$z$. To see this, let $L^{\prime}$ be such that $F$ is a union of cylinders on
$[-L^{\prime},L^{\prime}]$. Let $L=L^{\prime}+2N$. By examining $z_{[-L,L]}$,
we can determine whether there are marker coordinates for $z$ in $[-2N,0)$
and/or $[0,2N]$. If each of these intervals contains a marker coordinate, then
$\phi(z)_{0}$ is determined by $z_{T}$ where $T\subset[-2N,2N]$ is the unique
marker interval for $z$ containing $0$. If at least one of $[-2N,0),[0,2N]$
has no marker coordinates, then $0$ is in a long marker interval for $z$. If
there is a marker coordinate in $(-\ell,0]$, then $\phi(z)_{0}=*$. Otherwise,
by Lemma 2.4, $\phi(z)_{0}$ is determined by any subblock $z_{[a,b]}$ where
$a<0\leq b$, $b-a\geq 2N$, and $[a,b]$ contains no marker coordinate for $z$.
This concludes the proof that $\phi$ is continuous. ∎

The remainder of the proof of 1.1 follows the following proposition, the proof
of which is taken up in Section 4.

######  Proposition 3.7.

Let $X$ be a mixing SFT with gap $g$, $Y$ a mixing sofic shift, and $\pi:X\to
Y$ a factor code. Let $Z$ be a subshift with $h(Z)<h(Y)$ and $q_{n}(Z)\leq
r_{n}(\pi)$ for every $n\geq 1$. Then there exist: $N\geq 1$, subshifts
$V\subset X$, $W=\pi(V)\subset Y$, and a $(Y,W,g)$ stamp
$\mu\in\mathcal{B}(Y)\setminus\mathcal{B}(W)$, such that $|\mu|\leq N$,
$q_{n}(Z)\leq r_{n}(\pi|_{V})$ for $n\leq N-1$ and
$|\mathcal{B}_{n}(Z)|\leq|\mathcal{B}_{n-\ell}(W)|$ for $N+\ell\leq n\leq
2N+\ell-1$, where $\ell=|\mu|+2g$.

###### Proof of 1.1.

By Lemma 2.6, assume WLOG that $Z$ is a $1$-step SFT. Let $N$, $\ell$,
$V\subset X$, $W=\pi(V)\subset Y$, and $\mu$ be as in 3.7. Let
$M\subset\bigcup_{n=N}^{2N-1}\mathcal{B}_{n}(W)$ be as in Lemma 3.5, and let
$R\subset\bigcup_{n=1}^{N-1}R_{n}(\pi|_{V})$ be a union of finite orbits, such
that $q_{n}(Z)\leq|R\cap R_{n}(\pi|_{V})|$ for $n\leq N-1$. Each of which the
orbits in $R$ is, by the definition of $R_{n}$, necessarily the image of an
orbit with equal cardinality in $V$. Here, $R$ takes the role that $Q$ plays
in Lemma 3.5, but in Lemma 3.5, there was no channel $\pi$, and thus no
preimage requirement, hence the change in notation. By Lemma 3.5, let
$\phi:Z\to\mathrm{Blanks}(M,R,N,*,\ell)$ be an embedding.

Let $\hat{M}$, $\hat{R}$ be as in 3.4, let
$\pi[*]:\mathrm{Blanks}(\hat{M},\hat{R},N,*,\ell)\to\mathrm{Blanks}(M,R,N,*,\ell)$
be a conjugacy, and let $\gamma:\mathrm{Blanks}(\hat{M},\hat{R},N,*,\ell)\to
X$ be an embedding such that $\pi\circ\gamma$ is injective (by 3.4, using
$\mu$). Then $\psi=\gamma\circ(\pi[*])^{-1}\circ\phi:Z\to X$ is a sliding
block code such that $\pi\circ\psi$ is injective. ∎

###  3.3 Stamps and SFTs

In this subsection, we prove Lemma 3.9, which, in conjunction with Lemma 2.1,
allows us, in 4.4, to construct a mixing SFT $V\subset X$ such that the image
$\pi(V)\subset Y$ is a proper subshift of $Y$ but has entropy at least
$h(Y)-\varepsilon$ for a given $\varepsilon>0$. It may be possible to give a
more efficient construction of such a $V$, but we have not found one. We first
prove Lemma 3.8, which is related to the characterization of SFTs among
$S$-gap shifts (Theorem 3.3 in [2]).

######  Lemma 3.8.

Let $X$ be a mixing SFT with gap $g$ and let $V_{0}\subset X$ be an SFT. Let
$k\geq g$ and let $\mu\in\mathcal{B}(X)\setminus\mathcal{B}(V_{0})$ be an
$(X,V_{0},k)$ stamp. Let $N\geq|\mu|$ and let $V_{1}\subset X$ be the closure
of the set of points of the form

$\dots
v_{-1}\gamma^{+}_{-1}\mu\gamma^{-}_{0}v_{0}\gamma^{+}_{0}\mu\gamma^{-}_{1}v_{1}\dots\in
X$

where, for each $i$, $\gamma^{\pm}_{i}\in\mathcal{B}_{k}(X)$ and
$v_{i}\in\mathcal{B}(V_{0})$ with $|v_{i}|\geq N$. Then $V_{1}$ is a mixing
SFT.

###### Proof.

Assume without loss of generality that $X$ is a $1$-step SFT. We first perform
a small recoding for convenience, specifically to make it easier to recognize
stamps, by replacing $X$ by a conjugate shift $\hat{X}$. For each $x\in X$,
define $\hat{x}$ as follows: if $x_{[i,i+|\mu|)}=\mu$, then for each
$i\in[-k,|\mu|+k)$, let $a=x_{i}$ and let $\hat{x}_{i}=\hat{a}$, where for
symbols $a,b$ in the alphabet of $X$, we have $\hat{a}=\hat{b}$ if and only if
$a=b$, and the set of symbols with hats is disjoint from the alphabet of $X$.
If there is no $j\in(i-(|\mu|+k),i+k]$ with $x_{[j,j+|\mu|)}=\mu$, then let
$\hat{x}_{i}=x_{i}$. Clearly the map $x\mapsto\hat{x}$ is a sliding block
code, and it is just as clearly injective, since we recover $x$ from $\hat{x}$
by dropping hats. Therefore $\hat{X}=\\{\hat{x}\,|\,x\in X\\}$ is a mixing
SFT, conjugate to $X$.

Denote by $\hat{V}_{1}\subset\hat{X}$ the image of $V_{1}$ under the map
$x\mapsto\hat{x}$. Let $\ell=|\mu|+2k$. Since $\mu$ is an $(X,V_{0},k)$ stamp,
and $N\geq|\mu|$, blocks of the form $\gamma^{+}_{i}\mu\gamma^{-}_{i+1}$ do
not overlap in any point in $V$ by Lemma 3.3, so symbols with hats occur in
$\hat{V}_{1}$ in blocks of length exactly $\ell$. The blocks of symbols with
hats are separated by blocks from $V_{0}$. Since $\hat{V}_{1}$ is the image of
$V$ under a conjugacy $X\to\hat{X}$, $V_{1}$ is an SFT if and only if
$\hat{V}_{1}$ is an SFT.

Let $m\geq N$ be such that $\hat{X}$ and $V_{0}$ are $m$-step SFTs. We claim
that if $\hat{x}\in\hat{X}$ is such that
$x_{[i,i+m]}\in\mathcal{B}_{m+1}(\hat{V}_{1})$ for all $i\in\mathbb{Z}$, then
$\hat{x}\in\hat{V}_{1}$, which means precisely that $V$ is an $m$-step SFT. To
prove this claim, let $\mathcal{F}\subset\mathcal{B}_{m+1}(X)$ be the set of
blocks of length $m+1$ which contain at least one of the following: a block of
length greater than $\ell$ in which all symbols have hats; a block without
hats that is not in $\mathcal{B}(V_{0})$; or a block of symbols without hats,
of length less than $N$, bounded on both sides by symbols with hats. Note that
$\mathcal{F}$ is disjoint from $\mathcal{B}_{m+1}(\hat{V}_{1})$. Suppose that
$\hat{x}_{[i,i+m]}\notin\mathcal{F}$ for all $i\in\mathbb{Z}$. Then any block
of symbols with hats in $\hat{x}$ has length exactly $\ell$, and is thus of
the form $\gamma^{+}\mu\gamma^{-}$, where $\gamma^{\pm}\in\mathcal{B}_{g}(X)$
(with hats added). Furthermore, the blocks separating the blocks with hats
must have length at least $N$ and must be in $\mathcal{B}(V_{0})$, since every
subblock of length $m+1$ is in $\mathcal{B}(V_{0})$ and $V_{0}$ is an $m$-step
SFT. Thus indeed $\hat{x}\in\hat{V}_{1}$, so $\hat{V}_{1}$ is indeed an SFT.

To see that $V_{1}$ is irreducible, let $u_{-},u_{+}\in\mathcal{B}(V_{1})$. We
need to construct $u_{0}\in\mathcal{B}(V)$ such that
$u_{-}u_{0}u_{+}\in\mathcal{B}(V_{1})$. We do so as follows. Extend $u_{-}$ on
the right to form a block $v_{-}\in\mathcal{B}(V_{1})$, which begins with
$u_{-}$ and ends with $\gamma^{+}_{-1}\mu\gamma^{-}_{0}$ where
$\gamma^{+}_{-1},\gamma^{-}_{0}\in\mathcal{B}_{k}(V_{1})$. (It is possible
that $u_{-}$ overlaps $\gamma^{+}_{-1}\mu\gamma^{-}_{0}$.) Let
$v_{0}\in\mathcal{B}_{N}(V_{0})$ be such that $v_{-}v_{0}\in\mathcal{B}(X)$.
Similarly, extend $u_{+}$ on the left to form a block
$v_{+}\in\mathcal{B}(V_{1})$ which ends with $u_{+}$ and begins with
$\gamma^{+}_{0}\mu\gamma^{-}_{1}$, where
$\gamma^{+}_{0},\gamma^{-}_{1}\in\mathcal{B}_{k}(V_{1})$ and
$v_{0}\gamma^{+}_{0}\in\mathcal{B}(X)$. Let $x^{\pm}\in\mathcal{B}(V_{1})$ be
such that $x^{-}_{[0,\infty)}$ begins with $v_{-}$ and $x^{+}_{(-\infty,-1]}$
ends with $v^{+}$. Let
$x=x^{-}_{(-\infty,-1]}v_{-}v_{0}v_{+}x^{+}_{[0,\infty)}$. Then $x\in X$ since
$X$ is a $1$-step SFT. Moreover, $x\in V_{1}$, since the tails
$x^{-}_{(-\infty,-1]}v_{-}$ and $v_{+}x^{+}_{[0,\infty)}$ appear in $V_{1}$
and are joined together in a way that creates no violations of the
restrictions defining $V_{1}$. Letting $u_{0}$ be the block appearing between
$u_{-},u_{+}$, such that $v_{-}v_{0}v_{+}=u_{-}u_{0}u_{+}\in\mathcal{B}(V)$,
the construction is complete, showing that $V_{1}$ is indeed irreducible.

To see that $V_{1}$ is mixing, let $u_{1},u_{2}\in\mathcal{B}(V_{0})$ with
$|u_{1}|>m$, where $m$ is as above, and $|u_{2}|=|u_{1}|+1$. Let
$\gamma^{\pm}_{i}\in\mathcal{B}(X)$, $i=1,2$, be such that
$u_{i}\gamma^{+}_{i}\mu\gamma^{-}_{i}u_{i}\in\mathcal{B}(X)$. Then
$x_{i}=(u_{i}\gamma^{+}_{i}\mu\gamma^{-}_{i})^{\infty}\in V_{1}$ for both
$i=1,2$. Indeed, certainly $x_{i}\in X$, since
$u_{i}\gamma^{+}_{i}\mu\gamma^{-}_{i}u_{i}\in\mathcal{B}(X)$ and $X$ is a
$1$-step SFT. Moreover, $\mathrm{per}(x_{i})$ divides $\ell+|u_{i}|$, and
$\gcd(\ell+|u_{1}|,\ell+|u_{2}|)=\gcd(\ell+|u_{1}|,\ell+|u_{1}|+1)=1$, so
$\gcd(\mathrm{per}(x_{1}),\mathrm{per}(x_{2}))=1$. Since $V_{1}$ is an
irreducible SFT with periodic points of coprime periods, $V_{1}$ is mixing. ∎

As advertised, we now use Lemma 3.8 to prove the following lemma, which is
applied in the proof of 4.4, which in turn is the main input to the proof of
3.7.

######  Lemma 3.9.

Let $X$ be a mixing SFT, $Y$ a mixing sofic shift, and $\pi:X\to Y$ a factor
code. Let $W_{0}\subsetneq Y$ be an SFT. Then there exists a mixing SFT
$V_{1}\subset X$ with $W_{0}\subset\pi(V_{1})\subsetneq Y$.

###### Proof.

Let $V_{0}=\pi^{-1}(W_{0})\subset X$. Note that $V_{0}$ is an SFT since
$W_{0}$ is an SFT. Let $g$ be the mixing gap of $X$. Let $y\in Y\setminus
W_{0}$ be a periodic point with least period $k\geq g$. Such a $y$ certainly
exists because periodic points are dense in $Y$ and $W_{0}$ is a proper
subshift. Let $k^{\prime}$ be such that
$y_{[0,k^{\prime})}\notin\mathcal{B}_{k^{\prime}}(W_{0})$. Let
$\ell=k+k^{\prime}$. Then every $\ell$-block in $y$ is forbidden in $W_{0}$.
In particular, for any $x\in\pi^{-1}(\\{y\\})$ and any $i\in\mathbb{Z}$, we
have $x_{[i,i+\ell)}\notin\mathcal{B}(V_{0})$.

By 3.2, let $\mu$ be an $(X,V_{0},g)$ stamp. Let $V_{1}$ consist of the
closure of the set of points of the form $\dots
v_{-1}\gamma^{+}_{-1}\mu\gamma^{-}_{0}v_{0}\gamma^{+}_{0}\mu\gamma^{-}_{1}v_{1}\dots\in
X$ where each $v_{i}\in\mathcal{B}(V_{0})$ with $|v_{i}|\geq\ell$ and each
$\gamma^{\pm}_{i}\in\mathcal{B}_{g}(X)$. By Lemma 3.8, $V_{1}$ is indeed a
mixing SFT. Note that every point in $V_{1}$ contains $\ell$-blocks permitted
in $V_{0}$, so $V_{1}$ is disjoint from $\pi^{-1}(\\{y\\})$, and therefore
$\pi(V_{1})\subsetneq Y$. ∎

##  4 Counting

In this section, we prove 3.2 and 3.7, which state the existence and
properties respectively of the stamps and the shifts $V\subset X,W\subset Y$
used in Section 3. Section 4.1 contains two results required for the proof of
3.2, one (Lemma 4.1) showing that most blocks in a subshift with positive
entropy have little self-overlap, and the other (Lemma 4.2) showing that one
can assume, at the cost of a small loss of entropy, that a given sufficiently
long block appears syndetically in a mixing sofic shift. Section 4.2 then
gives a crucial asymptotic result on the number of periodic points in $Y$ with
a preimage of equal least period in $X$, and applies the results from Section
3.3 to construct the shifts $V$ and $W$.

###  4.1 Self-overlap and stamps

We begin by showing that most blocks have very little self-overlap, which we
use both to construct stamps and to determine the asymptotic number of
periodic points in $Y$ with a $\pi$-preimage of equal least period.

######  Lemma 4.1.

Let $Y$ be a subshift with $h(Y)>0$. For every $\alpha\in(0,1)$, there exist
$N\geq 1$ and $b>0$ such that for every $n\geq N$, there are at least
$(1-\exp(-bn))\exp(nh(Y))$ blocks $w\in\mathcal{B}_{n}(Y)$ with no self-
overlap of more than $\alpha n$.

###### Proof.

Let $\varepsilon=\frac{1}{2}(\alpha^{-1}-1)h(Y)$, so that
$\alpha(h(Y)+\varepsilon)<h(Y)$. Let $r=\exp(h(Y))$ and
$s=\exp(h(Y)+\varepsilon)$. Note that $s^{\alpha}<r<s$ and that
$r^{n}\leq|\mathcal{B}_{n}(Y)|$ for every $n$. Let $N_{0}$ be large enough
that for all $n\geq N_{0}$, we have $|\mathcal{B}_{n}(Y)|\leq s^{n}$. Let
$C_{1}=\sum_{k=1}^{N_{0}-1}|\mathcal{B}_{k}(Y)|$. Then the number of blocks in
$X$ of length $n$ with self-overlap of more than $\alpha n$ is at most

$\displaystyle\sum_{k=1}^{\lceil\alpha n\rceil}|\mathcal{B}_{k}(Y)|$
$\displaystyle\leq\sum_{k=1}^{N_{0}-1}|\mathcal{B}_{k}(Y)|+\sum_{k=N_{0}}^{\lceil\alpha
n\rceil}|\mathcal{B}_{k}(Y)|$ $\displaystyle\leq
C_{1}+\sum_{k=N_{0}}^{\lceil\alpha n\rceil}s^{n}$ $\displaystyle\leq
C_{1}+\frac{s^{\alpha n+2}-s^{N_{0}}}{s-1}$ $\displaystyle\leq C_{2}s^{\alpha
n}$

where

$C_{2}=C_{1}+\frac{s^{2}}{s-1}$

Let $N>\frac{(1-\alpha)h(Y)-\alpha\varepsilon}{\log C_{2}}$. Then, for $n\geq
N$, the number of blocks in $Y$ of length $n$ with no self-overlap by more
than $\alpha n$ is at least

$\displaystyle|\mathcal{B}_{n}(Y)|-\sum_{k=1}^{\lceil\alpha
n\rceil}|\mathcal{B}_{k}(Y)|$ $\displaystyle\geq r^{n}-C_{2}s^{\alpha n}$
$\displaystyle=r^{n}\left(1-C_{2}\left(\frac{s^{\alpha}}{r}\right)^{n}\right)$
$\displaystyle>(1-\exp(-bn))\exp(nh(Y))$

where we can take

$\displaystyle b$
$\displaystyle=\frac{1}{2}\log\left(C_{2}\left(\frac{r}{s^{\alpha}}\right)^{N}\right)$
$\displaystyle=(1-\alpha)h(Y)-\alpha\varepsilon-\frac{1}{N}\log C_{2}$

which is positive by the choice of $N$. ∎

We now control the entropy loss incurred by requiring a given long block to
appear syndetically.

######  Lemma 4.2.

Let $Y$ be a strongly irreducible subshift with $h(Y)>0$. For every
$\varepsilon>0$, there exist $\beta\in(0,1)$ and $N\geq 1$ such that for every
$n\geq N$ and every $\theta\in\mathcal{B}_{\lfloor\beta n\rfloor}(Y)$, the
subshift $S\subset Y$ consisting of points $y\in Y$ in which $\theta$ appears
at least once in $y_{[i,i+n)}$ for every $i\in\mathbb{Z}$ has entropy at least
$h(Y)-\varepsilon$.

###### Proof.

Let $g$ be the gap for $Y$. Let $\beta=\min\\{\varepsilon/(8h(Y)),1/2\\}$ and
let $N=\lceil 4(2g+1)h(Y)/\varepsilon\rceil$. Let $n\geq N$ and fix
$\theta\in\mathcal{B}_{\lfloor\beta n\rfloor}(Y)$. For $m\geq n$, and for all
$u_{1},\dots,u_{k}\in\mathcal{B}_{(1-2\beta)n-2g}(Y)$, where $k=\lfloor
m/n\rfloor$, there exist $v^{\pm}_{1},\dots,v^{\pm}_{k}\in\mathcal{B}_{g}(Y)$
and $v_{0}\in\mathcal{B}_{m-kn}(Y)$ such that

$v_{0}\theta v^{-}_{1}u_{1}v^{+}_{1}\theta v^{-}_{2}u_{2}v^{+}_{2}\dots\theta
v^{-}_{k}u_{k}v^{+}_{k}\in\mathcal{B}_{m}(Y)$

Therefore, by manipulation of logarithms and the fact that
$h(Y)=\inf_{\ell\geq 1}\frac{1}{\ell}\log|\mathcal{B}_{\ell}(Y)|$ by
definition,

$\displaystyle|\mathcal{B}_{m}(S)|$
$\displaystyle\geq|\mathcal{B}_{\lfloor(1-2\beta)n\rfloor-2g}(Y)|^{\lfloor
m/n\rfloor}$ $\displaystyle\frac{1}{m}\log|\mathcal{B}_{m}(S)|$
$\displaystyle\geq\frac{1}{m}\log\left(|\mathcal{B}_{\lfloor(1-2\beta)n\rfloor-2g}(Y)|^{(m-1)/n}\right)$
$\displaystyle=\left(1-\frac{1}{m}\right)\frac{1}{n}\log|\mathcal{B}_{\lfloor(1-2\beta)n\rfloor-2g}(Y)|$
$\displaystyle\geq\left(1-\frac{1}{m}\right)\frac{1}{n}(\lfloor(1-2\beta)n\rfloor-2g)h(Y)$
$\displaystyle>h(Y)-\varepsilon/2$

for large enough $m$, where the final inequality follows from the choices of
$\beta$ and $N$. We conclude that
$h(S)=\liminf_{m\to\infty}\frac{1}{m}|\mathcal{B}_{n}(S)|>h(Y)-\varepsilon$. ∎

###### Proof of 3.2.

It is clearly enough to prove the result for $u_{1},u_{2}$ sufficiently long,
since we can then pass to subwords of $u_{1},u_{2}$. By Lemma 4.2, let
$\beta\in(0,1)$, $m$ sufficiently large, and $\theta\in\mathcal{B}_{\beta
m}(Y)\setminus\mathcal{B}(W)$ be such that the subshift $S\subset Y$ defined
by requiring at least one appearance of $\theta$ in any block of length $m$
has $h(S)>0$. Let $\alpha\in(0,1)$ be arbitrary, and let $n>(m+k)/(1-\alpha)$
be large enough that, by Lemma 4.1, there exists $\mu\in\mathcal{B}_{n}(S)$
such that $\mu$ has no self-overlap by more than $\alpha n$, in particular by
more than $n-(m+k)$.

Let $u_{1}\in\mathcal{B}_{k_{1}}(U)$, $u_{2}\in\mathcal{B}_{k_{2}}(U)$ with
$k_{1},k_{2}\geq m$ and let $v_{1},v_{2}\in\mathcal{B}_{k}(Y)$. Then $\mu$
cannot appear in $u_{1}v_{2}\mu v_{2}u_{2}$ except at the position explicitly
indicated. Indeed, $\mu$ cannot appear at a position shifted by at most
$m+k$—otherwise, $\mu$ would overlap itself by too much—and it cannot appear
at a position shifted by more than $m+k$, as it would then overlap with
$u_{1}$ or $u_{2}$ in a block of length at least $m$, contradicting the fact
that $\mu\in\mathcal{B}(S)$, and thus has $\theta$ as a subword. ∎

###  4.2 Entropy and periodic points

We first show that at least a positive fraction of periodic points in $Y$ of
sufficient least period have a preimage of equal least period, and in
particular that their growth is exponential with rate $h(Y)$.

######  Proposition 4.3.

Let $X$ be a mixing SFT, $Y$ a mixing sofic shift, and $\pi:X\to Y$ a factor
code. Then $\lim_{n\to\infty}\frac{1}{n}\log r_{n}(\pi)=h(Y)$.

###### Proof.

Let $g$ be the mixing gap of $X$. By Lemma 4.1, let $b>0$ and $N>3g$ be such
that, for all $n\geq N$, the number of blocks in $Y$ of length $n-g$ with no
self-overlap by more than $n/3$ is at least $c\exp(nh(Y))$, where we may take
$c=\frac{1}{2}\exp(-gh(X))$. For each block $v\in\mathcal{B}_{n-g}(Y)$, there
exists a periodic point $x\in X$ with $\pi(x)_{[0,n-g)}=v$ such that
$\mathrm{per}(x)$ divides $n$. Thus $\pi(x)$ is also periodic with least
period dividing $n$. Moreover, if $v$ has no self-overlap by more than $n/3$,
then in fact $\mathrm{per}(\pi(x))=n$. Therefore $r_{n}(\pi)\geq
c\exp(nh(Y))$, so $\liminf_{n\to\infty}\frac{1}{n}\log r_{n}(\pi)\geq h(Y)$,
matching $\limsup_{n\to\infty}\frac{1}{n}\log
r_{n}(\pi)\leq\lim_{n\to\infty}\frac{1}{n}\log q_{n}(Y)=h(Y)$. ∎

We now assemble the quantitative results proven so far.

######  Proposition 4.4.

Let $X$ be a mixing SFT, $Y$ a mixing sofic shift, and $\pi:X\to Y$ a factor
code. Let $\varepsilon>0$ and $N_{0}\geq 1$. Then there exist $N_{1}\geq
N_{0}$ and proper subshifts $W\subsetneq Y$, $V=\pi^{-1}(W)\subset X$, such
that: $h(W)>h(Y)-\varepsilon$; for $n\leq N_{1}$,
$r_{n}(\pi|_{V})=r_{n}(\pi)$; and for $n\geq N_{1}$,
$r_{n}(\pi|_{V})>\exp(n(h(Y)-\varepsilon))$.

###### Proof.

By Lemma 2.1 and Lemma 3.9, let $V_{1}\subset X$ be a mixing SFT such that
$h(Y)-\varepsilon/2<h(\pi(V_{0}))<h(Y)$. Let $W_{1}=\pi(V_{1})$. By 4.3, let
$N_{1}\geq N_{0}$ be such that for any $n\geq N_{1}$, we have $\frac{1}{n}\log
r_{n}(\pi|_{V_{1}})>h(W_{1})-\varepsilon/2>h(Y)-\varepsilon$. Let
$W=W_{1}\cup\bigcup_{n=1}^{N_{1}}R_{n}(\pi)$ and $V=\pi^{-1}(W)$. Then
$r_{n}(\pi|_{V})=r_{n}(\pi)$ for all $n\leq N_{1}$.

To see that $W\neq Y$, observe that the only $n$-blocks in $W$ that may not be
in $W_{1}$ are those in the low-order periodic points that have been adjoined,
which are bounded in number by a constant. That is,
$|\mathcal{B}_{n}(W)|\leq|\mathcal{B}_{n}(W_{1})|+C$ for all $n\geq N_{1}$,
where we can take $C=\sum_{k=1}^{N_{1}}k|R_{k}(\pi)|$. Thus
$h(W)=h(W_{1})<h(Y)$. ∎

4.4 is the final input to the proof of 3.7, and thus of 1.1.

###### Proof of 3.7.

Let $\varepsilon=h(Y)-h(Z)$. Let $N_{0}\geq 1$ be large enough that for all
$n\geq N_{0}$,

$\frac{1}{n}\log\max\\{q_{n}(Z),|\mathcal{B}_{n}(Z)|\\}<h(Z)+\frac{\varepsilon}{4}$

By 4.4, let $W\subset Y$, $V=\pi^{-1}(W)\subset X$, and $N_{1}\geq N_{0}$ be
such that $h(W)>h(Y)-\frac{\varepsilon}{4}$, $r_{n}(\pi|_{V})=r_{n}(\pi)$ for
all $n\leq N_{1}$, and $\frac{1}{n}\log
r_{n}(\pi|_{V})>h(Y)-\frac{\varepsilon}{4}$ for all $n\geq N_{1}$. Note that
$h(W)>h(Z)+\frac{\varepsilon}{2}$ and that $q_{n}(Z)\leq r_{n}(\pi|_{V})$ for
all $n\geq 1$.

Let $g$ be the mixing gap of $X$. By 3.2, let
$\mu\in\mathcal{B}(Y)\setminus\mathcal{B}(W)$ be a $(Y,W,g)$ stamp. Let
$\ell=|\mu|+2g$. Then since $h(Z)<h(W)$, there exists $N$ sufficiently large
so that for all $n\geq N$, in particular for $N+\ell\leq n\leq 2N+\ell-1$, we
have $|\mathcal{B}_{n}(Z)|<|\mathcal{B}_{n-\ell}(W)|$. ∎

##  5 Proofs of Lemma 2.6 and 1.3

We first use 4.3, along with facts about Markov approximations in Section 2.2,
to prove Lemma 2.6, which reduces 1.1 to the case where $Z$ is a $1$-step SFT.

###### Proof of Lemma 2.6.

We use the properties of Markov approximations mentioned in Section 2. Let
$\varepsilon=h(Y)-h(Z)$. Let $m_{0}$ be such that
$h(Z_{m_{0}})<h(Z)+\varepsilon/3$, where $Z_{m_{0}}$ is the $m_{0}$th Markov
approximation to $Z$, and such that, by 4.3, for all $n\geq m_{0}$,
$\frac{1}{n}\log r_{n}(\pi)>h(Y)-\varepsilon/3$. Let $m_{1}\geq m_{0}$ be such
that $\frac{1}{n}\log q_{n}(Z_{m_{0}})<h(Z_{m_{0}})+\varepsilon/3$ for all
$n\geq m_{1}$. Let $m_{2}\geq m_{1}$ be such that for all periodic points
$z\in P(Z_{m_{1}})\setminus Z$ (under the natural embedding $Z\hookrightarrow
Z_{m_{1}}$) with $\mathrm{per}(z)\leq m_{1}$, we have
$z_{[0,m_{2})}\notin\mathcal{B}_{m_{2}}(Z)$. Then $Z_{m_{2}}$ satisfies
$q_{n}(Z_{m_{2}})=q_{n}(Z)\leq r_{n}(\pi)$ for all $n\leq m_{1}$. Moreover,
since $Z_{m_{2}}\subset Z_{m_{0}}$, $\frac{1}{n}\log
q_{n}(Z_{m_{2}})\leq\frac{1}{n}\log q_{n}(Z_{m_{0}})$ for all $n$; in
particular,

$\displaystyle\frac{1}{n}\log q_{n}(Z_{m_{2}})$
$\displaystyle<h(Z_{m_{0}})+\varepsilon/3$ $\displaystyle<h(Z)+2\varepsilon/3$
$\displaystyle<h(Y)-\varepsilon/3$ $\displaystyle<\frac{1}{n}\log r_{n}(\pi)$

for all $n\geq m_{1}$. Taking $Z^{\prime}=Z_{m_{2}}^{[m_{2}]}$ to be the
$m_{2}$th higher block shift, the lemma is proved. ∎

To prove 1.3, in the mixing sofic case, we use Lemma 2.2 to handle low-order
periodic point obstructions, with periodic points of sufficiently high order
controlled by 4.3. To handle the arbitrary case, we first give an improved
Markov approximation (Lemma 5.2), embedding an arbitrary subshift into a
mixing SFT with only slightly greater entropy. The construction uses Lemma
3.8; in Lemma 5.1 we estimate the entropy of the mixing SFT constructed in
Lemma 3.8.

######  Lemma 5.1.

Let $X$ be a mixing SFT with gap $g$ and let $V_{0}\subset X$ be an SFT. Let
$k\geq g$ and let $\mu\in\mathcal{B}(X)\setminus\mathcal{B}(V_{0})$ be an
$(X,V_{0},k)$ stamp. For any $\varepsilon>0$, there exists $N\geq|\mu|$ such
that $h(V_{1})<h(V_{0})+\varepsilon$, where $V_{1}$ (depending on $N$) is as
in Lemma 3.8.

###### Proof.

Let $N_{0}\geq 1$ be such that for all $n\geq N_{0}$ we have
$\frac{1}{n}\log|\mathcal{B}_{n}(V_{0})|<h(V_{0})+\varepsilon/4$. Let
$N>2N_{0}$ be such that

$\frac{1}{N}\max\\{\log
N,\log|\mathcal{B}_{k}(X)|^{2},\log|\mathcal{B}_{N_{0}}(V_{0})|\\}<\frac{\varepsilon}{4}$

We will show that
$\frac{1}{N}\log|\mathcal{B}_{N}(V_{1})|<h(V_{0})+\varepsilon$. Consider a
block of length $N$ in $V_{1}$. Such a block can contain at most one full or
partial block of the form $\gamma^{+}\mu\gamma^{-}$ where
$\gamma^{\pm}\in\mathcal{B}_{k}(X)$. The $\mu$, if present, can begin at any
of the $N$ positions. The rest of the block of length $N$, outside the block
$\gamma^{+}\mu\gamma^{-}$, consists of one or two blocks from $V_{0}$, with
length totalling at most $N$. We thus have

$|\mathcal{B}_{N}(V_{1})|\leq N|\mathcal{B}_{k}(X)|^{2}\max_{0\leq\ell\leq
N/2}|\mathcal{B}_{\ell}(V_{0})||\mathcal{B}_{N-\ell}(V_{0})|$

If $0\leq\ell\leq N_{0}$, then
$|\mathcal{B}_{\ell}(V_{0})||\mathcal{B}_{N-\ell}(V_{0})|\leq|\mathcal{B}_{N_{0}}(V_{0})||\mathcal{B}_{N}(V_{0})|$,
so

$\displaystyle\frac{1}{N}\log\left(|\mathcal{B}_{\ell}(V_{0})||\mathcal{B}_{N-\ell}(V_{0})|\right)$
$\displaystyle\leq\frac{1}{N}\log|\mathcal{B}_{N_{0}}(V_{0})|+\frac{1}{N}\log|\mathcal{B}_{N}(V_{0})|$
$\displaystyle<h(V_{0})+\frac{\varepsilon}{2}$

If $N_{0}\leq\ell\leq N/2$, then

$\displaystyle\frac{1}{N}\log\left(|\mathcal{B}_{\ell}(V_{0})||\mathcal{B}_{N-\ell}(V_{0})|\right)$
$\displaystyle<\frac{1}{N}\left(\ell\left(h(V_{0})+\frac{\varepsilon}{4}\right)+(N-\ell)\left(h(V_{0})+\frac{\varepsilon}{4}\right)\right)$
$\displaystyle=h(V_{0})+\frac{\varepsilon}{4}$

Therefore

$\displaystyle\frac{1}{N}\log|\mathcal{B}_{N}(V_{1})|$
$\displaystyle<\frac{1}{N}\log
N+\frac{1}{N}\log|\mathcal{B}_{k}(X)|^{2}+h(V_{0})+\frac{\varepsilon}{2}$
$\displaystyle<h(V_{0})+\varepsilon$

by the above choice of $N$. ∎

along with the following standard lemma improving the construction of the
Markov approximation. For completeness, we include a proof using Lemma 3.8.

######  Lemma 5.2.

Let $Z$ be a subshift and let $\varepsilon>0$. Then there exists a mixing SFT
$V$ containing $Z$ with $h(V)<h(Z)+\varepsilon$.

###### Proof.

Let $m$ be large enough that $h(Z_{m})<h(Z)+\varepsilon/2$, where $Z_{m}$ is
the $m$th Markov approximation to $Z$. Let $X$ be the full shift on the
alphabet of $Z$. Certainly $Z_{m}\subseteq X$. If $Z_{m}=X$, then we can take
$V=X$. If $Z_{m}\neq X$, then by 3.2, let $\mu$ be an $(X,Z_{m},k)$ stamp for
some $k\geq 0$. Let $V_{0}=Z_{m}$ and $V=V_{1}$ as in Lemma 3.8 where $N$ is
large enough that, by Lemma 5.1, we have $h(V)<\varepsilon/2$. Thus $V$ is
indeed a mixing SFT containing $Z$ with $h(V)<h(Z)+\varepsilon$. ∎

###### Proof of 1.3.

We first consider the case in which $Z$ is mixing sofic. Let $\tilde{Z}$ be a
mixing SFT and $\chi_{0}:\tilde{Z}\to Z$ an almost invertible factor code. If
already $q_{n}(\tilde{Z})\leq r_{n}(\pi)$ for all $n\geq 1$, then we can take
$Z^{\prime}=\tilde{Z}$ and apply 1.1 immediately to construct the claimed
embedding $\psi:Z^{\prime}\to X$. However, if $q_{n}(\tilde{Z})>r_{n}(\pi)$
for some $n$, so that $X,Y,\pi,\tilde{Z}$ violate the hypotheses of 1.1, then
we need to construct a further extension of $\tilde{Z}$ which satisfies the
hypotheses of 1.1. The construction, consisting a tower of extensions via
Lemma 2.2, is as follows.

By 4.3, since $h(\tilde{Z})=h(Z)<h(Y)$, there are at most finitely many $n$
such that $q_{n}(\tilde{Z})>r_{n}(\pi)$. Let $N$ denote the greatest such $n$.
Let $C=\sum_{k=1}^{N}\max\\{0,q_{k}(\tilde{Z})-r_{k}(\pi)\\}$. That is, $C$ is
the number of periodic points by which $X,Y,\pi,\tilde{Z}$ violate the
hypotheses of 1.1. For $1\leq k\leq N$ and $1\leq\ell\leq
k^{-1}\max\\{0,q_{k}(\tilde{Z})-r_{k}(\pi)\\}$, let $z_{k,\ell}$ be periodic
points with pairwise disjoint orbits, such that $\mathrm{per}(z_{k,\ell})=k$.
For a given $k$, the union of the orbits of the points $z_{k,\ell}$ has
cardinality $\max\\{0,q_{k}(\tilde{Z})-r_{k}(\pi)\\}$. Let
$C^{\prime}=\sum_{k=1}^{N}k^{-1}\max\\{0,q_{k}(\tilde{Z})-r_{k}(\pi)\\}$
(counting orbits, rather than points), and let
$\\{z^{(j)}\\}_{j=1}^{C^{\prime}}=\\{z_{k,\ell}\\}_{k,\ell}$ be an enumeration
of the points $z_{k,\ell}$.

Again by 4.3, let $M>N$ be large enough that for all $n\geq M$, we have
$q_{n}(\tilde{Z})+Cn\leq r_{n}(\pi)$. We now repeatedly apply Lemma 2.2. Let
$Z^{(0)}=\tilde{Z}$. For $1\leq j\leq C^{\prime}$, let $Z^{(j)}$ be a mixing
SFT and $\chi^{(j)}:Z^{(j)}\to Z^{(j-1)}$ an almost invertible factor code
such that the preimage of the orbit of $z_{j}$ under $\chi^{(j)}$ is a single
orbit of length $M\mathrm{per}(z_{j})$, and such that every periodic point in
$Z^{(j-1)}$ not in the orbit of $z_{j}$ has a unique preimage under
$\chi^{(j)}$. Let $\eta^{(1)}=\chi^{(1)}$ and
$\eta^{(j+1)}=\eta^{(j)}\circ\chi^{(j+1)}$. Let $Z^{\prime}=Z^{(C^{\prime})}$
and $\eta=\eta^{(C^{\prime})}:Z^{\prime}\to\tilde{Z}$. Certainly $\eta$ is
almost invertible, so $h(Z^{\prime})=h(\tilde{Z})<h(Y)$. We claim that
$q_{n}(Z^{\prime})\leq r_{n}(\pi)$ for all $n\geq 1$. Indeed, for each $j$, if
$\mathrm{per}(z_{j})=k$, then we have $q_{k}(Z^{(j)})=q_{k}(Z^{(j-1)})-k$,
$q_{Mk}(Z^{(j)})=q_{Mk}(Z^{(j-1)})+Mk$, and $q_{n}(Z^{(j)})=q_{n}(Z^{(j-1)})$
for all $n\notin\\{k,Mk\\}$. Therefore $q_{k}(Z^{\prime})=r_{k}(\pi)$, and

$\displaystyle q_{Mk}(Z^{\prime})$
$\displaystyle=q_{Mk}(\tilde{Z})+M\max\\{0,q_{k}(\tilde{Z})-r_{k}(\pi)\\}$
$\displaystyle\leq q_{Mk}(\tilde{Z})+CM$ $\displaystyle\leq r_{Mk}(\pi)$

where the last inequality follows from the choice of $M$. Therefore
$X,Y,\pi,Z^{\prime}$ satisfy the hypotheses of 1.1, so there exists a sliding
block code $\psi:Z^{\prime}\to X$ such that $\pi\circ\psi$ is injective. This
concludes the proof in the case that $Z$ is mixing sofic.

We now handle the general case, where $Z$ is an arbitrary subshift with
$h(Z)<h(Y)$. By Lemma 5.2, let $V$ be a mixing SFT containing $Z$ with
$h(V)<h(Y)$. By the mixing sofic case, let $V^{\prime}$ be a mixing SFT such
that $X,Y,\pi,V^{\prime}$ satisfy the hypotheses of 1.1, and let
$\chi:V^{\prime}\to V$ be an almost invertible factor code. Let
$Z^{\prime}=\chi^{-1}(Z)$. Then $\chi|_{Z^{\prime}}$ is still finite-to-one,
which concludes the proof. ∎

## Acknowledgments

I thank Tom Meyerovitch for posing the question that led to this work and
suggesting the argument for 4.3, and more generally for offering, with Brian
Marcus, very generous advice and supervision. I also thank Mike Boyle for a
helpful conversation by email about the relationship between my question [4]
and the embedding problem for sofic shifts.

## References

  * [1] Mike Boyle.  Lower entropy factors of sofic systems.  Ergod. Th. Dynam. Syst., 4:541–557, 1984.
  * [2] Dawoud Ahmad Dastjerdi and Somaye Jangjoo.  Dynamics and topology of $S$-gap shifts.  Topology Appl., 159:26554–2661, 2012.
  * [3] Guangyue Han, Brian Marcus, and Chengyu Wu.  Markov capacity for codes with an unambiguous symbol.  arXiv preprint, 2022.  https://arxiv.org/abs/2210.12251.
  * [4] Ville Salo (https://mathoverflow.net/users/123634/ville salo).  Cohomology for extension problems in symbolic/topological dynamics?  MathOverflow.  https://mathoverflow.net/q/424145 (version: 2022-06-07).
  * [5] John C. Kieffer.  Zero-error stationary coding over stationary channels.  Prob. Th. Rel. Fields, 56:113–126, 1981.
  * [6] Wolfgang Krieger.  On the subsystems of topological Markov chains.  Ergod. Th. Dynam. Syst., 2(2):195–203, 1982.
  * [7] Douglas Lind and Brian Marcus.  An introduction to symbolic dynamics and coding.  Cambridge University Press, 2nd edition, 2020.
  * [8] Brian Marcus.  Sofic systems and encoding data.  IEEE Trans. Info. Th., IT-31(3):366–377, 1985.
  * [9] Brian Marcus, Karl Petersen, and Susan Williams.  Transmission rates and factors of Markov chains.  In Richard Beals, Anatole Beck, Alexandra Bellow, and Arshag Hajian, editors, Conference in modern analysis and probability, volume 26 of Contemp. Math., pages 279–293. Amer. Math. Soc., 1984.
  * [10] Claude Shannon.  A mathematical theory of communication.  Bell Sys. Tech. J., 27:379–423, 623–656, 1948.
  * [11] Klaus Thomsen.  On the structure of a sofic shift space.  Trans. Amer. Math. Soc., 356(9):3557–3619, 2004.