arXiv:1701.02108v2 [] 23 Jan 2017

RIGHT AMENABILITY AND GROWTH OF FINITELY
RIGHT GENERATED LEFT GROUP SETS
SIMON WACKER

Abstract. We introduce right generating sets, Cayley graphs,
growth functions, types and rates, and isoperimetric constants for
left homogeneous spaces equipped with coordinate systems; characterise right amenable finitely right generated left homogeneous
spaces with finite stabilisers as those whose isoperimetric constant
is 0; and prove that finitely right generated left homogeneous spaces
with finite stabilisers of sub-exponential growth are right amenable,
in particular, quotient sets of groups of sub-exponential growth by
finite subgroups are right amenable.

The notion of amenability for groups was introduced by John von
Neumann in 1929. It generalises the notion of finiteness. A group
G is left or right amenable if there is a finitely additive probability
measure on P(G) that is invariant under left and right multiplication
respectively. Groups are left amenable if and only if they are right
amenable. A group is amenable if it is left or right amenable.
The definitions of left and right amenability generalise to left and
right group sets respectively. A left group set (M, G, ⊲) is left amenable if there is a finitely additive probability measure on P(M) that is
invariant under ⊲. There is in general no natural action on the right
that is to a left group action what right multiplication is to left group
multiplication. Therefore, for a left group set there is no natural notion
of right amenability.
A transitive left group action ⊲ of G on M induces, for each element
m0 ∈ M and each family {gm0 ,m }m∈M of elements in G such that,
for each point m ∈ M, we have gm0 ,m ⊲ m0 = m, a right quotient
set semi-action P of G/G0 on M with defect G0 given by m P gG0 =
−1
gm0 ,m ggm
⊲m, where G0 is the stabiliser of m0 under ⊲. Each of these
0 ,m
Key words and phrases. group actions, generating sets, Cayley graphs, growth
rates, isoperimetric constants, amenability.
1

2

SIMON WACKER

right semi-actions is to the left group action what right multiplication
is to left group multiplication. They occur in the definition of global
transition functions of cellular automata over left homogeneous spaces
as defined in [6]. A cell space is a left group set together with choices
of m0 and {gm0 ,m }m∈M .
A cell space is right amenable if there is a finitely additive probability measure on P(M) that is semi-invariant under P. For example cell
spaces with finite sets of cells, abelian groups, and finitely right generated cell spaces with finite stabilisers of sub-exponential growth are
right amenable, in particular, quotients of finitely generated groups of
sub-exponential growth by finite subgroups acted on by left multiplication. A net of non-empty and finite subsets of M is a right Følner net
if, broadly speaking, these subsets are asymptotically invariant under
P. A finite subset E of G/G0 and two partitions {Ae }e∈E and {Be }e∈E
of M constitute a right paradoxical decomposition if the map _ P e is
injective on Ae and Be , and the family {(Ae P e) ∪· (Be P e)}e∈E is a
partition of M. The Tarski-Følner theorem states that right amenability, the existence of right Følner nets, and the non-existence of right
paradoxical decompositions are equivalent. We prove it in [7] for cell
spaces with finite stabilisers.
A cell space R is finitely right generated if there is a finite subset S of
G/G0 such that, for each point m ∈ M, there is a family {si }i∈{1,2,...,k}
of elements in S ∪ S −1 such that m = (((m0 P s1 ) P s2 ) P · · · ) P sk . The
finite right generating set S induces the S-Cayley graph structure on
M: For each point m ∈ M and each generator s ∈ S, there is an edge
from m to m P s. The length of the shortest path between two points
of M yields the S-metric. The ball of radius ρ ∈ N0 centred at m ∈ M,
denoted by BS (m, ρ), is the set of all points whose distance to m is less
than or equal to ρ. The S-growth function is the map γS : N0 → N0 ,
k 7→ |BS (m, k)|; the growth type of R, which does not depend on S, is
the equivalence class [γS ]∼ , where two growth functions are equivalent
if they dominate each other; and the S-growth rate is the limit point
p
of the sequence ( k γS (k))k∈K .

RIGHT AMENABILITY AND GROWTH

3

A finitely right generated cell space R is said to have sub-exponential
growth if its growth type is not [exp]∼ , which is the case if and only if
its growth rates are 1. The S-isoperimetric constant is a real number
between 0 and 1 that measures, broadly speaking, the invariance under
P↾M ×S that a finite subset of M can have, where 0 means maximally
and 1 minimally invariant. In the case that G0 is finite, this constant
is 0 if and only if R is right amenable, and if R has sub-exponential
growth, then it is right amenable, and if G has sub-exponential growth,
then so has R.
Cayley graphs were introduced by Arthur Cayley in his paper ‘Desiderata and suggestions: No. 2. The Theory of groups: graphical
representation’[1]. The notion of growth was introduced by Vadim Arsenyevich Efremovich and Albert S. Švarc in their papers ‘The geometry
of proximity’[3] and ‘A volume invariant of coverings’[5]. Mikhail Leonidovich Gromov was the first to study groups through their word metrics, see for example his paper ‘Infinite Groups as Geometric Objects’[4].
The present paper is greatly inspired by the monograph ‘Cellular Automata and Groups’[2] by Tullio Ceccherini-Silberstein and Michel Coornaert.
In Section 1 we introduce right generating sets. In Section 2 we
recapitulate directed multigraphs. In Section 3 we introduce Cayley
graphs induced by right generating sets. In Section 4 we introduce
metrics and lengths induced by Cayley graphs. In Section 5 we consider balls and spheres induced by metrics. In Section 6 we consider
interiors, closures, and boundaries of any thickness of sets. In Section 7 we recapitulate growth functions and types. In Section 8 we
introduce growth functions and types of cell spaces. In Section 9 we
introduce growth rates of cell spaces. In Section 10 we prove that right
amenability and having isoperimetric constant 0 are equivalent, and we
characterise right Følner nets. And in Section 11 we prove that having
sub-exponential growth implies right amenability.
Preliminary Notions. A left group set is a triple (M, G, ⊲), where M is
a set, G is a group, and ⊲ is a map from G × M to M, called left group
action of G on M, such that G → Sym(M), g 7→ [g ⊲ _], is a group

4

SIMON WACKER

homomorphism. The action ⊲ is transitive if M is non-empty and for
each m ∈ M the map _ ⊲ m is surjective; and free if for each m ∈ M
the map _ ⊲ m is injective. For each m ∈ M, the set G ⊲ m is the orbit
of m, the set Gm = (_ ⊲ m)−1 (m) is the stabiliser of m, and, for each
m′ ∈ M, the set Gm,m′ = (_ ⊲ m)−1 (m′ ) is the transporter of m to m′ .
A left homogeneous space is a left group set M = (M, G, ⊲) such
that ⊲ is transitive. A coordinate system for M is a tuple K = (m0 ,
{gm0 ,m }m∈M ), where m0 ∈ M and for each m ∈ M we have gm0 ,m ⊲m0 =
m. The stabiliser Gm0 is denoted by G0 . The tuple R = (M, K) is a cell
−1
space. The map P : M × G/G0 → M, (m, gG0 ) 7→ gm0 ,m ggm
⊲ m (=
0 ,m
gm0 ,m g ⊲m0) is a right semi-action of G/G0 on M with defect G0 , which
means that
∀ m ∈ M : m P G0 = m,

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

∀ g ∈ G/G0 ∀ A ⊆ M : (_ P g)↾A injective =⇒ µ(A P g) = µ(A) ,

in which case the cell space R = (M, K) is called right amenable.
When the stabiliser G0 is finite, that is the case if and only if there
is a right Følner net in R indexed by (I, ≤), which is a net {Fi }i∈I in
{F ⊆ M | F 6= ∅, F finite} such that
∀ g ∈ G/G0 : lim
i∈I

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

RIGHT AMENABILITY AND GROWTH

5

1. Right Generating Sets
In this section, let R = ((M, G, ⊲), (m0, {gm0 ,m }m∈M )) be a cell space.
In Definition 1.1 we define right generating sets of R. And in
Lemma 1.4 we show how generating sets of G induce right ones of
R.
Definition 1.1. Let S be a subset of G/G0 such that G0 · S ⊆ S.

(1) The set {g −1G0 | s ∈ S, g ∈ s} is denoted by S −1 .
(2) The set S is said to right generate R, called right generating
set of R, and each element s ∈ S is called right generator if
and only if, for each element m ∈ M, there is a non-negative
integer k ∈ N0 and there is a family {si }i∈{1,2,...,k} of elements
in S ∪ S −1 such that



(m0 P s1 ) P s2 P · · · P sk = m.

(3) The set S is called symmetric if and only if S −1 ⊆ S.

Definition 1.2. The cell space R is called finitely right generated if
and only if there is a right generating set of R that is finite.
Remark 1.3. If S is a right generating set of R, then S ∪ S −1 is a
symmetric one; and, if S is also finite and G0 is finite, then S ∪ S −1 is
finite.
Lemma 1.4. Let T be a generating set of G. The set S = {g0 · tG0 |
g0 ∈ G0 , t ∈ T } is a right generating set of R. And, if T is symmetric,
then so is S. And, if T and G0 are finite, then so is S.
Proof. Let m ∈ M. Then, because P is transitive, there is a g ∈ G
such that m0 P gG0 = m. Moreover, there is a k ∈ N0 and there is a
{ti }i∈{1,2,...,k} ⊆ T ∪ T −1 such that t1 t2 · · · tk = g. Furthermore, there is
a {gi,0}i∈{2,3,...,k} ⊆ G0 such that



