The Garden of Eden theorem: old and new
Tullio Ceccherini-Silberstein Michel Coornaert
math.DS cs.IT math.GR math.IT nlin.CG 37B15, 37B10, 37B40, 37C29, 37D20, 43A07, 68Q80



Università del Sannio, 82100 Benevento, Italy
tullio.cs@sbai.uniroma1.it

Université de Strasbourg, CNRS, IRMA UMR 7501, F-67000 Strasbourg, France
michel.coornaert@math.unistra.fr
[2010]37B15, 37B10, 37B40, 37C29, 37D20,  
43A07, 68Q80


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


The Garden of Eden theorem: old and new
    Michel Coornaert
    December 30, 2023
=======================================









§ 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 MooreMoore, Edward F. and MyhillMyhill, John R. in the early 1960s
 for cellular automata with finite alphabet over the groups ^d. 
The fact that surjectivity implies pre-injectivity for such cellular automata was first proved by Moore in <cit.>, and  
 Myhill <cit.> 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 <cit.>, SchuppSchupp, Paul E. 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 <cit.>,Gromov, Misha L.
a finitely generated group is virtually nilpotent 
if and only if it has polynomial growth.
In 1993,  Machì and Mignosi <cit.>
proved that the Garden of Eden theorem is still valid over any finitely generated group with subexponential growth.
As Grigorchuk <cit.>,Grigorchuk, Rostislav I.
answering a longstanding open question raised by Milnor <cit.>,Milnor, John W.
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 <cit.> 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) = ⟨ a,b:aba^-1 = b^2⟩, that are amenable 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 <cit.>, BartholdiBartholdi, Laurent 
and Kielak <cit.>,
who showed that none of the implications of the Garden of Eden theorem
holds  when the group is nonamenable.
In <cit.>,
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
<cit.>
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 <cit.>,
<cit.>, <cit.> and, in collaboration with H. Li,Li, Hanfeng <cit.>.
In particular, a version of the Garden of Eden theorem was established    
for Anosov diffeomorphisms on tori in <cit.> and for principal expansive 
algebraic actions of countable abelian groups in <cit.>.
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 <cit.>. The present survey is a kind of complement to our book since for instance cellular automata between subshifts are not considered in <cit.> while they are treated  here. 
 The paper is organized as follows.
Configuration spaces and shifts are presented in Section <ref>.
Cellular automata are introduced in Section <ref>.
Section <ref> contains the proof of the Garden of Eden theorem in the case G = ^d
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 <ref>.
Examples of cellular automata that do not satisfy the Garden of Eden theorem for groups containing nonabelian free subgroups are described in Section <ref>.
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 <ref>.
In Section <ref>,
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.    




§ CONFIGURATION SPACES AND SHIFTS





 §.§ Notation

We use the symbol  to denote the set of integers {…,-2,-1,0,1,2,…}.
The symbol    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 

    ^d = ××⋯×_
 
for which we generally prefer additive notation.
Let G  be a group. We denote the identity element of G by 1_G.
If A, B are subsets of G and g ∈ G, we write
A B { a b : a ∈ A,b ∈ B},
A^-1{a^-1 : a ∈ A}, g A {g} A and A g  A {g}. A subset A ⊂ G is said to be symmetricsymmetric subset if it satisfies A = A^-1.




 §.§ Configurations spaces

Let  be a countable set, called the universe,universe and 
A  a finite set, called the alphabet.alphabet
Depending on the context, the elements of A are called  
letters, or   symbols, or states, or colors.  
As usual, we denote by A^ the set consisting of all maps x → A.
An element of A^ is called a configurationconfiguration of the universe .
Thus, a configuration is a way of attaching a letter of the alphabet to each element of the universe.
If x ∈ A^ is a configuration and ⊂, 
we shall write x|_ for the restriction of x to , i.e., the element 
x|_∈ A^ defined by x|_(v) = x(v) for all v ∈. 
If X ⊂ A^,
we shall write

    X_{ x|_ : x ∈ X }⊂ A^.

Two configurations x,y ∈ A^ are said to be almost equalalmost equal configurations if they coincide outside of a finite set, i.e., there is a finite subset
Ω⊂ such that x|_∖Ω = y|_∖Ω. 
Being almost equal clearly defines an equivalence relation on  A^.
We equip the configuration set A^ with its  prodiscreteprodiscrete!— topology
  topology, that is,
the product topology obtained by taking the discrete topology on each factor
A of A^ = ∏_u ∈ A.
A neighborhood base of a configuration x ∈ A^ is given by the sets

    V(x,Ω) = V(x,Ω,,A) { y ∈ A^ : x|_Ω = y|_Ω},

where Ω runs over all finite subsets of .
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 A^ is a compact totally disconnected metrizable space.
Note that A^ is homeomorphic to the Cantor set as soon as A contains more than one element and  is infinite. 



 §.§ Group actions

An actionaction of a group G on a set X is a map
α G × X → X satisfying
α(g_1,α(g_2,x)) = α(g_1 g_2,x) and α(1_G,x) = x for all g_1,g_2 ∈ G and x ∈ X.
In the sequel, if α is an action of a group G on a set X, we shall simply   write 
g x instead of α(g,x), if there is no risk of confusion.
Suppose that a group G acts on a set X.
The orbitorbit of a point x ∈ X is the subset G x ⊂ X defined by
G x {g x : g ∈ G}.
A point x ∈ X is called periodicperiodic point if its orbit is finite.
A subset Y ⊂ X is called invariantinvariant subset
if G y ⊂ Y for all y ∈ Y.
One says that Y ⊂ X is fixedfixed subset by G if g y = 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 equivariantequivariant map 
if f(g x) = g f(x) for all g ∈ G and x ∈ X. 
Let X be a topological space. An action of a group G on X is called continuouscontinuous actionaction!continuous — if the map x ↦ g x is continuous on X for each g ∈ G.
Note that if G acts continuously on X then, for each g ∈ G,  the map x ↦ g x is a homeomorphism of X with inverse x ↦ g^-1 x. 



 §.§ 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 ∈ A^G, we define
the configuration gx ∈ A^G by

    gx  x ∘ L_g^-1,

where L_g  G → G is the left-multiplication by g.
Thus

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

Observe that, for all g_1, g_2 ∈ G and x ∈ A^G,

    g_1(g_2x) =   x ∘ L_g_2^-1∘ L_g_1^-1 = x ∘ L_g_2^-1g_1^-1 = x ∘ L_(g_1g_2)^-1 
    = (g_1g_2)x,

and 

    1_G x = x ∘ L_1_G = x ∘_G = x.

Therefore the map

    G × A^G    → A^G 
    
    (g,x)    ↦ gx

defines an action of G on A^G. 
This action is called the G-shift, or simply the shift,shift  on 
 A^G.
Observe that if two configurations x,y ∈ A^G coincide on a subset Ω⊂ G, 
then, for every g ∈ G,
the configurations g x and g y coincide on g Ω.
As the sets V(x,Ω) defined by (<ref>) 
    form a base of neighborhoods of x ∈ A^G when Ω runs over all finite subsets of G, 
    we deduce that
the map x ↦ g x is continuous  on A^G for each 
g ∈ G. Thus, the shift action of G on A^G is continuous. 



 §.§ Patterns

A patternpattern is a map p Ω→ A, where Ω is a finite subset of G.
If p Ω→ A is a pattern,
we say that Ω is the supportsupport!— of a patternpattern!support of a — of p and write Ω = (p).
Let (G,A) denote the set of all patterns.
There is a natural  action of the group G on (G,A) defined as follows.
Given g ∈ G and a pattern p ∈(G,A) with support Ω,
we define the pattern g p ∈(G,A) as being the pattern with support g Ω such that
g p(h) = p(g^-1 h) for all h ∈ g Ω.
It is easy to check that this defines  an  action of G on (G,A), i.e.,
g_1(g_2 p) = (g_1 g_2) p and 1_G p = p for all g_1, g_2 ∈ G and p ∈(G,A).
Observe that
(g p) = g (p) for all g ∈ G and p ∈(G,A).
Note also that if p is the restriction of a configuration x ∈ A^G to a finite subset 
Ω⊂ G,
then g p is the restriction of the configuration g x to g Ω.



Take G =  and let A be a finite set.
Denote by A^⋆ the set of words on the alphabet A.word
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 = a_1 a_2 ⋯ a_n, where a_i ∈ A for 1 ≤ i ≤ n and   n ∈ is the lengthlength!— of a wordword!length of a — 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 Ω⊂  of cardinality n, say
Ω = {m , m + 1, …, m + n - 1} with m ∈ and n ∈.
Then one can associate with each pattern p Ω→ A 
the word 

    w = p(m) p(m + 1) ⋯ p(m + n - 1) ∈ A^⋆.

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.




 §.§ Subshifts

A subshiftsubshift is a subset 
X ⊂ A^G that is invariant under the G-shift and closed for the prodiscrete topology on A^G.



Take G = and A = {0,1}.
Then the  subset X ⊂ A^G, consisting of all x →{0,1} such that
(x(n),x(n + 1)) ≠ (1,1) for all n ∈, is a subshift.
This subshift is called the golden mean subshift.golden mean subshiftsubshift!golden mean —




Take G =^d and A = {0,1}.
Then the  subset X ⊂ A^G, consisting of all x ∈ A^G such that
(x(g),x(g + e_i)) ≠ (1,1) for all g ∈ G, where (e_i)_1≤ i ≤ d is the canonical basis of ^d,
is a subshift.
This subshift is called the hard-ball model.hard-ball modelsubshift!hard-ball model —
For d = 1, the hard-ball model is  the golden mean subshift of the previous example. 




Take G = and A = {0,1}.
Then the subset X ⊂ A^G, consisting of all bi-infinite sequences x →{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.even subshiftsubshift!even —




Take G = ^2 and A = {0,1} = /2 (the integers modulo 2).
Then the  subset X ⊂ A^G, consisting of all x ^2 →{0,1} such that

    x(m,n) + x(m + 1,n) + x(m,n + 1) = 0

for all (m,n) ∈^2, is a subshift.
This subshift is called the Ledrappier subshift.Ledrappier subshiftsubshift!Ledrappier —




Every intersection  of subshifts and every finite union of subshifts X ⊂ A^G is itself a subshift. Therefore the subshifts X ⊂ A^G are the closed subsets of a topology on A^G. This topology is coarser (it has less open sets) than the prodiscrete topology on A^G.
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 ⊂(G,A),
it is easy to see that the subset X(P) ⊂ A^G defined by

    X(P) { x ∈ A^G  such that    (g x)|_(p)≠ p  for all   g ∈ G  and  p ∈ P }

is a subshift.
Conversely, let  X ⊂ A^G be a subshift.
One says that a pattern p ∈(G,A) 
appearspattern!— appearing in a subshiftsubshift!pattern appearing in a — in X if
p ∈ X_(p), i.e., if   there is a configuration x ∈ X
such that x|_(p) = p.
Then one easily checks that X = X(P) for

    P { p ∈(G,A)  such that     p  does not appear in     X }.

One says that a subshift X ⊂ A^G is of finite typefinite type!subshift of —subshift!— of finite type if there exists a finite subset 
P ⊂(G,A) such that X = X(P).
The  hard-ball models (and hence in particular the golden mean subshift) and the Ledrappier subshift are examples of subshifts of finite type. On the other hand, the even subshift is not of finite type. 




§ CELLULAR AUTOMATA





 §.§ Definition


Let  G be a countable group and let A, B be  finite sets.
Suppose that X ⊂ A^G and Y ⊂ B^G are two subshifts.



One says that a map τ X → Y is a
cellular automatoncellular automaton
if there exist a finite subset S ⊂ G
and a map μ A^S → B such that

    τ(x)(g) = μ((g^-1x)|_S)

for all x ∈ X and g ∈ G, where we recall that (g^-1x)|_S denotes the restriction of the configuration g^-1x ∈ X to S.
 Such a set S is called a memory setmemory setcellular automaton!memory set of a —
 and μ is called a local defining maplocal defining mapcellular automaton!local defining map of a —
 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 τ A^G → B^G.
Observe also that if S is a memory set for a cellular automaton τ X → Y and g ∈ G,
then Formula (<ref>) 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 S_1 and S_2 are memory sets then so is S_1 ∩ S_2).





Take G = and A = {0,1} = /2.
Then the map τ A^G → A^G, defined by

    τ(x)(n)  x(n + 1) + x(n)

for all x ∈ A^G and n ∈, is a cellular automaton admitting
S {0,1}⊂ as a memory set and μ A^S → A given by

    μ(p)   p(0) + p(1)

for all p ∈ A^S, as a local defining map.
Using the representation of patterns with support S by words of length 2 on the alphabet A (cf. Example <ref>), the map μ is given by

    μ(00) = μ(11) = 0  and μ(01) =  μ(10) = 1.



[Majority vote]majority votecellular automaton!majority vote —

Take G = and A = {0,1}.
Then the map τ A^G → A^G, defined by

    τ(x)(n)  
    0     if  x(n-1) + x(n) + x(n + 1) ≤ 1 
    
    1     otherwise

for all x ∈ A^G and n ∈, is a cellular automaton admitting
S {-1,0,1}⊂ as a memory set and μ A^S → 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.



A cellular automaton τ A^G → A^G, where G =, A = {0,1}, admitting S = {-1,0,1} as a memory set  is called an elementary cellular automaton.elementary!— cellular automatoncellular automaton!elementary —
Each one of these  cellular automata is uniquely determined by its local defining map
μ A^S → A, so that there are exactly 2^8 = 256
elementary cellular automata.
They are numbered from 0 to 255 according to a notation that was introduced by Wolfram (cf. <cit.>).Wolfram, Stephen
To obtain the number n of an elementary cellular automaton τ, one proceeds as follows.
One first lists all eight patterns p ∈ A^S in increasing order from 000 to 111.
The number n is the integer whose expansion in base 2 is a_8 a_7 … a_1, where a_k 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.Rule of an elementary cellular automatonelementary!Rule of an — cellular automaton
For instance, the elementary cellular automaton described in Example <ref>
is Rule 102 while the one described in Example <ref> is Rule 232.majority votecellular automaton!majority vote —




Let G be a countable group, A a finite set, and X ⊂ A^G a subshift.
Then the identity map _X  X → X is a cellular automaton with memory set
S = {1_G} and local defining map μ = _A   A^S = A^{1_G} = A → A.



Let G be a countable group, A a finite set, and X ⊂ A^G a subshift.
Let s ∈ G and denote by R_s the right-multiplication by s, that is, the map
R_s  G → G defined by R_s(h)  h s for all s ∈ G.
Then the subset Y ⊂ A^G defined by

    Y {x ∘ R_s  such that  x ∈ X }

