THE GARDEN OF EDEN THEOREM: OLD AND NEW
TULLIO CECCHERINI-SILBERSTEIN AND MICHEL COORNAERT

arXiv:1707.08898v2 [math.DS] 29 Sep 2017

Abstract. We review topics in the theory of cellular automata and dynamical systems
that are related to the Moore-Myhill Garden of Eden theorem.

Contents
1. Introduction
2. Configuration spaces and shifts
2.1. Notation
2.2. Configurations spaces
2.3. Group actions
2.4. Shifts
2.5. Patterns
2.6. Subshifts
3. Cellular automata
3.1. Definition
3.2. The Curtis-Hedlund-Lyndon theorem
3.3. Operations on cellular automata
3.4. Surjectivity of cellular automata, GOE configurations, and GOE patterns
3.5. Pre-injectivity of cellular automata and mutually erasable patterns
4. The Garden of Eden theorem for Zd
5. The Garden of Eden theorem for general amenable groups
5.1. Amenability
5.2. Entropy
5.3. Tilings
5.4. The Garden of Eden theorem for amenable groups
6. Failure of the Garden of Eden theorem for nonamenable groups
7. The Garden of Eden theorem for subshifts
7.1. Strongly irreducible subshifts
7.2. The Moore and the Myhill properties for subshifts
8. Garden of Eden theorems for other dynamical systems
8.1. Dynamical systems

2
3
3
4
4
5
5
6
7
7
9
10
10
11
12
15
15
19
22
24
26
27
27
28
30
30

Date: October 2, 2017.
2010 Mathematics Subject Classification. 37B15, 37B10, 37B40, 37C29, 37D20, 43A07, 68Q80.
Key words and phrases. Garden of Eden theorem, cellular automaton, mutually erasable patterns,
dynamical system, homoclinicity, pre-injectivity, surjunctivity, amenability, soficity.
1

2

TULLIO CECCHERINI-SILBERSTEIN AND MICHEL COORNAERT

8.2. Expansiveness
8.3. Homoclinicity
8.4. The Moore and the Myhill properties for dynamical systems
8.5. Anosov diffeomorphisms
8.6. Principal algebraic dynamical systems
9. Some Additional topics
9.1. Infinite alphabets and uncountable groups
9.2. Linear cellular automata
9.3. Gromov’s Garden of Eden theorem
9.4. Cellular automata over homogeneous sets
References
Added in proof
Additional references

31
32
32
33
34
36
36
37
39
40
40
42
43

1. Introduction
In the beginning, the Garden of Eden theorem, also known as the Moore-Myhill theorem, is a result in the theory of cellular automata which states that a cellular automaton
is surjective if and only if it satisfies a weak form of injectivity, called pre-injectivity.
The theorem was obtained by Moore and Myhill in the early 1960s for cellular automata
with finite alphabet over the groups Zd . The fact that surjectivity implies pre-injectivity
for such cellular automata was first proved by Moore in [39], and Myhill [43] established
the converse implication shortly after. The proofs of Moore and Myhill appeared in two
separate papers both published in 1963. The biblical terminology used to designate the
Moore-Myhill theorem comes from the fact that configurations that are not in the image
of a cellular automaton are called Garden of Eden configurations because, when considering the sequence of consecutive iterates of the cellular automaton applied to the set
of configurations, they can only occur at time 0. Surjectivity of a cellular automaton is
equivalent to absence of Garden of Eden configurations. In 1988 [49, Question 1], Schupp
asked whether the class of groups for which the Garden of Eden theorem remains valid is
precisely the class of virtually nilpotent groups. By a celebrated result of Gromov [29],
a finitely generated group is virtually nilpotent if and only if it has polynomial growth.
In 1993, Machı̀ and Mignosi [36] proved that the Garden of Eden theorem is still valid over
any finitely generated group with subexponential growth. As Grigorchuk [28], answering a
longstanding open question raised by Milnor [38], gave examples of groups whose growth
lies strictly between polynomial and exponential, it follows that the class of finitely generated groups satisfying the Garden of Eden theorem is larger than the class of finitely
generated virtually nilpotent groups. Actually, it is even larger than the class of finitely
generated groups with subexponential growth. Indeed, Machı̀, Scarabotti, and the first
author [20] proved in 1999 that every amenable group satisfies the Garden of Eden theorem and it is a well known fact that there are finitely generated amenable groups, such
as the solvable Baumslag-Solitar group BS(1, 2) = ha, b : aba−1 = b2 i, that are amenable

THE GARDEN OF EDEN THEOREM: OLD AND NEW

3

and have exponential growth. It was finally shown that the class of groups that satisfy the
Garden of Eden theorem is precisely the class of amenable groups. This is a consequence
of recent results of Bartholdi [2], Bartholdi and Kielak [3], who showed that none of the
implications of the Garden of Eden theorem holds when the group is nonamenable.
In [30, Section 8], Gromov made an important contribution to the subject by providing
a deep analysis of the role played by entropy in the proof of the Garden of Eden theorem
and indicating new directions for extending it in many other interesting settings. He
mentioned in particular [30, p 195] the possibility of proving an analogue of the Garden of
Eden theorem for a suitable class of hyperbolic dynamical systems. Some results in that
direction were subsequently obtained by the authors in [17], [16], and [18]. In particular, a
version of the Garden of Eden theorem was established for Anosov diffeomorphisms on tori
in [17] and for principal expansive algebraic actions of countable abelian groups in [18].
The present article is intended as a reasonably self-contained survey on the classical
Garden of Eden theorem and some of its generalizations. Almost all results presented
here have already appeared in the literature elsewhere but we sometimes give complete
proofs when we feel they might be helpful to the reader. The general theory of cellular
automata over groups is developed in our monograph [12]. The present survey is a kind
of complement to our book since for instance cellular automata between subshifts are not
considered in [12] while they are treated here.
The paper is organized as follows. Configuration spaces and shifts are presented in
Section 2. Cellular automata are introduced in Section 3. Section 4 contains the proof of
the Garden of Eden theorem in the case G = Zd following Moore and Myhill. The proof
of the Garden of Eden theorem in the case of an arbitrary countable amenable group is
given in Section 5. Examples of cellular automata that do not satisfy the Garden of Eden
theorem for groups containing nonabelian free subgroups are described in Section 6. We
also discuss the results of Bartholdi and Kielak mentioned above, which, together with
the Garden of Eden theorem, lead to characterizations of amenability in terms of cellular
automata. Extensions of the Garden of Eden theorem to certain classes of subshifts are
reviewed in Section 7. In Section 8, we present versions of the Garden of Eden theorem we
obtained for certain classes of dynamical systems. The final section briefly discusses some
additional topics and provides references for further readings.
2. Configuration spaces and shifts
2.1. Notation. We use the symbol Z to denote the set of integers {. . . , −2, −1, 0, 1, 2, . . . }.
The symbol N denotes the set of nonnegative integers {0, 1, 2, . . . }. The cardinality of a
finite set X is written |X|.
We use multiplicative notation for groups except for abelian groups such as
Zd = Z × Z × · · · × Z
|
{z
}
d times

for which we generally prefer additive notation.

4

TULLIO CECCHERINI-SILBERSTEIN AND MICHEL COORNAERT

Let G be a group. We denote the identity element of G by 1G . If A, B are subsets of G
and g ∈ G, we write AB := {ab : a ∈ A, b ∈ B}, A−1 := {a−1 : a ∈ A}, gA := {g}A and
Ag := A{g}. A subset A ⊂ G is said to be symmetric if it satisfies A = A−1 .”
2.2. Configurations spaces. Let U be a countable set, called the universe, and A a
finite set, called the alphabet. Depending on the context, the elements of A are called
letters, or symbols, or states, or colors. As usual, we denote by AU the set consisting of all
maps x : U → A. An element of AU is called a configuration of the universe U. Thus, a
configuration is a way of attaching a letter of the alphabet to each element of the universe.
If x ∈ AU is a configuration and V ⊂ U, we shall write x|V for the restriction of x to
V, i.e., the element x|V ∈ AV defined by x|V (v) = x(v) for all v ∈ V. If X ⊂ AU , we shall
write
(2.1)

XV := {x|V : x ∈ X} ⊂ AV .

Two configurations x, y ∈ AU are said to be almost equal if they coincide outside of a
finite set, i.e., there is a finite subset Ω ⊂ U such that x|U \Ω = y|U \Ω . Being almost equal
clearly defines an equivalence relation on AU .
We equip the configuration set AU with its prodiscrete topology, that is, the
Q product
topology obtained by taking the discrete topology on each factor A of AU = u∈U A. A
neighborhood base of a configuration x ∈ AU is given by the sets
(2.2)

V (x, Ω) = V (x, Ω, U, A) := {y ∈ AU : x|Ω = y|Ω },

where Ω runs over all finite subsets of U. In this topology, two configurations are “close”
if they coincide on a “large” finite subset of the universe.
Every finite discrete topological space is compact, totally disconnected, and metrizable.
As a product of compact (resp. totally disconnected) topological spaces is itself compact
(resp. totally disconnected) and a countable product of metrizable spaces is itself metrizable, it follows that AU is a compact totally disconnected metrizable space. Note that AU
is homeomorphic to the Cantor set as soon as A contains more than one element and U is
infinite.
2.3. Group actions. An action of a group G on a set X is a map α : G × X → X
satisfying α(g1, α(g2 , x)) = α(g1 g2 , x) and α(1G , x) = x for all g1 , g2 ∈ G and x ∈ X. In
the sequel, if α is an action of a group G on a set X, we shall simply write gx instead of
α(g, x), if there is no risk of confusion.
Suppose that a group G acts on a set X. The orbit of a point x ∈ X is the subset
Gx ⊂ X defined by Gx := {gx : g ∈ G}. A point x ∈ X is called periodic if its orbit is
finite. A subset Y ⊂ X is called invariant if Gy ⊂ Y for all y ∈ Y . One says that Y ⊂ X
is fixed by G if gy = y for all g ∈ G and y ∈ Y .
Suppose now that a group G acts on two sets X and Y . A map f : X → Y is called
equivariant if f (gx) = gf (x) for all g ∈ G and x ∈ X.
Let X be a topological space. An action of a group G on X is called continuous if the
map x 7→ gx is continuous on X for each g ∈ G. Note that if G acts continuously on X
then, for each g ∈ G, the map x 7→ gx is a homeomorphism of X with inverse x 7→ g −1 x.

THE GARDEN OF EDEN THEOREM: OLD AND NEW

5

2.4. Shifts. From now on, our universe will be a countable group. So let G be a countable
group and A a finite set. Given an element g ∈ G and a configuration x ∈ AG , we define
the configuration gx ∈ AG by
gx := x ◦ Lg−1 ,
where Lg : G → G is the left-multiplication by g. Thus

gx(h) = x(g −1 h) for all h ∈ G.

Observe that, for all g1 , g2 ∈ G and x ∈ AG ,

g1 (g2 x) = x ◦ Lg2−1 ◦ Lg1−1 = x ◦ Lg2−1 g1−1 = x ◦ L(g1 g2 )−1 = (g1 g2 )x,
and
Therefore the map

1G x = x ◦ L1G = x ◦ IdG = x.
G × AG → AG
(g, x) 7→ gx

defines an action of G on AG . This action is called the G-shift, or simply the shift, on AG .
Observe that if two configurations x, y ∈ AG coincide on a subset Ω ⊂ G, then, for every
g ∈ G, the configurations gx and gy coincide on gΩ. As the sets V (x, Ω) defined by (2.2)
form a base of neighborhoods of x ∈ AG when Ω runs over all finite subsets of G, we deduce
that the map x 7→ gx is continuous on AG for each g ∈ G. Thus, the shift action of G on
AG is continuous.
2.5. Patterns. A pattern is a map p : Ω → A, where Ω is a finite subset of G. If p : Ω → A
is a pattern, we say that Ω is the support of p and write Ω = supp(p).
Let P(G, A) denote the set of all patterns. There is a natural action of the group G
on P(G, A) defined as follows. Given g ∈ G and a pattern p ∈ P(G, A) with support
Ω, we define the pattern gp ∈ P(G, A) as being the pattern with support gΩ such that
gp(h) = p(g −1h) for all h ∈ gΩ. It is easy to check that this defines an action of G on
P(G, A), i.e., g1 (g2 p) = (g1 g2 )p and 1G p = p for all g1 , g2 ∈ G and p ∈ P(G, A). Observe
that supp(gp) = g supp(p) for all g ∈ G and p ∈ P(G, A). Note also that if p is the
restriction of a configuration x ∈ AG to a finite subset Ω ⊂ G, then gp is the restriction of
the configuration gx to gΩ.
Example 2.1. Take G = Z and let A be a finite set. Denote by A⋆ the set of words on the
alphabet A. We recall that A⋆ is the free monoid based on A and that any element w ∈ A⋆
can be uniquely written in the form w = a1 a2 · · · an , where ai ∈ A for 1 ≤ i ≤ n and n ∈ N
is the length of the word w. The monoid operation on A⋆ is the concatenation of words
and the identity element is the empty word, that is, the unique word with length 0. Now
let us fix some finite interval Ω ⊂ Z of cardinality n, say Ω = {m, m + 1, . . . , m + n − 1}
with m ∈ Z and n ∈ N. Then one can associate to each pattern p : Ω → A the word
w = p(m)p(m + 1) · · · p(m + n − 1) ∈ A⋆ .

6

TULLIO CECCHERINI-SILBERSTEIN AND MICHEL COORNAERT

This yields a one-to-one correspondence between the patterns supported by Ω and the
words of length n on the alphabet A. This is frequently used to identify each pattern
supported by Ω with the corresponding word.
2.6. Subshifts. A subshift is a subset X ⊂ AG that is invariant under the G-shift and
closed for the prodiscrete topology on AG .
Example 2.2. Take G = Z and A = {0, 1}. Then the subset X ⊂ AG , consisting of all
x : Z → {0, 1} such that (x(n), x(n + 1)) 6= (1, 1) for all n ∈ Z, is a subshift. This subshift
is called the golden mean subshift.
Example 2.3. Take G = Zd and A = {0, 1}. Then the subset X ⊂ AG , consisting of all
x ∈ AG such that (x(g), x(g + ei )) 6= (1, 1) for all g ∈ G, where (ei )1≤i≤d is the canonical
basis of Zd , is a subshift. This subshift is called the hard-ball model. For d = 1, the
hard-ball model is the golden mean subshift of the previous example.
Example 2.4. Take G = Z and A = {0, 1}. Then the subset X ⊂ AG , consisting of all
bi-infinite sequences x : Z → {0, 1} such that there is always an even number of 0s between
two 1s, is a subshift. This subshift is called the even subshift.
Example 2.5. Take G = Z2 and A = {0, 1} = Z/2Z (the integers modulo 2). Then the
subset X ⊂ AG , consisting of all x : Z2 → {0, 1} such that
x(m, n) + x(m + 1, n) + x(m, n + 1) = 0
for all (m, n) ∈ Z2 , is a subshift. This subshift is called the Ledrappier subshift.
Remark 2.6. Every intersection of subshifts and every finite union of subshifts X ⊂ AG
is itself a subshift. Therefore the subshifts X ⊂ AG are the closed subsets of a topology on
AG . This topology is coarser (it has less open sets) than the prodiscrete topology on AG .
It is not Hausdorff as soon as G is not trivial and A has more than one element.
Given a (possibly infinite) subset of patterns P ⊂ P(G, A), it is easy to see that the
subset X(P ) ⊂ AG defined by
X(P ) := {x ∈ AG such that (gx)|supp(p) 6= p for all g ∈ G and p ∈ P }
is a subshift.
Conversely, let X ⊂ AG be a subshift. One says that a pattern p ∈ P(G, A) appears in
X if p ∈ Xsupp(p) , i.e., if there is a configuration x ∈ X such that x|supp(p) = p. Then one
easily checks that X = X(P ) for
P := {p ∈ P(G, A) such that p does not appear in X}.
One says that a subshift X ⊂ AG is of finite type if there exists a finite subset P ⊂
P(G, A) such that X = X(P ). The hard-ball models (and hence in particular the golden
mean subshift) and the Ledrappier subshifts are examples of subshifts of finite type. On
the other hand, the even subshift is not of finite type.

