On the complexity of the cogrowth sequence (Q2181189)

Summary: 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 \textit{S. Garrabrant} and \textit{I. Pak} [J. Comb. Algebra 1, No. 2, 127--144 (2017; Zbl 1422.20009)].