is a subshift.
Moreover, the map τ  X → Y, defined by
τ(x)  x ∘ R_s for all x ∈ X,
is a cellular automaton with memory set S = {s} and local defining map
μ = _A  A^S = A → A.
Observe that if s is in the center  of G, then X =  Y and τ X → X is the shift map 
x ↦ s^-1 x. 




Take G = and  A = {0,1}.
Let X ⊂ A^G and Y ⊂ A^G denote respectively the golden mean subshiftgolden mean subshiftsubshift!golden mean — and the even subshift.even subshiftsubshift!even —
For x ∈ X, define τ(x) ∈ A^G by

    τ(x)(n) 
    0     if  (x(n),x(n + 1)) = (0,1)  or  (1,0) 
    
    1    if  (x(n),x(n+1)) = (0,0)

for all n ∈. It is easy to see that τ(x) ∈ Y for all x ∈ X.
The map τ X → Y is a cellular automaton admitting S {0,1}⊂ as a memory set and the map
μ A^S  → A, defined by

    μ(00) = μ(11) = 1  and μ(01) = μ(10) = 0.

Note that the map μ'  A^S → 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 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 <cit.>),  yields a global characterization of cellular automata involving only the shift actions and the prodiscrete topology on the configuration spaces.


Curtis-Hedlund-Lyndon theoremtheorem!Curtis-Hedlund-Lyndon —
Let  G be a countable group and let A,B be finite sets.
Let τ X → Y be a map from a subshift X ⊂ A^G into 
a subshift Y ⊂ B^G. 
  Then the following conditions are equivalent:


  * τ is a cellular automaton;

  * τ is equivariant (with respect to the shift actions of G) and continuous (with respect to the prodiscrete topologies).   




Suppose first that   τ X → Y is a cellular automaton.
Let S ⊂ G be a memory set  and μ A^S → B a local defining map for τ.
For all g,h ∈ G
and x ∈ X, we have that

    τ(gx)(h)    = μ((h^-1gx)|_S)       (by Formula (<ref>))
       = μ(((g^-1h)^-1x)|_S) 
       = τ(x)(g^-1h) 
       = 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 (<ref>)
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)(1_G) 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)(1_G) =
τ(x)(1_G). 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 x_0 ∈ F be such that y ∈ V(x_0, Ω_x_0,G,A), that is, y |_Ω_x_0 = x_0|_Ω_x_0.
As Ω_x_0⊂ S, we have that
y |_Ω_x_0 = z |_Ω_x_0 and therefore  τ(y)(1_G) = τ(x_0)(1_G) = τ(z)(1_G).
We deduce that  there exists  a map μ A^S → B such that τ(x)(1_G) = μ(x|_S) for all x ∈ X.
Now, for all x ∈ X and  g ∈ G, we have that

    τ(x)(g)    = (g^-1τ(x))(1_G)       (by definition of the shift action on B^G)
       = τ(g^-1x)(1_G)       (since τ is equivariant)
       = μ((g^-1 x)|_S).

This shows that   τ is a cellular automaton
with memory set S and local defining map μ.
Thus (b) implies (a).






 §.§ Operations on  cellular automata




Let G be a countable group and let A, B,C be finite sets.
Suppose  that X ⊂ A^G, 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. 



This is an immediate consequence of the characterization of cellular automata 
given by the Curtis-Hedlund-Lyndon theorem
(cf. Theorem <ref>) since the composite of two equivariant (resp. continuous) maps is itself equivariant (resp. continuous).




If we fix the countable group G, we deduce from Proposition <ref> and Example <ref>
that the subshifts 
X ⊂ A^G, with A finite,
are the objects of a concrete category _G in which  the set of morphisms from
 X ∈_G to  Y ∈_G consist of all cellular automata 
τ X → Y (cf. <cit.>). In this category, the endomorphisms of X ∈_G consist of all cellular automata 
τ X → X and they form a monoid for the composition of maps. 



Let G be a countable group and let A, B be finite sets.
Suppose  that X ⊂ A^G, 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. 



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. 




 §.§ 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 EdenGarden of Eden!— configurationconfiguration!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 ∈(G,B) is a Garden of Eden patternGarden of Eden!— patternpattern!Garden of Eden — 
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|_(p) but there is no x ∈ X such that
 p = τ(x)|_(p).
 Note that the set of GOE configurations (resp. of GOE patterns) is an invariant subset of
 Y (resp. of (G,B)). 
 Observe also that if p ∈(G,B) is a GOE pattern for the cellular automaton τ X → Y, 
then every configuration y ∈ Y such that y|_(p) = p is a GOE configuration for τ.
  


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 <ref>.majority votecellular automaton!majority vote —



 
  Let τ X → Y be a cellular automaton.
 Then the  following conditions are  equivalent:
 
 
  * τ is  surjective;
 
  * τ admits no GOE configurations;
 
  * τ admits no GOE patterns.

 


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).





 §.§ 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 ∈ A^G are called almost
equal if they coincide outside of a finite subset of G.




Let X ⊂ A^G and Y ⊂ B^G be subshifts.
One says that a cellular automaton τ X → Y is pre-injectivepre-injective!— cellular automatoncellular automaton!pre-injective — if
there are no distinct configurations x_1, x_2 ∈ X that are almost equal and satisfy τ(x_1) = τ(x_2).


A pair of configurations  (x_1,x_2)  ∈ X × X
is called a diamonddiamond  
if x_1 and x_2 are distinct,  almost equal,  and have the same image under τ
(cf. <cit.>).
Thus, pre-injectivity is equivalent to absence of diamonds.
If (x_1,x_2) is a diamond, the nonempty finite subset

    {g ∈ G: x_1(g) ≠ x_2(g) }⊂ G

is called the supportsupport!— of a diamonddiamond!support of a — of the diamond (x_1,x_2).
Every injective cellular automaton is clearly pre-injective.
The converse is false, as shown by the following examples. 


Take G =, A = {0,1} = /2, and consider the cellular automaton τ A^G → A^G described in Example <ref> (Rule 102 in Wolfram's notation).
Then τ is pre-injective.
Indeed, it is clear that if two configurations x, x' ∈ A^G coincide on ∩ (-∞,n_0] for some n_0 ∈ and satisfy τ(x) = τ(x') then x = x'.
However, τ is not injective since the two constant configurations have the same image.




Consider the cellular automaton τ X → Y from the golden mean subshift to the even subshift described in Example <ref>.golden mean subshiftsubshift!golden mean —even subshiftsubshift!even —
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 p_1, p_2 ∈ X_Ω 
two   patterns with support Ω appearing in X. 
One says that the patterns p_1 and p_2 are mutually erasablemutually erasable patterns with respect to τ,
briefly ME,
 provided the following hold:
 

  * the set

    X_p_1,p_2{(x_1, x_2) ∈ X × X:
    x_1 |_Ω = p_1, x_2 |_Ω = p_2  x_1 |_G ∖Ω = x_2 |_G ∖Ω}

is nonempty;

  * for all (x_1, x_2) ∈  X_p_1,p_2 one has τ(x_1) = τ(x_2).

Note that “being ME" is an equivalence relation on X_Ω. This equivalence relation is not trivial in general.

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 <ref>.majority votecellular automaton!majority vote —


Observe that  if the patterns p_1 and p_2
are ME, then so are gp_1 and gp_2 for all g ∈ G.



Let τ X → Y be a cellular automaton.
Then the  following conditions are equivalent:


  * τ is pre-injective;

  * τ admits no distinct ME patterns.



 
Suppose first that τ admits two distinct ME patterns p_1 and p_2. 
Let Ω denote their  common support.
Take  (x_1, x_2) ∈  X_p_1,p_2.
Then the configurations x_1 and x_2  are almost equal since they coincide outside of Ω. 
Moreover, they satisfy  x_1 ≠ x_2 and τ(x_1) = τ(x_2).
Therefore (x_1,x_2) 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 (x_1,x_2) ∈ X × X. 
Let Δ denote the support of this diamond  
and  let S ⊂ G be a memory set for τ with 1_G ∈ S. 
Consider the set  ΩΔ S^-1 S.
 We claim that the patterns p_1  x_1|_Ω and p_2  x_2|_Ω are distinct ME patterns.
First observe that p_1 ≠ p_2 since ∅≠Δ⊂Ω. 
Moreover, X_p_1,p_2 is nonempty since, by construction, (x_1, x_2) ∈ X_p_1,p_2.
To complete  the proof, we only need to show the following: if (y_1, y_2) ∈ X_p_1,p_2 
then τ(y_1) = τ(y_2).
Let g ∈ G. Suppose first that g ∈ G ∖Δ S^-1. Then gS ∩Δ = ∅. Since y_1 and y_2 coincide on G ∖Δ,
we deduce that

    τ(y_1)(g) = τ(y_2)(g)   for all  g ∈ G ∖Δ S^-1.

Suppose now that g ∈Δ S^-1. Then gS ⊂Δ S^-1S = Ω.
As y_1|_Ω = p_1 = x_1|_Ω (resp. y_2|_Ω = p_2 = x_2|_Ω), by construction, we deduce that

    τ(y_1)(g) =  τ(x_1)(g) = τ(x_2)(g) = τ(y_2)(g)   for all  g ∈Δ S^-1.

From (<ref>) and (<ref>) we deduce that τ(y_1) = τ(y_2).





§ THE GARDEN OF EDEN THEOREM FOR ^D



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


Garden of Eden theorem!— (for ^d)theorem!Garden of Eden — (for ^d)
Let A be a finite set, d ≥ 1 an integer, and τ A^^d→ A^^d a cellular automaton.
Then the following conditions are equivalent:


  * τ is surjective;

  * τ is pre-injective.



The implication (a)  (b) is due to Moore <cit.>Moore, Edward F. and the converse to Myhill <cit.>.Myhill, John R.
We shall prove the contraposite of each implication.
Before undertaking the proof of Theorem <ref>, let us first introduce some notation and establish some preliminary results.
Let S⊂^d be a memory set for τ.
Since any finite subset of ^d 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


    Ω_m^+ {-r,-r+1,…, m+r-1}^d

and 

    Ω_m^- {r,r+1,…, m-r-1}^d,

so that

    |Ω_m| = m^d,    |Ω_m^+| = (m+2r)^d,   |Ω_m^-| = (m-2r)^d.

Observe that if two configurations x_1,x_2∈ A^^d coincide on Ω_m 
(resp. Ω_m^+, resp. ^d ∖Ω_m^-) then
τ(x_1) and τ(x_2) coincide on Ω_m^- (resp. Ω_m, resp. ^d ∖Ω_m).
Also, let us set, for all  integers k,n ≥ 1

    T_n^k {t=(t_1k, t_2k, …, t_dk)∈^d: 0 ≤ t_j ≤ n-1},

