#  An embedding theorem for multidimensional subshifts

Tom Meyerovitch  Ben-Gurion University of the Negev. Department of
Mathematics. Beer-Sheva, 8410501, Israel<EMAIL_ADDRESS>
###### Abstract.

Krieger’s embedding theorem provides clear necessary and sufficient conditions
for an arbitrary subshift to embed in a given topologically mixing
$\mathbb{Z}$-subshift of finite type. For certain families of
$\mathbb{Z}^{d}$-subshifts of finite type, Lightwood characterized the
_aperiodic_ subsystems. Here we remove the aperiodicity restriction and thus
generalize Krieger’s theorem by providing clear necessary and sufficient
conditions for an arbitrary subshift to embed in a “well-behaved” subshift of
finite type over a countable abelian group. To the best of our knowledge, our
characterization of subsystems with non-trivial periodic points is new already
for the case of the full shift $\\{0,1\\}^{\mathbb{Z}^{2}}$. The new class of
subshifts for which we have a complete characterization of the subsystems,
admits two natural equivalent descriptions. The first description involves the
map extension property, introduced implicitly by Mike Boyle in the early
1980’s for $\mathbb{Z}$-subshifts. The second description involves the notion
of an absolute retract, introduced by Borsuk in the 1930’s. Using an old
result of Boyle, we show that a $\mathbb{Z}$-subshift has the map extension
property if and only if it is a topologically mixing subshift of finite type.
We prove that a subshift over a countable abelian group has map extension
property if and only if it is an absolute retract, in a suitable sense. We
show that various natural examples of $\mathbb{Z}^{d}$ subshifts of finite
type satisfy the map extension property, hence our embedding theorem applies
for them. These include any subshift of finite type with a safe symbol and the
$k$-colorings of $\mathbb{Z}^{d}$ with $k\geq 2d+1$. We also establish a new
theorem regarding lower entropy factors of multidimensional subshifts, that
extends Boyle’s lower entropy factor theorem from the one-dimensional case.

##  1\. Introduction and statement of the main results

Krieger’s embedding theorem [16] provides simple necessary and sufficient
conditions for an arbitrary subshift to embed in a given topologically mixing
$\mathbb{Z}$-subshift of finite type.

Here is a formulation of Krieger’s embedding theorem [16]:

######  Theorem 1.1 (Krieger’s embedding theorem [16]).

Let $X$ be an arbitrary $\mathbb{Z}$-subshift and let $Y$ be a mixing
$\mathbb{Z}$-shift of finite type. Then $X$ embeds in $Y$ if and only if
either $X$ is topologically conjugate to $Y$ or $h(X)<h(Y)$ and for every
$n\in\mathbb{N}$ the number of points in $X$ that have least period $n$ is
less than or equal to the the number of points in $Y$ that have least period
$n$.

Because Krieger’s embedding theorem is a fundamental result in symbolic
dynamics, it was quite natural to seek a multidimensional version. Lightwood
carried out significant steps in this direction [17, 18] about a quarter of a
century ago. In particular, Lightwood characterized the _aperiodic_
$\mathbb{Z}^{d}$-subshifts that can embed in a certain class of
$\mathbb{Z}^{d}$-subshifts of finite type. A subshift $X$ is aperiodic if the
stabilzer of every point in $X$ is trivial. Here is a of one of Lightwood’s
main results:

######  Theorem 1.2 (Lightwood’s embedding theorem for square-filling mixing
$\mathbb{Z}^{2}$ -SFTs [17, 18]).

Let $X$ be an aperiodic $\mathbb{Z}^{2}$ subshift and let $Y$ be a square-
filling mixing $\mathbb{Z}^{2}$-SFT. Then $X$ embeds in $Y$ if and only if
$h(X)<h(Y)$.

We refrain from defining “square-filling mixing”, as this notion does not play
a role in the current paper.

The central missing ingredient in Lightwood’s work is a method of handling
points with non-trivial stabilizers in the domain $X$. In his paper [18]
Lightwood announced: “The techniques developed here play a central role in the
proof of an embedding theorem for general $\mathbb{Z}^{2}$ subshifts into
square-filling mixing SFTs which will be carried out in a subsequent paper”.
To the best of our knowledge, no such result has been published so far. In
this paper, building on previous work, including Krieger’s and Lightwood’s, we
obtain a complete characterization of the subsystems for a natural class of
$\mathbb{Z}^{d}$-SFTs.

In order to defer some definitions, we first state a particular case of our
main result. Given a $\mathbb{Z}^{2}$ subshift $X$ and $v\in\mathbb{Z}^{2}$,
let

$X_{v}=\\{x\in X\leavevmode\nobreak\ :\leavevmode\nobreak\
\sigma_{v}(x)=x\\}.$

Similarly, for a pair of linearly independent vectors $v,w\in\mathbb{Z}^{2}$
let $X_{v,w}$ denote the set of points in $x$ whose stablizer is equal to the
integer linear combinations of $v$ and $w$. The space $X_{v,w}$ is a finite
set.

Recall that a vector $v\in\mathbb{Z}^{2}$ is _primitive_ if it not a multiple
of some other vector in $w\in\mathbb{Z}^{2}$. If $v\in\mathbb{Z}^{2}$ is a
primitive vector and $n\in\mathbb{N}$, then the group $\mathbb{Z}^{2}/\langle
nv\rangle$ is isomorphic to
$\mathbb{Z}\times\left(\mathbb{Z}/n\mathbb{Z}\right)$, and so $X_{v}$ can
naturally be viewed as a $\mathbb{Z}\times(\mathbb{Z}/n\mathbb{Z})$-subshift.

######  Theorem 1.3.

A $\mathbb{Z}^{2}$-subshift $X$ embeds in $A^{\mathbb{Z}^{2}}$ if and only if
either $X$ is topologically conjugate to $A^{\mathbb{Z}^{2}}$ or both of the
following conditions hold:

  1. (1)

For every primitive vector $v\in\mathbb{Z}^{2}$ and every $n\in\mathbb{N}$
either $X_{nv}$ is topologically conjugate to the full-shift
$A^{\mathbb{Z}\times(\mathbb{Z}/n\mathbb{Z})}$ or the
$\mathbb{Z}\times(\mathbb{Z}/n\mathbb{Z})$-entropy of $X_{nv}$ is strictly
less than $\log(A)$.

  2. (2)

For every pair of independent vectors $v,w\in\mathbb{Z}^{2}$ the number of
points in $X_{v,w}$ does not exceed the number of points in
$A^{\mathbb{Z}^{2}}$ whose stablizer is equal to the integer linear
combinations of $v$ and $w$.

The statement of Theorem 1.3 suggests that subshifts over more general abelian
groups must be considered even when one is only interested in the
characterization of subsystems of $\mathbb{Z}^{d}$-SFTs.

In this paper, by a _map_ between $\Gamma$-subshifts $X$ and $Y$ we mean a
continuous, $\Gamma$-equivariant function from $X$ into $Y$. An _embedding_ of
$X$ into $Y$ is an injective map from $X$ into $Y$. An _isomorphism_ of $X$
and $Y$ is a bijective map between $X$ and $Y$. We use the notation
$X\hookrightarrow Y$ to indicate that $X$ embeds continuously and
$\Gamma$-equivariantly into $Y$.

######  Theorem 1.4.

Let $\Gamma$ be a countable abelian group and let $X,Y$ be $\Gamma$-subshifts.
Suppose that $Y$ has the map extension property. Let $Z\subseteq X$ be a
closed $\Gamma$-invariant set, and let $\hat{\rho}:Z\to Y$ be an embedding.
Then $\hat{\rho}$ extends to an embedding $\rho:X\to Y$ if and only if for
every subgroup $\Gamma_{0}\leq\Gamma$ one of the conditions holds:

  1. (1)

$\hat{\rho}\mid_{Z_{\Gamma_{0}}}:Z_{\Gamma_{0}}\to Y_{\Gamma_{0}}$ extends to
an isomorphism $\rho_{\Gamma_{0}}:X_{\Gamma_{0}}\to Y_{\Gamma_{0}}$

  2. (2)

$h(\overline{X}_{\Gamma_{0}})<h(\overline{Y}_{\Gamma_{0}})$ and
$\mathit{Ker}(Y_{\Gamma_{0}})\leq\mathit{Ker}(X_{\Gamma_{0}})$.

The notion of _map extension property is defined and discussed_ is defined and
discussed in Section 4. We prove that for a $\Gamma$-subshift $Y$, satisfying
the map extension property is equivalent to being an _absolute retract_ for
the class of subshift that avoid certain stablizers (Proposition 4.16). We
prove that a $\mathbb{Z}$-subshift has the map extension property if and only
if it is a mixing SFT. We prove the equivalence of these two properties in
Proposition 4.25. All the other new notations that appear in the statement of
Theorem 1.4 are defined in Section 2. Specifically, the notation
$X_{\Gamma_{0}}$ is given by Definition 2.13 and the notation
$\overline{X}_{\Gamma_{0}}$ is given by Definition 2.14.

We emphasize the primary case $\hat{X}=\emptyset$ in the following corollary:

######  Corollary 1.5.

Let $\Gamma$ be a countable abelian group and let $X,Y$ be $\Gamma$-subshifts.
Suppose that $Y$ has the map extension property. Then $X\hookrightarrow Y$ if
and only if for every subgroup $\Gamma_{0}\leq\Gamma$ one of the conditions
holds:

  1. (1)

$X_{\Gamma_{0}}$ is topologically conjugate to $Y_{\Gamma_{0}}$.

  2. (2)

$h(\overline{X}_{\Gamma_{0}})<h(\overline{Y}_{\Gamma_{0}})$ and
$\mathit{Ker}(Y_{\Gamma_{0}})\leq\mathit{Ker}(X_{\Gamma_{0}})$.

In the particular case that $\Gamma=\mathbb{Z}$, the statement of Corollary
1.5 coincides with the statement of Krieger’s embedding theorem, as stated in
Theorem 1.1.

_Acknowledgments:_ This research was supported by the Israel Science
Foundation grant No. 859/22.

##  2\. Notation and definitions

###  2.1. Countable abelian groups

Throughout this paper $\Gamma$ will be a countable or finite abelian group. We
will use additive notation for the group operation in $\Gamma$. We will denote
the identity element of $\Gamma$ by $0$. We write $A\Subset\Gamma$ to indicate
that that $A$ is a finite subset of $\Gamma$. For $A,B\subseteq\Gamma$ and
$\gamma\in\Gamma$ the following standard notation will be used:

$\gamma+A=\left\\{\gamma+a\leavevmode\nobreak\ :\leavevmode\nobreak\ a\in
A\right\\},$ $A+B=\left\\{a+b\leavevmode\nobreak\ :\leavevmode\nobreak\ a\in
A,\leavevmode\nobreak\ b\in B\right\\},$ $A-B=\left\\{a-b\leavevmode\nobreak\
:\leavevmode\nobreak\ a\in A,\leavevmode\nobreak\ b\in B\right\\},$
$-A=\left\\{-a\leavevmode\nobreak\ :\leavevmode\nobreak\ a\in A\right\\}.$

For $A,B,C\subseteq\Gamma$, we use the notation $C=A\oplus B$ to indicate that
for every $c\in C$ there exists a unique $a\in A$ and a unique $b\in B$ such
that $c=a+b$.

Call a set $A\subseteq\Gamma$ _symmetric_ if $A=-A$.

######  Definition 2.1.

Given $K,F\subseteq\Gamma$, let $\partial_{K}F$ denote the set of
$\gamma\in\Gamma$ such that $(\gamma+K)\cap F\neq\emptyset$ and
$(\gamma+K)\setminus F\neq\emptyset$. We refer to $\partial_{K}F$ as the _$K$
-boundary of $F$_.

######  Definition 2.2.

Given $\epsilon>0$ and $K\Subset\Gamma$, a set $F\Subset\Gamma$ is called
$(K,\epsilon)$-invariant if $|\partial_{K}F|<\epsilon|F|$.

######  Definition 2.3.

A sequence $(F_{n})_{n=1}^{\infty}$ of finite subsets $F_{n}\Subset\Gamma$ is
called a _Følner sequence_ in $\Gamma$ if for every $\epsilon>0$ and any
$K\Subset\Gamma$ there exists $n_{0}\in\mathbb{N}$ such that $F_{n}$ is
$(K,\epsilon)$-invariant for every $n\geq n_{0}$.

It is well-known that any countable abelian group admits a Følner sequence. A
countable group $\Gamma$ is called _amenable_ if it admits a Følner sequence.
The following definition is due to Weiss [23]:

######  Definition 2.4.

A finite subset $F\Subset\Gamma$ is called a _monotile_ if there exists
$A\subseteq\Gamma$ such that $\Gamma=F\oplus A$.

As mentioned in [23], it is easy to construct a for any countable abelian
group a Følner seqeunce of monotiles. This fact follows for instance from
Lemma 2.9 below.

######  Definition 2.5.

Given a set $K\subseteq\Gamma$, We set that a set $F\subseteq\Gamma$ is _$K$
-separated_ if $(v_{1}+K)\cap(v_{2}+K)=\emptyset$ whenever $v_{1},v_{2}\in F$
and $v_{1}\neq v_{2}$. We say that $F\subseteq\Gamma$ is a _maximal
$K$-separated_ set if $F$ is $K$-separated and there is no $K$-separated set
that properly contains $F$.

The following lemma collects some elementary yet useful statements related to
the notion of an $A$-separated set:

######  Lemma 2.6.

Let $A,B,C\subset\Gamma$ be subsets. Then:

  1. (1)

$A$ is $B$-separated if and only if $(A-A)\cap(B-B)=\\{0\\}$.

  2. (2)

$A$ is $B$-separated if and only if $B$ is $A$-separated.

  3. (3)

If $A$ is $B$-separated and $A+B$ is $C$-separated then $A$ is
$B+C$-separated.

###### Proof.

  1. (1)

The statement that $A$ is $B$-separated means that whenever $a_{1},a_{2}\in
A$, $b_{1},b_{2}\in B$ satisfy $a_{1}+b_{1}=a_{2}+b_{2}$ then $a_{1}=a_{2}$.
Equivalently, $a_{1},a_{2}\in A$, $b_{1},b_{2}\in B$ satisfy
$a_{1}-a_{2}=b_{2}-b_{1}$ then $a_{1}=a_{2}$ $b_{1}=b_{2}$. Rephrasing, $A$ is
$B$-separated if and only if if whenever $\gamma\in(A-A)\cap(B-B)$ then
$\gamma=0$.

  2. (2)

The previous formulation shows that the role of the sets $A$ and $B$ in the
statement “$A$ is $B$-separated” are completely symmetric. So $A$ is
$B$-separated if and only if $B$ is $A$-separated.

  3. (3)

Suppose that $A$ is $B$-separated and that $A+B$ is $C$-separated. Suppose
$a_{1},a_{2}\in A$, $b_{1},b_{2}\in B$ and $c_{1},c_{2}\in C$ satisfy that

$a_{1}+(b_{1}+c_{1})=a_{2}+(b_{2}+c_{2}).$

Because $A+B$ is $C$-separated, we have that $a_{1}+b_{1}=a_{2}+b_{2}$ and
$c_{1}=c_{2}$. Because $A$ is $B$-separated we have conclude that
$a_{1}=a_{2}$ and $b_{1}=b_{2}$. We conclude that under the assumptions above,
whenever $a_{1},a_{2}\in A$, $b_{1},b_{2}\in B$ and $c_{1},c_{2}\in C$ satisfy
that

$a_{1}+(b_{1}+c_{1})=a_{2}+(b_{2}+c_{2}),$

Then $a_{1}=a_{2}$. Equivalently, we showed that $A$ is $(B+C)$-separated.

∎

It is easy to check that an increasing union of $K$-separated sets is again a
$K$-separated set, so any $K$-separated set is contained in a maximal
$K$-separated set. The following basic lemma regarding maximal $K$-separated
sets will be useful:

######  Lemma 2.7.

Let $K\subseteq\Gamma$ be a non-empty symmetric set. $F\subseteq\Gamma$ be a
maximal $K$-separated set. Then $F+K+K=\Gamma$.

###### Proof.

Since $F$ is a maximal $K$-separated set, for any $v\in\Gamma$ there exists
$k,k_{1}\in K$ and $v_{2}\in F$ such that $v+k=v_{1}+k_{1}$. It follows that
$v=v_{1}+k_{1}-k$. Since $K$ is symmetric, $-k\in K$, so $v\in F+K+K$, proving
that $\Gamma=F+K+K$. ∎

######  Definition 2.8.

A subset $D\subseteq\Gamma$ is a _fundamental domain_ for
$\Gamma_{0}\leq\Gamma$ if for each $v\in\Gamma$ the coset $v+\Gamma_{0}$
intersects $D$ exactly once.

Equivalently, $D\subseteq\Gamma$ is a fundamental domain for
$\Gamma_{0}\leq\Gamma$ if and only if $\Gamma=D\oplus\Gamma_{0}$. It can be
directly verified that a subset $D\subseteq\Gamma$ is a fundamental domain for
$\Gamma_{0}\leq\Gamma$ if and only if $D$ is a maximal $\Gamma_{0}$-separated
set.

We will later use the following basic lemma:

######  Lemma 2.9.

Let $\Gamma$ be a countable abelian group, and let $K\Subset\Gamma$ be a
finite set and $\epsilon>0$. Then there exists a finite set $F$ such that any
$F$-separated subgroup $\Gamma_{0}\leq\Gamma$ admits a fundamental domain
which is a disjoint union of translates of a $(K,\epsilon)$-invariant set.

###### Proof.

Let $\Gamma$ be a countable abelian group, and let $K\Subset\Gamma$ be a
finite set and $\epsilon>0$. Let $\Delta\leq\Gamma$ be the group generated by
the elements of $K$. Since $\Delta$ is a finitely generated abelian group,
there exists a finite abelian group $G$ , an integer $d\geq 0$ and a group
isomorphism $\Psi:\Delta\to(\mathbb{Z}^{d}\times G)$. Let
$\tilde{K}=\Psi(K)\Subset(\mathbb{Z}^{d}\times G)$. Classical convex geometry
tells us that there exists $R>0$ such that for any compact convex set
$C\Subset\mathbb{R}^{d}$ that contains a euclidean ball of radius $R$ in
$\mathbb{R}^{d}$, the set $\tilde{C}=(C\cap\mathbb{Z}^{d})\times G$ is
$(\tilde{K},\epsilon)$-invariant (see Lemma 6.11). For such $R\in\mathbb{N}$,
let $F\Subset\Delta\subseteq\Gamma$ be given by
$F=\Psi^{-1}(\\{-R,\ldots,R\\}^{d}\times G)$.

Let $\Gamma_{0}\leq\Gamma$ be any $F$-separated subgroup. Let
$\Delta_{0}=\Delta\cap\Gamma_{0}$. Then
$\Psi(\Delta_{0})\leq\mathbb{Z}^{d}\times\\{0\\}$ is isomorphic to a subgroup
of $\mathbb{Z}^{d}$, thus $\Psi(\Delta_{0})$ is isomorphic to $\mathbb{Z}^{k}$
for some $0\leq k\leq d$. Let
$v_{1},\ldots,v_{k}\subset\mathbb{Z}^{d}\subset\mathbb{R}^{d}$ be independent
vectors such that $\\{(v_{1},0),\ldots,(v_{k},0)\\}$ are a generating set for
$\Psi(\Delta_{0})$. Find
$v_{k+1},\ldots,v_{d}\in\mathbb{Z}^{d}\setminus\\{-R,\ldots,R\\}^{d}$ so that
$\\{v_{1},\ldots,v_{d}\\}$ is a basis for $\mathbb{R}^{d}$. Let

$\tilde{D}_{0}=\left\\{\sum_{i=1}^{d}t_{i}v_{i}\leavevmode\nobreak\
:\leavevmode\nobreak\ 0\leq t_{i}\leq 1\right\\}\cap\mathbb{Z}^{d},$

and let $D_{0}=\Psi^{-1}(\tilde{D}_{0})\times G\subset\Delta$. Then
$D_{0}\Subset\Gamma$ is $(K,\epsilon)$-invariant. Let

$D_{1}=\biguplus_{n_{k+1},\ldots,n_{d}\in\mathbb{Z}^{d}}\left(\Psi^{-1}(\sum_{i=k+1}^{d}n_{i}v_{i},0)+D_{0}\right).$

Then $D_{1}$ is a fundamental domain for $\Delta_{0}$ in $\Delta$. Let
$\tilde{\Gamma}=\Gamma/\Delta$, and let $\tilde{\Gamma}_{0}$ denote the image
of $\Gamma_{0}$ in $\tilde{\Gamma}$. Let $\tilde{D}$ be any fundamental domain
for $\tilde{\Gamma}$. Then the elements of $\tilde{D}$ are $\Delta$-cosets.
Let $D_{2}\subset\Gamma$ be a subset the contains exactly one representative
from each $\Delta$-coset in $\tilde{D}$. Then $D=D_{1}+D_{2}\subset\Gamma$ is
a fundamental domain for $\Gamma_{0}$, and $D$ is a disjoint union of
translates of $D_{0}$, thus satisfies the conclusion of the lemma. ∎

We denote the space of subgroups of $\Gamma$ by $\mathrm{Sub}(\Gamma)$. The
space $\mathrm{Sub}(\Gamma)$ admits a standard topology called the _Chabauty
topology_.

For a countable discrete groups $\Gamma$, by viewing $\mathrm{Sub}(\Gamma)$ as
a closed subset of $\\{0,1\\}^{\Gamma}$, the Chabauty topology can be
interpreted as the relative topology induced from the product topology on
$\\{0,1\\}^{\Gamma}$.

A basis for the Chabauty topology is given by sets of the form

$N(A,B)=\left\\{\Gamma_{0}\in\mathrm{Sub}(\Gamma)\leavevmode\nobreak\
:\leavevmode\nobreak\ \Gamma_{0}\cap B=A\right\\},\leavevmode\nobreak\
A\Subset B\Subset\Gamma.$

