ON THE GARDEN OF EDEN THEOREM FOR ENDOMORPHISMS OF
SYMBOLIC ALGEBRAIC VARIETIES

arXiv:1803.08906v1 [math.DS] 23 Mar 2018

TULLIO CECCHERINI-SILBERSTEIN, MICHEL COORNAERT, AND XUAN KIEN PHUNG
Abstract. Let G be an amenable group and let X be an irreducible complete algebraic
variety over an algebraically closed field K. Let A denote the set of K-points of X and
let τ : AG → AG be an algebraic cellular automaton over (G, X, K), that is, a cellular
automaton over the group G and the alphabet A whose local defining map is induced
by a morphism of K-algebraic varieties. We introduce a weak notion of pre-injectivity
for algebraic cellular automata, namely (∗)-pre-injectivity, and prove that τ is surjective
if and only if it is (∗)-pre-injective. In particular, τ has the Myhill property, i.e., is
surjective whenever it is pre-injective. Our result gives a positive answer to a question
raised by Gromov in [8] and yields an analogue of the classical Moore-Myhill Garden of
Eden theorem.

Contents
1. Introduction
2. Background material and preliminary results
3. Algebraic cellular automata
4. Algebraic mean dimension
5. Algebraic mean dimension and surjectivity
6. Algebraic mean dimension and weak pre-injectivity
7. Main results
8. Counterexamples
9. Questions
References

1
5
13
16
17
19
26
27
32
32

1. Introduction
In [8], Gromov brought out fascinating connections between algebraic geometry and
symbolic dynamics. At the end of [8], he asked the following:
Date: March 26, 2018.
2010 Mathematics Subject Classification. 37B15, 14A10, 14A15, 37B10, 43A07, 68Q80.
Key words and phrases. algebraic cellular automaton, complete algebraic variety, amenable group, Krull
dimension, algebraic mean dimension, pre-injectivity, Garden of Eden theorem.
1

2

T.CECCHERINI-SILBERSTEIN, M.COORNAERT, AND X.K.PHUNG

8.J. Question. Does the Garden of Eden theorem generalize to the proalgebraic category? First, one asks if pre-injective =⇒ surjective, while the
reverse implication needs further modification of definitions.
Our goal here is to present some positive answers to Gromov’s question. Before stating our
main results, we need to recall a few facts related to the classical Garden of Eden theorem,
symbolic dynamics, and algebraic geometry (see Section 2 for more details and references).
Fix a set A, called the alphabet, and a group G, called the universe. The set AG :=
{c : G → A}, consisting of all maps from G to A, is called the set of configurations. Equip
AG with the G-shift, i.e., the action of G defined by the map G × AG → AG , (g, c) 7→ gc,
where (gc)(h) := c(g −1h) for all g, h ∈ G and c ∈ AG .
Given a configuration c ∈ AG and a subset Ω ⊂ G, we write c|Ω for the restriction of c
to Ω, i.e., the element c|Ω ∈ AΩ defined by c|Ω (g) := c(g) for all g ∈ Ω.
A cellular automaton over the group G and the alphabet A is a map τ : AG → AG
satisfying the following property: there exist a finite subset M ⊂ G and a map µ : AM → A
such that
(1.1)

(τ (c))(g) = µ((g −1c)|M ) for all c ∈ AG and g ∈ G.

Such a set M is then called a memory set of τ and µ is called the associated local defining
map (see [4]). Note that it immediately follows from (1.1) that every cellular automaton
τ : AG → AG is G-equivariant, i.e., satisfies τ (gc) = gτ (c) for all c ∈ AG and g ∈ G, and
continuous with respect to the prodiscrete topology, that is, the product topology on AG
obtained by taking the discrete topology on each factor A of AG .
Two configurations c1 , c2 ∈ AG are said to be almost equal if the set {g ∈ G : c1 (g) 6=
c2 (g)} is finite. A cellular automaton τ : AG → AG is called pre-injective if τ (c1 ) = τ (c2 )
implies c1 = c2 whenever c1 , c2 ∈ AG are almost equal.
In 1963, Myhill [17] proved that if A is a finite set and G = Zd (d ∈ N), then every
pre-injective cellular automaton τ : AG → AG is surjective. Together with the converse
implication, which had been established shortly before by Moore [16], this yields the celebrated Garden of Eden theorem of Moore and Myhill stating that a cellular automaton
with finite alphabet over the group Zd is pre-injective if and only if it is surjective. The
Garden of Eden theorem was subsequently extended to cellular automata with finite alphabet over amenable groups in [6]. There is also a linear version of the Garden of Eden
theorem. More precisely, it is shown in [3] (see also [4, Theorem 8.9.6]) that if A is a
finite-dimensional vector space over a field K and G is an amenable group, then a K-linear
cellular automaton τ : AG → AG is pre-injective if and only if it is surjective.
Consider now an algebraic variety X over a field K, i.e., a scheme of finite type over
K, and let A := X(K) denote the set of K-points of X, that is, the set consisting of all
K-scheme morphisms Spec(K) → X. We say that a cellular automaton τ : AG → AG is
an algebraic cellular automaton over (G, X, K) if τ admits a memory set M with local
defining map µ : AM → A such that µ is induced by some K-scheme morphism f : X M →
X, where X M denotes the K-fibered product of a family of copies of X indexed by M
(cf. Definition 1.1 in [5]).

ON THE GARDEN OF EDEN THEOREM

3

In the present paper, we shall first establish a version of the Myhill part of the Garden
of Eden theorem for certain algebraic cellular automata. This yields a positive answer to
the first part of Gromov’s question. More specifically, we shall prove the following result
(cf. Theorem 7.1 for a more general statement).
Theorem 1.1. Let G be an amenable group and let X be an irreducible complete algebraic
variety over an algebraically closed field K. Let A := X(K) denote the set of K-points of
X. Then every pre-injective algebraic cellular automaton τ : AG → AG over (G, X, K) is
surjective.
As injectivity trivially implies pre-injectivity, an immediate consequence of Theorem 1.1
is the following.
Corollary 1.2. Let X be an irreducible complete algebraic variety over an algebraically
closed field K and let G be an amenable group. Let A := X(K) denote the set of K-points
of X. Then every injective algebraic cellular automaton τ : AG → AG over (G, X, K) is
surjective.
It is shown in [5, Theorem 1.2] that if X is a complete (possibly not irreducible) algebraic
variety over an algebraically closed field K and G is a locally residually finite group,
then every injective algebraic cellular automaton over (G, X, K) is surjective. Therefore,
Corollary 1.2 remains true if the hypothesis that G is amenable is replaced by the hypothesis
that G is locally residually finite. We shall see in Example 8.5 that if G is a free group
on two generators, then, given any algebraically closed field K, there exist an irreducible
complete K-algebraic variety X and an algebraic cellular automaton over (G, X, K) that
is pre-injective but not surjective. As a free group on two generators is residually finite,
we deduce that Theorem 1.1 becomes false if amenable is replaced by residually finite in
its hypotheses.
Let us note that, as implicitly stated in Gromov’s question, the converse implication, i.e.,
the analogue of the Moore implication, does not hold under the hypotheses of Theorem 1.1.
For example, if K is an algebraically closed field whose characteristic is not equal to 2,
the projective line P1K is an irreducible complete K-algebraic variety and the morphism
f : P1K → P1K given by (x : y) 7→ (x2 : y 2 ) is surjective but not injective. Taking A :=
P1K (K), we deduce that, for any group G, the map τ : AG → AG defined by (τ (c))(g) :=
f (c(g)) for all c ∈ AG and g ∈ G, is an algebraic cellular automaton over (G, X, K) that is
surjective but not pre-injective.
In order to formulate a version of the Garden of Eden theorem for algebraic cellular
automata, we introduce a weak notion of pre-injectivity for them, namely (∗)-pre-injectivity
(see Definition 6.1 below). We shall prove that Theorem 1.1 remains valid if we replace
the hypothesis that τ is pre-injective by the weaker hypothesis that τ is (∗)-pre-injective.
This weak form of pre-injectivity also allows us to establish a version of the Moore part of
the Garden of Eden theorem for algebraic cellular automata.
Theorem 1.3. Let G be an amenable group and let X be an irreducible algebraic variety
over an algebraically closed field K. Let A := X(K) denote the set of K-points of X.

4

T.CECCHERINI-SILBERSTEIN, M.COORNAERT, AND X.K.PHUNG

Then every surjective algebraic cellular automaton τ : AG → AG over (G, X, K) is (∗)-preinjective.
Note that X is not assumed to be complete in Theorem 1.3. Combining these results, we
obtain the following version of the Garden of Eden theorem (see Theorem 7.1) for algebraic
cellular automata.
Theorem 1.4. Let G be an amenable group and let X be an irreducible complete algebraic
variety over an algebraically closed field K. Let A := X(K) denote the set of K-points
of X and let τ : AG → AG be an algebraic cellular automaton over (G, X, K). Then the
following conditions are equivalent:
(a) τ is surjective;
(b) τ is (∗)-pre-injective.
The paper is organized as follows. The next section collects background material on
algebraic varieties and amenable groups. Section 3 contains some preliminary results on
algebraic cellular automata. In Section 4, we introduce the algebraic mean dimension
mdimF (Γ) of a subset Γ ⊂ AG , where G is an amenable group equipped with a Følner
net F and A is the set of K-points of an algebraic variety X over an algebraically closed
field K. The definition of algebraic mean dimension is anologous to that of topological
entropy. Here mdimF (Γ) is obtained as a limit of the average Krull dimension of the
projection of Γ along the Følner net. It follows in particular that mdimF (Γ) is always
bounded above by the dimension of the variety X and equality holds if Γ = AG . In
Section 5, we prove that if X is irreducible and complete, then τ is surjective if and only if
its image has maximal algebraic mean dimension (Theorem 5.4). In Section 6, we introduce
the notions of (∗)-pre-injectivity and (∗∗)-pre-injectivity, which are both implied by preinjectivity. In the trivial case when A is finite, that is, X is 0-dimensional, every cellular
automaton τ : AG → AG is algebraic over (G, X, K) and (∗)-pre-injectivity is equivalent to
pre-injectivity (cf. Example 8.1). We show that if X is irreducible and complete, then τ is
(∗)-pre-injective if and only if it is (∗∗)-pre-injective (see Assertion (iii) in Proposition 6.4).
We also establish relations between (∗)-pre-injectivity, (∗∗)-pre-injectivity, and the fact
that the image of τ has maximal algebraic mean dimension. In Section 7, we combine the
results of the two previous sections to obtain Theorem 1.3 and Theorem 7.1, which extends
Theorem 1.1 as well as Theorem 1.4. Another result in this section says that, under suitable
conditions, the surjectivity of an algebraic cellular automaton, provided it is defined over
an amenable group and an algebraically closed field, is a property that is invariant under
base change of the ground field (Theorem 7.2). Several counterexamples are presented in
Section 8 showing that the hypotheses in our results are reasonably optimal. Some open
questions are formulated in the final section.
Let G be an amenable group with a Følner net F . Let X be an algebraic variety over an
algebraically closed field K. Let A := X(K) and suppose that τ : AG → AG is an algebraic
cellular automaton over (G, X, K). We can summarize our results in the following diagram

ON THE GARDEN OF EDEN THEOREM

5

relating the various properties of the algebraic cellular automaton τ :
Surjectivity
Prop. 4.2.(i)

X irred., complete (Thm. 5.4)

mdimF (τ (AG )) = dim(A)

X irred. (Prop. 6.6)

Prop. 6.5
X irred., complete (Prop. 6.4.(iii))

(∗∗)-pre-injectivity

(∗)-pre-injectivity
X irred. (Prop. 6.4.(ii))

Prop. 6.4.(i)
Prop. 6.4.(i)

Pre-injectivity

X finite (Ex. 8.1)

Injectivity

