Cellular Automata and Finite Groups
Alonso Castillo-Ramirez and Maximilien Gadouleau
May 3, 2017

arXiv:1610.00532v2 [] 1 May 2017

Abstract
For a finite group G and a finite set A, we study various algebraic aspects of cellular automata
over the configuration space AG . In this situation, the set CA(G; A) of all cellular automata over
AG is a finite monoid whose basic algebraic properties had remained unknown. First, we investigate the structure of the group of units ICA(G; A) of CA(G; A). We obtain a decomposition of
ICA(G; A) into a direct product of wreath products of groups that depends on the numbers α[H]
of periodic configurations for conjugacy classes [H] of subgroups of G. We show how the numbers
α[H] may be computed using the Möbius function of the subgroup lattice of G, and we use this to
improve the lower bound recently found by Gao, Jackson and Seward on the number of aperiodic
configurations of AG . Furthermore, we study generating sets of CA(G; A); in particular, we prove
that CA(G; A) cannot be generated by cellular automata with small memory set, and, when all
subgroups of G are normal, we determine the relative rank of ICA(G; A) on CA(G; A), i.e. the
minimal size of a set V ⊆ CA(G; A) such that CA(G; A) = hICA(G; A) ∪ V i.
Keywords: Cellular automata, Invertible cellular automata, Finite groups, Finite monoids,
Generating sets.

1

Introduction

Cellular automata (CA), introduced by John von Neumann and Stanislaw Ulam as an attempt to
design self-reproducing systems, are models of computation with important applications to computer
science, physics, and theoretical biology. In recent years, the mathematical theory of CA has been
greatly enriched by its connections to group theory and topology (e.g., see [6] and references therein).
The goal of this paper is to embark in the new task of exploring CA from the point of view of finite
group theory and finite semigroup theory.
First of all, we review the broad definition of CA that appears in [6, Sec. 1.4]. Let G be a group
and A a set. Denote by AG the configuration space, i.e. the set of all functions of the form x : G → A.
For each g ∈ G, let Rg : G → G be the right multiplication function, i.e. (h)Rg := hg, for any h ∈ G.
We emphasise that we apply functions on the right, while in [6] functions are applied on the left.
Definition 1. Let G be a group and A a set. A cellular automaton over AG is a transformation
τ : AG → AG such that there is a finite subset S ⊆ G, called a memory set of τ , and a local function
µ : AS → A satisfying
(g)(x)τ = ((Rg ◦ x)|S )µ, ∀x ∈ AG , g ∈ G,
where (Rg ◦ x)|S denotes the restriction to S of the configuration Rg ◦ x : G → A.
Most of the classical literature on CA focuses on the case when G = Zd , for d ≥ 1, and A is a
finite set (e.g. see survey [17]).
A semigroup is a set M equipped with an associative binary operation. If there exists an element
id ∈ M such that id · m = m · id = m, for all m ∈ M , the semigroup M is called a monoid and
id an identity of M . Clearly, the identity of a monoid is always unique. The group of units of M
is the set of all invertible elements of M (i.e. elements a ∈ M such that there is a−1 ∈ M with
a · a−1 = a−1 · a = id).

1

Let CA(G; A) be the set of all cellular automata over AG ; by [6, Corollary 1.4.11], this set equipped
with the composition of functions is a monoid. Although results on monoids of CA have appeared in
the literature before (see [4, 14, 19]), the algebraic structure of CA(G; A) remains basically unknown.
In particular, the study of CA(G; A), when G and A are both finite, has been generally disregarded
(except for the case when G = Zn , which is the study of one-dimensional CA on periodic points). It
is clear that many of the classical questions on CA are trivially answered when G is finite (e.g. the
Garden of Eden theorems become trivial), but, on the other hand, several new questions, typical of
finite semigroup theory, arise in this setting.
In this paper, we study various algebraic properties of CA(G; A) when G and A are both finite.
First, in Section 2, we introduce notation and review some basic results. In Section 3, we study the
group of units ICA(G; A) of CA(G; A), i.e. the group of all invertible (also known as reversible) CA
over AG . We obtain an explicit decomposition of ICA(G; A) into a direct product of wreath products
of groups that depends on the numbers α[H] of periodic configurations for conjugacy classes [H] of
subgroups H of G.
In Section 4, we show how the numbers α[H] may be computed using the Möbius function of the
subgroup lattice of G, and we give some explicit formulae for special cases. Furthermore, we make a
large improvement on the lower bound recently found by Gao, Jackson and Seward [11] on the number
of aperiodic configurations of AG .
Finally, in Section 5, we study generating sets of CA(G; A). A set T of CA is called a generating
set of CA(G; A) if every CA over AG is expressible as a word in the elements of T . We prove that
CA(G; A) cannot be generated by CA with small memory sets: every generating set T of CA(G; A)
must contain a cellular automaton with minimal memory set equal to G itself. This result provides a
striking contrast with CA over infinite groups because, in such cases, the memory set of any cellular
automaton may never be equal to the whole group (as memory sets are finite by definition). Finally,
when G is finite abelian, we find the smallest size of a set V ⊆ CA(G; A) such that ICA(G; A) ∪ V
generates CA(G; A); this number is known in semigroup theory as the relative rank of ICA(G; A) in
CA(G; A), and it turns out to be related with the number of edges of the subgroup lattice of G.
The present paper is an extended version of [5]. In this version, we added preliminary material
in order to make the paper self-contained, we improved the exposition, we generalised several results
(e.g. Corollary 2, Lemma 11, and Theorem 7), and we added the completely new Section 4.

2

Basic Results

For any set X, a transformation of X is a function of the form τ : X → X. Let Tran(X) and Sym(X)
be the sets of all transformations and bijective transformations of X, respectively. Equipped with
the composition of transformations, Tran(X) is known as the full transformation monoid on X, while
Sym(X) is the symmetric group on X. When X is finite and |X| = q, we write Tranq and Symq
instead of Tran(X) and Sym(X), respectively. A finite transformation monoid is simply a submonoid
of Tranq , for some q. This type of monoids has been extensively studied (e.g. see [10] and references
therein), and it should be noted its close relation to finite-state machines.
Recall that the order of a group G is simply the cardinality of G as a set. For the rest of the
paper, let G be a finite group of order n and A a finite set of size q. By Definition 1, it is clear that
CA(G; A) ≤ Tran(AG ) (where we use the symbol “≤” for the submonoid relation). We may always
assume that τ ∈ CA(G; A) has (not necessarily minimal) memory set S = G, so τ is completely
n
determined by its local function µ : AG → A. Hence, |CA(G; A)| = q q .
If n = 1, then CA(G; A) = Tran(A), while, if q ≤ 1, then CA(G; A) is the trivial monoid with one
element; henceforth, we assume n ≥ 2 and q ≥ 2. Without loss of generality, we identify A with the
set {0, 1, . . . , q − 1} and we denote the identity element of G by e.
A group action of G on a set X is a function · : X × G → X such that (x · g) · h = x · gh and
x · e = x for all x ∈ X, g, h ∈ G (where we denote the image of a pair (x, g) by x · g). A group G acts
on the configuration space AG as follows: for each g ∈ G and x ∈ AG , the configuration x · g ∈ AG is
defined by
(h)x · g = (hg −1 )x, ∀h ∈ G.
(1)

2