Thus, the statement $\lim_{n\to\infty}\Gamma_{n}=\Gamma_{0}$ means that for
any finite set $B\Subset\Gamma$ there exists $n_{0}\in\mathbb{N}$ such that
for any $n\geq n_{0}$ we have $\Gamma_{n}\cap B=\Gamma_{0}\cap B$.

###  2.2. Subshifts

######  Definition 2.10.

Let $A$ be a finite set. For $x\in A^{\Gamma}$ and $v\in\Gamma$, we denote the
value of $x$ at $v$ by $x_{v}$. Given $w\in\Gamma$ and $x\in A^{\Gamma}$ let
$\sigma_{w}(x)\in A^{\Gamma}$ be given by $\sigma_{w}(x)_{v}=x_{v+w}$ for
every $v\in\Gamma$. This defines an action of $\Gamma$ on $A^{\Gamma}$ called
the _shift action_ 111Since in this paper we restrict to commutative groups
$\Gamma$, any left-action is also a right action, and the convention we chose
is both standard and simple. In the case of non-commutative groups (in
multiplcative notation), to get an action from the left one uses
$(\sigma_{g}(x))_{h}=x_{g^{-1}h}$.. We equip $A^{\Gamma}$ with the product
topology, where $A$ is given the discrete topology. This makes $A^{\Gamma}$ a
compact metrizable topological space. A _$\Gamma$ -subshift_ is a non-empty
closed shift-invariant subset of $A^{\Gamma}$ for some finite set $A$. In this
context, we refer to $A^{\Gamma}$ as the _$\Gamma$ -full-shift_ (or simply the
full-shift when $\Gamma$ is fixed) over the alphabet $A$. Given
$F\subseteq\Gamma$ and $x\in A^{\Gamma}$, we let $x_{F}\in A^{F}$ denote the
restriction of $x$ to $F$.

######  Definition 2.11.

Let $X\subseteq A^{\Gamma}$ be a $\Gamma$-subshift and $F\Subset\Gamma$ a
finite set. We denote

$\mathcal{L}_{F}(X):=\left\\{w\in A^{F}:\leavevmode\nobreak\ \exists x\in
X\mbox{ s.t. }x_{F}=w\right\\}.$

The elements of $\mathcal{L}_{F}(X)$ are called _$X$ -admissible
$F$-patterns_.

######  Definition 2.12.

For $x\in A^{\Gamma}$, the _stablizer_ of $x$ is given by

$\mathit{stab}(x)=\\{v\in\Gamma:\leavevmode\nobreak\ \sigma_{v}(x)=x\\}.$

Clearly, $\mathit{stab}(x)$ is a subgroup of $\Gamma$.

######  Definition 2.13.

Given a $\Gamma$-subshift $X$ and a subgroup $\Gamma_{0}\leq\Gamma$ let

$X_{[\Gamma_{0}]}=\left\\{x\in X\leavevmode\nobreak\ :\leavevmode\nobreak\
\Gamma_{0}\leq\mathit{stab}(x)\right\\}.$

and

$X_{\Gamma_{0}}=\begin{cases}X_{[\Gamma_{0}]}&\mbox{ if
}[\Gamma:\Gamma_{0}]=\infty\\\ \left\\{x\in X\leavevmode\nobreak\
:\leavevmode\nobreak\ \mathit{stab}(x)=\Gamma_{0}\right\\}&\mbox{ if
}[\Gamma:\Gamma_{0}]<\infty.\end{cases}$

######  Definition 2.14.

Given a $\Gamma$-subshift $X\subseteq A^{\Gamma}$ and a subgroup
$\Gamma_{0}<\Gamma$ let
$\overline{X}_{[\Gamma_{0}]},\overline{X}_{\Gamma_{0}}\subseteq\overline{A}^{\Gamma/\Gamma_{0}}$
denote the natural images of $X_{[\Gamma_{0}]}$ and $X_{\Gamma_{0}}$
respectively. Namely,

$\overline{X}_{[\Gamma_{0}]}=\left\\{\overline{x}\in
A^{\Gamma/\Gamma_{0}}\leavevmode\nobreak\ :\leavevmode\nobreak\ \exists x\in
X_{[\Gamma_{0}]}\mbox{ s.t.
}x_{v}=\overline{x}_{v+\Gamma_{0}}\leavevmode\nobreak\ \forall
v\in\Gamma\right\\}$

and

$\overline{X}_{\Gamma_{0}}=\left\\{\overline{x}\in
A^{\Gamma/\Gamma_{0}}\leavevmode\nobreak\ :\leavevmode\nobreak\ \exists x\in
X_{\Gamma_{0}}\mbox{ s.t.
}x_{v}=\overline{x}_{v+\Gamma_{0}}\leavevmode\nobreak\ \forall
v\in\Gamma\right\\}.$

It is clear that both $\overline{X}_{\Gamma_{0}}^{*}$ and
$\overline{X}_{\Gamma_{0}}$ are closed $(\Gamma/\Gamma_{0})$-invariant sets,
and that there are continuous bijections
$\overline{X}_{\Gamma_{0}}\leftrightarrow X_{\Gamma_{0}}$ and
$\overline{X}_{\Gamma_{0}}^{*}\leftrightarrow X_{\Gamma_{0}}^{*}$ . Thus,
$\overline{X}_{\Gamma_{0}}$ and $\overline{X}_{\Gamma_{0}}^{*}$ are
$(\Gamma/\Gamma_{0})$-subshifts whenever they are non-empty.

######  Definition 2.15.

Given a $\Gamma$-subshift $X$, let

$\mathit{Ker}(X)=\\{v\in\Gamma\leavevmode\nobreak\ :\leavevmode\nobreak\
\sigma_{v}(x)=x\mbox{ for every }x\in X\\}.$

Equivalently,

$\mathit{Ker}(X)=\bigcap_{x\in X}\mathit{stab}(x).$

The action of $\Gamma$ on $X$ is called _faithful_ if $\mathit{Ker}(X)$ is
equal to the trivial subgroup.

######  Definition 2.16.

Let $W\Subset\Gamma$ be finite set, and let $\mathcal{F}\subset A^{W}$ be a
set of $W$-patterns. We say that a pattern $w\in A^{W}$ _occurs_ in $x\in
A^{\Gamma}$ at $v\in\Gamma$ if $\sigma_{v}(x)_{W}=w$.

######  Definition 2.17.

$\Gamma$-subshift $Y\subseteq A^{\Gamma}$ is call a _subshift of finite type
(SFT)_ if there exists a finite set $W\Subset\Gamma$ and a set of patterns
$\mathcal{F}\subset A^{W}$ such that

$Y=\\{y\in A^{\Gamma}\leavevmode\nobreak\ :\leavevmode\nobreak\
\sigma_{v}(y)_{W}\not\in\mathcal{F}\\}.$

In this case we say that $\mathcal{F}\subset A^{W}$ is a _defining set of
forbidden patterns for $Y$_.

For a given shift of finite type $Y\subseteq A^{\Gamma}$ is possible to find
many different sets $W_{1}\Subset\Gamma$ and $\mathcal{F}_{1}\subseteq
A^{W_{1}}$ such that $\mathcal{F}_{1}$ is a defining set of forbidden patterns
for $Y$.

######  Definition 2.18.

Given a finite set $W_{0}\Subset\Gamma$, a function $\Phi:A^{W_{0}}\to B$ and
another set $E\subseteq\Gamma$ let $\Phi^{E}:A^{W_{0}+E}\to B^{E}$ be given by

$\Phi^{E}(x)_{v}=\Phi(\sigma_{v}(x)_{W_{0}}).$

######  Definition 2.19.

Let $\rho:X\to Y$ be map between $\Gamma$-subshifts $X\subseteq A^{\Gamma}$,
$Y\subseteq B^{\Gamma}$. A finite set $W\Subset\Gamma$ is a _coding window_
for $\rho$ if there exists a function $\Phi:A^{W}\to B$ such that
$\rho(x)_{0}=\Phi(x_{W})$ for all $x\in X$. In this case we say that $\Phi$ is
a _sliding block code_ for $\rho$.

From the definition of the product topology, any map $\rho:X\to Y$ admits a
coding window and a sliding block code. This basic fact is known as the
_Curtis-Hedlund-Lyndon Theorem_. As in the case of defining set of forbidden
patterns for a subshift of finite type, there is no uniqueness: A map
$\rho:X\to Y$ can admit many different coding windows and many different
sliding block codes.

######  Definition 2.20.

Let $\rho:X\to Y$ be a map between subshifts $X\subseteq A^{\Gamma}$ and
$Y\subseteq B^{\Gamma}$, and let $\Phi:A^{W}\to B$ be a sliding block code for
$\rho$. We say that a finite set $W_{0}\Subset\Gamma$ is an _injectivity
window_ for $\rho$ if for any $w^{(1)},w^{(2)}\in\mathcal{L}_{W+W_{0}}(X)$
such that $w{(1)}_{0}\neq w^{(2)}_{0}$ there exist $v\in W_{0}$ such that
$\Phi^{W_{0}}(w^{(1)})_{v}\neq\Phi^{W_{0}}(w^{(2)})_{v}$.

By a standard compactness argument, a map $\rho:X\to Y$ is injective iff and
only if it admits a finite injectivity coding window.

######  Definition 2.21 (Topological entropy for subshifts).

Let $X$ be a $\Gamma$-subshift The topological entropy of $X$, denoted by
$h(X)$ is given by

$h(X)=\lim_{n\to\infty}\frac{1}{|F_{n}|}\log(|\mathcal{L}_{F_{n}}(X)|),$

For convenience, we denote

$h(\emptyset)=-\infty.$

where $(F_{n})_{n=1}^{\infty}$ is any Følner sequence in $\Gamma$.

The existence of the limit (which is acutally an infimum), and the fact that
it does not depend on the choice of Følner sequence are well-know.

A simpler, equivalent definition is the following:

$h(X)=\inf_{F\Subset\Gamma}\frac{1}{|F|}\log(|\mathcal{L}_{F}(X)|),$

where the infimum is over all finite subsets of $\Gamma$.

The equivalence of these definitions can be obtained from the following lemma,
which we will use subsequently:

######  Lemma 2.22.

For any $\epsilon>0$ there exists $\delta>0$ and a finite set $W\Subset\Gamma$
such that for any $(W,\delta)$-invariant set $F\Subset\Gamma$ the following
inequality holds:

$\log|\mathcal{L}_{F}(X)|\geq(1-\epsilon)|F|h(X).$

A short proof of this lemma can be obtained using Shearer’s inequality. See
[11], for instance.

The topological entropy of a subshift is invariant under isomorphism.
Furthermore, if $\rho:X\to Y$ is a map, then $h(\rho(X))\leq h(X)$.

It can be easily verified that for any $\Gamma_{0}\leq\Gamma$ and any
$\Gamma$-subshift $X$ we have:

$h(\overline{X}_{\Gamma_{0}})=\inf\left\\{\frac{1}{|K|}\log\left|\mathcal{L}_{K}(X_{\Gamma_{0}})\right|\leavevmode\nobreak\
:\leavevmode\nobreak\ K\Subset\Gamma\leavevmode\nobreak\ ,\leavevmode\nobreak\
\Gamma_{0}\mbox{ is }K\mbox{-separated}\right\\}$

and

$h(\overline{X}_{[\Gamma_{0}]})=\inf\left\\{\frac{1}{|K|}\log\left|\mathcal{L}_{K}(X_{[\Gamma_{0}]})\right|\leavevmode\nobreak\
:\leavevmode\nobreak\ K\Subset\Gamma\leavevmode\nobreak\ ,\leavevmode\nobreak\
\Gamma_{0}\mbox{ is }K\mbox{-separated}\right\\}.$

Note that when $\Gamma$ is a finite group and $X$ is a $\Gamma$-subshift, we
have

$h(X)=\frac{1}{|\Gamma|}\log|X|.$

The following result is probably folklore, we include it for completeness.

######  Proposition 2.23.

Let $X$ be a $\Gamma$-subshift. Then

$\limsup_{\Gamma_{0}\to\\{0_{\Gamma}\\}}h(\overline{X}_{[\Gamma_{0}]})\leq
h(X).$

###### Proof.

We need to prove that for every $\epsilon>0$ there exists a finite set
$K\Subset\Gamma$ such that for any $K$-separated subgroup $\Gamma_{0}<\Gamma$
it holds that $h(\overline{X}_{\Gamma_{0}})\leq h(X)+\epsilon$. Fix
$\epsilon>0$. Since
$h(X)=\inf_{K\Subset\Gamma}\frac{1}{|K|}\log|\mathcal{L}_{K}(X)|$, there
exists $K\Subset\Gamma$ such that

$\frac{1}{|K|}\log|\mathcal{L}_{K}(X)|\leq h(X)+\epsilon.$

Let $\Gamma_{0}\leq\Gamma$ be any $K$-separated subgroup. Then

$h(\overline{X}_{[\Gamma_{0}]})\leq\frac{1}{|K|}\log|\mathcal{L}_{K}(X_{[\Gamma_{0}]})|.$

Since $\mathcal{L}(X_{[\Gamma_{0}]})\subseteq\mathcal{L}(X)$, we have that

$\frac{1}{|K|}\log|\mathcal{L}_{K}(X_{[\Gamma_{0}]})|\leq\frac{1}{|K|}\log|\mathcal{L}_{K}(X)|,$

so

$h(\overline{X}_{[\Gamma_{0}]})\leq h(X)+\epsilon.$

∎

In the classical case $\Gamma=\mathbb{Z}$, Proposition 2.23 coincides with the
well-known fact that for any $\mathbb{Z}$-subshift $X$ the number of points
with period at most $n$ is bounded above by $e^{nh(X)+o(n)}$ as $n\to\infty$.

We introduce some specific notation to avoid repetition of the conditions that
appear in the statement of Theorem 1.4:

######  Definition 2.24.

Given $\Gamma$-subshifts $X,Y$, a closed $\Gamma$-invariant $Z\subseteq X$, an
injective map $\hat{\rho}:Z\to Y$ and $\Gamma_{0}\leq\Gamma$, we use the
notation $X\hookrightarrow_{\hat{\rho}}Y$ to indicate that $\hat{\rho}$
extends to an embedding of $X$ into $Y$, and use the notation
$X\cong_{\hat{\rho}}Y$ to indicate that $\hat{\rho}$ extends to an isomorphism
of $X$ and $Y$. We write $E(X,Y,\hat{\rho},\Gamma_{0})$ to indicate that
either $h(\overline{X}_{\Gamma_{0}})<h(\overline{Y}_{\Gamma_{0}})$ and
$\mathit{Ker}(Y_{\Gamma_{0}})\leq\mathit{Ker}(X_{\Gamma_{0}})$ or
$X_{\Gamma_{0}}\cong_{\hat{\rho}}Y_{\Gamma_{0}}$.

##  3\. Markers in the domain: Krieger’s Marker Lemma

In this section we state and prove a version of Krieger’s Marker Lemma that
applies to $\Gamma$-subshifts, where $\Gamma$ is a countable abelian group
(Lemma 3.3). Krieger’s original lemma is stated for $\mathbb{Z}$-subshifts
[16, Lemma 2]. Many variants of this lemma can be found in the literature, for
instance [14, Lemma $3.4$], [13, Lemma 2.1] and [20, Lemma 3.2], all with very
similar proofs. The main reason that we reprove the lemma here is that our
formulation of Lemma 3.3 involves a detailed treatment of non-free actions (a
slightly different treatment of non-free actions appears in [20, Lemma 3.2]).
We only deal here with abelian groups purely for simplicity of notation, to
maintain consistency of notation with the rest of the paper: Using suitable
(multiplicative) notion, Krieger’s marker lemma is valid for any action of a
countable groups on a compact zero dimensional space, essentially with the
same proof as our proof of Lemma 3.3 below.

######  Definition 3.1.

Let $X$ be a $\Gamma$-subshift and let $P\subset\Gamma\setminus\\{0\\}$ be a
finite set. We say that $A\subset X$ is a _$P$ -marker_ if

$A\cap\sigma_{\gamma}(A)=\emptyset,\mbox{ for all }\gamma\in P.$

The following basic lemma says that markers can be effectively merged:

######  Lemma 3.2.

Suppose that $X$ is a $\Gamma$-subshift and that
$P\subset\Gamma\setminus\\{0\\}$ is finite and symmetric. Suppose
$A,B\subseteq X$ are clopen $P$-markers. Then there exists a clopen $P$-marker
$C\subseteq X$ such that $A\cup B\subseteq C\cup\bigcup_{\gamma\in
P}\sigma_{\gamma}C$ and $C\subseteq(A\cup B)$.

###### Proof.

Let

$C:=A\cup\left(B\setminus\bigcup_{\gamma\in P}\sigma_{\gamma}(A)\right).$

Clearly, $C\subseteq(A\cup B)$. The set $C$ is clopen because it is contained
in the Boolean algebra spanned by
$\\{A,B\\}\cup\\{\sigma_{\gamma}(A):\gamma\in P\\}$. It is clear that
$A\subseteq C$. Thus

Also, if $x\in B\setminus\left(C\cup\bigcup_{\gamma\in
P}\sigma_{\gamma}(C)\right)$ then in particular $x\not\in C$ so
$x\in\sigma_{\gamma}(A)$ for some $\gamma\in P$. But since $A\subseteq C$, it
follows that $\gamma A\subseteq\gamma C$, so $x\in\gamma A\setminus\gamma
A=\sigma_{\gamma}\partial A$, which is impossible. This shows that $B\subseteq
C\cup\bigcup_{\gamma\in P}\sigma_{\gamma}(C)$.

It remains to check that $C$ is a $P$-marker. For any $\gamma\in P$ we have:

$C\subseteq A\cup\left(B\cap\sigma_{\gamma}(A^{c})\right)$

Because $P$ is symmetric also $-\gamma\in P$ so

$C\subseteq A\cup\left(B\cap\sigma_{\gamma}^{-1}A^{c}\right).$

Applying $\sigma_{\gamma}$ to both sides, we get:

$\sigma_{\gamma}(C)\subseteq\sigma_{\gamma}(A)\cup\left(\sigma_{\gamma}(B)\cap
A^{c}\right)$

It follows that $C\cap\sigma_{\gamma}C$ is contained in the union of the
following $4$ sets:

  1. (1)

$E_{1}:=A\cap\sigma_{\gamma}A$,

  2. (2)

$E_{2}:=A\cap\left(\sigma_{\gamma}B\cap A^{c}\right)$,

  3. (3)

$E_{3}:=\left(B\cap\sigma_{\gamma}A^{c}\right)\cap\sigma_{\gamma}A$,

  4. (4)

$E_{4}:=\left(B\cap\sigma_{\gamma}A^{c}\right)\cap\left(\sigma_{\gamma}B\cap
A^{c}\right)$.

By assumption $A$ is an $F$-marker so, $E_{1}\ =\emptyset$. Clearly,
$E_{2}\subseteq A\cap(A^{c})=\emptyset$ and
$E_{3}\subseteq\sigma_{\gamma}(A^{c})\cap g(A)=\emptyset$. Also,
$E_{4}\subseteq B\cap\sigma_{\gamma}(B)=\emptyset$ by assumption that $B$ is a
$P$-marker. This shows that $C\cap\sigma_{\gamma}C=\emptyset$ for all
$\gamma\in P$. ∎

######  Lemma 3.3 (Krieger’s Marker Lemma for $\Gamma$-subshifts).

Let $X$ be a $\Gamma$-subshift. Let $P\Subset\Gamma\setminus\\{0\\}$ be a
finite symmetric set, and let $V\subseteq X$ be a clopen set such that
$\sigma_{\gamma}(x)\neq x$ for every $\gamma\in P$ and every $x\in V$. Then
there exists a clopen set $C\subseteq V$ so that

$C\cap\sigma_{\gamma}(C)=\emptyset\mbox{ for every }\gamma\in P\mbox{ and
}V\subseteq C\cup\bigcup_{\gamma\in P}\sigma_{\gamma}(C).$ (1)

###### Proof.

For every $x\in V$ and $\gamma\in P$ we have that $x\neq g(x)$. We can thus
find for every $x\in V$ a clopen set $E_{x}\subseteq V$ such that $x\in E_{x}$
and $E_{x}\cap g(E_{x})=\emptyset$ for every $g\in P$ (that is $E_{X}$ is a
$P$-marker).

Since $V$ is compact, we can find a finite subcover
$\mathcal{U}=\\{D_{1},\ldots,D_{n}\\}$ of $\\{E_{x}:\leavevmode\nobreak\ x\in
V\\}$. Thus each $D_{j}\subseteq V$ is a clopen $P$-marker and
$V\subseteq\bigcup_{j=1}^{n}D_{j}$. By induction we construct clopen
$P$-markers $C_{1},\ldots,C_{n}\subseteq V$ such that
$\bigcup_{k=1}^{j}D_{k}\subseteq C_{j}\bigcup_{\gamma\in P}g(C_{j})$. To start
the induction, let $C_{1}=D_{1}$. For the induction step, apply Lemma 3.2 with
$A:=D_{j-1}$ and $B:=D_{j}$ to obtain a clopen $P$-marker $C_{j}$ such that
$A\cup B\subseteq U_{j}\bigcup_{\gamma\in P}\sigma_{\gamma}(U_{j})$. Then
$C=C_{n}$ is a clopen set that satisfies the conclusion of the lemma. ∎

As mentioned in the beining of this section, an inspection of the proof of
Lemma 3.2 and Lemma 3.3 reveals that commutatitivity of the group $\Gamma$ is
not used in the proof, except for notational purposes. Also, the fact that $X$
is a $\Gamma$-subshift rather than a general compact $\Gamma$-space is only
used to produce a clopen basis. In other words, expansiveness of the action is
never used. Thus, the proof of Lemma 3.3 directly extends to the following
(mentioned for future reference, the generality will not be used in the
current paper):

######  Lemma 3.4 (Krieger’s Marker Lemma for countable groups).

Let $\Gamma\curvearrowright X$ be an action of a countable group $\Gamma$ on a
totally disconnected compact metric space. Let $P\Subset\Gamma$ be a finite
symmetric set with $1_{\Gamma}\not\in P$, and let $V\subseteq X$ be a clopen
set such that $g(x)\neq x$ for every $g\in P$ and every $x\in V$. Then there
exists a clopen set $C\subseteq V$ so that

