Given a finitely 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–85DOI 10.4171/JCA/39