2. Background material and preliminary results
2.1. Krull dimension and Jacobson spaces. Let X be a topological space. Given a
subset Y ⊂ X, we denote by Y the closure of Y in X.
A point x ∈ X is said to be a closed (respectively, generic) point of X if {x} = {x}
(respectively, {x} = X).
One says that X is irreducible if every non-empty open subset of X is dense in X. This
amounts to saying that if X = Y ∪ Z, where Y and Z are closed subsets of Y , then X = Y
or X = Z.
A subset Y ⊂ X is called an irreducible component of X if Y is irreducible (for the
induced topology) and maximal for inclusion among all irreducible subsets of X. As the
closure of an irreducible subset of X is irreducible, every irreducible component of X is
closed in X. By Zorn’s lemma, every irreducible subset of X is contained in some irreducible
component of X. Since every singleton of X is irreducible, it follows that X is the union
of its irreducible components.
The topological space X is called Noetherian if every descending chain of closed subsets
of X is stationary. Every subset of a Noetherian topological space is Noetherian for the
induced topology. If X is Noetherian, then X is quasi-compact and admits only finitely
many irreducible components.

6

T.CECCHERINI-SILBERSTEIN, M.COORNAERT, AND X.K.PHUNG

The Krull dimension of X, denoted by dim(X), is defined as being the supremum of the
lengths of all the strictly ascending chains of closed irreducible subsets of X.
Proposition 2.1. Let X be a topological space. Then the following hold:
(i) if Y is a subset of X, then dim(Y ) ≤ dim(X);
(ii) if X is irreducible with dim(X) < ∞ and Y is a closed subset of X such that dim(Y ) =
dim(X), then one has Y = X;
(iii) if (Uλ )λ∈Λ is an open cover of X, then one has dim(X) = supλ∈Λ dim(Uλ );
(iv) one has dim(X) = supY ∈C(X) dim(Y ), where C(X) denotes the set of all irreducible
components of X;
(v) if X is the union of a finite family (Zi )i∈I of closed irreducible subsets of X, then
every irreducible component of X is equal to one of the Zi and one has dim(X) =
maxi∈I dim(Zi ).
Proof. For (i), (ii), (iii), and (iv), see [7, Lemma 5.7]. Assertion (v) follows from [15,
Proposition 2.4.5.(c)] and Assertion (iii).

A subset Y of a topological space X is said to be very dense in X if F ∩ Y is dense in
F for every closed subset F of X.
Proposition 2.2. Suppose that Y is a very dense subset of a topological space X. Then
one has dim(X) = dim(Y ).
Proof. By Proposition 2.1, it suffices to prove that dim(X) ≤ dim(Y ). We first observe
that if F and F ′ are closed subsets of X such that F ∩ Y = F ′ ∩ Y , then F = F ′ since Y
is very dense in X. Note also that F ∩ Y is irreducible for every closed irreducible subset
F of X. Thus, if F0 ⊂ F1 ⊂ · · · ⊂ Fn is a strictly ascending chain of closed irreducible
subsets of X, then F0 ∩ Y ⊂ F1 ∩ Y ⊂ · · · ⊂ Fn ∩ Y is a strictly ascending chain of closed
irreducible subsets of Y . It follows that dim(X) ≤ dim(Y ).

Let X be a topological space. We denote by X0 the set of closed points of X. One
says that the topological space X is Jacobson if X0 is very dense in X. From the result of
Proposition 2.2, we immediately deduce the following.
Corollary 2.3. Let X be a Jacobson space. Then one has dim(X) = dim(X0 ).
A subset of a topological space X is said to be locally closed if it is the intersection of
an open subset and a closed subset of X. A subset of X is called constructible if it is a
finite union of locally closed subsets of X. The set of constructible subsets of X is closed
under finite union, finite intersection, and set difference. Every constructible subset C ⊂ X
contains a dense open subset of C (see [1, Lemma 2.1]).
Proposition 2.4. Let X be a Jacobson topological space and let C be a constructible subset
of X. Then the following hold:
(i) C is Jacobson;
(ii) C0 = C ∩ X0 ;
(iii) dim(C) = dim(C0 ) = dim(C0 ∩ X0 ).

ON THE GARDEN OF EDEN THEOREM

7

Proof. See e.g. [5, Lemma 2.2] for the proof of (i) and (ii). Assertion (iii) follows from (i),
(ii), and Corollary 2.3.

As immediate consequences of the preceding proposition, we get the following.
Corollary 2.5. Let X be a Jacobson space. Then the map C 7→ C ∩ X0 yields a bijection
from the set of constructible subsets of X onto the set of constructible subsets of X0 .
Moreover, this map preserves Krull dimension.
Corollary 2.6. Let X be a Jacobson space. Then X is irreducible if and only if X0 is
irreducible.
2.2. Schemes and algebraic varieties. In this subsection, we collect all the material
about schemes and algebraic varieties that we shall need in the present paper (see [7], [10],
[11], [13], [14], [15], [18] for more details). All rings are commutative with 1. We recall
that a scheme is a locally ringed space, that is, a topological space endowed with a sheaf of
rings such that the stalk at each point is a local ring. Following a common abuse, if there
is no risk of confusion, we shall use the same symbol to denote a scheme and its underlying
topological space. The topology on the underlying topological space of a scheme is called
the Zariski topology.
Every scheme X is sobre, i.e., the map x 7→ {x} yields a bijection from X onto the set of
non-empty closed irreducible subsets of X (see e.g. Proposition 3.23 in [7]). In particular,
every non-empty closed irreducible subset of a scheme X admits a unique generic point. A
scheme is called irreducible (respectively, Jacobson) if its underlying topological space is
irreducible (respectively, Jacobson). The Krull dimension dim(X) of a scheme X is define
as being the dimension of its underlying topological space.
The spectrum of a ring R is a scheme whose underlying set consists of all prime ideals of
R. The spectrum of a ring R is denoted by Spec(R) or simply R when there is no risk of
confusion. The Krull dimension dim(R) of a ring R is the Krull dimension of its spectrum.
It is equal to the supremum of the lengths of all the strictly ascending chains of prime
ideals of R.
A scheme X is called Noetherian if the space X admits a finite affine open cover (Ui )i∈I
such that, for each i ∈ I, one has Ui = Spec(Ri ), where Ri is a Noetherian ring. The
underlying topological space of every Noetherian scheme is Noetherian. However, there
are schemes that are not Noetherian although their underlying topological spaces are Noetherian.
Let K be a field. An algebraic variety over K (or K-algebraic variety) is a scheme of
finite type over K.
Given an algebraic variety X over a field K, the set of K-points of X is the set X(K)
consisting of all K-scheme morphisms Spec(K) → X.
Proposition 2.7. Let X be an algebraic variety over an algebraically closed field K. Then
the map from X(K) into X, that sends each f ∈ X(K) to the image by f of the unique
point of Spec(K), yields a bijection from X(K) onto the set X0 ⊂ X consisting of all closed
points of X.

8

T.CECCHERINI-SILBERSTEIN, M.COORNAERT, AND X.K.PHUNG

Proof. See [12, Corollaire 6.4.2].



Remark 2.8. Proposition 2.7 allows us, in the case when X is an algebraic variety over
an algebraically closed field K, to identify X(K) with X0 .
Proposition 2.9. Let X be an algebraic variety over a field K. Let C and D be constructible subsets of X. Then the following hold:
(i) the scheme X is Noetherian;
(ii) X is Jacobson;
(iii) dim(X0 ) = dim(X) < ∞;
(iv) C is Jacobson;
(v) C0 = C ∩ X0 ;
(vi) dim(C0 ) = dim(C) = dim(C);
(vii) if C ⊂ D then C0 ⊂ D0 .
Proof. Assertions (i) and (ii) follow for instance from Assertions (i) and (iii) in [5, Lemma 3.4].
Since X is Jacobson, we have that dim(X0 ) = dim(X) by Corollary 2.3. To prove that
dim(X) < ∞, as every scheme is locally affine, we can assume, by virtue of Proposition 2.1.(iii), that X is affine. Then X = Spec(R) for some finitely generated K-algebra
R. By the Noether normalization lemma, there exist an integer d ≥ 0 and an injective
K-algebra morphism K[t1 , . . . , td ] → R such that R is a finitely generated K[t1 , . . . , td ]module. This implies dim(X) = dim(R) = d < ∞ (see [7, Corollary 5.17]) and completes
the proof of (iii).
Assertions (iv) and (v) follow from (i) and Proposition 2.4.
From (i) and Proposition 2.4.(iii), we deduce that dim(C ∩ X0 ) = dim(C). Thus, to
complete the proof of (vi), it remains only to show that dim(C) = dim(C). To see this,
we first observe that C contains an open dense subset U of C since C is constructible. Let
us equip C ⊂ X with its induced reduced closed subscheme structure. Then U is an open
subscheme of C and both C and U are K-algebraic varieties. Since U is Noetherian, it
admits finitely many irreducible components. Let x1 , . . . , xn denote the generic points of
the irreducible components of U and consider their closures {x1 }, . . . , {xn } in X, equipped
with their
S induced reduced closed subscheme structure. As U is dense in C, we have that
C = 1≤i≤n {xi }. Since each {xi } is a closed irreducible subset of C, we deduce from
Proposition 2.1.(v) that
(2.1)

dim(C) = max dim({xi }).
1≤i≤n

Now observe that, for all 1 ≤ i ≤ n, the set U ∩ {xi } is an open subset of {xi } that is
non-empty since xi ∈ U. Hence, Theorem 5.22.(3) in [7] applied to the irreducible algebraic
varieties {xi } implies that
(2.2)

dim({xi }) = dim(U ∩ {xi }) ≤ dim(U),

where the last inequality follows from Proposition 2.1.(i). We deduce from (2.1), (2.2),
and Proposition 2.1.(i) that dim(C) ≤ dim(U) ≤ dim(C). As dim(C) ≤ dim(C) by

ON THE GARDEN OF EDEN THEOREM

9

Proposition 2.1.(i), we conclude that
(2.3)

dim(U) = dim(C) = dim(C).

This completes the proof of (vi).
Assertion (vii) is an immediate consequence of (v).



Proposition 2.10. Let X and Y be algebraic varieties over a field K and let f : X → Y
be a K-scheme morphism. Let C be a constructible subset of X. Then the following hold:
(i) f (C) is a constructible subset of Y ;
(ii) f (C0 ) = (f (C))0 ;
(iii) dim(f (C)) ≤ dim(C);
(iv) f (X0 ) ⊂ Y0 ;
(v) dim(f (X)) ≤ dim(X);
(vi) if E is a constructible subset of X0 , then f (E) is a constructible subset of Y0 and one
has dim(f (E)) ≤ dim(E).
Proof. Assertion (i) is Chevalley’s theorem (see e.g. [10, Théorème 1.8.4], [14, p. 93], [18,
Theorem 7.4.2]).
For (ii), see e.g. [5, Lemma 3.6.(v)].
To prove (iii), first observe that D := f (C) is a constructible subset of Y by (i). Therefore
D contains a dense open subset V of D. Let y1 , . . . , ym denote the generic points of the
irreducible components of V (see the proof of Proposition 2.9.(vi)). As V ⊂ D, there
exist points x1 , . . . , xm ∈ C such that f (xi ) = yi for 1 ≤ i ≤ m. Consider the closure
{xi } (resp. {yi }) of the singletons {xi } (resp. {yi }) in X (resp.Y ), equipped with their
induced reduced closed subscheme structures. For 1 ≤ i ≤ m, let fi : {xi } → {yi } be the
dominant K-scheme morphism induced by f (cf. [12, Proposition I.5.2.2]). It follows from
Theorem 5.22.(3) in [7] that
(2.4)

dim({yi }) ≤ dim({xi }) for all 1 ≤ i ≤ m.
S
On the other hand, we have that D = 1≤i≤m {yi } since V is dense in D, so that
(2.5)