$C\cap g(C)=\emptyset\mbox{ for every }g\in P\mbox{ and }V\subseteq
C\cup\bigcup_{g\in P}g(C).$ (2)

As mentioned in the earlier, closely related statements have already appeared
in the literature.

##  4\. Retractions and the map extension property for subshifts

In this section we introduce the _map extension property_ for
$\Gamma$-subshifts, and the notion of an _absolute retract_. Both of these
properties make sense in the category of general topological dynamical
systems, and also in other categories. In topology the notion of an absolute
retract has been introduced by Borsuk in the 1930’s, see [19]. We show that a
$\Gamma$-subshift has the map extension property if and only if it is an
absolute retract for a certain class of subshifts. A $\mathbb{Z}$-subshift has
the map extension property if and only if it is a topologically mixing
subshift of finite type.

######  Definition 4.1.

Let $X,Y$ be $\Gamma$-subshifts. We write $X\rightsquigarrow Y$ if the
following holds: For every $x\in X$ there exists $y\in Y$ such that
$\mathit{stab}(x)<\mathit{stab}(y)$.

The condition $X\rightsquigarrow Y$ is a obviously a necessary condition for
the existence of map from $X$ into $Y$. Indeed, if there exists a map
$\pi:X\to Y$ then $X\rightsquigarrow Y$ because for any $x\in X$ we have
$\mathit{stab}(x)\leq\mathit{stab}(\pi(x))$.

######  Definition 4.2.

A $\Gamma$-subshift $Y$ has the _map extension property_ if:

  1. (1)

For every $\Gamma$-subshift $X$ is a such that $X\rightsquigarrow Y$ and any
map $\tilde{\pi}:\tilde{X}\to Y$ from a closed, $\Gamma$-invariant set
$\tilde{X}\subseteq X$ there exists a map $\pi:X\to Y$ that extends
$\tilde{\pi}$.

  2. (2)

There exists a finite set $\mathcal{G}\Subset\mathrm{Sub}(\Gamma)$ such that
for every $\Gamma_{0}\leq\Gamma$ either there exists $y\in Y$ with
$\Gamma_{0}\leq\mathit{stab}(y)$ or there exists $\Gamma_{1}\in\mathcal{G}$
such that $\Gamma_{1}\leq\Gamma_{0}$.

Let $X$ be a topological space. A subspace $Y\subseteq X$ is called a
_retract_ if there is a continuous function $r:X\to Y$ such that the
restriction of $r$ to $Y$ is the identity. Such a continuous function $r:X\to
Y$ is called a retraction. Let $\mathcal{C}$ be a class of topological spaces,
closed under homeomorphisms and passage to closed subsets. Following Borsuk, a
topological space is $Y$ is called an absolute retract for the class
$\mathcal{C}$ if $Y\in\mathcal{C}$ and whenever $Y$ is a closed subspace of
$X\in\mathcal{C}$ then $Y$ is a retract of $X$.

The notions of a retract and universal retract naturally adapt to the category
of dynamical systems, in particular to $\Gamma$-subshifts:

######  Definition 4.3.

Let $Y\subseteq X$ be $\Gamma$-subshifts. We say that $Y$ is a retract of $X$
if there exists a map $r:X\to Y$ such that the restriction of $r$ to $Y$ is
the identity. A map $r$ as above is called a retraction.

######  Definition 4.4.

A $\Gamma$-subshift $Y$ is called an _absolute retract_ if whenever $Y$ embeds
in a $\Gamma$-subshift $X$, then $Y$ is a retract of $X$.

######  Definition 4.5.

Let $\mathcal{C}$ be a class of $\Gamma$-subshifts, closed under isomorphism
and passing to subshift. A $\Gamma$-subshift $Y$ is called an _absolute
retract for the class $\mathcal{C}$_ if $Y\in\mathcal{C}$ and whenever $Y$
embeds in a $\Gamma$-subshift $X\in\mathcal{C}$ then $Y$ is a retract of $X$.

An absolute retract always has a fixed point for the following simple reason:
Any subshift $Y$ embeds in a subshift with a fixed point, and any retract of a
subshift with a fixed point must admit a fixed point.

######  Definition 4.6.

Given a finite set $\mathcal{G}\Subset\mathrm{Sub}(\Gamma)$ we say that a
$\Gamma$-subshift $X$ is _$\mathcal{G}$ -free_ if for every $x\in X$ and
$\Gamma_{0}\in\mathcal{G}$ we have that
$\Gamma_{0}\not\subseteq\mathit{stab}(x)$.

######  Definition 4.7.

Let $Y$ be a $\Gamma$-subshift, and let $\mathcal{G}$ be a finite set of
finitely generated subgroups of $\Gamma$. We say that a finite set
$K\Subset\Gamma$ _witnesses that $Y$ is $\mathcal{G}$-free_ if each
$\Gamma_{0}\in\mathcal{G}$ admits a finite generating set
$F_{\Gamma_{0}}\Subset\Gamma$ so that for every $w\in\mathcal{L}_{K}(Y)$ and
every $\Gamma_{0}\in\mathcal{G}$ there exists $\gamma\in F_{\Gamma_{0}}$ and
$v\in K$ such that $v+\gamma\in K$ and $w_{v}\neq w_{v+\gamma}$.

######  Lemma 4.8.

Let $\mathcal{G}\Subset\mathrm{Sub}(\Gamma)$ be a finite set of finitely
generated subgroups of $\Gamma$, and let $Y$ be a $\Gamma$-subshift. Then $Y$
is $\mathcal{G}$-free if and only if there exists a finite set
$K\Subset\Gamma$ with $0\in K$ that witnesses that $Y$ is $\mathcal{G}$-free.

###### Proof.

If $K\Subset\Gamma$ witnesses that $Y$ is $\mathcal{G}$-free then each
$\Gamma_{0}\in\mathcal{G}$ admits a finite generating set
$F_{\Gamma_{0}}\Subset\Gamma$ so that for every $y\in Y$ and every
$\Gamma_{0}\in\mathcal{G}$ there exists $v\in K$ and $\gamma\in
F_{\Gamma_{0}}$ such that $y_{v}\neq y_{v+\gamma}$, and so
$\Gamma_{0}\not\subseteq\mathit{stab}(y)$. This proves that $Y$ is
$\mathcal{G}$-free.

For the converse direction: For each $\Gamma_{0}\in\mathcal{G}$, fix a finite
generating set $F_{\Gamma_{0}}\Subset\Gamma$. Given $K\Subset\Gamma$ say that
$w\in\mathcal{L}_{K}(Y)$ is _$F_{\Gamma_{0}}$ -periodic_ if
$w_{v}=w_{v+\gamma}$ whenever $\gamma\in F_{\Gamma_{0}}$, and $v,v+\gamma\in
K$. Suppose that $Y$ is $\mathcal{G}$-free. Then for any $y\in Y$ and every
$\Gamma_{0}\in\mathcal{G}$ there exists a finite set
$K{y,\Gamma_{0}}\Subset\Gamma$ such that $y_{K}$ is not $F_{\Gamma_{0}}$
periodic. Take $K_{y}=\bigcup_{\Gamma_{0}\in\mathcal{G}}K_{y,\Gamma_{0}}$,
then $y_{K}$ is not $F_{\Gamma_{0}}$ periodic for all
$\Gamma_{0}\in\mathcal{G}$. For each $y\in Y$ let

$U_{y}=\left\\{\tilde{y}\in Y\leavevmode\nobreak\ :\leavevmode\nobreak\
\tilde{y}_{K_{y}}=y_{K_{y}}\right\\}.$

Then $U_{y}\subseteq Y$ is an open neighborhood of $y$. By compactness of $Y$
there exists a finite sub-cover $U_{y_{1}},\ldots,U_{y_{N}}$. Let
$K=\bigcup_{j=1}^{N}K_{y_{j}}$, then for every $y\in Y$ we have that $y_{K}$
is not $F_{\Gamma_{0}}$ periodic for all $\Gamma_{0}\in\mathcal{G}$. This
proves that $K$ witnesses that $Y$ is $\mathcal{G}$-free. ∎

######  Definition 4.9.

Given a $\Gamma$-subshift $Y\subseteq A^{\Gamma}$ and finite non-empty sets
$K,D\Subset\Gamma$ let

$Y^{(K,D)}=\left\\{y\in A^{\Gamma}\leavevmode\nobreak\ :\leavevmode\nobreak\
\forall v\in\Gamma\;\exists w\in D\mbox{ s.t.
}\sigma_{v+w}(y)_{K}\in\mathcal{L}_{K}(Y)\right\\}.$

######  Lemma 4.10.

Let $\mathcal{G}\Subset\mathrm{Sub}(\Gamma)$ be a finite set of finitely
generated subgroups, let $Y\subseteq A^{\Gamma}$ be $\mathcal{G}$-free
subshift, and let $K\Subset\Gamma$ be a finite set that witnesses that $Y$ is
$\mathcal{G}$-free. For any non-empty finite set $D\Subset\Gamma$, the
subshift $Y^{(K,D)}$ is a $\mathcal{G}$-free subshft such that $Y\subseteq
Y^{(K,D)}$.

###### Proof.

It is clear that $Y\subseteq Y^{(K,D)}$, because for any $y\in Y$ and any
$v\in\Gamma$ and $w\in D$ we have that
$\sigma_{v+w}(y)_{K}\in\mathcal{L}_{K}(Y)$. Because $K$ witness that $Y$ is
$\mathcal{G}$-free, it follows that $D+K$ witnesses that $Y^{(K,D)}$ is
$\mathcal{G}$-free. ∎

We proceed with some technical lemmas that will eventually be used to
establish significant properties for subshifts with the map extension
property, eventually used in the proof of the main theorem:

######  Lemma 4.11.

Let $\mathcal{G}\Subset\mathrm{Sub}(\Gamma)$ be a finite set of finitely
generated subgroups. Suppose that $Y$ is a $\mathcal{G}$-free
$\Gamma$-subshift, that $\tilde{X}$ is either a $\mathcal{G}$-free
$\Gamma$-subshift or $\tilde{X}=\emptyset$, and and that
$\tilde{\pi}:\tilde{X}\to Y$ is a map. Then there exists a finite set
$K\Subset\Gamma$ and $\mathcal{G}$-free subshift $\hat{Y}$ with
$Y\subseteq\hat{Y}$, so that for any $\mathcal{G}$-free $\Gamma$-subshift $X$
such that $\tilde{X}\subseteq X$ there exists a map $\pi:X\to\hat{Y}$ that
extends $\tilde{\pi}$ and so that $\pi(x)_{0}=\tilde{\pi}(x)_{0}$ for any
$x\in X$ such that $x_{K}\in\mathcal{L}_{K}(\tilde{X})$.

###### Proof.

Let $\mathcal{G}$, $\tilde{X}$, $Y$ and $\tilde{\pi}:\tilde{X}\to Y$ be as in
the statement of the lemma. Choose a finite symmetric generating set
$F_{\Gamma_{0}}\Subset\Gamma$ for each $\Gamma_{0}\in\mathcal{G}$. By Lemma
4.8 there exists a finite set $K_{0}\Subset\Gamma$ with $0\in K_{0}$ that
witnesses that $Y$ is $\mathcal{G}$-free. Let

$P=\bigcup_{\Gamma_{0}\in\mathcal{G}}F_{\Gamma_{0}},$

and let $\mathcal{Q}$ denote the collection of symmetric subsets $Q\subseteq
P$ that satisfy $Q\cap(\Gamma_{0}\setminus\\{0\\})\neq\emptyset$ for all
$\Gamma_{0}\in\mathcal{G}$. We are about to define a $\Gamma$-subshift
$\hat{Y}\subseteq\hat{A}^{\Gamma}$ and a map $\pi:X\to\hat{Y}$ that satisfy
the properties in the statement of the lemma. Let us first define the
“alphabet” $\hat{A}$:

$\hat{A}=A\uplus\mathcal{Q}\uplus\\{\hat{a}\\},$

where $Y\subseteq A^{\Gamma}$.

We regard the finite set $\mathcal{Q}$ as another alphabet disjoint for $A$,
and $\hat{a}$ as a new “symbol” not contained in $A$ or in $\mathcal{Q}$.

Let $W\Subset\Gamma$ be a coding window for $\tilde{\pi}$, and let
$K=K_{0}+W$.

Let $\hat{Y}\subseteq\hat{A}^{\Gamma}$ be the subshift defined by the
following constraints: For every $y\in\tilde{Y}$ and any $v\in\Gamma$:

  1. (1)

There exists $u\in K_{0}$ such that either
$\sigma_{v-u}(y)_{K_{0}}\in\mathcal{L}_{K_{0}}(Y)$ or there exists
$Q\in\mathcal{Q}$ and $\gamma\in Q\cup\\{0\\}$ such that
$\sigma_{v-u+\gamma}(y)=Q$.

  2. (2)

If $y_{v}=Q\in\mathcal{Q}$ then for every $\gamma\in Q$ we have that
$y_{v+\gamma}\neq Q$.

If $y\in Y$ then for every $v\in\Gamma$ and every $u\in K_{0}$ we have that
$\sigma_{v-u}(y)_{K_{0}}\in\mathcal{L}_{K_{0}}(Y)$, and $y_{v}\not\in Q$, so
$y\in\hat{Y}$. This shows that $Y\subseteq\hat{Y}$. Let us prove that
$\hat{Y}$ is $\mathcal{G}$-free: Given $y\in\hat{Y}$ and
$\Gamma_{0}\in\mathcal{G}$, we need to show that
$\Gamma_{0}\not\leq\mathit{stab}(y)$. Consider an arbitrary point
$y\in\hat{Y}$. If there exists $v\in\Gamma$ such that
$\sigma_{v}(y)_{K_{0}}\in\mathcal{L}_{K_{0}}(Y)$, then
$\Gamma_{0}\not\leq\mathit{stab}(y)$ for any $\Gamma_{0}\in\mathcal{G}$,
because $Y$ is $\mathcal{G}$-free. Otherwise, there exists $v\in\Gamma$ and
$Q\in\mathcal{Q}$ such that $\sigma_{v}(y)=\xi(Q)$. In this case for every
$\gamma\in Q$ we have $y_{v+\gamma}\neq y_{v}$, so $\mathit{stab}(y)\cap
Q=\emptyset$. Since $(\Gamma_{0}\setminus\\{0\\})\cap Q\neq\emptyset$ this
shows that $\Gamma_{0}\not\leq\mathit{stab}(y)$.

Let $X\subseteq B^{\Gamma}$ be a $\mathcal{G}$-free subshift such that
$\tilde{X}\subseteq X$. We will now describe a map $\pi:X\to\hat{Y}$ that
extends $Y$ and so that $\tilde{\pi}(x)_{0}=x_{0}$ for any $x\in X$ such that
$x_{K}\in\mathcal{L}_{K}(\tilde{X})$. As before, since $X$ is compact and
$\mathcal{G}$-free there exists a finite set $K_{1}\Subset\Gamma$ that
witnesses that $X$ is $\mathcal{G}$-free. For every $Q\in\mathcal{Q}$ let
$L_{Q}\subseteq B^{K_{1}}$ be the set of patterns $w\in B^{K_{1}}$ such that:

  * •

For every $\gamma\in Q$ there exists $v\in K_{1}$ such that $v+\gamma\in
K_{1}$ and $w_{v}\neq v_{v+\gamma}$.

  * •

For every $\gamma\in P\setminus Q$ and every $v\in K_{1}$ such that
$v+\gamma\in K_{1}$ we have $w_{v}=v_{v+\gamma}$.

The sets $\\{L_{Q}\\}_{Q\in\mathcal{Q}}$ are mutually disjoint and
$\mathcal{L}_{K_{1}}(X))\subseteq\biguplus_{Q\in\mathcal{Q}}L_{Q}$. For every
$Q\in\mathcal{Q}$ let $V_{Q}=\\{x\in X\leavevmode\nobreak\
:\leavevmode\nobreak\ x_{K_{1}}\in L_{Q}\\}$. Then $V_{Q}$ is a clopen set in
$X$. Furthermore for every $x\in V_{Q}$ and every $\gamma\in Q$ we have
$\sigma_{\gamma}(x)\neq x$. By Lemma 3.3 there exists a clopen set
$C_{Q}\subseteq V_{Q}$ such that

$C_{Q}\cap\sigma_{\gamma}(C_{Q})=\emptyset\mbox{ for every }\gamma\in Q\mbox{
and }V_{Q}\subseteq C_{Q}\cup\bigcup_{\gamma\in Q}\sigma_{\gamma}(C_{Q}).$

Define a map $\pi:X\to\hat{Y}$ as follows:

$\pi(x)_{v}=\begin{cases}\tilde{\pi}(\sigma_{v}(x))_{0}&\mbox{ if }\exists
u\in K_{0}\mbox{ s.t. }\sigma_{v-u}(x)_{K}\in\mathcal{L}_{K}(\tilde{X})\\\
Q&\mbox{ if }\sigma_{v}(x)\in C_{Q}\mbox{ for some }Q\in\mathcal{Q}\mbox{ and
we are not in the previous case},\\\ \hat{a}&\mbox{ otherwise.}\end{cases}$

Notice that if there exists $u\in K_{0}$ such that
$\sigma_{v-u}(x)_{K}\in\mathcal{L}_{K}(X)$, then because $K=K_{0}+W$, it
follows that $\sigma_{v}(x)_{W}\in\mathcal{L}_{W}(\tilde{X})$ and so
$\tilde{\pi}(\sigma_{v}(x))_{0}$ is well defined, because $W$ is a coding
window for $\tilde{\pi}$. Moreover, if
$\sigma_{v}(x)_{K}\in\mathcal{L}_{K}(\tilde{X})$ then there exists
$\tilde{x}\in\tilde{X}$ such that such that
$\pi(x)_{K_{0}}=\tilde{\pi}(\tilde{x})_{K_{0}}$, and in particular
$\pi(x)_{0}=\tilde{\pi}(x)_{0}$. Since
$X\subseteq\bigcup_{Q\in\mathcal{Q}}V_{Q}$ and $V_{Q}\subseteq
C_{Q}\cup\bigcup_{\gamma\in Q}\sigma_{\gamma}(C_{Q})$ for every
$Q\in\mathcal{Q}$, it follows that for every $x\in X$ and $v\in\Gamma$, either
there exists $u\in K_{0}$ such that
$\sigma_{v-u}(x)_{K}\in\mathcal{L}_{K}(X)$, in which case
$\sigma_{v-u}(\pi(x))\in\mathcal{L}_{K_{0}}(Y)$ or there exists
$Q\in\mathcal{Q}$ and $\gamma\in Q\cup\\{0\\}$ such that
$\sigma_{v+\gamma}(\hat{\pi}(y))=Q$. We have thus shown that
$\pi(x)\in\hat{Y}$ for every $x\in X$, completing the proof. ∎

######  Lemma 4.12.

Let $\mathcal{G}\Subset\mathrm{Sub}(\Gamma)$ be a finite set of finitely
generated subgroups. Let $Y\subset A^{\Gamma}$ be an absolute retract for the
class of $\mathcal{G}$-free subshifts. Then there exists a finite set
$F\Subset\Gamma$ such that for any $\mathcal{G}$-free subshift $X$ with
$Y\subseteq X$ there exists a retraction $r:X\to Y$ such that for any $x\in
X$, if $x_{F}\in\mathcal{L}_{F}(Y)$ then $r(x)_{0}=x_{0}$.

###### Proof.

Let $\mathcal{G}\Subset\mathrm{Sub}(\Gamma)$ and $Y$ be as in the statement.
By applying Lemma 4.11 with $\tilde{X}=Y$ and $\tilde{\pi}$ equal to the
identity map we deduce that there exists a finite set $K\Subset\Gamma$ with
$0\in K$ and a $\mathcal{G}$-free subshift $\hat{Y}$ such that for any
$\mathcal{G}$-free subshift $X$ such that $Y\subseteq X$ there exists a map
$\pi:X\to\hat{Y}$ that extends the identity map on $Y$ and so that
$\pi(y)_{0}=y_{0}$ whenever $x\in X$ and $x_{K}\in\mathcal{L}_{K}(Y)$. Since
$Y$ is an absolute retract for the class of $\mathcal{G}$-free subshifts,
there exist a retraction map $\hat{r}:X\to Y$. Let $W\Subset\Gamma$ be a
coding window for $\hat{r}$ with $0\in W$. Let $F=W+K$ and let
$r=\hat{r}\circ\pi$. Then for any $x\in X$ such that
$x_{F}\in\mathcal{L}_{F}(Y)$ we have that $\pi(x)_{W}=x_{W}$ and so
$r(x)_{0}=\hat{r}(\pi(x))_{0}=x_{0}$. ∎

######  Lemma 4.13.

Let $Y\subseteq A^{\Gamma}$ be $\Gamma$-subshift, $K\Subset\Gamma$ a non-empty
symmetric set , $\Gamma_{0}\leq\Gamma$ a subgroup, and $F\subseteq\Gamma$.
Suppose that $F$ is $(K+\Gamma_{0})$-separated and that $\Gamma_{0}$ is
$K$-separated. Then for any function $p:F\to\mathcal{L}_{K}(Y)$ there exists
$y\in Y_{[\Gamma_{0}]}^{(K,K+K)}$ such that $\sigma_{v}(y)_{K}=p(v)$ for all
$v\in F$.

###### Proof.

Let $Y$, $\Gamma_{0}\leq\Gamma$ $K\Subset\Gamma$ and $F\subseteq\Gamma$ be as
in the statement. Since any $(K+\Gamma_{0})$-separated set is contained in a
maximal $(K+\Gamma_{0})$-separated, we assume without loss of generality that
$F$ is a maximal $(K+\Gamma_{0})$-separated set. Given a function
$p:F\to\mathcal{L}_{K}(Y)$ construct a point $y\in A^{\Gamma}$ as follows:

  * •

