Bounding the minimal number of generators of groups of cellular automata

Alonso Castillo-Ramirez, Miguel Sanchez-Alvarez

Published 2019-01-09Version 1

For a group $G$ and a finite set $A$, denote by $\text{ICA}(G;A)$ the group of all invertible cellular automata over $A^G$. We study the minimal cardinality of a generating set, known as the rank, of $\text{ICA}(G;A)$. In the first part, when $G$ is a finite group, we give upper bounds for the rank in terms of the number of conjugacy classes of subgroups of $G$. The case when $G$ is a finite cyclic group has been studied before, so here we focus on the cases when $G$ is a finite dihedral group or a finite Dedekind group. In the second part, we find a basic lower bound for the rank of $\text{ICA}(G;A)$ when $G$ is a finite group, and we apply this to show that, for any infinite abelian group $H$, the group $\text{ICA}(H;A)$ is not finitely generated. The same is true for various kinds of infinite groups, so we ask if there exists an infinite group $H$ such that $\text{ICA}(H;A)$ is finitely generated.