{
  "id": "1901.02808",
  "version": "v1",
  "published": "2019-01-09T16:27:31.000Z",
  "updated": "2019-01-09T16:27:31.000Z",
  "title": "Bounding the minimal number of generators of groups of cellular automata",
  "authors": [
    "Alonso Castillo-Ramirez",
    "Miguel Sanchez-Alvarez"
  ],
  "comment": "12 pages",
  "categories": [
    "math.GR",
    "cs.FL"
  ],
  "abstract": "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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2019-01-09T16:27:31.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "68Q80",
      "05E18",
      "20M20"
    ],
    "keywords": [
      "cellular automata",
      "minimal number",
      "generators",
      "infinite group",
      "infinite abelian group"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 12,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}