Words in linear groups, random walks, automata and P-recursiveness

Abstract

Let $S$ be a generating set of a finitely generated group $G=⟨S⟩$. Denote by $a_n$ the number of words in $S$ of length $n$ that are equal to 1. We show that the cogrowth sequence $\{a_n\}$ is not always P-recursive. This is done by developing new combinatorial tools and using known results in computability and probability on groups.