dim(f (C)) = max dim({yi })
1≤i≤n

by applying Proposition 2.1.(v). From (2.5) and (2.4), we get
(2.6)

dim(D) ≤ max dim({xi }) ≤ dim(C),
1≤i≤n

where the last inequality follows from Proposition 2.1.(i). Now, as C ⊂ X and D ⊂ Y
are constructible subsets, we have that dim(C) = dim(C) and dim(D) = dim(D) by
Proposition 2.9.(vi). Therefore, inequality (2.6) gives us dim(D) ≤ dim(C). This completes
the proof of (iii).
Assertions (iv) and (v) are deduced from (ii) and (iii) after taking C = X.
Suppose now that E is a constructible subset of X0 . Then E = C ∩ X0 for some
constructible subset C ⊂ X by Corollary 2.5. We then have f (E) = f (C) ∩ Y0 by virtue

10

T.CECCHERINI-SILBERSTEIN, M.COORNAERT, AND X.K.PHUNG

of (i), (ii), and Proposition 2.9.(v), and hence
dim(f (E)) = dim(f (C) ∩ Y0 ) = dim(f (C)) ≤ dim(C) = dim(C ∩ X0 ) = dim(E)
by using (i), (iii), and Proposition 2.9.(vi). This shows (vi).



Proposition 2.11. Let X and Y be algebraic varieties over a field K and let f : X → Y
be a K-scheme morphism. For x ∈ X, let y := f (x). Then the following hold:
(i) there exists a closed point x ∈ X such that
(2.7)

dim(f −1 (y)) ≥ dim(X) − dim(Y );

(ii) if X and Y are both irreductible, then Inequality (2.7) is satisfied for every closed
point x ∈ X.
Proof. Consider the geometric fiber of f at y, that is, the Y -fibered product Xy := X ×Y
κ(y), where κ(y) is the residue field of Y at y, and recall that the first projection morphism
Xy → X induces a homeomorphism from Xy onto f −1 (y) (cf. [15, Proposition 3.1.16]). As
X and Y are Noetherian schemes, it follows from Theorem 4.3.12 in [15] that
(2.8)

dim(OXy ,x ) ≥ dim(OX,x ) − dim(OY,y )

for all x ∈ X.
Suppose first that X and Y are irreducible. If x is a closed point of X, then y = f (x)
is a closed point of Y (see e.g. Lemma 3.6 in [5]). By applying Corollary 2.5.24 in [15], we
then get
dim(OX,x ) = dim(X) and dim(OY,y ) = dim(Y ),
so that Assertion (ii) follows from (2.8) and the general fact that dim(OXy ,x ) ≤ dim(Xy ) =
dim(f −1 (y)).
To prove Assertion (i), consider an irreducible component Z of X such that dim(Z) =
dim(X) and the closure V = f (Z) ⊂ Y of its image. As the closure of every irreducible
subset is itself irreducible, V is also irreducible. We equip Z and V with their induced
reduced closed subscheme structures and denote by ι : Z → X the closed immersion associated with Z. By [12, Proposition I.5.2.2], f ◦ ι induces a K-morphism of irreducible
algebraic varieties h : Z → V . Let x ∈ Z be a closed point and y = h(x) = f (x). Then by
what we proved above for the irreducible case (Assertion (ii)), we conclude that
dim(f −1 (y)) ≥ dim(h−1 (y)) ≥ dim(Z) − dim(V ) ≥ dim(X) − dim(Y ),
where the first inequality follows from the inclusion f −1 (y) ⊃ h−1 (y) and the last one from
the inclusion V ⊂ Y .

Proposition 2.12. Let X and Y be algebraic varieties over a field K and let X ×K Y
denote their K-fibered product. Then the following hold:
(i) X ×K Y is a K-algebraic variety;
(ii) (X ×K Y )(K) = X(K) × Y (K);
(iii) dim(X ×K Y ) = dim(X) + dim(Y ).

ON THE GARDEN OF EDEN THEOREM

11

Proof. Assertion (i) follows from Lemma 4.22 in [7].
Assertion (ii) is an immediate consequence of the universal property of K-fibered products.
Assertion (iii) follows from Proposition 5.37 and Proposition 5.50 in [7].

Proposition 2.13. Let X and Y be algebraic varieties over an algebraically closed field K
and let X ×K Y denote their K-fibered product. Let C (resp. D) be a constructible subset
of X (resp. Y ). Then the following hold:
(i) (X ×K Y )0 = X0 × Y0 ;
(ii) C0 × D0 ⊂ (X ×K Y )0 ;
(iii) the set C0 × D0 ⊂ (X ×K Y )0 ⊂ X ×K Y being equipped with the Zariski topology,
one has that dim(C0 × D0 ) = dim(C0 ) + dim(D0 );
(iv) if X and Y are irreducible, then X ×K Y is irreducible.
Proof. Assertion (i) immediately follows from Remark 2.8 and Assertions (i) and (ii) in
Proposition 2.12.
Since C0 ⊂ X0 and D0 ⊂ Y0 by Proposition 2.9.(ii), we have that
C0 × D0 ⊂ X0 × Y0 = (X ×K Y )0
by using (i). This shows (ii).
Since C (resp. D) is a constructible subset of X (resp. Y ), it contains an open dense
subset U (resp. V ) of C (resp. D). Let us equip C and D with their induced reduced closed
subscheme structure. Thus U, V , C, and D are now viewed as K-algebraic varieties. By
properties of base change, U ×K V is an open subscheme of C ×K D, which is in turn a
closed subscheme of X ×K Y . By applyig Proposition 2.9.(vii), we have that U0 ⊂ C0 ⊂ C
and V0 ⊂ D0 ⊂ D, so that
(2.9)

(U ×K V )0 = U0 × V0 ⊂ C0 × D0 ⊂ (C)0 × (D)0 = (C ×K D)0 ⊂ C ×K D,

where the two equalities follow from (i). By using Proposition 2.1.(i), we deduce from (2.9)
that
(2.10)

dim((U ×K V )0 ) ≤ dim(C0 × D0 ) ≤ dim(C ×K D).

Now since
dim((U ×K V )0 ) = dim(U ×K V )

(by Proposition 2.9.(iii))

= dim(U) + dim(V )

(by Proposition 2.12.(iii))

= dim(C) + dim(D)

(by (2.3))

= dim(C0 ) + dim(D0 )

(by Proposition 2.9.(vi))

and
dim(C ×K D) = dim(C) + dim(D)
= dim(C0 ) + dim(D0 )

(by Proposition 2.12.(iii))
(by Proposition 2.9.(vi)),

it follows from (2.10) that dim(C0 × D0 ) = dim(C0 ) + dim(D0 ). This shows (iii).
Assertion (iv) follows from Proposition 5.50 in [7].



12

T.CECCHERINI-SILBERSTEIN, M.COORNAERT, AND X.K.PHUNG

Remark 2.14. Assertion (iv) in Proposition 2.13 becomes false if we remove the hypothesis
that the field K is algebraically closed. For example, X := Spec(C) is an irreducible
algebraic variety over K := R but X ×K X = Spec(C × C) is not irreducible.
2.3. Projective varieties. Let K be a field. A K-algebraic variety X is called a projective
variety over K if there exists a closed immersion ι : X → PN
K for some N ∈ N (cf. [15,
Definition 2.3.47]). In that case, we can identify the underlying topological space of X
with its image by ι.
Theorem 2.15 (Projective dimension Theorem). Let K be an algebraically closed field.
Let Y, Z be closed subschemes of PN
K of dimension r, s respectively. Suppose that r + s ≥ N.
Then Y ∩ Z is nonempty. Equivalently, Y (K) ∩ Z(K) ⊂ PN (K) is nonempty.
Proof. Up to replacing Y and Z by irreducible components of maximal dimension equipped
with their induced reduced closed subscheme structure, we can assume that Y and Z are
irreducible. The theorem is then just a reformulation of Theorem I.7.1 in [14]. Indeed, Y ∩Z
is closed so it is Jacobson. We then equip it with the induced reduced subscheme structure.
Hence, Y ∩Z is nonempty if and only if it has a closed point, i.e., (Y ∩Z)(K) = Y (K)∩Z(K)
is nonempty. See also Proposition 5.40 and its corollaries in [7].

Corollary 2.16. Let N ∈ N and let X ⊂ PN
K be a projective variety over an algebraically
closed field K. Let L ⊂ X be a hyperplane section of X, i.e., L = H ∩ X, where H ⊂ PN
K is
a hyperplane not containing X. Let C ⊂ X be a closed subscheme such that dim(C) ≥ 1.
Then L ∩ C is nonempty.
Proof. By hypothesis, X ⊂ PN
K is a closed subscheme. Hence, C is also a closed subscheme
of PN
since
C
is
closed
in
X.
Observe that dim(C) + dim(H) ≥ 1 + N − 1 = n. Therefore,
K
we deduce from Theorem 2.15 that H ∩ C 6= ∅. As C ⊂ X, we conclude that L ∩ C =
H ∩ X ∩ C = H ∩ C is non-empty.

Remark 2.17. With the notation as in Corollary 2.16, we claim that hyperplane sections of
X always exist. Indeed, let H0 , . . . , HN denote the N + 1 standard coordinate hyperplanes
of PN . Since H0 ∩ · · · ∩ HN = ∅ and X ⊃ C is nonempty, there exists a hyperplane Hi not
containing X. This proves the claim.
In fact, let ι : X → PN be the closed immersion. Let O(1) denote the Serre line bundle
of PN . Then each global section of the very ample line bundle ι∗ O(1) of X is a hyperplane
section. These global sections, denoted by H 0 (X, ι∗ O(1)), form a strictly positive finite
dimensional K-vector space. See chapters II.5, III, and Appendix A in [14] for more details.
Every projective K-algebraic variety is K-proper (see for example [15, Theorem 3.3.30]).
The converse is not true. However, we have the following consequence of Chow’s lemma,
which we shall use in Section 6.
Theorem 2.18. (Chow’s lemma) Let X be an irreducible complete algebraic variety over
a field K. Then there exist an irreducible projective K-algebraic variety X̃ and a surjective
K-morphism f : X̃ → X with dim(X̃) = dim(X).
Proof. See [9, Corollaire II.5.6.2].



ON THE GARDEN OF EDEN THEOREM

13

2.4. Amenable groups. A group G is called amenable if there exist a directed set I and
a family (Fi )i∈I of non-empty finite subsets of G such that
(2.11)

lim
i

|Fi \ Fi g|
= 0 for all g ∈ G
|Fi |

(see [4, Chapter 4] and the references therein). Such a family (Fi )i∈I is then called a (right)
Følner net for G.
All finitely generated groups of subexponential growth and all solvable groups are amenable.
Moreover, the class of amenable groups is closed under the operations of taking subgroups,
quotients, extensions, and direct limits. On the other hand, every group containing a
non-abelian free subgroup is non-amenable.
2.5. Tilings. Let G be a group. Let E and E ′ be two finite subsets of G. A subset T ⊂ G
is called an (E, E ′ )-tiling if it satisfies the following two conditions:
(T-1) the subsets
gE, g ∈ T , are pairwise disjoint,
S
(T-2) G = g∈T gE ′ .
The following statement is an immediate consequence of Zorn’s lemma (see [4, Proposition 5.6.3]).
Proposition 2.19. Let G be a group. Let E be a non-empty finite subset of G and let
E ′ := EE −1 = {gh−1 : g, h ∈ E}. Then there exists an (E, E ′ )-tiling T ⊂ G.
We shall need the following estimate on the growth of tilings with respect to Følner nets.
Proposition 2.20. Let G be an amenable group and let (Fi )i∈I be a Følner net for G. Let
E and E ′ be finite subsets of G and suppose that T ⊂ G is an (E, E ′ )-tiling. For each
i ∈ I, define the subset Ti ⊂ T by Ti := {g ∈ T : gE ⊂ Fi }. Then there exist a real number
α > 0 and an element i0 ∈ I such that |Ti | ≥ α|Fi | for all i ≥ i0 .
Proof. See [4, Proposition 5.6.4].