(m0 P t1 G0 ) P g2,0 t2 G0 P · · · P gk,0 tk G0 = m0 P t1 t2 · · · tk G0 = m.
In conclusion, because t1 G0 ∈ S ∪ S −1 and {gi,0 ti G0 }i∈{2,3,...,k} ⊆ S ∪
S −1 , the set S is a right generating set of R.

6

SIMON WACKER

Let T be symmetric. Furthermore, let s ∈ S and let g ∈ s. Then,
there is a g0 ∈ G0 , there is a t ∈ T , and there is a g0′ ∈ G0 such that
g0 · tG0 = s and g0 tg0′ = g. Hence, because (g0′ )−1 ∈ G0 and t−1 ∈ T ,
g −1 G0 = (g0′ )−1 t−1 g0−1 G0 = (g0′ )−1 · t−1 G0 ∈ S.
In conclusion, S −1 ⊆ S.
If T and G0 are finite, then so is S.



2. Directed Multigraphs
Definition 2.1. Let V and E be two sets, and let σ and τ be two
maps from E to V . The quadruple G = (V, E, σ, τ ) is called directed
multigraph; each element v ∈ V is called vertex ; each element e ∈ E is
called edge from σ(e) to τ (e); for each element e ∈ E, the vertex σ(e)
is called source of e and the vertex τ (e) is called target of e.
Definition 2.2. Let G = (V, E, σ, τ ) be a directed multigraph and let
e be an edge of G. The edge e is called loop if and only if τ (e) = σ(e).
Definition 2.3. Let G = (V, E, σ, τ ) be a directed multigraph and let
v be a vertex of G.
(1) The cardinal number

deg+ (v) = |{e ∈ E | σ(e) = v}|
is called out-degree of v.
(2) The cardinal number
deg− (v) = |{e ∈ E | τ (e) = v}|
is called in-degree of v.
(3) The cardinal number
deg(v) = deg+ (v) + deg− (v)
is called degree of v.
Definition 2.4. Let G be a directed multigraph, and let v and v ′ be
two vertices of G. The vertices v and v ′ are called adjacent if and only
if there is an edge from v to v ′ or one from v ′ to v.

RIGHT AMENABILITY AND GROWTH

7

Definition 2.5. Let G = (V, E, σ, τ ) be a directed multigraph and let
p = (ei )i∈{1,2,...,k} be a finite sequence of edges of G. The sequence p
is called path from σ(e1 ) to τ (ek ) if and only if, for each index i ∈
{1, 2, . . . , k − 1}, we have τ (ei ) = σ(ei+1 ).
Definition 2.6. Let G be a directed multigraph and let p = (ei )i∈{1,2,...,k}
be a path in G. The number |p| = k is called length of p.
Definition 2.7. Let G = (V, E, σ, τ ) be a directed multigraph. It is
called
(1) symmetric if and only if, for each edge e ∈ E, there is an edge
e′ ∈ E such that σ(e′ ) = τ (e) and τ (e′ ) = σ(e);
(2) strongly connected if and only if, for each vertex v ∈ V and each
vertex v ′ ∈ V , there is a path p from v to v ′ ;
(3) regular if and only if all vertices of G have the same degree and,
for each vertex v ∈ V , we have deg− (v) = deg+ (v).
Definition 2.8. Let G = (V, E, σ, τ ) be a directed multigraph, let W
be a subset of V , let F be the set {e ∈ E | σ(e), τ (e) ∈ W }, let
ς be the map σ↾F →W , and let υ be the map τ ↾F →W . The subgraph
G[W ] = (W, F, ς, υ) of G is called induced by W .
Definition 2.9. Let G = (V, E, σ, τ ) be a symmetric and strongly
connected directed multigraph. The map
d : V × V → N0 ,

(v, v ′ ) 7→ min{|p| | p path from v to v ′ },

is a metric on V and called distance on G.
Definition 2.10. Let (V, E, σ, τ ) be a directed multigraph, let Λ be a
set, and let λ be a map from E to Λ. The quintuple G = (V, E, σ, τ, λ)
is called Λ-edge-labelled directed multigraph.
3. Cayley Graphs
In this section, let R = ((M, G, ⊲), (m0 , {gm0 ,m }m∈M )) be a cell space
and let S be a right generating set of R.

8

SIMON WACKER

Definition 3.1. Let E be the set {(m, s, m P s) | m ∈ M, s ∈ S}, and
let σ : E → M, λ : E → S, and τ : E → M be the projections to the
first, second, and third component respectively. The S-edge-labelled
directed multigraph G = (M, E, σ, τ, λ) is called S-Cayley graph of R.
Remark 3.2. Let G be the S-Cayley graph of R.

(1) If S is symmetric, then G is symmetric and strongly connected.
(2) The following statements are equivalent:
(a) G0 ∈ S;
(b) At least one vertex of G has a loop;
(c) All vertices of G have a loop.
(3) Because P is free, there are no multiple edges in G.

Remark 3.3. Let G be the S-Cayley graph of R, and let m and m′
be two vertices of G. The vertices m and m′ are adjacent if and only if
there is an element s ∈ S such that m P s = m′ .
Remark 3.4. Let G be the S-Cayley graph of R and let m be a vertex
of G. The map
S → m P S,
s 7→ m P s,

is a bijection onto the out-neighbourhood of m. It is injective, because
P is free, and it is surjective, by definition. Therefore, if S is symmetric,
then the degree of m is 2|S| in cardinal arithmetic and the graph G is
regular.
4. Metrics and Lengths
In this section, let R = ((M, G, ⊲), (m0 , {gm0 ,m }m∈M )) be a cell space
and let S be a symmetric right generating set of R.
In Definitions 4.1 and 4.6 we define the S-metric dS and the S-length
|_|S on R induced by the S-Cayley graph. And in Lemmas 4.3 and 4.4
we show how the S-metric relates to the left group action ⊲ and the
right quotient set semi-action P.
Definition 4.1. The distance on the S-Cayley graph of R is called
S-metric on R and denoted by dS .

RIGHT AMENABILITY AND GROWTH

9

Remark 4.2. The S-metric on R is
d S : M × M → N0 ,

(m, m′ ) 7→ min{k ∈ N0 | ∃{si }i∈{1,2,...,k} ⊆ S :

(((m P s1 ) P s2 ) P · · · ) P sk = m′ }.

Lemma 4.3. Let m and m′ be two elements of M, and let s be an
element of S. Then, dS (m, m′ P s) ≤ dS (m, m′ ) + 1.
Proof. Let k = dS (m, m′ ). Then, there is a {si }i∈{1,2,...,k} ⊆ S such that
(((m P s1 ) P s2 ) P · · · ) P sk = m′ . Hence, ((((m P s1 ) P s2 ) P · · · ) P sk ) P s =
m′ P s. Therefore, dS (m, m′ P s) ≤ dS (m, m′ ) + 1.

Lemma 4.4. Let m and m′ be two elements of M, and let g be an
element of G. Then, dS (g ⊲ m, g ⊲ m′ ) = dS (m, m′ ).
Proof. Let k = dS (g ⊲ m, g ⊲ m′ ). Then, there is a {si }i∈{1,2,...,k} ⊆ S
such that ((((g ⊲ m) P s1 ) P s2 ) P · · · ) P sk = g ⊲ m′ . Moreover, because
⊲ and P semi-commute, for each i ∈ {1, 2, . . . , k}, there is a gi,0 ∈ G0 ,
such that




(g ⊲ m) P s1 P s2 P · · · P sk




=
g ⊲ (m P g1,0 · s1 ) P s2 P · · · P sk
= ···

=g⊲



(m P g1,0 · s1 ) P g2,0 · s2




P · · · P gk,0 · sk .


Hence, (((m P g1,0 · s1 ) P g2,0 · s2 ) P · · · ) P gk,0 · sk = m′ . Therefore,
dS (m, m′ ) ≤ k = dS (g ⊲ m, g ⊲ m′ ).
Taking g ⊲ m for m, g ⊲ m′ for m′ , and g −1 for g yields dS (g ⊲ m, g ⊲
m′ ) ≤ dS (g −1 ⊲ (g ⊲ m), g −1 ⊲ (g ⊲ m′ )) = dS (m, m′ ). In conclusion,
dS (g ⊲ m, g ⊲ m′ ) = dS (m, m′ ).

Lemma 4.5. Let m and m′ be two elements of M, let {si }i∈{1,2,...,dS (m,m′ )}
be a family of elements in S such that m′ = (((m P s1 ) P s2 ) P · · · ) P
sdS (m,m′ ) , let i be an element of {0, 1, 2, . . . , dS (m, m′ )}, and let mi =
(((m P s1 ) P s2 ) P · · · ) P si Then, dS (m, mi ) = i.

10

SIMON WACKER

Proof. By definition of mi , we have dS (m, mi ) ≤ i and dS (mi , m′ ) ≤
dS (m, m′ ) − i. Therefore, because dS (m, m′ ) ≤ dS (m, mi ) + dS (mi , m′ ),
we have dS (m, mi ) ≥ dS (m, m′ )−dS (mi , m′ ) ≥ dS (m, m′ )−(dS (m, m′ )−
i) = i. In conclusion, dS (m, mi ) = i.

Definition 4.6. The map
|_|S : M → N0 ,
is called S-length on R.

m 7→ dS (m0 , m),