For each $v\in F$ and $\tilde{\gamma}\in\Gamma_{0}$ let
$\sigma_{v+\tilde{\gamma}}(y)_{K}=p(v)$. The collection of sets
$\\{v+\tilde{\gamma}+K\\}_{v\in F,\leavevmode\nobreak\
\tilde{\gamma}\in\Gamma_{0}}$ are pairwise disjoint because $F$ is
$(K+\Gamma_{0})$-separated and $\Gamma_{0}$ is $K$-separated. This defines the
restriction of $y$ to $F+\Gamma_{0}+K$.

  * •

Choose $y_{(\Gamma\setminus(F+\Gamma_{0}+K))}\in
A^{(\Gamma\setminus(F+\Gamma_{0}+K))}$ in any manner that satisfies
$y_{v}=y_{v+\gamma_{0}}$ for every $\gamma_{0}\in\Gamma_{0}$ and
$v\in\Gamma\setminus(F+\Gamma_{0}+K)$. For instance, we can choose a fixed
$a\in A$ and let $y_{v}=a$ for every $v\in\Gamma\setminus(F+\Gamma_{0}+K)$.
Note that if $v\in\Gamma\setminus(F+\Gamma_{0}+K)$ then
$v+\gamma_{0}\in\Gamma\setminus(F+\Gamma_{0}+K)$ for every
$\gamma_{0}\in\Gamma_{0}$), so there is no conflict with the previous
definition.

Since $F$ is a maximal $(K+\Gamma_{0})$-separated set, and
$\Gamma_{0}=\Gamma_{0}+\Gamma_{0}$, by Lemma 2.7 we have that
$\Gamma=F+K+K+\Gamma_{0}$. So for every $v\in\Gamma$ there exists $v_{1}\in
F$, $k\in K+K$ and $\gamma_{0}\in\Gamma_{0}$ such that $v=v_{1}+k+\gamma_{0}$
and so $\sigma_{v-k-\gamma_{0}}(y)_{K}=p(v)\in\mathcal{L}_{K}(Y)$. This proves
that $y\in Y^{(K,K+K)}$. Also, it is clear that $\sigma_{\gamma_{0}}(y)=y$ for
every $\gamma_{0}\in\Gamma_{0}$, so $y\in Y^{(K,K+K)}_{[\Gamma_{0}]}$. ∎

######  Lemma 4.14.

Let $\mathcal{G}\Subset\mathrm{Sub}(\Gamma)$ be a finite set of finitely
generated subgroups, and let $Y$ be an absolute retract for the class of
$\mathcal{G}$-free subshifts. Then there exist finite sets
$K_{0},F_{0}\Subset\Gamma$ so that for any subgroup $\Gamma_{0}\leq\Gamma$ and
any $\Gamma_{0}$-separated symmetric set $K\Subset\Gamma$ with $K_{0}\subseteq
K$, any $(K+\Gamma_{0})$-separated set $F\subseteq\Gamma$ and any function
$p:F\to\mathcal{L}_{(K\setminus\partial_{F_{0}}K)}(Y)$, there exists $y\in
Y_{[\Gamma_{0}]}$ such that
$\sigma_{v}(y)_{(K\setminus\partial_{F_{0}}K)}=p(v)$ for all $v\in F$.

###### Proof.

Let $Y$ be an absolute retract for the class of $\mathcal{G}$-free subshifts.
By Lemma 4.8, there exists a finite set $K_{0}\Subset\Gamma$ with $0\in K$
that witnesses that $Y$ is $\mathcal{G}$-free. Let $F_{0}\Subset\Gamma$ be a
finite set as given by Lemma 4.12, so that for any $\mathcal{G}$-free subshift
$\hat{Y}$ with $Y\subseteq\hat{Y}$ there exists a retraction $r:\hat{Y}\to Y$
such that for any $y\in\hat{Y}$ if $y_{F_{0}}\in\mathcal{L}_{F_{0}}(Y)$ then
$r(y)_{0}=y_{0}$. Let $\Gamma_{0}\leq\Gamma$ be a subgroup and let
$K\Subset\Gamma$ be a symmetric, $\Gamma_{0}$-separated set such that
$K_{0}\subseteq K$. Let $F\subseteq\Gamma$ be a $(K+\Gamma_{0})$-separated
set. Let $p:F\to\mathcal{L}_{(K\setminus\partial_{F_{0}}K)}(Y)$ be any
function. Choose a function $\hat{p}:F\to\mathcal{L}_{K}(Y)$ such that
$\hat{p}(v)_{(K\setminus\partial_{F_{0}}K)}=p(v)$ for every $v\in F$. By Lemma
4.13 there exists $\tilde{y}\in Y^{(K,K+K)}_{[\Gamma_{0}]}$ such that
$\sigma_{v}(\tilde{y})_{K}=\hat{p}(v)$ for every $v\in F$. By Lemma 4.10 the
subshift $Y^{(K,K+K)}$ is $\mathcal{G}$-free and $Y\subseteq Y^{(K,K+K)}$, so
there exists a retraction $r:Y^{(K,K+K)}\to Y$ such that for any $\hat{y}\in
Y^{(K,K+K)}$ if $\hat{y}_{F_{0}}\in\mathcal{L}_{F_{0}}(Y)$ then
$r(\hat{y})_{0}=y_{0}$. Let $y=r(\tilde{y})$. Since $\tilde{y}\in
Y^{(K,K+K)}_{[\Gamma_{0}]}$, it follows that $y\in Y_{[\Gamma_{0}]}$. Since
$\sigma_{v}(y)_{K}=\hat{p}(v)\in\mathcal{L}_{K}(Y)$ for every $v\in F$, it
follows that for every $v\in F$ we have

$\sigma_{v}(y)_{(K\setminus\partial_{F_{0}}K)}=\sigma_{v}(\hat{y})_{(K\setminus\partial_{F_{0}}K)}=p(v).$

∎

######  Lemma 4.15.

Let $\mathcal{G}\Subset\mathrm{Sub}(\Gamma)$ be a finite set of finitely
generated subgroups, and let $Y$ be an absolute retract for the class of
$\mathcal{G}$-free subshifts. Then there exist finite sets
$K_{0},F_{0}\Subset\Gamma$ such that for any finite set $K\Subset\Gamma$ , any
symmetric monotile $F\Subset\Gamma$ with $K_{0}\subseteq F$ and any
$K$-separated subgroup $\Gamma_{0}\leq\Gamma$ we have:

$\log\left|\mathcal{L}_{K}(Y_{[\Gamma_{0}]})\right|\geq\lfloor\frac{|K\setminus\partial_{(F+F)}K|}{|F|}\rfloor\log\left|\mathcal{L}_{F\setminus\partial_{F_{0}}F}(Y)\right|.$

###### Proof.

Let $Y\subseteq A^{\Gamma}$ be an absolute retract for the class of
$\mathcal{G}$-free subshifts, and let $K_{0},F_{0}\Subset\Gamma$ be as in
Lemma 4.14.

Let $F\Subset\Gamma$ be a symmetric monotile $F$ with $K_{0}\subseteq F$ , and
let $\Gamma_{0}\leq\Gamma$ be a $K$-separated subgroup. Because $F$ is a
monotile, there exists $A\subseteq\Gamma$ such that $\Gamma=F\oplus A$.

Let

$C=\\{a\in A\leavevmode\nobreak\ :\leavevmode\nobreak\ a+F\subseteq K\\},$

and let $N=|C|$. Because $\Gamma=F\oplus A$, it follows that
$(K\setminus\partial_{(F+F)})K\subseteq F\oplus C$, and so

$\left|K\setminus\partial_{(F_{n}+F_{n})}\right|\leq N|F|.$

So it suffices to prove that

$\log|\mathcal{L}_{K}(Y_{\Gamma_{0}})\geq|F|\log\left|\mathcal{L}_{(F\setminus\partial
F_{0}F)}(Y)\right|.$

If $C=\emptyset$, then $N=0$, and there is nothing to prove. So we assume that
$C\neq\emptyset$. We will prove the above inequality by constructing an
injective function
$f:\left(\mathcal{L}_{(F\setminus\partial_{F_{0}}F)}(Y)\right)^{F}\to\mathcal{L}_{K}(Y_{\Gamma_{0}})$:

Choose $v\in V$. So $v+F\subseteq K$, and in particular $v+K_{0}\subseteq K$.
By Lemma 4.14 and the choice of $K_{0},F_{0}$, for every
$p\in\left(\mathcal{L}_{(F\setminus\partial_{F_{0}}F)}(Y)\right)^{F}$ there
exists $y^{(p)}\in Y_{[\Gamma_{0}]}$ such that
$\sigma_{v}(y^{(p}))_{F\setminus\partial_{F_{0}}F}=p(v)$. Define a function
$f:\left(\mathcal{L}_{(F\setminus\partial_{F_{0}}F)}(Y)\right)^{F}\to\mathcal{L}_{K}(Y_{[\Gamma_{0}]})$
by $f(p)=y^{(p)}_{K}$, with $y^{(p)}\in Y$ as above. Then $f$ is injective,
because If
$p,q\in\left(\mathcal{L}_{(F\setminus\partial_{F_{0}}F)}(Y)\right)^{F}$ and
$f(p)=f(q)$ then in particular since $v+F_{n}\subseteq K$ for every $v\in F$,
it follows that
$\sigma_{v}(y^{(p)})_{F\setminus\partial_{F_{0}}F}=\sigma_{v}(y^{(q)})_{F\setminus\partial_{F_{0}}F}$
for every $v\in F$, and so $p(v)=q(v)$ for every $v\in F$, so $p=q$. ∎

######  Proposition 4.16.

A $\Gamma$-subshift $Y$ has the map extension property if and only if it there
exists a finite set $\mathcal{G}\Subset\mathrm{Sub}(\Gamma)$ such that $Y$ is
an absolute retract for the class of $\mathcal{G}$-free subshifts.

###### Proof.

Suppose that $Y$ has the map extension property. Then there exists a finite
set of subgroups $\mathcal{G}_{1}\Subset\mathrm{Sub}(\Gamma)$ such that for
every $\Gamma_{0}\leq\Gamma$ either there exists $y\in Y$ with
$\Gamma_{0}\leq\mathit{stab}(y)$ or there exists
$\Gamma_{1}\in\mathcal{G}_{1}$ such that $\Gamma_{1}\leq\Gamma_{0}$. It
follows that $X\rightsquigarrow Y$ for any $\mathcal{G}_{1}$-free subshift
$X$. Let $\mathcal{G}\subseteq\mathcal{G}_{1}$ be a minimal set with the
property that $X\rightsquigarrow Y$ for any $\mathcal{G}$-free subshift $X$.
We will show that $Y$ is an absolute retract for the class of
$\mathcal{G}$-free subshifts. By minimality of $\mathcal{G}$, $Y$ itself is
$\mathcal{G}$-free. Let $X$ be any $\mathcal{G}$-free subshift such that
$Y\subseteq X$. Then $X\rightsquigarrow Y$. Since $Y$ has the map extension
property and $Y\subseteq X$, it follows that then the identity map on $Y$
extends to a retraction from $X$ to $Y$.

For the converse direction: Suppose that there exists a finite set
$\mathcal{G}\Subset\mathrm{Sub}(\Gamma)$ such that $Y$ is an absolute retract
for the class of $\mathcal{G}$-free subshifts. Let $X$ be a $\Gamma$-subshift
such that $X\rightsquigarrow Y$, and let $\pi:\tilde{X}\to Y$ be a map from a
closed, $\Gamma$-invariant subset $\tilde{X}\subseteq X$. Our goal is to show
that $\tilde{\pi}$ extends to a map $\pi:X\to Y$. By Lemma 4.11, since $X$ is
$\mathcal{G}$-free, exists a $\mathcal{G}$-free subshift $\hat{Y}$ with
$Y\subseteq\hat{Y}$ so that $\tilde{\pi}$ extends to a map
$\hat{\pi}:X\to\hat{Y}$. Since $Y$ is an absolute retract for the class of
$\mathcal{G}$-free subshifts, there exists a retraction map $r:\hat{Y}\to Y$.
Setting $\pi=r\circ\hat{\pi}$, we see that $\pi:X\to Y$ extends $\tilde{\pi}$.

It remains to show that there exists a finite set
$\mathcal{G}_{1}\Subset\mathrm{Sub}(\Gamma)$ such that for every
$\Gamma_{0}\geq\Gamma$, either there exists $y\in Y$ with
$\Gamma_{0}\leq\mathit{stab}(y)$ or there exists
$\Gamma_{1}\in\mathcal{G}_{1}$ such that $\Gamma_{1}\leq\Gamma_{0}$. Let
$K_{0},F_{0}\Subset\Gamma$ be as in Lemma 4.15. Choose a symmetric monotile
$F\Subset\Gamma$ sufficiently large so that with $K_{0}\subseteq F$ and
$F\setminus\partial_{F_{0}}F\neq\emptyset$. Then choose $K\Subset\Gamma$ with
$|K\setminus\partial_{(F+F)}K|>|F|$. Then by Lemma 4.15 for any $K$-separated
subgroup $\Gamma_{0}\leq\Gamma$ we have
$|\mathcal{L}_{K}(Y_{[\Gamma_{0}}])|\geq 1$, and in particular
$Y_{[\Gamma_{0}]}\neq\emptyset$. Let $\mathcal{G}_{1}$ denote the collection
of non-trivial subgroup of $\Gamma$ that are generated by a subset
$C\subset(K-K)$. If $\Gamma_{0}$ does not contain a subgroup from
$\mathcal{G}$, then $\Gamma_{0}\cap(K-K)=\\{0\\}$, and so $\Gamma_{0}$ is
$K$-separated, so $Y_{[\Gamma_{0}]}\neq\emptyset$, so there exists $y\in Y$
with $\Gamma_{0}\leq\mathit{stab}(y)$. ∎

######  Proposition 4.17.

Let $Y$ be a $\Gamma$-subshift with the map extension property. Then

$\lim_{\Gamma_{0}\to\\{0\\}}h(\overline{Y}_{[\Gamma_{0}]})=h(Y).$

If furthermore $\mathit{Ker}(Y)=\\{0\\}$ then

$\lim_{\Gamma_{0}\to\\{0\\}}h(\overline{Y}_{\Gamma_{0}})=h(Y).$

###### Proof.

Suppose that $Y\subseteq A^{\Gamma}$ is a $\Gamma$-subshift with the map
extension property By Proposition 2.23 we know that

$\limsup_{\Gamma_{0}\to\\{0\\}}h(\overline{Y}_{[\Gamma_{0}]})\leq h(Y),$

So we need to prove that

$\liminf_{\Gamma_{0}\to\\{0\\}}h(\overline{Y}_{[\Gamma_{0}]})\geq h(Y).$

In other words, we need to prove that for every $\epsilon>0$ there exists a
finite set $K\Subset\Gamma$ such that for any $K$-separated subgroup
$\Gamma_{0}<\Gamma$ it holds that $h(\overline{Y}_{[\Gamma_{0}]})\geq
h(Y)-\epsilon$.

Fix $0<\epsilon<1$. By Proposition 4.16 there exists a finite set
$\mathcal{G}\Subset\mathrm{Sub}(\Gamma)$ such that $Y$ is an absolute retract
for the class of $\mathcal{G}$-free subshifts. Let $F_{0},K_{0}\Subset\Gamma$
be as in the statement of Lemma 4.15, and let $(F_{n})_{n=1}^{\infty}$ be a
Følner sequence in $\Gamma$, such that each $F_{n}\Subset\Gamma$ is a
symmetric monotile with $K_{0}\subseteq F_{n}$. We have
$h(Y)=\lim_{n\to\infty}\frac{1}{|F_{n}|}\log|\mathcal{L}_{F_{n}}(Y)|$. Also
since $(F_{n})_{n=1}^{\infty}$ we have

$\lim_{n\to\infty}\frac{|F_{n}|}{|F_{n}\setminus\partial_{F_{0}}F_{n}|}=1\mbox{
and
}\lim_{n\to\infty}\frac{\log|\mathcal{L}_{F_{n}}(Y)|}{\log|\mathcal{L}_{|F_{n}\setminus\partial_{F_{0}}F_{n}|}(Y)|}=1.$

Thus, there exists $m\in\mathbb{N}$ so that

$\frac{1}{|F_{m}|}\log|\mathcal{L}_{F_{m}\setminus\partial_{F_{0}}F_{m}}(Y)|\geq
h(Y)-\frac{\epsilon}{2}.$

By Lemma 2.9, there exists a finite set $K_{1}\Subset\Gamma$ so that any
$K_{1}$-separated subgroup $\Gamma_{0}\leq\Gamma$ admits a fundamental domain
$D\subseteq\Gamma$ which is a union of
$((F_{m}+F_{m}),\frac{\epsilon}{4}(\log|A|)^{-1})$-invariant sets.

Now let $\Gamma_{0}\leq\Gamma$ be any $K_{1}$-separated subgroup, and let
$D\subseteq\Gamma$ be a fundamental domain for $\Gamma_{0}$ which is a union
of $((F_{m}+F_{m}),\frac{\epsilon}{4}(\log|A|)^{-1})$-invariant sets. Let
$(\overline{F}_{n})_{n=1}^{\infty})$ be a Følner sequence in
$\Gamma/\Gamma_{0}$, and for each $n$ let

$\tilde{F}_{n}=\left\\{v\in D\leavevmode\nobreak\ :\leavevmode\nobreak\
v+\Gamma_{0}\in\overline{F}_{n}\right\\}.$

Then for every $n\in\mathbb{N}$ we have $|\tilde{F}_{n}|=|\overline{F_{n}}|$
and
$\mathcal{L}_{\tilde{F}_{n}}(Y_{[\Gamma_{0}]})=\mathcal{L}_{\overline{F}_{n}}(\overline{Y}_{[\Gamma_{0}]})$,
and so

$h(\overline{Y}_{[\Gamma_{0}]})=\lim_{n\to\infty}\frac{1}{|\tilde{F}_{n}|}\log|\mathcal{L}_{\tilde{F}_{n}}(Y_{[\Gamma_{0}]})|.$

Since $(\overline{F}_{n})_{n=1}^{\infty})$ is a Følner sequence in
$\Gamma/\Gamma_{0}$ and $D$ is a union of
$((F_{m}+F_{m}),\frac{\epsilon}{4}(\log|A|)^{-1})$-invariant sets, it follows
that for sufficiently large $n$ we have

$\frac{|\tilde{F}_{n}\setminus\partial_{F_{m}+F_{m}}\tilde{F}_{n}|}{|\tilde{F}_{n}|}\geq
1-\frac{\epsilon}{4\log|A|}.$

For every $n\in\mathbb{N}$ we have that $\Gamma_{0}$ is
$\tilde{F}_{n}$-separated since ($\tilde{F}_{n}\subseteq D$), and so by Lemma
4.15 we have that

$\frac{|\mathcal{L}_{\tilde{F}_{n}}(Y_{[\Gamma_{0}]})|}{|\tilde{F}_{n}\setminus\partial_{F_{m}+F_{m}}\tilde{F}_{n}|}\geq\frac{1}{|F_{m}|}\log|\mathcal{L}_{F_{m}\setminus\partial_{F_{0}}F_{m}}(Y)|.$

and so for all sufficiently $n$ we have

$\frac{|\mathcal{L}_{\tilde{F}_{n}}(Y_{[\Gamma_{0}]})|}{|\tilde{F}_{n}|}\geq(1-\frac{\epsilon}{4\log|A|})\left(h(Y)-\frac{\epsilon}{2}\right)\geq
h(Y)-\epsilon.$

Taking $n\to\infty$ we conclude that $h(\overline{Y}_{[\Gamma_{0}]})\geq
h(Y)-\epsilon$.

It remains to prove that under the additional assumption that
$\mathit{Ker}(Y)=\\{0\\}$ we have

$\lim_{\Gamma_{0}\to\\{0\\}}h(\overline{Y}_{\Gamma_{0}})=h(Y).$

Since $\overline{Y}_{\Gamma_{0}}\subseteq\overline{Y}_{[\Gamma_{0}]}$ for any
$\Gamma_{0}\leq\Gamma$, with equality in the case that
$[\Gamma:\Gamma_{0}]=+\infty$, it suffices to prove that for any $\epsilon>0$,
there exists $K_{1}\Subset\Gamma$ such that for any $K_{1}$-separated subgroup
$\Gamma_{0}$ with $[\Gamma:\Gamma_{0}]<+\infty$ we have

$|Y_{[\Gamma_{0}]}|\leq|Y_{\Gamma_{0}}|e^{(1-\epsilon)[\Gamma:\Gamma_{0}]}.$

As in the first part of the proof, using Lemma 2.9, for any $\epsilon_{1}>0$
and $m\in\mathbb{N}$ we can find a finite set $K_{1}\Subset\Gamma$ so that any
$K_{1}$-separated subgroup $\Gamma_{0}\leq\Gamma$ admits a fundamental domain
$D\subseteq\Gamma$ which is a union of
$((F_{m}+F_{m}),\epsilon_{1})$-invariant sets. Now let $\Gamma_{0}\leq\Gamma$
be $K_{1}$-separated with $[\Gamma:\Gamma_{0}]<+\infty$. For any
$\epsilon_{2}>0$, using Lemma 4.13 one can show that if $m$ is sufficiently
big and $\epsilon_{1}>0$ is sufficiently small, there exists a set
$F\subseteq\Gamma/\Gamma_{0}$ with
$|F|\geq(1-\epsilon_{2})|\Gamma:\Gamma_{0}]$ so that for any $y\in
Y_{[\Gamma_{0}]}$ we can find $\tilde{y}\in Y_{\Gamma_{0}}$ with
$\tilde{y}_{F}=y_{F}$. This proves that

$|Y_{[\Gamma_{0}]}|\leq|Y_{\Gamma_{0}}||A|^{\epsilon_{2}[\Gamma:\Gamma_{0}]}.$

Taking $\epsilon_{2}<\epsilon_{1}\log|A|$, completes the proof.

∎

######  Definition 4.18.

Let $F_{1},F_{2},K\subsetneq\Gamma$ be subsets of $\Gamma$ and $\emptyset\neq
K\Subset\Gamma$. We say that $F_{1},F_{2}$ are _$K$ -disjoint_ if
$(K+F_{1})\cap(K+F_{2})=\emptyset$.

