# On the complexity of the cogrowth sequence

### Jason Bell

University of Waterloo, Canada### Marni Mishna

Simon Fraser University, Burnaby, Canada

## 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 Garrabrant and Pak.

## Cite this article

Jason Bell, Marni Mishna, On the complexity of the cogrowth sequence. J. Comb. Algebra 4 (2020), no. 1, pp. 73–85

DOI 10.4171/JCA/39