and observe that the n^d cubes  t + Ω_k, for t running over T_n^k,
form a partition of the cube Ω_n k.
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 <ref> we shall make use of the following elementary result
(here one should think of a:=|A| as to the cardinality of the alphabet set and a^(n k )^d
(resp. a^(n k - 2r)^d, for n k ≥ 2r) as to the number of all patterns supported by Ω_n k
(resp. Ω_n k^-), cf. (<ref>).


Let a,k,d,r be positive integers with a ≥ 2. 
Then there exists n_0 = n_0(a,k,d,r) ∈ such that

    (a^k^d - 1)^n^d < a^(n k - 2r)^d

for all n ≥ n_0.



Taking logarithms to base a, Inequality (<ref>) is equivalent to

    log_a(a^k^d - 1) < (k - 2r/n)^d.

Since

    log_a(a^k^d - 1) < log_a(a^k^d) = k^d = lim_n →∞(k - 2r/n)^d,

we deduce that there exists n_0 ∈ such that (<ref>) and therefore (<ref>) are satisfied for all n ≥ n_0.



We can assume that a  |A| ≥ 2.
Suppose first that τ is not pre-injective.
Then, by Proposition <ref>, τ admits two distinct ME patterns,
say p_1 and p_2.
Denote by Ω⊂^d their common support.
Since, for all t ∈^d, the patterns t p_1 and t p_2 (with support t + Ω) are also distinct and ME, and any finite subset of ^d 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 ≥ 2 r.
As the patterns t p_1 and t p_2 are ME, we have

    | A^t+Ω_k/∼ | ≤| A^t+Ω_k| - 1 = a^k^d-1

for all t ∈^d.
Now observe that two patterns with support  
Ω_n k are ME if  their restrictions to
t+Ω_k are ME for every  t ∈ T_n^k.
Using (<ref>), we deduce that

    | A^Ω_n k/∼| ≤∏_t ∈ T_n^k |A^t + Ω_k/∼| ≤  (a^k^d-1)^n^d.

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

    |τ(A^^d)_Ω_n k^-|  ≤ | A^Ω_n k / ∼ |  
    ≤  (a^k^d-1)^n^d < a^(n k - 2r)^d = | A^Ω_n k^- |.

This implies that τ(A^^d)_Ω_n k^-⫋ A^Ω_n k^-, 
so that there must  exist a GOE pattern for τ with support Ω_n k^-.
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 <ref>, there exists a GOE pattern p for τ.
Since tp is a GOE pattern for every t ∈^d, and any finite subset of ^d 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 Ω_n k into the n^d translates t+Ω_k, with t ∈ T_n^k, and observe that
tp ∈ A^t+Ω_k is GOE for every t ∈ T_n^k.  Any pattern q ∈ A^Ω_n k which is not GOE satisfies that
q|_t+Ω_k is not GOE for every t ∈ T_n^k. As a consequence, we have
that

    | τ(A^^d)_Ω_n k| 
    ≤∏_t ∈ T_n^k| τ(A^^d)_t + Ω_k| 
    ≤   (a^k^d -1)^n^d.

Let us fix now some element a_0 ∈ A and consider the set X consisting of all configurations 
x ∈ A^^d that satisfy

    x(g) = a_0   for all   g ∈^d ∖Ω_n k^-.

Observe that if x_1 and x_2 are in   X, then τ(x_1) and τ(x_2) coincide on 
^d ∖Ω_n k.
It follows that

    |τ(X)| = | τ(X)_Ω_n k|.

On the other hand, taking n ≥ n_0(a,k,d,r) and using (<ref>), 
we get

    | τ(X)_Ω_n k| 
    ≤| τ(A^^d)_Ω_n k| 
    ≤ (a^k^d -1)^n^d
    < a^(n k - 2r)^d = | A^Ω_kn^- | = |X|

and hence

    |τ(X)| < |X|.

By the pigeon-hole principle, this implies  that there exist two distinct configurations x_1,x_2 ∈ X such that τ(x_1) = τ(x_2).
As all configurations in X are almost equal,
we deduce that   τ is not pre-injective.
This shows that (b)  (a).



The proof of the implication (a)  (b) shows that if τ admits two distinct ME patterns supported by a
cube of side k ≥ 2 r, then a cube of side n k -2r, with n ≥ n_0(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 ≥ 2 r, then a cube of side kn+2r, with n ≥ n_0(a,k,d,r), supports two distinct ME patterns.
Indeed, the proof shows the existence of two configurations
x_1,x_2 ∈ A^^d that coincide outside of  Ω_n k^-
and satisfy  τ(x_1) = τ(x_2). It then follows from the proof of the implication (b)  (a) in
Proposition <ref>  that the set 

    (Ω_n k^- +(- S))+S = Ω_n k + S = Ω_n k^+
 
supports two distinct ME patterns.





§ THE GARDEN OF EDEN THEOREM FOR GENERAL AMENABLE GROUPS





 §.§ Amenability

 
(cf. <cit.>, <cit.>, <cit.>, <cit.>)


A countable group G is called amenableamenable groupgroup!amenable — if there exists a sequence (F_n)_n ∈ of nonempty finite subsets of G such that

    lim_n →∞| F_n ∖  F_n g|/| F_n | = 0   for all  g ∈ G.

 Such a sequence is called a Følner sequenceFø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 (<ref>) is equivalent to each of the following conditions:

    lim_n →∞|  F_n g ∖  F_n |/| F_n | = 0   for all  g ∈ G,

or

    lim_n →∞|  F_n △  F_n g |/| F_n | = 0   for all  g ∈ G.



All finite groups are amenable. Indeed, if G is a finite group, then the constant sequence, 
defined by F_n G for all n ∈,  is  a Følner sequence for G since F_n ∖  F_n g = ∅ 
for every g ∈ G.




The free abelian groups of finite rank ^d, d ≥ 1,  are also amenable.
As a Følner sequence for ^d, one can take for instance the sequence of cubes 

    F_n {x ∈^d: ‖ x ‖_∞≤ n} = {0,± 1,  …,± n}^d,

where ‖ x ‖_∞max_1 ≤ i ≤ d |x_i| for all x = (x_1,…,x_d) ∈^d is the sup-norm.
To see this, observe that

    |F_n| = (2n + 1)^d
 
and, by the triangle inequality, 

    F_n + g ⊂ F_n + ‖ g ‖_∞  for all  g ∈^d.

Since

    F_n ⊂ F_n + ‖ g ‖_∞,

this implies

    |( F_n + g) ∖ F_n| ≤  (2n + ‖ g ‖_∞ + 1)^d - (2n + 1)^d.

As the right-hand side of (<ref>) is a polynomial of degree d - 1 in n
while |F_n| is a polynomial of degree d in n by (<ref>), we conclude that

    lim_n →∞| ( F_n + g ) ∖  F_n |/| F_n | = 0,

which is (<ref>) in additive notation.


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

    γ(G,S) lim_n →∞√(|B_n|)

exists and satisfies 1 ≤γ(G,S) < ∞.
One says that the group G has subexponential growthsubexponential growthgroup!— of subexponential growth if
γ(G,S) = 1 and  exponential growthexponential growthgroup!— of 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.

 
The groups ^d have subexponential growth.
Indeed, if e_1,…,e_d is the canonical basis of ^d,
and we take S {± e_1, …, ± e_d}, then
the graph distance between two vertices g and h of (^d,S) is 
‖ g - h ‖_1, where we write
‖ x ‖_1 ∑_1 ≤ i ≤ d |x_i| for the 1-norm of x = (x_1,…,x_d) ∈^d.
 We then have

    B_n =  {g ∈^d : ‖ g ‖_1 ≤ n}⊂{0,± 1, …,± n}^d

and hence
|B_n| ≤  (2 n + 1)^d.
This implies that ^d has subexponential growth.
Here it can be checked that the sequence  (B_n)_n ∈ is also a Følner sequence for ^d.


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 
(B_n)_n ∈.  
Consequently, every finitely generated group with subexponential growth is amenable.



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,reduced form of an element of a free group i.e., in the form

    g = s_1 s_2 … s_n,

where n ≥ 0,  s_i ∈ S for all 1 ≤ i ≤ n, and s_i + 1≠ s_i^-1 for all 1 ≤ i ≤ n - 1.
The integer ℓ_S(g)  n is called the lengthlength!— of an element in a free group of g with respect to the generators a and b.  
It is equal to the distance from g to 1_G in the Cayley graph (G,S).
We deduce that  |B_n| = 4 · 3^n - 1 for all n ≥ 1 so that
  
    γ(G,S) = lim_n →∞√(4 · 3^n - 1) =  3 > 1.

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

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

Denote,
for each s ∈ S, 
by  G_s the subset of G consisting of all elements
 g ≠ 1_G 
whose reduced form   ends with the letter 
s^-1.
The four   sets G_s, s ∈ S, are pairwise disjoint
so that

    ∑_s ∈ S |F ∩ G_s| ≤ |F|.

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

    |F| = |F ∖ G_s| + |F ∩ G_s| =  |(F ∖ G_s) s| + |F ∩ G_s|.

 We now observe that  

    (G ∖ G_s) s ⊂ G_s^-1

so that

    (F ∖ G_s) s ⊂ (F s ∖ F) ∪ (F ∩ G_s^-1)

and hence

    |(F ∖ G_s) s|    ≤ |F s ∖ F| + |F ∩ G_s^-1|  
       = |F ∖  F s| +  |F ∩ G_s^-1| 
       ≤ε |F| +  |F ∩ G_s^-1|       (by (<ref>)).

By using   (<ref>), we deduce that

    |F| ≤ε |F| +  |F ∩ G_s^-1| + |F ∩ G_s|

for all s ∈ S.
After summing up over all s ∈ S, this yields

    4|F|    ≤ 4ε |F| +  ∑_s ∈ S( |F ∩ G_s^-1| + |F ∩ G_s| ) 
       = 4ε |F| +  2∑_s ∈ S |F ∩ G_s|.

Finally, combining with (<ref>),   we  obtain

    4|F| ≤ 4 ε |F| + 2 |F|

and hence |F| ≤ 2 ε |F|,  which is a contradiction since F ≠∅ 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 (n,), 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 <cit.>
where Ol'šanskiĭOl'šanskiĭ, Alexander Yu. constructed a nonamenable monster groupmonster groupgroup!monster — 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 groupBaumslag-Solitar groupgroup!Baumslag-Solitar — 
BS(1,2), i.e.,  the group with presentation  ⟨ a,b : a b a^-1 = b^2 ⟩, and the 
lamplighter group,lamplighter groupgroup!lamplighter —
i.e., the wreath product (/2)≀, 
have exponential growth but  are both solvable and hence amenable 
(cf. <cit.>).
The original definition of amenability that was given by von Neumann <cit.>von Neumann, John  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 <cit.>Day, Mahlon M. 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 <cit.> that the term amenableamenable group occured for the first time
 (see <cit.>).
The fact that nonabelian free groups are not amenable is related to  the Hausdorff-Banach-Tarski paradoxHausdorff-Banach-Tarski paradox which actually was the motivation of von Neumann for introducing the notion of amenability.



 §.§ Entropy

Let G be  countable group, A a finite set, and X a subset
of A^G (not necessarily a subshift).
Given a finite subset Ω⊂ G, recall (cf. (<ref>)) that

    X_Ω{x|_Ω: x ∈ X}⊂ A^Ω.

Suppose now that the group G is amenable and fix a Følner sequence = (F_n)_n ∈ for G.
The entropyentropysubshift!entropy of a — of X (with respect to ) is defined by

    h_(X) lim sup_n →∞log |X_F_n|/|F_n|.

Since X_F ⊂ A^F and hence log |X_F| ≤ |F| ·log |A| for every finite subset F ⊂ G, we always have

    h_(X) ≤ h_(A^G) = log |A|.
 


Take G = and  A = {0,1}.
Let us compute the entropy of the golden mean subshift X ⊂ A^Gentropy!— of the golden mean subshiftgolden mean subshift!entropy of the —subshift!golden mean — 
(cf. Example <ref>) with respect to the Følner sequence
= (F_n)_n ∈, where F_n {0,1,…,n}.
We observe that   u_n  |X_F_n| satisfies u_0 = 2, u_1 = 3, and
u_n + 2 = u_n + 1 + u_n for all n ≥ 2. Thus, the sequence (u_n)_n ∈ is a Fibonacci sequence and, by Binet's formula,

    u_n = 1/√(5)(φ^n + 3 - (1 - φ)^n + 3),

where φ  (1 + √(5))/2 is the golden mean (this is the origin of  the name of this subshift). It follows that

    h_(X) = lim sup_n →∞log u_n/n + 1 = logφ.




Take again G = and  A = {0,1},
and let us compute now the entropy of the even subshift X ⊂ A^Gentropy!— of the even subshifteven subshift!entropy of the —subshift!even —  
(cf. Example <ref>) with respect to the Følner sequence
= (F_n)_n ∈, where F_n {0,1,…,n}.
We observe that   u_n  |X_F_n| satisfies u_0 = 2, u_1 = 4, and
u_n + 2 = 1 + u_n + 1 + u_n for all n ≥ 2. Thus, the sequence (v_n)_n ∈,
defined by v_n   1 + u_n for all n ∈,  is a Fibonacci sequence.
As v_0 = 3 and v_1 = 5,  by applying again Binet's formula, we get

    u_n = - 1 + v_n = - 1 + 1/√(5)(φ^n + 5 - (1 - φ)^n + 5),

where φ is the golden mean.
 It follows that

    h_(X) = lim sup_n →∞log u_n/n + 1 = logφ.

Thus, the even subshift has the same entropy as the golden mean subshift with respect to .




Take G = ^2 and  A = /2.
Let us compute the entropy of the Ledrappier subshiftentropy!— of the Ledrappier subshiftLedrappier subshift!entropy of the —subshift!Ledrappier — 
X ⊂ A^G (cf. Example <ref>) with respect to the Følner sequence
= (F_n)_n ∈, where F_n {0,1,…,n}^2.
We observe that, for each x ∈ X, the pattern x|_F_n is entirely determined by 
x |_H_n, where H_n ⊂^2 is the horizontal interval
H_n {0,1, …,2n}×{0}. 
Therefore,    u_n  |X_F_n| satisfies

    log u_n ≤ |H_n| ·log|A| = (2n + 1) log 2.

This gives us

    h_(X) = lim sup_n →∞log u_n/(n + 1)^2 = 0.




It is a deep result due to OrnsteinOrnstein, Donald S. and Weiss <cit.>Weiss, Benjamin that,
when G is a countable amenable group, A a finite set, and X ⊂ A^G  a subshift, 
then the lim sup in (<ref>) is actually a true limit and does not depend on the
particular choice of the Følner sequence  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.



Let G be a countable amenable group with Følner sequence = (F_n)_n ∈ and
A,B  finite sets. 
Suppose that  τ A^G → B^G 
is a cellular automaton and X is a subset of A^G. 
Then one has h_(τ(X)) ≤ h_(X).


For the proof, we shall use the following general property of Følner sequences.



Let G be a countable amenable group with Følner sequence = (F_n)_n ∈ and
let S be a finite subset of G.
Then one has

    lim_n →∞|F_n S ∖ F_n|/|F_n| = 0.




Observe that

    F_n  S ∖ F_n = ⋃_s ∈ S (F_n  s ∖ F_n)

so that

    |F_n  S ∖ F_n| = | ⋃_s ∈ S (F_n  s ∖ F_n)  | 
    ≤∑_s ∈ S |F_n  s ∖ F_n|.

Thus we get

    |F_n S ∖ F_n|/|F_n|≤∑_s ∈ S|F_n s ∖ F_n|/|F_n|

for all n ∈. As 

    lim_n →∞|F_n s ∖ F_n|/|F_n| = 0

for each s ∈ S by (<ref>), this gives us (<ref>). 




Let us set Y τ(X) and let S ⊂ G be a memory set for τ
with 1_G ∈ S.
Recall that it immediately follows from (<ref>)  that if two configurations coincide on 
g S for  some g ∈ G  then their images by τ take the same value at g.
We deduce  that

    |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 F_n  and dividing both sides by |F_n|, this inequality becomes   
 
    log |Y_F_n|/|F_n|≤log |X_F_n|/|F_n| +
      |F_n S ∖ F_n|/|F_n|·log |A|.

As 

    lim_n →∞|F_n S ∖ F_n|/|F_n| = 0

by Lemma <ref>, taking the limsup in (<ref>) finally gives the required inequality h_(Y) ≤ h_(X).




Let G be a countable amenable group and let
A,B be  finite sets with |A| < |B|.
Then there exists no surjective cellular automaton τ A^G → B^G. 



This is an immediate consequence of 
Proposition <ref>
since

    h_(A^G) = log |A| < log |B| = h_(B^G).



The following example (cf. <cit.>)  shows that 
Corollary <ref> becomes false if  
 the amenability hypothesis is removed.
 
 
 Let G be the free group on two generators a and b.
 Take A /2 and B /2×/2, so that |A| = 2 and |B| = 4.
 Consider the map τ A^G → B^G defined by
 
    τ(x)(g) = (x(g) + x(g a), x(g) + x(g b))
  
 for all x ∈ A^G and g ∈ G.
 Observe that τ is a cellular automaton with memory set S = {1_G,a,b} and local defining map
μ A^G → B given by
 
    μ(p) = (p(1_G) + p(a),p(1_G) + p(b))

  for all p ∈ A^S. It is easy to check that τ is surjective.
Note that A^G 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 A^G.
 



 §.§ Tilings


Let G be a group. 
Given a finite subset E⊂ G, let us say that a subset T ⊂ G is an E-tilingtiling of G provided the sets t E, t ∈ T, are pairwise disjoint and there exists a finite subset
E' ⊂ G such that the sets    t E', t ∈ T,  cover G.


Take G = ^d and E = {0, ± 1, ± 2, …, ± m}^d for some m ∈, then T: = ((2m+1))^d  ⊂^d 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 𝒮(E) consisting of all subsets S ⊂ G such that the sets sE, s ∈ S, are pairwise disjoint.
We first observe that 𝒮(E) 
is nonempty 
since {1_G}∈𝒮(E).
On the other hand, 𝒮(E)
is inductive  with respect to set inclusion since  
if 𝒮' ⊂𝒮(E) is a chain, then M:= ∪_S ∈𝒮' S belongs to
𝒮(E) and is an upper bound for 𝒮'. By Zorn's lemma, there exists a maximal element T ∈𝒮(E). 
As T ∈𝒮(E),
 the sets t E, 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 
 g E ∩ t E ≠∅ and hence
g ∈ t E E^-1.
It follows that the sets t E E^-1, t ∈ T, cover G. 
Since the set E'  E E^-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.



Let G be a countable amenable group with Følner sequence  = (F_n)_n ∈.
Let E ⊂ G be a nonempty finite subset and
T ⊂ G an E-tiling. 
Define, for  n ∈, the subset T_n ⊂ T  by
 
    T_n {t ∈ T: t E ⊂ F_n}.

Then there exist   a constant 
α = α(,T) >0 and n_0 ∈ such that

    |T_n| ≥α |F_n|    n ≥ n_0.





Since T is a E-tiling, there exists a finite subset E' ⊂ G such that the sets t E', t ∈ T, cover G.
After replacing E' by E' ∪ E, if necessary, we may assume that E ⊂ E'.  
Define, for n ∈,

    T_n^+ {t ∈ T: tE' ∩ F_n ≠∅}.

Clearly T_n ⊂ T_n^+.
As the sets tE', t ∈ T_n^+, cover F_n, we have
|F_n| ≤ |T_n^+| · |E'| so that

    |T_n^+|/|F_n|≥1/|E'|

for all n ∈.
Now observe that

    T_n^+ = T ∩(⋃_g ∈ E' F_n g^-1)
      and  
    T_n = T ∩(⋂_h ∈ E  F_n h^-1),

so that

    T_n^+ ∖ T_n
       = T ∩( ⋃_g ∈ E' F_n g^-1∖⋂_h ∈ E  F_n h^-1)  
       ⊂⋃_g ∈ E' F_n g^-1∖⋂_h ∈ E  F_n h^-1
       = ⋃_g ∈ E',  h ∈ E (F_n g^-1∖ F_n h^-1).
 

We deduce that

    |T_n^+ ∖ T_n|
    ≤∑_g ∈ E',  h ∈ E |F_n g^-1∖ F_n h^-1|
    = ∑_g ∈ E',  h ∈ E |F_n   ∖ F_n h^-1 g|.

As

    lim_n →∞|F_n  ∖ F_n h^-1 g|/|F_n| =0

 for all g ∈ E' and h ∈ E by (<ref>),  
 it follows that

    |T_n^+ | - | T_n |/|F_n| = | T_n^+ ∖ T_n |/|F_n|→ 0

as  n →∞. 
Using (<ref>) and taking ε12|E'|, 
we deduce that  there exists n_0 ∈ such that

    |T_n|/|F_n| = |T_n^+|/|F_n| - | T_n^+ | - | T_n |/|F_n|≥1/|E'| - ε = α,

where α12|E'|, for all n ≥ n_0. 





Let G be a countable amenable group with Følner sequence  = (F_n)_n ∈
and let A be a finite set.  
Let X ⊂ A^G be a subset and suppose there exist a nonempty finite subset E ⊂ G
and an E-tiling T ⊂ G such that X_tE⫋ A^tE for all t ∈ T. Then h_(X) < log |A|.



Let us set, as above, T_n {t ∈ T: tE ⊂ F_n} and write 

    F_n^*  F_n ∖⋃_t ∈ T_n t E,
 
for all n ∈.
Observe that ⋃_t ∈ T_n t E ⊂ F_n so that 

    X_F_n⊂ A^F_n^*×∏_t ∈ T_n X_tE
 
and

    |F_n| = |F_n^*| + |T_n| · |E|.

 It follows that

    log |X_F_n|    ≤| F_n^*|·log |A| +  ∑_t ∈ T_nlog |X_tE| 
       ≤  |F_n^*| ·log |A| +  ∑_t ∈ T_nlog(|A^tE|-1) 
        = | F_n^* |·log |A| +  |T_n| ·log (|A|^|E| - 1) 
        = | F_n^* |·log |A| +  |T_n| · |E| ·log |A| + |T_n| ·log (1 - |A|^-|E|)
        = | F_n |·log |A| + |T_n| ·log (1 - |A|^-|E|),

where the last equality follows from (<ref>).
Setting c - log (1 - |A|^-|E|) > 0,  
we deduce that

    h_(X) = lim sup_n →∞log |X_F_n|/|F_n|≤log |A| - c α < log |A|,

where α = α(,T) is as in (<ref>).




Let G be a countable amenable group with Følner sequence  = (F_n)_n ∈
and let A be a finite set.  
Let X ⊂ A^G be a subshift 
and suppose that there exists a nonempty finite subset E ⊂ G
such that X_E⫋ A^E.  Then one has h_(X) < log |A|.



If T is an E-tiling of G,
we deduce from the shift-invariance of X
that
X_t E⫋ A^t E for all t ∈ T, so that Proposition <ref> applies. 




 §.§ The Garden of Eden theorem for amenable groups

The following result is due to Machì,  Scarabotti, and the first author <cit.>.
Since the groups ^d are all amenable,
it extends Theorem <ref>. 


Garden of Eden theorem!— (for amenable groups)theorem!Garden of Eden — (for amenable groups)
Let G be a countable amenable group with Følner sequence   
= (F_n)_n ∈ and A a finite set.
Suppose that τ A^G → A^G is a cellular automaton. Then the following conditions are
equivalent:


  * τ is surjective;

  * h_(τ(A^G)) = log |A|;

  * τ is pre-injective.




The implication (a)  (b) is obvious  since h_(A^G) = log|A|.
In order to show the converse implication, let us suppose that τ is not surjective, that is,
the image subshift X τ(A^G) is such that  X ⫋ A^G.
Since X is closed in A^G,
there exists  a finite subset E ⊂ G such that
X_E ⫋ A^E.
By applying Corollary <ref>,
we deduce that
h_(X)  < log|A|. This shows (b)  (a).
Let S ⊂ G be a memory set for τ such that 1_G ∈ S.
Let us  show (b)  (c). Suppose that τ is not pre-injective. By virtue of
Proposition <ref>, we can find
a nonempty finite subset Ω⊂ G and two distinct patterns p_1, p_2 ∈ A^Ω
that are mutually erasable for τ.
Let E Ω S^-1S.
Observe that Ω⊂ E since 1_G ∈ S.
Let  T ⊂ G be an E-tiling of G.
Consider the subset Z ⊂ A^G defined by

    Z{z ∈ A^G: z|_t Ω≠ tp_1  t ∈ T}.

Observe that Z_tE⫋ A^t E for all t ∈ T.
By using Proposition <ref> and Proposition <ref>, we deduce that h_(τ(Z))  ≤ h_(Z) < log |A|.
We claim that τ(Z) = τ(A^G). Let x ∈ A^G. Let T_x{t ∈ T: x|_tΩ = tp_1} and define
z ∈ Z by setting, for all g ∈ G,

    z(g) 
    tp_2(g)    
    
    x(g)

Let us check that τ(z) = τ(x). Let g ∈ G.
If g ∉∪_t ∈ T_x tΩ S^-1, then gS ∩ tΩ = ∅ for all t ∈ T_x 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) ∈ T_x and consider the
configuration y ∈ A^G defined by setting, for all h ∈ G,

    y(h) 
    tp_2(h)     h ∈ tΩ
    
    x(h)

Observe that x|_G ∖ tΩ = y|_G ∖ tΩ. Since the patterns x|_tΩ = tp_1 and y|_tΩ = tp_2 are mutually erasable, we deduce that τ(y) = τ(x). Moreover, as gS ⊂  tΩ S^-1S = 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 h_(τ(A^G)) = h_(τ(Z)) < log |A|. This shows the implication (b) 
 (c).
Finally, let us show  (c)  (b).
Let us set as above X τ(A^G) and suppose that h_(X) < log |A|.
As 1_G ∈ S, we have F_n ⊂ F_n S^-1 so that

    X_F_n S^-1⊂ X_F_n× A^F_n S^-1∖ F_n,

for all n ∈.
We deduce that

    log |X_F_n S^-1|/|F_n|≤log |X_F_n|/|F_n|
    +  |F_n S^-1∖ F_n|/|F_n|log |A|.

As

    lim_n →∞|F_n S^-1∖ F_n|/|F_n| =0

by Lemma <ref>,
we deduce from (<ref>) that

    lim sup_n →∞log |X_F_n S^-1|/|F_n|≤lim sup_n →∞log |X_F_n|/|F_n|
    = h_(X) < log |A|.

Consequently, we can find n_0 ∈ such that,

    |X_F_n_0 S^-1| < |A|^|F_n_0|.

Fix a_0 ∈ A and consider the subset Z ⊂ A^G defined by

    Z{z ∈ A^G: z(g) = a_0  g ∈ G ∖ F_n_0}.

Note that |Z| = |A|^|F_n_0|.
Let z_1, z_2 ∈ Z.
If g ∈ G ∖ F_n_0 S^-1, then z_1 and z_2 coincide on gS ⊂ G ∖ F_n_0 so that τ(z_1)(g) = τ(z_2)(g).
Therefore τ(z_1) and τ(z_2) coincide on G ∖ F_n_0S^-1.
This implies  that  |τ(Z)| ≤ |X_F_n_0 S^-1|.
Using (<ref>),
we deduce that |τ(Z)| < |Z|.
By the pigeon-hole principle, there exist two distinct elements z_1, z_2 ∈ Z such that
τ(z_1) = τ(z_2).
As all elements in Z are almost equal (they coincide outside of the finite set F_n_0),
we conclude that τ is not pre-injective.





§ FAILURE OF THE GARDEN OF EDEN THEOREM FOR NONAMENABLE GROUPS



Let us say that a countable group G has the Moore propertyMoore property!— for a groupgroup!— satisfying the Moore property  if 
every surjective cellular automaton τ A^G → A^G with finite alphabet A over G is 
pre-injective
and that it has the Myhill propertyMyhill property!— for a groupgroup!— satisfying the Myhill property  if
every pre-injective cellular automaton τ A^G → A^G with finite alphabet A over G is surjective.
Also let us  say that a countable group G satisfies the Moore-Myhill propertyMoore-Myhill property!— for a groupgroup!— satisfying the Moore-Myhill property 
or that it satisfies the Garden of Eden theoremGarden of Eden theorem!group satisfying the —group!— satisfying the Garden of Eden theorem 
  if G has both the Moore and the Myhill properties.
Theorem <ref>
tells us that every countable amenable group satisfies the Garden of Eden theorem.
The examples below, essentially due to Muller <cit.>Muller, David E.
(see also <cit.>, <cit.>, <cit.>), 
show that neither the Moore nor the Myhill property holds for countable groups containing  nonabelian free subgroups.




 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 τ A^G → A^G 
with memory set {1_G}∪ S
defined by

    τ(x)(g) 
    0     if  x(g) + x(ga) + x(ga^-1) + x(gb) + x(gb^-1) ≤ 2 
    
    1     otherwise

for all x ∈ A^G and g ∈ G.
The pair of configurations (x_1, x_2) ∈ A^G × A^G, defined by x_1(g) = 0 for all g ∈ G, and x_2(g) = 0 for all g ∈ G ∖{1_G} and x_2(1_G) = 1, is a diamond for τ. 
Therefore τ is not pre-injective.
However, τ is surjective.  To see this, let y ∈ A^G. Let us show that there exists x ∈ A^G 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 = r h with r ∈ R and h ∈ H. 
If g ∈ R, i.e., h = 1_G, 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 <ref>).
One easily checks that  τ(x) = y. This shows that τ is surjective.
Thus the Moore implication fails to hold for  groups containing nonabelian free subgroups.




 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 = /2×/2 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 τ A^G → A^G 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 ∈ A^G and g ∈ G.
The image of τ is contained in (/2×{0})^G. Therefore τ is not surjective.
We claim that τ is pre-injective. As τ is a group endomorphism of A^G, 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 ∈ A^G with nonempty finite support 
Ω{g ∈ G : x(g) ≠ 0_A }⊂ 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 ≠∅
and consider an element g = r h ∈Ω_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 x(g) = (α,β) ≠ (0,0) = 0_A.
Suppose first that α≠ 0.
We can find s ∈{a,a^-1} such that ℓ_S(h s) = ℓ_S(h) + 1.
For all t ∈ S ∖{s^-1},
we have that  ℓ_S(h s t) = ℓ(h) + 2 and hence
x(g s t) = 0_A by maximality.
It follows that

    τ(x)(g s) = p(x(g ) )= (α,0) ≠ 0_A,

which contradicts the fact that x is in the kernel of τ.
Suppose now that α = 0.
Then β≠ 0.
We take now s ∈{b,b^-1} such that
ℓ_S(h s) = ℓ_S(h) + 1.
By an argument similar to the one that we used in the first case, we get

    τ(x)(g s) = q(x(g ) )= (β,0) ≠ 0_A,

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 <ref>,
there are nonamenable countable groups containing no nonabelian free subgroups.
However, Bartholdi <cit.>Bartholdi, Laurent (see <cit.>) proved that
the Moore property fails to hold for all nonamenable countable groups.
Recently, Bartholdi 
and Kielak <cit.> 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 <ref>),
this yields the following characterization of amenability in terms of cellular automata. 


Let G be a countable group.
Then the following conditions are equivalent:


  * G is amenable;

  * G has the Moore property;

  * G has the Myhill property;

  * G satisfies the Garden of Eden theorem.







§ THE GARDEN OF EDEN THEOREM FOR SUBSHIFTS





 §.§ Strongly irreducible subshifts

Let G be a countable group and A a finite set.
A subshift X ⊂ A^G is called strongly irreduciblestrongly irreducible subshiftsubshift!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 x_1,x_2 ∈ X, there exists  a configuration x ∈ X which coincides with x_1 on Ω_1 and with x_2 on Ω_2.


The full shift A^G is strongly irreducible (one can take Δ = {1_G}).



The even subshift X ⊂{0,1}^, described in Example <ref>, is strongly irreducible
(one can take Δ = {-2,-1,0,1,2}).even subshiftsubshift!even —



The hard-ball model,  described in Example <ref>, is strongly irreducible
(one can take Δ = {0, ± e_1, …,± e_d}).hard-ball modelsubshift!hard-ball model —
In particular  (d = 1), the golden mean subshift is strongly irreducible.



The Ledrappier subshift, described in Example <ref>, 
is not strongly irreducible.Ledrappier subshiftsubshift!Ledrappier —



Fiorenzi <cit.> obtained the following extension of Theorem <ref>.



Let G be a countable amenable group with Følner sequence   
= (F_n)_n ∈ and A,B  finite sets.
Suppose that X ⊂ A^G is a strongly irreducible subshift of finite type and Y ⊂ B^G is a strongly irreducible subshift   with h_(X) = h_(Y) and
that τ X → Y is a cellular automaton. Then the following conditions are
equivalent:


  * τ is surjective;

  * h_(τ(X)) = h_(Y);

  * τ is pre-injective.




The cellular automaton τ X → Y from the golden mean subshift to the even subshift described in Example <ref>
satisfies all the hypotheses in the previous theorem.
As τ is pre-injective (cf. Example <ref>), we deduce that
τ is surjective.
Note that here one might also easily obtain  surjectivity of τ by a direct argument. 




 §.§ The Moore and the Myhill properties for subshifts


Let G be a countable group, A a finite set, and X ⊂ A^G a subshift.
One says that the subshift  X has the Moore propertyMoore property!— for a subshiftsubshift!— satisfying the
Moore property
if every surjective cellular automaton 
τ X → X is pre-injective
and that it has the Myhill propertyMyhill property!— for a subshiftsubshift!— satisfying the
Myhill property  
if every pre-injective cellular automaton 
τ X → X is surjective.
One says that X has the Moore-Myhill propertyMoore-Myhill property!— for a subshiftsubshift!— satisfying the
Moore-Myhill property  
or that it satisfies the Garden of Eden theorem if it has both the Moore and the Myhill properties.Garden of Eden theorem!subshift satisfying the —subshift!— satisfying the Garden of Eden theorem

From Theorem <ref>, we immediately deduce the following.



Let G be a countable amenable group and A a finite set.
Then every strongly irreducible subshift of finite type X ⊂ A^G has the Moore-Myhill property. 



Let G = ^d and A = {0,1}.
Consider the hard-ball model X ⊂ A^G described in Example <ref>.hard-ball modelsubshift!hard-ball model —
As ^d is amenable and X is both strongly irreducible and of finite type,
we deduce from Corollary <ref> that X has the Moore-Myhill property.
In particular (d = 1), the golden mean subshift has the Moore-Myhill property.golden mean subshiftsubshift!golden mean —  


[Fiorenzi]

Let A = {0,1} and let X ⊂ A^ be the even subshift 
(cf. Example <ref>).even subshiftsubshift!even —
Consider the cellular automaton  σ A^→ A^ with memory set
S = {0,1,2,3,4} and local defining map μ A^S → A given by

    μ(y) =
    
    1    
    
    0

Then one has σ(X) ⊂ X, and the cellular automaton τσ|_X   X → X is not
pre-injective. Indeed, the configurations x_1, x_2 ∈ X defined by

    x_1 = ⋯ 0 ⋯ 00(100)100 ⋯ 0 ⋯

and

    x_2 =  ⋯ 0 ⋯ 00(011)100 ⋯ 0 ⋯

satisfy

    τ(x_1) =  ⋯ 1 ⋯ 11(100)10011 ⋯ 1 ⋯ = τ(x_2).

Observe, alternatively, that the patterns p,q with support Ω{0,1, …, 12} defined by

    p(n) =  1      n = 6,9
    
    0     q(n) =  1      n = 7,8,9
    
    0

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 <cit.> and <cit.> for more details.


  As the even subshift is strongly irreducible and  is amenable, the previous example shows that
  the hypothesis that X is of finite type cannot be removed from Corollary <ref>. 
However, we have the following (cf. <cit.>).



Let G be a countable amenable group and  A  a finite set. 
Then every strongly irreducible subshift X ⊂ A^G has the Myhill property.



The even subshift X ⊂{0,1}^ has the Myhill property since it is strongly irreducible 
and  is amenable.even subshiftsubshift!even —




Let A = {0,1}. 
Let x_0,x_1 ∈ A^ denote the two constant configurations 
respectively defined by x_0(n) = 0 and
x_1(n) = 1 for all n ∈. Note that
X = {x_0,x_1} is a subshift of finite type.
The map τ X → X given by τ(x_0) = τ(x_1) = x_0 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 <ref>
nor from Theorem <ref>.
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.


[Fiorenzi]
Let A = {0,1,2} and let X ⊂ A^ be the subshift of finite
type consisting of all x ∈ A^ such that

    x(n) x(n + 1) ∉{01,02}   for all  n ∈.

Thus a configuration x → A is in X if and only if one of
the following conditions is satisfied:


  * x(n) = 0 for all n ∈;

  * x(n) ≠ 0 for all n ∈;

  * there exists n_0 ∈ such that x(n) ∈{1,2} for all 
n ≤ n_0 and x(n) = 0 for all n > n_0.

Consider the cellular automaton σ A^→ A^ with memory
set S = {0,1} and local defining map

    μ(y) =  y(0)     y(1) ≠ 0
    
    0

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 <cit.>). 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 σ'  A^→ A^ with memory
set S' = {-1,0} and local defining map

    μ'(y) =  y(0)     y(-1)y(0) ∉{10,20}
    
    y(-1)

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 ⊂ A^ a subshift.
One says that a word u ∈ A^⋆ of length n
appearsword!— appearing in a subshiftsubshift!word appearing in a — in X if there is a configuration x ∈ X and m ∈
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 languagelanguage of a subshiftsubshift!language of a — of X.
One says that the subshift X is irreducibleirreducible subshiftsubshift!irreducible — if given any two words u,v ∈ L(X) there exists a word w ∈ L(X) such that
u w v ∈ L(X).
Clearly every strongly irreducible subshift X ⊂ A^ is irreducible.
The converse is false as shown by the following example.


Let A = {0,1} and consider the subshift X ⊂ A^ consisting of the two configurations 
x ∈ A^ that satisfy x(n) ≠ x(n + 1) for all n ∈.
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 <cit.>
(cf. <cit.>).


Let A be a finite set.
Then every irreducible subshift of finite type X ⊂ A^ has the Moore-Myhill property.





§ GARDEN OF EDEN THEOREMS FOR OTHER DYNAMICAL SYSTEMS





 §.§ Dynamical systems

By a dynamical system,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 spacephase spacedynamical system!phase space of a — 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,α). 