This indeed defines a group action because:
(i) For all h ∈ G, (h)x · e = (h)x, so x · e = x.
(ii) For all h, g1 , g2 ∈ G,
(h)(x · g1 ) · g2 = (hg2−1 )x · g1 = (hg2−1 g1−1 )x = (h(g1 g2 )−1 )x = (h)x · g1 g2 ,
so (x · g1 ) · g2 = x · g1 g2 .
Note that in equation (1), h has to be multiplied by the inverse of g and not by g itself, as property
(ii) may not hold in the latter case when G is non-abelian.
Definition 2. A transformation τ : AG → AG is G-equivariant if, for all x ∈ AG , g ∈ G,
(x · g)τ = (x)τ · g.
Theorem 1. Let G be a finite group and A a finite set. Then,
CA(G; A) = {τ ∈ Tran(AG ) : τ is G-equivariant}.
Proof. By Curtis-Hedlund Theorem (see [6, Theorem 1.8.1]), a transformation τ ∈ Tran(AG ) is a
cellular automaton if and only if τ is G-equivariant and continuous in the prodiscrete topology of
AG (i.e. the product topology of the discrete topology). However, as both G and A are finite, every
transformation in Tran(AG ) is continuous, and the result follows.
In other words, the previous result means that CA(G; A) is the endomorphism monoid of the G-set
AG . This result allows us to study CA(G; A) form a pure algebraic perspective.
We review a few further basic concepts on group actions (see [9, Ch. 1]). For x ∈ AG , denote by
Gx the stabiliser of x in G:
Gx := {g ∈ G : x · g = x}.
Remark 1. For any subgroup H ≤ G there exists x ∈ AG such that Gx = H; namely, we may define
x : G → A by
(
1 if g ∈ H,
∀g ∈ G.
(g)x :=
0 otherwise,
For any x ∈ AG , denote by xG the G-orbit of x on AG :
xG := {x · g : g ∈ G}.
Let O(G; A) be the set of all G-orbits on AG :
O(G; A) := {xG : x ∈ AG }.
It turns out that O(G; A) forms a partition of AG . The following result is known as the Orbit-Stabiliser
Theorem (see [9, Theorem 1.4A.]).
Theorem 2. Let G be a finite group and A a finite set. For any x ∈ AG ,
|xG| =

|G|
.
|Gx |

Moreover, if x = y · g for some x, y ∈ AG , g ∈ G, then Gx = g−1 Gy g.
In general, when X is a set and P is a partition of X, we say that a transformation monoid
M ≤ Tran(X) preserves the partition if, for any P ∈ P and τ ∈ M there is Q ∈ P such that
(P )τ ⊆ Q.

3

Lemma 1. For any x ∈ AG and τ ∈ CA(G; A),
(xG)τ = (x)τ G.
In particular, CA(G; A) preserves the partition O(G; A) of AG .
Proof. The result follows by the G-equivariance of τ ∈ CA(G; A).
A configuration x ∈ AG is called constant if (g)x = k ∈ A, for all g ∈ G. In such case, we usually
denote x by k ∈ AG .
Lemma 2. Let τ ∈ CA(G; A) and let k ∈ AG be a constant configuration. Then, (k)τ ∈ AG is a
constant configuration.
Proof. Observe that x ∈ AG is constant if and only if x · g = x, for all g ∈ G. By G-equivariance,
(k)τ = (k · g)τ = (k)τ · g,

∀g ∈ G.

Hence, (k)τ is constant.
A subshift of AG is a subset X ⊆ AG that is G-invariant, i.e. for all x ∈ X, g ∈ G, we have
x · g ∈ X, and closed in the prodiscrete topology of AG . As G and A are finite, the subshifts of AG
are simply unions of G-orbits in AG .
The actions of G on two sets X and Y are equivalent if there is a bijection λ : X → Y such that,
for all x ∈ X, g ∈ G, we have (x · g)λ = (x)λ · g.
Two subgroups H1 and H2 of G are conjugate in G if there exists g ∈ G such that g −1 H1 g = H2 .
This defines an equivalence relation on the subgroups of G. Denote by [H] the conjugacy class of
H ≤ G. If y and z are two configurations in the same G-orbit, then by Theorem 2 we have [Gy ] = [Gz ].
We use the cyclic notation for the permutations of Sym(AG ). If B ⊆ AG and a ∈ AG , we define
the idempotent transformation (B → a) ∈ Tran(AG ) by
(
a if x ∈ B,
∀x ∈ AG .
(x)(B → a) :=
x otherwise,
When B = {b} is a singleton, we write (b → a) instead of ({b} → a).

3

The Structure of ICA(G; A)

Denote by ICA(G; A) the group of all invertible cellular automata:
ICA(G; A) := {τ ∈ CA(G; A) : ∃τ −1 ∈ CA(G; A) such that τ τ −1 = τ −1 τ = id}.
As the inverse of a bijective G-equivariant map is also G-equivariant, it follows by Theorem 1 that
ICA(G; A) = CA(G; A) ∩ Sym(AG ).
The following is an essential result for our description of the structure of the group of invertible
cellular automata.
Lemma 3. Let G be a finite group of order n ≥ 2 and A a finite set of size q ≥ 2. Let x, y ∈ AG be
such that xG 6= yG. Then, there exists τ ∈ ICA(G; A) such that (x)τ = y if and only if Gx = Gy .
Proof. Suppose first that there is τ ∈ ICA(G; A) such that (x)τ = y. Let g ∈ Gx . Then, y · g =
(x)τ · g = (x · g)τ = (x)τ = y, so g ∈ Gy . This shows that Gx ≤ Gy . Now, let h ∈ Gy . Then,
x · h = (y)τ −1 · h = (y · h)τ −1 = (y)τ −1 = x, where τ −1 ∈ ICA(G; A) is the inverse of τ , so h ∈ Gx .
Therefore, Gx = Gy .
Suppose now that Gx = Gy . We define a map τ : AG → AG as follows:


y · g if z = x · g,
∀z ∈ AG .
(z)τ := x · g if z = y · g,


z
otherwise,
4

We check that τ is well-defined:
x · g = x · h ⇔ gh−1 ∈ Gx = Gy ⇔ y · g = y · h;
therefore, every element of AG has a unique image under τ . Clearly, τ is G-equivariant and invertible
(in fact, τ = τ −1 ). Hence τ ∈ ICA(G; A), and it satisfies (x)τ = y.
Corollary 1. Under the assumptions of Lemma 1, there exists τ ∈ ICA(G; A) such that (xG)τ = yG
if and only if [Gx ] = [Gy ]
Proof. Suppose that (xG)τ = yG. Then, (x)τ = y · g, for some g ∈ G. By Lemma 1, Gx = Gy·g .
However, note that Gy·g = g−1 Gy g, so [Gx ] = [Gy ]. Conversely, if [Gx ] = [Gy ], then Gx = g−1 Gy g =
Gy·g , for some g ∈ G. By Lemma 1, there exists τ ∈ ICA(G; A) such that (x)τ = y · g, and by Lemma
1, (xG)τ = yG.
A subgroup H ≤ G is normal if [H] = {H} (i.e. g−1 Hg = H for all g ∈ G).
Corollary 2. Suppose that G is a finite group whose subgroups are all normal. For any x, y ∈ AG ,
there exists τ ∈ ICA(G; A) such that (xG)τ = yG if and only if Gx = Gy .
Groups whose subgroups are all normal are called Dedekind groups. Clearly, abelian groups are
always Dedekind. The finite non-abelian Dedekind groups (also known as finite Hamiltonian groups)
were classified by Richard Dedekind in [8] and have the form Q8 ×(Z2 )n ×H, where Q8 is the quaternion
group (i.e. the group of units of the quaternions H), n ≥ 0, and H is a finite abelian group of odd
order. Several of our stronger results on CA(G; A) will hold when G is a finite Dedekind group.
For any integer α ≥ 2 and any group C, the wreath product of C by Symα is the set
C ≀ Symα := {(v; φ) : v ∈ C α , φ ∈ Symα }
equipped with the operation
(v; φ) · (w; ψ) = (vwφ ; φψ), for any v, w ∈ C α , φ, ψ ∈ Symα ,
where φ acts on w by permuting its coordinates:
wφ = (w1 , w2 , . . . , wα )φ := (w(1)φ , w(2)φ , . . . , w(α)φ ).
In fact, as may be seen from the above definitions, C ≀Symα is equal to the external semidirect product
C α ⋊ϕ Symα , where ϕ : Symα → Aut(C α ) is given by (w)(φ)ϕ := wφ , for all w ∈ C α , φ ∈ Symα . For
a more detailed description of the wreath product of groups, see [9, Sec. 2.6].
T
Let O ∈ O(G; A) be a G-orbit. If G(O) is the pointwise stabiliser of O, i.e. G(O) := x∈O Gx , the
group GO := G/G(O) is isomorphic to a subgroup of Sym(O) (as the homomorphism ρ : G → Sym(O)
given by (x)(g)ρ = x · g, for all x ∈ O, g ∈ G, has kernel G(O) ; see [9, p. 17] for more details). Abusing
the notation, we also write GO for the isomorphic copy of GO inside Sym(O). Define the group
ICA(O) := {τ ∈ Sym(O) : τ is G-equivariant}.

(2)

Note that ICA(O) is isomorphic to the centraliser of GO in Sym(O):
ICA(O) ∼
= CSym(O) (GO ).
Let H be a subgroup of G and [H] its conjugacy class. Define
B[H] (G; A) := {x ∈ AG : [Gx ] = [H]}.
Note that B[H] (G; A) is a subshift of AG (i.e. a union of G-orbits) and, by Theorem 2, all the G-orbits
contained in B[H] (G; A) have equal sizes. Define

α[H] (G; A) := O ∈ O(G, A) : O ⊆ B[H] (G; A) .
If r is the number of different conjugacy classes of subgroups of G, observe that
B := {B[H] (G; A) : H ≤ G}
is a partition of AG into r blocks. When G and A are clear from the context, we write simply B[H]
and α[H] instead of B[H] (G; A) and α[H] (G; A), respectively.
5

Remark 2. For any G and A, we have B[G] (G; A) = {x ∈ AG : x is constant} and α[G] (G; A) = |A|.
Example 1. Let G ∼
= Zn = {0, 1, . . . , n − 1} be a cyclic group of order n ≥ 2 and let A be a finite
set of size q ≥ 2. Any configuration x : Zn → A may be represented by a n-tuple (x1 , x2 , . . . , xn ) such
that xi := (i − 1)x. The action of Zn on AG correspond to cyclic shifts of the n-tuples; for example,
(x1 , x2 , . . . , xn ) · 1 = (xn , x1 , x2 , . . . , xn−1 ).
As Zn has a unique subgroup Zd for each d | n, we have
n
no
α[Zd ] (Zn ; A) = O ∈ O(Zn , A) : |O| =
.
d

This number may be determined by “counting necklaces”, and we shall discuss how to do this in the
next section (see Lemma 7).
Example 2. Let G = Z2 × Z2 be the Klein four-group and A = {0, 1}. As G is abelian, [H] = {H},
for all H ≤ G. The subgroups of G are
H1 = G, H2 = h(1, 0)i, H3 = h(0, 1)i, H4 = h(1, 1)i, and H5 = h(0, 0)i,
where h(a, b)i denotes the subgroup generated by (a, b) ∈ G. Any configuration x : G → A may be
written as a 2 × 2 matrix (xi,j ) where xi,j := (i − 1, j − 1)x, i, j ∈ {1, 2}. The G-orbits on AG are





 

0
0
1
1
1
0
0
1
O1 :=
, O2 :=
, O3 :=
,
,
0
0
1
1
1
0
0
1

 


 

0
1
1
0
0
0
1
1
,
, O5 :=
,
O4 :=
1
0
0
1
1
1
0
0

 
 
 

1
0
0
1
0
0
0
0
O6 :=
,
,
,
,
0
0
0
0
0
1
1
0

 
 
 

0
1
1
0
1
1
1
1
O7 :=
,
,
,
.
1
1
1
1
1
0
0
1
Hence,
B[H1 ] := O1 ∪ O2 , B[H2 ] := O3 , B[H3 ] := O4 , B[H4 ] := O5 , B[H5 ] := O6 ∪ O7 ;
α[Hi ] (G; A) = 2, for i ∈ {1, 5}, and α[Hi ] (G; A) = 1, for i ∈ {2, 3, 4}.
For any H ≤ G, let NG (H) := {g ∈ G : H = g −1 Hg} ≤ G be the normaliser of H in G. Note that
H is always normal in NG (H). The following result determines the structure of the group ICA(G; A),
and it is a refinement of [4, Lemma 4] (c.f. [19, Theorem 9] and [7, Theorem 7.2]).
Theorem 3 (Structure of ICA(G; A)). Let G be a finite group and A a finite set of size q ≥ 2. Let
[H1 ], . . . , [Hr ] be the list of all different conjugacy classes of subgroups of G. Then,
ICA(G; A) ∼
=

r
Y
i=1


(NG (Hi )/Hi ) ≀ Symαi ,

where αi := α[Hi ] (G; A).
Proof. Let Bi := B[Hi ] , and note that all these subshifts are nonempty because of Remark 1. By
Corollary 1, any τ ∈ ICA(G; A) maps configurations inside Bi to configurations inside Bi ; hence,
ICA(G; A) is contained in the group
r
Y

Sym(Bi ) = Sym(B1 ) × Sym(B2 ) × · · · × Sym(Br ).

i=1

6

For each 1 ≤ i ≤ r, fix a G-orbit Oi ⊆ Bi , and let Oi be the set of G-orbits contained in Bi (so
Oi ∈ Oi ). Note that Oi is a uniform partition of Bi (i.e. all the blocks in the partition have the same
size). For any τ ∈ ICA(G; A), Lemma 1 implies that the projection of τ to Sym(Bi ) is contained in
the group that preserves this uniform partition, i.e. the projection of τ is contained in
S(Bi , Oi ) := {φ ∈ Sym(Bi ) : ∀P ∈ Oi , (P )φ ∈ Oi }.
By [2, Lemma 2.1(iv)],

S(Bi , Oi ) ∼
= Sym(Oi ) ≀ Symαi .

It is well-known that Symαi is generated by its transpositions. As the invertible cellular automaton
constructed in the proof of Lemma 3 induces a transposition (xG, yG) ∈ Symαi , with xG, yG ∈ Oi ,
we deduce that Symαi ≤ ICA(G; A). Now it is clear that the projection of ICA(G; A) to Sym(Bi ) is
exactly ICA(Oi ) ≀ Symαi . By [9, Theorem 4.2A (i)], it follows that
CSym(Oi ) (GOi ) ∼
= NG (Hi )/Hi .
The result follows because ICA(Oi ) ∼
= CSym(Oi ) (GOi ).
Corollary 3. Let G be a finite Dedekind group and A a finite set of size q ≥ 2. Let H1 , . . . , Hr be the
list of different subgroups of G. Then,
ICA(G; A) ∼
=

r
Y
i=1


(G/Hi ) ≀ Symαi ,

where αi := α[Hi ] (G; A).
Proof. As every subgroup of G is normal, the results follows because [Hi ] = {Hi } and NG (Hi ) = G,
for all 1 ≤ i ≤ r.
Example 3. For any n ≥ 2,
ICA(Zn ; A) ∼
=

r
Y
i=1


Zdi ≀ Symαi ,

where d1 , d2 , . . . , dr are the divisors of n, and αi := αZn/di (Zn ; A).
Example 4. Let G = Z2 × Z2 and A = {0, 1}. By Example 2,

ICA(G; A) ∼
= (Z2 )4 × (G ≀ Sym2 ).

4

Aperiodic Configurations

In this section, we shall determine the integers α[H] (G; A), for each H ≤ G, as they play an important
role in the decomposition of ICA(G; A) given by Theorem 3.
The following elementary result links the integers α[H] (G; A) with the sizes of the subshifts B[H] (G; A).
Lemma 4. Let G be a finite group of order n ≥ 2 and A a finite set of size q ≥ 2. Let H be a subgroup
of G of order m. Then,
α[H] · n = m · |B[H] |.
Proof. The set of G-orbits contained in B[H] forms a partition of B[H] into α[H] blocks. The result
n
by Theorem 2.
follows as each one of these G-orbits has size m
Denote by [G : H] the index of H in G (i.e. the number of cosets of H in G). It is well-known that
|G|
. The following result characterises the situations when BH contains a
when G is finite, [G : H] = |H|
unique G-orbit and will be useful in Section 5.2.
Lemma 5. Let G be a finite group and A a finite set of size q ≥ 2. Then, α[H] (G; A) = 1 if and only
if [G : H] = 2 and q = 2.
7

Proof. Suppose first that [G : H] = q = 2. The subgroup H is normal because it has index 2, so
Hg = gH for every g ∈ G. Fix s ∈ G \ H, and define x ∈ AG by
(
0 if g ∈ H
(g)x =
1 if g ∈ sH = Hs.
Clearly, Gx = H and x ∈ B[H] . Let y ∈ B[H] . As H is normal, [H] = {H}, so Gy = H. For any
h ∈ H,
(h)y = (e)y · h−1 = (e)y and (sh)y = (s)y · h−1 = (s)y,
so y is constant on the cosets of H. Therefore, either y = x, or
(
1 if g ∈ H
(g)y =
0 if g ∈ sH = Hs.
In the latter case, y · s = x and y ∈ xG. This shows that there is a unique G-orbit contained in B[H] ,
so α[H] (G; A) = 1.
Conversely, suppose that [G : H] 6= 2 or q ≥ 3. If [G : H] = 1, then G = H and α[H] (G; A) = q ≥ 2.
Now we prove the two cases separately.
Case 1: [G : H] ≥ 3. Define configurations x1 , x2 ∈ AG by
(
1 if g ∈ H,
(g)x1 =
0 otherwise.
(
0 if g ∈ H,
(g)x2 =
1 otherwise.
It is clear that x1 , x2 ∈ B[H] because Gx1 = Gx2 = H. Furthermore, x1 and x2 are not in the
same G-orbit because the number of preimages of 1 under x1 and x2 is different (as [G : H] ≥ 3).
Hence, α[H] (G; A) ≥ 2.
Case 2: q ≥ 3. Define a configuration x3 ∈ B[H] by
(
2
(g)x3 =
0

if g ∈ H,
otherwise,

and consider the configuration x1 ∈ B[H] defined in Case 1. Clearly, x1 and x3 are not in the
same G-orbit because 2 ∈ A is not in the image of x1 . Hence, α[H] (G; A) ≥ 2.

For any H ≤ G, consider the set of H-periodic configurations:
Fix(H) := {x ∈ AG : x · h = x, ∀h ∈ H} = {x ∈ AG : H ≤ Gx }.
By [6, Corollary 1.3.4.], we have
|Fix(H)| = q [G:H] .
By the Cauchy-Frobenius lemma ([9, Theorem 1.7A]), the total number of G-orbits on AG is
|O(G; A)| =

1 X n/|g|
q
,
|G|
g∈G

where |g| := |hgi| is the order of the element g. However, we need a somewhat more sophisticated
machinery in order to count the number of orbits inside B[H] (G; A).

8

The Möbius function of a finite poset (P, ≤) is a map µ : P × P → Z defined inductively by the
following equations:
µ(a, a) = 1, ∀a ∈ P,
µ(a, b) = 0, ∀a > b,
X

µ(a, c) = 0, ∀a < b.

a≤c≤b

If L(G) is the set of subgroups of G, the poset (L(G), ⊆) is called the subgroup lattice of G. Let
µ : L(G) × L(G) → Z be the Möbius function of the subgroup lattice of G. In particular, µ(H, H) = 1
for any H ≤ G, and µ(H, K) = −1 if H is a maximal subgroup of K ≤ G.
For any H ≤ G of order m, let pH be the smallest order of a subgroup between H and G (note
that pH ≥ 2m):
pH := min{|K| : H < K ≤ G},
and define
SH := {K : H < K ≤ G, |K| = pH }.
By convention, pG = n and SG = ∅.
In the next result we use the following asymptotic notation: write f (n) = o(g(n)), with g(n) not
(n)
identically zero, if limn→0 fg(n)
= 0.
Theorem 4. Let G be a finite group of order n ≥ 2 and A a finite set of size q ≥ 2. Let H be a
subgroup of G of order m.
(i)
|B[H] | = |[H]|

X

µ(H, K) · q n/|K|.

K≤G

(ii) Using asymptotic notation by fixing G and considering q = |A| as a variable, we have
|B[H] |
= q n/m − (|SH | + o(1))q n/pH .
|[H]|
Proof. In order to prove part (i), observe that
|Fix(H)| =

X

H≤K≤G

1
|B |.
|[K]| [K]

By Möbius inversion (see [18, 4.1.2]), we obtain that
X
|B[H] | = |[H]|
µ(H, K) · |Fix(K)|.
K≤G

The result follows as |Fix(K)| = q n/|K| .
Now we prove part (ii). The result is clear for H = G. Otherwise, we have
|B[H] |
=
|[H]|

X

µ(H, K)q n/|K|

H≤K≤G

= q n/m − |SH |q n/pH +

X

µ(H, K)q n/|K|

K ∈S
/ H

=q

n/m

− (|SH | −

X

K ∈S
/ H

The result follows as q n/|K|−n/pH = o(1).
9

µ(H, K)q n/|K|−n/pH )q n/pH .

As the Möbius function of the subgroup lattice of G is not easy to calculate in general, we shall
give a few more explicit results by counting the number of so-called aperiodic configurations:
ac(G; A) := |{x ∈ AG : Gx = {e}}| = |B[{e}] (G; A)|.
Part of our motivation to study this number is that, when H is a normal subgroup of G, the size
of the subshift B[H] is equal to the number of aperiodic configurations with respect to G/H.
Lemma 6. Let G be a finite group, A a finite set, and H a normal subgroup of G. Then,
|B[H] (G; A)| = ac(G/H; A).
Proof. As H is normal, then G/H is a group. By [6, Proposition 1.3.7.], there is a G/H-equivariant
bijection between the configuration space AG/H and Fix(H). Hence, configurations in AG/H with
trivial stabiliser correspond to configurations in Fix(H) with stabiliser H.
The following result gives some formulae for the number of aperiodic configurations of various
finite groups.
Lemma 7. Let G be a finite group of order n ≥ 2 and A a finite set of size q ≥ 2.
(i)
X

ac(G; A) =

µ({e}, K) · q n/|K| .

K≤G

(ii) If G ∼
= Zn is a cyclic group, then
ac(Zn , A) =

X

µ(1, d) · q n/d ,

d|n

where µ is the classic Möbius function of the poset (N, |).
(iii) If G is a p-group and H := {H ≤ G : H is elementary abelian}, then
ac(G; A) =

X

log p |H|
2

(−1)logp |H| p(

) q n/|H| .

H∈H

(iv) If G ∼
= Zm
p is an elementary abelian group, then
ac(Zm
p ; A)
where

m
r p

=q

pm

 
m
X
r pm−r r(r−1)/2 m
(−1) q
p
+
.
r p
r=1

is the Gaussian binomial coefficient:
 
m
(1 − pm )(1 − pm−1 ) . . . (1 − pm−r+1 )
.
:=
(1 − pr )(1 − pr−1 ) . . . (1 − p)
r p

Proof. Part (i) follows by Lemma 4 (iii). Part (ii) follows because the subgroup lattice of the cyclic
group Zn is isomorphic to the lattice of divisors of n.
We prove part (iii). If G is a p-group, by [15, Corollary 3.5.], for any H ≤ G we have
(
logp |H|
(−1)logp |H| p( 2 ) if H is elementary abelian,
µ ({e}, H) =
0
otherwise.
So the result follows by part (i).

10

pr .

Finally, we prove part (iv). Denote by Hr the set of elementary abelian subgroups of G of order
Then,
ac(G; A) =

m
X
r
m r
(−1)r |Hr |p(2) q p /p
r=0

m
X
m−r r(r−1)/2
(−1)r q p
p
|Hr |.
=
r=0

The result follows because the Gaussian binomial coefficient
groups of order pr of Zm
p (see [3, Section 9.2]).

m
r p



gives precisely the number of sub-

As constant configurations are never aperiodic, the following obvious upper bound of ac(G; A) is
obtained:
ac(G; A) ≤ q n − q
This upper bound is achieved if and only if n is a prime number (so G is a cyclic group). The following
lower bound bound of ac(G; A) was obtained by Gao, Jackson and Seward [11, Corollary 1.7.2.]:
q n − q n−1 ≤ ac(G; A),
which is achieved for small values of n and q, as for example, when n = q = 2, or when G = Z2 × Z2
and q = 2 (see Example 2).
For any d | n, define G(d) := {g ∈ G : |hgi| = d}. In the next result we improve the known
estimates of ac(G; A).
Theorem 5 (Lower bound on apperiodic configurations). Let G be a finite group of order n ≥ 2 and
A a finite set of size q ≥ 2. Let p be the smallest prime dividing n. Then:


|G(p) |
(i) ac(G; A) = q n − p−1 + o(1) q n/p .
(ii) We have the following lower bound:
q n − (n − 1)q n/p ≤ ac(G; A).
Proof. By Theorem 4 (ii) with H = {e}, we have
ac(G; A) = q n − (|S{e} | + o(1))q n/p{e} .
In this case, p{e} is the smallest order of a non-identity element in G, which, by Sylow’s theorem, is
equal to p, the smallest prime dividing n. Furthermore, |S{e} |, the number of subgroups of G of order
p, is G(p) /(p − 1), so part (i) follows.
In order to prove part (ii), let t1 , . . . , tr be the generators of the minimal subgroups of G (all of
which are cyclic groups of prime order). Then,
n

ac(G; A) = q −

r
[

n

Fix(hti i) ≥ q −

r
X

q n/|ti | ≥ q n − (n − 1)q n/p .

i=1

i=1

The lower bound of Theorem 5 (ii) is much tighter than the one given by [11, Corollary 1.7.2.].

5

Generating Sets of of CA(G; A)

For a monoid M and a subset T ⊆ M , denote by hT i the submonoid generated by T , i.e. the smallest
submonoid of M containing T . Say that T is a generating set of M if M = hT i; in this case, every
element of M is expressible as a word in the elements of T (we use the convention that the empty
word is the identity).
11

5.1

Memory Sets of Generators of CA(G; A)

A large part of the classical research on CA is focused on CA with small memory sets. In some cases,
such as the elementary Rule 110, or John Conway’s Game of Life, these CA are known to be Turing
complete. In a striking contrast, when G and A are both finite, CA with small memory sets are
insufficient to generate the monoid CA(G; A).
Theorem 6 (Minimal memory set of generators of CA(G; A)). Let G be a finite group of order n ≥ 2
and A a finite set of size q ≥ 2. Let T be a generating set of CA(G; A). Then, there exists τ ∈ T with
minimal memory set S = G.
Proof. Suppose that T is a generating set of CA(G; A) such that each of its elements has minimal
memory set of size at most n−1. Consider the idempotent σ := (0 → 1) ∈ CA(G; A), where 0, 1 ∈ AG
are different constant configurations. Then, σ = τ1 τ2 . . . τℓ , for some τi ∈ T . By the definition of σ
G
G
and Lemma 2, there must be 1 ≤ j ≤ ℓ such that (AG
c )τj = q − 1 and (Anc )τj = Anc , where
G
G
G
AG
c := {k ∈ A : k is constant} and Anc := {x ∈ A : x is non-constant}.

Let S ⊆ G and µ : AS → A be the minimal memory set and local function of τ := τj , respectively.
G
By hypothesis, s := |S| < n. Since the restriction of τ to AG
c is not a bijection, there exists k ∈ Ac
G
(defined by (g)k := k ∈ A, ∀g ∈ G) such that k 6∈ (Ac )τ .
For any x ∈ AG , define the k-weight of x by
|x|k := |{g ∈ G : (g)x 6= k}|.
Consider the sum of the k-weights of all non-constant configurations of AG :
X
X
X
w :=
|x|k =
|x|k −
|x|k
x∈AG
nc

x∈AG

= n(q − 1)q

n−1

x∈AG
c

− n(q − 1) = n(q − 1)(q n−1 − 1).

In particular, w
n is an integer not divisible by q.
For any x ∈ AG and y ∈ AS , define
Sub(y, x) := |{g ∈ G : y = x|Sg }|;
this counts the number of times that y appears as a subconfiguration of x. Then, for any fixed y ∈ AS ,
(
X
nq n−s
if y ∈ ASnc ,
Ny :=
Sub(y, x) =
n(q n−s − 1) if y ∈ ASc .
G
x∈Anc

To see why the previous equality holds, fix g ∈ G and count the number of configurations x ∈ AG
nc such
n−s
n−s
that y = x|Sg : there are q
such configurations if y is non-constant, and q
− 1 if y is constant.
The equality follows by counting this for each one of the n elements of G.
G
Let δ : A2 → {0, 1} be the Kronecker’s delta function. Since (AG
nc )τ = Anc , we have
X
X
w=
|(x)τ |k =
Ny (1 − δ(y)µ,k )
x∈AG
nc

= nq n−s

y∈AS

X

(1 − δ(y)µ,k ) + n(q n−s − 1)

y∈AS
nc

X

(1 − δ(y)µ,k ).

y∈AS
c

S
Because k 6∈ (AG
c )τ , we know that (y)µ 6= k for all y ∈ Ac . Therefore,
X
w
(1 − δ(y)µ,k ) + (q n−s − 1)q.
= q n−s
n
S
y∈Anc

As s < n, this implies that

w
n

is an integer divisible by q, which is a contradiction.
12

5.2

Relative Rank of ICA(G; A) in CA(G; A)

One of the fundamental problems in the study of a finite monoid M is the determination of the
cardinality of a smallest generating subset of M ; this is called the rank of M and denoted by Rank(M ):
Rank(M ) := min{|T | : T ⊆ M and hT i = M }.
It is well-known that, if X is any finite set, the rank of the full transformation monoid Tran(X) is 3,
while the rank of the symmetric group Sym(X) is 2 (see [10, Ch. 3]). Ranks of various finite monoids
have been determined in the literature before (e.g. see [1, 2, 12, 13, 16]).
In [4], the rank of CA(Zn ; A), where Zn is the cyclic group of order n, was studied and determined
when n ∈ {p, 2k , 2k p : k ≥ 1, p odd prime}. Moreover, the following problem was proposed:
Problem 1. For any finite group G and finite set A, determine Rank(CA(G; A)).
For any finite monoid M and U ⊆ M , the relative rank of U in M , denoted by Rank(M : U ), is
the minimum cardinality of a subset V ⊆ M such that hU ∪ V i = M . For example, for any finite set
X,
Rank(Tran(X) : Sym(X)) = 1,
as any τ ∈ Tran(X) with |(X)τ | = |X| − 1 satisfies hSym(X) ∪ {τ }i = Tran(X). One of the main
tools used to determine Rank(CA(G; A)) is based on the following result (see [2, Lemma 3.1]).
Lemma 8. Let M be a finite monoid and let U be its group of units. Then,
Rank(M ) = Rank(M : U ) + Rank(U ).
We shall determine the relative rank of ICA(G; A) in CA(G; A) for any finite abelian group G and
finite set A. In order to achieve this, we prove two lemmas that hold even when G is nonabelian and
have relevance in their own right.
Lemma 9. Let G be a finite group and A a finite set of size q ≥ 2. Let τ ∈ CA(G; A) and x ∈ AG .
If (x)τ ∈ xG, then τ |xG ∈ Sym(xG).
Proof. It is enough to show that (xG)τ = xG as this implies that τ |xG : xG → xG is surjective, so it
is bijective by the finiteness of xG. Since (x)τ ∈ xG, we know that (x)τ G = xG. Hence, by Lemma
1, (xG)τ = (x)τ G = xG.
Remark 3. Recall that a Garden of Eden (GoE) of τ ∈ CA(G; A) is a configuration x ∈ AG such
that x ∈
/ (AG )τ . As AG is finite in our setting, note that τ is non-invertible if and only if it has a
GoE. Moreover, by G-equivariance, x is a GoE of τ if and only if xG is a GoE of τ , so we shall talk
about GoE G-orbits, rather than GoE configurations.
Denote by CG the set of conjugacy classes of subgroups of G. For any [H1 ], [H2 ] ∈ CG , write
[H1 ] ≤ [H2 ] if H1 ≤ g−1 H2 g, for some g ∈ G.
Remark 4. The relation ≤ defined above is a well-defined partial order on CG . Clearly, ≤ is reflexive
and transitive. In order to show antisymmetry, suppose that [H1 ] ≤ [H2 ] and [H2 ] ≤ [H1 ]. Then,
H1 ≤ g−1 H2 g and H2 ≤ f −1 H1 f , for some f, g ∈ G, which implies that |H1 | ≤ |H2 | and |H2 | ≤ |H1 |.
As H1 and H2 are finite, |H1 | = |H2 |, and H1 = g−1 H2 g. This shows that [H1 ] = [H2 ].
Lemma 10. Let G be a finite group and A a finite set of size q ≥ 2. Let x, y ∈ AG be such that
xG 6= yG. There exists a non-invertible τ ∈ CA(G; A) such that (x)τ = y if and only if Gx ≤ Gy .
Proof. In general, for any τ ∈ CA(G; A) such that (x)τ = y, we have Gx ≤ Gy , because we may argue
as in the first line of the proof of Lemma 3.
Conversely, suppose that Gx ≤ Gy . We define an idempotent transformation τx,y : AG → AG as
follows:
(
y · g if z = x · g,
∀z ∈ AG .
(z)τx,y :=
z
otherwise,
Note that τx,y is well-defined because x · g = x · h, implies that gh−1 ∈ Gx ≤ Gy , so y · g = y · h.
Clearly, τx,y is non-invertible and G-equivariant, so τx,y ∈ CA(G; A) \ ICA(G; A).
13

Corollary 4. Let G be a finite group and A a finite set of size q ≥ 2. Let x, y ∈ AG be such
that xG 6= yG. There exists a non-invertible τ ∈ CA(G; A) such that (xG)τ = yG if and only if
[Gx ] ≤ [Gy ].
Consider the directed graph (CG , EG ) with vertex set CG and edge set

2
EG := ([Hi ], [Hj ]) ∈ CG
: [Hi ] ≤ [Hj ] .

When G is abelian, this graph coincides with the subgroup lattice of G.

Remark 5. Lemma 10 may be restated in terms of (CG , EG ). By Lemma 9, loops ([Hi ], [Hi ]) do not
have corresponding non-invertible CA when α[Hi ] (G; A) = 1.
Recall that an action of G on a set X is transitive if for any x, y ∈ X there exists g ∈ G such that
x · g = y (i.e. X = xG, for any x ∈ X). The following result will be useful in order to prove the main
theorem of this section.
Lemma 11. Let G be a finite group and A a finite set of size q ≥ 2. Then ICA(G; A) is transitive on
every G-orbit on AG if and only if G is a finite Dedekind group.
Proof. Let x ∈ AG be a configuration. By Theorem 3, the group ICA(G; A) acts on xG as the group
NG (Gx )/Gx via the action x · (Gx g) := x · g, for any Gx g ∈ NG (Gx )/Gx . Note that NG (Gx )/Gx is
transitive on xG if and only if G = NG (Gx ), which holds if and only if Gx is normal in G. As any
subgroup of G occurs as a stabiliser of a configuration, this shows that ICA(G; A) is transitive on xG,
for all x ∈ AG , if and only if every subgroup of G is normal.
Remark 6. It is obvious, by definition, that G is transitive on a G-orbit xG. However, Lemma 11
establishes a criterion for the transitivity of the group ICA(G; A) on xG.
Theorem 7 (Relative rank of ICA(G; A) on CA(G; A)). Let G be a finite group and A a finite set of
size q ≥ 2. Let I2 (G) be the set of subgroups of G of index 2:
I2 (G) = {H ≤ G : [G : H] = 2}.
Then,
(
|EG | − |I2 (G)|
Rank(CA(G; A) : ICA(G; A)) ≥
|EG |

if q = 2,
otherwise,

with equality if and only if G is a finite Dedekind group.
Proof. Let [H1 ], [H2 ], . . . , [Hr ] be the list of different conjugacy classes subgroups of G with H1 = G.
Suppose further that this is ordered such that
|H1 | ≥ |H2 | ≥ · · · ≥ |Hr |

(3)

For each 1 ≤ i ≤ r, let αi := α[Hi ] (G; A) and Bi := B[Hi ] (G; A). Fix orbits xi G ⊆ Bi such that
Gxi < Gxj whenever [Hi ] < [Hj ]. For every αi ≥ 2, fix orbits yi G ⊆ Bi such that xi G 6= yi G.
Consider the set

V := τxi ,xj : Gxi < Gxj ∪ {τxi ,yi : αi ≥ 2} ,

and τxi ,xj and τxi ,yi are the idempotents that map xi to xj and xi to yi , respectively, as defined in
Lemma 10. Observe that
(
n
X
|EG | − |I2 (G)| if q = 2,
δ(αi , 1) =
|V | = |EG | −
|EG |
otherwise,
i=1
where the last equality follows by Lemma 5.
Claim. The relative rank of ICA(G; A) on CA(G; A) is at least |V |.
14

Proof. Suppose there exists W ⊆ CA(G; A) such that |W | < |V | and
hICA(G; A) ∪ W i = CA(G; A).
Let τ ∈ CA(G; A). We say that τ is a Unique-Garden-of-Eden CA (UCA) of type (Bi , Bj ) if the
following holds:
(⋆) τ has a unique Garden of Eden G-orbit Oi (i.e. (AG )τ = AG \ Oi ), and it satisfies Oi ⊆ Bi and
(Oi )τ ⊆ Bj .
Note that UCA of type (Bi , Bi ) only exist when there are at least two different orbits in Bi , i.e. αi ≥ 2.
For example, the idempotents τxi ,yi ∈ V , with αi ≥ 2, are UCA of type (Bi , Bi ), while the
idempotents τxi ,xj , with Gxi < Gxj , are UCA of type (Bi , Bj ) with Oi = xi G. Note that τ ∈ CA(G; A)
is a UCA of type (Bi , Bj ) if and only if hICA(G; A), τ i contains a UCA of type (Bi , Bj ) if and only
if all non-invertible elements of hICA(G; A), τ i are UCA of type (Bi , Bj ) (because any φ ∈ ICA(G; A)
always satisfies φ(Bk ) = Bk for all k, by Corollary 1).
As |W | < |V |, and V has exactly one UCA of each possible type (see Lemma 10), there must be
τ ∈ V such that there is no UCA in W of the same type as τ . Without loss of generality, suppose
that the type of τ is (Bi , Bj ) (possibly with i = j). We finish the proof of the claim by showing that
there is no UCA of type (Bi , Bj ) in hW i. This would imply that there is no UCA of type (Bi , Bj ) in
hICA(G; A) ∪ W i, contradicting that hICA(G; A) ∪ W i = CA(G; A).
Assume that
ω := ω1 . . . ωs . . . ωℓ ∈ hW i, with ωm ∈ W, ∀m = 1, . . . , ℓ,
(4)
is a UCA of type (Bi , Bj ). First note that, as ω has no GoE in Bk , for all k 6= i, then (Bk )ω = Bk .
Hence,
(Bk )ωm = Bk for all k 6= i and m = 1 . . . ℓ,
(5)
because ωm cannot map any G-orbit of Bk to a different subshift Bc , as there is no CA mapping back
Bc to Bk (see Lemmas 10 and 3), and ωm does not have GoE inside Bk because this would be a GoE
for ω inside Bk .
Now, observe that each non-invertible ωm that appears in (4) has a unique GoE orbit Ωm (inside
Bi because of (5)). This is true because if Ωm consists of more than one orbit, then (AG )ωm = AG \Ωm
implies that the size of (AG )ω is strictly smaller than |AG | − |Oi |, where Oi ⊆ Bi is the unique GoE
G-orbit of ω.
Let ωs the the first non-invertible CA that appears in (4). We finish the proof by showing that
−1
. . . ω1−1 . There are three possibilities:
(Ωs )ωs ⊆ Bj . Let Ω′s = (Ωs )ωs−1
Case 1: (Ωs )ωs = Pc ⊆ Bc for c 6= i, j. Then:
(Ω′s )ω = (Ωs )ωs . . . ωℓ = (Pc )ωs+1 . . . ωℓ ⊆ Bc ,
where the last contention is because of (5). However, as ω maps all orbits of Bi to Bi ∪ Bj , this
case is impossible.
Case 2: (Ωs )ωs ⊆ Bi . If i = j, then ωs is a UCA of the same type as ω. Hence, let i 6= j. By the
uniqueness of Ωs , (Bi \ Ωs )ωs = (Bi \ Ωs ), so there exists a G-orbit Q ⊆ Bi , Q 6= Ωs , such that
−1
(Ωs )ωs = (Q)ωs . Let Q′ = (Q)ωs−1
. . . ω1−1 . Then,
(Ω′s )ω = (Ωs )ωs . . . Ωℓ = (Q)ωs . . . ωℓ = (Q′ )ω.
However, as ω maps its only GoE orbit to Bj , it does not collapse orbits in Bi . So this case,
with i 6= j is impossible.
Case 3: (Ωs )ωs ⊆ Bj . In this case, ωs is a UCA of type (Bi , Bj ).
In any case, we obtain a contradiction with the assumption that W has no UCA of type (Bi , Bj ).
Therefore, hW i has no UCA of type (Bi , Bj ).
15

Claim. If G is a Dedekind group, then Rank(CA(G; A) : ICA(G; A)) = |V |.
Proof. We will show that
CA(G; A) = M := hICA(G; A) ∪ V i .
For any σ ∈ CA(G; A), consider σi ∈ CA(G; A), 1 ≤ i ≤ r, defined by
(
(x)σ if x ∈ Bi
(x)σi =
x
otherwise.
By Lemmas 3 and 10, we know that Gx ≤ G(x)σ , for all x ∈ AG , so (Bi )σ ⊆
the order given by (3)). Hence, we have the decomposition

S

j≤i Bj

for all i (recall

σ = σ1 ◦ σ2 ◦ · · · ◦ σr .
We shall prove that σi ∈ M for all 1 ≤ i ≤ r. For each σi , decompose Bi = Bi′ ∪ Bi′′ , where
[
Bi′ :=
{P ∈ O(G; A) : P ⊆ Bi and (P )σi ⊆ Bj for some j < i} ,
[
Bi′′ :=
{P ∈ O(G; A) : P ⊆ Bi and (P )σi ⊆ Bi } .

If σi′ and σi′′ are the CA that act as σi on Bi′ and Bi′′ , respectively, and fix everything else, then
σi = σi′ ◦ σi′′ . We shall prove that σi′ ∈ M and σi′′ ∈ M .
1. We show that σi′ ∈ M . For any orbit P ⊆ Bi′ , the orbit Q := (P )σi′ is contained in Bj for some
j < i. By Theorem 3, there exists an involution

 
φ ∈ (NG (Gxi )/Gxi ) ≀ Symαi × (NG (Gxj )/Gxj ) ≀ Symαj ≤ ICA(G; A)
that induces the double transposition (xi G, P )(xj G, Q). By Lemma 11, ICA(G; A) is transitive
on xi G and xj G (as G is Dedekind), so we may take φ such that (xi )φσi′ = (xj )φ. Then,
(z)σi′ = (z)φτxi ,xj φ, ∀z ∈ P = (xi G)φ.
As σi′ may be decomposed as a product of CA that only move one orbit in Bi′ , this shows that
σi′ ∈ M .
2. We show that σi′′ ∈ M . In this case, σi′′ ∈ Tran(Bi ). In fact, as σi′′ preserves the partition of Bi
into G-orbits, Lemma 9 and [2, Lemma 2.1 (i)] imply that σi′′ ∈ (G/Gxi ) ≀ Tranαi . If αi ≥ 2, the
monoid Tranαi is generated by Symαi ≤ ICA(G; A) together with the idempotent τxi ,yi . Hence,
σi′′ ∈ M .
Therefore, we have established that CA(G; A) = hICA(G; A) ∪ V i.
Claim. If G is not a Dedekind group, then Rank(CA(G; A) : ICA(G; A)) > |V |.
Proof. As G is not Dedekind, so there is a subgroup H ≤ G which is not normal. Hence, H = Gxi for
a non-constant configuration xi ∈ AG , and, by the proof of Lemma 11, ICA(G; A) is not transitive on
xi G. Consider the idempotent τi,1 ∈ V . Then τi,1 = (P → x1 ), where P is the ICA(G; A)-orbit inside
xi G that contains xi and x1 ∈ AG is a constant configuration. Let Q be an ICA(G; A)-orbit inside xi G
such that Q 6= P . As there is no φ ∈ ICA(G; A) mapping P to Q, we have (Q → xi ) ∈
/ hICA(G; A)∪V i.
Therefore, the edge ([H], [G]) of the graph on CG must be counted at least twice for its contribution
towards the relative rank of ICA(G; A) on CA(G; A). The claim follows.

Using Theorem 7, we may find an upper bound for the smallest size of a generating set of CA(G; A),
when G is a finite Dedekind group.
16

Corollary 5. Let G be a finite Dedekind group and A a finite set of size q ≥ 2. Suppose that
Rank(G) = m and that G has r different subgroups. Then,
1
Rank(CA(G; A)) ≤ m(r − 1) + r(r + 5).
2
Proof. Observe that for any α ≥ 3 and any H ≤ G, we have Rank((G/H) ≀ Symα ) ≤ m + 2 because
{((g1 , e, . . . , e); id), . . . , ((gm , e, . . . , e); id), ((e, . . . , e); (1, 2)), ((e, . . . , e); (1, 2, . . . , α))}
is a generating set of (G/H) ≀ Symα , whenever {g1 , . . . , gm } is a generating set for G.
Let H1 , H2 , . . . , Hr be the list of different subgroups of G with H1 = G. For each 1 ≤ i ≤ r, let
αi := α[Hi ] (G; A). Thus, by Lemma 8, Corollary 3, and Theorem 7 we have:
Rank(CA(G; A)) = Rank(ICA(G; A)) + Rank(CA(G; A) : ICA(G; A))
r
X
Rank((G/Hi ) ≀ Symαi ) + |EG |
≤
i=1

≤ Rank(Symq ) +

r
X
i=2

 
r
(m + 2) +
+r
2

1
≤ 2 + (r − 1)(m + 2) + r(r − 1) + r
2
1
= m(r − 1) + r(r + 5).
2

H5 ∼
= Z1

H2 ∼
= Z2

H3 ∼
= Z2

H4 ∼
= Z2

H1 = G

Figure 1: Hasse diagram of subgroup lattice of G = Z2 × Z2 .
The bound of Corollary 5 may become tighter if we actually know |EG | and Rank(G/Hi ), for all
Hi ≤ G.
Example 5. Let G = Z2 × Z2 be the Klein-four group and A = {0, 1}. With the notation of Example
2, Figure 1 illustrates the Hasse diagram of the subgroup lattice of G (i.e. the actual lattice of
subgroups is the transitive and reflexive closure of this graph). Hence, by Theorem 7 and Example 4,
Rank(CA(G; A) : ICA(G; A)) = |EG | − 3 = 12 − 3 = 9,
Rank(CA(G; A)) ≤ 9 + 9 = 18, as Rank(ICA(G; A)) ≤ 9.

6

Conclusions

In this paper we studied the monoid CA(G; A) of all cellular automata over a finite group G and a
finite set A. Our main results are the following:

17

1. We completely determined the structure of the group of invertible cellular automata ICA(G; A)
in terms of the structure of G (Theorem 3).
2. We improved the known lower bound on the number of aperiodic configurations of AG (Theorem
5).
3. We showed that any generating set of CA(G; A) must have at least one cellular automaton whose
minimal memory set is G itself (Theorem 6).
4. We gave a lower bound for the minimal size of a set V ⊆ CA(G; A) such that ICA(G; A) ∪ V
generates CA(G; A), and we showed that this lower bound is achieved if and only if all subgroups
of G are normal (Theorem 7).
Most of our results are particularly good for finite Dedekind groups, i.e. finite groups in which all
subgroups are normal (this includes all finite abelian groups).
Some open problems and directions for future work are the following:
1. Examine further the case when G is not a Dedekind group; in particular, determine the relative
rank of ICA(G; A) on CA(G; A).
2. Improve the upper bound on Rank(CA(G; A)) given by Corollary 5.
3. Study generating sets of CA(G; A) when G is an infinite group.
4. Study other algebraic properties of the monoid CA(G; A).

7

Acknowledgments

This work was supported by the EPSRC grant EP/K033956/1. We kindly thank Turlough Neary and
Matthew Cook for their invitation to submit this paper and for the organisation of the conference
AUTOMATA 2016. We also thank the referees of this paper for their insightful suggestions.

References
[1] Araújo, J., Bentz, W., Mitchell, J.D., Schneider, C.: The rank of the semigroup of transformations
stabilising a partition of a finite set. Mat. Proc. Camb. Phil. Soc. 159, 339–353 (2015).
[2] Araújo, J., Schneider, C.: The rank of the endomorphism monoid of a uniform partition. Semigroup
Forum 78, 498–510 (2009).
[3] Cameron, P.J.: Combinatorics: Topics, Techniques, Algorithms. Cambridge University Press,
Cambridge (1994).
[4] Castillo-Ramirez, A., Gadouleau, M.: Ranks of finite semigroups of one-dimensional cellular automata. Semigroup Forum 93, no. 2, 347–362 (2016).
[5] Castillo-Ramirez, A., Gadouleau, M.: On Finite Monoids of Cellular Automata. In: Cook, M.,
Neary, T. (eds.) Cellular Automata and Discrete Complex Systems. LNCS 9664, 90–104, Springer
International Publishing (2016).
[6] Ceccherini-Silberstein, T., Coornaert, M.: Cellular Automata and Groups. Springer Monographs
in Mathematics, Springer-Verlag Berlin Heidelberg (2010).
[7] Cyr, V., Bryna, K.: The automorphism group of a shift of linear growth: beyond transitivity.
Forum Math. Sigma 3, e5, 1–27 (2015).
[8] Dedekind, R.: Ueber Gruppen, deren sämmtliche Theiler Normaltheiler sind (German) Math. Ann.
48, no. 4, 548–561 (1897).
18

[9] Dixon, J.D., Mortimer, B.: Permutation Groups. Graduate Texts in Mathematics 163, SpringerVerlag, New York (1996).
[10] Ganyushkin, O., Mazorchuk, V.: Classical Finite Transformation Semigroups: An Introduction.
Algebra and Applications 9, Springer-Verlag, London (2009).
[11] Gao, S., Jackson, S., Seward, B.: Group Colorings and Bernoulli Subflows. Mem. Am. Math. Soc.
241, no. 1141, 1–239 (2016).
[12] Gomes, G.M.S., Howie, J.M.: On the ranks of certain finite semigroups of transformations. Math.
Proc. Camb. Phil. Soc. 101, 395–403 (1987).
[13] Gray, R.D.: The minimal number of generators of a finite semigroup. Semigroup Forum 89,
135–154 (2014).
[14] Hartman, Y.: Large semigroups of cellular automata. Ergodic Theory Dyn. Syst. 32, 1991–2010
(2012).
[15] Hawkes, T., Isaacs, I.M., Özaydin, M.: On the Möbius Function of a Finite Group. Rocky Mt. J.
Math. 19, no. 4, 1003–1034 (1989).
[16] Howie, J.M., McFadden, R.B.: Idempotent rank in finite full transformation semigroups. Proc.
Royal Soc. Edinburgh 114A, 161–167 (1990).
[17] Kari, J.: Theory of cellular automata: A Survey. Theoret. Comput. Sci. 334, 3–33 (2005).
[18] Kerber, A.: Applied Finite Group Actions, 2nd ed. Algorithms and Combinatorics 19, Springer
(1999).
[19] Salo, V.: Groups and Monoids of Cellular Automata. In: Kari, J. (ed.) Cellular Automata and
Discrete Complex Systems. LNCS 9099, 17–45, Springer Berlin Heidelberg (2015).
A. Castillo-Ramirez (Corresponding author), Universidad de Guadalajara, CUCEI, Departamento de Matemáticas,
Guadalajara, México.
Email: alonso.castillor@academicos.udg.mx
M. Gadouleau, School of Engineering and Computing Sciences, Durham University, South Road, Durham
DH1 3LE, U.K.
Email: m.r.gadouleau@durham.ac.uk

19

