Generating infinite monoids of cellular automata

Abstract

For a group $G$ and a set $A$, let $\text{End}(A^G)$ be the monoid of all cellular automata over $A^G$, and let $\text{Aut}(A^G)$ be its group of units. By establishing a characterisation of surjunctuve groups in terms of the monoid $\text{End}(A^G)$, we prove that the rank of $\text{End}(A^G)$ (i.e. the smallest cardinality of a generating set) is equal to the rank of $\text{Aut}(A^G)$ plus the relative rank of $\text{Aut}(A^G)$ in $\text{End}(A^G)$, and that the latter is infinite when $G$ has an infinite decreasing chain of normal subgroups of finite index, condition which is satisfied, for example, for any infinite residually finite group. Moreover, when $A=V$ is a vector space over a field $\mathbb{F}$, we study the monoid ${\text{End}}_{\mathbb{F}}(V^G)$ of all linear cellular automata over $V^G$ and its group of units ${\text{Aut}}_{\mathbb{F}}(V^G)$. We show that if $G$ is an indicable group and $V$ is finite-dimensional, then ${\text{End}}_{\mathbb{F}}(V^G)$ is not finitely generated; however, for any finitely generated indicable group $G$, the group ${\text{Aut}}_{\mathbb{F}}({\mathbb{F}}^G)$ is finitely generated if and only if $\mathbb{F}$ is finite.

11 pages

References in corpus (2)

• A counterexample to the unit conjecture for group rings
• On the minimal number of generators of endomorphism monoids of full shifts