3. Algebraic cellular automata
3.1. Interiors, neighborhoods, and boundaries. Let G be a group and let M be a
finite subset of G. The M-interior Ω− and the M-neighborhood Ω+ of a subset Ω ⊂ G are
the subsets of G defined respectively by
Ω− := {g ∈ G : gM ⊂ Ω},
and
Ω+ := ΩM = {gh : g ∈ Ω and h ∈ M}.
Note that Ω− ⊂ Ω ⊂ Ω+ if 1G ∈ M.
We define the M-boundary ∂Ω of Ω by ∂M = Ω+ \ Ω− .
If G is an amenable group and (Fi )i∈I is a Følner net of G, then one has
(3.1)

lim
i

|∂Fi |
= 0 for every finite subset M ⊂ G.
|Fi |

14

T.CECCHERINI-SILBERSTEIN, M.COORNAERT, AND X.K.PHUNG

(see e.g. [4, Proposition 5.4.4]).
Let A be a set and let G be a group. Suppose now that we are given a celular automaton
τ : AG → AG with memory set M. Let Ω ⊂ G and let Ω− and Ω+ be defined as above.
−
+
The cellular automaton τ induces maps τΩ− : AΩ → AΩ and τΩ+ : AΩ → AΩ defined
respectively by
τΩ− (u) := (τ (c))|Ω− for all u ∈ AΩ ,
and
+
τΩ+ (u) := (τ (c))|Ω for all u ∈ AΩ ,
where c ∈ AG is any configuration extending u. Observe that the maps τΩ− and τΩ+ are well
defined. Indeed, Formula (1.1) implies that τ (c)(g) only depends of the restriction of c to
gM.
3.2. Cellular automata over algebraic varieties. (cf. [5]) Let S be a scheme and let
X, Y be S-schemes. We denote by X(Y ) the set of Y -points of X, i.e., the set consisting of
all S-scheme morphisms Y → X. If E is a finite set, X E will denote the S-fibered product
of a family of copies of X indexed by E. Note that (X E )(Y ) = (X(Y ))E by the universal
property of S-fibered products. If f : Z → X is an S-scheme morphism, then f induces a
map F (Y ) : Z(Y ) → X(Y ) given by f (Y ) (ϕ) = f ◦ ϕ for all ϕ ∈ Z(Y ).
Let A := X(Y ) and let G be a group. Let τ : AG → AG be a cellular automaton over the
alphabet A and the group G. We say that τ is an algebraic cellular automaton over the
group G and schemes S, X, Y if τ admits a memory set M such that the associated local
defining map µM : AM → A satisfies the following condition:
(∗) there exists an S-scheme morphism f : X M → X such that µM = f (Y ) .
Remark 3.1. If X(S) 6= ∅, and condition (∗) is satisfied for some memory set M of τ ,
then (∗) is satisfied for any memory set of τ (see [5, Proposition 5.1]). This applies in
particular when S = Spec(K) for some algebraically closed field K since in that case X(S)
is (identified with) the set of closed points of X and X is Jacobson.
Lemma 3.2. Let S be a scheme and let X, Y be S-schemes. Let A := X(Y ) and let G be
a group. Suppose that τ : AG → AG is an algebraic cellular automaton over the schemes
S, X, Y and let M be a memory set of τ satisfying (∗). Let Ω be a finite subset of G.
−
+
Then there exist S-scheme morphisms fΩ− : X Ω → X Ω and fΩ+ : X Ω → X Ω such that
−(Y )
+(Y )
fΩ
= τΩ− and fΩ
= τΩ+ .
Proof. We prove the assertion for fΩ− . The construction of fΩ+ is similar. For every g ∈ Ω− ,
we consider the S-scheme projection morphism pg : X Ω → X gM and the S-scheme isomorphism ig : X gM → X M induced by the bijective map gM → M given by left multiplication
by g −1 . Then the family of S-scheme morphisms f ◦ ig ◦ pg : X Ω → X for g ∈ Ω− , yields,
−
by the universal property of S-fibered products, a S-scheme morphism fΩ− : X Ω → X Ω .
−(Y )
It is clear from this construction that fΩ
= τΩ− .

Let G be a group and let K be a field. Let X be a K-algebraic variety and let A :=
X(K). We say that a cellular automaton τ : AG → AG is an algebraic cellular automaton

ON THE GARDEN OF EDEN THEOREM

15

over (G, X, K) if τ is an algebraic cellular automaton over the group G and the schemes
(K, X, K), i.e., for some, or equivalently any (by Remark 3.1), memory set M of τ , there
exists a K-scheme morphism f : X M → X such that f (K) : AM → A is the local defining
map of τ associated with M.
Suppose now that the field K is algebraically closed. Recall from Remark 2.8, that A is
regarded as the set of closed points of X. Given a finite subset Ω of G, we denote by X Ω the
K-fibered product of a family of copies of X indexed by Ω. It follows from Assertion (ii)
in Proposition 2.12 that
AΩ = (X(K))Ω = X Ω (K).
Thus, AΩ is the set of closed points of the algebraic variety X Ω . Note that Proposition 2.9
and Assertion (iii) in Proposition 2.12 imply that
(3.2)

dim(AΩ ) = dim(X Ω ) = |Ω| dim(X) < ∞.

In what follows, every subset of AΩ , or more generally of X Ω , is equiped with the topology
induced by the Zariski topology on X Ω .
Remark 3.3. Let ι : Xred → X denote the reduced scheme associated to the K-algebraic
variety X. Then Xred is also a K-algebraic variety and the immersion ι induces the
identification Xred (K) = X(K). Moreover, (Xred )Ω = (X Ω )red for every finite subset
Ω ⊂ G, so that every algebraic cellular automaton over (G, X, K) can be considered as an
algebraic cellular automaton over (G, Xred , K) (cf. [5, Remark 9.2]). Hence, there is no
loss of generality to assume that X is reduced.
Proposition 3.4. Let G be a group and let X be an algebraic variety over an algebraically
closed field K. Let A := X(K) and let τ : AG → AG be an algebraic cellular automaton
over (G, X, K). Let Γ ⊂ AG and let Φ := τ (Γ) denote the image of Γ under τ . Then the
following hold:
(i) if ΓΩ is a constructible subset of AΩ for every finite subset Ω ⊂ G, then ΦΩ is a
constructible subset of AΩ for every finite subset Ω ⊂ G;
(ii) if the variety X is complete and ΓΩ is closed in AΩ for every finite subset Ω ⊂ G,
then ΦΩ is closed in AΩ for every finite subset Ω ⊂ G.
Proof. Let M be a memory set of τ such that the associated local defining map µ : AM → A
is induced by some K-scheme morphism f : X M → X. Let Ω be a finite subset of G and
define Ω+ , τΩ+ , and fΩ+ as in Subsection 3.1 and Lemma 3.2. Note that ΦΩ = τΩ+ (ΓΩ+ ).
+
Thus, if ΓΩ+ is a constructible subset of AΩ , then ΦΩ = fΩ+ (ΓΩ+ ) is a constructible subset
of AΩ by Proposition 2.10.(vi). This shows (i).
+
Suppose now that the variety X is complete, i.e., proper over K. Then, X Ω and X Ω
are also proper over K since fibered products of proper schemes are proper. As every K+
morphism between proper K-schemes is closed, it follows that fΩ+ : X Ω → X Ω is closed.
+
Assume now that ΓΩ+ is closed in AΩ . This means that there exists a closed subset F
+
+
of X Ω such that ΓΩ+ = AΩ ∩ F is the set of closed points of F . We then get, by using
Proposition 2.10.(ii),
+

ΦΩ = fΩ+ (ΓΩ+ ) = fΩ+ (AΩ ∩ F ) = AΩ ∩ fΩ+ (F ),

16

T.CECCHERINI-SILBERSTEIN, M.COORNAERT, AND X.K.PHUNG

which implies that ΦΩ is closed in AΩ . This shows (ii).



4. Algebraic mean dimension
The definition of algebraic mean dimension we introduce in this section is analogous to
that of topological and measure-theoretic entropy, as well as the various notions of mean
dimension introduced by Gromov in [8].
Definition 4.1. Let G be an amenable group and let F = (Fi )i∈I be a Følner net for
G. Let X be an algebraic variety over an algebraically closed field K and let A := X(K)
denote the set of K-points of X. The algebraic mean dimension of a subset Γ ⊂ AG with
respect to F is the quantity mdimF (Γ) defined by
(4.1)

mdimF (Γ) := lim sup
i∈I

dim(ΓFi )
,
|Fi |

where dim(ΓFi ) denotes the Krull dimension of ΓFi ⊂ AFi ⊂ X Fi with respect to the Zariski
topology and | · | denotes cardinality.
Here are some immediate properties of algebraic mean dimension.
Proposition 4.2. Let G be an amenable group and let F = (Fi )i∈I be a Følner net for
G. Let X be an algebraic variety over an algebraically closed field K and let A := X(K).
Then the following hold:
(i) mdimF (AG ) = dim(X);
(ii) for all subsets Γ, Γ′ ⊂ AG such that Γ ⊂ Γ′ , one has mdimF (Γ) ≤ mdimF (Γ′ );
(iii) for every subset Γ ⊂ AG , one has mdimF (Γ) ≤ dim(X).
Proof. (i) For every i ∈ I, we have that (AG )Fi = AFi , so that
dim(AFi )
dim((AG )Fi )
=
|Fi |
|Fi |
|Fi | dim(X)
=
|Fi |
= dim(X).

(by (3.2))

It follows that mdimF (AG ) = lim supi dim(X) = dim(X).
(ii) Suppose that Γ ⊂ Γ′ ⊂ AG . Then, for all i ∈ I, we have that ΓFi ⊂ Γ′Fi and hence
dim(ΓFi ) ≤ dim(Γ′Fi ) by applying Proposition 2.1.(i). We deduce that
mdimF (Γ) = lim sup
i∈I

dim(Γ′Fi )
dim(ΓFi )
≤ lim sup
= mdimF (Γ′ ).
|Fi |
|Fi |
i∈I

Assertion (iii) is an immediate consequence of (i) and (ii).



ON THE GARDEN OF EDEN THEOREM

17

5. Algebraic mean dimension and surjectivity
Proposition 5.1. Let G be an amenable group and let F = (Fi )i∈I be a Følner net for
G. Let X be an algebraic variety over an algebraically closed field K and let A := X(K).
Let τ : AG → AG be an algebraic cellular automaton over (G, X, K). Suppose that a subset
Γ ⊂ AG satisfies the following property: for every finite subset Ω ⊂ G, the set ΓΩ is a
constructible subset of AΩ for the Zariski topology. Then one has
mdimF (τ (Γ)) ≤ mdimF (Γ).
Proof. Let Γ′ := τ (Γ). Let M ⊂ G be a memory set of τ such that the associated local
defining map µ : AM → A satisfies µ = f (K) for some K-scheme morphism f : X M → X.
By Remark 3.1, up to replacing M by M ∪ {1G } if necessary, we can assume that 1G ∈ M.
Let Ω be a finite subset of G. Observe that, using the notation introduced in Subsection 3.1
and Lemma 3.2,
Γ′Ω− = τΩ− (ΓΩ ) = fΩ− (ΓΩ ).
Therefore, it follows from Proposition 2.10.(vi) that
dim(Γ′Ω− ) ≤ dim(ΓΩ ).

(5.1)

Since 1G ∈ M, we have that Ω− ⊂ Ω ⊂ Ω+ and thus
−

−

−

Γ′Ω ⊂ Γ′Ω− × AΩ\Ω ⊂ X Ω ×K X Ω\Ω = X Ω .
Therefore, we find that
−