Let  G be a countable group  and A a compact metrizable topological space (e.g. a finite set with its discrete topology).
Equip A^G = {x  G → A}
with the product topology.
The shift actionshift!— actionshiftaction!shift — σ of G on A^G
is the action defined by σ(g,x) = g x, where

    (g x)(h) = x(g^-1 h)

for all x ∈ A^G and g,h ∈ G.
Then (A^G,G,σ) is a dynamical system. 



If  (X,G,α) is a dynamical system and  Y ⊂ X 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 ⊂ A^G a subshift,
then  (X,G,σ|_X) is a dynamical system.



Let f  X → X be a homeomorphism of a compact metrizable space X.
The dynamical system generateddynamical system!— generated by a homeomorphism by f is the dynamical system
(X,,α_f), where α_f is the action of  on X given by
α_f(n,f)  f^n(x) for all n ∈ and x ∈ X.
We shall also  write (X,f) to denote the dynamical system generated by f. 



If we fix the countable group G,
the dynamical systems (X,G) are the objects of a concrete category _G
in which the morphisms from an object X ∈_G to another object Y ∈_G consist of all 
equivariant continuous maps τ X → Y. 
It follows from the Curtis-Hedlund-Lyndon theorem (cf. Theorem <ref>) that the category _G described in 
Remark <ref> is a full subcategory of the category  _G.