THE GARDEN OF EDEN THEOREM: OLD AND NEW

7

3. Cellular automata
3.1. Definition. Let G be a countable group and let A, B be finite sets. Suppose that
X ⊂ AG and Y ⊂ B G are two subshifts.
Definition 3.1. One says that a map τ : X → Y is a cellular automaton if there exist a
finite subset S ⊂ G and a map µ : AS → B such that

(3.1)

τ (x)(g) = µ((g −1x)|S )

for all x ∈ X and g ∈ G, where we recall that (g −1 x)|S denotes the restriction of the
configuration g −1 x ∈ X to S. Such a set S is called a memory set and µ is called a local
defining map for τ .
It immediately follows from this definition that a map τ : X → Y is a cellular automaton
if and only if τ extends to a cellular automaton τe : AG → B G . Observe also that if S is
a memory set for a cellular automaton τ : X → Y and g ∈ G, then Formula (3.1) implies
that the value taken by the configuration τ (x) at g only depends on the restriction of x
to gS. Finally note that if S is a memory set for a cellular automaton τ , then any finite
subset of G containing S is also a memory set for τ . Consequently, the memory set of a
cellular automaton is not unique in general. However, every cellular automaton admits a
unique memory set with minimal cardinality (this follows from the fact that if S1 and S2
are memory sets then so is S1 ∩ S2 ).
Example 3.2. Take G = Z and A = {0, 1} = Z/2Z. Then the map τ : AG → AG , defined
by
τ (x)(n) := x(n + 1) + x(n)
G
for all x ∈ A and n ∈ Z, is a cellular automaton admitting S := {0, 1} ⊂ Z as a memory
set and µ : AS → A given by
µ(p) := p(0) + p(1)
S
for all p ∈ A , as a local defining map. Using the representation of patterns with support
S by words of length 2 on the alphabet A (cf. Example 2.1), the map µ is given by
µ(00) = µ(11) = 0 and µ(01) = µ(10) = 1.
Example 3.3 (Majority vote). Take G = Z and A = {0, 1}. Then the map τ : AG → AG ,
defined by
(
0 if x(n − 1) + x(n) + x(n + 1) ≤ 1
τ (x)(n) :=
1 otherwise
for all x ∈ AG and n ∈ Z, is a cellular automaton admitting S := {−1, 0, 1} ⊂ Z as a
memory set and µ : AS → A given by
µ(000) = µ(001) = µ(010) = µ(100) = 0

and
µ(011) = µ(101) = µ(110) = µ(111) = 1
as local defining map. The cellular automaton τ is called the majority vote cellular automaton.

8

TULLIO CECCHERINI-SILBERSTEIN AND MICHEL COORNAERT

Remark 3.4. A cellular automaton τ : AG → AG , where G = Z, A = {0, 1}, admitting
S = {−1, 0, 1} as a memory set is called an elementary cellular automaton. Each one of
these cellular automata is uniquely determined by its local defining map µ : AS → A, so
that there are exactly 28 = 256 elementary cellular automata. They are numbered from
0 to 255 according to a notation that was introduced by Wolfram (cf. [56]). To obtain
the number n of an elementary cellular automaton τ , one proceeds as follows. One first
lists all eight patterns p ∈ AS in increasing order from 000 to 111. The number n is the
integer whose expansion in base 2 is a8 a7 . . . a1 , where ak is the value taken by the local
defining map of τ at the k-th pattern in the list. One also says that τ is Rule n. For
instance, the elementary cellular automaton described in Example 3.2 is Rule 102 while
the one described in Example 3.3 is Rule 232.
Example 3.5. Let G be a countable group, A a finite set, and X ⊂ AG a subshift. Then
the identity map IdX : X → X is a cellular automaton with memory set S = {1G } and
local defining map µ = IdA : AS = A{1G } = A → A.
Example 3.6. Let G be a countable group, A a finite set, and X ⊂ AG a subshift. Let
s ∈ G and denote by Rs the right-multiplication by s, that is, the map Rs : G → G defined
by Rs (h) := hs for all s ∈ G. Then the subset Y ⊂ AG defined by
Y := {x ◦ Rs such that x ∈ X}
is a subshift. Moreover, the map τ : X → Y , defined by τ (x) := x ◦ Rs for all x ∈ X, is a
cellular automaton with memory set S = {s} and local defining map µ = IdA : AS = A →
A. Observe that if s is in the center of G, then X = Y and τ : X → X is the shift map
x 7→ s−1 x.
Example 3.7. Take G = Z and A = {0, 1}. Let X ⊂ AG and Y ⊂ AG denote respectively
the golden mean subshift and the even subshift. For x ∈ X, define τ (x) ∈ AG by
(
0 if (x(n), x(n + 1)) = (0, 1) or (1, 0)
τ (x)(n) :=
1 if (x(n), x(n + 1)) = (0, 0)
for all n ∈ Z. It is easy to see that τ (x) ∈ Y for all x ∈ X. The map τ : X → Y is a
cellular automaton admitting S := {0, 1} ⊂ Z as a memory set and the map µ : AS → A,
defined by
µ(00) = µ(11) = 1 and µ(01) = µ(10) = 0.
Note that the map µ′ : AS → A, defined by
µ′ (00) = 1 and µ′ (01) = µ′ (10) = µ′ (11) = 0
is also a local defining map for τ . Thus, τ is the restriction to X of both Rule 153 and
Rule 17.

THE GARDEN OF EDEN THEOREM: OLD AND NEW

9

3.2. The Curtis-Hedlund-Lyndon theorem. The definition of a cellular automaton
given in the previous subsection is a local one. For τ to be a cellular automaton, it requires
the existence of a rule, commuting with the shift, that allows one to evaluate the value
taken by τ (x) at g ∈ G by applying the rule to the restriction of x to a certain finite set,
namely the left-translate by g of a memory set of the automaton. The following result,
known as the Curtis-Lyndon-Hedlund theorem (see [31]), yields a global characterization
of cellular automata involving only the shift actions and the prodiscrete topology on the
configuration spaces.
Theorem 3.8. Let G be a countable group and let A, B be finite sets. Let τ : X → Y be a
map from a subshift X ⊂ AG into a subshift Y ⊂ B G . Then the following conditions are
equivalent:
(a) τ is a cellular automaton;
(b) τ is equivariant (with respect to the shift actions of G) and continuous (with respect to
the prodiscrete topologies).
Proof. Suppose first that τ : X → X is a cellular automaton. Let S ⊂ G be a memory set
and µ : AS → B a local defining map for τ . For all g, h ∈ G and x ∈ X, we have that
τ (gx)(h) = µ((h−1 gx)|S )
−1

(by Formula (3.1))

−1

= µ(((g h) x)|S )
= τ (x)(g −1 h)
= gτ (x)(h).
Thus τ (gx) = gτ (x) for all g ∈ G and x ∈ X. This shows that τ is equivariant.
Now let Ω be a finite subset of G. Recall that Formula (3.1) implies that if two configurations x, y ∈ X coincide on gS for some g ∈ G, then τ (x)(g) = τ (y)(g). Therefore, if the
configurations x and y coincide on the finite set ΩS, then τ (x) and τ (y) coincide on Ω. It
follows that
τ (X ∩ V (x, ΩS, G, A)) ⊂ V (τ (x), Ω, G, B).
This implies that τ is continuous. Thus (a) implies (b).
Conversely, suppose now that the map τ : X → Y is equivariant and continuous. Let us
show that τ is a cellular automaton. As the map ϕ : X → B defined by ϕ(x) := τ (x)(1G )
is continuous, we can find, for each x ∈ X, a finite subset Ωx ⊂ G such that if y ∈ X ∩
V (x, Ωx , G, A), then τ (y)(1G ) = τ (x)(1G ). The sets X ∩ V (x, Ωx , G, A) form an open cover
of X. As X is compact, there is a finite subset F ⊂ X such that the sets V (x, Ωx , G, A),
x ∈ F , cover X. Let us set S = ∪x∈F Ωx and suppose that two configurations y, z ∈ X
coincide on S. Let x0 ∈ F be such that y ∈ V (x0 , Ωx0 , G, A), that is, y|Ωx0 = x0 |Ωx0 . As
Ωx0 ⊂ S, we have that y|Ωx0 = z|Ωx0 and therefore τ (y)(1G ) = τ (x0 )(1G ) = τ (z)(1G ). We
deduce that there exists a map µ : AS → B such that τ (x)(1G ) = µ(x|S ) for all x ∈ X.

10

TULLIO CECCHERINI-SILBERSTEIN AND MICHEL COORNAERT

Now, for all x ∈ X and g ∈ G, we have that
τ (x)(g) = (g −1 τ (x))(1G )
= τ (g −1 x)(1G )

(by definition of the shift action on B G )

(since τ is equivariant)

−1

= µ((g x)|S ).
This shows that τ is a cellular automaton with memory set S and local defining map µ.
Thus (b) implies (a).

3.3. Operations on cellular automata.
Proposition 3.9. Let G be a countable group and les A, B, C be finite sets. Suppose that
X ⊂ AG , Y ⊂ B G , Z ⊂ C G are subshifts and that τ : X → Y , σ : Y → Z are cellular
automata. Then the composite map σ ◦ τ : X → Z is a cellular automaton.
Proof. This is an immediate consequence of the characterization of cellular automata given
by the Curtis-Hedlund-Lyndon theorem (cf. Theorem 3.8) since the composite of two equivariant (resp. continuous) maps is itself equivariant (resp. continuous).

Remark 3.10. If we fix the countable group G, we deduce from Proposition 3.9 and
Example 3.5 that the subshifts X ⊂ AG , with A finite, are the objects of a concrete
category CG in which the set of morphisms from X ∈ CG to Y ∈ CG consist of all cellular
automata τ : X → Y (cf. [15, Section 3.2]). In this category, the endomorphisms of X ∈ CG
consist of all cellular automata τ : X → X and they form a monoid for the composition of
maps.
Proposition 3.11. Let G be a countable group and let A, B be finite sets. Suppose that
X ⊂ AG , Y ⊂ B G are subshifts and that τ : X → Y is a bijective cellular automaton. Then
the inverse map τ −1 : Y → X is a cellular automaton.
Proof. This is again an immediate consequence of the Curtis-Hedlund-Lyndon theorem
since the inverse of a bijective equivariant map is an equivariant map and the inverse of a
bijective continuous map between compact Hausdorff spaces is continuous.

3.4. Surjectivity of cellular automata, GOE configurations, and GOE patterns.
In what follows, we keep the notation introduced for defining cellular automata. Let
τ : X → Y be a cellular automaton. A configuration y ∈ Y is called a Garden of Eden
configuration for τ , briefly a GOE configuration, if it does not belong to the image of τ , i.e.,
there is no x ∈ X such that y = τ (x). One says that a pattern p ∈ P(G, B) is a Garden
of Eden pattern for τ , briefly a GOE pattern, if the pattern p appears in the subshift Y
but not in the subshift τ (X), i.e., there exists y ∈ Y such that p = y|supp(p) but there is no
x ∈ X such that p = τ (x)|supp(p) . Note that the set of GOE configurations (resp. of GOE
patterns) is an invariant subset of Y (resp. of P(G, B)). Observe also that if p ∈ P(G, A)
is a GOE pattern for the cellular automaton τ : X → Y , then every configuration y ∈ Y
such that y|supp(p) = p is a GOE configuration for τ .

THE GARDEN OF EDEN THEOREM: OLD AND NEW

11

Example 3.12. It is easy to check that the pattern with support Ω := {0, 1, 2, 3, 4}
associated with the word 01001 is a GOE pattern for the majority vote cellular automaton
described in Example 3.3.
Proposition 3.13. Let τ : X → Y be a cellular automaton. Then the following conditions
are equivalent:
(a) τ is surjective;
(b) τ admits no GOE configurations;
(c) τ admits no GOE patterns.
Proof. The equivalence of (a) and (b) as well as the implication (b) =⇒ (c) are trivial.
The implication (c) =⇒ (b) easily follows from the compactness of τ (X).

3.5. Pre-injectivity of cellular automata and mutually erasable patterns. Let
G be a countable group and let A and B be finite sets. Recall that two configurations
x, y ∈ AG are called almost equal if they coincide outside of a finite subset of G.
Definition 3.14. Let X ⊂ AG and Y ⊂ B G be subshifts. One says that a cellular
automaton τ : X → Y is pre-injective if there are no distinct configurations x1 , x2 ∈ X
that are almost equal and satisfy τ (x1 ) = τ (x2 ).
A pair of configurations (x1 , x2 ) ∈ X × X is called a diamond if x1 and x2 are distinct,
almost equal, and have the same image under τ (cf. [32, Definition 8.1.15]). Thus, preinjectivity is equivalent to the absence of diamonds. If (x1 , x2 ) is a diamond, the nonempty
finite subset
{g ∈ G : x1 (g) 6= x2 (g)} ⊂ G
is called the support of the diamond (x1 , x2 ).
Every injective cellular automaton is clearly pre-injective. The converse is false, as shown
by the following examples.

Example 3.15. Take G = Z, A = {0, 1} = Z/2Z, and consider the cellular automaton
τ : AG → AG described in Example 3.2 (Rule 102 in Wolfram’s notation). Then τ is preinjective. Indeed, it is clear that if two configurations x, x′ ∈ AG coincide on Z ∩ (−∞, n0 ]
for some n0 ∈ Z and satisfy τ (x) = τ (x′ ) then x = x′ . However, τ is not injective since the
two constant configurations have the same image.
Example 3.16. Consider the cellular automaton τ : X → Y from the golden mean subshift
to the even subshift described in Example 3.7. It is easy to see that τ is pre-injective by
an argument similar to the one used in the previous example. However, τ is not injective
since the two sequences in X with exact period 2 have the same image under τ , namely
the constant sequence with only 0s.
Let Ω ⊂ G be a finite set and p1 , p2 ∈ XΩ two patterns with support Ω appearing in X.
One says that the patterns p1 and p2 are mutually erasable with respect to τ , briefly ME,
provided the following hold:

12

TULLIO CECCHERINI-SILBERSTEIN AND MICHEL COORNAERT

(MEP-1) the set
Xp1 ,p2 := {(x1 , x2 ) ∈ X × X : x1 |Ω = p1 , x2 |Ω = p2 and x1 |G\Ω = x2 |G\Ω }

is nonempty;
(MEP-2) for all (x1 , x2 ) ∈ Xp1 ,p2 one has τ (x1 ) = τ (x2 ).
Note that “being ME” is an equivalence relation on XΩ . This equivalence relation is not
trivial in general.
Example 3.17. The patterns with support Ω := {0, 1, 2} associated with the words 00000
and 00100 are ME patterns for the majority vote cellular automaton described in Example 3.3.
Observe that if the patterns p1 and p2 are ME, then so are gp1 and gp2 for all g ∈ G.

Proposition 3.18. Let τ : X → Y be a cellular automaton. Then the following conditions
are equivalent:
(a) τ is pre-injective;
(b) τ admits no distinct ME patterns.
Proof. Suppose first that τ admits two distinct ME patterns p1 and p2 . Let Ω denote their
common support. Take (x1 , x2 ) ∈ Xp1 ,p2 . Then the configurations x1 and x2 are almost
equal since they coincide outside of Ω. Moreover, they satisfy x1 6= x2 and τ (x1 ) = τ (x2 ).
Therefore (x1 , x2 ) is a diamond for τ . It follows that τ is not pre-injective.
Suppose now that τ is not pre-injective and let us show that τ admits two distinct ME
patterns. By definition, τ admits a diamond (x1 , x2 ) ∈ X × X. Let ∆ denote the support
of this diamond and let S ⊂ G be a memory set for τ with 1G ∈ S. Consider the set
Ω := ∆S −1 S. We claim that the patterns p1 := x1 |Ω and p2 := x2 |Ω are distinct ME
patterns. First observe that p1 6= p2 since ∅ 6= ∆ ⊂ Ω. Moreover, Xp1 ,p2 is nonempty
since, by construction, (x1 , x2 ) ∈ Xp1 ,p2 . To complete the proof, we only need to show
the following: if (y1 , y2) ∈ Xp1 ,p2 then τ (y1 ) = τ (y2 ). Let g ∈ G. Suppose first that
g ∈ G \ ∆S −1 . Then gS ∩ ∆ = ∅. Since y1 and y2 coincide on G \ ∆, we deduce that
(3.2)

τ (y1 )(g) = τ (y2 )(g) for all g ∈ G \ ∆S −1 .

Suppose now that g ∈ ∆S −1 . Then gS ⊂ ∆S −1 S = Ω. As y1 |Ω = p1 = x1 |Ω (resp.
y2 |Ω = p2 = x2 |Ω ), by construction, we deduce that
(3.3)

τ (y1 )(g) = τ (x1 )(g) = τ (x2 )(g) = τ (y2 )(g) for all g ∈ ∆S −1 .

From (3.2) and (3.3) we deduce that τ (y1 ) = τ (y2 ).



4. The Garden of Eden theorem for Zd
In this section, we present a proof of the Garden of Eden theorem of Moore and Myhill
for cellular automata over the group Zd . This is a particular case of the Garden of Eden
theorem for amenable groups that will be established in the next section.
d

d

Theorem 4.1. Let A be a finite set, d ≥ 1 an integer, and τ : AZ → AZ a cellular
automaton. Then the following conditions are equivalent:

THE GARDEN OF EDEN THEOREM: OLD AND NEW

13

(a) τ is surjective;
(b) τ is pre-injective.
The implication (a) =⇒ (b) is due to Moore [39] and the converse to Myhill [43]. We
shall prove the contraposite of each implication. Before undertaking the proof of Theorem
4.1, let us first introduce some notation and establish some preliminary results.
Let S ⊂ Zd be a memory set for τ . Since any finite subset of Zd containing a memory set
for τ is itself a memory set for τ , it is not restrictive to suppose that S = {0, ±1, . . . , ±r}d
for some integer r ≥ 1.
Let us set, for each integer m ≥ 2r,
Ωm := {0, 1, . . . , m − 1}d

and

d
Ω+
m := {−r, −r + 1, . . . , m + r − 1}
d
Ω−
m := {r, r + 1, . . . , m − r − 1} ,

so that
(4.1)

|Ωm | = md ,

d
−
d
|Ω+
m | = (m + 2r) , and |Ωm | = (m − 2r) .
d

d
−
Observe that if two configurations x1 , x2 ∈ AZ coincide on Ωm (resp. Ω+
m , resp. Z \ Ωm )
d
then τ (x1 ) and τ (x2 ) coincide on Ω−
m (resp. Ωm , resp. Z \ Ωm ).
Also, let us set, for all integers k, n ≥ 1

Tnk := {t = (t1 k, t2 k, . . . , td k) ∈ Zd : 0 ≤ tj ≤ n − 1},

and observe that the nd cubes t + Ωk , for t running over Tnk , form a partition of the cube
Ωnk .
Finally, we introduce the following additional notation. Given a finite subset Ω ⊂ G and
p, q ∈ AΩ we write p ∼ q if and only if the patterns p and q are ME for τ . As usual, we
denote by AΩ / ∼ the quotient set of AΩ by ∼, i.e., the set of all ME-equivalence classes of
patterns supported by Ω.
In the proof of Theorem 4.1 we shall make use of the following elementary result (here
d
one should think of a := |A| as to the cardinality of the alphabet set and a(nk) (resp.
d
a(nk−2r) , for nk ≥ 2r) as to the number of all patterns supported by Ωnk (resp. Ω−
nk ), cf.
(4.1).
Lemma 4.2. Let a, k, d, r be positive integers with a ≥ 2.
n0 (a, k, d, r) ∈ N such that
 nd
 d
d
k
< a(nk−2r)
(4.2)
a −1

Then there exists n0 =

for all n ≥ n0 .

Proof. Taking logarithms to base a, Inequality (4.2) is equivalent to
d
 
 d
2r
k
(4.3)
loga a − 1 < k −
.
n

14

Since

TULLIO CECCHERINI-SILBERSTEIN AND MICHEL COORNAERT

d

 d
 d

2r
k
d
k
,
= k = lim k −
loga a − 1 < loga a
n→∞
n

we deduce that there exists n0 ∈ N such that (4.3) and therefore (4.2) are satisfied for all
n ≥ n0 .

Proof of Theorem 4.1. We can assume that a := |A| ≥ 2.
Suppose first that τ is not pre-injective. Then, by Proposition 3.18, τ admits two distinct
ME patterns, say p1 and p2 . Denote by Ω ⊂ Zd their common support. Since, for all t ∈ Zd ,
the patterns tp1 and tp2 (with support t+Ω) are also distinct and ME, and any finite subset
of Zd containing the support of two distinct ME patterns is itself the support of two distinct
ME patterns, we may assume that Ω = Ωk for some integer k ≥ 2r. As the patterns tp1
and tp2 are ME, we have that
d

|At+Ωk / ∼ | ≤ |At+Ωk | − 1 = ak − 1

(4.4)

for all t ∈ Zd .
Now observe that two patterns with support Ωnk are ME if their restrictions to t + Ωk
are ME for every t ∈ Tnk . Using (4.4), we deduce that
Y
d
d
|AΩnk / ∼ | ≤
|At+Ωk / ∼ | ≤ (ak − 1)n .
t∈Tnk

Taking n ≥ n0 (a, k, d, r), we then get
d

d

d

d

−

τ (AZ )Ω− ≤ |AΩnk / ∼ | ≤ (ak − 1)n < a(nk−2r) = |AΩnk |.
nk

d

−

This implies that τ (AZ )Ω− $ AΩnk , so that there must exist a GOE pattern for τ with
nk
support Ω−
nk . Consequently, τ is not surjective. This shows that (a) =⇒ (b).
Let us now turn to the proof of the converse implication. Suppose that τ is not surjective.
Then, by Proposition 3.13, there exists a GOE pattern p for τ . Since tp is a GOE pattern
for every t ∈ Zd , and any finite subset of Zd containing the support of a GOE pattern is
itself the support of a GOE pattern, we can assume that p is supported by the cube Ωk for
some integer k ≥ 2r.
Decompose again Ωnk into the nd translates t + Ωk , with t ∈ Tnk , and observe that
tp ∈ At+Ωk is GOE for every t ∈ Tnk . Any pattern q ∈ AΩnk which is not GOE satisfies
that q|t+Ωk is not GOE for every t ∈ Tnk . As a consequence, we have that
Y
d
d
d
d
τ (AZ )Ωnk ≤
(4.5)
τ (AZ )t+Ωk ≤ (ak − 1)n .
t∈Tnk

Let us fix now some element a0 ∈ A and consider the set X consisting of all configurations
d
x ∈ AZ that satisfy
x(g) = a0 for all g ∈ Zd \ Ω−
nk .

THE GARDEN OF EDEN THEOREM: OLD AND NEW

15

Observe that if x1 and x2 are in X, then τ (x1 ) and τ (x2 ) coincide on Zd \ Ωnk . It follows
that
|τ (X)| = |τ (X)Ωnk | .
On the other hand, taking n ≥ n0 (a, k, d, r) and using (4.5), we get
d

d

d

d

−

|τ (X)Ωnk | ≤ τ (AZ )Ωnk ≤ (ak − 1)n < a(nk−2r) = |AΩkn | = |X|
and hence
|τ (X)| < |X|.
By the pigeon-hole principle, this implies that there exist two distinct configurations
x1 , x2 ∈ X such that τ (x1 ) = τ (x2 ). As all configurations in X are almost equal, we
deduce that τ is not pre-injective. This shows that (b) =⇒ (a).

Remark 4.3. The proof of the implication (a) =⇒ (b) shows that if τ admits two
distinct ME patterns supported by a cube of side k ≥ 2r, then a cube of side nk − 2r, with
n ≥ n0 (a, k, d, r), must support a GOE pattern. Conversely, a small addition to the proof
of the implication (b) =⇒ (a) yields that if τ admits a GOE pattern supported by a cube
of side k ≥ 2r, then a cube of side kn + 2r, with n ≥ n0 (a, k, d, r), supports two distinct
d
ME patterns. Indeed, the proof shows the existence of two configurations x1 , x2 ∈ AZ
that coincide outside of Ω−
nk and satisfy τ (x1 ) = τ (x2 ). It then follows from the proof of
the implication (b) =⇒ (a) in Proposition 3.18 that the set
+
(Ω−
nk + (−S)) + S = Ωnk + S = Ωnk

supports two distinct ME patterns.
5. The Garden of Eden theorem for general amenable groups
5.1. Amenability. (cf. [27], [47], [12, Chapter 4], [21, Chapter 9])
Definition 5.1. A countable group G is called amenable if there exists a sequence (Fn )n∈N
of nonempty finite subsets of G such that
|Fn \ Fn g|
= 0 for all g ∈ G.
(5.1)
lim
n→∞
|Fn |
Such a sequence is called a Følner sequence for G.
Note that if A and B are finite sets with the same cardinality, then |A \ B| = |B \ A|
and |A △ B| = |A \ B| + |B \ A| = 2|A \ B|, where △ denotes symmetric difference of sets.
As |F g| = |F | for every finite subset F ⊂ G and any g ∈ G, it follows that Condition (5.1)
is equivalent to each of the following conditions:
|Fn g \ Fn |
(5.2)
lim
= 0 for all g ∈ G,
n→∞
|Fn |
or
|Fn △ Fn g|
(5.3)
lim
= 0 for all g ∈ G.
n→∞
|Fn |

16

TULLIO CECCHERINI-SILBERSTEIN AND MICHEL COORNAERT

Example 5.2. All finite groups are amenable. Indeed, if G is a finite group, then the
constant sequence, defined by Fn := G for all n ∈ N, is a Følner sequence for G since
Fn \ Fn g = ∅ for every g ∈ G.
Example 5.3. The free abelian groups of finite rank Zd , d ≥ 1, are also amenable. As a
Følner sequence for Zd , one can take for instance the sequence of cubes
(5.4)

Fn := {x ∈ Zd : kxk∞ ≤ n} = {0, ±1, . . . , ±n}d ,

where kxk∞ := max1≤i≤d |xi | for all x = (x1 , . . . , xd ) ∈ Zd is the sup-norm. To see this,
observe that
|Fn | = (2n + 1)d

(5.5)
and, by the triangle inequality,
Since

Fn + g ⊂ Fn+kgk∞ for all g ∈ Zd .
Fn ⊂ Fn+kgk∞ ,

this implies
(5.6)

|(Fn + g) \ Fn | ≤ (2n + kgk∞ + 1)d − (2n + 1)d .

As the right-hand side of (5.6) is a polynomial of degree d−1 in n while |Fn | is a polynomial
of degree d in n by (5.5), we conclude that
|(Fn + g) \ Fn |
= 0,
n→∞
|Fn |
lim

which is (5.2) in additive notation.

Let G be a finitely generated group. If S ⊂ G is a finite symmetric generating subset,
the Cayley graph of G with respect to S is the graph G(G, S) whose set of vertices is G
and two vertices g, h ∈ G are joined by an edge if and only if h = gs for some s ∈ S.
Equip the set of vertices of G(G, S) with its graph metric and consider the ball Bn ⊂ G of
radius n centered at 1G . It is easy to see that the sequence of positive integers (|Bn |)n∈N
is submultiplicative. Thus the limit
p
(5.7)
γ(G, S) := lim n |Bn |
n→∞

exists and satisfies 1 ≤ γ(G, S) < ∞. One says that the group G has subexponential growth
if γ(G, S) = 1 and exponential growth if γ(G, S) > 1. The fact that G has subexponential
(resp. exponential) growth does not depend on the choice of the finite generating subset
S ⊂ G although the value of γ(G, S) does.

Example 5.4. The groups Zd have subexponential growth. Indeed, if e1 , . . . , ed is the
canonical basis of Zd , and we take S := {±e1 , . . . , ±ed }, then the graphPdistance between
two vertices g and h of G(Zd , S) is kg − hk1 , where we write kxk1 := 1≤i≤d |xi | for the
1-norm of x = (x1 , . . . , xd ) ∈ Zd . We then have
Bn = {g ∈ Zd : kgk1 ≤ n} ⊂ {0, ±1, . . . , ±n}d

THE GARDEN OF EDEN THEOREM: OLD AND NEW

17

and hence |Bn | ≤ (2n + 1)d . This implies that Zd has subexponential growth. Here it can
be checked that the sequence (Bn )n∈N is also a Følner sequence for Zd .
When G is an arbitrary finitely generated group of subexponential growth and S is a
finite symmetric generating set for G, it can be shown that one can always extract a Følner
sequence from the sequence (Bn )n∈N . Consequently, every finitely generated group with
subexponential growth is amenable.
Example 5.5. A (nonabelian) free group on two generators has exponential growth and
is not amenable. Indeed, let G be a free group based on two generators a and b. Consider
the finite symmetric generating subset S ⊂ G defined by
S := {a, b, a−1 , b−1 }.
Then every element g ∈ G can be uniquely written in reduced form, i.e., in the form
(5.8)

g = s1 s2 . . . sn ,

where n ≥ 0, si ∈ S for all 1 ≤ i ≤ n, and si+1 6= s−1
for all 1 ≤ i ≤ n − 1. The integer
i
ℓS (g) := n is called the length of g with respect to the generators a and b. It is equal to
the distance from g to 1G in the Cayley graph G(G, S). We deduce that |Bn | = 4 · 3n−1 for
all n ≥ 1 so that
√
n
γ(G, S) = lim 4 · 3n−1 = 3 > 1.
n→∞

This shows that G has exponential growth.
Now suppose by contradiction that (Fn )n∈N is a Følner sequence for G and choose some
positive real number ε < 1/2. Since the sequence (Fn )n∈N is Følner, it follows from (5.1)
that there exists an integer N ≥ 0 such that the set F := FN satisfies
(5.9)

|F \ F s| ≤ ε|F | for all s ∈ S.

Denote, for each s ∈ S, by Gs the subset of G consisting of all elements g 6= 1G whose
reduced form ends with the letter s−1 . The four sets Gs , s ∈ S, are pairwise disjoint so
that
X
(5.10)
|F ∩ Gs | ≤ |F |.
s∈S

On the other hand, for each s ∈ S, we have that
(5.11)

|F | = |F \ Gs | + |F ∩ Gs | = |(F \ Gs )s| + |F ∩ Gs |.

We now observe that
(G \ Gs )s ⊂ Gs−1
so that
(F \ Gs )s ⊂ (F s \ F ) ∪ (F ∩ Gs−1 )

18

TULLIO CECCHERINI-SILBERSTEIN AND MICHEL COORNAERT

and hence
|(F \ Gs )s| ≤ |F s \ F | + |F ∩ Gs−1 |
= |F \ F s| + |F ∩ Gs−1 |
≤ ε|F | + |F ∩ Gs−1 |

(by (5.9)).

By using (5.11), we deduce that
|F | ≤ ε|F | + |F ∩ Gs−1 | + |F ∩ Gs |
for all s ∈ S. After summing up over all s ∈ S, this yields
X
4|F | ≤ 4ε|F | +
(|F ∩ Gs−1 | + |F ∩ Gs |)
s∈S

= 4ε|F | + 2

X
s∈S

|F ∩ Gs |.

Finally, combining with (5.10), we obtain
4|F | ≤ 4ε|F | + 2|F |
and hence |F | ≤ 2ε|F |, which is a contradiction since F 6= ∅ and ε < 1/2. This proves
that G is not amenable.
The class of amenable groups is closed under the operations of taking subgroups, quotients, extensions (this means that if 1 → H → G → K → 1 is an exact sequence with
both H and K amenable, so is G), and inductive limits. Consequently, all locally finite
groups, all abelian groups and, more generally, all solvable groups are amenable. On the
other hand every group containing a free subgroup on two generators is nonamenable. This
implies for instance that all nonabelian free groups and the groups SL(n, Z), n ≥ 2, are
nonamenable. However, there are groups containing no free subgroups on two generators
that are nonamenable. The first examples of such a group was given in [45] where Ol’šanskiı̆
constructed a nonamenable monster group in which every proper subgroup is cyclic.
Let us note that there are finitely generated groups of exponential growth that are
amenable. For example, the Baumslag-Solitar group BS(1, 2), i.e., the group with presentation ha, b : aba−1 = b2 i, and the lamplighter group, i.e., the wreath product (Z/2Z) ≀ Z,
have exponential growth but are both solvable and hence amenable (cf. [23]).
The original definition of amenability that was given by von Neumann [44] in 1929 is
that a group G is amenable if there exists a finitely additive invariant probability measure
defined on the set of all subsets of G. A key observation due to Day [22] is that this is
equivalent to the existence of an invariant mean on the Banach space ℓ∞ (G) of bounded
real-valued functions on G. It is also in [22] that the term amenable occured for the first
time (see [46, p. 137]). The fact that nonabelian free groups are not amenable is related to
the Hausdorff-Banach-Tarski paradox which actually was the motivation of von Neumann
for introducing the notion of amenability.

THE GARDEN OF EDEN THEOREM: OLD AND NEW

19

5.2. Entropy. Let G be countable group, A a finite set, and X a subset of AG (not
necessarily a subshift). Given a finite subset Ω ⊂ G, recall (cf. (2.1)) that
XΩ := {x|Ω : x ∈ X} ⊂ AΩ .

Suppose now that the group G is amenable and fix a Følner sequence F = (Fn )n∈N for G.
The entropy of X (with respect to F ) is defined by
(5.12)

hF (X) := lim sup
n→∞

log |XFn |
.
|Fn |

Since XF ⊂ AF and hence log |XF | ≤ |F | · log |A| for every finite subset F ⊂ G, we always
have
hF (X) ≤ hF (AG ) = log |A|.
Example 5.6. Take G = Z and A = {0, 1}. Let us compute the entropy of the golden
mean subshift X ⊂ AG (cf. Example 2.2) with respect to the Følner sequence F = (Fn )n∈N ,
where Fn := {0, 1, . . . , n}. We observe that un := |XFn | satisfies u0 = 2, u1 = 3, and
un+2 = un+1 + un for all n ≥ 2. Thus, the sequence (un )n∈N is a Fibonacci sequence and,
by Binet’s formula,

1
un = √ ϕn+3 − (1 − ϕ)n+3 ,
5
√
where ϕ := (1 + 5)/2 is the golden mean (this is the origin of the name of this subshift).
It follows that
log un
= log ϕ.
hF (X) = lim sup
n→∞ n + 1
Example 5.7. Take again G = Z and A = {0, 1}, and let us compute now the entropy
of the even subshift X ⊂ AG (cf. Example 2.4) with respect to the Følner sequence F =
(Fn )n∈N , where Fn := {0, 1, . . . , n}. We observe that un := |XFn | satisfies u0 = 2, u1 = 4,
and un+2 = 1 + un+1 + un for all n ≥ 2. Thus, the sequence (vn )n∈N , defined by vn := 1 + un
for all n ∈ N, is a Fibonacci sequence. As v0 = 3 and v1 = 5, by applying again Binet’s
formula, we get

1
un = −1 + vn = −1 + √ ϕn+5 − (1 − ϕ)n+5 ,
5
where ϕ is the golden mean. It follows that
hF (X) = lim sup
n→∞

log un
= log ϕ.
n+1

Thus, the even subshift has the same entropy as the golden mean subshift with respect to
F.
Example 5.8. Take G = Z2 and A = Z/2Z. Let us compute the entropy of the Ledrappier
subshift X ⊂ AG (cf. Example 2.5) with respect to the Følner sequence F = (Fn )n∈N ,
where Fn := {0, 1, . . . , n}2 . We observe that, for each x ∈ X, the pattern x|Fn is entirely

20

TULLIO CECCHERINI-SILBERSTEIN AND MICHEL COORNAERT

determined by x|Hn , where Hn ⊂ Z2 is the horizontal interval Hn := {0, 1, . . . , 2n} × {0}.
Therefore, un := |XFn | satisfies
log un ≤ |Hn | · log |A| = (2n + 1) log 2.
This gives us
hF (X) = lim sup
n→∞

log un
= 0.
(n + 1)2

Remark 5.9. It is a deep result due to Ornstein and Weiss [46] that, when G is a countable
amenable group, A a finite set, and X ⊂ AG a subshift, then the lim sup in (5.12) is actually
a true limit and does not depend on the particular choice of the Følner sequence F for G.
However, we shall not need it in the sequel.
An important property of cellular automata that we shall use in the proof of the Garden
of Eden theorem below is that they cannot increase entropy. More precisely, we have the
following result.
Proposition 5.10. Let G be a countable amenable group with Følner sequence F =
(Fn )n∈N and A, B finite sets. Suppose that τ : AG → B G is a cellular automaton and
X is a subset of AG . Then one has hF (τ (X)) ≤ hF (X).
For the proof, we shall use the following general property of Følner sequences.
Lemma 5.11. Let G be a countable amenable group with Følner sequence F = (Fn )n∈N
and let S be a finite subset of G. Then one has
(5.13)

lim

n→∞

|Fn S \ Fn |
= 0.
|Fn |

Proof. Observe that
Fn S \ Fn =
so that
|Fn S \ Fn | =
Thus we get

for all n ∈ N. As

[

s∈S

[

s∈S

(Fn s \ Fn )

(Fn s \ Fn ) ≤

X
s∈S

|Fn s \ Fn |.

|Fn S \ Fn | X |Fn s \ Fn |
≤
|Fn |
|Fn |
s∈S
|Fn s \ Fn |
=0
n→∞
|Fn |
lim

for each s ∈ S by (5.2), this gives us (5.13).



THE GARDEN OF EDEN THEOREM: OLD AND NEW

21

Proof of Proposition 5.10. Let us set Y := τ (X) and let S ⊂ G be a memory set for τ with
1G ∈ S. Recall that it immediately follows from (3.1) that if two configurations coincide
on gS for some g ∈ G then their images by τ take the same value at g. We deduce that
(5.14)

|YΩ | ≤ |XΩS |

for every finite subset Ω ⊂ G. Now observe that

XΩS ⊂ XΩ × XΩS\Ω ⊂ XΩ × AΩS\Ω ,

so that we get
log |YΩ | ≤ log |XΩ | + |ΩS \ Ω| · log |A|.

After replacing Ω by Fn and dividing both sides by |Fn |, this inequality becomes
(5.15)
As

log |YFn |
log |XFn | |Fn S \ Fn |
≤
+
· log |A|.
|Fn |
|Fn |
|Fn |
|Fn S \ Fn |
=0
n→∞
|Fn |
lim

by Lemma 5.11, taking the limsup in (5.15) finally gives the required inequality hF (Y ) ≤
hF (X).

Corollary 5.12. Let G be a countable amenable group and let A, B be finite sets with
|A| < |B|. Then there exists no surjective cellular automaton τ : AG → B G .
Proof. This is an immediate consequence of Proposition 5.10 since
hF (AG ) = log |A| < log |B| = hF (B G ).

The following example (cf. [46, p. 138]) shows that Corollary 5.12 becomes false if the
amenability hypothesis is removed.
Example 5.13. Let G be the free group on two generators a and b. Take A := Z/2Z and
B := Z/2Z × Z/2Z, so that |A| = 2 and |B| = 4. Consider the map τ : AG → B G defined
by
τ (x)(g) = (x(g) + x(ga), x(g) + x(gb))
for all x ∈ AG and g ∈ G. Observe that τ is a cellular automaton with memory set
S = {1G , a, b} and local defining map µ : AG → B given by
µ(p) = (p(1G ) + p(a), p(1G ) + p(b))
for all p ∈ AS . It is easy to check that τ is surjective. Note that AG and B G are totally
disconnected compact abelian topological groups and τ is a continuous group morphism
whose kernel consists of the two constant configurations in AG .

22

TULLIO CECCHERINI-SILBERSTEIN AND MICHEL COORNAERT

5.3. Tilings. Let G be a group. Given a finite subset E ⊂ G, let us say that a subset
T ⊂ G is an E-tiling of G provided the sets tE, t ∈ T , are pairwise disjoint and there
exists a finite subset E ′ ⊂ G such that the sets tE ′ , t ∈ T , cover G.
Example 5.14. Take G = Zd and E = {0, ±1, ±2, . . . , ±m}d for some m ∈ N, then
T := ((2m + 1)Z)d ⊂ Zd is an E-tiling (here one can take E ′ = E).
Given any nonempty finite subset E of a group G, we can use Zorn’s lemma to prove
that there always exists an E-tiling T ⊂ G. Indeed, consider the set S(E) consisting of all
subsets S ⊂ G such that the sets sE, s ∈ S, are pairwise disjoint. We first observe that
S(E) is nonempty since {1G } ∈ S(E). On the other hand, S(E) is inductive with respect
to set inclusion since if S ′ ⊂ S(E) is a chain, then M := ∪S∈S ′ S belongs to S(E) and is
an upper bound for S ′ . By Zorn’s lemma, there exists a maximal element T ∈ S(E). As
T ∈ S(E), the sets tE, t ∈ T , are pairwise disjoint. Now, given any g ∈ G, we can find, by
maximality of T , an element t = t(g) ∈ T such that gE ∩ tE 6= ∅ and hence g ∈ tEE −1 . It
follows that the sets tEE −1 , t ∈ T , cover G. Since the set E ′ := EE −1 is finite, this shows
that T is an E-tiling of G.
For the proof of the Garden of Eden theorem in the next subsection, we shall use some
technical results about tilings in amenable groups.
Lemma 5.15. Let G be a countable amenable group with Følner sequence F = (Fn )n∈N .
Let E ⊂ G be a nonempty finite subset and T ⊂ G an E-tiling. Define, for n ∈ N, the
subset Tn ⊂ T by
Tn := {t ∈ T : tE ⊂ Fn }.
Then there exist a constant α = α(F , T ) > 0 and n0 ∈ N such that
(5.16)

|Tn | ≥ α|Fn |

for all n ≥ n0 .

Proof. Since T is a E-tiling, there exists a finite subset E ′ ⊂ G such that the sets tE ′ ,
t ∈ T , cover G. After replacing E ′ by E ′ ∪ E, if necessary, we may assume that E ⊂ E ′ .
Define, for n ∈ N,
Tn+ := {t ∈ T : tE ′ ∩ Fn 6= ∅}.

Clearly Tn ⊂ Tn+ . As the sets tE ′ , t ∈ Tn+ , cover Fn , we have |Fn | ≤ |Tn+ | · |E ′ | so that
|Tn+ |
1
≥ ′
|Fn |
|E |

(5.17)
for all n ∈ N. Now observe that
Tn+

=T∩

[

g∈E ′

Fn g

−1

!

and Tn = T ∩

\

h∈E

−1

Fn h

!

,

THE GARDEN OF EDEN THEOREM: OLD AND NEW

so that
Tn+ \ Tn = T ∩
⊂

[

g∈E ′

g∈E ′

g∈E ′ , h∈E

We deduce that
|Tn+ \ Tn | ≤

X

g∈E ′ , h∈E

As

Fn g −1 \

Fn g −1 \

[

=

[

\

\

Fn h−1

h∈E

23

!

Fn h−1

h∈E

(Fn g −1 \ Fn h−1 ).

|Fn g −1 \ Fn h−1 | =

X

g∈E ′ , h∈E

|Fn \ Fn h−1 g|.

|Fn \ Fn h−1 g|
=0
n→∞
|Fn |
for all g ∈ E ′ and h ∈ E by (5.1), it follows that
lim

|Tn+ | − |Tn |
|T + \ Tn |
= n
→0
|Fn |
|Fn |
1
, we deduce that there exists n0 ∈ N such
as n → ∞. Using (5.17) and taking ε :=
2|E ′|
that
|T + | |T + | − |Tn |
1
|Tn |
= n − n
≥ ′ − ε = α,
|Fn |
|Fn |
|Fn |
|E |
1
, for all n ≥ n0 .

where α :=
2|E ′ |
Proposition 5.16. Let G be a countable amenable group with Følner sequence F =
(Fn )n∈N and let A be a finite set. Let X ⊂ AG be a subset and suppose there exist a
nonempty finite subset E ⊂ G and an E-tiling T ⊂ G such that XtE $ AtE for all t ∈ T .
Then hF (X) < log |A|.
Proof. Let us set, as above, Tn := {t ∈ T : tE ⊂ Fn } and write
[
tE,
Fn∗ := Fn \

for all n ∈ N. Observe that

S

t∈Tn

t∈Tn

tE ⊂ Fn so that
Y
∗
XtE
XFn ⊂ AFn ×
t∈Tn

and
(5.18)

|Fn | = |Fn∗ | + |Tn | · |E|.

24

TULLIO CECCHERINI-SILBERSTEIN AND MICHEL COORNAERT

It follows that
log |XFn | ≤ |Fn∗ | · log |A| +

X

t∈Tn

X

log |XtE |


≤

|Fn∗ |

· log |A| +

=

|Fn∗ |

· log |A| + |Tn | · log(|A||E| − 1)

t∈Tn

log |AtE | − 1

= |Fn∗ | · log |A| + |Tn | · |E| · log |A| + |Tn | · log(1 − |A|−|E| )
= |Fn | · log |A| + |Tn | · log(1 − |A|−|E| ),

where the last equality follows from (5.18). Setting c := − log(1 − |A|−|E|) > 0, we deduce
that
log |XFn |
hF (X) = lim sup
≤ log |A| − cα < log |A|,
|Fn |
n→∞
where α = α(F , T ) is as in (5.16).

Corollary 5.17. Let G be a countable amenable group with Følner sequence F = (Fn )n∈N
and let A be a finite set. Let X ⊂ AG be a subshift and suppose that there exists a nonempty
finite subset E ⊂ G such that XE $ AE . Then one has hF (X) < log |A|.

Proof. If T is an E-tiling of G, we deduce from the shift-invariance of X that XtE $ AtE
for all t ∈ T , so that Proposition 5.16 applies.

5.4. The Garden of Eden theorem for amenable groups. The following result is due
to Machı̀, Scarabotti, and the first author [20]. Since the groups Zd are all amenable, it
extends Theorem 4.1.

Theorem 5.18. Let G be a countable amenable group with Følner sequence F = (Fn )n∈N
and A a finite set. Suppose that τ : AG → AG is a cellular automaton. Then the following
conditions are equivalent:
(a) τ is surjective;
(b) hF (τ (AG )) = log |A|;
(c) τ is pre-injective.
Proof. The implication (a) =⇒ (b) is obvious since hF (AG ) = log |A|.
In order to show the converse implication, let us suppose that τ is not surjective, that
is, the image subshift X := τ (AG ) is such that X $ AG . Since X is closed in AG , there
exists a finite subset E ⊂ G such that XE $ AE . By applying Corollary 5.17, we deduce
that hF (X) < log |A|. This shows (b) =⇒ (a).
Let S ⊂ G be a memory set for τ such that 1G ∈ S.
Let us show (b) =⇒ (c). Suppose that τ is not pre-injective. By virtue of Proposition 3.18, we can find a nonempty finite subset Ω ⊂ G and two patterns p1 , p2 ∈ AΩ that
are mutually erasable for τ . Let E := ΩS −1 S. Observe that Ω ⊂ E since 1G ∈ S. Let
T ⊂ G be an E-tiling of G. Consider the subset Z ⊂ AG defined by
Z := {z ∈ AG : z|tΩ 6= tp1 for all t ∈ T }.

THE GARDEN OF EDEN THEOREM: OLD AND NEW

25

Observe that ZtE $ AtE for all t ∈ T . By using Proposition 5.10 and Proposition 5.16, we
deduce that hF (τ (Z)) ≤ hF (Z) < log |A|. We claim that τ (Z) = τ (AG ). Let x ∈ AG . Let
Tx := {t ∈ T : x|tΩ = tp1 } and define z ∈ Z by setting, for all g ∈ G,
(
tp2 (g) if g ∈ tΩ for some t ∈ Tx
z(g) :=
x(g)
otherwise.
Let us check that τ (z) = τ (x). Let g ∈ G. If g ∈
/ ∪t∈Tx tΩS −1 , then gS ∩ tΩ = ∅ for all
t ∈ Tx and therefore z|gS = x|gS , so that τ (z)(g) = τ (x)(g). Suppose now that g ∈ tΩS −1
for some (unique) t = t(g) ∈ Tx and consider the configuration y ∈ AG defined by setting,
for all h ∈ G,
(
tp2 (h) if h ∈ tΩ
y(h) :=
x(h)
otherwise.
Observe that x|G\tΩ = y|G\tΩ . Since the patterns x|tΩ = tp1 and y|tΩ = tp2 are mutually
erasable, we deduce that τ (y) = τ (x). Moreover, as gS ⊂ tΩS −1 S = tE, we have z|gS =
y|gS , and therefore τ (z)(g) = τ (y)(g) = τ (x)(g). This shows that τ (z) = τ (x), and
the claim follows. We conclude that hF (τ (AG )) = hF (τ (Z)) < log |A|. This shows the
implication (b) =⇒ (c).
Finally, let us show (c) =⇒ (b). Let us set as above X := τ (AG ) and suppose that
hF (X) < log |A|. As 1G ∈ S, we have Fn ⊂ Fn S −1 so that
XFn S −1 ⊂ XFn × AFn S

−1 \F

n

,

for all n ∈ N. We deduce that
log |XFn | |Fn S −1 \ Fn |
log |XFnS −1 |
≤
+
log |A|.
(5.19)
|Fn |
|Fn |
|Fn |

As

|Fn S −1 \ Fn |
=0
n→∞
|Fn |
by Lemma 5.11, we deduce from (5.19) that
lim

lim sup
n→∞

log |XFnS −1 |
log |XFn |
≤ lim sup
= hF (X) < log |A|.
|Fn |
|Fn |
n→∞

Consequently, we can find n0 ∈ N such that,

(5.20)

|XFn0 S −1 | < |A||Fn0 | .

Fix a0 ∈ A and consider the subset Z ⊂ AG defined by

Z := {z ∈ AG : z(g) = a0 for all g ∈ G \ Fn0 }.

Note that |Z| = |A||Fn0 | . Let z1 , z2 ∈ Z. If g ∈ G \ Fn0 S −1 , then z1 and z2 coincide on
gS ⊂ G\Fn0 so that τ (z1 )(g) = τ (z2 )(g). Therefore τ (z1 ) and τ (z2 ) coincide on G\Fn0 S −1 .
This implies that |τ (Z)| ≤ |XFn0 S −1 |. Using (5.20), we deduce that |τ (Z)| < |Z|. By the
pigeon-hole principle, there exist two distinct elements z1 , z2 ∈ Z such that τ (z1 ) = τ (z2 ).

26

TULLIO CECCHERINI-SILBERSTEIN AND MICHEL COORNAERT

As all elements in Z are almost equal (they coincide outside of the finite set Fn0 ), we
conclude that τ is not pre-injective.

6. Failure of the Garden of Eden theorem for nonamenable groups
Let us say that a countable group G has the Moore property if every surjective cellular
automaton τ : AG → AG with finite alphabet A over G is pre-injective and that it has
the Myhill property if every pre-injective cellular automaton τ : AG → AG with finite
alphabet A over G is surjective. Also let us say that a countable group G satisfies the
Garden of Eden theorem if G has both the Moore and the Myhill properties. Theorem 5.18
tells us that every countable amenable group satisfies the Garden of Eden theorem. The
examples below, essentially due to Muller [42] (see also [36, Section 6], [20, Section 6],
[12, Chapter 5]), show that neither the Moore nor the Myhill property holds for countable
groups containing nonabelian free subgroups.
Example 6.1. Let G be a countable group and suppose that G contains two elements
a and b generating a nonabelian free subgroup H ⊂ G. Take A = {0, 1} and let S :=
{a, a−1 , b, b−1 }. Consider the cellular automaton τ : AG → AG with memory set {1G } ∪ S
defined by
(
0 if x(g) + x(ga) + x(ga−1 ) + x(gb) + x(gb−1 ) ≤ 2
:=
τ (x)(g)
1 otherwise
for all x ∈ AG and g ∈ G.
The pair of configurations (x1 , x2 ) ∈ AG × AG , defined by x1 (g) = 0 for all g ∈ G, and
x2 (g) = 0 for all g ∈ G \ {1G } and x2 (1G ) = 1, is a diamond for τ . Therefore τ is not
pre-injective. However, τ is surjective. To see this, let y ∈ AG . Let us show that there
exists x ∈ AG such that τ (x) = y. Let R ⊂ G be a complete set of representatives of
the left cosets of H in G. We define x as follows. Every element g ∈ G can be uniquely
written in the form g = rh with r ∈ R and h ∈ H. If g ∈ R, i.e., h = 1G , we set x(g) := 0.
Otherwise, we set x(g) := y(rh− ), where h− is the predecessor of h in H, i.e., the unique
element h− ∈ H such that ℓS (h− ) = ℓS (h) − 1 and h = h− s for some s ∈ S (here ℓS (·)
denotes the length of the reduced form for elements of H, see Example 5.5). One easily
checks that τ (x) = y. This shows that τ is surjective. Thus the Moore implication fails to
hold for groups containing nonabelian free subgroups.
Example 6.2. Let G be a countable group and suppose that G contains two elements a
and b generating a nonabelian free subgroup H ⊂ G. Let A = Z/2Z × Z/2Z be the Klein
four-group and consider the group endomorphisms p and q of A respectively defined by
p(α, β) = (α, 0) and q(α, β) = (β, 0) for all (α, β) ∈ A. Let τ : AG → AG be the cellular
automaton with memory set S := {a, a−1 , b, b−1 } defined by
τ (x)(g) = p(x(ga)) + p(x(ga−1 ) + q(x(gb)) + q(x(gb−1 ))

for all x ∈ AG and g ∈ G. The image of τ is contained in (Z/2Z × {0})G . Therefore
τ is not surjective. We claim that τ is pre-injective. As τ is a group endomorphism of

THE GARDEN OF EDEN THEOREM: OLD AND NEW

27

AG , it suffices to show that there is no configuration with finite support in the kernel of
τ . Assume on the contrary that there is an element x ∈ AG with nonempty finite support
Ω := {g ∈ G : x(g) 6= 0A } ⊂ G such that τ (x) = 0. Let R ⊂ G be a complete set of
representatives of the left cosets of H in G. Let us set Ωr := Ω ∩ rH for all r ∈ R. Then
Ω is the disjoint union of the sets Ωr , r ∈ R. Let r ∈ R such that Ωr 6= ∅ and consider
an element g = rh ∈ Ωr with h ∈ H at maximal distance from the identity in the Cayley
graph of (H, S) (i.e., with ℓS (h) maximal). We have that x(g) = (α, β) 6= (0, 0) = 0A .
Suppose first that α 6= 0. We can find s ∈ {a, a−1 } such that ℓS (hs) = ℓS (h) + 1. For all
t ∈ S \ {s−1 }, we have that ℓS (hst) = ℓ(h) + 2 and hence x(gst) = 0A by maximality. It
follows that
τ (x)(gs) = p(x(g)) = (α, 0) 6= 0A ,
which contradicts the fact that x is in the kernel of τ . Suppose now that α = 0. Then
β 6= 0. We take now s ∈ {b, b−1 } such that ℓS (hs) = ℓS (h) + 1. By an argument similar to
the one that we used in the first case, we get
τ (x)(gs) = q(x(g)) = (β, 0) 6= 0A ,

so that we arrive at a contradiction also in this case. Thus τ is pre-injective. This shows
that the Myhill implication fails to hold for groups containing nonabelian free subgroups.
As mentioned in Subsection 5.1, there are nonamenable countable groups containing no
nonabelian free subgroups. However, Bartholdi [2] (see [12, Chapter 5]) proved that the
Moore property fails to hold for all nonamenable countable groups. Recently, Bartholdi and
Kielak [3] also proved that the Myhill property fails to hold for all nonamenable countable
groups. Combining these results with the Garden of Eden theorem for amenable groups
(Theorem 5.18), this yields the following characterization of amenability in terms of cellular
automata.
Theorem 6.3. Let G be a countable group. Then the following conditions are equivalent:
(a) G is amenable;
(b) G has the Moore property;
(c) G has the Myhill property;
(d) G satisfies the Garden of Eden theorem.
7. The Garden of Eden theorem for subshifts
7.1. Strongly irreducible subshifts. Let G be a countable group and A a finite set.
A subshift X ⊂ AG is called strongly irreducible if there is a finite subset ∆ ⊂ G
satisfying the following property: if Ω1 and Ω2 are finite subsets of G such that Ω1 ∆ does
not meet Ω2 , then, given any two configurations x1 , x2 ∈ X, there exists a configuration
x ∈ X which coincides with x1 on Ω1 and with x2 on Ω2 .
Example 7.1. The full shift AG is strongly irreducible (one can take ∆ = {1G }).

Example 7.2. The even subshift X ⊂ {0, 1}Z , described in Example 2.4, is strongly
irreducible (one can take ∆ = {−2, −1, 0, 1, 2}).

28

TULLIO CECCHERINI-SILBERSTEIN AND MICHEL COORNAERT

Example 7.3. The hard-ball model, described in Example 2.3, is strongly irreducible
(one can take ∆ = {0, ±e1 , . . . , ±ed }). In particular (d = 1), the golden mean subshift is
strongly irreducible.
Example 7.4. The Ledrappier subshift, described in Example 2.5, is not strongly irreducible.
Fiorenzi [25, Theorem 4.7] obtained the following extension of Theorem 5.18.
Theorem 7.5. Let G be a countable amenable group with Følner sequence F = (Fn )n∈N
and A, B finite sets. Suppose that X ⊂ AG is a strongly irreducible subshift of finite type
and Y ⊂ B G is a strongly irreducible subshift with hF (X) = hF (Y ) and that τ : X → Y is
a cellular automaton. Then the following conditions are equivalent:
(a) τ is surjective;
(b) hF (τ (X)) = hF (Y );
(c) τ is pre-injective.
Example 7.6. The cellular automaton τ : X → Y from the golden mean subshift to the
even subshift described in Example 3.7 satisfies all the hypotheses in the previous theorem.
As τ is pre-injective (cf. Example 3.16), we deduce that τ is surjective. Note that here one
might also easily obtain surjectivity of τ by a direct argument.
7.2. The Moore and the Myhill properties for subshifts. Let G be a countable
group, A a finite set, and X ⊂ AG a subshift. One says that the subshift X has the Moore
property if every surjective cellular automaton τ : X → X is pre-injective and that it has
the Myhill property if every pre-injective cellular automaton τ : X → X is surjective. One
says that X has the Moore-Myhill property or that it satisfies the Garden of Eden theorem
if it has both the Moore and the Myhill properties.
From Theorem 7.5, we immediately deduce the following.
Corollary 7.7. Let G be a countable amenable group and A a finite set. Then every
strongly irreducible subshift of finite type X ⊂ AG has the Moore-Myhill property.

Example 7.8. Let G = Zd and A = {0, 1}. Consider the hard-ball model X ⊂ AG
described in Example 2.3. As Zd is amenable and X is both strongly irreducible and
of finite type, we deduce from Corollary 7.7 that X has the Moore-Myhill property. In
particular (d = 1), the golden mean subshift has the Moore-Myhill property.

Example 7.9 (Fiorenzi). Let A = {0, 1} and let X ⊂ AZ be the even subshift (cf. Example 2.4). Consider the cellular automaton σ : AZ → AZ with memory set S = {0, 1, 2, 3, 4}
and local defining map µ : AS → A given by
(
1 if y(0)y(1)y(2) ∈ {000, 111} or y(0)y(1)y(2)y(3)y(4) = 00100
µ(y) =
0 otherwise.
Then one has σ(X) ⊂ X, and the cellular automaton τ := σ|X : X → X is not pre-injective.
Indeed, the configurations x1 , x2 ∈ X defined by
x1 = · · · 0 · · · 00(100)100 · · · 0 · · ·

THE GARDEN OF EDEN THEOREM: OLD AND NEW

29

and
satisfy

x2 = · · · 0 · · · 00(011)100 · · · 0 · · ·

τ (x1 ) = · · · 1 · · · 11(100)10011 · · · 1 · · · = τ (x2 ).
Observe, alternatively, that the patterns p, q with support Ω := {0, 1, . . . , 12} defined by
(
(
1 if n = 6, 9
1 if n = 7, 8, 9
p(n) =
and q(n) =
0 otherwise
0 otherwise,
for all n ∈ Ω, are ME.
From a case-by-case analysis, one can show that τ is surjective. It follows that X does
not have the Moore property.
We refer to [24, Section 3] and [19, Counterexample 2.18] for more details.
As the even subshift is strongly irreducible and Z is amenable, the previous example
shows that the hypothesis that X is of finite type cannot be removed from Corollary 7.7.
However, we have the following (cf. [14]).
Theorem 7.10. Let G be a countable amenable group and A a finite set. Then every
strongly irreducible subshift X ⊂ AG has the Myhill property.
Example 7.11. The even subshift X ⊂ {0, 1}Z has the Myhill property since it is strongly
irreducible and Z is amenable.

Example 7.12. Let A = {0, 1}. Let x0 , x1 ∈ AZ denote the two constant configurations
respectively defined by x0 (n) = 0 and x1 (n) = 1 for all n ∈ Z. Note that X = {x0 , x1 } is
a subshift of finite type. The map τ : X → X given by τ (x0 ) = τ (x1 ) = x0 is a cellular
automaton which is pre-injective but not surjective. It follows that X does not have the
Myhill property. This very simple example shows that the hypothesis that X is strongly
irreducible cannot be removed neither from Corollary 7.7 nor from Theorem 7.10. Note
that X has the Moore property since X is finite, so that every surjective self-mapping of
X is injective and therefore pre-injective.
Example 7.13 (Fiorenzi). Let A = {0, 1, 2} and let X ⊂ AZ be the subshift of finite type
consisting of all x ∈ AZ such that
x(n)x(n + 1) ∈
/ {01, 02}

for all n ∈ Z.

Thus a configuration x : Z → A is in X if and only if one of the following conditions is
satisfied:
(i) x(n) = 0 for all n ∈ Z;
(ii) x(n) 6= 0 for all n ∈ Z;
(iii) there exists n0 ∈ N such that x(n) ∈ {1, 2} for all n ≤ n0 and x(n) = 0 for all n > n0 .
Consider the cellular automaton σ : AZ → AZ with memory set S = {0, 1} and local
defining map
(
y(0) if y(1) 6= 0
µ(y) =
0
otherwise.

30

TULLIO CECCHERINI-SILBERSTEIN AND MICHEL COORNAERT

Observe that σ(x) = x if x ∈ X is of type (i) or (ii) while, if x ∈ X is of type (iii), then σ(x)
is obtained from x by replacing its rightest nonzero term by 0. We deduce that σ(X) ⊂ X
and that the cellular automaton τ := σ|X : X → X is surjective but not pre-injective (see
[24, Counterexample 4.27]). It follows that X does not have the Moore property.
It turns out that X does not have the Myhill property either. Indeed, consider now the
cellular automaton σ ′ : AZ → AZ with memory set S ′ = {−1, 0} and local defining map
(
y(0)
if y(−1)y(0) ∈
/ {10, 20}
µ′ (y) =
y(−1) otherwise.
Observe that σ ′ (x) = x if x ∈ X is of type (i) or (ii) while, if x ∈ X is of type (iii), then
σ ′ (x) is obtained from x by repeating on its right its rightest nonzero term. We deduce
that σ ′ (X) ⊂ X and that the cellular automaton τ ′ := σ ′ |X : X → X is injective and
hence pre-injective. However, τ ′ is not surjective (observe for instance that the pattern
p ∈ A{−1,0,1} defined by p(−1)p(0)p(1) = 120 is a Garden of Eden pattern for τ ′ ).

Let A be a finite set and X ⊂ AZ a subshift. One says that a word u ∈ A⋆ of length
n appears in X if there is a configuration x ∈ X and m ∈ Z such that u = x(m)x(m +
1) · · · x(m + n − 1). The subset L(X) ⊂ A⋆ consisting of all words that appear in X is
called the language of X. One says that the subshift X is irreducible if given any two
words u, v ∈ L(X) there exists a word w ∈ L(X) such that uwv ∈ L(X). Clearly every
strongly irreducible subshift X ⊂ AZ is irreducible. The converse is false as shown by the
following example.
Example 7.14. Let A = {0, 1} and consider the subshift X ⊂ AZ consisting of the two
configurations x ∈ AZ that satisfy x(n) 6= x(n + 1) for all n ∈ Z. It is clear that X is
irreducible but not strongly irreducible. Observe that X is of finite type.
The following result is an immediate consequence of [32, Theorem 8.1.16] (cf. [24, Corollary 2.19]).
Theorem 7.15. Let A be a finite set. Then every irreducible subshift of finite type X ⊂ AZ
has the Moore-Myhill property.
8. Garden of Eden theorems for other dynamical systems
8.1. Dynamical systems. By a dynamical system, we mean a triple (X, G, α), where X
is a compact metrizable space, G is a countable group, and α is a continuous action of G
on X. The space X is called the phase space of the dynamical system. If there is no risk
of confusion, we shall write (X, G), or even sometimes simply X, instead of (X, G, α).
Example 8.1. Let G be a countable group and A a compact metrizable topological space
(e.g. a finite set with its discrete topology). Equip AG = {x : G → A} with the product
topology. The shift action σ of G on AG is the action defined by σ(g, x) = gx, where
(gx)(h) = x(g −1 h)
for all x ∈ AG and g, h ∈ G. Then (AG , G, σ) is a dynamical system.

THE GARDEN OF EDEN THEOREM: OLD AND NEW

31

Example 8.2. If (X, G, α) is a dynamical system and Y ⊂ X is a closed α-invariant
subset, then (Y, G, α|Y ), where α|Y denotes the action of G on Y induced by restriction
of α, is a dynamical system. In particular, if G is a countable group, A a finite set, and
X ⊂ AG a subshift, then (X, G, σ|X ) is a dynamical system.
Example 8.3. Let f : X → X be a homeomorphism of a compact metrizable space X.
The dynamical system generated by f is the dynamical system (X, Z, αf ), where αf is the
action of Z on X given by αf (n, f ) := f n (x) for all n ∈ Z and x ∈ X. We shall also write
(X, f ) to denote the dynamical system generated by f .
Remark 8.4. If we fix the countable group G, the dynamical systems (X, G) are the
objects of a concrete category DG in which the morphisms from an object X ∈ DG to
another object Y ∈ DG consist of all equivariant continuous maps τ : X → Y . It follows
from the Curtis-Hedlund-Lyndon theorem (cf. Theorem 3.8) that the category CG described
in Remark 3.10 is a full subcategory of the category DG .

e G) be two dynamical systems.
Let (X, G) and (X,
e G) are topologically conjugate if
One says that the dynamical systems (X, G) and (X,
they are isomorphic objects in the category DG , i.e., if there exists an equivariant homeoe → X.
morphism h : X
e G) if there exists an equivariant continuous
One says that (X, G) is a factor of (X,
e → X. Such a map θ is then called a factor map. A factor map
surjective map θ : X
e → X is said to be finite-to-one if the pre-image set θ−1 (x) is finite for each x ∈ X. A
θ: X
finite-to-one factor map is said to be uniformly bounded-to-one if there is an integer K ≥ 1
such that |θ−1 (x)| ≤ K for all x ∈ X.
8.2. Expansiveness. One says that a dynamical system (X, G) is expansive if there exists
a neighborhood W ⊂ X × X of the diagonal
∆X := {(x, x) : x ∈ X} ⊂ X × X

such that, for every pair of distinct points x, y ∈ X, there exists an element g = g(x, y) ∈ G
such that (gx, gy) ∈
/ W . Such a set W is then called an expansiveness neighborhood of the
diagonal.
If d is a metric on X compatible with the topology, the fact that (X, G) is expansive is
equivalent to the existence of a constant δ > 0 such that, for every pair of distinct points
x, y ∈ X, there exists an element g = g(x, y) ∈ G such that d(gx, gy) ≥ δ.

Example 8.5. Let G be a countable group and A a finite set. Then the G-shift on AG is
expansive. Indeed, it is clear that
W := {(x, y) ∈ AG × AG : x(1G ) = y(1G )}

is an expansiveness neighborhood of ∆AG .

Example 8.6. If (X, G) is an expansive dynamical system and Y ⊂ X is a closed invariant
subset, then (Y, G) is expansive. Indeed, if W is an expansiveness neighborhood of ∆X ,
then W ∩(Y ×Y ) is an expansiveness neighborhood of ∆Y . In particular, if G is a countable

32

TULLIO CECCHERINI-SILBERSTEIN AND MICHEL COORNAERT

group, A a finite set, and X ⊂ AG a subshift, then the dynamical system (X, G, σ|X ) is
expansive.
8.3. Homoclinicity. Let (X, G) be a dynamical system. Two points x, y ∈ X are called
homoclinic with respect to the action of G on X, ore more briefly, G-homoclinic, if for any
neighborhood W ⊂ X × X of the diagonal ∆X , there is a finite set F = F (W, x, y) ⊂ G
such that (gx, gy) ∈ W for all g ∈ G \ F .
If d is a metric on X that is compatible with the topology, two points x, y ∈ X are
homoclinic if and only if
lim d(gx, gy) = 0,
g→∞

where ∞ is the point at infinity in the one-point compactification of the discrete group G.
This means that, for every ε > 0, there is a finite subset F = F (ε, d, x, y) ⊂ G such that
d(gx, gy) < ε for all g ∈ G \ F .
Homoclinicity clearly defines an equivalence relation on X (transitivity follows from the
triangle inequality). The equivalence classes of this relation are called the G-homoclinicity
classes of X.
Definition 8.7. Let (X, G) be a dynamical system and Y a set. One says that a map
τ : X → Y is pre-injective if its restriction to each G-homoclinicity class is injective.
Example 8.8. Let G be a countable group and A a finite set. Two configurations x, y ∈ AG
are homoclinic with respect to the shift action of G on AG if and only if they are almost
equal (see e.g. [16, Proposition 2.5]). Indeed, first observe that the sets
WΩ := {(x, y) ∈ AG × AG : x|Ω = y|Ω },

where Ω runs over all finite subsets of G, form a neighborhood base of the diagonal ∆AG ⊂
AG × AG (this immediately follows from the definition of the product topology). Now, if
x, y ∈ AG are almost equal, then the set D ⊂ G consisting of all g ∈ G such that x(g) 6= y(g)
is finite, so that ΩD −1 is also finite for every finite subset Ω ⊂ G. As (gx, gy) ∈ WΩ for every
g ∈ G\ΩD −1 , this implies that x and y are homoclinic. Conversely, suppose that x, y ∈ AG
are homoclinic. Then there exists a finite subset F ⊂ G such that (gx, gy) ∈ W{1G } for all
g ∈ G \ F . This implies that x(g) = y(g) for all g ∈ G \ F −1 , so that x and y are almost
equal.
Example 8.9. Let (X, G, α) be a dynamical system and Y ⊂ X a closed invariant subset.
Denote as above by α|Y the restriction of α to Y . Then two points x, y ∈ Y are homoclinic
with respect to α|Y if and only if they are homoclinic with respect to α. In particular, if
G is a countable group, A a finite set, and X ⊂ AG a subshift, then two configurations
x, y ∈ X are homoclinic with respect to σ|X if and only if they are almost equal. It
follows that the definition of pre-injectivity for cellular automata between subshifts given
in Definition 3.14 agrees with the one given in Definition 8.7 above.
8.4. The Moore and the Myhill properties for dynamical systems. Let (X, G) be
a dynamical system.
An endomorphism of (X, G) is a continuous equivariant map τ : X → X.

THE GARDEN OF EDEN THEOREM: OLD AND NEW

33

One says that the dynamical system (X, G) has the Moore property if every surjective
endomorphism of (X, G) is pre-injective and that it has the Myhill property if every preinjective endomorphism of (X, G) is surjective. One says that (X, G) has the Moore-Myhill
property or that it satisfies the Garden of Eden theorem if it has both the Moore and the
Myhill properties.
Observe that all these properties are invariants of topological conjugacy in the sense
that if the dynamical systems (X, G) and (Y, G) are topologically conjugate then (X, G)
has the Moore (resp. the Myhill, resp. the Moore-Myhill) property if and only if (Y, G) has
the Moore (resp. the Myhill, resp. the Moore-Myhill) property.
Remark 8.10. In the particular case when (X, G) is a subshift, it immediately follows
from Theorem 3.8 and Example 8.9 that these definitions are equivalent to the ones given
in Subsection 7.2.
8.5. Anosov diffeomorphisms. Let f : M → M be a diffeomorphism of a compact
smooth manifold M. One says that f is an Anosov diffeomorphism (see e.g. [51], [7],
[50]) if the tangent bundle T M of M continuously splits as a direct sum T M = Es ⊕ Eu
of two df -invariant subbundles Es and Eu such that, with respect to some (or equivalently
any) Riemannian metric on M, the differential df is exponentially contracting on Es and
exponentially expanding on Eu , i.e., there are constants C > 0 and 0 < λ < 1 such that
(i) kdf n (v)k ≤ Cλn kvk,
(ii) kdf −n (w)k ≤ Cλn kwk
for all x ∈ M, v ∈ Es (x), w ∈ Eu (x), and n ≥ 0.
Example 8.11 (Arnold’s cat). Consider the matrix


0 1
A=
1 1

and the diffeomorphism f of the 2-torus T2 = R2 /Z2 = R/Z × R/Z given by


 
x2
x1
f (x) := Ax =
for all x =
∈ T2 .
x1 + x2
x2

The dynamical system (T2 , f ) is known as Arnold’s cat. The diffeomorphism
√ f is Anosov.
1
1+ 5
Indeed, the eigenvalues of A are λ1 = − , and λ2 = ϕ, where ϕ :=
is the golden
ϕ
2
mean. As −1 < λ1 < 0 and 1 < λ2 , it follows that df = A is exponentially contracting in
the direction of the eigenline associated with λ1 and uniformly expanding in the direction
of the eigenline associated with λ2 .
Example 8.12 (Hyperbolic toral automorphism). More generally, if A ∈ GLn (Z) has no
eigenvalue on the unit circle, then the diffeomorphism f of the n-torus Tn = Rn /Zn , defined
by f (x) = Ax for all x ∈ Tn , is Anosov. Such a diffeomorphism is called a hyperbolic toral
automorphism.
In [17, Theorem 1.1], we obtained the following result.

34

TULLIO CECCHERINI-SILBERSTEIN AND MICHEL COORNAERT

Theorem 8.13. Let f be an Anosov diffeomorphism of the n-dimensional torus Tn . Then
the dynamical system (Tn , f ) has the Moore-Myhill property.
The proof given in [17] uses two classical results. The first one is the Franks-Manning
theorem [26], [37] which states that (Tn , f ) is topologically conjugate to a hyperbolic
toral automorphism. The second one is a result of Walters [55] which says that every
endomorphism of a hyperbolic toral automorphism is affine.
We do not know if the dynamical system (M, f ) has the Moore-Myhill property whenever
f is an Anosov diffeomorphism of a compact smooth manifold M. However, we have
obtained in [16, Theorem 1.1] the following result.
Theorem 8.14. Let X be a compact metrizable space equipped with a continuous action
of a countable amenable group G. Suppose that the dynamical system (X, G) is expansive
e ⊂ AG , and a uniformly
and that there exist a finite set A, a strongly irreducible subshift X
e → X. Then the dynamical system (X, G) has the Myhill
bounded-to-one factor map θ : X
property.
A homeomorphism f of a topological space X is called topologically mixing if, given
any two nonempty open subsets U, V ⊂ X, there exists an integer N ≥ 0 such that
f n (U) ∩ V 6= ∅ for all n ∈ Z that satisfy |n| ≥ N. By the classical work of Bowen (cf. [6,
Theorem 28 and Proposition 30] and [5, Proposition 10]), dynamical systems generated by
topologically mixing Anosov diffeomorphisms satisfy the hypotheses of Theorem 8.14. As a
consequence (cf. [17, Corollary 4.4]), we get the following partial extension of Theorem 8.13.

Corollary 8.15. Let f be a topologically mixing Anosov diffeomorphism of a compact
smooth manifold M. Then the dynamical system (M, f ) has the Myhill property.
Remark 8.16. All known examples of Anosov diffeomorphisms are topologically mixing.
Also, all compact smooth manifolds that are known to admit Anosov diffeomorphisms are
infra-nilmanifolds. We recal that a nilmanifold is a manifold of the form N/Γ, where N is
a simply-connected nilpotent Lie group and Γ is a discrete cocompact subgroup of N and
that a infra-nilmanifold is a manifold that is finitely covered by some nilmanifold.
8.6. Principal algebraic dynamical systems. An algebraic dynamical system is a dynamical system of the form (X, G), where X is a compact metrizable abelian topological
group and G is a countable group acting on X by continuous group morphisms. Note that
if (X, G) is an algebraic dynamical system, then, for each g ∈ G, the map x 7→ gx is a
continuous group automorphism of G with inverse x 7→ g −1 x.
Example 8.17. Let G be a countable group and A a compact metrizable topological
group (for example a finite discrete abelian group, or the n-dimensional torus Tn , or the
infinite-dimensional torus TN , or the group Zp of p-adic integers for some prime p). Then
the G-shift (AG , G) is an algebraic dynamical system.
Example 8.18. Let X be a compact metrizable abelian group and f : X → X a continuous
group automorphism (for example X = Tn and f ∈ GLn (Z)). Then the dynamical system
(X, f ) generated by f is an algebraic dynamical system.

THE GARDEN OF EDEN THEOREM: OLD AND NEW

35

Let (X, G) be an algebraic dynamical system.
If d is a metric on X that is compatible with the topology then a point x ∈ X is
homoclinic to 0X if and only if one has
lim d(gx, 0X ) = 0.

g→∞

The set ∆(X, G) consisting of all points of X that are homoclinic to 0X is an G-invariant
additive subgroup of X, called the homoclinic group of (X, G) (cf. [33]). Two points x, y ∈
X are homoclinic if and only if x − y ∈ ∆(X, G). It follows that the set of homoclinicity
classes of (X, G) can be identified with the quotient group X/∆(X, G).
b of X. We recall that if L is a locally compact
Consider now the Pontryagin dual X
b are the characters of L, i.e., the
abelian group, the elements of its Pontryagin dual L
b is
continuous group morphisms χ : L → T, where T := R/Z, and that the topology on L
the topology of uniform convergence on compact subsets. (see e.g. [41]). As the abelian
b is a discrete countable abelian group. There is also
group X is compact and metrizable, X
b
a natural dual action of G on X defined by
gχ(x) := χ(g −1 x)

b and x ∈ X. Note that χ 7→ gχ is a group automorphism of X
b for
for all g ∈ G, χ ∈ X,
each g ∈ G.
We recall that the integral group ring Z[G] of G consists of all formal series
X
r=
rg g,
g∈G

where rg ∈ Z for all g ∈ G and rg = 0 for all but finitely many g ∈ G, and the operations
on Z[G] are defined by the formulas
X
r+s=
(rg + sg )g,
g∈G

rs =

X

rg 1 sg 2 g 1 g 2

g1 ,g2 ∈G

for all
r=

X
g∈G

rg g,

s=

X
g∈G

sg g ∈ Z[G].

b extends to a left Z[G]-module structure on X.
b
By linearity, the action of G on X
Conversely, if M is a countable left Z[G]-module and we equip M with its discrete
c is a compact metrizable abelian group. The left
topology, then its Pontryagin dual M
Z[G]-module structure on M induces by restriction an action of G on M, and, by dualizing,
c by continuous group morphisms, so that (M
c, G) is an algebraic
we get an action of G on M
dynamical system.
Using the fact that every locally compact abelian group is isomorphic to its bidual,
one shows that Pontryagin duality yields a one-to-one correspondence between algebraic

36

TULLIO CECCHERINI-SILBERSTEIN AND MICHEL COORNAERT

dynamical systems with acting group G and countable left Z[G]-modules (see [48], [34],
[35]).
Let f ∈ Z[G] and consider the cyclic left Z[G]-module Mf := Z[G]/Z[G]f obtained
by quotienting the ring Z[G] by the principal left ideal generated by f . The algebraic
dynamical system associated by Pontryagin duality with Mf is denoted by (Xf , G) and is
called the principal algebraic dynamical system associated with f .
In [18], we obtained the following result.
Theorem 8.19. Let G be a countable abelian group and f ∈ Z[G]. Suppose that the
principal algebraic dynamical system (Xf , G) associated with f is expansive and that Xf is
connected. Then the dynamical system (Xf , G) satisfies the Moore-Myhill property.
The proof uses two main ingredients. The first one is a result of Lind and Schmidt [33]
which asserts that the homoclinic group of (Xf , G), equipped with the discrete topology
and the induced action of G, is conjugate to the Pontryagin dual Z[G]/Z[G]f of Xf . The
second is a rigidity result of Bhattacharya [4] according to which every endomorphism of
(Xf , G) is affine (see [18] for more details).
−1
In the case G = Zd , the group ring Z[G] can be identified with the ring Z[u1 , u−1
1 , . . . , ud , ud ]
of Laurent polynomials with integral coefficients on d commuting indeterminates.
Example 8.20. For G = Z and f = u2 − u − 1 ∈ Z[u, u−1 ] = Z[G], one can check that
the associated principal algebraic dynamical system (Xf , Z) is topologically conjugate to
Arnold’s cat on T2 (see e.g. [48, Example 2.18.(2)]). Thus, we recover from Theorem 8.19
that Arnold’s cat satisfies the Moore-Myhill property.
9. Some Additional topics
9.1. Infinite alphabets and uncountable groups. The notion of a subshift and that
of a cellular automaton between subshifts can be extended to the case where the alphabet
sets are infinite and the group is not countable.
More specifically, let G be a (possibly uncountable) group and A a (possibly infinite) set.
The prodiscrete topology on AG is the Q
product topology obtained by taking the discrete
topology on each factor A of AG = g∈G A. The prodiscrete topology on AG is not
metrizable as soon as G is uncountable and A contains more than one element. However,
this topology is induced by the prodiscrete uniform structure on AG , that is, the product
uniform structure on AG obtained by taking the discrete uniform structure on each factor
A of AG (see [12, Appendix B] for more details). A subset X ⊂ AG is called a subshift if
X is invariant under the shift action and closed for the prodiscrete topology.
Let G be a group and let A, B be sets. Suppose that X ⊂ AG and Y ⊂ B G are two subshifts. One defines cellular automata between X and Y exactly as in Definition 3.1. Every
cellular automaton τ : X → Y is continuous with respect to the topologies on X and Y
induced by the prodiscrete topologies on AG and B G . The converse is false in general [10,
Section 4], [12, Example 1.8.2]. However, the Curtis-Hedlund-Lyndon theorem (cf. Theorem 3.8) admits the following generalization [10, Theorem 1.1], [12, Theorem 1.8.1]: a
map τ : X → Y is a cellular automaton if and only if it is equivariant (with respect to the

THE GARDEN OF EDEN THEOREM: OLD AND NEW

37

G-shift actions) and uniformly continuous (for the uniform structures on X and Y induced
by the prodiscrete uniform structures on AG and B G ).
One can extend the notion of amenability defined only for countable groups in Section 5.1
by declaring that a general group G is amenable if all of its finitely generated subgroups
are amenable. This extension makes sense since every finitely generated group is countable
and every subgroup of a countable amenable group is itself amenable. The Garden of Eden
theorem (cf. Theorem 5.18) remains valid in this more general setting: if G is a (possibly
uncountable) amenable group, A a finite set, and τ : AG → AG a cellular automaton, then
τ : AG → AG is surjective if and only if it is pre-injective. The proof can be reduced to the
case when the group G is finitely generated (and hence countable) by using the operations
of restriction and induction for cellular automata (see [11] and [12, Section 1.7]). One
can also directly follow the proof given above for Theorem 5.18 by replacing the Følner
sequence by a Følner net (see [12, Theorem 5.8.1]).
9.2. Linear cellular automata. Let G be a group and let K be a field. Let A be a
finite-dimensional vector space over K and set d = dimK (A). Observe that A is infinite
as soon as the field K is infinite (e.g. K = R) and d 6= 0. Taking A as an alphabet, the
configuration set AG inherits a natural product vector space structure. The support of a
configuration x ∈ AG is the subset supp(x) := {g ∈ G : x(g) 6= 0} ⊂ G. Thus, x ∈ AG has
finite support if and only if it is almost equal to the constant zero-configuration. We denote
by A[G] ⊂ AG the vector subspace consisting of all configurations with finite support.
Recall that an involutive K-algebra is a K-algebra equipped with an involution that is
a K-algebra anti-automorphism.
The vector space K[G] has a natural additional structure of an involutive K-algebra.
The multiplication on K[G] is the convolution product defined by
X
X
α(g1)β(g2 ) =
α(h)β(h−1g)
(αβ)(g) :=
g1 ,g2 ∈G:
g1 g2 =g

h∈G

for all α, β ∈ K[G] and g ∈ G, and the involution is the map α 7→ α∗ given by
α∗ (g) := α(g −1)
for all α ∈ K[G] and g ∈ G. This involutive K-algebra is called the group algebra of the
group G with coefficients in K. Note that the group G embeds as a subgroup of the group
of invertible elements of K[G] via the map g 7→ δg , where δg ∈ K[G] is defined by δg (g) = 1
and δg (h) = 0 for all h ∈ G with h 6= g, and that G ⊂ K[G] is a base for the vector space
K[G].
The G-shift action on AG is clearly K-linear, so that it yields a left K[G]-module structure on AG . Observe that A[G] is a submodule of AG .
A linear cellular automaton over the group G and the alphabet A is a cellular automaton
τ : AG → AG that is K-linear with respect to the vector space structure on AG (if S is any
memory set for τ and µ : AS → A is the associated local defining map, this is equivalent
to requiring that µ is K-linear).

38

TULLIO CECCHERINI-SILBERSTEIN AND MICHEL COORNAERT

Let us denote by LCA(G; A) the vector space consisting of all linear cellular automata
τ : AG → AG .
Let τ ∈ LCA(G; A). Note that A[G] is stable under τ . Indeed, if S ⊂ G is a memory set
for τ , then supp(τ (x)) ⊂ supp(x)S −1 for all x ∈ AG ) (see [12, Proposition 8.2.3]). Moreover,
τ is pre-injective if and only if τ |A[G] : A[G] → A[G] is injective (cf. [12, Proposition 8.2.5]).
Observe also that τ is a K[G]-module endomorphism of AG and hence of A[G].
The vector space LCA(G; A) has a natural structure of a K-algebra with the composition
of maps as the multiplicative operation. Furthermore, the restriction map τ 7→ τ |A[G] yields
a K-algebra isomorphism from LCA(G; A) onto EndK[G] (A[G]), the endomorphism Kalgebra of the K[G]-module A[G] (cf. [12, Theorem 8.7.6]). It turns out that A[G] is a free
K[G]-module with rank d. Actually, if (ei )1≤i≤d is a base for the vector space A, then the
family (xi )1≤i≤d , where xi ∈ A[G] is the configuration defined by xi (1G ) = ei and xi (g) = 0
for g 6= 1G , is a free base for the K[G]-module A[G] (cf. [12, Proposition 8.7.3]). One
deduces that EndK[G](A[G]) is isomorphic, as a K-algebra, to the K-algebra Matd (K[G])
of d × d matrices with coefficients in the group algebra K[G]. It follows that LCA(G; A)
and Matd (K[G]) are isomorphic as K-algebras (cf. [12, Corollary 8.7.8]). For instance, the
map Φ : Matd (K[G]) → LCA(G; A), sending each matrix α = (αij )1≤i,j≤d ∈ Matd (K[G])
to the unique linear cellular automaton τ ∈ LCA(G; A) such that
X
∗
τ (xi ) =
αji
xj
1≤j≤d

for all 1 ≤ i ≤ d, is a K-algebra isomorphism.
The adjoint of a matrix α ∈ Matd (K[G]) is the matrix α∗ ∈ Matd (K[G]) given by
∗
∈ K[G] for all 1 ≤ i, j ≤ d. The involution α 7→ α∗ makes Matd (K[G])
(α∗ )ij := αji
into an involutive K-algebra. Let us transport this involution to LCA(G; A) via Φ. Thus,
LCA(G; A) becomes an involutive K-algebra with involution τ 7→ τ ∗ satisfying
X
τ ∗ (xi ) =
αij xj
1≤j≤d

for all 1 ≤ i ≤ d and τ = Φ(α) ∈ LCA(G; A). Note that this involution on LCA(G; A)
depends on the choice of a base for A.
Consider now the non-degenerate K-bilinear symmetric map A × A → K defined by
X
X
X
a·b=
ai bi for all a =
ai ei and b =
bi ei , with ai , bi ∈ K for 1 ≤ i ≤ d.
1≤i≤d

1≤i≤d

1≤i≤d

Then the K-bilinear map A[G] × AG → K, defined by
X
hx, yi :=
x(g) · y(g)
g∈G

for all x ∈ A[G] and y ∈ AG , is non-degenerate in both arguments. Given a linear cellular
automaton τ : AG → AG , Bartholdi [1] (see also [52]) observed that
hτ (x), yi = hx, τ ∗ (y)i

THE GARDEN OF EDEN THEOREM: OLD AND NEW

39

for all x ∈ A[G] and y ∈ AG , and used this to show that τ is pre-injective (resp. surjective)
if and only if τ ∗ is surjective (resp. pre-injective).
In [8] (see also [12, Theorem 8.9.6]) a linear version of the Garden of Eden theorem is
proved, namely that if G is amenable and τ ∈ LCA(G; A), then τ is surjective if and only
if it is pre-injective.
Let G be a nonamenable group. In [3, Theorem 1.1] Bartholdi showed that there exists a finite field K (in [1] he actually observed that the field K can be arbitrary), a
finite dimensional vector space A over K, and a pre-injective linear cellular automaton
τ ∈ LCA(G; A) which is not surjective. As a consequence ([1, Corollary]), the cellular
automaton τ ∗ ∈ LCA(G; A) is surjective but not pre-injective. These two facts, in combination with the linear version of the Garden of Eden theorem in [8], yield a characterization
of group amenability in terms of linear cellular automata.
The linear version of the Garden of Eden theorem has been extended in [13] to linear
cellular automata τ : X → X with X ⊂ AG a strongly irreducible linear subshift of finite
type, and in [9] to the case when the alphabet A is a semi-simple left-module of finite
length over a (possibly noncommutative) ring.
9.3. Gromov’s Garden of Eden theorem. In [30, Subsection 8.F’], Gromov proved a
Garden of Eden type theorem generalizing Theorem 5.18 under several aspects. First of
all, the alphabet set A is only assumed to be countable, not necessarily finite. In addition,
the universe is (the vertex set V of) a connected simplicial graph G = (V, E) of bounded
degree with a natural homogeneity condition (to admit a dense pseudogroup of partial
isometries). The classical case corresponds to G = C(G, S) being the Cayley graph of
a finitely generated group G with respect to a finite and symmetric generating subset
S ⊂ G \ {1G }. The dense pseudogroup of partial isometries is, in this particular case, given
by partial left-multiplication by group elements. In this more general setting, the category
corresponding to that of cellular automata consists now of the following:
• stable spaces, i.e. (stable) projective limits of locally-finite projective systems (XΩ )
of A-valued maps on (subsets of) V with a suitable finiteness and irreducibility
condition (bounded propagation) and admitting a dense holonomy (corresponding
to shift-invariance in the classical case) as objects, and
• maps of bounded propagation (this condition corresponds to continuity) admitting
a dense holonomy (this corresponds to G-equivariance), as morphisms.
The notion of a Følner sequence and of amenability for simplicial graphs, together with the
corresponding notion of entropy (for the above-mentioned spaces of A-valued maps), carry
verbatim from the group theoretical framework. All this said, Gromov’s theorem states as
follows.
Let G = (V.E) be an amenable simplicial connected graph of bounded degree admitting a
dense pseudogroup of partial isometries and let A be a finite or countably infinite alphabet
set. Suppose that X, Y ⊂ AV are stable spaces of bounded propagation with the same
entropy. Let τ : X → Y be a a map of bounded propagation admitting a dense holonomy.
Then τ is surjective if and only if it is pre-injective.

40

TULLIO CECCHERINI-SILBERSTEIN AND MICHEL COORNAERT

In [19, Lemma 3.11] it is shown that a stable space of bounded propagation is strongly
irreducible (cf. Section 7) and of finite type (cf. Section 2). However, as shown in [19,
Counterexample 3.13], the converse fails to hold: strong irreducibility and finite type conditions do not imply, in general, bounded propagation. As a consequence, the following
theorem (cf. [19, Theorem B]) improves on Gromov’s theorem.
Let G = (V.E) be an amenable simplicial connected graph of bounded degree admitting a
dense pseudogroup of partial isometries and let A be a finite or countably infinite alphabet
set. Suppose that X, Y ⊂ AV are strongly irreducible stable spaces of finite type with
the same entropy. Let τ : X → Y be a a map of bounded propagation admitting a dense
holonomy. Then τ is surjective if and only if it is pre-injective.
Note that this last result also covers Theorem 7.5.
9.4. Cellular automata over homogeneous sets. Cellular automata where the universe is a set endowed with a transitive group action have been investigated by Moriceau [40].
Versions of the Curtis-Hedlund-Lyndon theorem and of the Garden of Eden theorem in
this more general setting have been obtained by Wacker [53], [54].
Acknowledgements. We thank Laurent Bartholdi for valuable comments and remarks.
References
[1] L. Bartholdi, Linear cellular automata, duality and sofic groups, arXiv:1612.06117.
[2] L. Bartholdi, Gardens of Eden and amenability on cellular automata, J. Eur. Math. Soc. (JEMS),
12 (2010), pp. 241–248.
[3] L. Bartholdi and D. Kielak, Amenability of groups is characterized by Myhill’s theorem,
arXiv:1605.09133.
[4] S. Bhattacharya, Orbit equivalence and topological conjugacy of affine actions on compact abelian
groups, Monatsh. Math., 129 (2000), pp. 89–96.
[5] R. Bowen, Markov partitions and minimal sets for Axiom A diffeomorphisms, Amer. J. Math., 92
(1970), pp. 907–918.
[6]
, Markov partitions for Axiom A diffeomorphisms, Amer. J. Math., 92 (1970), pp. 725–747.
[7] M. Brin and G. Stuck, Introduction to dynamical systems, Cambridge University Press, Cambridge,
2002.
, The Garden of Eden theorem for linear cellular automata, Ergodic Theory Dynam. Systems,
[8]
26 (2006), pp. 53–68.
, Amenability and linear cellular automata over semisimple modules of finite length, Comm.
[9]
Algebra, 36 (2008), pp. 1320–1335.
[10]
, A generalization of the Curtis-Hedlund theorem, Theoret. Comput. Sci., 400 (2008), pp. 225–
229.
, Induction and restriction of cellular automata, Ergodic Theory Dynam. Systems, 29 (2009),
[11]
pp. 371–380.
, Cellular automata and groups, Springer Monographs in Mathematics, Springer-Verlag, Berlin,
[12]
2010.
, A Garden of Eden theorem for linear subshifts, Ergodic Theory Dynam. Systems, 32 (2012),
[13]
pp. 81–102.
[14]
, The Myhill property for strongly irreducible subshifts over amenable groups, Monatsh. Math.,
165 (2012), pp. 155–172.

THE GARDEN OF EDEN THEOREM: OLD AND NEW

[15]
[16]
[17]
[18]
[19]

[20]
[21]
[22]
[23]
[24]
[25]
[26]
[27]
[28]
[29]
[30]
[31]
[32]
[33]
[34]
[35]
[36]
[37]
[38]
[39]
[40]

41

, Surjunctivity and reversibility of cellular automata over concrete categories, in Trends in harmonic analysis, vol. 3 of Springer INdAM Ser., Springer, Milan, 2013, pp. 91–133.
, Expansive actions of countable amenable groups, homoclinic pairs, and the Myhill property,
Illinois J. Math., 59 (2015), pp. 597–621.
, A garden of Eden theorem for Anosov diffeomorphisms on tori, Topology Appl., 212 (2016),
pp. 49–56.
T. Ceccherini-Silberstein and M. Coornaert, A Garden of Eden theorem for principal algebraic
actions, preprint 2017. arXiv:1706.06548.
T. Ceccherini-Silberstein, F. Fiorenzi, and F. Scarabotti, The Garden of Eden theorem for
cellular automata and for symbolic dynamical systems, in Random walks and geometry, Walter de
Gruyter, Berlin, 2004, pp. 73–108.
T. Ceccherini-Silberstein, A. Machı̀, and F. Scarabotti, Amenable groups and cellular automata, Ann. Inst. Fourier (Grenoble), 49 (1999), pp. 673–685.
M. Coornaert, Topological dimension and dynamical systems, Universitext, Springer, Cham, 2015.
Translated and revised from the 2005 French original.
M. M. Day, Amenable semigroups, Illinois J. Math., 1 (1957), pp. 509–544.
P. de la Harpe, Topics in geometric group theory, Chicago Lectures in Mathematics, University of
Chicago Press, Chicago, IL, 2000.
F. Fiorenzi, The Garden of Eden theorem for sofic shifts, Pure Math. Appl., 11 (2000), pp. 471–484.
, Cellular automata and strongly irreducible shifts of finite type, Theoret. Comput. Sci., 299
(2003), pp. 477–493.
J. Franks, Anosov diffeomorphisms, in Global Analysis (Proc. Sympos. Pure Math., Vol. XIV,
Berkeley, Calif., 1968), Amer. Math. Soc., Providence, R.I., 1970, pp. 61–93.
F. P. Greenleaf, Invariant means on topological groups and their applications, Van Nostrand Mathematical Studies, No. 16, Van Nostrand Reinhold Co., New York, 1969.
R. I. Grigorchuk, Degrees of growth of finitely generated groups and the theory of invariant means,
Izv. Akad. Nauk SSSR Ser. Mat., 48 (1984), pp. 939–985.
M. Gromov, Groups of polynomial growth and expanding maps, Inst. Hautes Études Sci. Publ. Math.,
(1981), pp. 53–73.
, Endomorphisms of symbolic algebraic varieties, J. Eur. Math. Soc. (JEMS), 1 (1999), pp. 109–
197.
G. A. Hedlund, Endomorphisms and automorphisms of the shift dynamical system, Math. Systems
Theory, 3 (1969), pp. 320–375.
D. Lind and B. Marcus, An introduction to symbolic dynamics and coding, Cambridge University
Press, Cambridge, 1995.
D. Lind and K. Schmidt, Homoclinic points of algebraic Zd -actions, J. Amer. Math. Soc., 12 (1999),
pp. 953–980.
, Symbolic and algebraic dynamical systems, in Handbook of dynamical systems, Vol. 1A, NorthHolland, Amsterdam, 2002, pp. 765–812.
D. Lind and K. Shmidt, A survey of algebraic actions of the discrete Heisenberg group, Uspekhi
Mat. Nauk, 70 (2015), pp. 77–142.
A. Machı̀ and F. Mignosi, Garden of Eden configurations for cellular automata on Cayley graphs
of groups, SIAM J. Discrete Math., 6 (1993), pp. 44–56.
A. Manning, There are no new Anosov diffeomorphisms on tori, Amer. J. Math., 96 (1974), pp. 422–
429.
J. Milnor, A note on curvature and fundamental group, J. Differential Geometry, 2 (1968), pp. 1–7.
E. F. Moore, Machine models of self-reproduction, vol. 14 of Proc. Symp. Appl. Math., American
Mathematical Society, Providence, 1963, pp. 17–34.
S. Moriceau, Cellular automata on a G-set, J. Cell. Autom., 6 (2011), pp. 461–486.

42

TULLIO CECCHERINI-SILBERSTEIN AND MICHEL COORNAERT

[41] S. A. Morris, Pontryagin duality and the structure of locally compact abelian groups, Cambridge
University Press, Cambridge-New York-Melbourne, 1977. London Mathematical Society Lecture Note
Series, No. 29.
[42] D. E. Muller, Unpublished class notes, university of illinois, (1976).
[43] J. Myhill, The converse of Moore’s Garden-of-Eden theorem, Proc. Amer. Math. Soc., 14 (1963),
pp. 685–686.
[44] J. von Neumann, Zur allgemeinen theorie des Masses, Fund. Math., 13 (1929), pp. 73–116.
[45] A. J. Ol′ šanskiı̆, On the question of the existence of an invariant mean on a group, Uspekhi Mat.
Nauk, 35 (1980), pp. 199–200.
[46] D. S. Ornstein and B. Weiss, Entropy and isomorphism theorems for actions of amenable groups,
J. Analyse Math., 48 (1987), pp. 1–141.
[47] A. L. T. Paterson, Amenability, vol. 29 of Mathematical Surveys and Monographs, American
Mathematical Society, Providence, RI, 1988.
[48] K. Schmidt, Dynamical systems of algebraic origin, vol. 128 of Progress in Mathematics, Birkhäuser
Verlag, Basel, 1995.
[49] P. E. Schupp, Arrays, automata and groups—some interconnections, in Automata networks (ArgelèsVillage, 1986), vol. 316 of Lecture Notes in Comput. Sci., Springer, Berlin, 1988, pp. 19–28.
[50] M. Shub, Global stability of dynamical systems, Springer-Verlag, New York, 1987. With the collaboration of A. Fathi and R. Langevin, Translated from the French by Joseph Christy.
[51] S. Smale, Differentiable dynamical systems, Bull. Amer. Math. Soc., 73 (1967), pp. 747–817.
[52] M. C. H. Tointon, Characterizations of algebraic properties of groups in terms of harmonic functions, Groups Geom. Dyn., 10 (2016), pp. 1007–1049.
[53] S. Wacker, Cellular automata on group sets and the uniform Curtis-Hedlund-Lyndon theorem, in
Cellular automata and discrete complex systems, vol. 9664 of Lecture Notes in Comput. Sci., Springer,
[Cham], 2016, pp. 185–198.
, The Garden of Eden theorem for cellular automata on group sets, in Cellular automata, vol. 9863
[54]
of Lecture Notes in Comput. Sci., Springer, [Cham], 2016, pp. 66–78.
[55] P. Walters, Topological conjugacy of affine transformations of tori, Trans. Amer. Math. Soc., 131
(1968), pp. 40–50.
[56] S. Wolfram, A new kind of science, Wolfram Media, Inc., Champaign, IL, 2002.
Added in proof
Recently, after our preprint [18] had circulated, Hanfeng Li posted his paper [60] containing an
impressive Garden of Eden type theorem generalizing several results mentioned above in our survey.
The key notion in Li’s paper is that of specification, a strong orbit tracing property which was introduced by Rufus Bowen for Z-actions in relation to his studies on Axiom A diffeomorphisms in [57]
(see also [59, Definition 21.1]) and was extended to Zd -actions by Ruelle in [61]. Several versions and
generalizations of specification have appeared in the literature (see, in particular, [33, Definition 5.1]
and [58, Definition 6.1]). Here is the one we need (cf. [58, Definition 6.1]).
Definition 9.1. A dynamical system (X, G) has the weak specification property if for any ε > 0 there
exists a nonempty symmetric finite subset ∆ ⊂ G satisfying the following property: if (Ωi )i∈I is any
finite family of finite subsets of G such that ∆Ωi ∩ Ωj = ∅ for all distinct i, j ∈ I, and (xi )i∈I is any
family of points in X, then there exists x ∈ X such that
d(sx, sxi ) ≤ ε for all i ∈ I and s ∈ Ωi ,
where d is any metric compatible with the topology on X.
It is straightforward (cf. [60, Proposition A.1]) to check that is G is a countable group, A is a finite
alphabet set, and X ⊂ AG is a subshift, then the shift dynamical system (X, G) has the weak

THE GARDEN OF EDEN THEOREM: OLD AND NEW

43

specification property if and only if it is strongly irreducible (cf. Section 7). Also, it is easy to see that
the weak specification property passes to factors.
Li [60, Theorem 1.1] proved the following:
Theorem 9.2. Let (X, G) be a dynamical system. Suppose that the group G is amenable and that
(X, G) is expansive and has the weak specification property. Then (X, G) has the Myhill property.
Note that Theorem 9.2 covers Theorem 8.14, by virtue of the remarks following Definition 9.1.
Recall (cf. Example 7.9) that if X ⊂ {0, 1}Z denotes the even subshift (cf. Example 2.4), then (X, Z)
is expansive, has the weak specification property (since X is strongly irreducible), but does not have
the Moore property. This shows that from the hypotheses of Theorem 9.2 one cannot deduce the
Moore property, in general. However, Li [60, Theorem 1.2] proved that when restricting to the class of
algebraic dynamical systems (cf. Section 8.6) with amenable acting group, the Moore property follows
from expansiveness and weak specification:
Theorem 9.3. Let (X, G) be an algebraic dynamical system. Suppose that the group G is amenable
and that (X, G) is expansive and has the weak specification property. Then (X, G) has the Moore
property.
As an immediate consequence of Theorems 9.2 and 9.3, one deduces the following (cf. [60, Theorem
1.3]):
Corollary 9.4. Let (X, G) be an algebraic dynamical system. Suppose that the group G is amenable
and that (X, G) is expansive and has the weak specification property. Then (X, G) has the Moore-Myhill
property.
Moreover, since (cf. [60, Lemma 2.1], see also [58, Theorem 1.2]) every expansive principal algebraic
action has the weak specification property, one immediately deduces (cf. [60, Theorem 1.3]):
Corollary 9.5. Let (X, G) be a principal algebraic dynamical system. Suppose that the group G is
amenable and that (X, G) is expansive. Then (X, G) has the Moore-Myhill property.
Note that Corollary 9.5 covers Theorem 8.19 (since every abelian group is amenable and no
assumption on connectedness of the phase space is required).
Additional references
[57] R. Bowen, Periodic points and measures for Axiom A diffeomorphisms, Trans. Amer. Math. Soc.,
154 (1971), pp. 377–397.
[58] N. Chung and H. Li, Homoclinic groups, IE groups, and expansive algebraic actions, Invent. Math.,
199 (2015), no.3, pp. 805-858.
[59] M. Denker, Ch. Grillenberger, and K. Sigmund, Ergodic theory on compact spaces. Lecture
Notes in Mathematics, Vol. 527. Springer-Verlag, Berlin-New York, 1976.
[60] H. Li, Garden of Eden and specification, preprint 2017. arXiv:1708.09012.
[61] D. Ruelle, Statistical mechanics on a compact set with Z ν action satisfying expansiveness and
specification, Trans. Amer. Math. Soc., 187 (1971), pp. 237–251.
Dipartimento di Ingegneria, Università del Sannio, C.so Garibaldi 107, 82100 Benevento, Italy
E-mail address: tullio.cs@sbai.uniroma1.it
Université de Strasbourg, CNRS, IRMA UMR 7501, F-67000 Strasbourg, France
E-mail address: michel.coornaert@math.unistra.fr