Remark 4.7. For each element m ∈ M, we have |m|S = 0 if and only
if m = m0 .
5. Balls and Spheres
In this section, let R = ((M, G, ⊲), (m0 , {gm0 ,m }m∈M )) be a cell space
and let S be a symmetric right generating set of R.
In Definition 5.1 we define balls BS and spheres SS in the S-metric
on R. And in the lemmata and corollaries of this section we show how
balls, spheres, the left group action ⊲, the right quotient set semi-action
P, and the S-metric relate to each other.
Definition 5.1. Let m be an element of M and let ρ be a non-negative
integer.
(1) The set
BS (m, ρ) = {m′ ∈ M | dS (m, m′ ) ≤ ρ}

is called ball of radius ρ centred at m. The ball of radius ρ
centred at m0 is denoted by BS (ρ).
(2) The set
SS (m, ρ) = {m′ ∈ M | dS (m, m′ ) = ρ}

is called sphere of radius ρ centred at m. The sphere of radius
ρ centred at m0 is denoted by SS (ρ).
Remark 5.2. For each element m ∈ M, we have SS (m, 0) = BS (m, 0),
and, for each positive integer ρ ∈ N+ , we have SS (m, ρ) = BS (m, ρ) r
BS (m, ρ − 1).

RIGHT AMENABILITY AND GROWTH

11

Remark 5.3. For each non-negative integer ρ ∈ N0 ,
BS (ρ) = {m ∈ M | |m|S ≤ ρ}

and

SS (ρ) = {m ∈ M | |m|S = ρ}.
Definition 5.4. Let (Ak )k∈N0 be a sequence of sets.
(1) The set
lim inf Ak =
k→∞

