Journal of Combinatorial Algebra


Full-Text PDF (273 KB) | Metadata | Table of Contents | JCA summary
Volume 1, Issue 2, 2017, pp. 127–144
DOI: 10.4171/JCA/1-2-1

Published online: 2017-04-06

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

Scott Garrabrant[1] and Igor Pak[2]

(1) UCLA, Los Angeles, USA
(2) UCLA, Los Angeles, USA

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

Keywords: Cogrowth sequence of groups, probability of return, P-recursive sequences, linear groups, finite state automata

Garrabrant Scott, Pak Igor: Words in linear groups, random walks, automata and P-recursiveness. J. Comb. Algebra 1 (2017), 127-144. doi: 10.4171/JCA/1-2-1