dim(Γ′Ω ) ≤ dim(Γ′Ω− × AΩ\Ω ) (by Proposition 2.1)
−

= dim(Γ′Ω− ) + dim(AΩ\Ω ) (by Proposition 2.13.(iii))
= dim(Γ′Ω− ) + |Ω \ Ω− | dim(A) (by Proposition 2.13.(iii))
≤ dim(ΓΩ ) + |Ω \ Ω− | dim(A) (by (5.1))
Since Ω \ Ω− ⊂ ∂Ω, we deduce that
dim(Γ′Ω ) ≤ dim(ΓΩ ) + |∂Ω| dim(A).
Taking Ω = Fi , this gives us
dim(Γ′Fi )
dim(ΓFi ) |∂Fi |
≤
+
dim(A).
|Fi |
|Fi |
|Fi |
Since
lim |∂Fi |/|Fi | = 0
i∈I

by (3.1), we conclude that
dim(Γ′Fi )
|Fi |
i∈I
dim(ΓFi )
≤ lim sup
= mdimF (Γ).
|Fi |
i∈I

mdimF (Γ′ ) = lim sup



18

T.CECCHERINI-SILBERSTEIN, M.COORNAERT, AND X.K.PHUNG

Lemma 5.2. Let G be an amenable group and let F = (Fi )i∈I be a Følner net for G. Let X
be an irreducible algebraic variety over an algebraically closed field K and let A := X(K).
Suppose that Γ ⊂ AG satisfies the following condition:
(C) there exist finite subsets E, E ′ ⊂ G and an (E, E ′ )-tiling T ⊂ G such that for all
g ∈ T , ΓgE $ AgE is a proper closed subset of AgE for the Zariski topology.
Then one has mdimF (Γ) < dim(X).
Proof. For each i ∈ I, define, as in Proposition 2.20, the subset Ti ⊂ T by Ti := {g ∈ T :
gE ⊂ Fi } and set
a
Fi∗ := Fi \
gE,
g∈Ti