[ \

Aj

k∈N0 j∈N0
j≥k

is called limit inferior of (Ak )k∈N0 .
(2) The set
\ [
Aj
lim sup Ak =
k→∞

k∈N0 j∈N0
j≥k

is called limit superior of (Ak )k∈N0 .
(3) Let A be a set. The sequence (Ak )k∈N0 is said to converge to A,
the set A is called limit set of (Ak )k∈N0 , and A is denoted by
limk→∞ Ak if and only if lim inf k→∞ Ak = lim supk→∞ Ak = A.
(4) The sequence (Ak )k∈N0 is called convergent if and only if lim inf k→∞ Ak =
lim supk→∞ Ak .
Lemma 5.5. Let (Ak )k∈N0 be a non-decreasing or non-increasing seT
S
quence of sets. It converges to k∈N0 Ak or k∈N0 Ak respectively. 

Remark 5.6. For each element m ∈ M, we have BS (m, 0) = {m}, and
the sequence (BS (m, ρ))ρ∈N0 is non-decreasing with respect to inclusion
and converges to M, and hence, for each non-negative integer ρ,
[
BS (m, ρ′ ) = M.
ρ′ ∈N0
ρ′ ≥ρ

Remark 5.7. For each element m ∈ M and each non-negative integer
ρ ∈ N0 , in cardinal arithmetic,
because the map

|BS (m, ρ)| ≤ (1 + |S|)ρ ,

({G0 } ∪ S)ρ → BS (m, ρ),

12

SIMON WACKER

(s1 , s2 , . . . , sρ ) 7→ (((m P s1 ) P s2 ) P · · · ) P sρ ,
is surjective and |{G0 } ∪ S|ρ ≤ (1 + |S|)ρ .
Lemma 5.8. Let m be an element of M, let ρ be a non-negative integer,
and let s be an element of S. Then, BS (m, ρ) P s ⊆ BS (m, ρ + 1).
Proof. Let m′ ∈ BS (m, ρ) P s. Then, there is an m′′ ∈ BS (m, ρ) such
that m′′ P s = m′ . Hence, according to Lemma 4.3, we have dS (m, m′ ) =
dS (m, m′′ P s) ≤ dS (m, m′′ ) + 1 ≤ ρ + 1. Therefore, m′ ∈ BS (m, ρ + 1).
In conclusion, BS (m, ρ) P s ⊆ BS (m, ρ + 1).

Lemma 5.9. Let m be an element of M, let ρ be a non-negative integer,
and let g be an element of G. Then, g ⊲ BS (m, ρ) = BS (g ⊲ m, ρ).
Proof. First, let m′ ∈ g ⊲ BS (m, ρ). Then, g −1 ⊲ m′ ∈ BS (m, ρ) and thus
dS (m, g −1 ⊲ m′ ) ≤ ρ. Hence, according to Lemma 4.4,
dS (g ⊲ m, m′ ) = dS (g −1 ⊲ (g ⊲ m), g −1 ⊲ m′ )
= dS (m, g −1 ⊲ m′ )
≤ ρ.
Therefore, m′ ∈ BS (g ⊲m, ρ). In conclusion, g ⊲BS (m, ρ) ⊆ BS (g ⊲m, ρ).
Secondly, let m′ ∈ BS (g ⊲ m, ρ). Then, dS (g ⊲ m, m′ ) ≤ ρ. Thus,
according to Lemma 4.4,
dS (m, g −1 ⊲ m′ ) = dS (g ⊲ m, g ⊲ (g −1 ⊲ m′ ))
= dS (g ⊲ m, m′ )
≤ ρ.
Hence, g −1 ⊲m′ ∈ BS (m, ρ). Therefore, m′ ∈ g⊲BS (m, ρ). In conclusion,
BS (g ⊲ m, ρ) ⊆ g ⊲ BS (m, ρ).

Corollary 5.10. Let m be an element of M, let ρ be a non-negative integer, and let gm be an element of Gm . Then, gm ⊲BS (m, ρ) = BS (m, ρ).
In particular, Gm ⊲ BS (m, ρ) = BS (m, ρ).
Proof. Because gm ⊲ m = m, this is a direct consequence of Lemma 5.9.


RIGHT AMENABILITY AND GROWTH

13

Corollary 5.11. Let m and m′ be two elements of M, and let ρ be a
non-negative integer. Then, |BS (m, ρ)| = |BS (m′ , ρ)|.
Proof. Because there is a g ∈ G such that g ⊲ m = m′ , and g ⊲ _ is
injective, this is a direct consequence of Lemma 5.9.

Lemma 5.12. Let m and m′ be two elements of M and identify M
with G/G0 by [m 7→ Gm0 ,m ]. Then, m P m′ = gm0 ,m ⊲ m′ .
Proof. Let g ∈ Gm0 ,m′ . Then, Gm0 ,m′ = gG0 . Hence,
m P m′ = m P Gm0 ,m′
= m P gG0
= gm0 ,m g ⊲ m0
= gm0 ,m ⊲ (g ⊲ m0 )
= gm0 ,m ⊲ m′ .



Lemma 5.13. Let m, m′ , and m′′ be three elements of M and identify
M with G/G0 by [m 7→ Gm0 ,m ]. Then, there is an element g0 ∈ G0
such that (m P m′ ) P m′′ = m P (m′ P (g0 ⊲ m′′ )).
Proof. Because P is a right semi-action, there is an element g0 ∈ G0
such that m P gm0 ,m′ · g0 · Gm0 ,m′′ = (m P gm0 ,m′ G0 ) P Gm0 ,m′′ . And, under
the identification of M with G/G0 , we have Gm0 ,m′′ = m′′ , gm0 ,m′ G0 =
Gm0 ,m′ = m′ , and gm0 ,m′ · g0 · Gm0 ,m′′ = m′ P (g0 ⊲ m′′ ). Therefore,
m P (m′ P (g0 ⊲ m′′ )) = (m P m′ ) P m′′ .

Corollary 5.14. Let m be an element of M, let ρ be a non-negative
integer, and identify M with G/G0 by [m 7→ Gm0 ,m ]. Then, mPBS (ρ) =
BS (m, ρ).
Proof. According to Lemma 5.12 and Lemma 5.9,
m P BS (ρ) = gm0 ,m ⊲ BS (ρ)
= gm0 ,m ⊲ BS (m0 , ρ)
= BS (gm0 ,m ⊲ m0 , ρ)
= BS (m, ρ).



14

SIMON WACKER

Corollary 5.15. Let m be an element of M, let ρ and ρ′ be two nonnegative integers, and identify M with G/G0 by [m 7→ Gm0 ,m ]. Then,
BS (m, ρ) P BS (ρ′ ) = BS (m, ρ + ρ′ ).
Proof. First, let m′ ∈ BS (m, ρ) P BS (ρ′ ). Then, there is an m′′ ∈
BS (m, ρ) such that m′ ∈ m′′ P BS (ρ′ ). Moreover, according to Corollary 5.14, we have m′′ P BS (ρ′ ) = BS (m′′ , ρ′ ). Hence, because dS is
subadditive, dS (m, m′ ) ≤ dS (m, m′′ ) + dS (m′′ , m′ ) ≤ ρ + ρ′ . Therefore,
m′ ∈ BS (m, ρ + ρ′ ). In conclusion, BS (m, ρ) P BS (ρ′ ) ⊆ BS (m, ρ + ρ′ ).
Secondly, let m′ ∈ BS (m, ρ + ρ′ ).

Case 1: m′ ∈ BS (m, ρ). Then, because m0 ∈ BS (ρ′ ), we have
m′ = m′ P m0 ∈ BS (m, ρ) P BS (ρ′ ).
Case 2: m′ ∈
/ BS (m, ρ). Then, there is a j ∈ {ρ + 1, ρ + 2, . . . , ρ +
′
ρ } and there is a {si }i∈{1,2,...,j} ⊆ S such that (((m′′ P sρ+1 ) P
sρ+2 ) P · · · ) P sρ+ρ′ = m′ , where m′′ = (((m P s1 ) P s2 ) P · · · ) P sρ ∈
BS (m, ρ). Hence, m′ ∈ BS (m′′ , ρ′ ) = m′′ P BS (ρ′ ) ⊆ BS (m, ρ) P
BS (ρ′ ).

In either case, m′ ∈ BS (m, ρ) P BS (ρ′ ). In conclusion, BS (m, ρ + ρ′ ) ⊆
BS (m, ρ) P BS (ρ′ ).

Definition 5.16. Let A and A′ be two subsets of M. The non-negative
number or infinity
dS (A, A′ ) = min{dS (a, a′ ) | a ∈ A, a′ ∈ A′ }

is called distance of A and A′ , where we put min ∅ = ∞. In the case
that A = {a}, we write dS (a, A′ ) in place of dS ({a}, A′ ); and in the
case that A′ = {a′ }, we write dS (A, a′ ) in place of dS (A, {a′ }).
Lemma 5.17. Let m and m′ be two elements of M, and let ρ be a nonnegative integer such that ρ ≤ dS (m, m′ ). Then, dS (SS (m, ρ), m′ ) =
dS (m, m′ ) − ρ.
Proof. Let ρ′ = dS (m, m′ ).
Then, there is a {si }i∈{1,2,...,ρ′ } such that (((m P s1 ) P s2 ) P · · · ) P sρ′ =
′
m . Let m′′ = (((m P s1 ) P s2 ) P · · · ) P sρ . Then, (((m′′ P sρ+1 ) P sρ+2 ) P
· · · ) P sρ′ = m′ . And, according to Lemma 4.5, we have m′′ ∈ SS (m, ρ).
Thus, dS (SS (m, ρ), m′ ) ≤ dS (m′′ , m′ ) ≤ ρ′ − ρ.

RIGHT AMENABILITY AND GROWTH

15

Suppose that dS (SS (m, ρ), m′ ) < ρ′ − ρ. Then, there is an m′′ ∈
SS (m, ρ) such that dS (m′′ , m′ ) < ρ′ −ρ. Hence, dS (m, m′ ) ≤ dS (m, m′′ )+
dS (m′′ , m′ ) < ρ+(ρ′ −ρ) = ρ′ , which contradicts dS (m, m′ ) = ρ′ . Therefore, dS (SS (m, ρ), m′ ) ≥ ρ′ − ρ.
In conclusion, dS (SS (m, ρ), m′ ) = ρ′ − ρ = dS (m, m′ ) − ρ.

Corollary 5.18. Let m be an element of M, and let ρ and ρ′ be two
non-negative integers such that the spheres SS (m, ρ) and SS (m, ρ′ ) are
non-empty. Then, dS (SS (m, ρ), SS (m, ρ′ )) = |ρ − ρ′ |.
Proof. Without loss of generality, let ρ ≤ ρ′ . Then, for each m′ ∈
SS (m, ρ′ ), according to Lemma 5.17, we have dS (SS (m, ρ), m′ ) = ρ′ − ρ.
In conclusion, dS (SS (m, ρ), SS (m, ρ′ )) = ρ′ − ρ = |ρ − ρ′ |.

Corollary 5.19. Let m and m′ be two elements of M, and let ρ be a
non-negative integer. Then, dS (SS (m, ρ), m′ ) ≥ |dS (m, m′ ) − ρ|.
Proof. If SS (m, ρ) = ∅, then dS (SS (m, ρ), m′ ) = ∞ ≥ |dS (m, m′ ) − ρ|.
Otherwise, let ρ′ = dS (m, m′ ). Then, SS (m, ρ′ ) 6= ∅. Hence, according
to Corollary 5.18, we have dS (SS (m, ρ), m′ ) ≥ dS (SS (m, ρ), SS (m, ρ′ )) =
|ρ − ρ′ | = |dS (m, m′ ) − ρ|.

Lemma 5.20. Let m and m′ be two elements of M, and let ρ and
ρ′ be two non-negative integers such that ρ + ρ′ ≤ dS (m, m′ ). Then,
dS (BS (m, ρ), BS (m′ , ρ′ )) = dS (m, m′ ) − (ρ + ρ′ ).
Proof. For each mρ ∈ BS (m, ρ) and each m′ρ′ ∈ BS (m′ , ρ′ ), because dS
is subadditive,
dS (m, m′ ) ≤ dS (m, mρ ) + dS (mρ , m′ρ′ ) + dS (m′ρ′ , m′ )
≤ ρ + dS (mρ , m′ρ′ ) + ρ′ ,

and hence dS (mρ , m′ρ′ ) ≥ dS (m, m′ )−(ρ+ρ′ ). Therefore, dS (BS (m, ρ), BS (m′ , ρ′ )) ≥
dS (m, m′ ) − (ρ + ρ′ ).
Moreover, there is a {si }i∈{1,2,...,dS (m,m′ )} such that (((mPs1 )Ps2 ) · · · )P
sdS (m,m′ ) = m′ . Let mρ = ((m P s1 ) P · · · ) P sρ and let m′ρ′ = ((mρ P
sρ+1 ) P · · · ) P sdS (m,m′ )−ρ′ . Then, mρ ∈ BS (m, ρ) and, because (((m′ρ′ P
sdS (m,m′ )−ρ′ +1 ) P sdS (m,m′ )−ρ′ +2 ) · · · ) P sdS (m,m′ ) = m′ , we have m′ρ′ ∈

16

SIMON WACKER

BS (m′ , ρ′ ). And, dS (mρ , m′ρ′ ) ≤ dS (m, m′ )−ρ′ −ρ. Therefore, dS (BS (m, ρ), BS (m′ , ρ′ )) ≤
dS (m, m′ ) − (ρ + ρ′ ).
In conclusion, dS (BS (m, ρ), BS (m′ , ρ′ )) = dS (m, m′ ) − ρ − ρ′ .

6. Interiors, Closures, and Boundaries
In this section, let R = ((M, G, ⊲), (m0 , {gm0 ,m }m∈M )) be a cell space
and let S be a symmetric right generating set of R.
In Definition 6.1 we define θ-interiors A−θ , θ-closures A+θ , and (internal/external) θ-boundaries ∂θ A, ∂θ− A, or ∂θ+ A. And in the lemmata
and corollaries of this section we characterise them and show how they
and the S-metric relate to each other.
Definition 6.1. Let A be a subset of M, let θ be a non-negative
integer, and identify M with G/G0 by [m 7→ Gm0 ,m ].
(1) The set

A−θ = A−BS (θ)

= {m ∈ M | m P BS (θ) ⊆ A}

is called θ-interior of A.
(2) The set
A+θ = A+BS (θ)




= {m ∈ M | (m P BS (θ)) ∩ A 6= ∅}

is called θ-closure of A.
(3) The set
∂θ A = A+θ r A−θ


= A+BS (θ) r A−BS (θ) = ∂BS (θ) A

is called θ-boundary of A.
(4) The set
∂θ− A = A r A−θ

is called internal θ-boundary of A.
(5) The set
∂θ+ A = A+θ r A
is called external θ-boundary of A.
Lemma 6.2. Let A be a subset of M and identify M with G/G0 by
[m 7→ Gm0 ,m ]. For each non-negative integer θ ∈ N0 ,
(1) A−θ = {m ∈ A | BS (m, θ) ⊆ A};

RIGHT AMENABILITY AND GROWTH

(2) A+θ =

[

17

BS (m, θ) = A P BS (θ).

m∈A

Proof. Let θ ∈ N0 and let m ∈ M.

(1) According to Corollary 5.14,
A−θ = {m ∈ M | BS (m, θ) ⊆ A}.
Therefore, because m ∈ BS (m, θ),
A−θ = {m ∈ A | BS (m, θ) ⊆ A}.
(2) According to Corollary 5.14,
A+θ = {m ∈ M | (m P BS (θ)) ∩ A 6= ∅}

= {m ∈ M | ∃ m′ ∈ A : m′ ∈ m P BS (θ)}
= {m ∈ M | ∃ m′ ∈ A : m′ ∈ BS (m, θ)}.

Moreover, because of the symmetry of dS , for each m′ ∈ A,
m′ ∈ BS (m, θ) ⇐⇒ dS (m, m′ ) ≤ θ

⇐⇒ m ∈ BS (m′ , θ).

Hence, according to Corollary 5.14,
A+θ = {m ∈ M | ∃ m′ ∈ A : m ∈ BS (m′ , θ)}
[
=
BS (m′ , θ)
m′ ∈A

=

[

m′ P BS (θ)

m′ ∈A

= A P BS (θ).



Corollary 6.3. Let m be an element of M, let ρ be a non-negative
integer, and let θ be a non-negative integer. Then,
(1) BS (m, ρ)−θ ⊇ BS (m, ρ − θ);
(2) BS (m, ρ)+θ = BS (m, ρ + θ);
(3) ∂θ BS (m, ρ) ⊆ BS (m, ρ + θ) r BS (m, ρ − θ).
Proof.

(1) According to Corollary 5.15, we have BS (m, ρ − θ) P
BS (θ) ⊆ BS (m, ρ). Hence, according to Definition 6.1, we have
BS (m, ρ − θ) ⊆ BS (m, ρ)−θ .

18

SIMON WACKER

(2) According to Item 2 of Lemma 6.2 and Corollary 5.15, we have
BS (m, ρ)+θ = BS (m, ρ) P BS (θ) = BS (m, ρ + θ).
(3) This is a direct consequence of Items 1 and 2.

Lemma 6.4. Let A be a subset of M, and let θ and θ′ be two nonnegative integers. The following statements hold:
(1)
(2)
(3)
(4)
(5)
Proof.

′

′

(A−θ )−θ = A−(θ+θ ) ;
′
∂θ−′ A−θ = A−θ r A−(θ+θ ) ;
′
′
(A+θ )+θ = A+(θ+θ ) ;
′
∂θ+′ A+θ = A+(θ+θ ) r A+θ ;
′
′
′
′
Let θ′ ≤ θ. Then, A+(θ−θ ) ⊆ (A+θ )−θ and (A−θ )+θ ⊆ A−(θ−θ ) .
(1) For each m′ ∈ A, according to Corollary 5.14 and Lemma 6.2,
we have m′ ∈ A−θ if and only if m′ P BS (θ) = BS (m′ , θ) ⊆ A.
Hence, according to Corollary 5.15,
′

(A−θ )−θ = {m′ ∈ A | BS (m′ , θ′ ) ⊆ A−θ }

= {m′ ∈ A | BS (m′ , θ′ ) P BS (θ) ⊆ A}
= {m′ ∈ A | BS (m′ , θ + θ′ ) ⊆ A}
′

= A−(θ+θ ) .

(2) According to Item 1,
∂θ−′ A−θ = A−θ r (A−θ )−θ

′

′

= A−θ r A−(θ+θ ) .
(3) According to Lemma 6.2 and Corollary 5.15,
′

(A+θ )+θ = A+θ P BS (θ′ )
=

[

BS (m, θ)

m∈A

=

[

!

P BS (θ ′ )

BS (m, θ) P BS (θ′ )

m∈A

=

[

BS (m, θ + θ′ )

m∈A
′

= A+(θ+θ ) .

RIGHT AMENABILITY AND GROWTH

19

(4) According to Item 3,
′

∂θ+′ A+θ = (A+θ )+θ r A+θ
′

= A+(θ+θ ) r A+θ .
(5) According to Lemma 6.2 and Item 3,
′

′

A+(θ−θ ) P BS (θ′ ) = (A+(θ−θ ) )+θ
′

′

′

= A+((θ−θ )+θ )
= A+θ .
Thus, for each m ∈ A+(θ−θ ) , according to Corollary 5.15, we
have BS (m, θ′ ) = m P BS (θ′ ) ⊆ A+θ and, in particular, m ∈
′
A+θ . Therefore, according to Lemma 6.2, we have A+(θ−θ ) ⊆
′
(A+θ )−θ .
According to Lemma 6.2, Item 3, and Definition 6.1,
′

(A−θ )+θ

′

P BS (θ

′

′

− θ′ ) = ((A−θ )+θ )+(θ−θ )
′

′

= (A−θ )+θ +(θ−θ )

= (A−θ )+θ
= A−θ P BS (θ)
⊆ A.
Therefore, according to Definition 6.1, we have (A−θ )+θ ⊆
′
A−(θ−θ ) .

′

Lemma 6.5. Let k be a non-negative integer, and let A and A′ be two
subsets of M. Then, dS (A, A′ r A+k ) ≥ k + 1.
Proof. If A or A′ r A+k is empty, then dS (A, A′ r A+k ) = ∞ ≥ k + 1.
Otherwise, let m′ ∈ A′ r A+k . According to [8, Item 3 of Lemma 1], we
have A′ r A+k = (A′ r A)−k . Hence, according to Lemma 6.2, we have
BS (m′ , k) ⊆ A′ rA. Therefore, for each m ∈ A, we have m ∈
/ BS (m′ , k)
and hence dS (m, m′ ) ≥ k + 1. Thus, dS (A, m′ ) ≥ k + 1. In conclusion,
dS (A, A′ r A+k ) ≥ k + 1.

Corollary 6.6. Let k be a non-negative integer, let k ′ be a positive
integer, and let A be a subset of M. Then, dS (A, ∂k+′ A+k ) ≥ k + 1.

20

SIMON WACKER

Proof. Because ∂k+′ A+k = (A+k )+k r A+k , this is a direct consequence
of Lemma 6.5.

′

Lemma 6.7. Let A be a finite subset of M and let S ′ be the set {G0 } ∪
S. There is a non-negative integer k ∈ N0 such that
A ⊆ {m ∈ M | ∃{s′i }i∈{1,2,...,k} ⊆ S ′ : (((m0 P s′1 ) P s′2 ) P · · · ) P s′k }.
Proof. If A is empty, then any k ∈ N0 works. Otherwise, let k =
maxa∈A dS (m0 , a). Because A is finite, we have k ∈ N0 . By the choice
of k, we have A ⊆ B(m0 , k). And, because G0 ∈ S ′ and _ P G0 = idM ,
we have B(m0 , k) = {m ∈ M | ∃{s′i }i∈{1,2,...,k} ⊆ S ′ : (((m0 P s′1 ) P s′2 ) P
· · · ) P s′k }. In conclusion, the stated inclusion holds.

7. Growth Functions And Types
In this section we recapitulate growth functions and types, more or
less as presented in the monograph ‘Cellular Automata and Groups’[2].
Definition 7.1. Let γ be a map from N0 to R≥0 . It is called growth
function if and only if it is non-decreasing, that is to say, that

∀ k ∈ N0 ∀ k ′ ∈ N0 : k ≤ k ′ =⇒ γ(k) ≤ γ(k ′ ) .
Definition 7.2. Let γ and γ ′ be two growth functions. The growth
function γ is said to dominate γ ′ and we write γ < γ ′ if and only if
∃ α ∈ N+ : ∀ k ∈ N+ : α · γ(α · k) ≥ γ ′ (k).
Definition 7.3. Let γ and γ ′ be two growth functions. They are called
equivalent and we write γ ∼ γ ′ if and only if γ < γ ′ and γ ′ < γ.
Lemma 7.4 ([2, Proposition 6.4.3]).
(1) The relation < is reflexive and transitive.
(2) The relation ∼ is an equivalence relation.
(3) If γ1 ∼ γ2 and γ1′ ∼ γ2′ , then γ1 < γ1′ implies γ2 < γ2′ .
Definition 7.5. Let γ be a growth function. The equivalence class of
γ with respect to ∼ is denoted by [γ]∼ and called growth type.

RIGHT AMENABILITY AND GROWTH

21

Definition 7.6. Let Γ and Γ′ be two growth types. The growth type
Γ is said to dominate Γ′ and we write Γ < Γ′ if and only if
∃ γ ∈ Γ ∃ γ ′ ∈ Γ′ : γ < γ ′ .
Example 7.7 ([2, Examples 6.4.4]).
(1) The growth function [k 7→ k] dominates 1 but they are not
equivalent.
Proof. For each k ∈ N+ , we have k ≥ 1(k). But, for each
α ∈ N+ , there is a k ∈ N+ , for example k = α + 1, such that
α1(αk) = α < k.

(2) Let r and s be two non-negative real numbers. Then, [k 7→
k r ] < [k 7→ k s ] if and only if r ≥ s. And, [k 7→ k r ] ∼ [k 7→ k s ]
if and only if r = s.
(3) Let γ be a growth function such that it is a polynomial function
of degree d ∈ N0 . Then, γ ∼ [k 7→ k d ].
(4) Let r and s be two elements of R>1 . Then, [k 7→ r k ] ∼ [k 7→ sk ].
In particular, [k 7→ r k ] ∼ exp.
Proof. Without loss of generality, suppose that r ≤ s. Then,
for each k ∈ N+ , we have r k ≤ sk . Hence, [k 7→ r k ] 4 [k 7→ sk ].
Moreover, let α = ⌈logr s⌉ ∈ N+ . Then, for each k ∈ N+ ,
sk = (r logr s )k = r (logr s)k ≤ r αk ≤ αr αk .

Hence, [k 7→ r k ] < [k 7→ sk ]. In conclusion, [k 7→ r k ] ∼ [k 7→
sk ].

(5) Let d be a non-negative integer. Then, exp < [k 7→ k d ] and
[k 7→ k d ] ≁ exp.
Proof. See [2, Examples 6.4.4 (d)].



Lemma 7.8. Let γ be a growth function and let d be a non-negative
integer such that [k 7→ k d ] < γ. Then, exp < γ and exp ≁ γ.
Proof. According to Item 5 of Example 7.7, we have exp < [k 7→ k d ]
and exp ≁ [k 7→ k d ]. Hence, because < is transitive and [k 7→ k d ] < γ,
we have exp < γ and exp ≁ γ.


22

SIMON WACKER

8. Cell Spaces’ Growth Functions and Types
In this section, let R = ((M, G, ⊲), (m0 , {gm0 ,m }m∈M )) be a cell space
such that there is a finite and symmetric right generating set S of R.
In Definition 8.1 we define the S-growth function γS of R. In
Lemma 8.3 and its corollaries we show that γS is dominated by exp and
that the ∼-equivalence class [γS ]∼ does not depend on S. In Definition 8.10 we define the growth type γ(R) of R as that equivalence class.
In Lemma 8.13 and its corollary we relate the inclusion-behaviour of
the sequence of balls to the cardinality of M. And in Definition 8.17 we
define the terms ‘exponential growth’, ‘sub-exponential growth’, ‘polynomial growth’, and ‘intermediate growth of R’.
Definition 8.1. The map
γ S : N0 → N0 ,

k 7→ |BS (k)|,

is called S-growth function of R.

Remark 8.2. According to Remark 5.6, we have γS (0) = 1 and the
sequence (γS (k))k∈N0 is non-decreasing with respect to the partial order
≤. Moreover, according to Remark 5.7, for each non-negative integer
k ∈ N0 , we have γS (k) ≤ (1 + |S|)k .
Lemma 8.3. Let S ′ be a finite and symmetric right generating set of
R and let α be the non-negative integer min{k ∈ N0 | BS (1) ⊆ BS ′ (k)}.
Then,
∀ m ∈ M ∀ m′ ∈ M : dS ′ (m, m′ ) ≤ α · dS (m, m′ ),
in particular,

∀ m ∈ M : |m|S ′ ≤ α · |m|S .
Proof. For each m ∈ M, let αm = min{k ∈ N0 | BS (m, 1) ⊆ BS ′ (m, k)},
in particular, αm0 = α.
Proof of: ∀ m ∈ M : αm = α. Let m ∈ M, let k ∈ N0 , and let
g ∈ Gm0 ,m . Then, because g ⊲ _ is bijective, BS (1) ⊆ BS ′ (k) if and
only if g ⊲ BS (1) ⊆ g ⊲ BS ′ (k). Moreover, according to Lemma 5.9,
we have g ⊲ BS (1) = BS (m, 1) and g ⊲ BS ′ (k) = BS ′ (m, k). Therefore,

RIGHT AMENABILITY AND GROWTH

23

BS (1) ⊆ BS ′ (k) if and only if BS (m, 1) ⊆ BS ′ (m, k). In conclusion,
αm = α.
Proof by induction on the distance, that is, proof by induction on k
of
∀ k ∈ N0 ∀ m ∈ M ∀ m′ ∈ M :

(dS (m, m′ ) = k =⇒ dS ′ (m, m′ ) ≤ α · k).

Base Case. Let k = 0. Furthermore, let m and m′ ∈ M such that
dS (m, m′ ) = k. Then, m = m′ . Hence, dS ′ (m, m′ ) = 0. Therefore,
dS ′ (m, m′ ) ≤ α · k.
Inductive Step. Let k ∈ N0 such that

∀ m ∈ M ∀ m′ ∈ M : (dS (m, m′ ) = k =⇒ dS ′ (m, m′ ) ≤ α · k).

Furthermore, let m and m′′ ∈ M such that dS (m, m′′ ) = k + 1. Then,
there is a {si }i∈{1,2,...,k+1} ⊆ S such that m′ P sk+1 = m′′ , where
m′ = (((m P s1 ) P s2 ) P · · · ) P sk . And, according to Lemma 4.5,
we have dS (m, m′ ) = k. Therefore, according to the inductive hypothesis, dS ′ (m, m′ ) ≤ α · k. Moreover, by definition of αm′ , we have
m′′ = m′ P sk+1 ∈ BS (m′ , 1) ⊆ BS ′ (m′ , αm′ ). Hence, because αm′ = α,
we have dS ′ (m′ , m′′ ) ≤ αm′ = α. In conclusion, because dS ′ is subadditive, dS ′ (m, m′′ ) ≤ dS ′ (m, m′ ) + dS ′ (m′ , m′′ ) ≤ α · k + α = α · (k + 1). 
Corollary 8.4. In the situation of Lemma 8.3, for each element m ∈
M and each non-negative integer k ∈ N0 , we have BS (m, k) ⊆ BS ′ (m, α·
k).
Proof. This is a direct consequence of Lemma 8.3, because for each
element m ∈ M, each non-negative integer k ∈ N0 , and each element

m′ ∈ M, if dS (m, m′ ) ≤ k, then dS ′ (m, m′ ) ≤ α · k.
Corollary 8.5. In the situation of Lemma 8.3, for each non-negative
integer k ∈ N0 , we have γS (k) ≤ γS ′ (α · k).
Proof. This is a direct consequence of Corollary 8.4.



Definition 8.6. Let X be a set, and let d and d′ be metrics on X.
The metrics d and d′ are called Lipschitz equivalent if and only if there
are positive real numbers κ and κ such that κ · d ≤ d′ ≤ κ · d.

24

SIMON WACKER

Corollary 8.7. Let S ′ be a finite and symmetric right generating set
of R. The metrics dS and dS ′ are Lipschitz equivalent.
Proof. Let α = min{k ∈ N0 | BS (1) ⊆ BS ′ (k)} and let α′ = min{k ∈
N0 | BS ′ (1) ⊆ BS (k)}. If α = 0 or α′ = 0, then M = {m0 }, hence
dS = 0 = dS ′ , and therefore dS ≤ dS ′ ≤ dS . Otherwise, according to

Lemma 8.3, we have α1 · dS ′ ≤ dS ≤ α′ · dS ′ .
Corollary 8.8. Let S ′ be a finite and symmetric right generating set
of R. The S-growth function γS of R and the S ′ -growth function γS ′
of R are equivalent.
Proof. According to Corollary 8.5, there is a α ∈ N0 such that, for each
k ∈ N0 , we have γS (k) ≤ γS ′ (α · k). Hence, according to Remark 8.2,
for each k ∈ N0 , we have γS (k) ≤ (α + 1)γS ′ ((α + 1) · k). Therefore,
γS is dominated by γS ′ . Switching roles of S and S ′ yields that γS ′ is

dominated by γS . In conclusion, γS and γS ′ are equivalent.
Corollary 8.9. The S-growth function γS of R is dominated by exp.
Proof. According to Remark 8.2, for each k ∈ N0 , we have γS (k) ≤ r k ,
where r = 1+|S|. Hence, γS 4 [k 7→ r k ]. Moreover, according to Item 4
of Example 7.7, we have [k 7→ r k ] ∼ exp. In conclusion, γS 4 exp. 
Definition 8.10. The equivalence class γ(R) = [γS ]∼ is called growth
type of R.
Lemma 8.11 ([2, Proposition 6.4.6]). Let γ be a growth function such
that γ(0) > 0. Then, γ is equivalent to 1 if and only if γ is bounded.
Corollary 8.12. The set M is finite if and only if the growth types
γ(R) and [1]∼ are equal.
Proof. First, let M be finite. Then, for each k ∈ N0 , we have γS (k) ≤
|M| = |M| · 1(|M| · k).
Secondly, let γ(R) = [1]∼ . Then, according to Lemma 8.11, γS is
S
bounded by some ξ ∈ R>0 . Therefore, because M = k∈N0 BS (k),
(BS (k))k∈N0 is non-decreasing with respect to ⊆, and (γS (k))k∈N0 =
(|BS (k)|)k∈N0 , we have |M| ≤ supk∈N0 γS (k) ≤ ξ. In conclusion, M is
finite.


RIGHT AMENABILITY AND GROWTH

25

Lemma 8.13. Either the sequence (BS (k))k∈N0 is strictly increasing
with respect to ⊆ or eventually constant, that is to say, that there is
a non-negative integer k ∈ N0 such that, for each non-negative integer
k ′ ∈ N0 with k ′ ≥ k, we have BS (k ′ ) = BS (k).
Proof. According to Remark 5.6, the sequence (BS (k))k∈N0 is non-decreasing
with respect to ⊆. If it is strictly increasing with respect to ⊆, it
is not eventually constant. Otherwise, there is a k ∈ N0 such that
BS (k) = BS (k + 1). We proof by induction on k ′ that, for each k ′ ∈ N0
with k ′ ≥ k, we have BS (k ′ ) = BS (k).

Base Case. Let k ′ = k. Then, BS (k ′ ) = BS (k).

Inductive Step. Let k ′ ∈ N0 with k ′ ≥ k such that BS (k ′ ) = BS (k).
Furthermore, let m ∈ BS (k ′ + 1).
Case 1: m ∈ BS (k ′ ). Then, according to the inductive hypothesis, m ∈ BS (k).
Case 2: m ∈
/ BS (k ′ ). Then, there is a {si }i∈{1,2,...,k′+1} ⊆ S such
that m′ P sk′ +1 = m, where m′ = (((m0 P s1 ) P s2 ) P · · · ) P
sk′ . Hence, m′ ∈ BS (k ′ ) and thus, according to the inductive
hypothesis, m′ ∈ BS (k). Therefore, according to Lemma 5.8,
we have m ∈ BS (k + 1). Thus, because BS (k + 1) = BS (k), we
have m ∈ BS (k).

In either case, m ∈ BS (k). Therefore, BS (k ′ + 1) ⊆ BS (k) ⊆ BS (k ′ ) ⊆
BS (k ′ + 1). In conclusion, BS (k ′ + 1) = BS (k).
In conclusion, (BS (k))k∈N0 is eventually constant.


Corollary 8.14. The set M is infinite if and only if the sequence
(BS (k))k∈N0 is strictly increasing with respect to ⊆.
Proof. First, let M be infinite. Suppose that (BS (k))k∈N0 is eventually
constant. Then, there is a k ∈ N0 such that, for each k ′ ∈ N0 with
k ′ ≥ k, we have BS (k ′ ) = BS (k). Hence, according to Remark 5.6, we
S
have M = k′ ∈N0 ,k′≥k BS (k ′ ) = BS (k) and therefore, according to Remark 5.7, the set M is finite, which contradicts the precondition that
M is infinite. Thus, (BS (k))k∈N0 is not eventually constant. In conclusion, according to Lemma 8.13, the sequence (BS (k))k∈N0 is strictly
increasing with respect to ⊆.

26

SIMON WACKER

Secondly, let (BS (k))k∈N0 be strictly increasing with respect to ⊆.
S
Then, because M = k∈N0 BS (k), the set M is infinite.


Corollary 8.15. The set M is infinite if and only if
(1)

∀ ρ ∈ N0 : SS (ρ) 6= ∅.

Proof. We have SS (0) = {m0 } =
6 ∅. And, according to Remark 5.2, for
each ρ ∈ N+ , we have SS (ρ) = BS (ρ) r BS (ρ − 1). Hence, (BS (k))k∈N0
is strictly increasing with respect to ⊆ if and only if Eq. (1) holds.
Therefore, according to Corollary 8.14, the set M is infinite if and only
if Eq. (1) holds.

Lemma 8.16. The set M is infinite if and only if the growth type of
R dominates [k 7→ k]∼ .

Proof. First, let M be infinite. Then, according to Corollary 8.14, the
sequence (BS (k))k∈N0 is strictly increasing with respect to ⊆. Hence,
because BS (0) = {m0 }, for each k ∈ N0 , we have γS (k) = |BS (k)| ≥
k + 1. In conclusion, γS dominates [k 7→ k] and hence γ(R) dominates
[k 7→ k]∼ .
Secondly, let M be finite. Then, according to Corollary 8.12, we
have R = [1]∼ . Hence, according to Item 1 of Example 7.7, the cell
space R does not dominate [k 7→ k]∼ .

Definition 8.17. The cell space R is said to have

(1) exponential growth if and only if its growth type γ(R) is equal
to [exp]∼ ;
(2) sub-exponential growth if and only if it does not have exponential growth;
(3) polynomial growth if and only if there is a non-negative integer
d ∈ N0 such that γS is dominated by [k 7→ k d ].
(4) intermediate growth if and only if it has sub-exponential growth
but not polynomial growth.

Lemma 8.18. Let R have polynomial growth. The cell space R has
sub-exponential growth.
Proof. There is a d ∈ N0 such that [k 7→ k d ] < γS . Hence, according to
Lemma 7.8, γS ≁ exp. In conclusion, γ(R) 6= [exp]∼ .


RIGHT AMENABILITY AND GROWTH

27

9. Growth Rates
In this section, let R = ((M, G, ⊲), (m0 , {gm0 ,m }m∈M )) be a cell space
such that there is a finite and symmetric right generating set S of R.
In Definition 9.2 we define the S-growth rate of R. And in Lemma 9.3
show how that growth rate and exponential growth relate to each other.
p
p
Lemma 9.1. The sequence ( k γS (k))k∈N0 converges to inf k∈N0 k γS (k) ∈
R≥1 .
Proof. According to Corollary 5.15,
γS (k + k ′ ) = |BS (k + k ′ )|

= |BS (k) P BS (k ′ )|

≤ |BS (k)| · |BS (k ′ )|

= γS (k) · γS (k ′ ).

p
Hence, according to [2, Lemma 6.5.1], the sequence ( k γS (k))k∈N0 conp
verges to inf k∈N0 k γS (k). Moreover, because, for each k ∈ N0 , we have
γS (k) ≥ 1, that limit point must be in R≥1 .

p
Definition 9.2. The limit point λS = limk→∞ k γS (k) is called Sgrowth rate of R.
Lemma 9.3. The S-growth rate λS of R is greater than 1 if and only
if the cell space R has exponential growth.
Proof. First, let λS > 1. According to Lemma 9.1, for each k ∈ N0 , we
p
have k γS (k) ≥ λS and hence γS (k) ≥ λkS . Therefore, γS dominates
(_)
(_)
λS and, because λS > 1, the growth function λS is equivalent to exp,
and thus γS dominates exp. Moreover, according to Corollary 8.9, the
growth function γS is dominated by exp. Altogether, γS is equivalent
to exp. In conclusion, γ(R) = [γS ]∼ = [exp]∼ .
Secondly, let γ(R) = [exp]∼ . Then, γS and exp are equivalent. In
particular, γS dominates exp. Hence, there is a α ∈ N+ such that, for
each k ∈ N+ , we have αγS (αk) ≥ exp(k). Therefore, for each k ∈ N+ ,
p
p
√ αk
αk
α γS (αk) = αk αγS (αk)
p
≥ αk exp(k)

28

SIMON WACKER

=

√
α

e.

p
√
Thus, because ( αk α)k∈N+ converges to 1 and ( αk γS (αk))k∈N+ , as subp
√
sequence of ( k γS (k))k∈N0 , converges to λS , we conclude λS ≥ α e >
1.

Corollary 9.4. The S-growth rate λS of R is equal to 1 if and only if
the cell space R has sub-exponential growth.
Proof. This is a direct consequence of Lemma 9.3.



Corollary 9.5. Let S ′ be a finite and symmetric right generating set
of R. The S-growth rate λS of R is equal to 1 or greater than 1 if
and only if the S ′ -growth rate λS ′ of R is equal to 1 or greater than 1
respectively.
Proof. This is a direct consequence of Corollary 9.4 and Lemma 9.3. 
10. Amenability, Følner Conditions/Nets, and
Isoperimetric Constants
In this section, let R = ((M, G, ⊲), (m0, {gm0 ,m }m∈M )) be a finitely
right generated cell space such that the stabiliser G0 is finite, and let
S be a finite and symmetric right generating set of R.
In Definition 10.3 we define the S-isoperimetric constant of R, which
measures, broadly speaking, the invariance under P↾M ×S that a finite
subset of M can have, where 0 means maximally and 1 minimally
invariant. In Theorem 10.5 we show that R is right amenable if and
only if a kind of Følner condition holds, which in turn holds if and
only if the S-isoperimetric constant is 0. And in Theorem 10.6 we
characterise right Følner nets using ρ-boundaries.
Remark 10.1. Let g and g′ be two elements of G/G0 , and let A, B,
and C be three sets. Then,
(_ P g)−1 (A r B) = (_ P g)−1 (A) r (_ P g)−1 (B)
and
(_ P g) P g′

−1


(A) = (_ P g)−1 (_ P g′ )−1 (A) .

RIGHT AMENABILITY AND GROWTH

29

Remark 10.2. Let A, B, and C be three finite sets. Then,
|A r B| ≤ |A r C| + |C r B|.
Definition 10.3. Let E be a subset of G/G0 and let F be the set
{F ⊆ M | F is non-empty and finite}. The non-negative real number
S
| e∈E F r (_ P e)−1 (F )|
ιE (R) = inf
F ∈F
|F |
is called E-isoperimetric constant of R.
Lemma 10.4. Let A be a subset of M, let g and g′ be two elements of
G/G0 , and identify M with G/G0 by [m 7→ Gm0 ,m ]. Then,
[
−1

(_ P g)−1 (A)r _ P (g P g′ ) (A) ⊆
(_ P g)−1 Ar(_ P g0 ·g′ )−1 (A) .
g0 ∈G0

Proof. Let m ∈ (_ P g)−1 (A) r (_ P (g P g′ ))−1 (A). Then, according to
Lemma 5.13, there is a g0 ∈ G0 such that (mPg)Pg0 ·g′ = mP(gPg′ ) ∈
/ A.
′
−1
−1
Therefore, m ∈
/ ((_ P g) P g0 · g ) (A) and hence m ∈ (_ P g) (A) r
((_ P g) P g0 · g′ )−1 (A). Moreover, according to Remark 10.1, we have
((_ P g) P g0 · g′ )−1 (A) = (_ P g)−1 ((_ P g0 · g′ )−1 (A)). Thus, according
to Remark 10.1, we have (_ P g)−1 (A) r ((_ P g) P g0 · g′ )−1 (A) =
S
(_ P g)−1 (A r (_ P g0 · g′ )−1 (A)). Hence, m ∈ g0 ∈G0 (_ P g)−1 (A r
(_ P g0 · g′ )−1 (A)).

Theorem 10.5. The following statements are equivalent:

(1) The cell space R is right amenable;
(2) For each positive real number ε ∈ R>0 , there is a non-empty
and finite subset F of M such that
|F r (_ P s)−1 (F )|
(2)
∀s ∈ S :
< ε;
|F |
(3) The isoperimetric constant ιS (R) is 0.
Proof. 1 =⇒ 2. Let R be right amenable. Then, according to [7,
Main Theorem 4], there is a right Følner net in R. Hence, according to
[7, Lemma 9], for each ε ∈ R>0 , there is a non-empty and finite F ⊆ M
such that Eq. (2) holds.
2 =⇒ 1. For each ε ∈ R>0 , let there be a non-empty and finite F ⊆ M
such that Eq. (2) holds. Furthermore, let ε′ ∈ R>0 , let E ⊆ G/G0 be

30

SIMON WACKER

finite, and identify M with G/G0 by [m 7→ Gm0 ,m ]. Then, according to
Lemma 6.7, there is a k ∈ N0 such that
E ⊆ {m ∈ M | ∃{s′i }i∈{1,2,...,k} ⊆ S ′ : (((m0 P s′1 ) P s′2 ) P · · · ) P s′k },
where S ′ = {G0 }∪S. Let ε = ε′ /(|G0 |2 ·k) and let F ⊆ M be non-empty
and finite such that Eq. (2) holds. Furthermore, let e ∈ E. Then, there
is a {s′i }i∈{1,2,...,k} ⊆ S ′ such that (((m0 P s′1 ) P s′2 ) P · · · ) P s′k = e. For
each i ∈ {0, 1, . . . , k}, let mi = (((m0 P s′1 ) P s′2 ) P · · · ) P s′i and let
Fi = (_ P mi )−1 (F ). Note that mk = e and that F0 = F . Then,
according to Remark 10.2,
|F r Fk | = |F0 r Fk |

≤ |F0 r F1 | + |F1 r Fk |

≤ |F0 r F1 | + |F1 r F2 | + |F2 r Fk |
≤ ...
≤

k
X
i=1

|Fi−1 r Fi |.

Let i ∈ {1, 2, . . . , k}. Then, because mi = mi−1 P s′i , we have Fi−1 r
Fi = (_ P mi−1 )−1 (F ) r (_ P (mi−1 P s′i ))−1 (F ). Hence, according to
S
Lemma 10.4, we have Fi−1 r Fi ⊆ g0 ∈G0 (_ P mi−1 )−1 (F r (_ P g0 ·
s′i )−1 (F )). Therefore,
[
(_ P mi−1 )−1 (F r (_ P g0 · s′i )−1 (F ))|
|Fi−1 r Fi | ≤ |
g0 ∈G0

≤

X

g0 ∈G0

|(_ P mi−1 )−1 (F r (_ P g0 · s′i )−1 (F ))|.

Thus, according to [8, Corollary 1],
X
|G0 | · |F r (_ P g0 · s′i )−1 (F )|.
|Fi−1 r Fi | ≤
g0 ∈G0

Hence, because G0 · S ′ ⊆ S ′ , F r (_ P G0 )−1 (F ) = F r F = ∅, and
Eq. (2) holds,
X
|G0 | · ε · |F |
|Fi−1 r Fi | <
g0 ∈G0

= |G0 |2 · ε · |F |

RIGHT AMENABILITY AND GROWTH

= |G0 |2 ·
=

ε′
|F |.
k

31

ε′
· |F |
|G0 |2 · k

Therefore,
k
X
ε′
|F r Fk | ≤
|Fi−1 r Fi | < k |F | = ε′ |F |.
k
i=1

Thus, because Fk = (_ P e)−1 (F ),

|F r (_ P e)−1 (F )|
< ε′ .
|F |

Hence, according to [7, Lemma 3.9], there is a right Følner net in R.
In conclusion, according to [7, Theorem 5.1], the cell space R is right
amenable.
2 =⇒ 3. Let ε′ ∈ R>0 and let ε = ε′ /|S|. Then, there is a non-empty
and finite F ⊆ M such that Eq. (2) holds. Therefore,
S
| s∈S F r (_ P s)−1 (F )| X |F r (_ P s)−1 (F )|
≤
< |S| · ε = ε′ .
|F |
|F |
s∈S

In conclusion, ιS (R) = 0.

3 =⇒ 2. Let ε ∈ R>0 . Then, because ιS (R) = 0, there is a non-empty
and finite F ⊆ M such that
S
| s∈S F r (_ P s)−1 (F )|
< ε.
|F |
S
Hence, for each s ∈ S, because F r (_ P s)−1 (F ) ⊆ s′ ∈S F r (_ P
s′ )−1 (F ),
|F r (_ P s)−1 (F )|
< ε.
|F |
In conclusion, Eq. (2) holds.



Theorem 10.6. Let {Fi }i∈I be a net in {F ⊆ M | F 6= ∅, F finite}
indexed by (I, ≤). It is a right Følner net in R if and only if
(3)

∀ ρ ∈ N0 : lim
i∈I

|∂ρ Fi |
= 0.
|Fi |

32

SIMON WACKER

Proof. First, let {Fi }i∈I be a right Følner net. Furthermore, let ρ be
a non-negative integer. Then, for each index i ∈ I, we have ∂ρ Fi =
∂B(ρ) Fi . And, according to Remark 5.7, the ball B(ρ) is finite. Hence,
according to [8, Theorem 1],
lim
i∈I

|∂B(ρ) Fi |
= 0.
|Fi |

In conclusion, Eq. (3) holds.
Secondly, let Eq. (3) hold. Furthermore, let N be a finite subset of
G/G0 . Then, according to Remark 5.6, there is a non-negative integer
ρ such that N ⊆ B(ρ). Hence, for each index i ∈ I, according to [8,
Item 4 of Lemma 1], we have ∂N Fi ⊆ ∂B(ρ) Fi = ∂ρ Fi . Therefore,
lim
i∈I

|∂N Fi |
= 0.
|Fi |

In conclusion, according to [8, Theorem 1], the net {Fi }i∈I is a right
Følner net.

11. Subexponential Growth and Amenability
In this section, let R = ((M, G, ⊲), (m0, {gm0 ,m }m∈M )) be a finitely
right generated cell space such that the stabiliser G0 is finite.
In Main Theorem 11.1 we show that if R has sub-exponential growth,
then it is right amenable. And in Theorem 11.3 we show that if G has
sub-exponential growth, then so has R.
Lemma 11.1 ([2, Lemma 6.11.1]). Let (rk )k∈N0 be a sequence of positive real numbers. Then,
√
rk+1
lim inf
≤ lim inf k rk .
k→∞
k→∞
rk
Main Theorem 11.1. Let the cell space R have sub-exponential growth.
It is right amenable.
Proof. Let S be a finite and symmetric right generating set of R. According to Lemma 11.1 and Corollary 9.4,
p
γS (k + 1)
1 ≤ lim inf
≤ lim k γS (k) = λS = 1.
k→∞
k→∞
γS (k)
Therefore, lim inf k→∞

γS (k+1)
γS (k)

= 1.

RIGHT AMENABILITY AND GROWTH

33

(k)
< 1 + ε.
Let ε ∈ R>0 . Then, there is a k ∈ N+ such that γSγS(k−1)
Hence, γS (k) − γS (k − 1) < ε · γS (k − 1). Furthermore, let F = BS (k)
and let s ∈ S. Then, according to Lemma 5.8, we have BS (k − 1) ⊆
(_ P s)−1 (F ). Therefore, because BS (k −1) ⊆ F and γS (k −1) ≤ γS (k),

|F r (_ P s)−1 (F )| ≤ |F r BS (k − 1)|

= |F | − |BS (k − 1)|

= γS (k) − γS (k − 1)
< ε · γS (k − 1)

≤ ε · γS (k)
= ε · |F |.

In conclusion, according to Theorem 10.5, the cell space R is right
amenable.

Lemma 11.2. Let the group G be finitely generated. The growth rate
of G dominates the one of R.
Proof. There is a finite and symmetric generating set T of G such that
G0 T ⊆ T . And, according to Lemma 1.4, the set S = {tG0 | t ∈ T } =
{g0 · tG0 | g0 ∈ G0 , t ∈ T } is a finite and symmetric right generating
set of R.
Let k ∈ N0 be a non-negative integer. Furthermore, let m be an element of BR
S (k). Then, there is a non-negative integer j ∈ {0, 1, 2, . . . , k}
and a family {si }i∈{1,2,...,j} of elements in S such that



m = (m0 P s1 ) P s2 P · · · P sj .
And, by the definition of S, there is a family {ti }i∈{1,2,...,j} of elements
in T such that {ti G0 }i∈{1,2,...,j} = {si }i∈{1,2,...,j}. And, because P is a
right semi-action, there is a family {gi,0}i∈{1,2,...,j} of elements in G0
such that
m = (((m0 P s1 ) P s2 ) P · · · ) P sj

= m0 P t1 g2,0 t2 g3,0 t3 · · · gj,0tj G0

= g1,0 t1 g2,0 t2 g3,0 t3 · · · gj,0tj ⊲ m0 ,

34

SIMON WACKER

where g1,0 = gm0 ,m0 . And, because G0 T ⊆ T , the family {gi,0 ti }i∈{1,2,...,j}
G
is one of elements in T . Hence, m ∈ BG
T (j) ⊲ m0 ⊆ BT (k) ⊲ m0 . ThereG
fore, BR
S (k) ⊆ BT (k) ⊲ m0 and thus
G
G
|BR
S (k)| ≤ |BT (k) ⊲ m0 | ≤ |BT (k)|.

Hence, γSR (k) ≤ γTG (k). In conclusion, γTG dominates γSR and thus γ(G)
dominates γ(R).

Theorem 11.3. Let the group G be finitely generated and let it have
sub-exponential growth. The cell space R has sub-exponential growth
and is right amenable.
Proof. According to Lemma 11.2, the cell space R has sub-exponential
growth. Hence, according to Main Theorem 11.1, it is right amenable.

References
[1] Cayley, Arthur (1878). Desiderata and suggestions: No. 2. The Theory of
groups: graphical representation. American Journal of Mathematics 1 (2):
174–176. doi:10.2307/2369306. JSTOR 2369306. In his Collected Mathematical
Papers 10: 403–405.
[2] Ceccherini-Silberstein, Tullio and Coornaert, Michel. Cellular Automata and
Groups. Springer Monographs in Mathematics. Springer-Verlag, 2010.
[3] Efremovich, Vadim Arsenyevich: The geometry of proximity. I. Mat. Sbornik
N. S. 31(73), 189–200 (1952)
[4] Gromov, Mikhail Leonidovich: Infinite groups as geometric objects, Proc. Int.
Congress Math. Warsaw 1983 1 (1984), 385-392
[5] Švarc, Albert S.: A volume invariant of coverings. Dokl. Akad. Nauk SSSR 105,
32–34 (1955)
[6] Wacker, Simon. Cellular Automata on Group Sets and the Uniform CurtisHedlund-Lyndon Theorem. Cellular Automata and Discrete Complex Systems
(2016), pages 185-198. arXiv:1603.07271 [].
[7] Wacker, Simon. Right Amenable Left Group Sets and the Tarski-Følner Theorem. Preprint (2016). arXiv:1603.06460 [].
[8] Wacker, Simon. The Garden of Eden Theorem for Cellular Automata on Group
Sets. Cellular Automata (2016), pages 66-78. arXiv:1603.07272 [].
Simon Wacker, Department of Informatics, Karlsruhe Institute of
Technology, Am Fasanengarten 5, 76131 Karlsruhe, Germany
E-mail address: simon.wacker@kit.edu

