Words in linear groups, random walks, automata and P-recursiveness (Q528822): Difference between revisions

Summary: Let \(S\) be a generating set of a finitely generated group \(G = \langle S \rangle\). Denote by \(a_n\) the number of words in \(S\) of length \(n\) that are equal to 1. We show that the \textit{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.