arXiv:1706.05827v1 [] 19 Jun 2017

THE MOORE AND THE MYHILL PROPERTY FOR
STRONGLY IRREDUCIBLE SUBSHIFTS OF FINITE
TYPE OVER GROUP SETS
SIMON WACKER

Abstract. We prove the Moore and the Myhill property for strongly
irreducible subshifts over right amenable and finitely right generated left homogeneous spaces with finite stabilisers. Both properties together mean that the global transition function of each
big-cellular automaton with finite set of states and finite neighbourhood over such a subshift is surjective if and only if it is preinjective. This statement is known as Garden of Eden theorem.
Pre-Injectivity means that two global configurations that differ at
most on a finite subset and have the same image under the global
transition function must be identical.

The notion of amenability for groups was introduced by John von
Neumann in 1929. It generalises the notion of finiteness. A group
G is left or right amenable if there is a finitely additive probability
measure on P(G) that is invariant under left and right multiplication
respectively. Groups are left amenable if and only if they are right
amenable. A group is amenable if it is left or right amenable.
The definitions of left and right amenability generalise to left and
right group sets respectively. A left group set (M, G, .) is left amenable if there is a finitely additive probability measure on P(M ) that is
invariant under .. There is in general no natural action on the right
that is to a left group action what right multiplication is to left group
multiplication. Therefore, for a left group set there is no natural notion
of right amenability.
A transitive left group action . of G on M induces, for each element
m0 ∈ M and each family {gm0 ,m }m∈M of elements in G such that,
for each point m ∈ M , we have gm0 ,m . m0 = m, a right quotient
set semi-action P of G/G0 on M with defect G0 given by m P gG0 =
−1
gm0 ,m ggm
.m, where G0 is the stabiliser of m0 under .. Each of these
0 ,m
right semi-actions is to the left group action what right multiplication
is to left group multiplication. They occur in the definition of global
transition functions of semi-cellular automata over left homogeneous
spaces as defined in [9]. A cell space is a left group set together with
choices of m0 and {gm0 ,m }m∈M .
1

2

SIMON WACKER

A cell space R is right amenable if there is a finitely additive probability measure on P(M ) that is semi-invariant under P. For example cell
spaces with finite sets of cells, abelian groups, and finitely right generated cell spaces with finite stabilisers of sub-exponential growth are
right amenable, in particular, quotients of finitely generated groups of
sub-exponential growth by finite subgroups acted on by left multiplication. A net of non-empty and finite subsets of M is a right Følner net
if, broadly speaking, these subsets are asymptotically invariant under
P. A finite subset E of G/G0 and two partitions {Ae }e∈E and {Be }e∈E
of M constitute a right paradoxical decomposition if the map _ P e is
injective on Ae and Be , and the family {(Ae P e) ∪· (Be P e)}e∈E is a
partition of M . The Tarski-Følner theorem states that right amenability, the existence of right Følner nets, and the non-existence of right
paradoxical decompositions are equivalent. We prove it in [10] for cell
spaces with finite stabilisers.
A cell space R is finitely right generated if there is a finite subset S
of G/G0 such that, for each cell m ∈ M , there is a family {si }i∈{1,2,...,k}
of elements in S ∪ S −1 such that m = (((m0 P s1 ) P s2 ) P · · · ) P sk . The
finite right generating set S induces the S-Cayley graph structure on
M : For each cell m ∈ M and each generator s ∈ S, there is an edge
from m to m P s. The length of the shortest path between two points
of M yields the S-metric.
A subset X of QM , where Q is a finite set, is a shift space of finite
type if it is generated by a finite set of forbidden blocks or, equivalently, if it is shift-invariant and compact. Such a space X is strongly
irreducible if each pair of finite patterns that are allowed in X and at
least some fixed positive integer apart, are embedded in a point of X.
A map ∆ from a shift space X to a shift space Y is local if the state
∆(x)(m) is uniformly and locally determined in m, in other words, if
the map ∆ is the restriction of the global transition function of a bigcellular automaton with finite neighbourhood to the domain X and the
codomain Y .
For a right amenable and finitely right generated cell space with finite
stabilisers we may choose a right Følner net F = {Fi }i∈I . The entropy
of a subset X of QM with respect to F, where Q is a finite set, is,
broadly speaking, the asymptotic growth rate of the number of finite
patterns with domain Fi that occur in X. For non-negative integers θ,
κ, and θ0 , a (θ, κ, θ0 )-tiling is a subset T of M such that {B(t, θ)}t∈T is
pairwise at least κ + 1 apart and {B(t, θ0 )}t∈T is a cover of M . If for
each point t ∈ T not all patterns with domain B(t, θ) occur in a subset
of QM , then that subset does not have maximal entropy.

THE MOORE AND THE MYHILL PROPERTY

3

A local map from a non-empty strongly irreducible shift space of
finite type to a strongly irreducible shift space with the same entropy
over a right amenable and finitely right generated cell space with finite
stabilisers is surjective if and only if its image has maximal entropy and
its image has maximal entropy if and only if it is pre-injective. This
establishes the Garden of Eden theorem, which states that a local map
as above is surjective if and only if it is pre-injective. This answers a
question posed by Sébastien Moriceau at the end of his paper ‘Cellular
Automata on a G-Set’[7]. And it follows that strongly irreducible shift
spaces of finite type over right amenable and finitely right generated
cell spaces have the Moore and the Myhill property.
The Garden of Eden theorem for cellular automata over Z2 is a
famous theorem by Edward Forrest Moore and John R. Myhill from
1962 and 1963, which was proved in their papers ‘Machine models
of self-reproduction’[6] and ‘The converse of Moore’s Garden-of-Eden
theorem’[8]. That theorem also holds for cellular automata over amenable finitely generated groups, which was proved by Tullio CeccheriniSilberstein, Antonio Machi, and Fabio Scarabotti in their paper ‘Amenable groups and cellular automata’[1]. It even holds for such automata on strongly irreducible shifts of finite type, which was proved by
Francesca Fiorenzi in her paper ‘Cellular automata and strongly irreducible shifts of finite type’[4]. The present paper generalises results
from and is greatly inspired by Francesca Fiorenzi’s paper.
In Section 1 we introduce full shifts, patterns, blocks, and shiftinvariance. In Section 2 we introduce shift spaces or subshifts (of
finite type), strong irreducibility, bounded propagation, local maps,
conjugacies, and the Moore and the Myhill property. In Section 3 we
introduce tilings, prove their existence, and relate them to entropies.
And in Section 4 we prove the Garden of Eden theorem, from which
we deduce that both the Moore and the Myhill property hold.
Preliminary Notions. A left group set is a triple (M, G, .), where M is
a set, G is a group, and . is a map from G × M to M , called left group
action of G on M , such that G → Sym(M ), g 7→ [g . _], is a group
homomorphism. The action . is transitive if M is non-empty and for
each m ∈ M the map _ . m is surjective; and free if for each m ∈ M
the map _ . m is injective. For each m ∈ M , the set G . m is the orbit
of m, the set Gm = (_ . m)−1 (m) is the stabiliser of m, and, for each
m0 ∈ M , the set Gm,m0 = (_ . m)−1 (m0 ) is the transporter of m to m0 .
A left homogeneous space is a left group set M = (M, G, .) such
that . is transitive. A coordinate system for M is a tuple K = (m0 ,
{gm0 ,m }m∈M ), where m0 ∈ M and for each m ∈ M we have gm0 ,m .m0 =

4

SIMON WACKER

m. The stabiliser Gm0 is denoted by G0 . The tuple R = (M, K) is a cell
−1
space. The map P : M × G/G0 → M , (m, gG0 ) 7→ gm0 ,m ggm
. m (=
0 ,m
gm0 ,m g .m0 ) is a right semi-action of G/G0 on M with defect G0 , which
means that
∀ m ∈ M : m P G0 = m,

∀ m ∈ M ∀ g ∈ G ∃ g0 ∈ G0 : ∀ g0 ∈ G/G0 : m P g · g0 = (m P gG0 ) P g0 · g0 .
It is transitive, which means that the set M is non-empty and for each
m ∈ M the map m P _ is surjective; and free, which means that for
each m ∈ M the map m P _ is injective; and semi-commutes with .,
which means that
∀ m ∈ M ∀ g ∈ G ∃ g0 ∈ G0 : ∀ g0 ∈ G/G0 : (g . m) P g0 = g . (m P g0 · g0 ).
The maps ι : M → G/G0 , m 7→ Gm0 ,m , and m0 P _ are inverse to each
other. Under the identification of M with G/G0 by either of these
maps, we have P : (m, g) 7→ gm0 ,m . g. (See [9].)
A left homogeneous space M is right amenable if there is a coordinate
system K for M and there is a finitely additive probability measure µ
on M such that

∀ g ∈ G/G0 ∀ A ⊆ M : (_ P g)A injective =⇒ µ(A P g) = µ(A) ,
in which case the cell space R = (M, K) is called right amenable.
When the stabiliser G0 is finite, that is the case if and only if there
is a right Følner net in R indexed by (I, ≤), which is a net {Fi }i∈I in
{F ⊆ M | F 6= ∅, F finite} such that
|∂ρ Fi |
= 0.
i∈I |Fi |
If a net is a right Følner net for one coordinate system, then it is
a right Følner net for each coordinate system. In particular, a left
homogeneous space M with finite stabilisers is right amenable if and
only if, for each coordinate system K for M, the cell space (M, K) is
right amenable. (See [10, 12].)
A left homogeneous space M is finitely right generated if there is a
coordinate system K for M and there is a finite subset S of G/G0 such
that G0 · S ⊆ S and, for each m ∈ M , there is a k ∈ N0 and there is
a {si }i∈{1,2,...,k} ⊆ S ∪ S −1 , where S −1 = {g −1 G0 | s ∈ S, g ∈ s}, such
that

 
m = (m0 P s1 ) P s2 · · · P sk .
∀ ρ ∈ N0 : lim

in which case the cell space R = (M, K) is called finitely right generated. The left homogeneous space M is finitely right generated if and
only if, for each coordinate system K for M, the cell space (M, K)

THE MOORE AND THE MYHILL PROPERTY

5

