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

### Scott Garrabrant

UCLA, Los Angeles, USA### Igor Pak

UCLA, Los Angeles, USA

## 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.

## Cite this article

Scott Garrabrant, Igor Pak, Words in linear groups, random walks, automata and P-recursiveness. J. Comb. Algebra 1 (2017), no. 2, pp. 127–144

DOI 10.4171/JCA/1-2-1