Let (X,G) and (X,G) be two dynamical systems.
One says that the dynamical systems (X,G) and 
(X,G) are topologically conjugatetopologically!— conjugate dynamical systems
if they are isomorphic objects in the category _G, i.e., 
if there exists an equivariant homeomorphism 
h X→ X.
One says that (X,G) is a factorfactor!— of a dynamical systemdynamical system!factor of a — of 
(X,G) if there exists an equivariant continuous surjective map
θX→ X. 
Such a map θ is then called a factor map.factor!— map
A factor map θX→ X is said to be finite-to-onefactor!finite-to-one — mapfinite-to-one factor map 
if the pre-image set 
θ^-1(x) is finite for each x ∈ X.
A finite-to-one factor map is said to be uniformly bounded-to-onefactor!uniformly bounded-to-one — mapuniformly bounded-to-one factor map  
if there is an integer K ≥ 1 such that
|θ^-1(x)| ≤ K for all  x ∈ X. 




 §.§ Expansiveness

One says that a dynamical system  (X,G) is expansiveexpansive dynamical systemdynamical system!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
(g x, g y) ∉ W.
Such a set W is then called an
expansiveness neighborhoodexpansiveness 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(g x,g y) ≥δ.


Let G be a countable group and A a finite set. Then the G-shift on A^G is expansive.
Indeed, it is clear that

    W {(x,y) ∈ A^G × A^G : x(1_G) = y(1_G)}

is an expansiveness neighborhood of Δ_A^G.



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 group, A a finite set,
and X ⊂ A^G a subshift,
then the dynamical system (X,G,σ|_X) is expansive.




 §.§ Homoclinicity


Let (X,G) be a dynamical system.
Two points x,y ∈ X are called homoclinichomoclinic!— points 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_g →∞ d(g x, g y) = 0,

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(g x,g y) < ε 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 classeshomoclinicity class 
of X.



Let (X,G) be a dynamical system and Y a set.
One says that a map τ X → Y is pre-injectivepre-injective!— map if its restriction to each G-homoclinicity class is injective.




Let G be a countable group and A  a finite set.
Two configurations x, y ∈ A^G are homoclinic with respect to the shift action of G on A^G if and only if they are almost equal
(see e.g. <cit.>).
Indeed, first observe that the sets

    W_Ω{(x,y) ∈ A^G × A^G : x|_Ω = y|_Ω},

where Ω runs over all finite subsets of G, form a neighborhood base of the diagonal 
Δ_A^G⊂ A^G × A^G (this immediately follows from the definition of the product topology).
Now, if x, y ∈ A^G are almost equal, then the set D ⊂ G consisting of all g ∈ G such that x(g) ≠ y(g) is finite, so that
Ω D^-1 is also finite for every finite subset Ω⊂ G.
As (g x, g y) ∈ W_Ω for every g ∈ G ∖Ω D^-1, this implies that x and y are homoclinic.
Conversely, suppose that x, y ∈ A^G are homoclinic.
Then there exists a finite subset F ⊂ G such that (g x, g y) ∈ W_{1_G} 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.




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 ⊂ A^G 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 <ref> 
agrees with  the one given in Definition <ref> above.  




 §.§ The Moore and the Myhill properties for dynamical systems

Let (X,G) be a dynamical system.
An endomorphismendomorphism of a dynamical systemdynamical system!endomorphism of a — of (X,G) is a continuous equivariant map τ X → X.
One says that the dynamical system  (X,G) has the Moore propertyMoore property!— for a dynamical systemdynamical system!Moore property for a — if every surjective endomorphism of (X,G)  is pre-injective
and that it has the Myhill propertyMyhill property!— for a dynamical systemdynamical system!Myhill property for a — if every pre-injective 
endomorphism of (X,G)  is surjective.
One says that (X,G) has the Moore-Myhill propertyMoore-Myhill property!— for a dynamical systemdynamical system!Moore-Myhill property for a — 
or that it satisfies the Garden of Eden theoremGarden of Eden theorem!dynamical system satisfying the —dynamical system!— satisfying 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.

  
In the particular case when (X,G) is a subshift, it immediately follows from  
Theorem <ref>  and Example <ref> that these definitions are equivalent to the ones given in Subsection <ref>.



 §.§ Anosov diffeomorphisms

Let f  M → M be a diffeomorphism of a compact smooth manifold M.
One says that f is an Anosov diffeomorphismAnosov diffeomorphism
(see e.g. <cit.>, <cit.>,   
 <cit.>)
 if the tangent bundle TM of M 
continuously splits as a direct sum TM = E_s ⊕ E_u of two df-invariant subbundles E_s and E_u such that, with respect to some (or equivalently any) Riemannian metric on M,
 the differential df is exponentially  contracting on E_s and exponentially expanding on E_u, 
 i.e.,
 there are constants  C > 0 and 0 < λ < 1 such that
 
 
  * ‖ df^n(v) ‖≤ Cλ^n ‖ v ‖,

  * ‖ df^-n(w) ‖≤ C λ^n ‖ w ‖

for all x ∈ M, v ∈ E_s(x),  w ∈ E_u(x), and n ≥ 0.

[Arnold's cat]Arnold's catdynamical system!Arnold's cat —
Consider the matrix

    A = 
    [ 0 1; 1 1 ]

 and the diffeomorphism  f 
of the 2-torus ^2 = ^2/^2 = /×/ 
given by

    f(x)  A x = 
     [       x_2; x_1 + x_2 ]  for all 
     x = [ x_1; x_2 ]∈^2.

The dynamical system (^2,f) is known as Arnold's cat.dynamical system!Arnold's cat —
The diffeomorphism f is Anosov.
Indeed, the eigenvalues of A are
λ_1 = - 1φ, and 
λ_2 = φ, where φ1 + √(5)2 is the golden 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.


[Hyperbolic toral automorphism]hyperbolic toral automorphism
More generally, if A ∈_n() has no eigenvalue on the unit circle,
then the diffeomorphism f of the n-torus ^n = ^n/^n, defined by f(x) = A x for all x ∈^n, is Anosov.
Such a  diffeomorphism is called a hyperbolic toral automorphism.  


In <cit.>,
we obtained the following result.



Let f be an Anosov diffeomorphism of the n-dimensional torus ^n.
Then the dynamical system (^n,f) has the Moore-Myhill property.


The proof given in <cit.> uses two  classical results.
The first one is the Franks-Manning theorem <cit.>, <cit.>Franks-Manning theoremtheorem!Franks-Manning — 
which states that
(^n,f) is topologically conjugate to a hyperbolic toral automorphism. 
The second one is a result of Walters <cit.> 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 <cit.> the following result.



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 
and that there exist a finite set A, a strongly irreducible subshift 
X⊂ A^G, and a uniformly bounded-to-one factor map 
θX→ X.
Then the dynamical system (X,G) has the Myhill property.


A homeomorphism f of a topological space X is called topologically mixingtopologically!— mixing dynamical systemdynamical system!topologically mixing — if, given any two nonempty open subsets 
U,V ⊂ X, there exists an integer N ≥ 0 such that
f^n(U) ∩ V ≠∅ for all n ∈ that satisfy  |n| ≥ N.
By the classical work of BowenBowen, Robert E. (Rufus) (cf. <cit.> and  <cit.>),  dynamical systems generated by topologically mixing Anosov diffeomorphisms satisfy the hypotheses of
Theorem <ref>. 
As a consequence (cf. <cit.>), we get the following partial extension of 
Theorem <ref>.



Let  f be a topologically mixing Anosov diffeomorphism of a 
compact smooth manifold M.
Then the dynamical system (M,f) has the Myhill property.



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 recall that a nilmanifoldnilmanifold 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-nilmanifoldinfra-nilmanifold  is a manifold that is finitely covered by some nilmanifold.




 §.§ Weak specification


Recently, after our preprint <cit.> had circulated, Hanfeng LiLi, Hanfeng posted his paper <cit.> containing an impressive Garden of Eden type theorem generalizing several results mentioned above (see Theorems <ref>
and <ref>, and Corollaries <ref> and <ref>).

The key notion in Li's paper is that of specification, a strong orbit tracing property which was introduced
by Rufus BowenBowen, Robert E. (Rufus) for -actions in relation to his studies on Axiom A diffeomorphisms in <cit.> (see
also <cit.>) and was subsequently extended to ^d-actions by RuelleRuelle, David in 
<cit.>. Several versions and generalizations of specification have appeared in the literature 
(see, in particular, <cit.> and <cit.>).
Here is the one we need (cf. <cit.>).



A dynamical system (X,G) has the weak specification propertyweak specification propertydynamical system!weak specification property for a — 
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 (x_i)_i ∈ I 
is any family of points in X, then there exists x ∈ X such that 

    d(sx,sx_i) ≤ε   i ∈ I  s ∈Ω_i,

where d is any metric compatible with the topology on X.


It is straightforward (cf. <cit.>) to check that if G is a countable group, A is a finite
alphabet set, and X ⊂ A^G is a subshift, then the shift dynamical system (X,G) has the weak specification property 
if and only if it is strongly irreducible (cf. Section <ref>). 
Also, it is easy to see that the weak specification property passes to factors.

Li <cit.> proved the following:



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 <ref> covers Theorem <ref>, by virtue of the remarks following 
Definition <ref>.  

Recall (cf. Example <ref>) that if X ⊂{0,1}^ denotes the even subshift 
(cf. Example <ref>),  then (X, ) 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 <ref> one cannot deduce the Moore property, in general.



 §.§ Algebraic dynamical systems


An algebraic dynamical systemalgebraic dynamical systemdynamical system!algebraic — 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 ↦ g x is a continuous group automorphism of G with inverse x ↦ g^-1 x.


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 ^n, or  the infinite-dimensional torus ^,  or  the group _p  of p-adic integers for some prime p).
Then the G-shift (A^G,G) is an algebraic dynamical system. 
  


