{
  "id": "1805.08118",
  "version": "v1",
  "published": "2018-05-21T15:29:53.000Z",
  "updated": "2018-05-21T15:29:53.000Z",
  "title": "On the Complexity of the Cogrowth Sequence",
  "authors": [
    "Jason Bell",
    "Marni Mishna"
  ],
  "comment": "20 pages",
  "categories": [
    "math.CO"
  ],
  "abstract": "Given a finitely generated group with generating set $S$, we study the cogrowth sequence, which is the number of words of length $n$ over the alphabet $S$ that are equal to one. This is related to the probability of return for walks in a Cayley graph with steps from $S$. We prove that the cogrowth sequence is not P-recursive when $G$ is an amenable group of superpolynomial growth, answering a question of Garrabant and Pak. In addition, we compute the cogrowth for certain infinite families of free products of finite groups and free groups, and prove that a gap theorem holds: if $S$ is a finite symmetric generating set for a group $G$ and if $a_n$ denotes the number of words of length $n$ over the alphabet $S$ that are equal to $1$ then either $\\limsup_n a_n^{1/n} \\le 2$ or $\\limsup_n a_n^{1/n} \\ge 2\\sqrt{2}$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2018-05-21T15:29:53.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05A05",
      "05A15",
      "20F10"
    ],
    "keywords": [
      "cogrowth sequence",
      "complexity",
      "gap theorem holds",
      "finite symmetric generating set",
      "cayley graph"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 20,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}