On the complexity of the cogrowth sequence
Jason P. Bell, Marni Mishna · Journal of Combinatorial Algebra · 2020
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.