Let X be a compact metrizable abelian group and f  X → X a continuous group automorphism (for example X = ^n and f ∈_n()).
Then the dynamical system (X,f) generated by f is an algebraic dynamical system.


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 0_X if and only if one has

    lim_g →∞ d(g x, 0_X) = 0.

The set Δ(X,G) consisting of all points of X that are homoclinic to 0_X is an 
G-invariant additive subgroup of X, called
the homoclinic grouphomoclinic!— groupgroup!homoclinic — of (X,G)
(cf. <cit.>).
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).
 Consider now the Pontryagin dual X of X.
We recall that if L is a locally compact abelian group,locally compact abelian groupgroup!locally compact abelian — the elements of its Pontryagin dual LPontryagin duallocally compact abelian group!Pontryagin dual of a —group!Pontryagin dual of a locally compact abelian — are 
the characterscharacter of a locally compact abelian grouplocally compact abelian group!character of a —group!character of a locally compact abelian — of L, i.e., the continuous group morphisms
χ L →, where /,
and that the topology on L is the topology of uniform convergence on compact subsets
(see e.g. <cit.>).
As the abelian group X is  compact and  metrizable, 
X is a discrete countable abelian group.
There is also a natural dual action of G on X defined by

    g χ(x) χ(g^-1 x)

for all g ∈ G, χ∈X, and x ∈ X.
Note that χ↦ g χ is a group automorphism of X for each g ∈ G.
We recall that the integral group ringintegral group ringgroup!integral — ring [G] of G  consists of all formal series

    r = ∑_g ∈ G r_g g,

where r_g ∈ for all g ∈ G and r_g = 0 for all but finitely many g ∈ G, and  the  operations on [G] are defined by the formulas

    r + s    = ∑_g ∈ G (r_g + s_g) g,  
    
    r s    = ∑_g_1,g_2 ∈ G r_g_1 s_g_2  g_1 g_2

for all

    r = ∑_g ∈ G r_g g,    s = ∑_g ∈ G s_g g ∈[G].

By linearity, the action of G on X extends to a left [G]-module structure on 
X.
Conversely, if M is a countable left [G]-module and we equip M with its discrete topology, then its Pontryagin dual M is a compact metrizable abelian group.
The left [G]-module structure on M induces by restriction an action of G on M, and, by dualizing, we get an action of G on M by continuous group morphisms, 
so that (M,G) is an algebraic 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 dynamical systems with acting group G and  countable left [G]-modules
(see <cit.>, <cit.>, <cit.>).


Recall that from the hypotheses of Theorem <ref> one cannot deduce the Moore property, in general.
However, Li <cit.> proved that when restricting to the class of algebraic dynamical 
systems (cf. Section <ref>) with amenable acting group, the Moore property follows from 
expansiveness and weak specification:



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 <ref> and <ref>, one deduces the following (cf. <cit.>):


Garden of Eden theorem!— for expansive algebraic dynamical systems with the weak specification propertytheorem!Garden of Eden — for expansive algebraic dynamical systems with the weak specification property
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.




 §.§ Principal algebraic dynamical systems



Let f ∈[G] and consider the cyclic left [G]-module M_f [G]/ [G]f obtained by quotienting the ring [G] by the principal left ideal generated by f.
The algebraic dynamical system associated by Pontryagin duality with M_f is denoted by (X_f,G) and is called the principal algebraic dynamical systemprincipal algebraic dynamical systemalgebraic dynamical system!principal — associated with f.
There is a beautiful characterization of expansivity for principal algebraic dynamical systems due to Deninger and Schmidt <cit.> (see also <cit.>).
Let G be a countable group and f ∈[G]. Then (X_f,G) is expansive if and only if f is invertible in ℓ^1(G).
(Here ℓ^1(G) denotes the Banach algebra consisting of all formal sums r = ∑_g ∈ Gr_g g such that 
r_g ∈ for all g ∈ G and ‖ r ‖_1 ∑_g ∈ G |r_g| < ∞, 
equipped with its obvious real vector space structure and the convolution product as in (<ref>).)

It turns out (cf. <cit.>, see also <cit.>), that every expansive principal algebraic action
has the weak specification property. From Corollary <ref> one immediately deduces (cf. <cit.>):


Garden of Eden theorem!— for principal expansive algebraic dynamical systemstheorem!Garden of Eden — for principal expansive algebraic dynamical systems
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.


In <cit.> we had proved the same result under the stronger assumptions that G is abelian and the
phase space X is connected.
In the case  G = ^d, the group ring [G] can be identified with the ring [u_1, u_1^-1, …, u_d, u_d^-1] of Laurent polynomials with integral coefficients on d commuting indeterminates.


Arnold's catdynamical system!Arnold's cat —
For G = and f = u^2 - u - 1 ∈[u,u^-1] = [G], one can check that the associated principal algebraic dynamical system
(X_f,) is topologically conjugate to Arnold's cat on ^2 (see e.g. <cit.>).
Thus, from Corollary <ref> we recover that Arnold's cat satisfies the Moore-Myhill property.


In <cit.>, in collaboration with Hanfeng Li,Li, Hanfeng we introduced a notion of weak expansivity for elements in the integral group ring [G], for any countable group G, and proved a Garden of Eden theorem for principal algebraic dynamical systems associated with weakly expansive polynomials. In order to state it, let us first introduce some preliminary material and notation.
We denote by _0(G) the real vector space consisting of all maps r  G → such that lim_g →∞ r(g) = 0
(this means that for all ε > 0 there exists a finite subset F ⊂ G such that |r(g)| < ε for all
g ∈ G ∖ F). 
Note that if r ∈_0(G) and s ∈[G] then the map rs  G → defined by 
(rs)(g) = ∑_g_1,g_2 ∈ G r(g_1) s_g_2 for all g ∈ G (cf. (<ref>)) belongs to _0(G). 
This endows _0(G) with a structure of a  right [G]-module. Moreover G ⊂[G] ⊂_0(G).



An element f ∈[G] is said to be weakly expansiveweakly expansive polynomial provided:


  * ∀ r ∈_0(G), fr = 0 ⇒ r = 0;

  * ∃ω∈_0(G) such that fω = 1_G.



For principal algebraic dynamical systems with elementary amenable acting group there is a characterization of connectedness of the phase space. First recall that a non-zero element f ∈[G] is called primitiveprimitive polynomial if there is no integer n ≥ 2 that divides all coefficients of f. Also recall (cf. for instance <cit.>) that the class of elementary amenable groupsamenable group!elementary —group!elementary amenable —elementary!— amenable group is the smallest class of groups containing all finite groups and all Abelian groups that is closed under the operations of taking subgroups, quotiens, extensions, and direct limits. In <cit.> we showed that is G is a countable torsion-free elementary amenable group (e.g. G = ^d) and f ∈[G] is non-trivial, then X_f is connected if and only if f is primitive.

We are now in position to state the main result of <cit.> (Theorem 1.1 therein).


Garden of Eden theorem!— for algebraic actions associated with weakly expansive polynomialstheorem!Garden of Eden — for algebraic actions associated with weakly expansive polynomials
Let G be a countable Abelian group and f ∈[G].
Suppose that f is weakly expansive and that X_f is connected.
Then the dynamical system (X_f,G) has the Moore-Myhill property.


There are two main ingredients in our proof of Theorem <ref>.
The first one is a rigidity result (a generalization of <cit.>)
for algebraic dynamical systems associated with weakly expansive polynomials and with connected phase space.
We used it to prove that, under the above conditions, every endomorphism of (X_f,G) is affine with linear part of the form
x ↦ r x for some r ∈[G].
The second one, a generalization of <cit.>),
asserts that, if f is weakly expansive, then the homoclinic group Δ(X_f,G), equipped with
the induced action of G, is dense in X_f and isomorphic, as a [G]-module, to [G]/ [G] f^*, where
f^* ∈[G] is defined by (f^*)_g  f_g-1 for all g ∈ G.

In <cit.> we showed that if f ∈[G] and the associated principal algebraic dynamical system 
(X_f,G) is expansive then f is weakly expansive. It follows that Theorem <ref> constitutes a generalization of the main result in <cit.>.

Recall that a polynomial f ∈[G] is said to be well-balancedwell-balanced polynomial (cf. <cit.>) if the following conditions are satisfied:


  * ∑_g ∈ G f_g = 0,

  * f_g ≤ 0 for all g ∈ G ∖{1_G},

  * f_g = f_g^-1 for all g ∈ G (i.e., f is self-adjoint),

  * and (f) {g ∈ G: f_g ≠ 0}, the support of f, generates G.support!— of a polynomial


If f∈[G] is well-balanced, the associated dynamical system (X_f, G) is called a harmonic model.harmonic modeldynamical system!harmonic model —
For G = ^d, the Laurent polynomial f = 2d - ∑_i=1^d (u_i + u_i^-1) ∈[u_1, u_1^-1, …, u_d, u_d^-1] = [^d] is
well-balanced and the corresponding harmonic model (X_f,^d)  shares many interesting measure theoretic and entropic properties with other different models in mathematical physics, probability theory, and dynamical systems such as the Abelian sandpile model, spanning trees,
and the dimer models <cit.>.
Since a well-balanced polynomial f ∈[G], with G infinite countable not virtually  or ^2,
is weakly expansive (<cit.>), from Theorem <ref> we deduce 
(cf. <cit.>):


Garden of Eden theorem!— for harmonic modelstheorem!Garden of Eden — for harmonic models
Let G be an infinite countable Abelian group which is not virtually  or ^2  (e.g. G = ^d, with d ≥ 3).
Suppose that f ∈[G] is well-balanced and that X_f is connected.
Then the dynamical system (X_f,G) has the Moore-Myhill property.


If G = ^d, then any polynomial f ∈[G] may be regarded, by duality, as a function on G = ^d.
We denote by Z(f) {(t_1, t_2, …, t_d) ∈^d: f(t_1, t_2, …, t_d) = 0} its zero-set.
Recall that an irreducible polynomial f is atoralatoral polynomial <cit.> if there is some
r∈[G] such that r ∉[G] f and Z(f)⊂ Z(r). This is equivalent to the condition
Z(f)≤ d-2, where the meaning of (·) is explained in <cit.>; in particular,
one has (∅)  - ∞.
Also remark that, if d = 1, an irreducible polynomial f ∈[] = [u_1,u_1^-1] is atoral if and only if Z(f) = ∅
and this, in turn, is equivalent to (X_f,) being expansive (cf. <cit.>).
We are now in position to state the following (cf. <cit.>):


Garden of Eden theorem!— for irreducible atoral polynomialstheorem!Garden of Eden — for irreducible atoral polynomials
Let f∈[^d] be an irreducible atoral polynomial such that Z(f) is contained in the image of the intersection of [0,1]^d and a finite union of hyperplanes in ^d under the natural quotient map ^d →^d (e.g., when d ≥ 2 such that Z(f) is finite).
Then the dynamical system (X_f,^d) has the Moore-Myhill property.



Here below, we present some examples of irreducible atoral polynomials f ∈[^d], mainly from 
<cit.> and <cit.>. We can then apply Theorem <ref> and deduce
that the corresponding algebraic dynamical systems (X_f, ^d) satisfy the Garden of Eden theorem.



  * Let d=1 and f(u) = u^2 - u - 1 ∈[u,u^-1] = [] (cf. Example <ref>).Arnold's catdynamical system!Arnold's cat —
Then f is irreducible and, since Z(f) = ∅, atoral.
Recall that the associated principal algebraic dynamical system (X_f,) is conjugated to Arnold's cat.
Thus we get yet another proof of the fact that this hyperbolic dynamical systems satisfies the Garden of Eden theorem.


  * Let d = 2 and f(u_1,u_2) = 2 - u_1 - u_2 ∈[u_1,u_1^-1,u_2,u_2^-1] = [^2]. Then
Z(f) = {(1,1)}, and so f is atoral.
Note that, in fact, f is weakly expansive (though not well-balanced) by <cit.>.
Moreover, f is also primitive, so that, by the characterization we presented above, X_f is connected.
Applying Theorem <ref>, we obtain an alternative proof of the fact that (X_f,^2) has the Moore-Myhill property.


  * Let d=2, and consider the Laplace harmonic model f(u_1,u_2) = 4 - u_1-u_1^-1-u_2-u_2^-1∈[u_1,u_1^-1,u_2,u_2^-1] = [^2].Laplace harmonic modeldynamical system!Laplace harmonic model — 
