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.

Abstract

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