######  Definition 4.19.

A subshift $X\Subset A^{\Gamma}$ is called _strongly irreducible_ if there
exists $K\Subset\Gamma$ such that for any pair of $K$-disjoint sets
$F_{1},F_{2}\subseteq\Gamma$ and any $x^{(1)},x^{(2)}\in X$ there exists $x\in
X$ such that $x_{F_{1}}=x^{(1)}_{F_{1}}$ and $x_{F_{2}}=x^{(2)}_{F_{2}}$. We
say that $K\Subset\Gamma$ as above is an _irreducibility window_ for $X$.

######  Proposition 4.20.

The following families of subshifts are closed under taking retracts:

  1. (1)

sofic shifts

  2. (2)

topologically mixing subshifts

  3. (3)

strongly irreducbile subshifts

  4. (4)

shifts of finite type

###### Proof.

The classes of sofic shifts, topological mixing subshifts and strongly
irreducible subshifts are each closed under taking (subshift) factors. In
particular, they are closed under taking retracts. It remains to show that a
retract of any retract of a shift of finite type is also a shift of finite
type. Let $X\subseteq A^{\Gamma}$ be a shift of finite type with a defining
set of forbidden patterns $\mathcal{F}_{1}\Subset A^{W_{1}}$. Suppose that
$Y\subseteq X$ is a retract, with $r:X\to Y$ a retraction. Let
$W_{0}\Subset\Gamma$ be a coding window for $r$ such that $0\in W_{0}$, and
let $\Phi:A^{W_{0}}\to A$ be a sliding block code for $r$. Let

$\mathcal{F}_{0}=\left\\{w\in A^{W_{0}}\leavevmode\nobreak\
:\leavevmode\nobreak\ \Phi(w)_{0}\neq w_{0}\right\\}.$

Now suppose that $x\in X$ satisfies that
$\sigma_{v}(x)_{W_{0}}\not\in\mathcal{F}_{0}$ for all $v\in\Gamma$. It follows
that $r(x)=x$, so $x\in Y$. This means that

$Y=\left\\{x\in X\leavevmode\nobreak\ :\leavevmode\nobreak\
\sigma_{v}(x)_{W_{0}}\not\in\mathcal{F}_{0}\mbox{ for all
}v\in\Gamma\right\\}.$

$W=W_{0}\cup W_{1}$ and let

$\mathcal{F}=\left\\{w\in A^{W}\leavevmode\nobreak\ :\leavevmode\nobreak\
\leavevmode\nobreak\ w_{W_{0}}\in\mathcal{F}_{0}\mbox{ or
}w_{W_{1}}\in\mathcal{F}_{1}\right\\}.$

Then $\mathcal{F}$ is a defining set of forbidden patterns for $Y$. This
proves that $Y$ is a shift of finite type. ∎

######  Lemma 4.21.

Let $\mathcal{G}\Subset\mathrm{Sub}(\Gamma)$ be a finite set, and let
$Y\subseteq A^{\Gamma}$ be a $\mathcal{G}$-free subshift. Then there exists a
finite set $\hat{A}$ with $A\subset\hat{A}$ and a $\mathcal{G}$-free subshift
$\hat{Y}\subseteq\hat{A}^{\Gamma}$ such that $Y\subseteq\hat{Y}$ and so that
$\hat{Y}$ is a strongly irreducible shift of finite type.

###### Proof.

Let $Y\subseteq A^{\Gamma}$ be a $\mathcal{G}$-free subshift. By compactness
of $Y$, there exists a finite set $W\Subset\Gamma$ such that any
$w\in\mathcal{L}_{W}(Y)$ is $\mathcal{G}$-free in the following sense: For
every $\Gamma_{0}\in\mathcal{G}$ there exists $v\in\Gamma_{0}$ and $u\in W$
such that $u+v\in W$ and $w_{u}\neq w_{u+v}$. Let $W\Subset\Gamma$ be as
above, and in addition, assume that $0\in W$ and that $W$ is symmetric Given a
finite set $\hat{A}$ let $\mathcal{F}\subset\hat{A}^{W}$ denote the set of
words that are not $\mathcal{G}$-free in the sense that there exists
$\Gamma_{0}\in\mathcal{G}$ such that for every $v\in\Gamma_{0}$ if $u\in W$
and $u+v\in W$ then $w_{u}=w_{u+v}$. Let $\hat{Y}\subseteq\hat{A}^{\Gamma}$
the subshift of finite type defined by the set of forbidden words
$\mathcal{F}$. Then $\hat{Y}$ is obviously $\mathcal{G}$-free. Also, if
$A\subseteq\hat{A}$ then $Y\subseteq\hat{Y}$. We claim that if $|\hat{A}|\geq
W$ then for any set $F\subseteq\Gamma\setminus\\{0\\}$ and any
$w\in\hat{A}^{F}$ such that $\sigma_{v}(w))_{W}\not\in\mathcal{F}$ for
$\hat{Y}$ is strongly irreducible. To see this, it suffices to show that for
any $F\subseteq\Gamma\setminus\\{0\\}$ and any pattern $w\in\hat{A}^{F}$ which
is $\mathcal{F}$-free (in the sense that sub-patterns from $\mathcal{F}$ do
not occur in it) can be extended to a $\mathcal{F}$-free pattern
$\tilde{w}\in\hat{A}^{F\cup\\{0\\}}$.

Let $F\subseteq\Gamma\setminus\\{0\\}$ and an $\mathcal{F}$-free pattern $w\in
A^{F}$. Since $|W\setminus\\{0\\}|<|\hat{A}|$ there exists $\hat{a}\in\hat{A}$
such that $w_{v}\neq\hat{a}$ for any $v\in(W\cap F)\setminus\\{0\\}$. Let
$\tilde{w}\in\hat{A}^{F\cup\\{0\\}}$ be defined by

$\tilde{w}_{v}=\begin{cases}\hat{a}&\mbox{ if }v=0\\\ w_{v}&\mbox{
otherwise.}\end{cases}$

Then $\tilde{W}$ is also $\mathcal{F}$-free $\tilde{w}_{F}=w$. ∎

######  Proposition 4.22.

Let $\Gamma$ be an infinite countable abelian group and let $Y$ be a
$\Gamma$-subshift with the map extension property. Then $Y$ is a strongly
irreducible shift of finite type.

###### Proof.

Suppose that $Y$ has the map extension property. Then by Proposition 4.16,
there exists a finite set $\mathcal{G}\Subset\mathrm{Sub}(\Gamma)$ such that
$Y$ is an absolute retract for the class of $\mathcal{G}$-free subshifts.

Then by Lemma 4.21, $Y$ embeds in a $\mathcal{G}$-free strongly irreducible
SFT $\hat{Y}$. By Proposition 4.20 it follows that $Y$ is also a strongly
irreducible subshift of finite type. ∎

######  Lemma 4.23.

Let $Y$ be a $\Gamma$-subshift with the map extension property. For any
$\Gamma_{0}\leq\Gamma$, if $Y_{[\Gamma_{0}]}$ is non-empty then
$\overline{Y}_{[\Gamma_{0}]}$ has the map extension property.

###### Proof.

Suppose that $Y$ is a $\Gamma$-subshift with the map extension property. Then
there exists a finite set $\mathcal{G}\Subset\mathrm{Sub}(\Gamma)$ such that
for every $\Gamma_{0}\leq\Gamma$ there exists $y\in Y$ with
$\Gamma_{0}\leq\mathit{stab}(y)$ or there exists $\Gamma_{1}\in\mathcal{G}$
such that $\Gamma_{1}\leq\Gamma_{0}$. Now suppose that $\Gamma_{0}\leq\Gamma$
and that that $Y_{[\Gamma_{0}]}$ is non-empty.

Let $\mathcal{G}_{1}\Subset\mathrm{Sub}(\Gamma/\Gamma_{0})$ be the set
obtained via the natural projection from $\Gamma$ to $\Gamma/\Gamma_{1}$.
Suppose that $\tilde{\Gamma}\leq\Gamma/\Gamma_{0}$, Let

$\Gamma_{2}=\left\\{\gamma\in\Gamma\leavevmode\nobreak\ :\leavevmode\nobreak\
\gamma+\Gamma_{0}\in\tilde{\Gamma}\right\\}.$

If there exists $y\in Y$ such that $\Gamma_{2}\leq\mathit{stab}(y)$ then in
particular for that $y$ we have that $y\in Y_{[\Gamma_{0}]}$ and so there
exists $\tilde{y}\in\overline{Y}_{[\Gamma_{0}]}$ such that
$\tilde{\Gamma}\leq\tilde{y}$. Otherwise, there exists
$\Gamma_{1}\in\mathcal{G}$ such that $\Gamma_{1}\leq\Gamma_{2}$, and in this
case $\tilde{\Gamma}$ contains the projection of $\Gamma_{1}$, which is an
element of $\mathcal{G}_{1}$.

Now suppose that $Z$ is a $\Gamma/\Gamma_{0}$-subshift $\tilde{Z}\subseteq Z$
is a closed $\Gamma/\Gamma_{0}$-invariant set and that
$\tilde{\pi}:\tilde{Z}\to Z$ is a map. Let $X$ denote the $\Gamma$-subshift
obtained by “lifting” $Z$ in the sense that for any $x\in X$ there exists
$z\in Z$ such that $x_{\gamma}=z_{\gamma+\Gamma_{0}}$ for all
$\gamma\in\Gamma$. Let $\tilde{X}\subseteq X$ denote the “lift” of
$\tilde{Z}$, namely $\tilde{x}\in\tilde{X}$ if and only if there exists
$\tilde{z}\in\tilde{Z}$ such that
$\tilde{x}_{\gamma}=\tilde{z}_{\gamma+\Gamma_{0}}$ for all $\gamma\in\Gamma$.
Let $\hat{\pi}:\tilde{X}\to Y$ be the map obtained by “lifting” $\tilde{\pi}$.
Then by the map extension property of $Y$ there exist a map $\check{\pi}:X\to
Y$ that extends $\hat{\pi}$. Since $\Gamma_{0}\leq\mathit{Ker}(X)$, it follows
that $\check{\pi}$ projects to a map $\pi:X\to Y_{[\Gamma_{0}]}$ that extends
$\tilde{\pi}$. ∎

In preparation for the next result, we recall Boyle’s extension lemma [5,
Lemma 2.2]:

######  Lemma 4.24 (Boyle’s Extension Lemma [5]).

Let $X$ be a $\mathbb{Z}$-subshift, let $\tilde{X}\subseteq X$ be a closed
shift-invariant set, and let $Y\subseteq B^{\mathbb{Z}}$ be mixing subshift of
finite type such that $X\rightsquigarrow Y$. Let $\tilde{\pi}:\tilde{X}\to Y$
be a map. Then $\tilde{\pi}$ extends to a map $\pi:X\to Y$.

######  Proposition 4.25.

A $\mathbb{Z}$-subshift has the map extension property if and only if it is a
topologically mixing subshift of finite type.

###### Proof.

From Proposition 4.22 it follows that any $\Gamma$-subshift which has the map
extension property is a strongly irreducible SFT. In particular, any
$\mathbb{Z}$-subshift which is a restricted absolute retract is a mixing shift
of finite type. Now suppose $Y\subset A^{\mathbb{Z}}$ is a mixing SFT. Let
$\mathcal{G}\subset\mathrm{Sub}(\mathbb{Z})$ denote the collection of
subgroups $\Gamma_{0}\leq\mathbb{Z}$ such that for every $y\in Y$ the subgroup
$\Gamma_{0}$ is not contained in $\mathit{stab}(x)$. We claim that
$\mathcal{G}$ is a finite set. Indeed, since $Y$ is a mixing $\mathbb{Z}$-SFT,
there exists $n_{0}\in\mathbb{N}$ such that for every $n\geq n_{0}$ there
exists $y\in Y$ with $\sigma^{n}(y)=y$. Thus, every subgroup
$\Gamma_{0}\in\mathcal{G}$ must be of the form $n\mathbb{Z}$ with $n<n_{0}$.
It follows from Boyle’s Extension (Lemma 4.24) that $Y$ has the map extension
property. ∎

Although the map extension property is a rather strong property for
$\mathbb{Z}^{d}$-subshifts, it is satisfied by many “naturally occuring”
subshifts of finite type:

######  Definition 4.26.

Let $X\subseteq A^{\Gamma}$ be a subshift. We say that $a\in A$ is a _safe
symbol_ or $X$ if for any $F\Subset\Gamma$ and any $w\in\mathcal{L}_{F}(X)$
and any $\tilde{w}\in A^{F}$ any pattern $\tilde{w}\in A^{F}$ that satisfies
$\tilde{w}_{v}\in\\{a,w_{v}\\}$ for all $v\in F$ is in $\mathcal{L}_{F}(X)$.
Equivalently, $a\in A$ is a safe symbol for $X$ if for any $x\in X$ changing
the value of $x$ any $v\in\Gamma$ to $a$ results in a point of $X$.

######  Proposition 4.27.

Any $\Gamma$-SFT with a safe symbol is an absolute retract for the class of
subshifts, and in particular has the map extension property.

###### Proof.

Let $X\subseteq A^{\Gamma}$ be a $\Gamma$-SFT with a safe symbol $a\in A$, and
suppose that $Y\subseteq\tilde{A}^{\Gamma}$ is another subshift such that
$X\subseteq Y$. Let $\mathcal{F}\subset A^{W}$ be a defining set of forbidden
patterns for $X$. We can define a retraction $r:Y\to X$ as follows:

$r(y)_{v}=\begin{cases}y_{v}&(\sigma_{-v-w}(y))_{W}\not\in\mathcal{F}\mbox{
for all }w\in W\\\ a&\mbox{ otherwise}.\end{cases}$

∎

Given a finite, symmetric set $F\subset\Gamma\setminus\\{0\\}$ and
$k\in\mathbb{N}$, we denote by $X_{k,F}\subseteq\\{1,\ldots,k\\}^{\Gamma}$ the
space of proper $k$-colorings of Cayley graph of $\Gamma$ corresponding to
$F$:

$X_{k,F}=\left\\{x\in\\{1,\ldots,k\\}^{\Gamma}\leavevmode\nobreak\
:\leavevmode\nobreak\ \forall\gamma\in\Gamma,v\in F\leavevmode\nobreak\
x_{\gamma}\neq x_{\gamma+v}\right\\}.$

In particular, when $\Gamma=\mathbb{Z}^{2}$ and $F=\\{(\pi 1,0),(0,\pm 1)\\}$
is the standard generating set, the subshift $X_{k,F}$, which is the space of
proper $k$-colorings of the $\mathbb{Z}^{2}$-lattice, was shown to be strongly
irreducible if and only if $k\geq 4$ [1]. The following result show in
particular that when $k\geq 5$ the space of $5$-colorings of $\mathbb{Z}^{d}$
has the map extension property.

######  Proposition 4.28.

For any finite set $F\subset\Gamma\setminus\\{0\\}$ and any $k>|F|$ the
subshift $X_{k,F}$ has the map extension property.

###### Proof.

Let $F\Subset\Gamma\setminus\\{0\\}$ be a finite symmetric set and $k>|F|$.
Let $\mathcal{G}\Subset\mathrm{Sub}(\Gamma)$ denote the set of cyclic subgroup
generated by elements of $F$:

$\mathcal{G}=\left\\{\langle v\rangle\leavevmode\nobreak\
:\leavevmode\nobreak\ v\in F\right\\}.$

We will prove that $X_{k,F}$ is an absolute retract for the class of
$\mathcal{G}$-free subshifts. Since $x_{0}\neq x_{v}$ for any $x\in X_{k,F}$
and $v\in F$, it is clear that $v\not\in\mathit{stab}(x)$ for any $x\in
X_{k,F}$, so $X_{k,F}$ is $\mathcal{G}$-free. Let $X$ be any
$\mathcal{G}$-free subshift such that $X_{k,F}\subseteq X$. By Lemma 3.3 there
exists a clopen set $C\subset X$ such that $C\cap\sigma_{v}(C)=\emptyset$ for
every $v\in F$ and $X=C\bigcup_{v\in V}\sigma_{v}(C)$. Define a map
$\alpha:X\to\\{0,1\\}^{\Gamma}$ by declaring for $x\in X$ and $v\in\Gamma$

$\alpha(x)_{v}=\begin{cases}1&\sigma_{v}(x)\in C\\\
0&\mbox{otherwise}.\end{cases}$

For $x\in X$ let

$B(x)=\\{x_{v}\leavevmode\nobreak\ :\leavevmode\nobreak\ v\in F\\}.$

Let $F=\\{v_{0},v_{1},\ldots,v_{|F|}\\}$ be some enumeration of the elements
of $F\cup\\{0\\}$. For every $x\in X$ let

$t(x)=\min\\{0\leq j\leq|F|\leavevmode\nobreak\ :\leavevmode\nobreak\
\sigma_{v}(x)\in C\\}.$

For every $0\leq j\leq|F|$, define a map $r^{(j)}:X\to X$ as follows be
declaring for $x\in X$ and $v\in\Gamma$:

$r^{(j)}(x)_{v}=\begin{cases}x_{v}&\mbox{ if }t(X)\neq j\mbox{ or
}x_{v}\in\\{1,\ldots,k\\}\setminus B(\sigma_{v}(x)).\\\
\min\left(\\{1,\ldots,k\\}\setminus B(\sigma_{v}(x))\right)&\mbox{ otherwise.
}\end{cases}$