One has Z(f)={(1, 1)}. Thus f is atoral and (X_f, α_f) satisfies the Garden of Eden theorem, by virtue of Theorem <ref>. (Note that we cannot apply Theorem <ref>.)


  * Let d=2, and f(u_1,u_2) = 1 + u_1 + u_2 ∈[u_1,u_1^-1,u_2,u_2^-1] = [^2]. Then Z(f)={(ω, ω^2),
(ω^2, ω)}, where ω = exp(2π i/3). The algebraic dynamical system (X_f, ^2) is called the connected Ledrappier subhift.Ledrappier subshift!connected —subshift!connected Ledrappier — Thus the connected Ledrappier shift satisfies the Garden of Eden theorem.
On the other hand, the (disconnected) Ledrappier shift (cf. Example <ref>)Ledrappier subshiftsubshift!Ledrappier —
X {x ∈ (/2)^^2: x(m,n)+x(m+1,n)+x(m,n+1)=0} (which may be regarded as an algebraic dynamical
system with phase space [^2]/I, where I = 2[^2] + f[^2] is the ideal generated by 2 and 
f(u_1,u_2) = 1+u_1+u_2 ∈[u_1,u_1^-1,u_2,u_2^-1] = [^2]) does not satisfy the Garden on Eden theorem. 
Indeed, one has Δ(X,^2) = {0_(/2)^^2} so that every map τ X → X is pre-injective. 
This ensures the Moore property for (X,^2). 
However, the constant map x ↦ 0_(/2)^^2 (which is a pre-injective endomorphism of (X,^2)) is clearly not surjective, showing that (X,^2) does not satisfy the Myhill property.


  * Let d=3 and f(u_1,u_2,u_3) = 3 + 3u_1 - 3 u_1^3 + u_1^4 - u_2 - u_3  ∈[u_1,u_1^-1,u_2,u_2^-1, u_3,u_3^-1] = [^3].
One has has Z(f)={(η, η, η), (η,η,η)}, where η is an algebraic integer.



 

Let d=1 and f = 2 - u - u^-1∈[u,u^-1] = [].Laplace harmonic modeldynamical system!Laplace harmonic model —
Then the associated dynamical system X_f = {x ∈^: x(n-1)+x(n+1) = 2x(n)  n ∈} is the one-dimensional
Laplace harmonic model. It is easy to see that Δ(X_f,α_f) = {0_^}.
Then (X_f,α_f) satisfies the Moore property but not the Myhill property
(the constant map x ↦ 0_^ (which is a pre-injective endomorphism of (X_f,α_f)) is clearly not surjective).


We then have (cf. <cit.>):


Garden of Eden theorem!— for Laplace harmonic modelstheorem!Garden of Eden — for Laplace harmonic models
The Laplace harmonic modelLaplace harmonic modeldynamical system!Laplace harmonic model — (i.e. the principal algebraic dynamical 
system (X_f,α_f) associated with the polynomial 
f = 2d - ∑_i=1^d (u_i + u_i^-1) ∈[u_1, u_1^-1, …, u_d, u_d^-1] = [^d])
satisfies the Moore-Myhill property if and only if d ≥ 2.





§ SOME ADDITIONAL TOPICS





 §.§ 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 topologyprodiscrete!— topology on A^G is the product topology obtained by taking the discrete topology on each factor A of A^G  = ∏_g ∈ G A.
The prodiscrete topology on A^G 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 structureprodiscrete!— uniform structure on A^G, that is, the product uniform structure on A^G obtained by taking the discrete uniform structure on each factor A of A^G (see <cit.> for more details).
A subset X ⊂ A^G is called a subshiftsubshift 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 ⊂ A^G and Y ⊂ B^G are two subshifts.
One defines cellular automata between X and Y exactly as in
Definition <ref>.
Every cellular automaton τ X → Y is continuous with respect to the topologies on X and Y induced by the prodiscrete topologies on A^G and B^G.
The converse is false in general <cit.>, <cit.>.
However, the Curtis-Hedlund-Lyndon theorem (cf. Theorem <ref>) admits the following generalization <cit.>, <cit.>: a map τ X → Y is a cellular automaton if and only if it is equivariant 
(with respect to the G-shift actions) and uniformly continuous
(for  the uniform structures on X and Y induced by the prodiscrete uniform structures on A^G and  B^G).
One can extend the notion of amenability defined only for countable groups in Section <ref> 
by declaring  that a general group  G is amenableamenable groupgroup!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 <ref>)
remains valid in this more general setting:
if G is a (possibly uncountable) amenable group, A a finite set, and τ A^G → A^G a cellular automaton,
then τ A^G → A^G 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 <cit.> and <cit.>).
One can also directly follow the proof given above for Theorem <ref>
by replacing the Følner sequence by a Følner net (see <cit.>).  



 §.§ 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 = _K(A).
Observe that A is infinite as soon as the field K is infinite (e.g. K =) and d ≠ 0.
Taking A as an alphabet, the configuration set A^G inherits a natural product vector space structure.
The support of a configuration x ∈ A^G is the subset (x) {g ∈ G: x(g) ≠ 0 }⊂ G.
Thus, x ∈ A^G has finite support if and only if it is almost equal to the constant zero-configuration.
We denote by A[G] ⊂ A^G the vector subspace consisting of all configurations with finite support.
Recall that an involutive K-algebrainvolutive 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 productconvolution product defined by

    (αβ)(g) ∑_g_1, g_2 ∈ G:
     g_1g_2 = gα(g_1) β(g_2)
    = ∑_h ∈ Gα(h) β(h^-1 g)

for all α, β∈ K[G] and g ∈ G,
and  the involution is the map α↦α^* given by
 
    α^*(g) α(g^-1)

 for all α∈ K[G] and g ∈ G.
This involutive K-algebra  is called the group algebragroup!— 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 ↦δ_g, where δ_g ∈ K[G] is defined by δ_g(g) = 1 and δ_g(h) = 0 for all h ∈ G with h ≠ g,
and  that G ⊂ K[G] is a base for the vector space K[G].
The G-shift action on A^G is clearly K-linear, so that it yields a left K[G]-module structure on A^G. 
Observe that A[G] is a submodule of A^G.
A linear cellular automatonlinear cellular automatoncellular automaton!linear — over the group G and the alphabet A is a cellular automaton 
τ A^G → A^G that is K-linear with respect to the vector space structure on A^G 
(if S is any memory set for τ and μ A^S → A is the associated local defining map, 
this is equivalent to requiring that μ is K-linear).
Let us denote by (G;A) the vector space consisting of all linear cellular automata τ A^G → A^G.
Let τ∈(G;A). 
Note that A[G] is stable under τ. Indeed, if S ⊂ G is a memory set for τ, then
(τ(x)) ⊂(x)S^-1 for all x ∈ A^G) (see <cit.>).
Moreover,  τ is pre-injective if and only if τ|_A[G] A[G] → A[G] is injective
(cf. <cit.>).
Observe also that τ is a K[G]-module endomorphism of A^G and hence of A[G].
The vector space (G;A) has a natural structure of a K-algebra with the composition of maps
as the multiplicative operation.
Furthermore, the restriction map τ↦τ|_A[G] yields a
K-algebra isomorphism from (G;A) onto _K[G](A[G]), the endomorphism K-algebra of the K[G]-module
A[G] (cf. <cit.>).
It turns out  that A[G] is a free K[G]-module with rank d.
Actually, if (e_i)_1 ≤ i ≤ d is a base for the vector space A, then the family (x_i)_1 ≤ i ≤ d, where x_i ∈ A[G] is the configuration defined by
x_i(1_G) = e_i and x_i(g) = 0 for g ≠ 1_G, is a free base for the K[G]-module A[G]
(cf. <cit.>).
One deduces that _K[G](A[G]) is isomorphic, as a K-algebra,
to the K-algebra _d(K[G]) of d × d matrices with coefficients in the group algebra K[G].
It follows that (G;A) and _d(K[G]) are isomorphic as K-algebras 
(cf. <cit.>).
For instance, the map Φ_d(K[G]) →(G;A), sending each matrix
α = (α_i j)_1 ≤ i,j ≤ d∈_d(K[G]) to the unique linear cellular automaton
τ∈(G;A) such that

    τ(x_i) = ∑_1 ≤ j ≤ dα_j i^*  x_j

for all 1 ≤ i ≤ d, is a K-algebra isomorphism. 
The adjointadjoint matrix of a matrix α∈_d(K[G]) is the matrix
α^* ∈_d(K[G]) given by (α^*)_ijα_ji^* ∈ K[G]  for all 
1 ≤ i,j ≤ d.
The involution α↦α^* makes _d(K[G]) into an involutive K-algebra.
Let us  transport this involution to (G;A) via Φ.
Thus, (G;A) becomes an involutive K-algebra with involution τ↦τ^* satisfying

    τ^*(x_i) = ∑_1 ≤ j ≤ dα_i j  x_j