is finitely right generated. The right generating set S is symmetric
if S −1 ⊆ S. The S-edge-labelled directed multigraph (M, E, σ, τ, λ),
where E = {(m, s, m P s) | m ∈ M, s ∈ S} and σ : E → M , λ : E → S,
and τ : E → M are the projections to the first, second, and third component respectively, is the S-Cayley graph. The distance dS on that
graph is the S-metric and the map |_|S = dS (m0 , _) is the S-length.
For each m ∈ M and each ρ ∈ N0 , the sets
BS (m, ρ) = {m0 ∈ M | dS (m, m0 ) ≤ ρ},
SS (m, ρ) = {m0 ∈ M | dS (m, m0 ) = ρ}
are the ball/sphere of radius ρ centred at m, the ball BS (m0 , ρ) is denoted by BS (ρ), and the sphere SS (m0 , ρ) by SS (ρ). For each A ⊆ M ,
each θ ∈ N0 , the set A−θ = {m ∈ A | BS (m, θ) ⊆ A} is the θ-interior of
A, the set A+θ = {m ∈ M | BS (m, θ)∩A 6= ∅} is the θ-closure of A, the
set ∂θ A = A+θ r A−θ is the θ-boundary of A, the set ∂θ− A = A r A−θ
is the internal θ-boundary of A, and the set ∂θ+ A = A+θ r A is the
external θ-boundary of A. (See [12].)
A semi-cellular automaton is a quadruple C = (R, Q, N, δ), where R
is a cell space; Q, called set of states, is a set; N , called neighbourhood,
is a subset of G/G0 such that G0 · N ⊆ N ; and δ, called local transition
function, is a map from QN to Q. A local configuration is a map ` ∈ QN ,
a global configuration is a map c ∈ QM , and a pattern is a map p ∈ QA ,
where A is a subset of M . The stabiliser G0 acts on QN on the left by
• : G0 × QN → QN , (g0 , `) 7→ [n 7→ `(g0−1 · n)], and the group G acts on
the set of patterns on the left by
[
[
I: G ×
QA →
QA ,
A⊆M

A⊆M

"
(g, p) 7→

g . dom(p) → Q,

#

m 7→ p(g −1 . m).

The global transition function of C is the map ∆ : QM → QM , c 7→
[m 7→ δ(n 7→ c(m P n))].
A cellular automaton is a semi-cellular automaton C = (R, Q, N, δ)
such that δ is •-invariant, which means that, for each g0 ∈ G0 , we have
δ(g0 • _) = δ(_). Its global transition function is I-equivariant, which
means that, for each g ∈ G, we have ∆(g I _) = g I ∆(_).
A subgroup H of G is K-big if the set {gm0 ,m | m ∈ M } is included in
H. A big-cellular automaton is a semi-cellular automaton C = (R, Q,
N, δ) such that, for some K-big subgroup H of G, the local transition
function δ is •G0 ∩H -invariant, which means that, for each h0 ∈ G0 ∩

6

SIMON WACKER

H, we have δ(h0 • _) = δ(_). Its global transition function is IH equivariant, which means that, for each h ∈ H, we have ∆(h I _) =
h I ∆(_). Note that each K-big subgroup of G includes the subgroup
of G generated by {gm0 ,m | m ∈ M } and that hence a semi-cellular
automaton is a big-cellular automaton if and only if its local transition
function is •G0 ∩hgm0 ,m |m∈M i -invariant. (See [9].)
For each A ⊆ M , let πA : QM → QA , c 7→ cA .
Context. In the present paper, let R = (M, K) = ((M, G, .), (m0 ,
{gm0 ,m }m∈M )) be a finitely right generated cell space such that the
stabiliser G0 of m0 under . is finite; let S be a finite and symmetric
right generating set of R; let H be a K-big subgroup of G; let H0 be the
stabiliser of m0 under .H×M , which is H ∩ G0 ; for each cell m ∈ M ,
let Hm0 ,m be the transporter of m0 to m under .H×M ; let Q be a finite
set; let QM be equipped with the prodiscrete topology; and identify
M with G/G0 by ι : m 7→ Gm0 ,m . Moreover, we omit the subscript S,
in particular, instead of dS we write d, instead of |_|S we write |_|,
instead of BS we write B, and instead of SS we write S.
1. Full Shifts
Contents. The full shift is the set of global configurations, the points of
the full shift (see Definition 1.1). A pattern is a map from a subset of
cells to the set of states (see Definition 1.4), its size is the cardinality of
its domain (see Definition 1.5), it is empty if its domain is empty (see
Definition 1.6), it is finite and called block if its domain is finite (see
Definitions 1.8 and 1.9), and restricting its domain yields a subpattern
(see Definition 1.10). A subset of the full shift is shift-invariant if it
is invariant under a group that contains the coordinates (see Definition 1.11). A pattern centred at the origin can be shifted to a new
centre by sort of acting on the new centre (see Definition 1.14).
Definition 1.1. The set QM is called full shift and each element c ∈
QM is called point.
Example 1.2 ([5, Definition 1.1.1]). Let M be the left homogeneous
space (Z, Z, +), let K be the coordinate system (0, {z}z∈Z ), let R be
the cell space (M, K), let S be the set {−1, 1}, let H be the only K-big
subgroup Z of Z, and let Q be the binary set {0, 1}. The stabiliser Z0
of 0 under + is the singleton set {0}; under the identification of Z with
Z/Z0 by z 7→ z + Z0 , the right semi-action of Z/Z0 on Z is but +; and
the set S is a finite and symmetric right generating set of R. The full
shift QZ is the usual full 2-shift considered in symbolic dynamics and
its points are called bi-infinite binary sequences.

THE MOORE AND THE MYHILL PROPERTY

7

Remark 1.3. There is a bijective map ϕ from Q to Z|Q| (= {0, 1, . . . , |Q|−
1}). It induces the bijective map
Φ : QM → ZM
|Q| ,


c 7→ m 7→ ϕ c(m) .
Definition 1.4. Let A be a subset of M and let p be a map from A
to Q. The map p is called A-pattern and the set dom(p) = A is called
domain of p.
Definition 1.5. Let p be an A-pattern. The cardinal number |p| = |A|
is called size of p.
Definition 1.6. The ∅-pattern is called empty.
Remark 1.7. The empty pattern is the only one of size 0.
Definition 1.8. Let u be an F -pattern. It is called finite and F -block
if and only if its domain F is finite.
Definition 1.9. The set {u ∈ QF | F ⊆ M finite} of all blocks is
denoted by Q∗ .
Definition 1.10. Let p be an A- and let p0 be an A0 -pattern. The
pattern p is called subpattern of p0 if and only if A ⊆ A0 and p = p0 A .
Definition 1.11. Let X be a subset of QM . It is called shift-invariant
if and only if
∀ h ∈ H : h I X = X.
Remark 1.12. Shift-invariance is the same as

IH -invariance.

Remark 1.13. The set X is shift-invariant if and only if
∀ h ∈ H : h I X ⊆ X.
Definition 1.14. The map
[
[
J: M ×
QA →
QA ,
A⊆M

A⊆M


(m, p) 7→

m P dom(p) → Q,



m P a 7→ p(a),

broadly speaking, maps a point m and a pattern p that is centred at
m0 to the corresponding pattern centred at m.
Remark 1.15. Let p be an A-pattern and let m be an element of M .
Then, m J p = gm0 ,m I p and dom(m J p) = gm0 ,m . dom(p).
Remark 1.16. Let X be a shift-invariant subset of QM . Then,
∀ m ∈ M : m J X = X.

8

SIMON WACKER

2. Shift Spaces
Contents. A pattern semi-occurs in another pattern if a rotation of
it occurs in the other pattern (see Definition 2.1 and Remarks 2.3
and 2.4). It is allowed in a subset of the full shift if it semi-occurs
in one of its points and it is forbidden otherwise (see Definition 2.5).
The set of points of the full shift in which each block of a given set is
forbidden is generated by that set (see Definition 2.6) and it is a shift
space (see Definition 2.7), which is shift-invariant (see Lemma 2.12),
closed (see Lemma 2.16), and compact (see Lemma 2.17).
If there is a finite generating set, then the shift space is of finite
type (see Definition 2.19), the radius κ of a ball that includes the
domains of the patterns of the generating set is its memory and it itself
is called κ-step (see Definition 2.21 and Lemma 2.23), and its points
are characterised by restrictions to balls with its memory as radius (see
Lemma 2.24). Finitely many points of shift spaces of finite type can be,
in various ways, cut into pieces and glued together to construct new
points, as long as the pieces agree on a big enough boundary of the
cuts (see Lemma 2.25 and Corollaries 2.26 and 2.27). A shift space is
strongly irreducible if allowed finite patterns that are at least a certain
distance apart can be embedded in the same point (see Definitions 2.28
and 2.30). It has bounded propagation if finite patterns are allowed
whenever their restrictions to balls of a certain radius are allowed (see
Definitions 2.33 and 2.35). Such spaces are strongly irreducible and of
finite type (see Lemma 2.36).
A map from a shift space to another one is local if it is uniformly and
locally determined in each cell (see Definitions 2.40 and 2.43). Such
maps are global transition functions of big-cellular automata with finite
neighbourhoods (see Remark 2.44), their domains and codomains can
be simultaneously restricted to a subset of cells and its interior (see
Definition 2.47), and their images are shift spaces (see Lemma 2.48).
The difference of two points of the full shift is the set of cells in which
they differ (see Definition 2.49) and a local map is pre-injective if it
is injective on points with finite support (see Definition 2.50). A local
map that has a local inverse is a conjugacy (see Definition 2.51), and
its domain and codomain are conjugate (see Definition 2.52). Entropy
is invariant under conjugacy (see Lemma 2.53). A subshift has the
Moore property if each surjective local map is pre-injective, and the
Myhill property if the converse holds (see Definition 2.54). Both these
properties are invariant under conjugacy (see Remark 2.55).
Body. A pattern occurs in another pattern if a translation of it coincides with a subpattern the other pattern and it semi-occurs in another

THE MOORE AND THE MYHILL PROPERTY

9

pattern if a rotation and translation of it coincides with a subpattern
of the other pattern, as defined in
Definition 2.1. Let p be an A-pattern and let p0 be an A0 -pattern.
(1) Let m be an element of M . The pattern p is said to occur at m
in p0 and we write p vm p0 if and only if
m P A ⊆ A0 and m J p = p0 mPA .

◦m p0 if
And it is said to semi-occur at m in p0 and we write p v
and only if
∃ h ∈ Hm0 ,m : h . A ⊆ A0 and h I p = p0 h.A .
(2) The pattern p is said to occur in p0 and we write p v p0 if and
only if
∃ m ∈ M : p vm p0 .
◦ p0 if and
And it is said to semi-occur in p0 and we write p v
only if
◦ m p0 .
∃m ∈ M : p v
Remark 2.2. Let R be the cell space ((G, G, ·), (eG , {g}g∈G )), where
G is a group, · is its operation, and eG is its neutral element. Then,
G0 = {eG }, P = ·, J = I, and, for each element g ∈ G, we have
HeG ,g = {g}. Hence, the notions occurs and semi-occurs are identical,
and they are the common notion of occurrence as used in [4].
Semi-occurrence can be characterised in many ways, each illuminating a different aspect, some of which are given in
Remark 2.3. Let p be an A-pattern, let p0 be an A0 -pattern, and let
m be an element of M . The following statements are equivalent:
◦ m p0 ;
(1) p v
(2) ∃ h0 ∈ H0 : h0 I p vm p0 ;
(3) ∃ h0 ∈ H0 : gm0 ,m h0 . A ⊆ A0 and gm0 ,m h0 I p = p0 gm0 ,m h0 .A ;
(4) ∃ h ∈ Hm,m0 : A ⊆ h . A0 and (h I p0 )A = p;
−1
−1
I p0 )A = p.
(5) ∃ h0 ∈ H0 : A ⊆ h0 gm
. A0 and (h0 gm
0 ,m
0 ,m
Remark 2.4. Let p be an A-pattern and let p0 be an A0 -pattern. The
following statements are equivalent:
◦ p0 ;
(1) p v
(2) ∃ h0 ∈ H0 : h0 I p v p0 ;
(3) ∃ h ∈ H : h . A ⊆ A0 and h I p = p0 h.A ;
(4) ∃ h ∈ H : A ⊆ h . A0 and (h I p0 )A = p.
A pattern is allowed in a subset of the full shift if it semi-occurs in
one of its points and forbidden otherwise, as defined in

10

SIMON WACKER

Definition 2.5. Let X be a subset of QM and let p be an A-pattern.
The pattern p is called
(1) allowed in X if and only if
◦ x;
∃x ∈ X : p v
(2) forbidden in X if and only if
◦ x.
∀ x ∈ X : p 6v
The greatest subset of the full shift with respect to inclusion in which
each block of a given set of blocks is forbidden is said to be generated
by the set of blocks, as defined in
Definition 2.6. Let F be a subset of Q∗ . The set
◦ c}
hFi = {c ∈ QM | ∀ f ∈ F : f 6v
is said to be generated by F.
A shift space is a subset of the full shift that is generated by a set of
blocks, as defined in
Definition 2.7. Let X be a subset of QM . It is called shift space
and subshift of QM if and only if there is a subset F of Q∗ such that
hFi = X.
Example 2.8 (Full Shift). Because h∅i = QM , the set QM is a shift
space.
Example 2.9 (Empty Shift). If we identify each q ∈ Q with the B(m0 )block [m0 7→ q], then hQi = ∅ and hence the set ∅ is a shift space.
Example 2.10 (Golden Mean Shift [5, Example 1.2.3]). In the situation of Example 1.2, the set X of all bi-infinite binary sequences with
no two 1’s next to each other is the shift space known as golden mean
shift. It is for example generated by the forbidden block 11.
Example 2.11 (Even Shift [5, Example 1.2.4]). In the situation of
Example 1.2, the set X of all bi-infinite binary sequences such that,
between any two occurrences of 1’s, there are an even number of 0’s, is
the shift space known as even shift. It is for example generated by the
forbidden blocks 102k+1 1, for k ∈ N0 .
Each shift space is shift-invariant, which is shown in
Lemma 2.12. Let X be a subshift of QM . It is shift-invariant.

THE MOORE AND THE MYHILL PROPERTY

11

Proof. There is a subset F of Q∗ such that hFi = X. Let x ∈ X and
◦ h I x. Then,
let h ∈ H. Suppose that there is an f ∈ F such that f v
0
0
there is an h ∈ H such that h I f = (h I x)h0 .dom(f) . Thus, because
(h I x)h0 .dom(f) = h I (xh−1 h0 .dom(f) ), we have h−1 h0 I f = xh−1 h0 .dom(f) .
◦ x, which contradicts that
Hence, because h−1 h0 ∈ H, we have f v
x ∈ hFi. Therefore, contrary to the supposition, for each f ∈ F, we
◦ h I x. Hence, h I x ∈ X. Therefore, h I X ⊆ X. In conclusion,
have f 6v
according to Remark 1.13, the subshift X is shift-invariant.

Example 2.13 (Shift-Invariant Non-Shift [5, Example 1.2.10]). In the
situation of Example 1.2, the set X of all bi-infinite binary sequences
in which the symbol 1 occurs exactly once is shift-invariant, but it is
not a shift space.
Patterns with the same domain can all be restricted to some subdomain, as done in
Definition 2.14. Let A be a subset of M , let B be a subset of A, and
let P be a subset of QA . The set
PB = {pB | p ∈ P }
is the set of all B-subpatterns of patterns of P .
Because subshifts are shift-invariant, restrictions to patterns behave
nicely with translations and rotations, as remarked in
Remark 2.15. Let X be a subshift of QM , let A be a subset of M , let h
be an element of H, and let m be an element of M . For each A-pattern
p, we have p ∈ XA if and only if h I p ∈ Xh.A , and p ∈ XA if and only
if m J p ∈ XmPA . In particular, h I XA = Xh.A and m J XA = XmPA .
And, if A is finite, then |XA | = |Xh.A | and |XA | = |XmPA |.
Because shift spaces are generated by forbidden blocks, which have
finite domains, a point of the full shift belongs to a shift space if and
only if its subpatterns do, which is shown in
Lemma 2.16. Let X be a subshift of QM and let c be a point of QM .
Then, c ∈ X if and only if
(1)

∀ ρ ∈ N0 : cB(ρ) ∈ XB(ρ) .

Proof. If c ∈ X, then Equation (1) holds. From now on, let Equation (1) hold. Because X is a subshift, there is a subset F of Q∗ such
that hFi = X. Let f ∈ F. Suppose that f semi-occurs in c. Then,
because |f| < ∞, according to [12, Remark 5.6], there is a ρ ∈ N0 such
that f semi-occurs in cB(ρ) . Hence, cB(ρ) ∈
/ XB(ρ) , which contradicts

12

SIMON WACKER

Equation (1). Therefore, f does not semi-occur in c. In conclusion,
c ∈ X.

Shift spaces are characterised by shift-invariance and compactness,
which is shown in
Lemma 2.17. Let X be a subset of QM . It is a shift space if and only
if it is shift-invariant and compact.
Proof. First, let X be a shift space. Then, according to Lemma 2.12,
it is shift-invariant. Moreover, let (xk )k∈N+ be a sequence in X that
converges to a point c ∈ QM . Then, for each ρ ∈ N0 , there is a k ∈ N+
such that cB(ρ) = xk B(ρ) ∈ XB(ρ) . Thus, according to Lemma 2.16,
we have c ∈ X. Hence, X is closed. And, according to [2, the first
paragraph in Section 1.8], the set QM is compact. Therefore, X is
compact.
Secondly, let X be shift-invariant and compact. Then, X is closed
and QM r X is open. Hence, for each c ∈ QM r X, there is a ρc ∈ N0
such that Cyl(cB(ρc ) ) ⊆ QM r X. Put F = {cB(ρc ) | c ∈ QM r X}.
◦ x. Then,
Let x ∈ X. Suppose that there is an f ∈ F such that f v
according to Remark 2.4, there is an h ∈ H such that (h I x)dom(f) = f.
Thus, h I x ∈ Cyl(f) ⊆ QM r X. And, because X is shift-invariant, we
also have h I x ∈ X, which contradicts that h I x ∈ QM r X. Hence,
◦ x. Therefore,
contrary to the supposition, for each f ∈ F we have f 6v
X ⊆ hFi.
Let c ∈ hFi. Suppose that c ∈
/ X. Then, cB(ρc ) ∈ F. Thus c ∈
/ hFi,
which contradicts that c ∈ hFi. Hence, c ∈ X. Therefore, hFi ⊆ X.
Altogether, hFi = X. In conclusion, X is a shift space.

Remark 2.18. Compactness cannot be omitted in the equivalence.
For example, the subset of {0, 1}Z from Example 2.13 is shift-invariant
but not a shift space.
A shift space of finite type is one that is generated by finitely many
forbidden blocks, as defined in
Definition 2.19. Let X be a subshift of QM . It is said to be of finite
type if and only if there is a finite subset F of Q∗ such that hFi = X.
Example 2.20 (Of Finite Type or Not). As is apparent from their
definition, the full shift (Example 2.8), the empty shift (Example 2.9),
and the golden mean shift (Example 2.10) are of finite type. According
to [5, Example 2.1.5], the even shift (Example 2.11) is not of finite
type.

THE MOORE AND THE MYHILL PROPERTY

13

A κ-step shift space is one that is generated by forbidden B(κ)-blocks,
as defined in
Definition 2.21. Let X be a subshift of QM and let κ be a nonnegative integer. The subshift X is called κ-step and the integer κ is
called memory of X if and only if there is a subset F of QB(κ) such that
hFi = X.
Remark 2.22. Let X be a κ-step subshift of QM . Because the set
QB(κ) is finite, the subshift X is of finite type. And, for each nonnegative integer κ0 such that κ0 ≥ κ, the subshift X is κ0 -step.
A shift space of finite type is κ-step, where κ is the radius of a ball
that includes all domains of a finite generating set of the shift space,
which is shown in
Lemma 2.23. Let X be a subshift of QM of finite type. There is a
non-negative integer κ such that X is κ-step.
Proof. Because X is of finite type, there is a finite subset F of Q∗
such that hFi = X. And, because the set F is finite, according to
[12, Remark 5.6], there is a non-negative integer κ such that, for each
f ∈ F, we have dom(f) ⊆ B(κ). Let F0 be the set {p ∈ QB(κ) | ∃ f ∈ F :
pdom(f) = f}. Then, hF0 i = hFi = X. In conclusion, X is κ-step.

A shift space is κ-step if and only if it contains each point of the full
shift whose restrictions to the balls of radius κ are allowed patterns,
which is shown in
Lemma 2.24. Let X be a subshift of QM and let κ be a non-negative
integer. The subshift X is κ-step if and only if



M
(2)
∀ c ∈ Q : ∀ m ∈ M : cB(m,κ) ∈ XB(m,κ) =⇒ c ∈ X .
Proof. First, let X be κ-step. Then, there is an F ⊆ QB(κ) such that
hFi = X. Furthermore, let c ∈ QM such that
(3)

∀ m ∈ M : cB(m,κ) ∈ XB(m,κ) .

◦ c. Then, there is an m ∈ M
Suppose that there is an f ∈ F such that f v
◦m c. Thus, there is an h ∈ Hm0 ,m such that h I f = ch.B(κ) .
such that f v
Moreover, because h . m0 = m, according to [12, Lemma 5.9], we
have h . B(κ) = B(m, κ). Hence, according to Equation (3), we have
h I f = cB(m,κ) ∈ XB(m,κ) = Xh.B(κ) . Therefore, there is an x ∈ X such
◦ x, which contradicts that hFi = X. In conclusion, for each
that f v
◦ c, and hence c ∈ X.
f ∈ F, we have f 6v

14

SIMON WACKER

Secondly, let Equation (2) hold. Furthermore, let F = QB(κ) r XB(κ) .
We show below that X ⊆ hFi and hFi ⊆ X. Hence, hFi = X. In
conclusion, X is κ-step.
Subproof of: X ⊆ hFi.
◦ c. Thus,
Let c ∈ QM r hFi. Then, there is an f ∈ F such that f v
there is an m ∈ M and there is an h ∈ Hm0 ,m such that h I f = cB(m,κ) .
Therefore, because h I _ is bijective, according to Remark 2.15 and
[12, Lemma 5.9], we have cB(m,κ) ∈ h I F = h I (QB(κ) r XB(κ) ) =
(h I QB(κ) ) r (h I XB(κ) ) = QB(m,κ) r XB(m,κ) . Hence, c ∈ QM r X. In
conclusion, X ⊆ hFi.
Subproof of: hFi ⊆ X.
Let c ∈ QM rX. Then, according to Equation (2), there is an m ∈ M
such that cB(m,κ) ∈ QB(m,κ) r XB(m,κ) . Furthermore, let h = gm0 ,m .
Then, similar as above, h−1 I cB(m,κ) ∈ QB(κ) r XB(κ) = F. Thus, there
is an f ∈ F such that h I f = cB(m,κ) . Hence, because h ∈ H, we have
◦ c. Therefore, c ∈ QM r hFi. In conclusion, hFi ⊆ X.
fv

If we cut holes in a point of a shift space of finite type that are far
enough apart and fill these holes with pieces from other points of the
shift space that agree on big enough boundaries of the holes with the
holey point, then we still have a point of the shift space, which is shown
in
Lemma 2.25. Let X be a κ-step subshift of QM , let x be a point
of X, let {Ai }i∈I be a family of subsets of M such that the family
{A+2κ
}i∈I is pairwise disjoint, and let {xi }i∈I be a family of points of
i
+
+
. The map
X such that, for each index i ∈ I, we have xi ∂2κ
A
Ai = x∂2κ
i
`
`
S
xM r( i∈I Ai ) × i∈I xi Ai is identical to xM r(Si∈I A+2κ
)×
i∈I xi A+2κ
i
i
and a point of X.
Proof. Because {A+2κ
}i∈I is pairwise disjoint, so is {Ai }i∈I . Hence,
i `
x0 = xM r(Si∈I Ai ) × i∈I xi Ai is well-defined. Furthermore, for each
0
S
i ∈ I, we have xi A+2κ
rAi = xA+2κ
rAi . Hence, x = xM r( i∈I A+2κ
) ×
i
i
i
`
. Moreover, because X is κ-step, there is an F ⊆ QB(κ)
i∈I xi A+2κ
i
such that hFi = X.
Let u ∈ QB(κ) semi-occur in x0 . Then, there is an m ∈ M and there
is an h ∈ Hm0 ,m such that h I u = x0 h.B(κ) . Moreover, according to
[12, Lemma 5.9] and [12, Item 2 of Lemma 6.2], we have h . B(κ) =
B(m, κ) = {m}+κ .
Case 1: ∃ i ∈ I : m ∈ A+κ
i . Then, according to [12, Item 3
+κ
of Lemma 6.4], we have {m}+κ ⊆ (A+κ
⊆ A+2κ
. Hence,
i )
i

THE MOORE AND THE MYHILL PROPERTY

15

h . B(κ) ⊆ A+2κ
. Thus, x0 h.B(κ) = xi h.B(κ) . Therefore, u
i
semi-occurs in xi . S
Hence, u ∈
/ F.
Case 2: m ∈ M r ( i∈I A+κ
).
Then, according to [11, Item 3 of
i
Lemma 1] and [12, Item 5 of Lemma 6.4], we have {m}+κ ⊆
S
S
S
+(κ−κ)
+κ
−κ
(M r( Si∈I A+κ
⊆ M r( i∈I (A+κ
) ⊆ MS
r( i∈I Ai
)=
i ))
i )
M r ( i∈I Ai ). Hence, h . B(κ) ⊆ M r ( i∈I Ai ). Thus,
x0 h.B(κ) = xh.B(κ) . Therefore, u semi-occurs in x. Hence,
u∈
/ F.
In either case, u ∈
/ F. In conclusion, x0 ∈ X.

If we sew one part and respectively the other part of two sufficiently
overlapping points of a shift space of finite type together, then we get
a point of the shift space, which is shown in
Corollary 2.26. Let X be a κ-step subshift of QM , let A be a subset
0
+
+
of M , and let x and x0 be two points of X such that x∂2κ
A = x ∂2κ
A.
0
0
The map xA × x M rA is identical to xA+2κ × x M rA+2κ and a point
of X.
Proof. This is a direct consequence of Lemma 2.25 with {xi }i∈I = {x0 }.

If two patterns with the same domain, that are allowed in a shift
space of finite type, agree on a big enough boundary, then they can be
identically extended to points of the shift space, which is shown in
Corollary 2.27. Let X be a κ-step subshift of QM , let A be a subset
0
+
+
of M , let p and p0 be two patterns of XA+2κ such that p∂2κ
A = p ∂2κ
A.
0
0
There are two points x and x of X such that xA+2κ = p, x A+2κ = p0 ,
and xM rA = x0 M rA .
Proof. Because p, p0 ∈ XA+2κ , there are x00 , x0 ∈ X such that x00 A+2κ =
0
00
0
+
+
+
+
p and x0 A+2κ = p0 . Because p∂2κ
A = p ∂2κ
A , we have x ∂2κ
A = x ∂2κ
A.
00
0
Hence, according to Lemma 2.25, we have x = x A × x M rA ∈ X.
Moreover, xM rA = x0 M rA . And, because x = x00 A+2κ × x0 M rA+2κ ,
we have xA+2κ = p.

A shift space is strongly irreducible if two allowed finite patterns that
are far enough apart are embedded in a point of the shift space, which
is defined in
Definition 2.28. Let X be a subshift of QM and let κ be a nonnegative integer. The subshift X is called κ-strongly irreducible if and
only if for each tuple (p, p0 ) of finite patterns allowed in X such that
d(dom(p), dom(p0 )) ≥ κ+1, there is a point x ∈ X such that xdom(p) =
p and xdom(p0 ) = p0 .

16

SIMON WACKER

Remark 2.29. Let X be a κ-strongly irreducible subshift of QM . For
each non-negative integer κ0 such that κ0 ≥ κ, the subshift X is κ0 strongly irreducible.
Definition 2.30. Let X be a subshift of QM . It is called strongly
irreducible if and only if there is a non-negative integer κ such that it
is κ-strongly irreducible.
Example 2.31 (Strongly Irreducible). The full shift (Example 2.8)
and the empty shift (Example 2.9) are 0-strongly irreducible. The
golden mean shift is 1-strongly irreducible. The even shift is 2-strongly
irreducible. The generalised golden mean shifts (Example 2.38) and the
shift space of Example 2.39 are strongly irreducible. Of these examples,
according to Example 2.20, all but the even shift are of finite type.
Example 2.32 (Not Strongly Irreducible [3, Example 4.6]). In the
situation of Example 1.2, the set X of all bi-infinite binary sequences
with no two 0’s and no two 1’s next to each other is a shift space. It is
for example generated by the forbidden blocks 00 and 11, in particular,
it is of finite type. It consists of the two bi-infinite binary sequences
with alternating 0’s and 1’s. And, it is not strongly irreducible; indeed,
for each even and non-negative integer κ, the finite patterns 01 and 10
are allowed in X, the allowed patterns of size κ are of the form (01)κ/2
or (10)κ/2 , but the patterns 01(01)κ/2 10 and 01(10)κ/2 10 are not allowed
and hence not embedded in a point of X.
A shift space has bounded propagation if a finite pattern is allowed
whenever all restrictions of it to balls of a fixed radius are allowed, as
defined in
Definition 2.33. Let X be a subshift of QM and let ρ be a nonnegative integer. The subshift X is said to have ρ-bounded propagation
if and only if
∀ F ⊆ M finite ∀ p ∈ QF :



∀ f ∈ F : pB(f,ρ)∩F ∈ XB(f,ρ)∩F =⇒ p ∈ XF .
Remark 2.34. Let X be a subshift of QM with ρ-bounded propagation. For each non-negative integer ρ0 such that ρ0 ≥ ρ, the subshift X
has ρ0 -bounded propagation.
Definition 2.35. Let X be a subshift of QM . It is said to have bounded
propagation if and only if there is a non-negative integer ρ such that it
has ρ-bounded propagation.

THE MOORE AND THE MYHILL PROPERTY

17

A subshift with bounded propagation is strongly irreducible and of
finite type, which is shown in
Lemma 2.36. Let X be a subshift of QM with ρ-bounded propagation.
It is ρ-strongly irreducible and ρ-step.
Proof. Let (p, p0 ) be a tuple of finite patterns allowed in X such that
d(dom(p), dom(p0 )) ≥ ρ+1. Moreover, let F = dom(p)∪dom(p0 ) and let
p00 = p × p0 ∈ QF . Furthermore, let f ∈ F . Then, if f ∈ dom(p), then
B(f, ρ) ∩ F ⊆ dom(p); and, if f ∈ dom(p0 ), then B(f, ρ) ∩ F ⊆ dom(p0 ).
Thus, in either case, p00 B(f,ρ)∩F ∈ XB(f,ρ)∩F . Hence, because X has ρbounded propagation, we have p00 ∈ XF . Therefore, there is an x ∈ X
such that xF = p00 , in particular, xdom(p) = p and xdom(p0 ) = p0 . In
conclusion, X is ρ-strongly irreducible.
Let c ∈ QM such that, for each m ∈ M , we have cB(m,ρ) ∈ XB(m,ρ) .
Moreover, let ρ0 ∈ N0 . Then, for each f ∈ B(ρ0 ), we have (cB(ρ0 ) )B(f,ρ)∩B(ρ0 ) =
(cB(f,ρ) )B(ρ0 )∩B(f,ρ) ∈ (XB(f,ρ) )B(ρ0 )∩B(f,ρ) = XB(f,ρ)∩B(ρ0 ) . Thus, because
X has ρ-bounded propagation, we have cB(ρ0 ) ∈ XB(ρ0 ) . Hence, according to Lemma 2.16, we have c ∈ X. In conclusion, according to
Lemma 2.24, the subshift X is ρ-step.

Example 2.37 (Has Bounded Propagation or Not). The full shift (Example 2.8) and the empty shift (Example 2.9) have 0-bounded propagation. The golden mean shift (Example 2.10) has 1-bounded propagation. The even shift (Example 2.11) is, according to Example 2.20,
not of finite type and hence it is, according to Lemma 2.36, does not
have bounded propagation. The shift of Example 2.32 is not strongly
irreducible and hence it is, according to Lemma 2.36, does not have
bounded propagation.
Example 2.38 (Generalised Golden Mean Shifts [3, Example 2.8]).
Let q be a positive integer, let Q be the set {0, 1, . . . , q}, let k be
a positive integer, let {Fi }i∈{1,2,...,k} be a family of finite subsets of
M
that
S that contain m0 , let ρ be the least non-negative integer such B(ρ)
F
⊆
B(ρ),
and
let
X
be
the
ρ-step
subshift
hp
∈
Q
|
i
i∈{1,2,...,k}
M
∀ i ∈ {1, 2, . . . , k} ∀ m ∈ Fi : p(m) 6= 0i of Q . The subshift X is
called generalised golden mean shift, it is equal to {c ∈ QM | ∀ i ∈
{1, 2, . . . , k} ∀ h ∈ H ∃ m ∈ h . Fi : c(m) = 0}, and it has ρ-bounded
propagation, in particular, according to Lemma 2.36, it is ρ-strongly
irreducible.
In the case that R is the cell space from Example 1.2, q = 1, k = 1,
and F1 = {0, 1}, the non-negative integer ρ is equal to 1 and the
generalised golden mean shift X is equal to the golden mean shift from
Example 2.10.

18

SIMON WACKER

Proof of Bounded Propagation. Let F be a finite subset of M , let p be
a pattern of QF such that
∀ f ∈ F : pB(f,ρ)∩F ∈ XB(f,ρ)∩F ,
and let c be the point of QM that is equal to p on F and identically
0 on M r F . Moreover, let i ∈ I and let h ∈ H. If h . Fi * F ,
then, there is an m ∈ (h . Fi ) r F , and, by definition of c, we have
c(m) = 0. Otherwise, if h . Fi ⊆ F , then, because m0 ∈ Fi , we
have h . m0 ∈ F ; thus, because pB(h.m0 ,ρ)∩F ∈ XB(h.m0 ,ρ)∩F , there is
a point x ∈ X such that pB(h.m0 ,ρ)∩F = xB(h.m0 ,ρ)∩F ; hence, by the
characterisation of X, there is a cell m ∈ h . Fi such that x(m) = 0;
and therefore, because h . Fi ⊆ (h . B(ρ)) ∩ F = B(h . m0 , ρ) ∩ F ,
we have c(m) = p(m) = x(m) = 0. Hence, in either case, there is an
m ∈ h . Fi such that c(m) = 0. Therefore, by the characterisation of
X, we have c ∈ X and hence p = cF ∈ XF . In conclusion, X has
ρ-bounded propagation.

Example 2.39 ([4, Section 4, at the very end]). In the situation of
Example 1.2, the subshift h010, 111i of {0, 1}Z is strongly irreducible
and of finite type but does not have bounded propagation.
A map from a shift space to another shift space is local if the image
of a point is uniformly and locally determined in each cell, as defined
in
Definition 2.40. Let X and Y be two subshifts of QM , let ∆ be a
map from X to Y , let κ be a non-negative integer, let N be a subset
of B(κ) such that G0 . N ⊆ N , and let •H0 be the left group action
IH0 ×XN →XN of H0 on XN . The map ∆ is called κ-local if and only if
there is a •H0 -invariant map δ : XN → Q such that
∀ x ∈ X ∀ m ∈ M : ∆(x)(m) = δ(n 7→ x(m P n)).
Remark 2.41. For each point x ∈ X and each cell m ∈ M , we have
−1
I x)N ).
∆(x)(m) = δ((gm
0 ,m
Remark 2.42. Let ∆ be a κ-local map from X to Y . For each nonnegative integer κ0 such that κ0 ≥ κ, the map ∆ is κ0 -local.
Definition 2.43. Let X and Y be two subshifts of QM and let ∆ be
a map from X to Y . The map ∆ is called local if and only if there is
a non-negative integer κ such that it is κ-local.
Remark 2.44. Let X and Y be two subshifts of QM and let ∆ be a
map from X to Y . The map ∆ is local if and only if it is the restriction
to X → Y of the global transition function of a big-cellular automaton
over R with set of states Q and finite neighbourhood.

THE MOORE AND THE MYHILL PROPERTY

19

Example 2.45 (Sliding Block Codes [5, Definition 1.5.1]). In the situation of Example 1.2, local maps are but sliding block codes.
Example 2.46 (From Golden Mean to Even Shift [5, Example 1.5.6]).
Let X be the golden mean shift (Example 2.10), let Y be the even
shift (Example 2.11), let δ be the map from X{0,1} to {0, 1} given by
00 7→ 1, 01 7→ 0, and 10 7→ 0, and let ∆ be the map from X to Y given
by x 7→ [z 7→ δ(n 7→ x(z + n))]. The map ∆ is, by definition, local and
it is, according to [5, Example 1.5.6], surjective.
Domain and codomain of a local map can be restricted simultaneously to a subset of cells and its interior, as is done in
Definition 2.47. Let ∆ be a κ-local map from X to Y and let A be
a subset of M . The map
∆−
A : XA → YA−κ ,
p 7→ ∆(c)A−κ , where c ∈ X such that cA = p,
is called restriction of ∆ to A.
The image of a local map is a shift space, which is shown in
Lemma 2.48. Let ∆ be a local map from X to Y . Its image ∆(X) is
a subshift of QM .
Proof. According to Lemma 2.17, the shift space X is compact. And,
according to Remark 2.44 and [9, Corollary 3], the map ∆ is continuous.
Therefore, the topological space ∆(X) is compact and hence closed.
Moreover, because h I ∆(X) = ∆(h I X) = ∆(X), the topological
space ∆(X) is shift-invariant. Therefore, according to Lemma 2.17,
the topological space ∆(X) is a subshift of QM .

The difference of two points of the full shift is the set of cells in which
they differ, as defined in
Definition 2.49. Let c and c0 be two points of QM . The set diff(c, c0 ) =
{m ∈ M | c(m) 6= c0 (m)} is called difference of c and c0 .
A local map is pre-injective if it is injective on points with finite
support, as defined in
Definition 2.50. Let ∆ be a local map from X to Y . It is called
pre-injective if and only if, for each tuple (x, x0 ) ∈ X × X such that
diff(x, x0 ) is finite and ∆(x) = ∆(x0 ), we have x = x0 .
A bijective local map with local inverse is a conjugacy, and its domain
and codomain are conjugate, which is defined in

20

SIMON WACKER

Definition 2.51. Let ∆ be a local map from X to Y . It is called
conjugacy if and only if it is bijective and its inverse is local.
Definition 2.52. Let X and Y be two shift spaces. They are called
conjugate if and only if there is a conjugacy from X to Y .
Entropy of shift spaces is invariant under conjugacy, which is shown
in
Lemma 2.53. Let R be right amenable, let F be a right Følner net
in R, and let X and Y be two conjugate subshifts of QM . Then,
entF (X) = entF (Y ).
Proof. This is a direct consequence of Remark 2.44 and [11, Theorem 3].

Definition 2.54. Let X be a subshift of QM . It is said to have the
(1) Moore property if and only if each surjective local map from X
to X is pre-injective;
(2) Myhill property if and only if each pre-injective local map from
X to X is surjective.
Remark 2.55. Both the Moore and the Myhill property is invariant
under conjugacy.
3. Tilings
Contents. A (θ, κ, θ0 )-tiling is a subset of cells such that the balls of
radius θ about those cells are pairwise at least κ + 1 apart and the
balls of radius θ0 about those cells cover all cells (see Definitions 3.1
and 3.3). If there are infinitely many cells, then, for each θ and κ, there
is a (θ, κ, 4θ + 2κ)-tiling (see Theorem 3.5). And, a subset of a strongly
irreducible shift space has less entropy than that space if about each
point of a (θ, κ, θ0 )-tiling the subset has fewer patterns with ball-shaped
domains of radius θ than the space (see Theorem 3.10); in the proof of
that statement we use Lemmas 3.6, 3.7 and 3.9 and Corollary 3.8.
Definition 3.1. Let {Aj }j∈J be a family of subsets of M and let κ be
a non-negative integer. The family {Aj }j∈J is called pairwise at least
κ + 1 apart if and only if

∀ j ∈ J ∀ j 0 ∈ J : j 6= j 0 =⇒ d(Aj , Aj 0 ) ≥ κ + 1 .
Remark 3.2. Each pairwise at least κ + 1 apart family is pairwise
disjoint. And each pairwise disjoint family is pairwise at least 0 + 1
apart.

THE MOORE AND THE MYHILL PROPERTY

21

Definition 3.3. Let T be a subset of M , and let θ, κ, and θ0 be three
non-negative integers. The set T is called (θ, κ, θ0 )-tiling of R if and
only if the family {B(t, θ)}t∈T is pairwise at least κ + 1 apart and the
family {B(t, θ0 )}t∈T is a cover of M .
Remark 3.4. According to Remark 3.2, each (θ, κ, θ0 )-tiling of R is a
(B(θ), B(θ0 ))-tiling of R, see [11, Definition 2]; and each (B(θ), B(θ0 ))tiling of R is a (θ, 0, θ0 )-tiling of R.
Greedily picking elements that are pairwise far enough apart yields
a tiling, which we show in
Theorem 3.5. Let M be infinite, and let θ and κ be two non-negative
integers. There is a countably infinite (θ, κ, θ0 )-tiling T of R, where
θ0 = 4θ + 2κ.
Usage Note. In the proof, infiniteness of M is used to deduce that
spheres of arbitrarily big radii are non-empty.
Proof Sketch. From each of the spheres S(i(2θ + κ + 1)), for i ∈ N0 ,
pick elements that are pairwise at least 2θ + κ + 1 apart and whose
(2θ+κ)-closure covers the sphere — they constitute a set T . The family
{B(t, θ)}t∈T is pairwise at least κ + 1 apart and the family {B(t, 4θ +
2κ)}t∈T is a cover of M . See Figure 1 for a schematic representation.
Proof. Let i ∈ N0 . Furthermore, let Mi,1 = S(i(2θ + κ + 1)). Then,
because M is infinite, according to [12, Corollary 8.15], the set Mi,1
is non-empty and finite. For j ∈ N+ in increasing order, if Mi,j r
{mi,1 , mi,2 , . . . , mi,j−1 } =
6 ∅, then choose mi,j ∈ Mi,j r{mi,1 , mi,2 , . . . , mi,j−1 }
and put
Mi,j+1 = {mi,j } ∪ Mi,j r B(mi,j , 2θ + κ)
= {m ∈ Mi,j | d(m, mi,j ) = 0 or d(m, mi,j ) ≥ 2θ + κ + 1};
otherwise stop, put ji = j and put Mi = Mi,ji (see Figure 1).
By construction,
(4)


∀ m ∈ Mi ∀ m0 ∈ Mi : m 6= m0 =⇒ d(m, m0 ) ≥ 2θ + κ + 1 ,

and
(5)

∀ m ∈ Mi,1 ∃ m0 ∈ Mi : d(m, m0 ) ≤ 2θ + κ,

and, for each i0 ∈ N0 with i0 6= i, because Mi ⊆ Mi,1 and Mi0 ⊆ Mi0 ,1 ,
and M is infinite, according to [12, Corollary 5.18],
(6)

d(Mi , Mi0 ) ≥ d(Mi,1 , Mi0 ,1 ) ≥ 2θ + κ + 1.

22

SIMON WACKER

m

mi,1
0

m

mi,2 = m00

mi,5

mi,3
mi,4

Figure 1. Schematic representation of the set-up of the
proof of Theorem 3.5. The whole space is M ; the
dot in the centre is m0 ; the smaller solid circle is
Mi,1 = S(i(2θ + κ + 1)) and the larger solid circle
is Mi+1,1 = S((i + 1)(2θ + κ + 1)); the dots on the
smaller solid circle are the elements of Mi ; the
region enclosed by the dotted circle about mi,j
is B(mi,j , θ); the region enclosed by the dashdotted circle about mi,j is B(mi,j , θ + κ); the region enclosed by the dashed circle about mi,j is
B(mi,j , 2θ + κ); the dots labelled m, m0 , and m00
are the respective elements from the last part of
the proof.

S
Let T = i∈N0 Mi . Because, for each i ∈ N0 , the set Mi is finite, the
set T is countable. And, because (Mi,1 )i∈N0 is pairwise disjoint, so is
(Mi )i∈N0 and hence T is infinite. Thus, T is countably infinite.

THE MOORE AND THE MYHILL PROPERTY

23

Subproof of: {B(t, θ)}t∈T is pairwise at least κ + 1 apart.
Let t, t0 ∈ T such that t 6= t0 . If there is an i ∈ N0 such that t, t0 ∈ Mi ,
then, according to Equation (4), we have d(t, t0 ) ≥ 2θ+κ+1. Otherwise,
there are i, i0 ∈ N0 with i 6= i0 such that t ∈ Mi and t0 ∈ Mi0 , and then,
according to Equation (6), we have d(t, t0 ) ≥ d(Mi , Mi0 ) ≥ 2θ + κ + 1.
In conclusion, in both cases, according to [12, Lemma 5.20], we have
d(B(t, θ), B(t0 , θ)) ≥ κ + 1.
Subproof of: {B(t, 4θ + 2κ)}t∈T is a cover of M (see Figure 1).
Let m ∈ M . Then, there is an i ∈ N0 such that i(2θ + κ + 1) ≤
|m| < (i + 1)(2θ + κ + 1). Hence, according to [12, Lemma 5.17],
d(m, Mi,1 ) = d(Mi,1 , m) ≤ d(m0 , m) − i(2θ + κ + 1)
< (i + 1)(2θ + κ + 1) − i(2θ + κ + 1) = 2θ + κ + 1.
Thus, d(m, Mi,1 ) ≤ 2θ + κ. Therefore, there is an m0 ∈ Mi,1 such that
d(m, m0 ) ≤ 2θ + κ. Moreover, according to Equation (5), there is an
m00 ∈ Mi such that d(m0 , m00 ) ≤ 2θ + κ. Thus,
d(m, m00 ) ≤ d(m, m0 ) + d(m0 , m00 ) ≤ 4θ + 2κ.
00
00
Hence,
S m ∈ B(m , 4θ + 2κ). Therefore,
S because m ∈ T , we have
m ∈ t∈T B(t, 4θ + 2κ). In conclusion, t∈T B(t, 4θ + 2κ) = M .


One by one forbidding subpatterns with similar domains that are far
enough apart in a set of finite patterns, decreases its size by at least a
multiplicative constant between 0 and 1 in each step. In other words,
the number of finite patterns with a fixed domain, excluding those
in which some subpatterns with similar domains that are far enough
apart are embedded, is bounded above by some constant between 0 and
1 raised to the power of the number of forbidden subpatterns times the
number of all finite patterns with the fixed domain, which is shown in
Lemma 3.6. Let X be a non-empty and κ-strongly irreducible subshift
of QM , let F be a finite subset of M , let θ be a non-negative integer, let
T be a subset of M such that the family {B(t, θ)}t∈T is pairwise at least
κ + 1 apart, and, for each element t ∈ T , let pt be a pattern of XB(t,θ) .
Furthermore, let ξ be the positive integer |XB(θ)+κ |, let S be the finite
set T ∩ F −(θ+κ) (= {t ∈ T | B(t, θ)+κ ⊆ F }), and, for each element
s ∈ S, let πs be the map XF → XB(s,θ) , p 7→ pB(s,θ) (see Figure 2).
Then,
[
|XF r
πs−1 (ps )| ≤ (1 − ξ −1 )|S| · |XF |.
s∈S

24

SIMON WACKER

The whole space is M ; the dots
and circles are the elements of the
set T ; for each element t ∈ T ,
the region enclosed by the rectangle
with solid border about t is the set
B(t, θ) and the region enclosed by
the rectangle with dash-dotted border about t is the set B(t, θ)+κ ;
the region enclosed by the rectangle
with dashed border is F ; the region
enclosed by the rectangle with dotted border is F −(θ+κ) ; the circles are
the elements of S = T ∩ F −(θ+κ) ;
the
S hatched region is the set F r
( s∈S B(s, θ)).
Figure 2. Schematic representation of the set-up of Lemma 3.6.

Usage Note. In the proof, κ-strong irreducibility is used to extend an
in X allowed F r B(s, θ)+κ -pattern by the B(s, θ)-pattern ps and a
∂κ+ B(s, θ)-pattern to an in X allowed F -pattern.
Proof Sketch. Let {sj }j∈{1,2,...,|S|} be an enumeration of S, let Z0 = XF ,
(psϑ+1 )∩Zϑ ).
and, for each ϑ ∈ {0, 1, . . . , |S|−1}, let Zϑ+1 = Zϑ r(πs−1
ϑ+1
Furthermore, let ϑ ∈ {0, 1, . . . , |S| − 1}. Then, |Zϑ | ≤ |XB(sϑ+1 ,θ)+κ | ·
|(Zϑ )F rB(sϑ+1 ,θ)+κ | = ξ·|(Zϑ )F rB(sϑ+1 ,θ)+κ |. And, because X is κ-strongly
irreducible, each pattern of (Zϑ )F rB(sϑ+1 ,θ)+κ can be extended by psϑ+1
and a pattern with domain B(sϑ+1 , θ)+κ r B(sϑ+1 , θ) to a pattern of
πs−1
(psϑ+1 ) ∩ Zϑ and thus |(Zϑ )F rB(sϑ+1 ,θ)+κ | ≤ |πs−1
(psϑ+1 ) ∩ Zϑ |.
ϑ+1
ϑ+1
−1
−1
Hence, |πsϑ+1 (psϑ+1 ) ∩ Zϑ | ≥ ξ · |Zϑ |. Therefore, |Zϑ+1 | = |Zϑ | −
|πs−1
(psϑ+1 ) ∩ Zϑ | ≤ (1 − ξ −1 ) · |Zϑ |. The statement follows by inducϑ+1
tion.
Proof. As claimed, because X 6= ∅, the integer ξ is positive; because,
according to [12, Corollary 5.14] and [12, Item 2 of Corollary 6.3],
s P B(θ+κ) = B(s, θ)+κ ,Swe have S = T ∩F −(θ+κ) = {t ∈ T | B(t, θ)+κ ⊆
F }; and, because S ⊆ s∈S B(s, θ)+κ ⊆ F and F is finite, the set S is
finite.

THE MOORE AND THE MYHILL PROPERTY

25

Let {Bs }s∈S = {B(s, θ)}s∈S , let {sj }j∈{1,2,...,|S|} be an enumeration of
S, and, for each ϑ ∈ {0, 1, . . . , |S|}, let
Zϑ = XF r

ϑ
[

πs−1
(psj )
j



= {p ∈ XF | ∀ j ∈ {1, 2, . . . , ϑ} : pBsj


6 ps j } .
=

j=1

To establish the claim, we prove by induction on ϑ, that, for each
ϑ ∈ {0, 1, . . . , |S|},
(7)

|Zϑ | ≤ (1 − ξ −1 )ϑ · |XF |.

Base Case.
S
(psj ) = ∅ and (1 − ξ −1 )0 = 1,
Let ϑ = 0. Then, because 0j=1 πs−1
j
Equation (7) holds. Note that 00 = 1.
Inductive Step.
Let ϑ ∈ {0, 1, . . . , |S| − 1} such that Equation (7), called inductive
hypothesis, holds. Furthermore, let Z = Zϑ . Because Bs+κ
⊆ F,
ϑ+1
Z ⊆ ZBs+κ × ZF rBs+κ ⊆ XBs+κ × ZF rBs+κ .
ϑ+1

ϑ+1

ϑ+1

ϑ+1

Hence, |Z| ≤ |XBs+κ |·|ZF rBs+κ |. Moreover, according to Remark 2.15,
ϑ+1
ϑ+1
= sϑ+1 P
we have |XBs+κ | = |XB(θ)+κ | = ξ (where we used that Bs+κ
ϑ+1
ϑ+1
B(θ)+κ , which holds according to [12, Corollary 5.14] and [12, Item 2
of Corollary 6.3]). Therefore, |Z| ≤ ξ · |ZF rBs+κ |.
ϑ+1
Let p ∈ ZF rBs+κ . Then, p ∈ XF rBs+κ . Moreover, according to [12,
ϑ+1
ϑ+1
) ≥ κ + 1. Hence, because X is
Lemma 6.5], we have d(Bsϑ+1 , F r Bs+κ
ϑ+1
00
κ-strongly irreducible, there is a p ∈ XF such that p00 dom(p) = p and
p00 dom(psϑ+1 ) = psϑ+1 . Furthermore, because {B(t, θ)}t∈T is pairwise at
least κ + 1 apart, for each j ∈ {1, 2, . . . , ϑ}, we have Bsj ⊆ F r Bs+κ
.
ϑ+1
Therefore, for each j ∈ {1, 2, . . . , ϑ}, we have p00 Bsj = pBsj 6= psj
and hence p00 ∈
/ πs−1
(psj ). Thus, p00 ∈ Z. Moreover, p00 ∈ πs−1
(psϑ+1 ).
j
ϑ+1
−1
Therefore, |ZF rBs+κ | ≤ |πsϑ+1 (psϑ+1 ) ∩ Z|.
ϑ+1
Together,
|Z| ≤ ξ · |πs−1
(psϑ+1 ) ∩ Z|.
ϑ+1
Because Zϑ+1 = Z r πs−1
(psϑ+1 ),
ϑ+1
|Zϑ+1 | = |Z r πs−1
(psϑ+1 )|
ϑ+1
= |Z r (πs−1
(psϑ+1 ) ∩ Z)|
ϑ+1
= |Z| − |πs−1
(psϑ+1 ) ∩ Z|
ϑ+1
≤ |Z| − ξ −1 · |Z|

26

SIMON WACKER

The whole space is M ; the dots
and circles are the elements of the
set T ; for each element t ∈ T ,
the region enclosed by the rectangle
with solid border about t is the set
B(t, θ)+κ and the region enclosed by
the rectangle with dash-dotted border about t is the set B(t, θ0 ); the region enclosed by the rectangle with
dashed border is F ; the region enclosed by the smallest rectangle with
0
dotted border is F −(θ+κ+θ ) and the
region enclosed by the largest rectangle with dotted border is F −(θ+κ) ;
the circles are the elements of S =
T ∩ F −(θ+κ) .
Figure 3. Schematic representation of the set-up of Lemma 3.7.

= (1 − ξ −1 ) · |Z|.
Hence, according to the inductive hypothesis,
|Zϑ+1 | ≤ (1 − ξ −1 ) · (1 − ξ −1 )ϑ · |XF |
= (1 − ξ −1 )ϑ+1 · |XF |.
In conclusion, according to the principle of mathematical induction,
for each ϑ ∈ {0, 1, . . . , |S|}, Equation (7) holds.

The number of elements in a finite set is bounded above by the
number of elements its interior shares with a tiling times the number
of elements of a big enough ball plus the number of elements of a big
enough boundary of the finite set, which is shown in
Lemma 3.7. Let F be a finite subset of M , let θ, κ, and θ0 be three
non-negative integers, let T be a subset of M such that {B(t, θ0 )}t∈T
is a cover of M , and let S be the finite set T ∩ F −(θ+κ) (= {t ∈ T |
B(t, θ)+κ ⊆ F }) (see Figure 3). Then,
−
|F | ≤ |S| · |B(θ0 )| + |∂θ+κ+θ
0 F |.
0

0

Proof Sketch. For each m ∈ F , if mS ∈
/ S +θ , then m ∈
/ F −(θ+κ+θ ) .
−
+θ0
−(θ+κ+θ0 )
0
Thus, F ⊆ S ∪ F r F
= ( s∈S B(s, θ )) ∪ ∂θ+κ+θ0 F . Hence,
−
0
|F | ≤ |S| · |B(θ )| + |∂θ+κ+θ0 F |.

THE MOORE AND THE MYHILL PROPERTY

27

S
Proof. Let m ∈ F r s∈S B(s, θ0 ). Because {B(t, θ0 )}t∈T Sis a cover of
M , there is a t ∈ T such that m ∈ B(t, θ0 ). Because m ∈
/ s∈S B(s, θ0 ),
we have t ∈
/ S and hence B(t, θ)+κ * F . Because m ∈ B(t, θ0 ), we
0
have d(m, t) ≤ θ0 and hence t ∈ B(m, θ0 ) = {m}+θ . Suppose that
0
m ∈ F −(θ+κ+θ ) . Then, according to [12, Item 2 of Lemma 6.2] and [12,
Item 5 of Lemma 6.4],
B(t, θ)+κ = ({t}+θ )+κ

+κ
+θ0 +θ
⊆ {m}
0

= {m}+(θ+κ+θ )
0

0

⊆ (F −(θ+κ+θ ) )+(θ+κ+θ )
= F,
0

which contradicts that B(t, θ)+κ * F . Hence, m ∈ F r F −(θ+κ+θ ) =
−
∂θ+κ+θ
0 F . Therefore,
[

−
B(s, θ0 ) ∪ ∂θ+κ+θ
F ⊆
0 F.
s∈S

Moreover, because S ⊆ s∈S B(s, θ)+κ ⊆ F and F is finite, the set S is
finite. And, for each s ∈ S, according to [12, Corollary 5.11], we have
|B(s, θ0 )| = |B(θ0 )|. In conclusion,
X
−
|F | ≤
|B(θ0 )| + |∂θ+κ+θ
0F |
S

s∈S
−
= |S| · |B(θ0 )| + |∂θ+κ+θ
0 F |.


The number of elements that the components of a right Følner net
share with a tiling is asymptotically bounded below away from zero,
which is shown in
Corollary 3.8. Let R be right amenable, let {Fi }i∈I be a right Følner
net in R, let θ, κ, and θ0 be three non-negative integers, let T be a
subset of M such that {B(t, θ0 )}t∈T is a cover of M . There is a positive
real number ε ∈ R>0 and there is an index i0 ∈ I such that, for each
−(θ+κ)
index i ∈ I with i ≥ i0 , we have |T ∩ Fi
| ≥ ε|Fi |.
−(θ+κ)

Proof. Let i ∈ I and let Ti = T ∩ Fi

. According to Lemma 3.7,

−
|Fi | ≤ |Ti | · |B(θ0 )| + |∂θ+κ+θ
0 Fi |.

28

SIMON WACKER

−
Thus, because ∂θ+κ+θ
0 Fi ⊆ ∂θ+κ+θ 0 Fi ,


|Ti |
1
|∂θ+κ+θ0 Fi |
≥
· 1−
.
|Fi |
|B(θ0 )|
|Fi |

According to [12, Theorem 10.6], there is an i0 ∈ I

|∂θ+κ+θ0 Fi |
∀ i ∈ I : i ≥ i0 =⇒
≤
|Fi |

such that

1
.
2

Let ε = 1/(2|B(θ0 )|). Then, for each i ∈ I with i ≥ i0 ,
|Ti |
1
≥
= ε.
|Fi |
2|B(θ0 )|

If a shift space has at least two points, then, for each non-empty
domain, it has at least two patterns.
Lemma 3.9. Let X be a subshift of QM such that |X| ≥ 2 and let A
be a non-empty subset of M . Then, |XA | ≥ 2.
Proof. Because |X| ≥ 2, there are x and x0 in X such that x 6= x0 .
Thus, there is an m ∈ M such that x(m) 6= x0 (m). And, because A is
−1
is contained
non-empty, there is an a ∈ A. The element h = gm0 ,a gm
0 ,m
−1
in H and satisfies h . a = m. Hence, (h I x)(a) 6= (h I x0 )(a).
Therefore, (h I x)A and (h I x0 )A are distinct and are contained in
XA . In conclusion, |XA | ≥ 2.

A subset of a strongly irreducible shift space has less entropy than
that space if about each point of a tiling the subset has fewer patterns
of a certain radius than the space, which is shown in
Theorem 3.10. Let R be right amenable, let F = {Fi }i∈I be a right
Følner net in R, let X be a κ-strongly irreducible subshift of QM such
that |X| ≥ 2, let Y be a subset of X, and let T be a (θ, κ, θ0 )-tiling of
R such that, for each element t ∈ T , we have YB(t,θ) $ XB(t,θ) . Then,
entF (Y ) < entF (X).
Usage Note. In the proof, κ-strong
is used to apply Lemma 3.6
S irreducibility
−1
yielding the inequality |XFi r t∈Ti πi,t
(pt )| ≤ (1 − ξ −1 )|Ti | · |XFi |.
−(θ+κ)

Proof Sketch. Let pt ∈ XB(t,θ) r YB(t,θ) and let Ti = T ∩ Fi
. Then,
S
−1
−1 |Ti |
YFi ⊆ XFi r t∈Ti πi,t (pt ). Hence, |YFi | ≤ (1−ξ ) ·|XFi |. Therefore,
log|YFi |/|Fi | ≤ log(1 − ξ −1 ) · |Ti |/|Fi | + log|XFi |/|Fi |. In conclusion,
because log(1−ξ −1 ) < 0 and {|Ti |/|Fi |}i∈I is eventually bounded below
away from zero, we have entF (Y ) < entF (X).

THE MOORE AND THE MYHILL PROPERTY

29

Proof. For each t ∈ T , because YB(t,θ) $ XB(t,θ) , we have XB(t,θ) r
YB(t,θ) 6= ∅. Let {pt }t∈T be a transversal of {XB(t,θ) r YB(t,θ) }t∈T and
−(θ+κ)
let ξ = |XB(θ)+κ |. Furthermore, let i ∈ I, let Ti = T ∩ Fi
(=
{t ∈ T | B(t, θ)+κ ⊆ Fi }) and, for each t ∈ Ti , let πi,t : XFi → XB(t,θ) ,
p 7→ pB(t,θ) . Note that, because |X| ≥ 2, according to Lemma 3.9, we
have ξ ≥ 2 and hence 1 − ξ −1 > 0.
Because {B(t, θ)}t∈T is pairwise at least κ + 1 apart, according to
Lemma 3.6,
[
|XFi r
πt−1 (pt )| ≤ (1 − ξ −1 )|Ti | · |XFi |.
t∈Ti
−1
For each t ∈ Ti , because pt ∈
/ YB(t,θ) , we have πi,t
(pt ) ∩ YFi = ∅. Hence,

S
−1
t∈Ti πi,t (pt ) ∩ YFi = ∅. Therefore,
[
−1
|YFi | = |YFi r
πi,t
(pt )|
t∈Ti

≤ |XFi r

[

−1
πi,t
(pt )|

t∈Ti
−1 |Ti |

≤ (1 − ξ )

· |XFi |.

Thus,
log|YFi |
|Ti |
log|XFi |
≤
· log(1 − ξ −1 ) +
.
|Fi |
|Fi |
|Fi |
Because {B(t, θ0 )}t∈T is a cover of M , according to Corollary 3.8, there
is an ε ∈ R>0 and there is an i0 ∈ I such that


|Ti |
∀ i ∈ I : i ≥ i0 =⇒
≥ε .
|Fi |
Hence, because log(1 − ξ −1 ) < 0,
entF (Y ) ≤ ε · log(1 − ξ −1 ) + entF (X) < entF (X).

4. The Garden of Eden Theorems
Contents. The image of a local map to a strongly irreducible shift space
that is not surjective does not have maximal entropy (see Theorem 4.1).
And the converse of that statement obviously holds. Moreover, a local
map from a strongly irreducible shift space of finite type whose image
has less entropy than its domain is not pre-injective (see Theorem 4.3).
And the converse of that statement also holds (see Theorem 4.5). These

30

SIMON WACKER

four statements establish the Garden of Eden theorem (see Main Theorem 4.7). It follows that strongly irreducible shift spaces of finite type
have the Moore and the Myhill property (see Corollary 4.8).
Body. Because a local map that is not surjective has a Garden of Eden
pattern, the entropy of its image is not maximal, which is shown in
Theorem 4.1. Let R be right amenable, let F be a right Følner net
in R, let M be infinite, let X be a non-empty subshift of QM , let Y be
a strongly irreducible subshift of QM , and let ∆ be a local map from X
to Y that is not surjective. Then, entF (∆(X)) < entF (Y ).
Usage Note. In the proof, infiniteness of M is used to apply Theorem 3.5 yielding a tiling, locality of ∆ is used to apply Lemma 2.48
yielding that ∆(X) is a subshift of QM , and strong irreducibility of Y
is used to apply Theorem 3.10 yielding a strict inequality for entropies.
Proof Sketch. Because ∆ is not surjective, there is a Garden of Eden
configuration. Thus, because ∆ is local, there is a Garden of Eden
pattern. Hence, there are too many Garden of Eden configurations for
the entropy to be maximal.
Proof. Because Y is strongly irreducible, there is a κ ∈ N0 such that
Y is κ-strongly irreducible. And, because ∆ is not surjective, there is
a y ∈ Y r ∆(X). Hence, according to Lemma 2.16, there is a ρ ∈ N0
such that yB(ρ) ∈
/ (∆(X))B(ρ) and thus yB(ρ) ∈ YB(ρ) r (∆(X))B(ρ) .
And, because M is infinite, according to Theorem 3.5, there is a (ρ, κ,
θ0 )-tiling T of R.
According to Lemma 2.48, the set ∆(X) is a subshift of QM . And, for
each t ∈ T , according to [12, Corollary 5.14], we have t P B(ρ) = B(t, ρ).
Therefore, for each t ∈ T , because t J _ is bijective and according to
Remark 2.15, we have t J (yB(ρ) ) ∈ YB(t,ρ) r (∆(X))B(t,ρ) and thus
(∆(X))B(t,ρ) $ YB(t,ρ) .
Because X is non-empty and ∆ is not surjective, we have |Y | ≥
2. In conclusion, because Y is κ-strongly irreducible, according to
Theorem 3.10, we have entF (∆(X)) < entF (Y ).

If there are less patterns in the codomain of a local map than in its
domain, at least two patterns have the same image, which is shown in
Lemma 4.2. Let X be a κ-strongly irreducible subshift of QM , let Y
be a subshift of QM , let ∆ be a κ-local map from X to Y , and let
F be a finite subset of M such that |YF +2κ | < |XF |. There are two
0
+ +κ = p  + +κ , and
patterns p and p0 in XF +3κ such that p 6= p0 , p∂2κ
F
∂2κ F
−
0
∆−
(p)
=
∆
(p
).
+3κ
+3κ
F
F

THE MOORE AND THE MYHILL PROPERTY

31

Usage Note. In the proof, strong irreducibility of X is used to extend
+ +κ
an in X allowed F -pattern by an in X allowed ∂2κ
F -pattern and an
+3κ
+
∂κ F -pattern to an in X allowed F -pattern; and κ-locality of ∆ is
used to restrict it to a map from XF +3κ to YF +2κ .
Proof. Because |YF +2κ | < |XF |, we have |XF | > 0, thus XF 6= ∅, and
+ +κ . Let Pv = {p ∈ XF +3κ |
hence X 6= ∅. Therefore, there is a v ∈ X∂2κ
F
pdom(v) = v}. Note that, according to [12, Item 4 of Lemma 6.4], we
+ +κ
have ∂2κ
F = F +3κ r F +κ .
Let u ∈ XF . According to [12, Corollary 6.6], we have d(F, dom(v)) ≥
κ + 1. Hence, because X is κ-strongly irreducible, there is an x ∈ X
such that xF = u and xdom(v) = v. Let p = xF +3κ . Then, pF = u
and p ∈ Pv .
+3κ →
Therefore, |Pv | ≥ |XF | > |YF +2κ |. The restriction φ of ∆−
F +3κ : XF
−
YF +2κ to Pv → ∆F +3κ (Pv ) is surjective. Note that, because ∆ is κ-local
and, according to [12, Item 5 of Lemma 6.4], we have (F +3κ )−κ ⊇ F +2κ ,
we can choose YF +2κ as the codomain of ∆−
F +3κ . If φ were injective, then
|Pv | = |φ(Pv )| ≤ |YF +2κ |, which contradicts that |Pv | > |YF +2κ |. Hence,
φ is not injective. In conclusion, there are p, p0 ∈ Pv such that p 6= p0
and φ(p) = φ(p0 ).

Because a local map, that has an image whose entropy is less than
the entropy of its domain, maps at least two finite patterns to the same
pattern, it is not pre-injective, which is shown in
Theorem 4.3. Let R be right amenable, let F = {Fi }i∈I be a right
Følner net in R, let X be a strongly irreducible subshift of QM of finite
type, let Y be a subshift of QM , and let ∆ be a local map from X to Y
such that entF (∆(X)) < entF (X). The map ∆ is not pre-injective.
Usage Note. In the proof, strong irreducibility of X and locality of
∆ are used to apply Lemma 4.2 yielding two distinct finite patterns
with the same domain, identical boundaries, and identical images; and
of finite typeness of X is used to apply Corollary 2.27 to identically
extend these patterns to points of X.
Proof Sketch. Because the entropy of ∆(X) is less than the one of X,
the number of finite patterns in ∆(X) grows slower than in X. Hence,
there are two distinct finite patterns in X that have the same image
and these can be identically extended to two distinct points of X that
have the same image. Therefore, the map ∆ is not pre-injective.
Proof. According to Remark 2.29, Lemma 2.23 and Remark 2.22, and
Remark 2.42, there is a κ ∈ N0 such that X is κ-strongly irreducible,
X is κ-step, and ∆ is κ-local.

32

SIMON WACKER

Let Y = ∆(X). According to Remark 2.44 and [11, Lemma 11]
and the precondition entF (Y ) < entF (X), we have ent{Fi+2κ }i∈I (Y ) ≤
entF (Y ) < entF (X). Hence, there is an i ∈ I such that
log|YFi+2κ |
|Fi |

<

log|XFi |
.
|Fi |

Thus, log|YFi+2κ | < log|XFi | and thus |YFi+2κ | < |XFi |. Therefore,
because X is κ-strongly irreducible and ∆ is κ-local, according to
+ +κ =
Lemma 4.2, there are p and p0 in XFi+3κ such that p 6= p0 , p∂2κ
Fi
−
−
0
0
+ +κ , and ∆ +3κ (p) = ∆ +3κ (p ).
p ∂2κ
Fi
Fi
Fi
Hence, because X is κ-step, according to Corollary 2.27, there are
x and x0 in X such that xdom(p) = p, x0 dom(p0 ) = p0 , and xM rFi+κ =
x0 M rFi+κ . In particular, because p 6= p0 , we have x 6= x0 and, because
Fi+κ is finite, the set diff(x, x0 ) is finite.
Moreover, ∆(x)Fi+2κ = ∆−
(p) = ∆−
(p0 ) = ∆(x0 )Fi+2κ . And,
Fi+3κ
Fi+3κ
according to Remark 2.44 and [11, Lemma 2], we have ∆(x)M rFi+2κ =
∆(x0 )M rFi+2κ . Therefore, ∆(x) = ∆(x0 ). In conclusion, ∆ is not preinjective.

If in a point of a shift space we replace all occurrences of a pattern
by another pattern with the same image that agree on a big enough
boundary, we get a new point of the shift space in which the first
pattern does not occur that has the same image as the original point,
which is shown in
Lemma 4.4. Let X be a κ-step subshift of QM , let Y be a subshift
of QM , let ∆ be a κ-local map from X to Y , let A be a subset of M ,
0
+
+
let p and p0 be two patterns in XA+2κ such that p∂2κ
A = p ∂2κ
A and
−
−
0
∆A+2κ (p) = ∆A+2κ (p ). Furthermore, let c be a point of X and let T be
a subset of M such that the family {t P A+2κ }t∈T is pairwise disjoint
and that, for each element t ∈ T , we have p vt c. Put
a
c0 = cM r(St∈T tPA+2κ ) ×
t J p0 .
t∈T

Then, for each element t ∈ T , we have p0 vt c0 , and c0 ∈ X, and
∆(c) = ∆(c0 ). In particular, if p 6= p0 , then, for each element t ∈ T ,
we have p 6vt c0 .
Usage Note. In the proof, κ-stepness of X is used to apply Lemma 2.25
to deduce that c0 is a point of X; and locality of ∆ is used to deduce
that ∆(c) = ∆(c0 ).

THE MOORE AND THE MYHILL PROPERTY

33

Proof. There are x and x0 in X such that xA+2κ = p and x0 A+2κ = p0 .
Thus, for each t ∈ T , we have (t J x0 )tPA+2κ = t J p0 . Hence,
a
c0 = cM r(St∈T tPA+2κ ) × (t J x0 )tPA+2κ
t∈T

Moreover, for each t ∈ T , according to Remark 1.16, we have t J x0 ∈ X.
And, by precondition, {(t P A)+2κ }t∈T is pairwise disjoint (where we
used that t P A+2κ = (t P A)+2κ , which holds according to [11, Item 9
+ P
of Lemma 1]). And, for each t ∈ T , we have (t J x0 )∂2κ
(t A) = (t J
+
0
P
+ P
+ P
+ P
p )∂2κ
(t A) = (t J p)∂2κ
(t A) = c∂2κ
(t A) (where we used that ∂2κ (t A) =
+
t P ∂2κ A, which holds according to [11, Item 9 of Lemma 1]). Therefore,
because X is κ-step, according to Lemma 2.25, we have c0 ∈ X.
Let m ∈ M .
Case 1: ∃ t ∈ T : m ∈ t P A+κ . Then, according to [12, Item 2 of
Lemma 6.2] and [12, Item 3 of Lemma 6.4]
m P B(κ) ⊆ (t P A+κ ) P B(κ)
= (t P A+κ )+κ

= t P A+2κ .
Hence, because ∆ is κ-local,

J p0 )
∆(c0 )(m) = ∆−
tPA+2κ (t
0
= t J ∆−
A+2κ (p )

= t J ∆−
A+2κ (p)
J p)
= ∆−
tPA+2κ (t

= ∆(c)(m).
S
Case 2: ∀ t ∈ T : m ∈
/ t P A+κ . Then, m ∈ M r t∈T t P A+κ .
Hence, according to [12, Item 2 of Lemma 6.2], [11, Item 3 of
Lemma 1], and [12, Item 5 of Lemma 6.4],
[

m P B(κ) ⊆ M r
t P A+κ P B(κ)
t∈T

= Mr

[
t∈T

=Mr

[
t∈T

⊆Mr

[
t∈T

t P A+κ

+κ

t P A+κ

−κ

(t P A+κ )−κ

34

SIMON WACKER

⊆Mr

[
t∈T

=Mr

[
t∈T

t P A+0
t P A.

Therefore, because ∆ is κ-local and c0 M rSt∈T tPA = cM rSt∈T tPA ,
we have ∆(c0 )(m) = ∆(c)(m).
In either case, ∆(c0 )(m) = ∆(c)(m). Therefore, ∆(c0 ) = ∆(c).

Because a local map that is not pre-injective maps at least two finite
patterns to the same pattern, the entropy of its image is less than the
entropy of its domain, which is shown in
Theorem 4.5. Let M be infinite, let X be a strongly irreducible subshift
of QM of finite type, let Y be a subshift of QM , and let ∆ be a local map
from X to Y that is not pre-injective. Then, entF (∆(X)) < entF (X).
Usage Note. In the proof, infiniteness of M is used to apply Theorem 3.5 yielding a tiling, strong irreducibility of X is used to apply
Theorem 3.10 yielding a strict inequality for entropies, finite typeness
of X and locality of ∆ is used to apply Lemma 4.4 yielding that the
image of all points of X in which a certain pattern does not occur at
points of a tiling is the same as the image of X.
Proof Sketch. Because ∆ is not pre-injective, there are two distinct
points of X with the same image that differ only in finitely many cells.
Thus, there are two distinct finite patterns, say p and p0 , with the same
image. Hence, the image of X is equal to the image of the set Z of all
points of X in which the pattern p does not occur. Because there are
too many points not in Z, this set does have less entropy than X.
Proof. According to Remark 2.29, Lemma 2.23 and Remark 2.22, and
Remark 2.42, there is a κ ∈ N0 such that X is κ-strongly irreducible,
X is κ-step, and ∆ is κ-local.
Because ∆ is not pre-injective, there are c and c0 in X such that
diff(c, c0 ) is finite, ∆(c) = ∆(c0 ), and c 6= c0 ; in particular, |X| ≥ 2.
Hence, there is a ρ ∈ N0 such that diff(c, c0 ) ⊆ B(ρ). Let p = cB(ρ)+2κ
and let p0 = c0 B(ρ)+2κ . Then, p 6= p0 ; m0 ∈ B(ρ); p, p0 ∈ XB(ρ)+2κ ;
−
0
0
+
+
p∂2κ
B(ρ) = p ∂2κ
B(ρ) ; and, because ∆(c) = ∆(c ), we have ∆B(ρ)+2κ (p) =
0
∆−
B(ρ)+2κ (p ).
Because M is infinite, according to Theorem 3.5, there is a (ρ + 2κ,
κ, θ0 )-tiling T of R. Let
Z = {x ∈ X | ∀ t ∈ T : p 6vt x}.

THE MOORE AND THE MYHILL PROPERTY

35

For each t ∈ T , according to Remark 2.15, we have t J p ∈ XtPB(ρ)+2κ r
ZtPB(ρ)+2κ and hence ZtPB(ρ)+2κ $ XtPB(ρ)+2κ . Moreover, for each t ∈ T ,
according to [12, Item 2 of Corollary 6.3] and [12, Corollary 5.14],
we have t P B(ρ)+2κ = B(t, ρ + 2κ). Therefore, because X is κ-strongly
irreducible and |X| ≥ 2, according to Theorem 3.10, we have entF (Z) <
entF (X). Hence, according to [11, Theorem 3], we have entF (∆(Z)) <
entF (X).
Let x ∈ X. Put U = {t ∈ T | p vt x}. Because X is κ-step and
∆ is κ-local, according to Lemma 4.4, there is an x0 ∈ X such that
x0 ∈ Z and ∆(x) = ∆(x0 ). Therefore, ∆(X) = ∆(Z). In conclusion,
entF (∆(X)) < entF (X).

Because a right Følner net in a finite cell space is eventually equal
to the set of cells, the entropy of a subset of the full shift is a function
of the cardinality of that set, which is shown in
Lemma 4.6. Let R be right amenable, let F = {Fi }i∈I be a right
Følner net in R, let M be finite, and let X be a subset of QM . Then,

|X| = exp |M | · entF (X) .
Proof. Let F be a non-empty and finite subset of M such that F 6=
M . Then, because P is transitive, there is a g ∈ G/G0 such that
(F P g) ∩ (M r F ) 6= ∅. Hence, F P g * F , thus F * (_ P g)−1 (F ),
6 0.
thus F r (_ P g)−1 (F ) 6= ∅, and therefore |F r (_ P g)−1 (F )| =
−1
On the other hand, |M r (_ P g) (M )| = 0. Moreover, because M is
finite, the set {F ⊆ M | F 6= ∅, F finite} is finite and hence its subset
{Fi | i ∈ I} is finite too. Furthermore, because F is a right Følner net,
∀ g ∈ G/G0 : lim
i∈I

|Fi r (_ P g)−1 (Fi )|
= 0.
|Fi |

Altogether, F is eventually equal to M . Therefore,
entF (X) =

log|πM (X)|
log|X|
=
.
|M |
|M |

In conclusion, |X| = exp(|M | · entF (X)).



Because surjectivity as well as pre-injectivity of a local map is characterised by maximal entropy of its image with respect to its codomain
or domain, if both domains have the same entropy, then a local map is
surjective if and only if it is pre-injective, which is shown in
Main Theorem 4.7 (Garden of Eden theorem). Let R be right amenable, let F be a right Følner net in R, let X be a non-empty strongly
irreducible subshift of QM of finite type, let Y be a strongly irreducible

36

SIMON WACKER

subshift of QM such that entF (X) = entF (Y ), and let ∆ be a local map
from X to Y . The map ∆ is surjective if and only if it is pre-injective.
Usage Note. In the proof, non-emptiness of X, strong irreducibility of
Y , and locality of ∆ are used to apply Theorem 4.1 yielding a characterisation of surjectivity; and strong irreducibility and finite typeness
of X, and locality of ∆ are used to apply Theorems 4.3 and 4.5 yielding
a characterisation of pre-injectivity.
Proof. First, let M be finite. Then, QM is finite, and thus X and Y are
finite. Hence, because entF (X) = entF (Y ), according to Lemma 4.6,
we have |X| = |Y |. Therefore, ∆ is surjective if and only if it is
injective. Moreover, because M is finite, the map ∆ is pre-injective if
and only if it is injective. In conclusion, ∆ is surjective if and only if
it is pre-injective.
Secondly, let M be infinite. According to Theorem 4.1, the map ∆ is
not surjective if and only if entF (∆(X)) < entF (Y ). And, according to
Theorem 4.3 and Theorem 4.5, because entF (X) = entF (Y ), we have
entF (∆(X)) < entF (Y ) if and only if ∆ is not pre-injective. Hence, ∆
is not surjective if and only if it is not pre-injective. In conclusion, ∆
is surjective if and only if it is pre-injective.

Corollary 4.8. Let R be right amenable. Each strongly irreducible
subshift of QM of finite type has the Moore and the Myhill property. 
Corollary 4.9. Let M = (M, G, .) be a right amenable and finitely
right generated left homogeneous space with finite stabilisers and let
Q be a finite set. For each coordinate system K for M and each Kbig subgroup H of G, each strongly irreducible subshift of QM of finite
type with respect to R = (M, K) and H has the Moore and the Myhill
property with respect to R and H.

Remark 4.10. Note that in Corollary 4.9 we do not have to choose a
finite and symmetric right generating set S, because being a subshift,
being strongly irreducible, being of finite type, being local, being surjective, being pre-injective, having the Moore property, and having the
Myhill property, do not depend on the choice of a finite and symmetric
right generating set of R; the reason for the properties that depend on
the metric induced by such a right generating set is that those metrics
are, according to [12, Corollary 8.7], pairwise Lipschitz equivalent.
Example 4.11 (From Golden Mean to Even Shift). In the situation
of Example 2.46, let F be the right Følner net ({1, . . . , n})n∈N+ . Recall
that the golden mean shift X is non-empty (Example 2.10), strongly
irreducible (Example 2.31), and of finite type (Example 2.20); and

THE MOORE AND THE MYHILL PROPERTY

37

that the even shift Y is strongly irreducible (Example 2.31) but not of
finite type (Example 2.20). And, according to [5, Example 4.1.4] and
[5, Example 4.1.6], the entropy of X √
with respect to F and the one
of Y are both the golden mean (1 + 5)/2. Therefore, according to
Main Theorem 4.7, because the local map ∆ from X to Y is surjective
(Example 2.46), it is also pre-injective. However, it is not injective,
because the two points of X with alternating 0’s and 1’s, that is, those
of the form . . . 010101 . . . , are both mapped to the point of Y with only
0’s, that is, the one of the form . . . 000 . . . .
References
[1] Ceccherini-Silberstein, Tullio, Machi, Antonio, and Scarabotti, Fabio. Amenable
groups and cellular automata. In: Annales de l’institut Fourier 49.2 (1999),
pages 673-685.
[2] Ceccherini-Silberstein, Tullio and Coornaert, Michel. Cellular Automata and
Groups. In: Springer Monographs in Mathematics. Springer-Verlag, 2010.
[3] Ceccherini-Silberstein, Tullio and Coornaert, Michel. On the density of periodic
configurations in strongly irreducible subshifts. In: Nonlinearity 25.7 (2012),
pages 2119-2131.
[4] Fiorenzi, Francesca. Cellular automata and strongly irreducible shifts of finite
type. In: Journal of Theoretical Computer Science 299.1 (2003), pages 477-493.
[5] Lind, Douglas and Marcus, Brian. An Introduction to Symbolic Dynamics and
Coding. Cambridge University Press, 1995.
[6] Moore, Edward Forrest. Machine models of self-reproduction. In: Proceedings
of Symposia in Applied Mathematics 14 (1962), pages 17–33.
[7] Moriceau, Sébastien. Cellular Automata on a G-Set. In: Journal of Cellular
Automata 6.6 (2011), pages 461-486.
[8] Myhill, John R. The converse of Moore’s Garden-of-Eden theorem. In: Proceedings of the American Mathematical Society 14 (1963), pages 685–686.
[9] Wacker, Simon. Cellular Automata on Group Sets and the Uniform CurtisHedlund-Lyndon Theorem. Cellular Automata and Discrete Complex Systems
(2016), pages 185-198. arXiv:1603.07271 [].
[10] Wacker, Simon. Right Amenable Left Group Sets and the Tarski-Følner Theorem. Preprint (2016). arXiv:1603.06460 [].
[11] Wacker, Simon. The Garden of Eden Theorem for Cellular Automata on Group
Sets. Cellular Automata (2016), pages 66-78. arXiv:1603.07272 [].
[12] Wacker, Simon. Right Amenability And Growth Of Finitely Right Generated
Left Group Sets. Preprint (2017). arXiv:1701.02108 [].
Simon Wacker, Department of Informatics, Karlsruhe Institute of
Technology, Am Fasanengarten 5, 76131 Karlsruhe, Germany
E-mail address: simon.wacker@kit.edu

