Ranks of finite semigroups of one-dimensional cellular automata (Q343476)

A cellular automaton over a group \(G\) and a set \(A\) is a mapping \(A^G\to A^G\) which is determined by the action of \(G\) on itself by right multiplication within a fixed finite neighborhood. Such cellular automata constitute a semigroup \(\mathrm{CA}(G;A)\) under composition of mappings. When both \(G\) and \(A\) are finite, which is the case of interest in the paper, \(\mathrm{CA}(G;A)\) is the centralizer of a certain set of transformations of \(A^G\). The aim of the paper is to compute the rank, in the sense of the minimum cardinality of a generating set, for the semigroups \(\mathrm{CA}(G;A)\) when \(G=\mathbb{Z}_n\) is a cyclic group. Explicit formulas are established when \(n\) is a prime, a power of 2, or a power of 2 times a prime, while lower and upper bounds are given in the general case.