On the Complexity of the Cogrowth Sequence

Jason Bell, Marni Mishna

Published 2018-05-21Version 1

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}$.