Note that for every $v\in F\cap\\{0\\}$ we have that Since
$|B(\sigma_{v}(x)|\leq|F|<k$, it follows that $\\{1,\ldots,k\\}\setminus
B(\sigma_{v}(x))\neq\emptyset$, so $r^{(j)}$ is well-defined.

Define $\tilde{r}^{(0)}=r^{(0)}$ and
$\tilde{r}^{(j)}=r^{(j)}\circ\tilde{r}^{(j-1)}$ for every $1\leq j\leq|F|$.
Let $r=\tilde{r}^{(|F|)}:X\to X$. We claim that $r:X\to X_{k,F}$ is a
retraction. By induction it follows that if $x\in
C\cup\bigcup_{\ell=1}^{j}\sigma_{v_{\ell}}^{-1}(C)$ then
$x_{0}\in\\{1\ldots,k\\}\setminus B(x)$. In particular, since
$X=\bigcup_{\ell=1}^{|F|}\sigma_{v_{\ell}}^{-1}(C)$, it follows that
$r(x)_{0}\in\\{1\ldots,k\\}\setminus B(x)$ for every $x\in X$. So for every
$x\in X$, $r(x)\in\\{1,\ldots,l\\}^{\Gamma}$ and $r(x)_{v}\neq r(x)_{v+W}$ for
every $v\in\Gamma$ and $w\in F$. This proves that $r(x)\in X_{k,F}$ for every
$x\in X$. It is easy to check that $r^{(j)}(x)=x$ for every $0\leq j\leq|F|$
and $x\in X_{k,F}$, so $r(x)=x$ for every $x\in X_{k,F}$. This proves that
$r:X\to X_{k,F}$ is indeed a retraction. ∎

In relation with the previous result: For any $d>1$, the space
$X_{3}\subseteq\\{0,1,2\\}^{\mathbb{Z}^{2}}$, $3$-colors of $\mathbb{Z}^{2}$,
which is a topologically mixing subshift of finite type (but not strongly
irreducible). It is not clear if one can formulate a “reasonable”
characterization of the subsystems of $X_{3}$. It is known that $X_{3}$ does
not contain any strongly irreducible subshift [9, Proposition 12.2], so
certainly an analog of Theorem 1.4 does not hold with $Y=X_{3}$.

##  5\. Entropy minimal subshifts and necessity of the conditions for
embedding

In this section we recall the notion of entropy minimality for subshifts, and
prove that for an entropy minimal $\Gamma$-subshift $Y$, the conditions in the
statement of Theorem 1.4 are necessary for the existence of an extension of
$\hat{\rho}$ to an embedding $\rho:X\to Y$.

A $\Gamma$-subshift $Y$ is called _entropy minimal_ if the only
$\Gamma$-subshift $X\subseteq Y$ that satisfies $h(X)=h(Y)$ is $X=Y$.
Equivalently, any proper subshift of $Y$ has strictly lower topological
entropy.

The following easy result is a consequence of the fact that isomorphic
subshifts have equal topological entropy and that a topological entropy of a
subsystem of $Y$ never exceeds the topological entropy of $Y$.

######  Proposition 5.1.

Let $\Gamma$ be a countable abelian group and let $X,Y$ be $\Gamma$-subshifts,
let $Z\subseteq X$ be a closed $\Gamma$-invariant set, and let
$\hat{\rho}:Z\to Y$ be an embedding. If $X\hookrightarrow_{\hat{\rho}}Y$ then
for any subgroup $\Gamma_{0}\leq\Gamma$ we have that
$h(\overline{X}_{\Gamma_{0}})\leq h(\overline{Y}_{\Gamma_{0}})$. Furthermore,
if for some subgroup $\Gamma_{0}\leq\Gamma$ the subshift
$\overline{Y}_{\Gamma}$ is entropy minimal, then the condition
$E(X,Y,\hat{\rho},\Gamma_{0})$ holds.

It is well-known that any strongly irreducible $\Gamma$-subshift is entropy
minimal, see for instance [6, 21]. In particular, if $Y$ is a
$\Gamma$-subshift with the map extension property, then by Lemma 4.23 and
Proposition 4.22 we have that $\overline{Y}_{\Gamma_{0}}$ is strongly
irreducible for any $\Gamma_{0}\leq\Gamma$.

It follows that the conditions in the statement of Theorem 1.4 for extending
an embedding of a subsystem to an embedding are necessary when the target $Y$
is has the map extension property:

######  Corollary 5.2.

Let $\Gamma$ be a countable abelian group and let $X,Y$ be $\Gamma$-subshifts,
where $Y$ has the map extension property let $Z\subseteq X$ be a closed
$\Gamma$-invariant set, and let $\hat{\rho}:Z\to Y$ be an embedding. If
$X\hookrightarrow_{\hat{\rho}}Y$ then for any subgroup $\Gamma_{0}\leq\Gamma$,
the condition $E(X,Y,\hat{\rho},\Gamma_{0})$ holds.

##  6\. Truncated Voronoi diagrams and Partial tilings

Throughout this section $\Gamma$ will be a finitely generated abelian group of
the form $\Gamma=\mathbb{Z}^{d}\times G$, where $G$ is a finite abelian group.

######  Definition 6.1.

A _partial tiling_ of $\Gamma$ is a collection of pairwise disjoint finite
subsets of $\Gamma$. We denote the set of partial tilings of $\Gamma$ by
$\mathit{PTilings}(\Gamma)$. A _tiling_ of $\Gamma$ is a partition of $\Gamma$
into pairwise disjoint finite subsets. For a partial tiling
$\tau\in\mathit{PTilings}(\Gamma)$ we refer to the elements of $\tau$ as
tiles.

The space $\mathit{PTilings}(\Gamma)$ admits a natural Polish topology, which
we now describe: We describe a basis for this topology. For $F\Subset\Gamma$
and $\tau\in\mathit{PTilings}(\Gamma)$ let
$N(F,\tau)\subseteq\mathit{PTilings}(\Gamma)$ denote the collection of partial
tilings $\tilde{\tau}\in\mathit{PTilings}(\Gamma)$ that satisfy the property
that for $T\subseteq F$ we have that $T\in\tilde{\tau}$ if and only if
$T\in\tau$. A closed subset $P\subseteq\mathit{PTilings}(\Gamma)$ is compact
if and only if every $\gamma\in\Gamma$ is covered by one of finitely many
tiles (among all possibilities of tilings in $\Gamma$). The group $\Gamma$
acts on $\mathit{PTilings}(\Gamma)$ by translations. Although we will not use
this fact, we mention that any compact $\Gamma$-invariant subsystem of
$\mathit{PTilings}(\Gamma)$ is isomorphic to a $\Gamma$-subshift.

######  Definition 6.2.

Let $\mathcal{T}\in\mathit{PTilings}(\Gamma)$ be a partial tiling. Denote
$\bigcup\mathcal{T}\subseteq\Gamma$ the union of tiles in $\tau$. We say that
$\mathcal{T}\in\mathit{PTilings}(\Gamma)$ is _$(K,\epsilon)$ -invariant_ for
$K\Subset\Gamma$ and $\epsilon>0$ if each $T\in\mathcal{T}$ is
$(K,\epsilon)$-invariant. Given a partial tiling
$\mathcal{T}\in\mathit{PTilings}(\Gamma)$, $T\in\mathcal{T}$ and
$K\Subset\Gamma$, we let

$\partial_{K}^{\mathcal{T}}T=\left\\{v\in\Gamma\leavevmode\nobreak\
:\leavevmode\nobreak\ (v+K)\cap T\neq\emptyset\mbox{ and
}(v+K)\not\subseteq\bigcup\mathcal{T}\right\\}.$

We refer to the set $\partial_{K}^{\mathcal{T}}T$ as the _exterior
$K$-boundary of $T$ with respect to $\mathcal{T}$_. We say that a partial
tiling $\mathcal{T}$ _has $(K,\epsilon)$-small exterior boundary_ if every
$T\in\mathcal{T}$ satisfies

$|\partial_{K}^{\mathcal{T}}T|\leq\epsilon|T|.$

######  Definition 6.3.

We identify the space $\\{0,1\\}^{\Gamma}$ with the space of subsets of
$\Gamma$ via the obvious bijection

$x\in\\{0,1\\}^{\Gamma}\Leftrightarrow\left\\{v\in\Gamma\leavevmode\nobreak\
:\leavevmode\nobreak\ x_{v}=1\right\\}.$

Given $F\Subset\Gamma$, we say that a $\Gamma$-subshift $Z\Subset\Gamma$ is
$F$-separated if every $z\in Z$ is $F$-separated (when viewed as a subset of
$\Gamma$). Given a $\Gamma$-subshift $Z$, $K\Subset\Gamma$ and $\epsilon>0$,
we say that a map $\tau:Z\to\mathit{PTilings}(\Gamma)$ is a _$(K,\epsilon)$
-invariant tiling of $Z$_ if for every $z\in z$ the partial tiling
$\tau(z)\in\mathit{PTilings}(\Gamma)$ is $(K,\epsilon)$-invariant. If
$Z\subseteq\\{0,1\\}^{\Gamma}$ is a $\Gamma$-subshift, we say that a map
$\tau:Z\to\mathit{PTilings}(\Gamma)$ is a _pointed partial tiling_ if for
every $z\in Z$ for every tile $T\in\tau(z)$ there exists a unique $v\in T$
such that $z_{v}=1$. In that case we say that $v$ is the _center_ of the tile
$z$.

Our main goal is to prove that any $\Gamma$-subshift $X$ admits a “well-
behaved” continuous, equivariant map into the space of
$(K,\epsilon)$-invariant partial tilings, for arbitrary $K\Subset\Gamma$ and
$\epsilon>0$:

######  Proposition 6.4.

Let $\Gamma$ be a finitely generated abelian group, and let $X$ be a
$\Gamma$-subshift. For every $K\Subset\Gamma$ and $\epsilon>0$ there exists a
finite set $P\Subset\Gamma\setminus\\{0\\}$ so that given:

  * •

A finite subset $W\Subset\Gamma$,

  * •

$\epsilon_{1}>0$,

  * •

A set of patterns $\mathcal{F}\subseteq\mathcal{L}_{W}(X)$ so that
$x_{W}\not\in\mathcal{F}$ for any $x\in X$ such that $\mathit{stab}(x)\cap
P=\emptyset$.

There exists a map $\alpha:X\to\\{0,1\\}$ and a pointed
$(K,\epsilon)$-invariant tiling $\tau:\alpha(X)\to\mathit{PTilings}(\Gamma)$
such that for every $x\in X$:

  1. (1)

If $v\not\in\bigcup\tau(\alpha(x))$ then $\sigma_{v}(x)_{W}\in\mathcal{F}$.

  2. (2)

If $v\in\Gamma$ satisfies $\alpha(x)_{v}=1$ then
$\sigma(x)_{W}\not\in\mathcal{F}$ and there exist $T\in\tau(\alpha(x))$ such
that $v+K\subseteq T$.

  3. (3)

The partial tiling $\tau(\alpha(x))\in\mathit{PTilings}(\Gamma)$ has
$(W,\epsilon_{1})$-small exterior boundary.

The statement of the Proposition 6.4 above is slightly involved because in our
application it will be essential that the set $P\Subset\Gamma\setminus\\{0\\}$
can be chosen depending only on $K\Subset\Gamma$ and $\epsilon>0$, and
independently from $\epsilon_{1}>0$, $W\Subset\Gamma$ and
$\mathcal{F}\subseteq\mathcal{L}_{W}(Y)$. In our application the parameters
$\epsilon_{1}>0$, $W\Subset\Gamma$ and
$\mathcal{F}\subseteq\mathcal{L}_{W}(Y)$ will actually depend on the set
$P\Subset\Gamma\setminus\\{0\\}$ and the previously chosen parameters.

In the case where $X$ is an aperiodic subshift, we actually get a map into the
space of $(K,\epsilon)$-invariant partial tiling:

######  Corollary 6.5.

[Lightwood [17]] Let $\Gamma$ be a finitely generated abelian group, and let
$X$ be an aperiodic $\Gamma$-subshift. Then for any $K\Subset\Gamma$ and
$\epsilon$ there exists a map from $\tau:X\to\mathit{PTilings}(\Gamma)$ such
that for every $x\in X$ $\tau(x)$ is a $(K,\epsilon)$-invariant tiling.

For context, we explain why Corollary 6.5 is a direct consequence of
Proposition 6.4:

###### Proof.

Let $X$ be an aperiodic $\Gamma$-subshift and let $K\Subset\Gamma$ and
$\epsilon>0$ be given. Apply Proposition 6.4 on $X$ with the given $K$ and
$\epsilon$. We obtain a corresponding set $P\Subset\Gamma\setminus\\{0\\}$
(and a map $\alpha:X\to\\{0,1\\}^{\Gamma}$). Choose any
$W,\tilde{W}\Subset\Gamma$ and any $\epsilon_{1}>0$. Take
$\mathcal{F}=\emptyset$ then $\mathcal{F}\subseteq\mathcal{L}_{W}(X)$ and
since $\mathit{stab}(x)\cap P=\emptyset$ for any $x\in X$, in particular
$x_{W}\not\in\mathcal{F}$ for any $x\in X$ such that $\mathit{stab}(x)\cap
P=\emptyset$. Then there exists a map $\tau:X\to\mathit{PTilings}(X)$ such
that $\tau(x)$ is $(K\epsilon)$-invariant and such that each $\tau(x)$ is a
tiling (because if for some $x\in X$ there exists
$v\in\Gamma\setminus\bigcup\tau(x)$ then
$\sigma_{-v}(x)_{W}\in\mathcal{F}=\emptyset$, which is impossible). ∎

We remark that the assumption that $\Gamma$ is finitely generated can be
removed with out much difficulty both in Corollary 6.5 and in Proposition 6.4.
We also remark that the conclusion of Corollary 6.5 holds for various non-
abelian amenable groups. See [12] and also [4], although in the more general
setting the proof proceeds via different methods.

However, in the presence of points with non-trivial stablizer, one can easily
see that it is impossible to get a map into the space of
$(K,\epsilon)$-invariant partial tilings for arbitrary $K\Subset\Gamma$ and
$\epsilon>0$.

The proof below of Proposition 6.4 proceeds via the notion of Voronoi diagrams
(that still makes sense in any metric space, in particular for finitely
generated groups). The arguments involve some elementary convex analysis in
euclidean spaces. Similar results, proven using similar methods, can be found
in the literature [2, 14, 17]. We present the self-contained proofs here for
the sake of completeness and also due to certain less standard variations that
we seem to require for our specific application.

Recall that $\Gamma$ is a finitely generated abelain group of the form
$\Gamma=\mathbb{Z}^{d}\times G$, where $G$ is a finite abelian group. Let
$P_{\Gamma,\mathbb{Z}^{d}}:\Gamma\to\mathbb{Z}^{d}$ and
$P_{\Gamma,G}:\Gamma\to G$ denote the obvious projection maps given by

$P_{\Gamma,\mathbb{Z}^{d}}(v,g)=v\mbox{ for }v\in\mathbb{Z}^{d}\mbox{ and
}g\in G$

and

$P_{\Gamma,G}(v,g)=g\mbox{ for }v\in\mathbb{Z}^{d}\mbox{ and }g\in G$

On the group $\Gamma=\mathbb{Z}^{d}\times G$ we consider the metric
$\mathrm{dist}_{\Gamma}:\Gamma\times\Gamma\to[0,+\infty)$ given by:

$\mathrm{dist}_{\Gamma}\left(\gamma_{1},\gamma_{2}\right)=\mathrm{dist}_{\mathbb{R}^{d}}(P_{\Gamma,\mathbb{Z}^{d}}(\gamma_{1}),P_{\Gamma,\mathbb{Z}^{d}}(\gamma_{2}))+\delta(\gamma_{1},\gamma_{2}),\leavevmode\nobreak\
\gamma_{1},\gamma_{2}\in\Gamma,$

where
$\mathrm{dist}_{\mathbb{R}^{d}}:\mathbb{R}^{d}\times\mathbb{R}^{d}\to[0,+\infty)$
is the Euclidean distance in $\mathbb{R}^{d}$ and

$\delta(\gamma_{1},\gamma_{2})=\begin{cases}0&\gamma_{1}=\gamma_{2}\\\
1&\mbox{otherwise.}\end{cases}$

######  Definition 6.6.

Let $C\subseteq\Gamma$ be a subset of $\Gamma$. The _Voroni cell_ of $c\in C$
with respect to $C$, denoted by $V(c,C)$, is defined be the set of point in
$v\in\Gamma$ such that $\mathrm{dist}_{\Gamma}$ distance between $c$ and $v$
is smaller than the distance to any other point in $C$:

$V(c,C)=\left\\{\gamma\in\Gamma:\leavevmode\nobreak\
\mathrm{dist}_{\Gamma}(c,\gamma)\leq\inf_{\tilde{c}\in
C}\mathrm{dist}_{\Gamma}(\tilde{c},\gamma)\right\\}.$

The _Voroni diagram_ of $C$ is the collection of Voronoi cells.

Given $R>0$ the _$R$ -truncated Voronoi cell_ of $c\in C$ with respect to $C$,
denoted by $V_{R}(c,C)$ is the intersection of the Voronoi cell of $c$ with
the ball of $\mathrm{dist}_{\Gamma}$ radius $R$ around $C$:

$V_{R}(c,C)=\left\\{\gamma\in V(c,C)\leavevmode\nobreak\ :\leavevmode\nobreak\
\mathrm{dist}_{\Gamma}(c,\gamma)\leq R\right\\}.$

The _$R$ -truncated Voronoi diagram_ of $C$ is the collection of $R$-truncated
Voronoi cells.

In general, the Voronoi cells corresponding to a subset $C$ and also the
$R$-truncated Voronoi cells are not disjoint because it could happen that for
some $v\in\Gamma$ there exist $c_{1},c_{2}\in C$ with $c_{1},\neq c_{2}$ such
that

$\mathrm{dist}_{\Gamma}(c_{1},\gamma)=\mathrm{dist}_{\Gamma}(c_{1},\gamma)=\inf_{\tilde{c}\in
C}\mathrm{dist}_{\Gamma}(\tilde{c},\gamma)\leq R.$

For our application we would like to extract a partial tiling from the
$R$-truncated Vorinoi diagram. For this purpose we need to “disjointify” the
cells.

######  Definition 6.7.

Fix an arbitrary total order $\prec_{\Gamma}$ on the group $\Gamma$, with the
property that whenever
$\gamma_{1},\tilde{\gamma}_{1},\gamma_{2},\tilde{\gamma}_{2}\in\Gamma$ satisfy
that
$P_{\Gamma,\mathbb{Z}^{d}}(\gamma_{1})=P_{\Gamma,\mathbb{Z}^{d}}(\tilde{\gamma}_{1})\neq
P_{\Gamma,\mathbb{Z}^{d}}(\gamma_{2})=P_{\Gamma,\mathbb{Z}^{d}}(\tilde{\gamma}_{2})$
and $\gamma_{1}\prec_{\Gamma}\gamma_{2}$ then
$\tilde{\gamma}_{1}\prec\tilde{\gamma}_{2}$. We do not require that the total
order $\prec_{\Gamma}$ is invariant, as this can only be done in the case
where $G$ is the trivial group, otherwise $\Gamma$ has non-trivial torsion,
hence is not orderable.

The _disjointified $R$-truncated Voronoi cell_ of $c\in C$, denoted by
$\overline{V}_{R}(c,C)$ is the subset of $V_{R}(c,C)$ obtained by “breaking
ties according to $\prec_{\Gamma}$”:

$\overline{V}_{R}(c,C)=\left\\{\gamma\in V_{R}(c,C)\leavevmode\nobreak\
:\leavevmode\nobreak\ (\gamma-c)\prec_{\Gamma}(\gamma-\tilde{c})\mbox{ for
every }\tilde{c}\in M(\gamma,C)\right\\},$

where $M(\gamma,C)\subseteq C$ is the set is the set of minimizers of
$\mathrm{dist}_{\Gamma}(\gamma,\cdot)$ in $C$:

$M(\gamma,C)=\left\\{c\in C\leavevmode\nobreak\ :\leavevmode\nobreak\
\mathrm{dist}_{\Gamma}(\gamma,c)\leq\inf_{\tilde{c}\in
C}\mathrm{dist}_{\Gamma}(\gamma,\tilde{c})\right\\}.$

The _disjointified $R$-truncated Voronoi digaram of $C\subset\Gamma$_, denoted
$\overline{V}(C)$ is the collection

$\overline{V}(C)=\\{\overline{V}_{R}(c,C)\leavevmode\nobreak\
:\leavevmode\nobreak\ c\in C\\}$

of disjointified $R$-truncated Voronoi cells.

######  Definition 6.8.

Call a finite set $F\Subset\Gamma$ _convex_ if there exists a compact convex
subset $\tilde{F}\subset\mathbb{R}^{d}$ such that
$F=(\tilde{F}\cap\mathbb{Z}^{d})\times G$.

######  Lemma 6.9.

For any $C\subseteq\Gamma$ and $R>0$ we have:

  1. (1)

The disjointified $R$-truncated Voronoi diagram of $C$ is a partial tiling of
$\Gamma$.

  2. (2)

$(C+B_{R}^{\Gamma})\subseteq\biguplus_{c\in
C}\overline{V}_{R}(c,C)=\bigcup_{c\in C}V_{R}(c,C)$, where

$B_{R}^{\Gamma}=\left\\{\gamma\in\Gamma\leavevmode\nobreak\
:\leavevmode\nobreak\
\mathrm{dist}_{\mathbb{R}^{d}}(0,P_{\Gamma,\mathbb{Z}^{d}}(\gamma))\leq
R\right\\}.$

  3. (3)

If $C\subset\Gamma$ is a $(\\{0\\}\times G)$-separated set then every $c\in
C$, the $R$-truncated Voronoi cell $V_{R}(c,C)\Subset\Gamma$ is convex.

###### Proof.

  1. (1)

Fix $C\subseteq\Gamma$ and $R>0$. For every $c\in c$ the disjointified
$R$-truncated Voronoi cell $\overline{V}_{R}(c,C)$ is a finite, because the
number of elements in $\Gamma$ whose distance from $c$ is bounded by $R$ is
finite. We need to prove that
$\overline{V}_{R}(c_{1},C)\cap\overline{V}_{R}(c_{2},C)$ whenever
$c_{1},c_{2}\in C$ and $c_{1}\neq c_{2}$. Choose any district elements
$c_{1},c_{2}\in C$. Suppose that
$v\in\overline{V}_{R}(c_{1},C)\cap\overline{V}_{R}(c_{1},C)$. In particular,
$c_{1},c_{2}\in M(\gamma,C)$. Since $c_{1}\neq c_{2}$ it follows that
$v-c_{1}\neq v-c_{2}$ so either $v-c_{1}\prec_{\Gamma}v-c_{2}$ or
$v-c_{2}\prec_{\Gamma}v-c_{1}$. In the first case we have that
$v\not\in\overline{V}_{R}(c_{2},C)$ and in the second case we have that
$v\not\in\overline{V}_{R}(c_{1},C)$, either way we have a contradiction.

  2. (2)

If $v\in C+B_{R}^{\Gamma}$ then there exists $c\in C$ such that
$\mathrm{dist}_{\mathbb{R}^{d}}(P_{\Gamma,\mathbb{Z}^{d}}(v)\leq R$. It
follows that $v\in\overline{V}_{R}(\tilde{c},C)$, where $\tilde{c}\in M(v,C)$
is the element of $M(v,c)$ such that $(v-\tilde{c})$ is maximal with respect
to $\prec_{\Gamma}$.

  3. (3)

The fact that every cell of the disjointified $R$-truncated Voronoi cell
$\overline{V}_{R}(c,C)\Subset\Gamma$ is convex follows from the classical and
well-known that every cell of a Voronoi diagram of a discrete subset of
$\mathbb{R}^{d}$ is a convex polygon.

∎

The following simple lemma is closely related to Lemma 3.5 in [17], except
that in [17] the Voronoi diagram of syndetic sets was considered, rather than
the disjointified $R$-truncated Voronoi diagram of an arbitrary subset of
$\Gamma$ (also in [17] only the case $\Gamma=\mathbb{Z}^{d}$ was considered,
though this it is a trivial modification to consider the case
$\Gamma=\mathbb{Z}^{d}\times G$, with $G$ finite):

######  Lemma 6.10.

For any $R>0$ the function
$V_{R}:\\{0,1\\}^{\Gamma}\to\mathit{PTilings}(\Gamma)$ that sends $V$ to the
disjointified $R$-truncated Voronoi diagram of (the set corresponding to) $z$
is continuous and equivariant.

###### Proof.

By Lemma 6.9 $\overline{V}_{R}(z)\in\mathit{PTilings}(\Gamma)$ for every $z\in
Z$. Equivariance follows directly from the fact that Euclidean distances are
invariant under translations in $\mathbb{R}^{d}$. ∎

The following result is implicitly contained in [17], and also in [2], where
it was shown that for any $\mathbb{Z}^{d}$ subshift $X$ we have
$h(X)=\lim_{n\to\infty}\frac{1}{|C_{n}|}\log|\mathcal{L}_{C_{n}}(X)|$ for any
sequence $(C_{n})_{n=1}^{\infty}$ of bounded convex subsets in
$\mathbb{Z}^{d}$ such that for every $r>0$ there exist $n_{0}\in\mathbb{N}$ so
that $C_{n}$ contains a ball or radius $r$ for all $n\geq n_{0}$. A similar
statement (with a similar proof) can also be found in [14, Lemma 3.5]. Again,
we include a proof for completeness.

######  Lemma 6.11.

For any $K\Subset\Gamma$ and any $\epsilon>0$ there exists a finite set
$F_{0}\Subset\Gamma$ such that any convex set $F\Subset\Gamma$ with
$F_{0}\subseteq F$ is $(K,\epsilon)$-invariant.

For a subset $A\Subset\mathbb{R}^{d}$ and $t\in(0,\infty)$ we use the notation
$tA=\left\\{tv\leavevmode\nobreak\ :\leavevmode\nobreak\ v\in A\right\\}$.
Also, for $t>0$ let $B^{d}_{t}\subseteq\mathbb{R}$ denote the Euclidean ball
of radius $t$ around $0$. We denote the Lebesgue measure of a measurable set
$A\subseteq\mathbb{R}^{d}$ by $m_{d}(A)$. For a set
$\tilde{F}\subseteq\mathbb{R}^{d}$, $\partial\tilde{F}$ denotes the boundary
of $\tilde{F}$ with respect to the usual topology on $\mathbb{R}^{d}$. Given
$r_{0}>0$ we denote

$\partial_{r_{0}}\tilde{F}=\partial\tilde{F}+B^{d}_{r_{0}}.$

The proof of Lemma 6.11 is based on the following lemma about convex sets in
$\mathbb{R}^{d}$:

######  Lemma 6.12.

For any convex compact set $\tilde{F}\subseteq\mathbb{R}^{d}$ that contains
$B^{d}_{r}$ , the Euclidean ball of radius $r$ around $0$ and any $0<r_{0}<r$,
the following inclusion holds:

$\partial_{r_{0}}\tilde{F}\subseteq\overline{\left(1+\frac{r_{0}}{r}\right)\tilde{F}\setminus\left(1-\frac{r_{0}}{r}\right)\tilde{F}}.$
(3)

Thus,

$m_{d}(\partial_{r_{0}}\tilde{F})\leq\left((1+\frac{r_{0}}{r})^{d}-(1-\frac{r_{0}}{r})^{d}\right)m_{d}(\tilde{F}).$

###### Proof.

By assumption, $B^{d}_{r}\subseteq\tilde{F}$, so
$B^{d}_{r_{0}}\subseteq\frac{r_{0}}{r}\tilde{F}$. It follows that

$\partial_{r_{0}}\tilde{F}=\partial\tilde{F}+B^{d}_{r_{0}}\subseteq\partial\tilde{F}+\frac{r_{0}}{r}\tilde{F}\subseteq\tilde{F}+\frac{r_{0}}{r}\tilde{F}=\left(1+\frac{r_{0}}{r}\right)\tilde{F}.$

In the last equality we use the fact that for a convex set
$A\subseteq\mathbb{R}^{d}$ and $t_{1},t_{2}>0$ it holds that
$t_{1}A+t_{2}A=(t_{1}+t_{2})A$.

Also, by similar considerations for any $t<\left(1-\frac{r_{0}}{r}\right)$ we
have that

$t\tilde{F}+B^{d}_{r_{0}}\subseteq
t-\frac{r_{0}}{r}\tilde{F}\subseteq\tilde{F}\setminus\partial\tilde{F}.$

It follows that
$\partial_{r_{0}}\tilde{F}\subseteq\overline{\mathbb{R}^{d}\setminus\left(1-\frac{r_{0}}{r}\right)\tilde{F}}$.
This proves that

$\partial_{r_{0}}\tilde{F}\subseteq\overline{\left(1+\frac{r_{0}}{r}\right)\tilde{F}\setminus\left(1-\frac{r_{0}}{r}\right)\tilde{F}}.$

Thus (because the boundary of convex sets has zero Lebesgue measure),

$m_{d}\left(\partial_{r_{0}}\tilde{F}\right)\leq
m_{d}\left(\left(1+\frac{r_{0}}{r}\right)\tilde{F}\right)-m_{d}\left(\left(1-\frac{r_{0}}{r}\right)\tilde{F}\right).$

From this it follows that

$m_{d}(\partial_{r_{0}}\tilde{F})\leq\left((1+\frac{r_{0}}{r})^{d}-(1-\frac{r_{0}}{r})^{d}\right)m_{d}(\tilde{F}).$

∎

For $k\in\mathbb{N}$ we denote

$B_{k}=\\{-k,\ldots,k\\}^{d}\times G\Subset\Gamma.$

###### Proof of Lemma 6.11.

For any finite subset $K\Subset\Gamma$ we can find $r_{0}>0$ such that
$K\subseteq(B_{r_{0}}^{d}\cap\mathbb{Z}^{d})\times G$. For such $r_{0}>0$, and
any convex set $\tilde{F}\subseteq\mathbb{R}^{d}$ it holds:

$|\partial_{K}\left((\tilde{F}\cap\mathbb{Z}^{d})\times G\right)|\leq|G|\cdot
m_{d}(\partial_{r_{0}}\tilde{F}).$

Also, for any convex set $\tilde{F}\subseteq\mathbb{R}^{d}$:

$\left||G|\cdot m_{d}(\tilde{F})-|(\tilde{F}\cap\mathbb{Z}^{d})\times
G|\right|\leq m_{d}(\partial_{\sqrt{d}}\tilde{F}).$

Let $F\subset\Gamma$ be a convex set that contains $B_{j}$. By our definition
of a convex set in $\Gamma$, there exists a convex set
$\tilde{F}\subset\mathbb{Z}^{d}$ so that
$F=(\tilde{F}\cap\mathbb{Z}^{d})\times G$. Since $B_{j}\subset F$. If $j$ is
sufficiently big it follows that $B_{r}^{d}\subseteq\tilde{F}$.

It thus suffices to prove that for any $r_{0}>0$ and any $\delta>0$ there
exists $r>0$ such that for any compact convex subset
$\tilde{F}\subseteq\mathbb{R}^{d}$ that contains the Euclidean ball of radius
$r$ around $0$ the following inequality holds:

$m_{d}(\partial_{r_{0}}\tilde{F})\leq\delta\cdot m_{d}(\tilde{F}).$

Fix $r_{0}>0$ and $\delta>0$. Since

$\lim_{r\to\infty}(1+\frac{r_{0}}{r})^{d}-(1-\frac{r_{0}}{r})^{d}=0,$

we can choose $r>0$ sufficiently big so that

$(1+\frac{r_{0}}{r})^{d}-(1-\frac{r_{0}}{r})^{d}<\delta.$

Then by Lemma 6.12 it follows that
$m_{d}(\partial_{r_{0}}\tilde{F})\leq\delta\cdot m_{d}(\tilde{F})$ for any
convex set $\tilde{F}$ that contains $B_{r}^{d}$. ∎

We now proceed to state and prove results needed to ensure that the cells of
the disjointified $R$-truncated Voronoi diagram have “sufficiently small
external boundary”, provided that $R$ is sufficiently big.

######  Lemma 6.13.

For any convex set $A\subseteq\mathbb{R}^{d}$ and any $0<r_{0}<R$ such that
$0\in A$ the following inequality holds:

$m_{d}\left(A\cap B_{R+r_{0}}\setminus
B_{R-{r_{0}}}\right)\leq\left(\frac{(R+r_{0})^{d}-(R-r_{0})^{d}}{(R-r_{0})^{d}}\right)m_{d}(A).$
(4)

###### Proof.

Let for $t>0$ let $S^{d-1}\subset\mathbb{R}^{d}$ denote the unit sphere in
$\mathbb{R}^{d}$, namely, $S^{d-1}=\partial B_{1}^{d}$. Let
$A\subseteq\mathbb{R}^{d}$ be a convex set such that $0\in A$ and $0<r_{0}<R$.
For $t>0$, consider the set $A_{t}\subseteq S^{d-1}$ given by:

$A_{t}=\left\\{v\in S^{d-1}\leavevmode\nobreak\ :\leavevmode\nobreak\ tv\in
A\right\\}.$

Given a Borel subset $B\subseteq S^{d-1}$ let $H_{d-1}(B)$ denote the
$d-1$-dimensional Hausdorff measure of $B$. Then there exists a constant $c>0$
(that depends on the normalization of $H_{d-1}$) so that:

$m_{d}(A)=c\int_{0}^{\infty}t^{d-1}H_{d-1}(A_{t})dt.$

and so

$m_{d}\left(A\cap B_{R+r_{0}}\setminus
B_{R-{r_{0}}}\right)=c\int_{R-r_{0}}^{R+r_{0}}t^{d-1}H_{d-1}(A_{t})dt.$

Because $0\in A$ and $A$ is convex, it follows that for every $0<t_{1}<t_{2}$
we have $A_{t_{2}}\subseteq A_{t_{1}}$. Thus,

$m_{d}(A)\geq
c\int_{0}^{R-r_{0}}t^{d-1}H_{d-1}(A_{R-r_{0}})dt=\frac{cH_{d-1}(A_{R-r_{0}})}{d}\cdot(R-r_{0})^{d}.$

and

$m_{d}\left(A\cap B_{R+r_{0}}\setminus B_{R-{r_{0}}}\right)\leq
c\int_{R-r_{0}}^{R+r_{0}}t^{d-1}H_{d-1}(A_{R-r_{0}})dt=\frac{cH_{d-1}(A_{R-r_{0}})}{d}\cdot\left((R+r_{0})^{d}-(R-r_{0})^{d}\right).$

The proof of the lemma follows directly by combining these inequalities. ∎

######  Lemma 6.14.

For any $K\Subset\Gamma$ and $\epsilon>0$ there exists a finite set
$F\Subset\Gamma$ and $R_{0}>0$ such that for any $F$-separated set
$C\subseteq\Gamma$ and any $R>R_{0}$, the disjointified $R$-truncated Voronoi
diagram of $C$ is $(K,\epsilon)$-invariant.

###### Proof.

Fix $K\Subset\Gamma$ and $\epsilon>0$. By Lemma 6.11 there exists
$F_{0}\Subset\Gamma$ so that any convex set that contains $F_{0}$ is
$(K,\epsilon)$-invariant. Since the property of being $(K,\epsilon)$-invariant
remains unchanged under translations, it is clear that any any convex set that
contains $v+F_{0}$ for some $v\in\Gamma$ is also $(K,\epsilon)$-invariant.
Choose
$R_{1}>\max\\{\mathrm{dist}_{\mathbb{R}^{d}}(0,P_{\Gamma,\mathbb{Z}^{d}}(v))\leavevmode\nobreak\
:\leavevmode\nobreak\ v\in F_{0}\\}$ Let $F\Subset\Gamma$ be a finite set such
that $(\\{0\\}\times G)\subseteq F$, and also so that $F$ contains the set
$B_{R_{1}}^{\Gamma}=\left\\{\gamma\in\Gamma\leavevmode\nobreak\
:\leavevmode\nobreak\
\mathrm{dist}_{\mathbb{R}^{d}}(0,P_{\Gamma,\mathbb{Z}^{d}}(v))\leq
R_{1}\right\\}$. Note that since $F\Subset\Gamma$ such that $(\\{0\\}\times
G)\subseteq F$, it follows that any $F$-separated set $C\subseteq\Gamma$ is
also $(\\{0\\}\times G)$-separated. Choose $R_{0}>2R_{1}$. By Lemma 6.9, every
cell $\overline{V}_{R}(c,C)$ is convex, and
$c+F\subseteq\overline{V}_{R}(c,C)$, so $\overline{V}_{R}(c,C)$ is
$(K,\epsilon)$-invariant.

∎

######  Lemma 6.15.

There exists $F_{0}\Subset\Gamma$ so that for any $K\Subset\Gamma$ and any
$\epsilon>0$ there exists $R_{0}>0$ such that for any $R>R_{0}$ and any
$F_{0}$-separated $C\subseteq\Gamma$ the disjointified $R$-truncated Voronoi
diagram of $C$ has $(K,\epsilon)$-small exterior boundary.

###### Proof.

Using Lemma 6.14 we choose $F_{0}\Subset\Gamma$ and $R_{1}$ so that for any
$F_{0}$-separated set $C\subseteq\Gamma$ and any $R>R_{1}$, the size of any
cell in the disjointified $R$-truncated Voronoi diagram of $C$ is at least
half the size of the (non-disjointified) $R$-truncated Voronoi cell. Given
$K\Subset\Gamma$, we can find $r_{0}>0$ such that
$K\subseteq(B_{r_{0}}^{d}\cap\mathbb{Z}^{d})\times G$. Thus, if
$F\Subset\Gamma$ is a cell of the $R$-truncated Voronoi diagram of $C$, there
exists a compact convex set $\tilde{F}\subseteq\mathbb{R}^{d}$ such that
$F=(\tilde{F}\cap\mathbb{Z}^{d})\times G$. The exterior $K$-boundary of $F$ is
contained in

$\tilde{F}\cap(B_{R+r_{0}}^{d}\setminus
B_{R-r_{0}}^{d})\cap\mathbb{Z}^{d})\times G.$

As in the proof of Lemma 6.11, it thus suffices to prove that for any
$\delta>0$, provided that $R$ is sufficiently big, we have

$m_{d}\left(\tilde{F}\cap(B_{R+r_{0}}^{d}\setminus
B_{R-r_{0}}^{d})\right)\leq\delta m_{d}(\tilde{F}).$

This follows from Lemma 6.13, provided that $R$ is big enough so that

$\frac{(R+r_{0})^{d}-(R-r_{0})^{d}}{(R-r_{0})^{d}}<\delta.$

∎

###### Proof of Proposition 6.4:.

Let $\epsilon>0$ and $K\Subset\Gamma$ be given. By Lemma 6.14 there exists
$F\Subset\Gamma$ and $R_{0}>0$ such that for any $F$-separated set
$C\subseteq\Gamma$ and any $R>R_{0}$, the disjointified $R$-truncated Voronoi
diagram of $C$ is $(K,\epsilon)$-invariant. By further enlarging $F$, we can
assume that $F_{0}\subseteq F$, where $F_{0}\Subset\Gamma$ is as in Lemma
6.15, and that $F$ is symmetric and so that $B_{R_{1}}\subseteq F$, where
$R_{1}=2\max\\{\mathrm{dist}_{\mathbb{R^{d}}}(0,v)\leavevmode\nobreak\
:\leavevmode\nobreak\ v\in K\\}$ and
$B_{R_{1}}=\\{v\in\Gamma\leavevmode\nobreak\ :\leavevmode\nobreak\
\mathrm{dist}_{\mathbb{R}^{d}}(0,P_{\Gamma,\mathbb{Z}^{d}}(v))\leq R_{1}\\}$.

Let $P=(F+F)\setminus\\{0\\}$. Now let $X$ be a $\Gamma$-subshift,
$W\Subset\Gamma$ and let $\mathcal{F}\subseteq\mathcal{L}_{W}(X)$ be a set of
patterns so that $x_{W}\not\in\mathcal{F}$ for any $x\in X$ such that
$\mathit{stab}(x)\cap P=\emptyset$. By Lemma 3.3, there exists a clopen set
$C\subset X$ such that $C\cap\sigma_{v}(C)=\emptyset$ for every $v\in P$ and
so that for every $x\in X$ either there exists $v\in P\cup\\{0\\}=B_{k}$ such
that $\sigma_{v}(x)\in C$ or $x_{W}\in\mathcal{F}$.

Define $\alpha:X\to\\{0,1\\}^{\Gamma}$ by

$\alpha(x)_{v}=\begin{cases}1&\sigma_{v}(x)\in C\\\ 0&\mbox{
otherwise}.\end{cases}$

It is clear that $\alpha:X\to\\{0,1\\}^{\Gamma}$ is equivariant. Continuity of
$\alpha$ follows from the fact that $C$ is a clopen set.

Because $C\cap\sigma_{v}(C)=\emptyset$ for every $v\in P$ it follows that for
every $x\in X$ $\alpha(x)$ corresponds to an $F$-separated.

Using Lemma 6.15 we can find $R>\max\\{R_{0},R_{1}\\}$ so that for any
$F$-separated $C\subseteq\Gamma$ the disjointified $R$-truncated diagram of
$C$ has $(W,\epsilon_{1})$-small exterior boundary.

Let $\tau:\\{0,1\\}^{\Gamma}\to\mathit{PTilings}(\Gamma)$ be the map given by
$\tau(z)=\overline{V}_{R}(z)$ be the map that assigns to every
$z\in\\{0,1\\}^{\Gamma}$ the disjointified $R$-truncated diagram of
$\alpha(x)\in\\{0,1\\}^{\Gamma}$ (interpreted as a subset of $\Gamma$). By
Lemma 6.10 $\tau:\\{0,1\\}^{\Gamma}\to\mathit{PTilings}(\Gamma)$ is continuous
and equivariant. For every $x\in X$, since every $\alpha(x)$ corresponds to an
$F$-separated set, by the choice of $F$ it follows that $\tau(\alpha(x))$ is a
pointed $(K,\epsilon)$-invariant tiling. If $v\not\in\bigcup\tau(\alpha(x))$
then $\mathrm{dist}_{\mathbb{R}^{d}}(v,w)\geq R$ for every $w\in\Gamma$ such
that $\alpha(x)_{w}=1$. This means that $\sigma_{v}(x)\not\in\bigcup_{u\in
P\cup\\{0\\}}\sigma_{u}(C)$, so $\sigma_{-v}(x)_{W}\in\mathcal{F}$. This
proves that property $1$ is satisfied. Because $B_{R_{1}}\subseteq F$ and
$\alpha(x)$ is $F$-separated, it follows that whenever $\alpha(x)_{v}=1$ then
the unique $T\in\tau(\alpha(x))$ corresponding to the disjointified
$R$-truncated Voronoi cell of $v$ contains $v+K$. This proves that property
$2$ is satisfied. By the choice of $R$ using Lemma 6.15, the disjointified
$R$-truncated diagram of the set corresponding to $\alpha(x)$ has
$(W,\epsilon_{1})$-small exterior boundary for every $x\in X$. This proves
that property $3$ is satisfied. ∎

##  7\. Good marker patterns in the rage via the map extension property

One of the key ideas in Krieger’s proof of his embedding theorem is to
designate a special pattern in the range of the embedding to mark the
occurrences of some clopen set in the domain. These “marker patterns” need to
satisfy several condition. In particular, they need to be “locally
identifyable”, which in particular requires them to have no self overlaps.
Also, the subshift obtained from $Y$ by forbidding this marker pattern needs
to have enough entropy“big enough to embed $X$”. The purpose of this section
is to formulate and prove a lemma that guarantees suitable marker patterns in
the domain. The slightly involved formulation is given in Lemma 7.3.

We first state a basic result about the existence of patterns without self-
overlaps.

######  Definition 7.1.

Given $F\Subset\Gamma$, $v\in\Gamma$ and a pattern $w\in A^{F}$, we say that
$w$ _has a self-overlap $v$_ if

$w_{F\cap(v+F)}=\sigma_{v}(w)_{F\cap(v+F)}.$

We say that $w^{(1)},w^{(2)}\in A^{F}$ have an overlap at $v\in\Gamma$ if

$w^{(1)}_{F\cap(v+F)}=\sigma_{v}(w^{(2)})_{F\cap(v+F)}.$

######  Lemma 7.2.

Let $G$ be a finite abelian group, $d\geq 1$ and $\Gamma=\mathbb{Z}^{d}\times
G$, and for $k\in\mathbb{N}$ let

$B_{k}=\\{-k,\ldots,\ldots,k\\}^{d}\times G\Subset\Gamma.$ (5)

and

$Q_{k}=B_{k}\setminus B_{\lfloor k/10\rfloor}.$

and let $Y$ be a non-trivial strongly irreducible $\Gamma$-subshift of finite
type. Then there exists $n_{0}$ such that for every $n\geq n_{0}$ there exist
$w\in\mathcal{L}_{Q_{n}}(Y)$ that has no self-overlaps in
$B_{n}\setminus\mathit{Ker}(Y)$.

Similar results have appeared in the literature. For instance in [22] patterns
without self-overlaps have been constructed for strongly irreducible
$\mathbb{Z}^{2}$-subshifts. Also see [15] where the existence of non-
overlapping pattern is established using a non-constructive argument using
only positive positive entropy. We briefly sketch a proof below.

###### Proof.

Let $Y$ be a non-trivial strongly irreducible $\Gamma$-subshift of finite
type. In particular, $Y$ is topologically mixing and non-trivial so
$\mathit{Ker}(Y)$ is a finite subgroup of $\Gamma$. Since $Y$ is strongly
irreducible subshift of finite type there exists $N\in\mathbb{N}$ so that for
any $m\in\mathbb{N}$, any set $F\Subset\Gamma$ and any $B_{n+N}$-separated set
$K$ and any $f:K\to\mathcal{L}_{B_{m}}(Y)$ there exists $x\in X$ with
$\sigma_{v}(x)_{B_{m}}=f(v)$ for all $v\in K$. Choose $m\in\mathbb{N}$
sufficiently big, and then choose $n\in\mathbb{N}$ much bigger. Since $B_{m}$
is a monotile for $\Gamma$, there is a $B_{n+N}$ separated subset $K_{n,m}$ of
$Q_{n}$ of size at least $\frac{|Q_{n}|-|\partial_{B_{m}}Q_{n}|}{|B_{m}|}$.
Choose $f\in\mathcal{L}_{B_{m}}(Y)^{K_{n,m}}$ uniformly at random. In other
words, for every $v\in K_{n,m}$ choose $f(v)\in\mathcal{L}_{B_{m}}(Y)$
uniformly at random, so that the random variables $(f(v))_{v\in K_{n,m}}$ are
jointly independent. Let $w\in\mathcal{L}_{B_{m}}(Y)$ be such that
$\sigma_{v}(w)_{B_{m}}=f(v)$ for every $v\in K_{n,m}$. If $m$ is sufficiently
big, there exists $p<1$ such that the probability that a uniformly chosen
$w\in\mathcal{L}_{B_{m}}(Y)$ has a self-overlap in
$B_{2N}\setminus\mathit{Ker}(Y)$ is at most $p$. Also if $m$ is sufficiently
big, the probability that independently chosen
$w^{(1)},w^{(2)}\in\mathcal{L}_{B_{m}}(Y)$ have an overlap in $B_{\lfloor
m/w\rfloor-N}$ is at most $p$. It follows that for any $v\in
B_{n}\setminus\mathit{Ker}(Y)$ the probability that the randomly chosen $w$
has a self-overlap $v$ is at most
$p^{\frac{|Q_{n-m}\cap(v+Q_{n-m})|}{|B_{m}|}}$. Since $Q_{n-m}\cap(v+Q_{n-m})$
contains a translate of $B_{\lfloor n/3\rfloor}$ for every $v\in B_{m}$, it
follows that the probability that $w$ has an overlap at $v\in
B_{m}\setminus\mathit{Ker}(Y)$ is at most $p^{(n-m)/3m}$. By a union-bound,
the probability that $w$ has a self-overlap in $B_{n}\setminus\mathit{Ker}(Y)$
is bounded from above by $(2n+1)^{d}p^{(n-m)/3m}$, which tends to $0$ as
$n\to\infty$, for fixed $m$. ∎

######  Lemma 7.3.

Let $\Gamma$ be an infinite finitely generated abelian group, let $Y$ be a
non-trivial $\Gamma$-subshift with the map extension property, and let
$\hat{Y}\subset Y$ be a (possibly empty) closed, $\Gamma$-invariant set
strictly contained in $Y$. For any given $\epsilon>0$, and any finite set
$F_{0}\Subset\Gamma$ there exist:

  * •

A subshift $S\subset Y$ with $\hat{Y}\subseteq S$.

  * •

A retraction map $\tilde{r}:Y\to S$.

  * •

A map $\kappa:S\times\\{0,1\\}^{\Gamma}\to Y$.

  * •

A finite symmetric set $F\Subset\Gamma$ such that $F_{0}\Subset F$.

  * •

Patterns $w^{(0)},w^{(1)}\in\mathcal{L}_{F}(Y)$ such that
$w^{(0)}\not\in\mathcal{L}_{F}(S)$.

So that the following hold:

  1. (1)

For any $y\in Y$ if $\tilde{r}(y)_{0}\neq y_{0}$ then there exists $w\in F$
such that $\sigma_{w}(y)_{F}=w^{(0)}$. In particular, if $y\in Y$ and
$y_{F+F}\in\mathcal{L}_{F+F}(S)$ then $\tilde{r}(y)_{0}=y_{0}$.

  2. (2)

For every $y\in S$ and $z\in\\{0,1\\}^{\Gamma}$ if $\tilde{y}=\kappa(y,z)$
then $\tilde{y}_{F}=w^{(0)}$ if and only if $y_{F}=w^{(1)}$ and $z_{0}=1$.

  3. (3)

For every $y\in S$ and $z\in\\{0,1\\}^{\Gamma}$ if $\tilde{y}=\kappa(y,z)$ and
$z_{v}\neq 1$ for all $v\in F$ then $\tilde{y}_{0}=y_{0}$

  4. (4)

For any $\Gamma_{0}\leq\Gamma$, if $Y_{\Gamma_{0}}\neq\emptyset$ then
$S_{\Gamma_{0}}\neq\emptyset$.

  5. (5)

For any $\Gamma_{0}\leq\Gamma$ it holds that
$\mathit{Ker}(Y_{\Gamma_{0}})=\mathit{Ker}(S_{\Gamma_{0}})$ and and
$h(\overline{S}_{\Gamma_{0}})\geq h(\overline{Y}_{\Gamma_{0}})-\epsilon$.

###### Proof.

By the structure of finitely generated abelian groups we can assume that
$\Gamma=\mathbb{Z}^{d}\times G$, where $G$ is a finite abelian group and
$d\geq 1$. Let $Y$ be a non-trivial $\Gamma$-subshift with the map extension
property, and let $\hat{Y}\subset Y$ be a (possibly empty) closed,
$\Gamma$-invariant set such that $\hat{Y}\neq Y$. Note that since $Y$ is a
non-trivial subshift with the map extension property, it is topologically
mixing and in particular $\mathit{Ker}((Y)$ is finite hence contained in
$\\{0\\}\times G\leq\Gamma$. Replacing $\Gamma$ with $\Gamma/\mathit{Ker}(Y)$,
we can conveniently assume that $\mathit{Ker}(Y)=\\{0\\}$ Fix any $\epsilon>0$
and any finite set $F_{0}\Subset\Gamma$. For any $n\in\mathbb{N}$ let
$B_{n},Q_{n}\Subset\Gamma$ be defined as in Lemma 7.2, and let

$W_{n,k}=\left\\{w\in\mathcal{L}_{B_{n}}(Y)\leavevmode\nobreak\
:\leavevmode\nobreak\ w_{Q_{n}}=w^{(1)}_{Q_{n}}\right\\}.$

Since $Y$ has the map extension property, by Proposition 4.22, $Y$ is strongly
irreducible. By Lemma 7.2, for sufficiently big $n\in\mathbb{N}$, we can find
a pattern $w^{(1)}\in\mathcal{L}_{B_{n}}(Y)$ such that $w^{(1)}_{Q_{n}}$ has
no self-overlaps in $B_{n}$. Because $Y$ is strongly irreducible, we can
choose $n\in\mathbb{N}$ sufficiently big and $\frac{1}{20}n<k<\frac{1}{11}n$
so that the following are also satisfied:

  * •

For every $\hat{w}\in\mathcal{L}_{Q_{n}}(Y)$ and
$\tilde{w}\in\mathcal{L}_{B_{k}}(Y)$, there exists
$w\in\mathcal{L}_{B_{n}}(Y)$ so that $w_{Q_{n}}=\hat{w}$ and
$w_{B_{k}}=\tilde{w}$.

  * •

$F_{0}\subseteq B_{\lfloor n/11\rfloor}$.

  * •

$|\mathcal{L}_{B_{k}}(Y)\setminus\mathcal{L}_{B_{k}}(\hat{Y})|\geq|B_{n}|+2$.

  * •

$\log\left(\frac{|W_{n,k}|}{|W_{n,k}|-1}\right)\leq\epsilon,$

The properties above grantees that there exists two distinct words
$\tilde{w}^{(0)},\tilde{w}^{(2)}\in\mathcal{L}_{B_{k}}(Y)\setminus\mathcal{L}_{B_{k}}(\tilde{Y})$
that do not occur in $w^{(1)}$, and also (under our assumption that
$\mathit{Ker}(Y)=\\{0\\}$) and so that
$\sigma_{v}(\tilde{w}^{(i)})\neq\tilde{w}^{(i)}$ for every $v\in\\{0\\}\times
G$ and $i\in\\{0,2\\}$. Also, there exists
$w^{(0)},w^{(2)}\in\mathcal{L}_{B_{n}}(Y)$ such that
$w^{(0)}_{Q_{n}}=w^{(1)}_{Q_{n}}=w^{(2)}_{Q_{n}}$ and
$w^{(i)}_{B_{k}}=\tilde{w}^{(i)}$ for $i\in\\{0,2\\}$.

Let $F=B_{n}$, and let

$S=Y^{w^{(0)}}=\left\\{y\in Y\leavevmode\nobreak\ :\leavevmode\nobreak\
\sigma_{v}(y)_{B_{n}}\neq w^{(0)}\mbox{ for all }v\in\Gamma\right\\}.$

Since $\tilde{w}\not\in\mathcal{L}_{B_{k}}(\hat{Y})$, it follows that
$w^{(0)}\not\in\mathcal{L}_{B_{n}}(\hat{Y})$, so $\hat{Y}\subseteq S$.

Let $\tilde{r}:Y\to S$ be the map that replaces every occurrence of $w^{(0)}$
with an occurrence of $w^{(1)}$. The map $r$ is well defined because the
occurrences of $w^{(0)}$ in any $y\in Y$ are $B_{n}$-separated and also
$B_{n-k}$-disjoint from the occurrences of $w^{(1)}$. The map $\tilde{r}$ is a
retraction map from $Y$ to $S$. It is clear that condition $(1)$ in the
statement of the lemma holds.

Let $\kappa:S\times\\{0,1\\}^{\Gamma}\to Y$ be the map defined as follows: For
$y\in S$ and $z\in\\{0,1\\}^{\Gamma}$ the point $\tilde{y}\in Y$ is obtained
by replacing the occurrences of $w^{(1)}$ in the set
$\\{v\in\Gamma\leavevmode\nobreak\ :\leavevmode\nobreak\ z_{v}=1\\}$ by
occurrences of $w^{(0)}$. Because the occurrences of $w^{(1)}$ are
$B_{n}$-separated, this is well defined. From the definition it follows that
conditions $(2)$ and $(3)$ in the statement of the lemma are satisfied.

We will now show that for any $y\in Y$ there exists $\hat{y}\in S$ with
$\mathit{stab}(y)=\mathit{stab}(\hat{y})$. Take any $y\in Y$. If $w^{(0)}$
does not occur in $y$, then $y\in S$ and we can take $\hat{y}=y$. Otherwise,
there exists $v\in\Gamma$ such that $w^{(0)}$ occurs in $y$ at $v+w$ for every
$w\in\mathit{stab}(y)$. Replacing $y$ by $\sigma_{-v}(y)$, we can assume that
$w^{(0)}$ occurs in $y$ at every $w\in\mathit{stab}(y)$. Let $\hat{y}\in Y$ be
the point obtained from $y$ by replacing each occurrence of $w^{(0)}$ in
$\mathit{stab}(y)$ by an occurrence of $w^{(2)}$, and replacing every other
occurrence of $w^{(0)}$ or $w^{(2)}$ in $y$ by an occurrence of $w^{(1)}$. It
is clear that $\mathit{stab}(y)\leq\mathit{stab}(\hat{y})$. On the other hand,
since $w^{(2)}$ only occurs in $y$ at $\mathit{stab}(y)$, it follows that
$\mathit{stab}(\hat{y})\leq\mathit{stab}(y)$.

From this it follows that if $Y_{\Gamma_{0}}\neq\emptyset$ then
$S_{\Gamma_{0}}\neq\emptyset$, and also that for every $\Gamma_{0}\leq\Gamma$
we have $\mathit{Ker}(S_{\Gamma_{0}})=\mathit{Ker}(Y_{\Gamma_{0}})$. In
particular, condition $(4)$ in the statement of the lemma is satisfied.

Let $\Gamma_{0}\leq\Gamma$ be a subgroup which is not $B_{n}$-separated, then
$w^{(0)}$ does not occur in $Y_{\Gamma_{0}}$, and so
$S_{\Gamma_{0}}=Y_{\Gamma_{0}}$, and in particular if
$Y_{\Gamma_{0}}\neq\emptyset$ then $S_{\Gamma_{0}}\neq\emptyset$, and in that
case $\mathit{Ker}(S_{\Gamma_{0}})=\mathit{Ker}(Y_{\Gamma_{0}})$ and
$h(S_{\Gamma_{0}})=h(Y_{\Gamma_{0}})$. Take any $B_{n}$-separated subgroup
$\Gamma_{0}\leq\Gamma$.

and let $D_{\Gamma_{0}}$ be a fundamental domain for $\Gamma_{0}$.

Then

$\frac{|\mathcal{L}_{B_{m}}(Y_{\Gamma_{0}})|}{|\mathcal{L}_{B_{n}}(S_{\Gamma_{0}})|}\leq\left(\frac{|W_{n,k}|}{|W_{n,k}|-1}\right)^{|B_{m}\cap
D_{\Gamma_{0}}|}$

It follows that

$\frac{1}{|B_{m}\cap
D_{\Gamma}|}\log\left|\mathcal{L}_{B_{m}}(Y_{\Gamma_{0}})\right|-\frac{1}{|B_{m}\cap
D_{\Gamma}|}\log\left|\mathcal{L}_{B_{m}}(S_{\Gamma_{0}})\right|\leq\log\left(\frac{|W_{n,k}|}{|W_{n,k}|-1}\right).$

So taking $m\to\infty$ we have that

$h(\overline{Y}_{\Gamma_{0}})\leq h(\overline{S}_{\Gamma_{0}})+\epsilon.$

This show that condition $(5)$ is satisfied and completes the proof of the
lemma. ∎

##  8\. Proof of the embedding theorem for subshifts over a finitely generated
abelian group

In this section we complete the proof of the more difficult direction of our
main theorem for the case that $\Gamma$ is a finitely generated abelian group.
Namely, we prove that in the case that $\Gamma$ is a finitely generated
abelain group, the conditions $E(X,Y,\hat{\rho},\Gamma_{0})$ are sufficient to
assure that
$X_{\tilde{\Gamma}}\hookrightarrow_{\hat{\rho}}Y_{\tilde{\Gamma}}$. We phrase
a slightly more involved statement for the purpose of the internal inductive
nature of our proof:

######  Proposition 8.1.

Let $\Gamma$ be a finitely generated abelian group and let $X,Y$ be
$\Gamma$-subshifts. Suppose that $Y$ has the map extension property. Let
$Z\subseteq X$ be a closed $\Gamma$-invariant set, and let $\hat{\rho}:Z\to Y$
be an embedding. Suppose that $E(X,Y,\hat{\rho},\Gamma_{0})$ holds for any
subgroup $\Gamma_{0}\leq\Gamma$. Then
$X_{\tilde{\Gamma}}\hookrightarrow_{\hat{\rho}}Y_{\tilde{\Gamma}}$.

###### Proof.

We will prove the statement by a double induction: The external induction on
the rank of the group $\Gamma$, and the internal induction over the size of
the torsion subgroup of $\Gamma$.

Let $X\subseteq B^{\Gamma}$, $Y\subseteq A^{\Gamma}$, $Z\subseteq X$ and
$\hat{\rho}:Z\to Y$ be as in the statement of the lemma.

By Proposition 4.16 there exists a finite set
$\mathcal{G}\Subset\mathrm{Sub}(\Gamma)$ such that $Y$ is an absolute retract
for the class of $\mathcal{G}$-free subshifts. In particular, by Lemma 4.8
there exists a finite set $W_{0}\Subset\Gamma$ that witnesses that $Y$ is
$\mathcal{G}$-free. By Lemma 4.12, there exists a finite set $F\Subset\Gamma$
so that for any $\mathcal{G}$-free subshift $\hat{Y}$ there exists a
retraction map $\hat{r}:\hat{Y}\to Y$ such that if $y\in\hat{Y}$ and
$y_{F}\in\mathcal{L}_{F}(Y)$ then $\hat{r}(y)_{0}=y_{0}$.

Since $E(X,Y,\hat{\rho},\\{0\\})$ holds, either $h(X)<h(Y)$ or
$X\cong_{\hat{\rho}}Y$. In the second case, there is nothing to prove. So we
can assume that $h(X)<h(Y)$. Let $\eta=\frac{1}{3}(h(Y)-h(X))$. Choose
$n\in\mathbb{N}$ sufficiently big so that $F\subseteq B_{n}$, and also so that
any for any pattern $w\in\mathcal{L}_{B_{5n}(Y)}$ and any $y\in Y$ there
exists $\tilde{y}\in Y$ so that $\tilde{y}_{B_{5n}}=w$ and
$\tilde{y}_{\Gamma\setminus B_{6n}}=y_{\Gamma\setminus B_{6n}}$.

By Proposition 4.17 there exists a finite set
$F_{1}\Subset\Gamma\setminus\\{0\\}$ such that for any $\Gamma_{0}<\Gamma$
with $\Gamma_{0}\cap F_{1}\neq\emptyset$ we have that
$h_{\Gamma_{0}}(Y)>h(Y)-\eta$. By Proposition 2.23 there exists a finite set
$F_{2}\Subset\Gamma\setminus\\{0\\}$ such that for any $\Gamma_{0}<\Gamma$
with $\Gamma_{0}\cap F_{2}\neq\emptyset$ we have that
$h_{\Gamma_{0}}(X)<h(X)+\eta$. Let $F_{0}=F_{1}\cup F_{2}$. It follows that
$h_{\Gamma_{0}}(X)<h_{\Gamma_{0}}(Y)-\eta$ whenever $\Gamma_{0}<\Gamma$
satisfies that $F\cap\Gamma_{0}\neq\emptyset$.

Let $\mathcal{G}_{0}$ denote the family of subgroups non-trivial subgroups of
$\Gamma$ generated by a subset of the elements of $F_{0}$. Let
$\hat{Y}=\hat{\rho}(Z)\cup\bigcup_{\Gamma_{0}\in\mathcal{G}_{0}}Y_{\Gamma_{0}}$.

Applying Lemma 7.3 with $X,Y,\hat{Y}$ $F_{0}$ as above and $\epsilon=\eta$, we
can find a finite symmetric set $F\subset\Gamma$, subshift $S\subset Y$, a
retraction map $\tilde{r}:Y\to S$, a map $\kappa:S\times\\{0,1\\}^{\Gamma}\to
Y$ and patterns $w^{(0)},w^{(1)}\in\mathcal{L}_{F}(Y)$ such that
$w^{(0)}\not\in\mathcal{L}_{F}(S)$ so that conditions $(1)-(5)$ in the
statement of Lemma 7.3 hold.

Observe that the subshift $S$ also has the map extension property, since it is
a retract of $Y$. Furthermore, $h(S)>h(X)$ and for any $\Gamma_{0}\leq\Gamma$
the condition $E(X,S,\hat{\rho},\Gamma_{0})$ holds. Since $h(X)<h(S)$, by
Lemma 2.22 we can find $\epsilon>0$ and $K\Subset\Gamma$ so that for any
$(K,\epsilon)$-invariant set $T\Subset\Gamma$ we have

$\log\left|\mathcal{L}_{T+F+F}(X)\right|\leq(1-\epsilon)\log\left|\mathcal{L}_{T\setminus\left(\partial_{(F+F)}T\cup(F+F)\right)}(S)\right|.$
(6)

Applying Proposition 6.4 with $X$, $K\subset\Gamma$ and $\epsilon>0$ we obtain
a suitable set $P\Subset\Gamma\setminus\\{0\\}$.

Let $\mathcal{G}_{1}\Subset\mathrm{Sub}(\Gamma)$ denote the union of
$\mathcal{G}_{0}$ with the family of subgroups non-trivial subgroups of
$\Gamma$ generated by a subset of the elements of $P$.

Order the elements of $\mathcal{G}_{1}$ as
$\mathcal{G}_{1}=\left\\{\Gamma_{1},\ldots,\Gamma_{m}\right\\}$. We will prove
that for every $1\leq j\leq m$ there exists an embedding
$\rho_{j}:(Z\cup\bigcup_{\ell=1}^{j}X_{\Gamma_{\ell}})\to\tilde{Y}$ that
extends $\tilde{\rho}$. The construction proceeds in $m$ steps, where in step
$j$ we extend $\rho_{j}$ to $\rho_{j+1}$ using the main induction hypothesis
with $\Gamma$ replaced by $\Gamma/\Gamma_{j+1}$ (noting that
$\Gamma/\Gamma_{j+1}$ either has lower rank than $\Gamma$ or smaller torsion).

So now we can conveniently replace $Z$ with
$Z\cup\bigcup_{j=1}^{m}X_{\Gamma_{j}}$ and replacing $\hat{\rho}$ with
$\rho_{m}$, and thus assume that $X_{\Gamma_{j}}\subseteq Z$ for every $1\leq
j\leq m$.

Let $W_{1}\Subset\Gamma$ be a coding window for $\hat{\rho}$, and let
$\hat{\Phi}:B^{W_{1}}\to A$ be a sliding block code for $\hat{\rho}$. By
possibly enlarging $W_{1}\Subset\Gamma$, we can also assume that $F\subseteq
W_{1}$ (and in particular that $0\in W_{1}$), and also that $W_{1}$ is
symmetric. Since $Z$ is relatively of finite type on $X$ We can further
enlarge $W_{1}$ so that if $x\in X$ then $x\in Z$ of and only if and
$\sigma_{v}(x)_{W}\in\mathcal{F}$ for all $v\in\Gamma$. In particular, if
$x\in X$ and $x_{W}\not\in\mathcal{F}$ then $x\not\in Z$, and in particular
$\mathit{stab}(x)\cap P=\emptyset$. Let $\mathcal{F}=\mathcal{L}_{W_{1}}(Z)$.
Then indeed if $x\in X$ and $x_{W}\not\in\mathcal{F}$ then
$\mathit{stab}(x)\cap P=\emptyset$. Let $W_{2}$ be a symmetric injectivity
window for $\hat{\rho}$ (with respect to the sliding block $\hat{\Phi}$), with
$0\in W_{2}$. Let $\tilde{W}=W_{1}+W_{2}$. Then $\hat{\rho}$ extends to an
embedding of the subshift of finite type $\tilde{Z}$ given by

$\tilde{Z}=\left\\{z\in B^{\Gamma}\leavevmode\nobreak\ :\leavevmode\nobreak\
\sigma_{v}(z)_{\tilde{W}}\in\mathcal{L}_{\tilde{W}}(Z)\mbox{ for all
}v\in\Gamma\right\\}.$

Since $Z\subseteq\tilde{Z}$, we can conveniently replace $Z$ by $\tilde{Z}$.

Given a map $\alpha:X\to\\{0,1\\}^{\Gamma}$, a pointed partial tiling
$\tau:\alpha(X)\to\mathit{PTilings}(\Gamma)$, $x\in X$ and $v\in\Gamma$ such
that $\alpha(x)_{v}=1$, let $T_{v}(x)\Subset\Gamma$ denote the tile in
$\tau(\alpha(x))$ that contains $v$. and let

$T^{-}_{v}(x)=T_{v}(x)\setminus\left((v+F+F)\cup\partial_{F}T_{v}(x)\right)$

and

$T^{+}_{v}(x)=(T_{v}(x)+F)\cup\partial_{W}^{\mathcal{T}}T_{v}(x).$

Applying Proposition 6.4 with the previously obtained set
$P\Subset\Gamma\setminus\\{0\\}$, $W=W_{1}$ and $\tilde{W}=W_{1}+W_{2}$ and
$\epsilon_{1}>0$ sufficiently small, we obtain the existence of a map
$\alpha:X\to\\{0,1\\}$ and a pointed $(K,\epsilon)$-invariant tiling
$\tau:\alpha(X)\to\mathit{PTilings}(\Gamma)$ such that for every $x\in X$:

  1. (1)

For every $v\in\Gamma$ such that $\alpha(x)_{v}=1$, letting
$T^{-}=T^{-}_{v}(x)$ and $T^{+}=T^{+}_{v}(x)$ it holds that
$\left|\mathcal{L}_{T^{+}}(X)\right|\leq\left|\mathcal{L}_{T^{-}}(Y)\right|$.

  2. (2)

If $v\in\Gamma$ is not contained in some tile $T\in\tau(\alpha(x))$ then
$\sigma_{v}(x)_{W_{1}+W_{2}}\in\mathcal{L}(Z)$.

Given $x\in X$, let

$P_{v}^{+}(x)=x_{T_{v}^{+}(x)}\in\mathcal{L}_{T_{v}^{+}(x)}(X).$

For every $T,T^{-},T^{+}\Subset\Gamma$ that occur as
$T_{0}(x),T_{0}^{-}(x),T_{0}^{+}(x)$ for some $x\in X$ with $\alpha(x)_{0}=1$,
choose an injective function