Ranks of finite semigroups of one-dimensional cellular automata

Abstract

Since first introduced by John von Neumann, the notion of cellular automaton has grown into a key concept in computer science, physics and theoretical biology. In its classical setting, a cellular automaton is a transformation of the set of all configurations of a regular grid such that the image of any particular cell of the grid is determined by a fixed local function that only depends on a fixed finite neighbourhood. In recent years, with the introduction of a generalised definition in terms of transformations of the form $\tau : A^G \rightarrow A^G$ (where G is any group and A is any set), the theory of cellular automata has been greatly enriched by its connections with group theory and topology. In this paper, we begin the finite semigroup theoretic study of cellular automata by investigating the rank (i.e. the cardinality of a smallest generating set) of the semigroup $\mathrm {CA}(\mathbb {Z}_n; A)$ consisting of all cellular automata over the cyclic group $\mathbb {Z}_n$ and a finite set A. In particular, we determine this rank when n is equal to p, $2^k$ or $2^kp$, for any odd prime p and $k \ge 1$, and we give upper and lower bounds for the general case.

1 Introduction

Cellular automata (CA) were introduced by John von Neumann as an attempt to design self-reproducing systems that were computationally universal (see [19]). Since then, the theory of CA has grown into an important area of computer science, physics, and theoretical biology (e.g. [4, 12, 20]). Among the most famous CA are Rule 110 and John Conway’s Game of Life, both of which have been widely studied as discrete dynamical systems and are known to be capable of universal computation.

In recent years, many interesting results linking CA and group theory have appeared in the literature (e.g. see [3–5]). One of the goals of this paper is to embark in the new task of exploring CA from the point of view of finite semigroup theory.

We shall review the broad definition of CA that appears in [4, Sect. 1.4]. Let G be a group and A a set. Denote by $A^G$ the set of functions of the form $x:G \rightarrow A$. For each $g \in G$, denote by $R_g : G \rightarrow G$ the right multiplication map, i.e. $(h)R_g := hg$ for any $h \in G$. We shall emphasise that in this paper we apply maps on the right, while in [4] maps are applied on the left.

Definition 1

Let G be a group and A a set. A cellular automaton over G and A is a map $\tau : A^G \rightarrow A^G$ satisfying the following property: there exists a finite subset $S \subseteq G$ and a local map $\mu : A^S \rightarrow A$ such that

$$\begin{aligned} (g)(x)\tau = (( R_g \circ x )\vert _{S}) \mu , \end{aligned}$$

for all $x \in A^G$, $g \in G$, where $(R_g \circ x )\vert _{S}$ is the restriction to S of $(R_g \circ x) : G \rightarrow A$.

Let $\mathrm {CA}(G;A)$ be the set of all cellular automata over G and A; it is straightforward to show that, under composition of maps, $\mathrm {CA}(G;A)$ is a semigroup. Most of the literature on CA focus on the case when $G=\mathbb {Z}^d$, $d\ge 1$, and A is a finite set (see [12]). In this situation, an element $\tau \in \mathrm {CA}(\mathbb {Z}^d;A)$ is referred as a d-dimensional cellular automaton.

Although results on semigroups of CA have appeared in the literature before (see [10, 18]), the semigroup structure of $\mathrm {CA}(G;A)$ remains basically unknown. In particular, the study of the finite semigroups $\mathrm {CA}(G;A)$, when G and A are finite, has been generally disregarded, perhaps because some of the classical questions are trivially answered (e.g. the Garden of Eden theorem becomes trivial). However, many new questions, typical of finite semigroup theory, arise in this setting.

One of the fundamental problems in the study of a finite semigroup M is the determination of the cardinality of a smallest generating subset of M; this is called the rank of M and denoted by $\mathrm {Rank}(M)$:

$$\begin{aligned} \mathrm {Rank}(M) := \min \{ \vert H \vert : H \subseteq M \text { and } \langle H \rangle = M \}. \end{aligned}$$

It is well-known that, if X is any finite set, the rank of the full transformation semigroup $\mathrm {Tran}(X)$ (consisting of all functions $f : X \rightarrow X$) is 3, while the rank of the symmetric group $\mathrm {Sym}(X)$ is 2 (see [7, Ch. 3]). Ranks of various finite semigroups have been determined in the literature before (e.g. see [1, 2, 8, 9, 11]).

In order to hopefully bring more attention to the study of finite semigroups of CA, we shall propose the following problem.

Problem 1

For any finite group G and any finite set A, determine $\mathrm {Rank}(\mathrm {CA}(G;A))$.

A natural restriction of this problem, and perhaps a more feasible goal, is to determine the ranks of semigroups of CA over finite abelian groups.

In this paper we study the finite semigroups $\mathrm {CA}(\mathbb {Z}_n;A)$, where $\mathbb {Z}_n$ is the cyclic group of order $n \ge 2$ and A is a finite set with at least two elements. By analogy with the classical setting, we may say that the elements of $\mathrm {CA}(\mathbb {Z}_n;A)$ are one-dimensional cellular automata over $\mathbb {Z}_n$ and A.

In this paper we shall establish the following theorems.

Theorem 1

Let $k \ge 1$ be an integer, p an odd prime, and A a finite set of size $q \ge 2$. Then:

$$\begin{aligned} \mathrm {Rank}(\mathrm {CA}(\mathbb {Z}_p; A))&= 5; \\ \mathrm {Rank}(\mathrm {CA}(\mathbb {Z}_{2^k}; A))&= {\left\{ \begin{array}{ll} \frac{1}{2} k (k+7), &{}\quad \text { if }\quad q = 2; \\ \frac{1}{2} k (k+7) + 2, &{}\quad \text { if }\quad q \ge 3; \end{array}\right. } \\ \mathrm {Rank}(\mathrm {CA}(\mathbb {Z}_{2^kp}; A))&= {\left\{ \begin{array}{ll} \frac{1}{2} k (3k+17) + 3 , &{} \quad \text { if }\quad q=2; \\ \frac{1}{2} k (3k+ 17) + 5, &{}\quad \text { if }\quad q \ge 3. \end{array}\right. } \end{aligned}$$

Let $2 \mathbb {Z}$ be the set of even integers. For any integer $n \ge 2$, let $[n]:=\{1,2, \dots , n\}$. Denote by $\mathrm {d}(n)$ the number of divisors of n (including 1 and n itself) and by $\mathrm {d}_+(n)$ the number of even divisors of n. Let

$$\begin{aligned} E(n) := \left| \left\{ (s,t) \in [n]^2: t\mid n, \ s \mid n, \text { and } t \mid s \right\} \right| \end{aligned}$$

be the number of edges in the divisibility digraph of n (see Sect. 4).

Theorem 2

Let $n \ge 2$ be an integer and A a finite set of size $q \ge 2$. Then:

$$\begin{aligned} \mathrm {Rank}( \mathrm {CA}(\mathbb {Z}_n; A) ) = {\left\{ \begin{array}{ll} \mathrm {d}(n) + \mathrm {d}_+(n) + E(n) - 2 + \epsilon (n,2), &{}\quad \text { if }\quad q=2 \, \text { and }\, n \in 2 \mathbb {Z}; \\ \mathrm {d}(n) + \mathrm {d}_+(n) + E(n) + \epsilon (n,q), &{}\quad \text {otherwise;} \end{array}\right. } \end{aligned}$$

where $0 \le \epsilon (n,q) \le \max \{ 0 , \mathrm {d}(n) - \mathrm {d}_+(n) - 2 \}$.

2 Preliminary results

For the rest of the paper, let $n \ge 2$ be an integer and A a finite set of size $q \ge 2$. We may assume that $A = \{0,1,\dots ,q-1\}$. When G is a finite group, we may always assume that the finite subset $S \subseteq G$ of Definition 1 is equal to G, so any cellular automaton over G and A is completely determined by the local map $\mu : A^G \rightarrow A$. Therefore, if $\vert G \vert = n$, we have $\left| \mathrm {CA}(G ; A)\right| = q^{q^n}$.

It is clear that $\mathrm {CA}(\mathbb {Z}_n;A)$ is contained in the semigroup of transformations $\mathrm {Tran}(A^n)$, where $A^n$ is the n-th Cartesian power of A. For any $f \in \mathrm {Tran}(A^n)$ write $f=(f_1, \dots , f_n)$, where $f_i : A^n \rightarrow A$ is the i-th coordinate function of f. For any semigroup M and $\sigma \in M$, define the centraliser of $\sigma$ in M by

$$\begin{aligned} C_{M} (\sigma ) := \{ \tau \in M : \tau \sigma = \sigma \tau \}. \end{aligned}$$

It turns out that $\mathrm {CA}(\mathbb {Z}_n ; A)$ is equal to the centraliser of a certain transformation in $\mathrm {Tran}(A^n)$.

For any $f \in \mathrm {Tran}(A^n)$, define an equivalence relation $\sim$ on $A^n$ as follows: for any $x,y \in A^n$, say that $x \sim y$ if and only if there exist $r,s \ge 1$ such that $(x)f^r = (y)f^s$. The equivalence classes induced by this relation are called the orbits of f.

Lemma 1

Let $n \ge 2$ be an integer and A a finite set. Consider the map $\sigma : A^n \rightarrow A^n$ given by

$$\begin{aligned} (x_1, \dots , x_n ) \sigma = (x_n, x_1, \dots , x_{n-1}). \end{aligned}$$

Then:

(i):

$\mathrm {CA}(\mathbb {Z}_n ; A) = C_{\mathrm {Tran}(A^n)}(\sigma ) := \{ \tau \in \mathrm {Tran}(A^n) : \tau \sigma = \sigma \tau \}$.

(ii):

Let $\mathcal {O}$ be the set of orbits of $\sigma : A^n \rightarrow A^n$. For every $P \in \mathcal {O}$, $\vert P \vert$ divides n.

(iii):

Every $\tau \in \mathrm {CA}(\mathbb {Z}_n; A)$ satisfies the following property: for every $P \in \mathcal {O}$ there exists $Q \in \mathcal {O}$, with $\vert Q \vert$ dividing $\vert P \vert$, such that $(P)\tau = Q$.

Proof

We shall prove each part.

(i):

By Definition 1, a map $\tau :A^n \rightarrow A^n$ is a cellular automaton over $G=\mathbb {Z}_n$ and A if and only if there exists a map $\mu :A^n \rightarrow A$ such that

$$\begin{aligned} (x_1, x_2, \dots , x_n )\tau _i = (x_{1+i},x_{2+i}, \dots , x_{n+i})\mu \end{aligned}$$

for any $1 \le i \le n$, where the sum in the subindex of $x_{j+i}$ is done modulo n. Hence,

$$\begin{aligned} (x_1, x_2, \dots , x_n) \sigma \tau&= (x_n, x_1, \dots , x_{n-1})\tau \\&= ((x_1, x_2, \dots , x_n )\mu , (x_2, x_3, \dots , x_1)\mu , \dots , (x_n, x_1, \dots , x_{n-1})\mu ) \\&= ((x_2, x_3, \dots , x_1)\mu , (x_3, x_4, \dots , x_2) \mu , \dots , (x_1, x_2, \dots , x_n )\mu ) \sigma \\&= (x_1, x_2, \dots , x_n) \tau \sigma . \end{aligned}$$

This shows that $\mathrm {CA}(\mathbb {Z}_n ; A) \le \{ \tau \in \mathrm {Tran}(A^n) : \tau \sigma = \sigma \tau \}$. Let $f \in \mathrm {Tran}(A^n)$ be such that $f\sigma = \sigma f$. This implies that $f \sigma ^k = \sigma ^k f$ for any $k \in \mathbb {Z}$, so

$$\begin{aligned} (x_1, x_2, \dots , x_n ) f_{n-k} = (x_{1-k}, x_{2-k}, \dots , x_{n-k}) f_{n}. \end{aligned}$$

Therefore, f is a cellular automaton over $\mathbb {Z}_n$ and A with $\mu = f_n$.

(ii):

This follows directly by the Orbit-Stabiliser Theorem ([6, Theorem 1.4A]).

(iii):

Fix $\tau \in \mathrm {CA}(\mathbb {Z}_n ; A)$, $P \in \mathcal {O}$ and $x \in P$. By definition of orbit, and since $\sigma$ is a permutation, for every $y \in P$ there is $i \in \mathbb {Z}$ such that $(x)\sigma ^i = y$. By part (i), $(x)\tau \sigma ^i = (x)\sigma ^i \tau = (y)\tau$, so $(P)\tau \subseteq Q$ for some $Q \in \mathcal {O}$. Furthermore, for every $z \in Q$ there is $j \in \mathbb {Z}$ such that $(z)\sigma ^j = (x)\tau$, so $z = (x)\sigma ^{-j}\tau \in (P)\tau$. This shows that $(P)\tau = Q$. Finally, we show that $\vert Q \vert$ divides $\vert P \vert$. Fix $z \in Q$. For any $w \in Q$ there is $k \in \mathbb {Z}$ such that $z = (w) \sigma ^k$. Then $\sigma ^k$ is a bijection between the preimage sets $(z) \tau ^{-1}$ and $(w) \tau ^{-1}$. This means that $\left| (z) \tau ^{-1} \right| = \left| (w) \tau ^{-1} \right|$ for every $w \in Q=(P)\tau$. Therefore,

$$\begin{aligned} \vert P \vert = \sum _{w \in Q} \left| (w)\tau ^{-1} \right| = \left| (z)\tau ^{-1} \right| \cdot \left| Q \right| . \end{aligned}$$

Lemma 1 (i) is in fact a particular case of a more general result.

Lemma 2

Let G be a finite group and A a finite set. For each $g \in G$, let $\sigma _g \in \mathrm {Tran}(A^G)$ be the transformation defined by $(h)(x)\sigma _g := (hg^{-1})x$, for any $h \in G, x \in A^G$. Then,

$$\begin{aligned} \mathrm {CA}(G;A) = \{ \tau : A^G \rightarrow A^G : \tau \sigma _g = \sigma _g \tau , \ \forall g \in G \}. \end{aligned}$$

Proof

The result follows by Curtis-Hedlund Theorem (see [4, Theorem 1.8.1]).

Let $\mathrm {ICA}(G;A)$ be the set of invertible cellular automata:

$$\begin{aligned} \mathrm {ICA}(G;A) := \{ \tau \in \mathrm {CA}(G;A) : \exists \phi \in \mathrm {CA}(G;A) \text { such that } \tau \phi = \phi \tau = \mathrm {id}\}. \end{aligned}$$

It may be shown that $\mathrm {ICA}(G;A) = \mathrm {CA}(G;A) \cap \mathrm {Sym}(A^G)$ whenever A is finite (see [4, Theorem 1.10.2]).

We shall use the cyclic notation to denote the permutations in $\mathrm {Tran}(A^n)$. If $D \subseteq A^n$ and $a \in A^n$, we define the transformation $(D \rightarrow a) \in \mathrm {Tran}(A^n)$ by

$$\begin{aligned} (x)(D \rightarrow a) := {\left\{ \begin{array}{ll} a &{} \text { if } x \in D \\ x &{} \text { otherwise }. \end{array}\right. } \end{aligned}$$

When $D=\{ b\}$ is a singleton, we write $(b \rightarrow a)$ instead of $(\{ b\} \rightarrow a)$.

In the following examples, we identify the elements of $A^n$ with their lexicographical order: $(a_1, a_2, \dots , a_n) \sim \sum _{i=1}^n a_i q^{i-1}$.

Example 1

A generating set for $\mathrm {CA}\left( \mathbb {Z}_{2} ; \{ 0,1 \} \right)$ is

$$\begin{aligned} \{ (1,2), \ (\{1,2\} \rightarrow 0), \ (0,3), \ (3 \rightarrow 0) \}, \end{aligned}$$

where $0:=(0,0)$, $1:=(1,0)$, $2:=(0,1)$ and $3:=(1,1)$. Direct calculations in GAP show that indeed $\mathrm {Rank}(\mathrm {CA}\left( \mathbb {Z}_{2} ; \{ 0,1 \} \right) ) = 4$.

Example 2

A generating set for $\mathrm {CA}\left( \mathbb {Z}_{3} ; \{ 0,1 \} \right)$ is

$$\begin{aligned} \{\left( 1,2,4\right) \left( 0,7\right) , \ \left( 1,6\right) \left( 2,5\right) \left( 3,4\right) , \ (1 \rightarrow 6) (2 \rightarrow 5)( 4 \rightarrow 3), \ (\{1,2,4\} \rightarrow 0), \left( 7\rightarrow 0\right) \}. \end{aligned}$$

Direct calculations in GAP show that indeed $\mathrm {Rank}(\mathrm {CA}\left( \mathbb {Z}_{3} ; \{ 0,1 \} \right) ) = 5$.

If U is a subset of a finite semigroup M, the relative rank of U in M, denoted by $\mathrm {Rank}(M:U)$, is the minimum cardinality of a subset $V \subseteq M$ such that $\langle U,V \rangle = M$. The proof of the main results of this paper are based in the following observation.

Lemma 3

Let G be a finite group and A a finite set. Then,

$$\begin{aligned} \mathrm {Rank}(\mathrm {CA}(G ; A)) = \mathrm {Rank}(\mathrm {CA}(G;A):\mathrm {ICA}(G;A)) + \mathrm {Rank}(\mathrm {ICA}(G;A)). \end{aligned}$$

Proof

As $\mathrm {ICA}(G;A)$ is the group of units of $\mathrm {CA}(G ; A)$, this follows by [1, Lemma 3.1]. $\square$

In Sect. 3 we study the rank of $\mathrm {ICA}(\mathbb {Z}_n;A)$, while in Sect. 4 we study the relative rank of $\mathrm {ICA}(\mathbb {Z}_n;A)$ in $\mathrm {CA}(\mathbb {Z}_n;A)$.

3 The rank of $\mathrm {ICA}(\mathbb {Z}_n ; A)$

Let $\sigma : A^n \rightarrow A^n$ be as defined in Lemma 1. For any $d \ge 1$ dividing n, the number of orbits of $\sigma$ of size d is given by the Moreau’s necklace-counting function

$$\begin{aligned} \alpha (d, q) = \frac{1}{d} \sum _{b \mid d} \mu \left( \frac{d}{b} \right) q^{b}, \end{aligned}$$

where $\mu$ is the classic Möbius function (see [14]). In particular, if $d=p^k$, where p is a prime number and $k \ge 1$, then

$$\begin{aligned} \alpha (p^k, q) = \frac{q^{p^k} - q^{p^{k-1}}}{p^k}. \end{aligned}$$

(1)

Remark 1

Observe that $\alpha (d,q) = 1$ if and only if $(d,q)=(2,2)$. Hence, the case when n is even and $q=2$ is degenerate and shall be analysed separately in the rest of the paper.

We say that d is a non-trivial divisor of n if $d \mid n$ and $d \ne 1$ (note that, in our definition, $d = n$ is a non-trivial divisor of n). For any integer $\alpha \ge 1$, let $\mathrm {Sym}_\alpha$ and $\mathrm {Alt}_\alpha$ be the symmetric and alternating groups on $[\alpha ]=\{1, \dots , \alpha \}$, respectively.

A wreath product of the form $\mathbb {Z}_d \wr \mathrm {Sym}_{\alpha } := \{ (v; \phi ) : v \in (\mathbb {Z}_d)^\alpha , \phi \in \mathrm {Sym}_\alpha \}$ is called a generalized symmetric group (see [17]). We shall use the additive notation for the elements of $(\mathbb {Z}_d)^\alpha$, so the product in $\mathbb {Z}_d \wr \mathrm {Sym}_{\alpha }$ is

$$\begin{aligned} (v;\phi ) \cdot (w; \psi ) = (v + w^{\phi }; \phi \psi ), \end{aligned}$$

where $v,w \in (\mathbb {Z}_d)^\alpha$, $\phi , \psi \in \mathrm {Sym}_\alpha$, and $\phi$ acts on w by permuting the coordinates. We shall identify the elements $(v; \mathrm {id}) \in \mathbb {Z}_d \wr \mathrm {Sym}_{\alpha }$ with $v \in (\mathbb {Z}_d)^\alpha$.

The following result is a refinement of [18, Theorem 9].

Lemma 4

Let $n \ge 2$ be an integer and A a finite set of size $q \ge 2$. Let $d_1, d_2, \dots , d_\ell$ be the non-trivial divisors of n. Then

$$\begin{aligned} \mathrm {ICA}(\mathbb {Z}_n; A) \cong (\mathbb {Z}_{d_1} \wr \mathrm {Sym}_{\alpha (d_1,q)}) \times \dots \times (\mathbb {Z}_{d_\ell } \wr \mathrm {Sym}_{\alpha (d_\ell ,q)}) \times \mathrm {Sym}_q . \end{aligned}$$

Proof

Let $\mathcal {O}$ the set of orbits of $\sigma : A^n \rightarrow A^n$ as defined in Lemma 1. Part (ii) of that lemma shows that $\mathrm {CA}(\mathbb {Z}_n ; A)$ is contained in the semigroup

$$\begin{aligned} \mathrm {Tran}(A^n, \mathcal {O}) := \{ f \in \mathrm {Tran}(A^n) : \forall P \in \mathcal {O}, \ \exists Q \in \mathcal {O} \text { such that } (P)f \subseteq Q \}. \end{aligned}$$

As $\mathcal {O}$ contains q singletons and $\alpha (d_i, q)$ orbits of size $d_i \ge 2$, we know by [2, Lemma 2.1] that the group of units of $\mathrm {Tran}(A^n, \mathcal {O})$ is

$$\begin{aligned} S(A^n, \mathcal {O}) \cong (\mathrm {Sym}_{d_1} \wr \mathrm {Sym}_{\alpha (d_1,q)}) \times \dots \times (\mathrm {Sym}_{d_\ell } \wr \mathrm {Sym}_{\alpha (d_\ell ,q)}) \times \mathrm {Sym}_q. \end{aligned}$$

Clearly, $\mathrm {ICA}(\mathbb {Z}_n ; A) \le S(A^n, \mathcal {O})$. Let P be an orbit of size $d_i$. Since the restriction of $\sigma$ to P, denoted by $\sigma \vert _{P}$, is a cycle of length $d_i$, and the centraliser of $\sigma \vert _{P}$ in $\mathrm {Sym}_{d_i}$ is $\langle \sigma \vert _{P} \rangle \cong \mathbb {Z}_{d_i}$, it follows that

$$\begin{aligned} \mathrm {ICA}(\mathbb {Z}_n ; A) \le (\mathbb {Z}_{d_1} \wr \mathrm {Sym}_{\alpha (d_1,q)}) \times \dots \times (\mathbb {Z}_{d_\ell } \wr \mathrm {Sym}_{\alpha (d_\ell ,q)}) \times \mathrm {Sym}_q. \end{aligned}$$

Equality follows as any permutation stabilising the sets of orbits of size $d_i$ commutes with $\sigma$. $\square$

For $1 \le i \le \alpha$, denote by $e^i$ the element of $(\mathbb {Z}_d)^\alpha$ with 1 at the i-th coordinate, and 0 elsewhere. Denote by $e^0$ the element of $(\mathbb {Z}_d)^\alpha$ with 0’s everywhere. For any $\alpha \ge 2$, define permutations $z_\alpha \in \mathrm {Sym}_\alpha$ by

$$\begin{aligned} z_\alpha := {\left\{ \begin{array}{ll} (1,2,3,\dots ,\alpha ), &{} \text { if } \alpha \text { is odd,} \\ (2,3, \dots , \alpha ) &{} \text { if } \alpha \text { is even.} \end{array}\right. } \end{aligned}$$

(2)

Note that the order of $z_\alpha$, denoted by $o(z_\alpha )$, is always odd.

In the following Lemma we determine the rank of the generalized symmetric group.

Lemma 5

Let $d, \alpha \ge 2$. Then, $\mathrm {Rank}\left( \mathbb {Z}_d \wr \mathrm {Sym}_{\alpha } \right) = 2$.

Proof

It is clear that $\mathbb {Z}_d \wr \mathrm {Sym}_{\alpha }$ is not a cyclic group, so $2 \le \mathrm {Rank}\left( \mathbb {Z}_d \wr \mathrm {Sym}_{\alpha } \right)$.

Define $z_\alpha$ as in (2). We will show that $\mathbb {Z}_d \wr \mathrm {Sym}_{\alpha }$ is generated by

$$\begin{aligned} x:= (e^1; z_\alpha ) \ \text { and } \ y:= (e^1 ;(1,2)). \end{aligned}$$

Let $M := \langle x,y \rangle \le \mathbb {Z}_d \wr \mathrm {Sym}_{\alpha }$. Let $\rho : \mathbb {Z}_d \wr \mathrm {Sym}_{\alpha } \rightarrow \mathrm {Sym}_\alpha$ be the natural projection, and note that this is a group homomorphism. Clearly, $(M)\rho = \mathrm {Sym}_\alpha$ and $\ker (\rho ) = (\mathbb {Z}_d)^\alpha$, so, in order to prove that $M=\mathbb {Z}_d \wr \mathrm {Sym}_{\alpha }$, it suffices to show that $(\mathbb {Z}_d)^\alpha \le M$.

Since $(M)\rho = \mathrm {Sym}_\alpha$, the intersection $(\mathbb {Z}_d)^\alpha \cap M$ is a $\mathrm {Sym}_\alpha$-invariant submodule of $(\mathbb {Z}_d)^\alpha$. If $\alpha = 2$, then $x = e^1$ generates $(\mathbb {Z}_d)^\alpha$ as $\mathrm {Sym}_\alpha$-module, so $(\mathbb {Z}_d^\alpha ) \cap M = (\mathbb {Z}_d^\alpha )$. Henceforth, assume $\alpha \ge 3$. Observe that

$$\begin{aligned} y^2 = e^1 + e^2 = (1, 1, 0 \dots , 0) \in (\mathbb {Z}_d)^\alpha \cap M. \end{aligned}$$

Now, by $\mathrm {Sym}_\alpha$-invariance

$$\begin{aligned}&y^2 + \sum _{i=1}^{d-1} \big (y^2\big )^{(1,2,3)} + \big (y^2\big )^{(1,3,2)} \\&\quad = (1, 1, 0, \dots , 0) + (0, d-1, d-1, 0, \dots , 0) + (1,0,1,0, \dots , 0) \\&\quad = (2,0,\dots ,0) =: 2e^1 \in (\mathbb {Z}_d)^\alpha \cap M \end{aligned}$$

If d is odd, then $2e^1$ generates $(\mathbb {Z}_d)^\alpha$ as $\mathrm {Sym}_\alpha$-module, so $(\mathbb {Z}_d)^\alpha \cap M = (\mathbb {Z}_d)^\alpha$.

Suppose that d is even and $\alpha$ is odd. Then,

$$\begin{aligned} x^{\alpha } = (1,1, \dots , 1) \in (\mathbb {Z}_d)^\alpha \cap M. \end{aligned}$$

Since $\mathrm {Sym}_\alpha$ is 2-transitive on the basis of $(\mathbb {Z}_d)^\alpha$ and $y^2 = (1, 1, 0 \dots , 0) \in (\mathbb {Z}_d)^\alpha \cap M$, we obtain that $(1,\dots ,1,0) \in (\mathbb {Z}_d)^\alpha \cap M$. Therefore,

$$\begin{aligned} (1,1, \dots , 1) - (1,\dots ,1,0) = (0,\dots ,0,1) \in (\mathbb {Z}_d)^\alpha \cap M, \end{aligned}$$

and $(\mathbb {Z}_d)^\alpha \cap M = (\mathbb {Z}_d)^\alpha$.

Finally, suppose that d and $\alpha$ are both even. Then,

$$\begin{aligned} x^{\alpha -1} = (\alpha - 1, 0, \dots , 0) \in (\mathbb {Z}_d)^\alpha \cap M. \end{aligned}$$

Write $\alpha -1 = 2k + 1$, for some $k \in \mathbb {N}$. Then

$$\begin{aligned} x^{\alpha -1} - \sum _{i=1}^k 2e^1 = (1,0, \dots , 0) \in (\mathbb {Z}_d)^\alpha \cap M. \end{aligned}$$

Therefore, $(\mathbb {Z}_d)^\alpha \cap M = (\mathbb {Z}_d)^\alpha$. $\square$

We need the following results in order to establish $\mathrm {Rank}(\mathrm {ICA}(\mathbb {Z}_p, A))$ when p is a prime number.

Lemma 6

(Lemma 5.3.4 in [13]) Let $\alpha \ge 2$. The permutation module for $\mathrm {Sym}_\alpha$ over a field $\mathbb {F}$ of characteristic p has precisely two proper nonzero submodules:

$$\begin{aligned} U_1 := \left\{ (a,a, \dots , a) : a \in \mathbb {F} \right\} \ \ \text {and} \ \ U_2 := \left\{ (a_1, a_2, \dots , a_\alpha ) \in \mathbb {F}^{\alpha } : \sum _{i=1}^\alpha a_i = 0 \right\} \!. \end{aligned}$$

Theorem 3

([15, 16]) Let $q \ge 3$ be an integer.

(i):

Except for $q \in \{5,6,8 \}$, $\mathrm {Sym}_q$ is generated by an element of order 2 and an element of order 3.

(ii):

If $p^\prime > 3$ is a prime number dividing q! and $q \ne 2p^\prime -1$, then $\mathrm {Sym}_q$ is generated by an element of order 2 and an element of order $p^\prime$.

Lemma 7

Let p be a prime number and A a finite set of size $q \ge 2$. Then:

(i):

If $q \ge 3$ and $p=2$, then $\mathrm {Rank}(\mathrm {ICA}(\mathbb {Z}_2; A)) = 3$.

(ii):

If $q \ge 2$ and $p \ge 3$, or $q=p=2$, then $\mathrm {Rank}(\mathrm {ICA}(\mathbb {Z}_p; A)) = 2$.

Proof

If $q=p=2$, the result follows by Example 1. Assume $(p,q) \ne (2,2)$. By Lemma 4,

$$\begin{aligned} \mathrm {ICA}(\mathbb {Z}_p; A) \cong W:= (\mathbb {Z}_{p} \wr \mathrm {Sym}_{\alpha }) \times \mathrm {Sym}_q , \end{aligned}$$

where $\alpha :=\alpha (p,q) \ge 2$ is the Moreau’s necklace-counting function. We use the basic fact that $\mathrm {Rank}(G/N) \le \mathrm {Rank}(G)$, for any group G and any normal subgroup N of G. Let $U_2$ be the $\mathrm {Sym}_\alpha$-invariant submodule of $(\mathbb {Z}_p)^\alpha$ defined in Lemma 6. Then $U_2$ is a normal subgroup of $\mathbb {Z}_{p} \wr \mathrm {Sym}_{\alpha }$ such that $(\mathbb {Z}_{p} \wr \mathrm {Sym}_{\alpha })/U_2 \cong \mathbb {Z}_p \times \mathrm {Sym}_{\alpha }$. Now, $\mathrm {Alt}_{\alpha }$ is a normal subgroup of $\mathbb {Z}_p \times \mathrm {Sym}_{\alpha }$ with quotient $\mathbb {Z}_p \times \mathbb {Z}_2$. This implies that there is a normal subgroup N of $\mathbb {Z}_p \wr \mathrm {Sym}_{\alpha }$ with quotient isomorphic to $\mathbb {Z}_p \times \mathbb {Z}_2$. Therefore, $N \times \mathrm {Alt}_q$ is a normal subgroup of W with quotient group isomorphic to $\mathbb {Z}_{p} \times \mathbb {Z}_2 \times \mathbb {Z}_2$. Hence,

$$\begin{aligned} \mathrm {Rank}(\mathbb {Z}_{p} \times \mathbb {Z}_2 \times \mathbb {Z}_2) \le \mathrm {Rank}(W). \end{aligned}$$

(3)

Define $z_\alpha$ and $z_q$ as in (2). We shall prove the two cases (i) and (ii).

(i):

Suppose that $q \ge 3$ and $p = 2$, so $3 \le \mathrm {Rank}(W)$ by (3). We shall show that $W = \langle v_1, v_2, v_3 \rangle$ where

$$\begin{aligned} v_1&:= ( (e^1 ; z_\alpha ), \mathrm {id}), \\ v_2&:= ( (e^1 ; (1,2)), z_q ), \\ v_3&:= ((e^0; \mathrm {id}), (1,2) ). \end{aligned}$$

The projections of $v_1$, $v_2$ and $v_3$ to $\mathrm {Sym}_q$ generate $\mathrm {Sym}_q$, so it is enough to prove that $v_1$ and

$$\begin{aligned} (v_2)^{o(z_q)} = {\left\{ \begin{array}{ll} ((e^1; (1,2)) , \mathrm {id}), &{} \text {if}\quad o(z_q) = 1 \mod (4) \\ ((e^2; (1,2)) , \mathrm {id}), &{} \text {if}\quad o(z_q) = 3 \mod (4) \end{array}\right. } \end{aligned}$$

generate $\mathbb {Z}_2 \wr \mathrm {Sym}_\alpha$. Let $M := \langle v_1, (v_2)^{o(z_q)} \rangle$. We follow a similar strategy as in the proof of Lemma 5. Note that the projections of $v_1$ and $(v_2)^{o(z_q)}$ to $\mathrm {Sym}_\alpha$ generate $\mathrm {Sym}_\alpha$. Now, $(\mathbb {Z}_2)^{\alpha } \cap M$ is an $\mathrm {Sym}_\alpha$-invariant submodule of $(\mathbb {Z}_2)^{\alpha }$.

If $\alpha$ is even, then

$$\begin{aligned} (v_1)^{o(z_\alpha )} = (1,0,\dots ,0) = e^1 \in (\mathbb {Z}_2)^{\alpha } \cap M, \end{aligned}$$

and so $(\mathbb {Z}_2)^{\alpha } \cap M= (\mathbb {Z}_2)^{\alpha }$ in this case.

Suppose that $\alpha$ is odd. Then

$$\begin{aligned} (v_1)^{o(z_\alpha )} = (1,1, \dots 1 )\in (\mathbb {Z}_2)^{\alpha } \cap M. \end{aligned}$$

Observe that

$$\begin{aligned} (v_2)^{2o(z_q)} = (1,1, 0, \dots , 0) \in (\mathbb {Z}_2)^{\alpha } \cap M . \end{aligned}$$

By the 2-transitivity of $\mathrm {Sym}_\alpha$ we obtain that $(0,1,\dots ,1) \in (\mathbb {Z}_2)^{\alpha } \cap M$. Therefore,

$$\begin{aligned} e^1 = (1,1,\dots ,1) + (0,1,\dots ,1) \in (\mathbb {Z}_2)^{\alpha } \cap M, \end{aligned}$$

and we conclude that $(\mathbb {Z}_2)^{\alpha } \cap M= (\mathbb {Z}_2)^{\alpha }$ in this case as well.

(ii):

Suppose that $q \ge 2$ and $p \ge 3$. Then $2 \le \mathrm {Rank}(W)$ by (3). Observe that (1) implies that $\alpha = \frac{q^p-q}{p}$ is always an even number. We shall find generators $u_1$ and $u_2$ of W of the form

$$\begin{aligned} u_1:=((e^1; (2,3, \dots , \alpha )), g ) \ \text { and } \ u_2:=((e^1; (1,2)), h ), \end{aligned}$$

(4)

where $g,h \in \mathrm {Sym}_q$, g is an involution, and $\langle g,h \rangle = \mathrm {Sym}_q$. As the projections of $u_1$ and $u_2$ to $\mathrm {Sym}_q$ generate $\mathrm {Sym}_q$, it is enough to show that $(u_1)^2$ and $(u_2)^{o(h)}$ generate $\mathbb {Z}_{p} \wr \mathrm {Sym}_{\alpha }$. Let $M:=\langle (u_1)^2, (u_2)^{o(h)} \rangle$. The projections of $(u_1)^2$ and $(u_2)^{o(h)}$ to $\mathrm {Sym}_\alpha$ generate $\mathrm {Sym}_\alpha$, so, as in the proof of Lemma 5, it is enough to show that $(\mathbb {Z}_p)^{\alpha } \le M$. Observe that $(\mathbb {Z}_p)^{\alpha } \cap M$ is a $\mathrm {Sym}_\alpha$-invariant subspace of $(\mathbb {Z}_p)^{\alpha }$.

We shall show that $(\mathbb {Z}_p)^{\alpha }\cap M$ is a nonzero $\mathrm {Sym}_\alpha$-invariant subspace of $(\mathbb {Z}_p)^{\alpha }$ different from $U_1$ and $U_2$, as given by Lemma 6, so $(\mathbb {Z}_p)^{\alpha }\cap M=M$. Whenever $\alpha \ge 3$, it suffices to show that at least one of the following elements of $(\mathbb {Z}_p)^{\alpha }\cap M$ is nonzero:

$$\begin{aligned} w_1&:= (u_1)^{2(\alpha -1)} = (2(\alpha -1),0, \dots ,0), \\ w_2&:= (u_2)^{2o(h)} = (o(h),o(h),0,\dots ,0). \end{aligned}$$

Let $q = 2$, and take $g := (1,2)$ and $h := (1)$. The only case when $\alpha =2$ is when $p=3$. Here, although $w_2 = (1,1)$ is nonzero, it generates $U_1$; however, $w_1 = (2,0) \not \in U_1 \cup U_2$, as required. For $p \ge 4$, $w_2 = (1,1,0,\dots ,0)$ is always nonzero, as required. Henceforth, suppose $q \ge 3$.

Assume first that $p > 3$. For $q \not \in \{ 5,6,8 \}$, take g and h as the generators of $\mathrm {Sym}_q$ of orders 2 and 3, respectively, stated in Theorem 3 (i). Hence, $w_2 = (3,3,0,\dots ,0)$ is nonzero.

For $q \in \{5,6,8 \}$, take $g := (1,2)$ and $h := z_q$ (as defined in (2)). If $q=5$, then $w_2$ is nonzero, except when $p=5$. In this case, by Eq. (1),

$$\begin{aligned} \alpha - 1 = \frac{5^5 - 5}{5} - 1 = 623 \ne 0 \mod (5), \end{aligned}$$

so $w_1$ is nonzero. If $q=6$, then $w_2$ is nonzero, except when $p=5$. In this case,

$$\begin{aligned} \alpha - 1 = \frac{6^5 - 6}{5} - 1 = 1553 \ne 0 \mod (5), \end{aligned}$$

so $w_1$ is nonzero. If $q=8$, then $w_2$ is nonzero, except when $p=7$. In this case,

$$\begin{aligned} \alpha - 1 = \frac{8^7 - 8}{7} - 1 = 299591 \ne 0 \mod (7), \end{aligned}$$

so $w_1$ is nonzero.

Assume now that $p=3$. If $q \ge 5$, then $5 \mid q!$ and, for $q \ne 2\cdot 5 -1 = 9$, we may take g and h as the generators of $\mathrm {Sym}_q$ of orders 2 and 5, respectively, stated in Theorem 3 (ii). Hence, $w_2$ is nonzero. If $q=3$, $q=4$, or $q=9$, then

$$\begin{aligned} \alpha - 1&= \frac{3^3 - 3}{3}-1 = 7 \ne 0 \mod (3), \\ \alpha - 1&= \frac{4^3 - 4}{3} - 1 = 19 \ne 0 \mod (3), \text { or } \\ \alpha - 1&= \frac{9^3 - 9}{3} -1 = 239 \ne 0 \mod (3), \end{aligned}$$

respectively. Therefore, $w_1$ is nonzero, which completes the proof.

$\square$

Recall that for any integer $n \ge 2$, we denote by $\mathrm {d}(n)$ the number of divisors of n (including 1 and n itself) and by $\mathrm {d}_+(n)$ the number of even divisors of n (so $\mathrm {d}_+(n)=0$ if and only if n is odd).

Theorem 4

Let $n \ge 2$ be an integer and A a finite set of size $q \ge 2$.

(i):

If n is not a power of 2, then

$$\begin{aligned} \mathrm {Rank}( \mathrm {ICA}(\mathbb {Z}_n; A) ) = {\left\{ \begin{array}{ll} \mathrm {d}(n) + \mathrm {d}_+(n) - 1 + \epsilon (n,2) &{}\quad \text {if }\quad q=2 \,\text { and }\, n \in 2\mathbb {Z}; \\ \mathrm {d}(n) + \mathrm {d}_+(n) + \epsilon (n,q), &{} \quad \text {otherwise;} \end{array}\right. } \end{aligned}$$

where $0 \le \epsilon (n,q) \le \mathrm {d}(n) - \mathrm {d}_+(n) - 2$.

(ii):

If $n = 2^k$, then

$$\begin{aligned} \mathrm {Rank}( \mathrm {ICA}(\mathbb {Z}_{2^k}; A) ) = {\left\{ \begin{array}{ll} 2 \mathrm {d}(2^k) - 2 = 2k &{}\quad \text {if }\quad q=2; \\ 2 \mathrm {d}(2^k) -1 = 2k + 1 &{}\quad \text {if }\quad q \ge 3. \end{array}\right. } \end{aligned}$$

Proof

Let $d_1, d_2, \dots , d_\ell$ be the non-trivial divisors of n, with $\ell = \mathrm {d}(n) - 1$, and let

$$\begin{aligned} \mathrm {ICA}(\mathbb {Z}_n; A) \cong W := (\mathbb {Z}_{d_1} \wr \mathrm {Sym}_{\alpha (d_1,q)}) \times \dots \times (\mathbb {Z}_{d_\ell } \wr \mathrm {Sym}_{\alpha (d_\ell , q )}) \times \mathrm {Sym}_q . \end{aligned}$$

Suppose first that $q \ne 2$ or n is odd. Then $\alpha (d_i,q) \ge 2$ for all i. As in the proof of Lemma 7, there is a normal subgroup $U \trianglelefteq \mathbb {Z}_{d_i} \wr \mathrm {Sym}_{\alpha (d_i,q)}$ with quotient group $\mathbb {Z}_{d_i} \times \mathrm {Sym}_{\alpha (d_i,q)}$, and $\mathrm {Alt}_{\alpha (d_i,q)}$ is a normal subgroup of $\mathbb {Z}_{d_i} \times \mathrm {Sym}_{\alpha (d_i,q)}$ with quotient group $\mathbb {Z}_{d_i} \times \mathbb {Z}_2$. Hence, there is a normal subgroup $N_{d_i}$ of $\mathbb {Z}_{d_i} \wr \mathrm {Sym}_{\alpha (d_i, q)}$ with quotient isomorphic to $\mathbb {Z}_{d_i} \times \mathbb {Z}_2$. Therefore, $N_{d_1} \times \dots \times N_{d_\ell }$ is a normal subgroup of W with quotient isomorphic to

$$\begin{aligned} Q := (\mathbb {Z}_{d_1} \times \mathbb {Z}_2) \times \dots \times (\mathbb {Z}_{d_\ell } \times \mathbb {Z}_2) \times \mathbb {Z}_2. \end{aligned}$$

If n is odd, then $\gcd (2,d_i) = 1$ for all i, so

$$\begin{aligned} Q \cong \mathbb {Z}_{2 d_1} \times \dots \times \mathbb {Z}_{2d_\ell } \times \mathbb {Z}_2, \end{aligned}$$

and $\mathrm {Rank}(Q) = \ell + 1 = \mathrm {d}(n)$ in this case. If n is even, suppose that $d_1, \dots , d_{e}$, with $e=\mathrm {d}_+(n)$, are all the even divisors of n. Hence,

$$\begin{aligned} Q \cong \mathbb {Z}_{d_1} \times \dots \times \mathbb {Z}_{d_{e}} \times \mathbb {Z}_{2 d_{e+1}} \times \dots \times \mathbb {Z}_{2d_{\ell }} \times (\mathbb {Z}_2)^{e + 1}, \end{aligned}$$

and $\mathrm {Rank}(Q) = \ell + e + 1 = \mathrm {d}(n) + \mathrm {d}_+(n)$. This gives the lower bound for the rank of W.

For the upper bound, we shall use the basic fact that $\mathrm {Rank}(G_1 \times G_2) \le \mathrm {Rank}(G_1) + \mathrm {Rank}(G_2)$, for any pair of groups $G_1$ and $G_2$. Assume first that n is not a power of 2 and let $d_\ell$ be an odd prime. Hence, $\mathrm {Rank}\left( (\mathbb {Z}_{d_\ell } \wr \mathrm {Sym}_{\alpha (d_\ell , q )}) \times \mathrm {Sym}_q \right) = 2$ by Lemma 7 (ii), and $\mathrm {Rank}(\mathbb {Z}_{d_i} \wr \mathrm {Sym}_{\alpha (d_i, q )}) = 2$ for all i by Lemma 5. Thus, $\mathrm {Rank}(W) \le 2\ell = 2\mathrm {d}(n) - 2$. If n is a power of 2, then $\mathrm {Rank}\left( (\mathbb {Z}_{2} \wr \mathrm {Sym}_{\alpha (2, q )}) \times \mathrm {Sym}_q \right) = 3$ by Lemma 7 (i), so $\mathrm {Rank}(W) \le 2\ell + 1 = 2\mathrm {d}(n) - 1$.

When $q=2$ and n is even, we may assume that $d_\ell = 2$, so $\mathrm {ICA}(\mathbb {Z}_n; A) \cong (\mathbb {Z}_{d_1} \wr \mathrm {Sym}_{\alpha (d_1,2)}) \times \dots \times (\mathbb {Z}_{d_{\ell -1}} \wr \mathrm {Sym}_{\alpha (d_{\ell -1} , 2 )}) \times (\mathbb {Z}_2)^2$. The rest of the proof is similar to the previous paragraphs. $\square$

Corollary 1

Let p be an odd prime and $k \ge 1$ an integer. Let A be a finite set of size $q \ge 2$. Then:

$$\begin{aligned} \mathrm {Rank}( \mathrm {ICA}(\mathbb {Z}_{2^kp}; A) ) = {\left\{ \begin{array}{ll} 4k + 1 &{}\quad \text {if }\quad q=2, \\ 4k + 2 &{}\quad \text {if }\quad q \ge 3. \end{array}\right. } \end{aligned}$$

Proof

This follows by Theorem 4 (i) because $\mathrm {d}(2^k p) - \mathrm {d}_+(2^k p) - 2 = 0$, so $\epsilon (2^k p,q) = 0$. $\square$

4 The relative rank of $\mathrm {ICA}(\mathbb {Z}_n ; A)$ in $\mathrm {CA}(\mathbb {Z}_n ; A)$

For any integer $n \ge 2$, define the divisibility digraph of n as the digraph with vertices $\mathcal {V} := \{ s \in [n] : s \mid n \}$ and edges $\mathcal {E} := \left\{ (s,t) \in \mathcal {V}^2 : t \mid s \right\}$. Denote $E(n) := \left| \mathcal {E} \right|$.

Lemma 8

Let $n \ge 2$. If $n =p_1^{a_1} p_2^{a_2} \dots p_m^{a_m}$, where $p_i$ are distinct primes, then

$$\begin{aligned} E(n) = \frac{1}{2^m}\prod _{i=1}^m (a_i + 1)(a_i+2). \end{aligned}$$

Proof

Note that the outdegree of any $s = p_1^{b_1} p_2^{b_2} \dots p_m^{b_m} \mid n$ is

$$\begin{aligned} \text {outdeg}(s) = (b_1 +1)(b_2 + 1) \dots (b_m +1). \end{aligned}$$

Therefore,

$$\begin{aligned} E(n)= & {} \sum _{s \mid n } \text {outdeg}(s) = \sum _{b_1 = 0}^{a_1} \dots \sum _{b_m = 0}^{a_m} (b_1 +1)(b_2 + 1) \dots (b_m +1) \\= & {} \frac{1}{2^m}\prod _{i=1}^m (a_i + 1)(a_i+2). \end{aligned}$$

$\square$

In the proof of the following result we shall use the notion of kernel of a transformation $\tau : A^n \rightarrow A^n$ as the partition of $A^n$ induced by the equivalence relation $\{ (x,y ) \in A^n \times A^n : (x)\tau = (y) \tau \}$.

Lemma 9

Let $n \ge 2$ be an integer and A a finite set of size $q \ge 2$. Then:

$$\begin{aligned} \mathrm {Rank}( \mathrm {CA}(\mathbb {Z}_n; A) : \mathrm {ICA}(\mathbb {Z}_n; A) ) = {\left\{ \begin{array}{ll} E(n) - 1 &{}\quad \text {if }\quad q=2 \text { and } n \in 2 \mathbb {Z}; \\ E(n) &{}\quad \text {otherwise.} \end{array}\right. } \end{aligned}$$

Proof

Let $\mathcal {O}$ be the set of orbits of $\sigma : A^n \rightarrow A^n$, as defined in Lemma 1. Let $d_1, \dots , d_\ell$ be all the divisors of n ordered as follows

$$\begin{aligned} 1 = d_1 < d_2 < \dots < d_{\ell -1} < d_\ell = n. \end{aligned}$$

For $1 \le i \le \ell$, let $\alpha _i := \alpha (d_i,q)$ and denote by $\mathcal {O}_i$ the subset of $\mathcal {O}$ of orbits of size $d_i$. Let

$$\begin{aligned} B_i := \bigcup _{P \in \mathcal {O}_i} P. \end{aligned}$$

Suppose that $q \ne 2$ or n is odd, so $\alpha _i \ge 2$ for all i. For any pair of divisors $d_j$ and $d_i$ such that $d_j \mid d_i$, fix $\omega _j \in B_j$ and $\omega _i \in B_i$ in distinct orbits. Denote the orbits that contains $\omega _i$ by $[\omega _i]$. Define idempotents $\tau _{i,j} \in \mathrm {CA}(\mathbb {Z}_n; A )$ in the following way:

$$\begin{aligned} (x)\tau _{i,j} := {\left\{ \begin{array}{ll} (\omega _{j}){\sigma ^k} &{}\quad \text { if }\quad x = (\omega _{i}){\sigma ^k} \\ x &{}\quad \text { if }\quad x \in A^n \setminus [\omega _i]. \end{array}\right. } \end{aligned}$$

Note that $\tau _{i,j}$ collapses $[\omega _i]$ to $[\omega _j]$ and fixes everything else.

We claim that

$$\begin{aligned} H:=\left\langle \mathrm {ICA}(\mathbb {Z}_n ; A), \tau _{i,j} : d_j \mid d_i \right\rangle = \mathrm {CA}(\mathbb {Z}_n ; A). \end{aligned}$$

Let $\xi \in \mathrm {CA}(\mathbb {Z}_n ; A)$. For $1 \le i \le \ell$, and define

$$\begin{aligned} (x)\xi _i := {\left\{ \begin{array}{ll} (x)\xi &{} \text { if }\quad x \in B_i \\ x &{} \text {otherwise}. \end{array}\right. } \end{aligned}$$

Clearly $\xi _i \in \mathrm {CA}(\mathbb {Z}_n; A)$. By Lemma 1, we have $(B_i)\xi \subseteq \bigcup _{j \le i }B_i$, so

$$\begin{aligned} \xi = \xi _1 \xi _2 \dots \xi _\ell . \end{aligned}$$

We shall prove that $\xi _i \in H$ for all $1 \le i \le \ell$. For each i, decompose $B_i = B_i^{\prime } \cup B_i^{\prime \prime }$, where

$$\begin{aligned} B_i^\prime&= \bigcup \left\{ P \in \mathcal {O}_i : (P)\xi _i \subseteq B_j \text { for some } j <i \right\} , \\ B_i^{\prime \prime }&= \bigcup \left\{ P \in \mathcal {O}_i : (P)\xi _i \subseteq B_i \right\} . \end{aligned}$$

If $\xi ^\prime _i$ and $\xi ^{\prime \prime }_i$ are the transformations that act as $\xi _i$ on $B_i^\prime$ and $B_i^{\prime \prime }$, respectively, and fix everything else, then $\xi _i = \xi _i^{\prime } \xi _{i}^{\prime \prime }$.

• 1. We show that $\xi _i^{\prime } \in H$. For any orbit $P \subseteq B_i^\prime$, the orbit $Q:= (P)\xi _i^\prime$ is contained in $B_j$ for some $j<i$. By Lemma 4, there is $\phi \in \mathrm {Sym}_{\alpha _i} \times \mathrm {Sym}_{\alpha _j} \le \mathrm {ICA}(\mathbb {Z}_n;A)$ such that $\phi _s$ acts as the double transposition $( [\omega _i] , P_s) ([\omega _j] , Q_s)$, and

  $$\begin{aligned} (P) \xi _i^\prime = (P)\phi ^{-1} \tau _{i, j} \phi . \end{aligned}$$

  As $\xi _i^\prime$ may be decomposed as a product of transformations that only move one orbit in $B_i^\prime$, the above equality implies that $\xi _i^\prime \in H$.

• 2. We show that $\xi _{i}^{\prime \prime } \in H$. In this case, $\xi _i^{\prime \prime } \vert _{B_i} \in \mathrm {Tran}(B_i)$. In fact, as $\xi _i^{\prime \prime }$ preserves the partition of $B_i$ into orbits, $\xi _i^{\prime \prime } \vert _{B_i} \in \langle \sigma \vert _{B_i} \rangle \wr \mathrm {Tran}_{\alpha _i}$. As $\alpha _i \ge 2$, the semigroup $\mathrm {Tran}_{\alpha _i}$ is generated by $\mathrm {Sym}_{\alpha _i} \le \mathrm {ICA}(\mathbb {Z}_n;A)$ together with the idempotent $\tau _{i, i}$. Hence, $\xi _i^{\prime \prime } \in H$.

This establishes that the relative rank of $\mathrm {ICA}(\mathbb {Z}_n ; A)$ in $\mathrm {CA}(\mathbb {Z}_n ; A)$ is at most E(n).

For the converse, suppose that

$$\begin{aligned} \left\langle \mathrm {ICA}(\mathbb {Z}_n ; A), U \right\rangle = \mathrm {CA}(\mathbb {Z}_n ; A), \end{aligned}$$

where $\vert U \vert < E(n)$. Hence, we may assume that, for some $d_j \mid d_i$,

$$\begin{aligned} U \cap \langle \mathrm {ICA}(\mathbb {Z}_n; A) , \tau _{i, j} \rangle = \emptyset . \end{aligned}$$

(5)

By Lemma 1, there is no $\tau \in \mathrm {CA}(\mathbb {Z}_n ; A)$ such that $(X) \tau \subseteq Y$ for $X \in \mathcal {O}_a$, $Y \in \mathcal {O}_b$ with $d_b \not \mid d_a$. This, together with (5), implies that U has no element with kernel of the form

$$\begin{aligned} \left\{ \{ x,y \}, \{ z \} : x \in P, y \in Q, z \in A^n \setminus (P \cup Q) \right\} \end{aligned}$$

for any $P \in \mathcal {O}_i$, $Q \in \mathcal {O}_j$. Thus, there is no element in $\left\langle \mathrm {ICA}(\mathbb {Z}_n ; A), U \right\rangle$ with kernel of such form, which is a contradiction (because $\tau _{i,j}\in \mathrm {CA}(\mathbb {Z}_n ; A)$ has indeed this kernel).

The case when $q=2$ and n is even follows similarly, except that now, as there is a unique orbit of size 2 in $\mathcal {O}$, there is no idempotent $\tau _{2,2}$. $\square$

Finally, Theorems 1 and 2 follow by Theorem 4 and Lemmas 3, 7, 8 and 9.