paper

On the Complexity of the Cogrowth Sequence

arXiv:1805.08118

Abstract

Given a finitely generated group with generating set $S$ , we study the \emph{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.

10 pages