{
  "id": "2403.11148",
  "version": "v1",
  "published": "2024-03-17T08:55:35.000Z",
  "updated": "2024-03-17T08:55:35.000Z",
  "title": "The word problem and growth of groups",
  "authors": [
    "Ievgen Bondarenko"
  ],
  "comment": "14 pages",
  "categories": [
    "math.GR",
    "cs.FL"
  ],
  "abstract": "Let $\\mathrm{WP}_G$ denote the word problem in a finitely generated group $G$. We consider the complexity of $\\mathrm{WP}_G$ with respect to standard deterministic Turing machines. Let $\\mathrm{DTIME}_k(t(n))$ be the complexity class of languages solved in time $O(t(n))$ by a Turing machine with $k$ tapes. We prove that $\\mathrm{WP}_G\\in\\mathrm{DTIME}_1(n\\log n)$ if and only if $G$ is virtually nilpotent. We relate the complexity of the word problem and the growth of groups by showing that $\\mathrm{WP}_G\\not\\in \\mathrm{DTIME}_1(o(n\\log\\gamma(n)))$, where $\\gamma(n)$ is the growth function of $G$. We prove that $\\mathrm{WP}_G\\in\\mathrm{DTIME}_k(n)$ for strongly contracting automaton groups, $\\mathrm{WP}_G\\in\\mathrm{DTIME}_k(n\\log n)$ for groups generated by bounded automata, and $\\mathrm{WP}_G\\in\\mathrm{DTIME}_k(n(\\log n)^d)$ for groups generated by polynomial automata. In particular, for the Grigorchuk group, $\\mathrm{WP}_G\\not\\in\\mathrm{DTIME}_1(n^{1.7674})$ and $\\mathrm{WP}_G\\in\\mathrm{DTIME}_1(n^2)$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2024-03-17T08:55:35.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "20F10",
      "68Q70",
      "03D10",
      "20E08"
    ],
    "keywords": [
      "word problem",
      "standard deterministic turing machines",
      "strongly contracting automaton groups",
      "growth function",
      "grigorchuk group"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 14,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}