JournalsjcaVol. 4, No. 1pp. 73–85

On the complexity of the cogrowth sequence

  • Jason Bell

    University of Waterloo, Canada
  • Marni Mishna

    Simon Fraser University, Burnaby, Canada
On the complexity of the cogrowth sequence cover
Download PDF

A subscription is required to access this article.


Given a fi nitely generated group with generating set SS, we study the cogrowth sequence, which is the number of words of length nn over the alphabet SS that are equal to one. This is related to the probability of return for walks in a Cayley graph with steps from SS. We prove that the cogrowth sequence is not PP-recursive when GG 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