for all 1 ≤ i ≤ d and τ = Φ(α) ∈(G;A).
Note that this involution on (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

    a · b = ∑_1 ≤ i ≤ d a_ib_i    for all   a = ∑_1 ≤ i ≤ d a_i e_i  and    b = ∑_1 ≤ i ≤ d b_i e_i, 
    with  a_i,b_i ∈ K  for  1 ≤ i ≤ d.

Then the K-bilinear map A[G] × A^G → K, defined by

    ⟨ x,y ⟩∑_g ∈ G x(g)· y(g)

for all x ∈ A[G] and y ∈ A^G, is non-degenerate in both arguments.
Given a linear cellular automaton τ A^G → A^G,
Bartholdi <cit.> (see also <cit.>)Bartholdi, Laurent 
observed that

    ⟨τ(x), y ⟩ = ⟨ x, τ^*(y) ⟩

for all x ∈ A[G] and y ∈ A^G, and used this to show that τ is pre-injective (resp. surjective) if and only if
τ^* is surjective (resp. pre-injective).
In <cit.> (see also <cit.>)Garden of Eden theorem!linear —theorem!linear Garden of Eden — a linear version of the Garden of Eden theorem is proved, namely that
if G is amenable and τ∈(G;A), then τ is surjective if and only if it is pre-injective.
Let G be a nonamenable group. In <cit.> BartholdiBartholdi, Laurent  showed that there exists a finite field K (in <cit.> 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 τ∈(G;A) which is not surjective. 
As a consequence (<cit.>), the cellular automaton τ^* ∈(G;A) is surjective but not pre-injective.
These two facts, in combination with the linear version of the Garden of Eden theorem in <cit.>, 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 <cit.> to linear cellular automata τ X → X with X ⊂ A^G a strongly irreducible linear subshift of finite type, and in <cit.> to the case when the alphabet A is a semi-simple left-module of finite length
over a (possibly noncommutative) ring.



 §.§ Algebraic cellular automata

Let G be a group. In <cit.> we introduced the class of algebraic cellular automata over G. Given a field K, let A be an affine algebraic setaffine algebraic set over K. This means that A ⊂ K^n for some integer n ≥ 1 is the set of common zeroes of a family of polynomials in n variables with coefficients in K. Then a cellular automaton τ A^G → A^G is called an algebraic
cellular automatonalgebraic cellular automatoncellular automaton!algebraic — provided it admits a memory set S ⊂ G and a local defining map μ A^S → A that is
regular,regular map i.e., it is the restriction of some polynomial map (K^n)^S → K^n. This definition was generalized in <cit.>
as follows.


Let 𝒮 be a scheme and let X, Y be schemes based over 𝒮. 
Denote by A  X(Y) the set of Y-points of X,
that is, the set consisting of all 𝒮-scheme morphism Y → X.
Then an algebraic cellular automaton over the group G and the
𝒮-scheme X with coefficients in the 𝒮-scheme Y, briefly, an algebraic cellular automaton over
the group G and the schemes 𝒮,X,Y,algebraic cellular automaton!— over a schemecellular automaton!algebraic — over a scheme is a cellular automaton τ A^G → A^G over the group G and the alphabet A that admits a memory set S ⊂ G and a local defining map μ A^S → A which is induced by some 𝒮-scheme morphism f  X^S → X, where X^S denotes the 𝒮-fibered product of a family of copies of
X indexed by S.

Note that Definition <ref> generalizes that of an algebraic cellular automaton given in <cit.>.
Indeed, if K is a field and A ⊂ K^n an algebraic set, there is an 𝒮-scheme X associated with A for
𝒮 = (K), namely  X = (K[u_1,…,u_n]/I), where I = I(A) is the ideal of K[u_1,…,u_n] consisting of all polynomials that identically vanish on A.
One then has A = X(𝒮) and the regular maps between two regular sets A_1 ⊂ K^n_1 and A_2 ⊂ K^n_2
are precisely those induced by the 𝒮-morphisms between their corresponding 𝒮-schemes X_1 and X_2, equivalently, the K-algebra morphisms from
K[z_1,…,z_n_2]/I(A_2) to K[t_1,…,t_n_1]/I(A_1). Thus, τ A^G → A^G is an algebraic cellular automaton,
as defined in <cit.>, if and only if τ is a cellular automaton in the sense of Definition <ref>
over the schemes 𝒮,X,Y for 𝒮 = Y = (K) and X is the 𝒮-scheme associated with A.
Recall that an algebraic varietyalgebraic variety over a field K is a scheme of finite type over K.
In <cit.> we showed the following Myhill type result for algebraic cellular automata:


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 τ A^G → A^G
over (G,X,K) is surjective.

Let us note that the converse implication, i.e., the analogue of the Moore implication, does not hold under the hypotheses of
Theorem <ref>, even with the additional hypothesis that the variety X is complete. 
For example, if K is an algebraically closed field whose characteristic is not equal to 2,
the projective line _K^1 is an irreducible complete K-algebraic variety
and the morphism f _K^1 →_K^1 given by (x:y) ↦ (x^2:y^2) is surjective but not injective.
Taking A _K^1(K),  we deduce that, for any group G, the map τ A^G → A^G defined by
(τ(c))(g)   f(c(g)) for all c ∈ A^G 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, the following weak notion of pre-injectivity
was introduced in <cit.>:

algebraic cellular automaton!(*)-pre-injective —cellular automaton!(*)-pre-injective algebraic —
Let G be a group and let X be an algebraic variety over an algebraically closed field K.
Let A X(K) and let τ A^G → A^G 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 proper subset H ⊂ A^Ω that is closed for the Zariski topology such that

    τ((A^Ω)_p)=τ(H_p)    for all  p ∈ A^G∖Ω

where H_p {x ∈ A^G: x|_Ω∈ H  x|_G ∖Ω = p} for p ∈ A^G∖Ω and any subset H ⊂ A^Ω.

It turns out that Theorem <ref> remains valid if we replace the hypothesis that τ is pre-injective by the weaker hypothesis that τ is (*)-pre-injective. Moreover, this weak form of pre-injectivity also allows us to establish a version of the Moore implication for algebraic cellular automata. Altogether we obtained the following version of the Garden of Eden theorem
(cf. <cit.>) for algebraic cellular automata:

Garden of Eden theorem!— for algebraic cellular automatatheorem!Garden of Eden — for algebraic cellular automata
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 τ A^G → A^G be an algebraic cellular automaton
over (G,X,K).
Then the following conditions are equivalent:


  * τ is surjective;

  * τ is (*)-pre-injective.


One of the main ingredients in the proof of the above results is the notion of algebraic mean dimension.algebraic mean dimension
If G is an amenable group equipped with a Følner net  and A is the set of K-points of an algebraic variety X over an algebraically closed field K, given a subset Γ⊂ A^G then the algebraic mean dimension
_(Γ) of Γ is defined as a limit of the average Krull dimensionKrull dimension 
of the projection of Γ along the Følner net.
The definition of algebraic mean dimension is analogous to that of topological entropy (cf. (<ref>)).



 §.§ Gromov's Garden of Eden theorem
Gromov's Garden of Eden theoremGarden of Eden theorem!Gromov's —theorem!Gromov's Garden of Eden —
In <cit.>, Gromov proved a Garden of Eden type theorem generalizing Theorem <ref> 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 = (V,E) of bounded degree with a
natural homogeneity condition (to admit a dense pseudogroup of partial isometries).
The classical case corresponds to = (G,S) being the Cayley graph of a finitely generated group G with respect to a finite and
symmetric generating subset S ⊂ G ∖{1_G}. 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,stable space 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)stable space!— of bounded propagationbounded propagation!— of a stable space and admitting a dense holonomystable space!— of dense holonomydense holonomy!— of a stable space (corresponding to shift-invariance in the classical case) as objects, and

  * maps of bounded propagationmap of bounded propagationbounded propagation!map of —
(this condition corresponds to continuity) admitting a dense holonomymap of bounded propagation!— admitting a dense holonomydense holonomy!map of bounded propagation admitting a — (this corresponds to G-equivariance), as morphisms.

The notions 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 the following.Gromov's Garden of Eden theoremGarden of Eden theorem!Gromov's —theorem!Gromov's Garden of Eden —

Let = (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 ⊂ A^V 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.


In <cit.> it is shown that a stable space of bounded propagation is strongly irreducible (cf. Section <ref>) and of finite type (cf. Section <ref>).
However, as shown in <cit.>, 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. <cit.>) improves on 
Gromov's theorem.

Let = (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 ⊂ A^V 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 <ref>.




 §.§ Cellular automata over homogeneous sets

Cellular automata where the universe is a set endowed with a transitive group action have been investigated by Moriceau <cit.>.
Versions  of the Curtis-Hedlund-Lyndon theorem and of the Garden of Eden theorem in this more general setting have been obtained by
Wacker <cit.>, <cit.>. 


Acknowledgements. We thank Laurent Bartholdi for valuable comments and remarks.






siam
'
10

bartholdi:2017
L. Bartholdi, Cellular automata, duality, and sofic groups,
New York J. Math. 23 (2017) pp. 1417–1425.

bartholdi
L. Bartholdi, Gardens of Eden and amenability on cellular
  automata, J. Eur. Math. Soc. (JEMS), 12 (2010), pp. 241–248.

bartholdi:2016
L. Bartholdi and D. Kielak, Amenability of groups is characterized
  by Myhill's theorem, arXiv:1605.09133.

bhattacharya
S. Bhattacharya, Orbit equivalence and topological conjugacy of
  affine actions on compact Abelian groups, Monatsh. Math. 129 (2000),
  pp. 89–96.
	
Bowen-Li
L. Bowen and H. Li, Harmonic models and spanning forsets of residually finite groups, J. Funct. Anal.
263 (2012), pp. 1769–1808.	

bowen-markov-minimal_AJM-1970
R. Bowen, Markov partitions and minimal sets for Axiom A
  diffeomorphisms, Amer. J. Math., 92 (1970), pp. 907–918.

bowen-markov-1970
height 2pt depth -1.6pt width 23pt, Markov partitions
  for Axiom A diffeomorphisms, Amer. J. Math., 92 (1970),
  pp. 725–747.
	
bowen-periodic-1971
R. Bowen, Periodic points and measures
  for Axiom A diffeomorphisms, Trans. Amer. Math. Soc., 154 (1971),
  pp. 377–397.	

brin-stuck
M. Brin and G. Stuck, Introduction to dynamical systems, Cambridge
  University Press, Cambridge, 2002.

csc-linear-goe
T. Ceccherini-Silberstein and M. Coornaert,
The Garden of
  Eden theorem for linear cellular automata, Ergodic Theory Dynam. Systems,
  26 (2006), pp. 53–68.

csc-goe-modules
height 2pt depth -1.6pt width 23pt, Amenability and
  linear cellular automata over semisimple modules of finite length, Comm.
  Algebra, 36 (2008), pp. 1320–1335.

csc-curtis-hedlund
height 2pt depth -1.6pt width 23pt, A generalization of
  the Curtis-Hedlund theorem, Theoret. Comput. Sci., 400 (2008),
  pp. 225–229.

induction
height 2pt depth -1.6pt width 23pt, Induction and
  restriction of cellular automata, Ergodic Theory Dynam. Systems, 29 (2009),
  pp. 371–380.

book
height 2pt depth -1.6pt width 23pt, Cellular automata
  and groups, Springer Monographs in Mathematics, Springer-Verlag, Berlin,
  2010.
	
	cc-algebraic-ca
height 2pt depth -1.6pt width 23pt, On algebraic
  cellular automata, J. Lond. Math. Soc. (2), 84 (2011), pp. 541–558.

csc-goe-linear-sub
height 2pt depth -1.6pt width 23pt, A Garden of Eden
  theorem for linear subshifts, Ergodic Theory Dynam. Systems, 32 (2012),
  pp. 81–102.

csc-myhill-monatsh
height 2pt depth -1.6pt width 23pt, The Myhill
  property for strongly irreducible subshifts over amenable groups, Monatsh.
  Math., 165 (2012), pp. 155–172.

csc-cat
height 2pt depth -1.6pt width 23pt, 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.

csc-ijm-expansive
height 2pt depth -1.6pt width 23pt, Expansive actions of
  countable amenable groups, homoclinic pairs, and the Myhill property,
  Illinois J. Math., 59 (2015), pp. 597–621.

csc-goe-anosov
height 2pt depth -1.6pt width 23pt, A garden of Eden
  theorem for Anosov diffeomorphisms on tori, Topology Appl., 212 (2016),
  pp. 49–56.

csc-goe-principal
height 2pt depth -1.6pt width 23pt, 
 A Garden of Eden
  theorem for principal algebraic actions, preprint 2017. arXiv:1706.06548.
	
cscl-goe-homoclinically
T. Ceccherini-Silberstein, M. Coornaert, and H. Li,
Homoclinically expansive actions and a Garden of Eden theorem for harmonic models,
preprint 2018. arXiv: 1803.03541.


cscp-alg-ca
T. Ceccherini-Silberstein, M. Coornaert, and X. K. Phung, 
On injective cellular automata over schemes, preprint 2017. arXiv:1712.05716.
	
cscp-GOE-myhill
height 2pt depth -1.6pt width 23pt,

On the Garden of Eden theorem for endomorphisms of symbolic algebraic varieties, preprint 2018. arXiv:1803.08906.
	
CFS-goe
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.

ceccherini
T. Ceccherini-Silberstein, A. Machì, and F. Scarabotti, Amenable groups and cellular automata, Ann. Inst. Fourier (Grenoble), 49
  (1999), pp. 673–685.
	
Chou
C. Chou, Elementary amenable groups, Ill. J. Math. 24(3)
  (1980), pp. 396–407.	
	
chung-li-2015
N. Chung and H. Li, Homoclinic groups, IE groups, and expansive algebraic actions, Invent. Math., 199 (2015), no.3,
  pp. 805-858.

coo-book
M. Coornaert, Topological dimension and dynamical systems,
  Universitext, Springer, Cham, 2015.
Translated and revised from the 2005 French original.

day-ijm-1957
M. M. Day, Amenable semigroups, Illinois J. Math., 1 (1957),
  pp. 509–544.

de-la-harpe
P. de la Harpe, Topics in geometric group theory, Chicago Lectures
  in Mathematics, University of Chicago Press, Chicago, IL, 2000.
	
deninger-schmidt
C. Deninger and K. Schmidt, Expansive algebraic actions of discrete
  residually finite amenable groups and their entropy, Ergodic Theory Dynam.
  Systems 27 (2007), pp. 769–786.	
	
denker-grillenberger-sigmund
M. Denker, Ch. Grillenberger, and K. Sigmund, Ergodic theory on compact spaces. Lecture Notes in Mathematics, Vol. 527. 
Springer-Verlag, Berlin-New York, 1976. 

fiorenzi-sofic
F. Fiorenzi, The Garden of Eden theorem for sofic shifts, Pure
  Math. Appl., 11 (2000), pp. 471–484.

fiorenzi-strongly
height 2pt depth -1.6pt width 23pt, Cellular automata
  and strongly irreducible shifts of finite type, Theoret. Comput. Sci., 299
  (2003), pp. 477–493.

franks
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.

greenleaf
F. P. Greenleaf, Invariant means on topological groups and their
  applications, Van Nostrand Mathematical Studies, No. 16, Van Nostrand
  Reinhold Co., New York, 1969.

grigorchuk-1984
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.

gromov-polynomial-growth
M. Gromov, Groups of polynomial growth and expanding maps, Inst.
  Hautes Études Sci. Publ. Math.,  (1981), pp. 53–73.

gromov-esav
height 2pt depth -1.6pt width 23pt, Endomorphisms of
  symbolic algebraic varieties, J. Eur. Math. Soc. (JEMS), 1 (1999),
  pp. 109–197.

hedlund
G. A. Hedlund, Endomorphisms and automorphisms of the shift
  dynamical system, Math. Systems Theory, 3 (1969), pp. 320–375.
	

	li-2017
H. Li, Garden of Eden and specification, preprint 2017. arXiv:1708.09012.
	

lind-marcus
D. Lind and B. Marcus, An introduction to symbolic dynamics and
  coding, Cambridge University Press, Cambridge, 1995.

lind-schmidt
D. Lind and K. Schmidt, Homoclinic points of algebraic Z^d-actions, J. Amer. Math. Soc., 12 (1999), pp. 953–980.

lind-schmidt-handbook
height 2pt depth -1.6pt width 23pt, Symbolic and
  algebraic dynamical systems, in Handbook of dynamical systems, Vol. 1A,
  North-Holland, Amsterdam, 2002, pp. 765–812.

lind-schmidt-survey-heisenberg
D. Lind and K. Shmidt, A survey of algebraic actions of the discrete
  Heisenberg group, Uspekhi Mat. Nauk, 70 (2015), pp. 77–142.
	
lind-schmidt-verbitskiy
D. Lind, K. Schmidt and E. Verbitskiy, Entropy and growth rate of periodic points of algebraic Z^d-actions. In: Dynamical numbers: interplay between dynamical systems and number theory,
	ed. S. Kolyada, Yu. Manin, M. Möller, P. Moree and T. Ward,
	pp. 195–211, Contemporary Mathematics,
	vol. 523. American Mathematical Society, Providence (RI) (2010).	
	
lind-schmidt-verbitskiy-2
D. Lind, K. Schmidt, and E. Verbitskiy, Homoclinic points, atoral polynomials, and periodic points of algebraic ^d-actions,
Ergodic Theory Dynam. Systems 33 (2013), pp. 1060–1081.	

machi-mignosi
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.

manning
A. Manning, There are no new Anosov diffeomorphisms on tori,
  Amer. J. Math., 96 (1974), pp. 422–429.

milnor-growth
J. Milnor, A note on curvature and fundamental group, J.
  Differential Geometry, 2 (1968), pp. 1–7.

moore
E. F. Moore, Machine models of self-reproduction, vol. 14 of Proc.
  Symp. Appl. Math., American Mathematical Society, Providence, 1963,
  pp. 17–34.

moriceau
S. Moriceau, Cellular automata on a G-set, J. Cell. Autom., 6
  (2011), pp. 461–486.

morris
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.

muller
D. E. Muller, Unpublished class notes, university of illinois,
  (1976).

myhill
J. Myhill, The converse of Moore's Garden-of-Eden theorem,
  Proc. Amer. Math. Soc., 14 (1963), pp. 685–686.
	
von-neumann
J. von Neumann, Zur allgemeinen theorie des Masses, Fund.
  Math., 13 (1929), pp. 73–116.
	

olshanskii-monster
A. J. Olšanskiĭ, On the question of the
  existence of an invariant mean on a group, Uspekhi Mat. Nauk, 35 (1980),
  pp. 199–200.

ornstein-weiss
D. S. Ornstein and B. Weiss, Entropy and isomorphism theorems for
  actions of amenable groups, J. Analyse Math., 48 (1987), pp. 1–141.

paterson
A. L. T. Paterson, Amenability, vol. 29 of Mathematical Surveys and
  Monographs, American Mathematical Society, Providence, RI, 1988.
	
ren-2015
X. Ren, Periodic measures are dense in invariant measures for residually finite amenable group
actions with specification, preprint 2015.  arXiv:1509.09202.
		
		
ruelle-statistical-1973
D. Ruelle, Statistical mechanics on a compact set with Z^ν action satisfying expansiveness and specification, 
Trans. Amer. Math. Soc., 187 (1971), pp. 237–251.
	

schmidt-book
K. Schmidt, Dynamical systems of algebraic origin, vol. 128 of
  Progress in Mathematics, Birkhäuser Verlag, Basel, 1995.
	
schmidt-verbitskiy
K. Schmidt and E. Verbitskiy, Abelian sandpiles and the harmonic model,
Comm. Math. Phys. 292 (2009), pp. 721–759.	

schupp-arrays
P. E. Schupp, Arrays, automata and groups—some interconnections,
  in Automata networks (Argelès-Village, 1986), vol. 316 of Lecture Notes
  in Comput. Sci., Springer, Berlin, 1988, pp. 19–28.

shub-global-stability
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.

smale-bams
S. Smale, Differentiable dynamical systems, Bull. Amer. Math. Soc.,
  73 (1967), pp. 747–817.

tointon-harmonic
M. C. H. Tointon, Characterizations of algebraic properties of
  groups in terms of harmonic functions, Groups Geom. Dyn., 10 (2016),
  pp. 1007–1049.

wacker-curtis
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.

wacker-goe
height 2pt depth -1.6pt width 23pt, The Garden of
  Eden theorem for cellular automata on group sets, in Cellular automata,
  vol. 9863 of Lecture Notes in Comput. Sci., Springer, [Cham], 2016,
  pp. 66–78.

walters
P. Walters, Topological conjugacy of affine transformations of
  tori, Trans. Amer. Math. Soc., 131 (1968), pp. 40–50.

wolfram-new-kind
S. Wolfram, A new kind of science, Wolfram Media, Inc., 
Champaign, IL, 2002.