where
denotes disjoint union. For all g ∈ T , the set ΓgE is a proper closed subset of AgE
by our hypothesis (C). As AgE is irreducible since X is irreducible and K is algebraically
closed (cf. Proposition 2.12.(iv) and Corollary 2.6), it follows from Proposition 2.1.(ii) that
`

(5.2)

dim(ΓgE ) ≤ dim(AgE ) − 1 = |gE| dim(A) − 1 = |gE| dim(X) − 1

for all g ∈ T . Now observe that, for each i ∈ I,
Y
Y
∗
∗
ΓFi ⊂ AFi ×
ΓgE ⊂ X Fi ×K
X gE = X Fi ,
g∈Ti

g∈Ti

so that
∗

dim(ΓFi ) ≤ dim(AFi ×

Y

ΓgE ) (by Proposition 2.1.(i))

g∈Ti

=

|Fi∗ | dim(A)

+

X

dim(ΓgE ) (by Proposition 2.13.(iii))

X

(|gE| dim(A) − 1) (by (5.2))

g∈Ti

≤ |Fi∗ | dim(A) +

g∈Ti



X
∗
= |Fi | +
|gE| dim(A) − |Ti |
g∈Ti

= |Fi | dim(A) − |Ti | = |Fi | dim(X) − |Ti |.
Now, by virtue of Proposition 2.20, there exist α > 0 and i0 ∈ i such that |Ti | ≥ α|Fi | for
all i ≥ i0 . We deduce that, for all i ≥ i0 ,
dim(ΓFi )
≤ dim(X) − α.
|Fi |
This implies that
mdimF (Γ) = lim sup
i∈I

dim(ΓFi )
≤ dim(X) − α < dim(X).
|Fi |


ON THE GARDEN OF EDEN THEOREM

19

Lemma 5.3. Let G be an amenable group and let F = (Fi )i∈I be a Følner net for G. Let X
be an irreducible algebraic variety over an algebraically closed field K and let A := X(K).
Suppose that a G-invariant subset Γ ⊂ AG satisfies the following conditions:
(D1) Γ is closed in AG for the prodiscrete topology;
(D2) for every finite subset Ω of G, the set ΓΩ is closed in AΩ for the Zariski topology;
(D3) mdimF (Γ) = dim(X).
Then one has Γ = AG .
Proof. We proceed by contradiction. Suppose that there is a configuration c ∈ AG that
does not belong to Γ. By (D1), the set AG \ Γ is an open subset of AG for the prodiscrete
topology. Thus, we can find a finite subset E ⊂ G such that c|E ∈
/ ΓE . This implies that
ΓE $ AE . As Γ is G-invariant, we have that
(5.3)

ΓgE $ AgE

for all g ∈ G.

By Proposition 2.19, there exist a finite subset E ′ ⊂ G and an (E, E ′ )-tiling T ⊂ G. Since
Γ satisfies the hypotheses of Lemma 5.2 by (D2) and (5.3), we deduce that mdimF (Γ) <
dim(X), which contradicts (D3).

We can now prove the main result of this section.
Theorem 5.4. Let G be an amenable group and let F be a Følner net for G. Let X
be an irreducible complete algebraic variety over an algebraically closed field K and let
A := X(K). Let τ : AG → AG be an algebraic cellular automaton over (G, X, K). Suppose
that mdimF (τ (AG )) = dim(X). Then τ is surjective.
Proof. Let us check that Γ := τ (AG ) satisfies the hypotheses of Lemma 5.3. Condition
(D1), that is, the fact that Γ is closed in AG for the prodiscrete topology, follows from
Theorem 6.1 in [5]. On the other hand, Condition (D2), that is, the fact that ΓΩ is closed
in AΩ with respect to the Zariski topology for every finite subset Ω ⊂ G, is satisfied by
Proposition 3.4.(ii). By applying Lemma 5.3, we conclude that Γ = AG . This shows that
τ is surjective.

6. Algebraic mean dimension and weak pre-injectivity
In this section, we introduce two notions of weak pre-injectivity for algebraic cellular
automata, namely (∗)-pre-injectivity and (∗∗)-pre-injectivity. We shall see that these two
notions are equivalent under general hypotheses and that they are both implied by preinjectivity.
We use the following notation. Given a set A, a group G, a finite subset Ω ⊂ G, a subset
D ⊂ AΩ , and an element p ∈ AG\Ω , we write
Dp := D × {p} = {c ∈ AG : c|Ω ∈ D and c|G\Ω = p}.
We say that a subset Γ ⊂ AG has finite support if Γ = Dp for some D, p as above.
Let τ : AG → AG be a cellular automaton over the group G and the alphabet A with
memory set M. Observe that if Γ ⊂ AG has finite support then τ (Γ) also has finite support.
+
+
Indeed, τ (Dp ) = Rs for some subset R ⊂ AΩ and s = s(τ, p) ∈ AG\Ω . Suppose now that

20

T.CECCHERINI-SILBERSTEIN, M.COORNAERT, AND X.K.PHUNG

X is an algebraic variety over an algebraically closed field K and A = X(K). Then we
write dim(Dp ) := dim(D), where dim(D) is the Krull dimension of D ⊂ AΩ with respect
to the Zariski topology. Note that dim(Dp ) is well-defined. Indeed, suppose that Cq = Dp
for some C ⊂ AΛ and q ∈ AG\Λ , where Λ is a finite subset of G. Then clearly C and D are
homeomorphic so that dim(Cq ) = dim(C) = dim(D) = dim(Dp ).
Definition 6.1. Let G be a group and let X be an algebraic variety over an algebraically
closed field K. Let A := X(K) and let τ : AG → AG be an algebraic cellular automaton
over (G, X, K).
We say that τ is (∗)-pre-injective if there do not exist a finite subset Ω ⊂ G and a subset
H ( AΩ that is closed for the Zariski topology such that
τ ((AΩ )p ) = τ (Hp )

for all p ∈ AG\Ω .

We say that τ is (∗∗)-pre-injective if there does not exist a finite subset Ω ⊂ G such that
dim(τ ((AΩ )p )) < dim(AΩ )

for all p ∈ AG\Ω .

Remark 6.2. Let us note that (∗)-pre-injectivity and (∗∗)-pre-injectivity as well as preinjectivity itself, are local properties. More precisely, using again the notation of Definition 6.1 and Subsection 3.1, let M be a memory set of τ such that 1G ∈ M and M = M −1 .
Then (∗)-pre-injectivity amounts to saying that, for every finite subset Ω ⊂ G, there exist
no proper closed subsets H ( AΩ such that
τΩ+ (AΩ × {q}) = τΩ+ (H × {q})

for all q ∈ AΩ

+ \Ω

.

Similarly, (∗∗)-pre-injectivity means (by Proposition 2.10.(iii)) that for every finite subset
Ω ⊂ G, we have
dim(τΩ+ (AΩ × {q})) = dim(AΩ )

for some q ∈ AΩ

+ \Ω

.

Finally, pre-injectivity means that for every finite subset Ω ⊂ G and every q ∈ AΩ
(where Ω++ = (Ω+ )+ ), the restriction of
τΩ++ : AΩ
to AΩ × {q} ⊂ AΩ

++

++

→ AΩ

++ \Ω

+

is injective.

In order to establish, in the next proposition, some key relations between pre-injectivity,
(∗)-pre-injectivity, and (∗∗)-pre-injectivity, we shall use the following general auxiliary
result.
Lemma 6.3. Let X be an irreducible complete algebraic variety over an algebraically closed
field K. Then there exists a proper closed subset H ( X satisfying the following property:
(P) if Y is a K-algebraic variety with dim(Y ) < dim(X) and h : X ։ Y is a surjective
K-scheme morphism, then one has h(H) = Y .
Proof. Since X is irreducible and complete over K, it follows from Chow’s lemma (cf. Theorem 2.18) that there exist an irreducible projective K-algebraic variety X̃ with dim(X̃) =

ON THE GARDEN OF EDEN THEOREM

21

dim(X) and a surjective morphism f : X̃ → X of K-schemes. Let H̃ be a hyperplane section of the projective variety X̃ (cf. Corollary 2.16 and Remark 2.17). Let H := f (H̃) ⊂ X.
As f is a morphism between proper schemes, it is proper and hence closed. Thus, H is a
closed subset of X. Since H̃ ( X is a proper closed subset and X̃ is irreducible, we have
dim(H̃) < dim(X̃). We deduce from Proposition 2.10.(iii) that
dim(X) = dim(X̃) > dim(H̃) ≥ dim(f (H̃)) = dim(H).
It follows that H is a proper closed subset of X.
Now let Y and h : X ։ Y be as in the statement of the lemma. As X is irreducible,
Y = h(X) is also irreducible. Consider the surjective composite morphism
g := h ◦ f : X̃ → Y.
By Assertion (ii) of Proposition 2.11 applied to g : X̃ → Y , for every closed point y ∈ Y ,
the closed subset g −1 (y) ⊂ X̃ satisfies
dim(g −1(y)) ≥ dim(X̃) − dim(Y ) = dim(X) − dim(Y ) ≥ 1.
Hence, we deduce from Corollary 2.16 that the closed subset H̃ ∩ g −1 (y) is nonempty for
every closed point y ∈ Y . Therefore, f (H̃) contains the set of closed points Y0 of Y . As
g = h ◦ f and H = f (H̃), it follows that
(6.1)

h(H) = h(f (H̃)) = g(H̃) ⊃ Y0 .

Since h(H) is constructible in Y by Chevalley’s theorem, Y \ h(H) is also constructible
and hence Jacobson (cf. Proposition 2.9.(iv)). On the other hand, Y \ h(H) does not
contain any closed point of Y by (6.1). We then deduce from Proposition 2.9.(iv) that the
Jacobson space Y \ h(H) has no closed points. It follows that Y \ h(H) is empty. This
shows that h(H) = Y .

Proposition 6.4. Let G be a group and let X be an algebraic variety over an algebraically
closed field K. Let A := X(K) and let τ : AG → AG be an algebraic cellular automaton
over (G, X, K). Then the following hold:
(i) if τ is pre-injective, then τ is both (∗)-pre-injective and (∗∗)-pre-injective;
(ii) if X is irreducible and τ is (∗∗)-pre-injective, then τ is (∗)-pre-injective;
(iii) if X is irreducible and complete over K, then τ is (∗)-pre-injective if and only if it is
(∗∗)-pre-injective.
Proof. Suppose first that X is irreducible and that τ is not (∗)-pre-injective, i.e., there
exists a finite subset Ω ⊂ G and a closed subset H ( AΩ such that
(6.2)

τ ((AΩ )p ) = τ (Hp )

for all p ∈ AG\Ω .

22

T.CECCHERINI-SILBERSTEIN, M.COORNAERT, AND X.K.PHUNG

Since K is algebraically closed, we deduce from Proposition 2.13.(iv) that X Ω and hence
AΩ are irreducible. Thus, it follows from (6.2) that
dim(τ ((AΩ )p )) = dim(τ (Hp ))
≤ dim(Hp ) = dim(H)

(by Proposition 2.10.(iii))

< dim(AΩ )

(by Proposition 2.1.(ii))

for all p ∈ AG\Ω . Therefore τ is not (∗∗)-pre-injective. This proves (ii).
Let M be a memory set of τ and f : X M → X a K-scheme morphism such that
f (K) : AM → A is the local defining map associated with M. After enlarging M if necessary, we can assume 1G ∈ M and M = M −1 . We use again the notation introduced in
Subsection 3.1 and write Ω++ := (Ω+ )+ . Note that Ω ⊂ Ω+ ⊂ Ω++ since 1G ∈ M.
For the proof of (i) and (iii), we shall use the following construction. We suppose that
τ is not (∗∗)-pre-injective, i.e., there exists a finite subset Ω ⊂ G such that
dim(τ ((AΩ )p )) < dim(AΩ )

(6.3)

for all p ∈ AG\Ω .

Let p ∈ AG\Ω with Ω as above and a configuration c ∈ (AΩ )p extending p. Observe that
τ (c)|G\Ω+ only depends on p (here we use the fact that gM ⊂ G \ Ω for all g ∈ G \ Ω+
since M −1 = M).
Consider the following closed immersion induced by p:
Y
++
ι := (IdX Ω , p|Ω++\Ω ) : X Ω = X Ω ×K
Spec(K) → X Ω .
Ω++ \Ω

++

Let Z := ι(X Ω ) ⊂ X Ω be the closed image of ι equipped with the reduced closed
++
subscheme structure. Let j : Z → X Ω be the corresponding closed immersion. Since we
can assume that X is reduced by Remark 3.3, it follows from [12, Proposition I.5.2.2] that
ι factors through a morphism γ : X Ω → Z. Note that Z is homeomorphic to X Ω . Note
also that for any subset Γ ⊂ AΩ , we have
(6.4)

γ(Γ) = Γ × {p|Ω++\Ω } = Γp |Ω++ \Ω .

We consider now the K-scheme morphism
+

h := fΩ++ ◦ j : Z → X Ω ,
where fΩ++ : X Ω
(6.5)

++

+

→ X Ω is defined as in Lemma 3.2. Clearly
σ := h(K) : Z(K) → AΩ

+

is the restriction of τΩ++ to Z(K) = AΩ × {p|Ω++ \Ω }.
+
+
Let Y := Im(h) ⊂ X Ω be the closure of Im(h) in X Ω . We equip Y with the induced
reduced closed subscheme structure over K. By [12, Proposition I.5.2.2], the morphism h
factors through a K-scheme morphism
k : Z → Y.

ON THE GARDEN OF EDEN THEOREM

23

+

Observe that Im(h) is constructible in X Ω by Chevalley’s theorem. We then have the
identifications σ(Z(K)) = h(Z0 ) = Im(h)0 by Proposition 2.10.(ii) and Remark 2.8. From
Proposition 2.9.(vi),
dim(σ(Z(K))) = dim(Im(h)0 ) = dim(Im(h))
= dim(Im(h)) = dim(Y ).
Thus, we deduce from Inequality (6.3) and the above equalities that
(6.6)

dim(Z) = dim(X Ω ) = dim(AΩ )
> dim(τ ((AΩ )p )) = dim(τΩ++ (AΩ × {p|Ω++\Ω }))
= dim(σ(Z(K))) = dim(Y ).

In order to show (i), suppose that τ is pre-injective but not (∗∗)-pre-injective. Let
Ω ⊂ G, p ∈ AG\Ω and the maps h, k be constructed as above. Since τ is pre-injective, the
map σ = h(K) (cf. (6.5)) is injective. As K is algebraically closed, we can identify closed
points of Z and Y with Z(K) and Y (K) respectively. We deduce (from [5, Lemma 3.6.(iii)]
for example) that h and thus k are injective. Proposition 2.11.(i) applied to k : Z → Y
+
shows that there exists a closed point b ∈ Y0 ⊂ X Ω such that
dim(h−1 (b)) = dim(k −1 (b)) ≥ dim(Z) − dim(Y ) ≥ 1,
where the last inequality follows from (6.6). This is a contradiction since h−1 (b) = k −1 (b) is
Jacobson and has at most one closed point by the injectivity of h and k. This proves that
when τ is pre-injective, it must be (∗∗)-pre-injective. Since pre-injectivity implies trivially
(∗)-pre-injectivity by the definition, the point (i) is proved.
We proceed now to the proof of (iii). Suppose that X is irreducible and complete over
K and that τ is not (∗∗)-pre-injective. Let Ω ⊂ G, p ∈ AG\Ω , c ∈ (AΩ )p and the maps
h, k, γ be as above. Observe again that X Ω is irreducible by Proposition 2.13.(iv). As X
+
+
is proper, the varieties X Ω , X Ω and Z are also proper over K. Hence h : Z → X Ω is a
morphism of proper K-schemes. Consequently, h is closed, Y = Im(h) and thus k : Z → Y
is surjective.
Since X Ω is irreducible and complete, Lemma 6.3 shows that there exists a proper closed
subset L ( X Ω independent of p satisfying:
(P) if V is a K-algebraic variety with dim(V ) < dim(X Ω ) and Φ : X Ω ։ V is a surjective
K-scheme morphism, then one has Φ(L) = V .
We consider the set of K-points of L:
H := L(K) ( AΩ .
Applying Property (P ) to the surjective morphism k ◦ γ : X Ω ։ Y , we deduce that
k(γ(L)) = Y . Since a surjective morphism between K-algebraic varieties induces a surjective map between their sets of closed points (cf. [5, Lemma 2.22.(iv)]), we deduce that
(6.7)

h(H × {p|Ω++ \Ω }) = k((γ(H)) = Y (K) = h(AΩ × {p|Ω++ \Ω }).

24

T.CECCHERINI-SILBERSTEIN, M.COORNAERT, AND X.K.PHUNG
+

Now let d = h(c|Ω++ ) = τ (c)|Ω+ ∈ AΩ be identified with a closed point in Y0 = Y (K). By
(6.7), there exists z ∈ H = L(K) such that h(z × {p|Ω++ \Ω }) = d. Let c′ ∈ Hp ⊂ AG be a
configuration such that c′ |Ω = z and c′ |G\Ω = p. Then we see that
h(c′ |Ω++ ) = h(c|Ω++ ) = d.
Hence, τ (c′ )|Ω+ = τ (c)|Ω+ = d. As c′ |G\Ω = c|G\Ω = p, we have τ (c′ )|G\Ω+ = τ (c)|G\Ω+ .
Thus, we find that τ (c′ ) = τ (c). As p ∈ AG\Ω and c ∈ (AΩ )p are arbitrary and c′ ∈ Hp , we
deduce that
τ ((AΩ )p ) = τ (Hp ) for all p ∈ AG\Ω .
Therefore, τ is not (∗)-pre-injective. Hence, (∗)-pre-injectivity implies (∗∗)-pre-injectivity
when X is irreducible and complete over K. Together with (ii), this completes the proof
of (iii).

Proposition 6.5. Let G be an amenable group and let F = (Fi )i∈I be a Følner net for
G. Let X be an algebraic variety over an algebraically closed field K and let A := X(K).
Let τ : AG → AG be an algebraic cellular automaton over (G, X, K). Suppose that τ is
(∗∗)-pre-injective. Then one has
mdimF (τ (AG )) = dim(X).

(6.8)

Proof. We proceed by contradiction. Suppose that (6.8) is not satisfied, i.e.,
mdimF (τ (AG )) < dim(X).

(6.9)

Let M be a memory set for τ such that 1G ∈ M. Let Γ := τ (AG ). As ΓFi+ is a subset of
+

ΓFi × AFi \Fi and ΓFi is a constructible subset of AFi (by Assertion (i) of Proposition 3.4),
we have that
+

dim(ΓFi+ ) ≤ dim(ΓFi × AFi

\Fi

)

(by Proposition 2.1.(i))

Fi+ \Fi

= dim(ΓFi ) + dim(A

)

(by Proposition 2.13.(iii))

= dim(ΓFi ) + |Fi+ \ Fi | dim(X)

(by (3.2))

≤ dim(ΓFi ) + |∂(Fi )| dim(X)

(since Fi+ \ Fi ⊂ ∂Fi ).

Hence, we find that
dim(ΓF + )
i

|Fi |

≤

dim(ΓFi ) |∂(Fi )|
+
dim(X).
|Fi |
|Fi |

The above inequality together with (6.9) and (3.1) show that there exists i0 ∈ I such that
dim(ΓFi+ ) < |Fi0 | dim(X).

(6.10)

0

+

Observe now that for all p ∈ AG\Fi0 , we have that τ ((AFi0 )p ) ⊂ τ (AG ) ∩ (AFi0 )q where
+
q = τ (p̃)|G\F + ∈ AG\Fi0 and p̃ ∈ AG is an arbitrary configuration that extends p. Therefore,
i0

ON THE GARDEN OF EDEN THEOREM

25

we have for all p ∈ AG\Fi0 that
dim(τ ((AFi0 )p )) ≤ dim(τ (AG )|Fi+ ) = dim(ΓFi+ )
0

0

< |Fi0 | dim(A) = dim(AFi0 )

(by (6.10)).

We can thus conclude that τ is not (∗∗)-pre-injective.



As described by the next proposition, the converse of Proposition 6.5 also holds if we
replace (∗∗)-pre-injectivity by (∗)-pre-injectivity.
Proposition 6.6. Let G be an amenable group and let F be a Følner net for G. Let X be an
algebraic variety over an algebraically closed field K. Let A := X(K) and let τ : AG → AG
be an algebraic cellular automaton over (G, X, K). Suppose that X is irreducible and that
mdimF (τ (AG )) = dim(X).

(6.11)
Then τ is (∗)-pre-injective.

Proof. We proceed by contradiction. Suppose that the cellular automaton τ is not (∗)-preinjective. Thus, there exist a finite subset E ⊂ G and a closed proper subset H ( AE such
that
(6.12)

τ ((AE )p ) = τ (Hp )

for all p ∈ AG\E .

By Proposition 2.19, we can find a finite subset E ′ ⊂ G such that G contains an (E, E ′ )tiling T . For every t ∈ T , we define Ht ⊂ AtE to be the image of H under the canonical
bijective map AE → AtE that is induced by the left-multiplication by t−1 . Since τ is
G-equivariant, we deduce from (6.12) that for each t ∈ T , we have that
(6.13)

τ ((AtE )p ) = τ ((Ht )p )

for all p ∈ AG\tE .

Consider the subset Γ ⊂ AG defined by
Γ := AG\T E ×

Y

Ht .

t∈T

We claim that τ (AG ) = τ (Γ). Indeed, let c ∈ AG be any configuration and let us show
that there exists a configuration in Γ whose image under τ is equal to τ (c).
To see this, consider the set Φ ⊂ AG consisting of all configurations d ∈ AG satisfying
the following conditions:
(C1) d|G\T E = c|G\T E ;
(C2) if t ∈ T , then d|tE = c|tE or d|tE ∈ Ht ;
(C3) τ (d) = τ (c).
Given a configuration d ∈ Φ, we define the subset Td ⊂ T by
Td := {t ∈ T : d|tE ∈ Ht }.
We partially order Φ by the relation ≤ defined by
d ≤ e ⇐⇒ (Td ⊂ Te and d|tE = e|tE for all t ∈ Td ) .

26

T.CECCHERINI-SILBERSTEIN, M.COORNAERT, AND X.K.PHUNG

Let us check that Φ satisfies the hypotheses of Zorn’s lemma. The set Φ is not empty since
c ∈ Φ. On the other hand, suppose that Ψ is a non-empty totally ordered subset of Φ. Let
us show that Ψ admits an upper bound in Φ. To see this, first observe that, for t ∈ T fixed,
the restrictions d|tE , d ∈ Ψ, are eventually constant, i.e., there exists λt ∈ AtE such that
d|tE = λt for all d ∈ Ψ large enough (with respect to ≤). Consider now the configuration
e ∈ AG defined by
e|G\T E = c|G\T E and e|tE = λt for all t ∈ T.
It is clear that e satisfies (C1) and (C2). If Ω is a finite subset of G, then there are only
finitely many g ∈ T such that gE ⊂ Ω. It follows that there exists d ∈ Ψ such that
e|Ω = d|Ω . Taking Ω = gM, where g ∈ G and M is a memory set of τ , we deduce that
τ (e)(g) = τ (d)(g) = τ (c)(g) for all g ∈ G. This shows that e also satisfies (C3). Thus,
e ∈ Φ is an upper bound for Ψ. By Zorn’s lemma, Φ admits a maximal element m. We
have that τ (m) = τ (c) since m ∈ Φ satisfies (C3). We also have that m ∈ Γ. Indeed,
otherwise, there would be some t ∈ T such that m|tE ∈
/ Ht . But then using (6.13), we
could modify m on tE and get an element m′ ≥ m in Φ with Tm′ = Tm ∪ {t}, contradicting
the maximality of m. This completes the proof that τ (AG ) = τ (Γ).
We then get
mdimF (τ (AG )) = mdimF (τ (Γ))
≤ mdimF (Γ)

(by Proposition 5.1)

< dim(X)

(by Lemma 5.2),

which contradicts (6.11). Observe that the hypotheses of Proposition 5.1 are satisfied since
ΓΩ is a closed and hence constructible subset of AΩ for every finite subset Ω ⊂ G. Note
also that the hypotheses of Lemma 5.2 are satisfied since X is assumed to be irreducible
and ΓtE = Ht is a proper closed subset of AtE for all t ∈ T .

7. Main results
Proof of Theorem 1.3. The result follows from Proposition 4.2.(i) and Proposition 6.6. 
The following statement contains Theorem 1.1 as well as Theorem 1.4.
Theorem 7.1. Let G be an amenable group. Let X be an irreducible complete algebraic
variety over an algebraically closed field K and let A := X(K). Suppose that τ : AG →
AG is an algebraic cellular automaton over (G, X, K). Then the following conditions are
equivalent:
(a) τ is surjective;
(b) τ is (∗)-pre-injective;
(c) τ is (∗∗)-pre-injective;
(d) for some (or equivalently any) Følner net F of the group G, one has mdimF (τ (AG )) =
dim(X).
Moreover, if τ is pre-injective then it is surjective.

ON THE GARDEN OF EDEN THEOREM

27

Proof. The fact that (a) implies (d) follows from Proposition 4.2.(i) and the converse implication from Theorem 5.4. Thus, (a) and (d) are equivalent. We have that (d) implies
(b) by Proposition 6.6, and (b) implies (c) by Proposition 6.4.(ii). On the other hand, we
have that (c) implies (d) by Proposition 6.5. This shows that conditions (b), (c), and (d)
are equivalent.
Finally, the last assertion follows from the fact that pre-injectivity implies (∗)-preinjectivity by Proposition 6.4.(i) and the implication (b) =⇒ (a).

Let G be a group et M ⊂ G be finite subset. Let X be an algebraic variety over an
algebraically closed field K and let f : X M → X be a K-scheme morphism. For each
field extension L/K, let XL := X ×K Spec(L) denote the L-algebraic variety obtained
by the base change Spec(L) → Spec(K). Then we have XL (L) = X(L). We denote by
τ (L) : X(L)G → X(L)G the algebraic cellular automaton over (G, XL , L) with memory set
M and associated local defining map f (L) .
Theorem 7.2. With the above notation, suppose in addition that G is amenable, X is
irreducible and complete, and L is algebraically closed. Then τ (K) is surjective if and only
if τ (L) is surjective.
Proof. This follows from Theorem 5.4 and the invariance of dimension of algebraic varieties
under base change of the ground field. Indeed, let Γ(K) := τ (K) (X(K)G ) and Γ(L) :=
τ (L) (X(L)G ). Let Ω ⊂ G be a finite subset. Then we have the identifications
(K)

+(K)

(L)

+(L)

ΓΩ = fΩ
ΓΩ = fΩ

+

+

(X(K)Ω ) = fΩ+ (X Ω )0
+

+

(X(L)Ω ) = (fΩ+ × IdL )(XLΩ )0 .

Thus for all finite subset Ω ⊂ G, we find that
(K)

+

+

(L)

dim(ΓΩ ) = dim(fΩ+ (X Ω )) = dim((fΩ+ × IdL )(XLΩ )) = dim(ΓΩ ).
Let F = (Fi )i∈I be a Følner net of G. Then by the definition of mean dimension, we have
that
(K)
(L)
dim(ΓFi )
dim(ΓFi )
(K)
mdimF (Γ ) := lim sup
= lim sup
=: mdimF (Γ(L) ).
|F
|
|F
|
i∈I
i∈I
i
i
We can therefore conclude from Theorem 5.4 that τ (K) is surjective if and only if τ (L) is
surjective.

8. Counterexamples
In the following example, we shall see that Theorem 1.4, Theorem 5.4, and Proposition 6.4 become false if we remove the hypothesis that X is irreducible, even if X is
assumed to be 0-dimensional.
Example 8.1. Let G be a group and K an algebraically closed field.
Suppose that X is a K-algebraic variety with dim(X) = 0. Then A := X(K) is a finite
non-empty set. Moreover, every map A → A is induced by some K-scheme morphism

28

T.CECCHERINI-SILBERSTEIN, M.COORNAERT, AND X.K.PHUNG

X → X. Conversely, given a finite non-empty set A, there exists a 0-dimensional Kalgebraic variety X such that X(K) = A. We can take for example the reduced Kalgebraic variety X obtained by taking the discrete union of a family indexed by A of
copies of Spec(K).
Let A be a finite non-empty set and X a 0-dimensional K-algebraic variety such that
X(K) = A. Clearly the cellular automata over the group G and the alphabet A are
precisely the algebraic cellular automata over (G, X, K).
Now let τ : AG → AG be a cellular automaton over the group G and the alphabet
A. By the classical Garden of Eden theorem in [6], the surjectivity of τ is equivalent to
its pre-injectivity and is also equivalent to the fact that τ (AG ) has maximal topological
entropy. Note that it immediately follows from the characterization of pre-injectivity by
the absence of a pair of distinct mutually erasable patterns (see e.g. [4, Proposition 5.5.2])
that τ is pre-injective if and only if it is (∗)-pre-injective. Observe also that τ is always
(∗∗)-pre-injective. In the case when G is amenable with a Følner net F then τ satisfies
mdimF (τ (AG )) = dim(X) = 0 since
dim(AΩ ) = 0
for every finite subset Ω ⊂ G. The variety X is irreducible if and only if A is a singleton.
Otherwise, there exist cellular automata τ : AG → AG that are not surjective (e.g., the
map τ : AG → AG defined by τ (c) = c0 for all c ∈ AG , where c0 ∈ AG is some constant
configuration). Such a cellular automaton is (∗∗)-pre-injective but not (∗)-pre-injective.
The next example shows that we cannot replace the hypothesis that X is irreducible
by the weaker hypothesis that it is connected in Theorem 1.4, Theorem 5.4, and Proposition 6.4.
Example 8.2. Let G be an amenable group and let F be a Følner net for G. Let K be
an algebraically closed field. Consider the projective curve X in P2K defined by
X := Proj(K[u, v, w]/(uv)) ⊂ P2K .
Then X = Lu ∪ Lv ⊂ P2K is the union of the two projective coordinate lines
Lu := {u = 0},

Lv := {v = 0} ⊂ P2K .

Since X has two irreducible components Lu and Lv , it is not irreducible. However, X is
clearly connected. In the principal affine chart A2K = D+ (w) = {w 6= 0} ⊂ P2K , we see that
X is given by
Y = Spec(K[x, y]/(xy)) = Ix ∪ Iy ⊂ A2K ,
where x = u/w, y = v/w and Ix = {x = 0}, Iy = {y = 0}. Let h : Y → Y be the
contraction morphism induced by the morphism of K-algebras:
K[x, y]/(xy) → K[x, y]/(xy)
(x, y) 7→ (x, 0).

ON THE GARDEN OF EDEN THEOREM

29

It is clear that h(Y ) = h(Iy ) = Iy = Spec(K[x, y]/(y)) ≃ A1K . By, for example, the
valuative criteria of properness (cf. [14, Theorem II.4.7]), there is a K-scheme morphism
f : X → X extending h and that
f ((0 : 1 : 0)) = f ((1 : 0 : 0)) = (1 : 0 : 0) ∈ Lv .
Hence, f (X) = f (Lv ) = Lv and thus dim(f (X)) = dim(Lv ) = 1. Clearly f is not surjective
and thus f (K) is not surjective either.
Now let A := X(K) and let τ : AG → AG be the cellular automaton over (G, X, K) with
memory set M = {1G } and associated local defining map f (K) : A → A. Observe that τ
is not pre-injective since f is not injective and M = {1G }. Also τ is not (∗)-pre-injective
since f (X) = f (Lv ) = Lv . On the other hand, mdimF (τ (AG )) = 1 = dim(X) and τ is
(∗∗)-pre-injective but not surjective.
The following example shows that Theorem 1.4 and Theorem 5.4 do not hold in general
for irreducible non-complete algebraic varieties.
Example 8.3. Let G be an amenable group and let F be a Følner net for G. Let K
be an algebraically closed field. Let X be an irreducible algebraic variety over K and let
A := X(K). Suppose that f : X → X is a non-surjective dominant K-scheme morphism.
Observe that f is not injective by the Ax-Grothendieck theorem. Let τ : AG → AG be the
algebraic cellular automaton over (G, X, K) with memory set M = {1G } and associated
local defining map f (K) : A → A.
Since f is dominant, Chevalley’s theorem and Proposition 2.9.(vi) imply that dim(f (X)) =
dim(X). As K is algebraically closed, we have that
dim(f (A)) = dim(f (X)) = dim(X).
We deduce that mdimF (τ (AG )) = dim(X). It is clear that τ is both (∗)- and (∗∗)-preinjective. However, since f is not surjective, f (K) is not surjective either (see e.g. [5,
Lemma 2.22.(iv)]). Hence, τ is not surjective as well. Note also that f (K) is not injective
since f is not (see e.g. [5, Lemma 2.22.(iii)]). It follows that τ is not pre-injective.
Here is a class of such couples (X, f ). Let X = A2 = Spec(K[x, y]) be the affine plane
over K and consider the morphism f : A2 → A2 given by the morphism of K-algebras
K[x, y] → K[x, y]
(x, y) 7→ (xr , xs P (y)),
where r, s ≥ 1 and P ∈ K[y] is a non-constant polynomial in y. It is clear that f (A2 ) =
A2 \({x = 0}\{(0, 0)}). Hence f is indeed a non-surjective dominant K-scheme morphism.
This construction can be easily generalized to higher dimensional affine spaces An for n ≥ 2
by using for example the morphisms of K-algebras given by
K[x1 , . . . , xn ] → K[x1 , . . . , xn ]
(x1 , . . . , xn ) 7→ (xr11 , xr12 P2 (x2 ), . . . , xr1n Pn (xn )),
where r1 , . . . , rn ∈ N∗ and P2 , . . . , Pn are nonconstant polynomials in x2 , . . . , xn respectively.

30

T.CECCHERINI-SILBERSTEIN, M.COORNAERT, AND X.K.PHUNG

We give now an example with non-trivial minimal memory set showing that we cannot
omit the hypothesis that X is complete in Theorem 5.4.
Example 8.4. In this example, we take G := Z. Thus G is amenable. Let X := A1K =
Spec(K[t]) be the affine line over an algebraically closed field K and let A := X(K) = K.
Let τ : AG → AG be the cellular automaton over (G, X, K) with memory set M = {0, 1} ⊂
Z and associated local defining map given by f (K) : X(K)K → X(K), where f : X M → X
is the K-scheme morphism induced by the morphism of K-algebras
K[t] → K[x, y]
t 7→ xy
Clearly τ : K Z → K Z is given by the formula:
τ (c)(n) = c(n)c(n + 1) for all c ∈ K Z and n ∈ Z.
Consider the configuration d ∈ K Z such that d(−1) = d(1) = 1 and d(n) = 0 if n ∈
Z \ {−1, 1}. If there were some configuration c ∈ KZ such that τ (c) = d, then we would
have c(0)c(1) = d(0) = 0. This would imply c(0) = 0 or c(1) = 0 and hence d(−1) = 0 or
d(1) = 0, which is a contradiction. We deduce that d has no pre-image under τ . Thus τ is
not surjective.
We claim that mdim(τ (K Z )) = 1 = dim(X). Indeed, let Γ := τ (K Z ). For each m ∈ N,
let Fm := [−m, m] ∩ Z ⊂ Z. Then F := (Fm )m is a Følner sequence for Z. Note that
Fm+ = [−m, m + 1] ∩ Z. Consider the K-scheme morphism (cf. Lemma 3.2)
+

fF+m : X Fm = A2m+2 → X Fm = A2m+1 .
+(K)

Then τF+m = fFm . It is immediate that
τF+m (c−m , . . . , cm+1 ) = (c−m c−m+1 , . . . , cm cm+1 ).
We deduce that the image of fF+m contains A2m+1 \ L where
L = V ((x−m . . . xm )) ⊂ A2m+1 = Spec(K[x−m , . . . , xm ])
is the union of the 2m + 1 coordinate hyperplanes given by the equation x−m . . . xm = 0.
Therefore, we have dim(Im(fF+m )) = dim(A2m+1 ) and thus dim(ΓFm ) = |Fm | = 2m + 1 for
all m ∈ N. Hence, we conclude that
dim(ΓFm )
mdimF (Γ) = lim sup
= 1 = dim(A)
|Fm |
m
as claimed. Since d is almost equal to the configuration 0 ∈ K Z and τ (d) = τ (0) = 0, we
see that τ is not pre-injective. It follows from Proposition 6.6 that τ is (∗)-pre-injective.
The following example shows that the hypothesis that G is amenable cannot be omitted
in Theorem 1.1.
Example 8.5. Let G = F2 be the free group of rank 2 based on the generators a, b.
We recall that G is residually finite but not amenable. Let M := {a, b, a−1 , b−1 } ⊂ F2 .
Consider an abelian variety Y = (Y, +) over an algebraically closed field K with indentity

ON THE GARDEN OF EDEN THEOREM

31

element e ∈ Y (K). We suppose that Y is non-trivial, so that dim(Y ) ≥ 1. The Kfibered product X := Y ×K Y is also a non-trivial abelian variety over K. The set A :=
X(K) = Y (K) × Y (K) of K-points of X is a non-trivial abelian group. For i = 1, 2 let
q i : Y M ×K Y M → Y M be the i-th projection and for g ∈ M, let qg : Y M → Y be the
projection on the g-factor. For i = 1, 2 and g ∈ M, let pig : X M = Y M ×K Y M → Y be the
projection defined by pig := qg ◦ q i . Let h : X M → Y be the morphism defined by
h := p1a + p1a−1 + p2b + p2b−1 .
Let ι := (IdY , e) : Y = Y ×K Spec(K) → X = Y ×K Y . Finally, we define f := ι◦ h : X M →
X.
Let τ : AG → AG be the algebraic cellular automaton over (G, X, K) with memory set
M and associated local defining map µ = f (K) : AM → A. Observe that for all c ∈ AG :

τ (c)(g) = π1 (c(ga)) + π1 (c(ga−1)) + π2 (c(gb)) + π2 (c(gb−1)), e ,

where πi : A → A is given by πi (u1 , u2) = (ui , e) for i = 1, 2 and (u1 , u2) ∈ Y (K) × Y (K) =
A. By [4, Proposition 5.11], we see that τ is pre-injective but not surjective.

The following example shows in particular that Theorem 1.3 yields another characterization of group amenability.
Example 8.6. Let G be a group and let K be an algebraically closed field. Let X := AnK
and A := X(K) = K n . Suppose that τ : AG → AG is a K-linear cellular automaton (cf.
[4, Section 8.1]). Clearly τ is an algebraic cellular automaton over (G, X, K).
We claim that τ is pre-injective if and only if it is (∗)-pre-injective. Suppose that τ is not
pre-injective. Hence there exists a configuration c ∈ AG with a nonempty finite support
Ω ⊂ G such that τ (c) = 0 (cf. [4, Proposition 8.2.5]). Let M ⊂ G be a memory set for τ
such that 1G ∈ M and M = M −1 . Set Ω++ := (Ω+ )+ = ΩM 2 (cf. Subsection 3.1). Recall
++
that Ω ⊂ Ω+ ⊂ Ω++ since 1G ∈ M. Let H be a linear hyperplane in AΩ not containing
++
c|Ω++ , so that AΩ = H ⊕ Kc|Ω++ . Let us show that
τ ((AΩ

(8.1)
G\Ω++

++

)p ) = τ (Hp )

for all p ∈ AG\Ω

++

.
++

Ω++

)p , we only need to show the inclusion τ ((AΩ )p ) ⊂
Let p ∈ A
. Since Hp ⊂ (A
++
τ (Hp ). Let d ∈ (AΩ )p . Then we can find h ∈ H and k ∈ K such that d|AΩ++ = h+kc|Ω++ .
Let hp ∈ Hp be the unique configuration such that (hp )|AΩ++ = h and (hp )|G\AΩ++ = p,
and let us show that τ (d) = τ (hp ). Let g ∈ G and suppose first that g ∈ Ω+ so that
gM ⊂ Ω++ . Then d|gM = (hp + kc)|gM and therefore
τ (d)(g) = τ (hp + kc)(g) = τ (hp )(g) + kτ (c)(g) = τ (hp )(g),
where the last equality follows from the fact that τ (c) = 0. Suppose now that g ∈ G \ Ω+ .
Then gM ∩ Ω = ∅ (here we use M = M −1 ) so that d|gM = (hp )|gM and therefore
τ (d)(g) = τ (hp )(g).
++

Thus τ (d) = τ (hp ), and the inclusion τ ((AΩ )p ) ⊂ τ (Hp ) follows. This shows (8.1).
++
Now, since H is a proper closed subset of AΩ , we deduce that τ is not (∗)-pre-injective.

32

T.CECCHERINI-SILBERSTEIN, M.COORNAERT, AND X.K.PHUNG

Since, conversely, every pre-injective algebraic cellular automaton is (∗)-pre-injective by
Proposition 6.4, this proves our claim.
Suppose now that G is non-amenable. By a result of Bartholdi [2, Corollary 1.5] there
exists an integer n ≥ 1 and a surjective K-linear cellular automaton τ : AG → AG that is
not pre-injective (and hence not (∗)-pre-injective). As X = AnK is irreducible, this shows
that Theorem 1.3 becomes false if the group G is non-amenable.
9. Questions
Question 1. Can we remove the hypothesis that X is complete (respectively, irreducible)
in Theorem 1.1?
Question 2. Does Theorem 1.3 still hold without the assumption that X is irreducible?
Question 3. Does Theorem 7.2 remain valid without the amenability hypothesis on the
group G?
Question 4. Does Theorem 1.1 characterize amenable groups?
References
[1] J. An, Rigid geometric structures, isometric actions, and algebraic quotients, Geom. Dedicata, 157
(2012), pp. 153–185.
[2] L. Bartholdi, Cellular automata, duality and sofic groups, New York J. Math. 23 (2017), pp. 1417–
1425.
[3] T. Ceccherini-Silberstein and M. Coornaert, The Garden of Eden theorem for linear cellular
automata, Ergodic Theory Dynam. Systems, 26 (2006), pp. 53–68.
, Cellular automata and groups, Springer Monographs in Mathematics, Springer-Verlag, Berlin,
[4]
2010.
[5] T. Ceccherini-Silberstein, M. Coornaert, and X. K. Phung, On injective cellular automata
over schemes, arXiv:1712.05716.
[6] T. Ceccherini-Silberstein, A. Machı̀, and F. Scarabotti, Amenable groups and cellular automata, Ann. Inst. Fourier (Grenoble), 49 (1999), pp. 673–685.
[7] U. Görtz and T. Wedhorn, Algebraic geometry I, Advanced Lectures in Mathematics, Vieweg +
Teubner, Wiesbaden, 2010. Schemes with examples and exercises.
[8] M. Gromov, Endomorphisms of symbolic algebraic varieties, J. Eur. Math. Soc. (JEMS), 1 (1999),
pp. 109–197.
[9] A. Grothendieck, Éléments de géométrie algébrique. II. Étude globale élémentaire de quelques
classes de morphismes, Inst. Hautes Études Sci. Publ. Math., (1961), p. 222.
, Éléments de géométrie algébrique. IV. Étude locale des schémas et des morphismes de schémas.
[10]
I, Inst. Hautes Études Sci. Publ. Math., (1964), p. 259.
, Éléments de géométrie algébrique. IV. Étude locale des schémas et des morphismes de schémas.
[11]
III, Inst. Hautes Études Sci. Publ. Math., (1966), p. 255.
[12]
, Éléments de géométrie algébrique. I, vol. 166 of Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], Springer-Verlag, Berlin, 1971.
[13] J. Harris, Algebraic geometry, vol. 133 of Graduate Texts in Mathematics, Springer-Verlag, New
York, 1995. A first course, Corrected reprint of the 1992 original.
[14] R. Hartshorne, Algebraic geometry, Springer-Verlag, New York, 1977. Graduate Texts in Mathematics, No. 52.

ON THE GARDEN OF EDEN THEOREM

33

[15] Q. Liu, Algebraic geometry and arithmetic curves, vol. 6 of Oxford Graduate Texts in Mathematics,
Oxford University Press, Oxford, 2002. Translated from the French by Reinie Erné, Oxford Science
Publications.
[16] E. F. Moore, Machine models of self-reproduction, vol. 14 of Proc. Symp. Appl. Math., American
Mathematical Society, Providence, 1963, pp. 17–34.
[17] J. Myhill, The converse of Moore’s Garden-of-Eden theorem, Proc. Amer. Math. Soc., 14 (1963),
pp. 685–686.
[18] R. Vakil, MATH 216: Foundations of Algebraic Geometry.
Università del Sannio, I-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
Université de Strasbourg, CNRS, IRMA UMR 7501, F-67000 Strasbourg, France
E-mail address: phung@math.unistra.fr

