On the complexity of the cogrowth sequence

On the complexity of the cogrowth sequence

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.

This talk will survey the connections between the structure of the group, and properties of the cogrowth sequence. We will then show that the cogrowth sequence is not P-recursive when G is an amenable group of superpolynomial growth, answering a question of Garrabant and Pak. In addition, we compute the exponential growth of the cogrowth sequence for certain infinite families of free products of finite groups and free groups, and prove that a gap theorem holds: if S is a finite symmetric generating set for a group G and if a(n) denotes the number of words of length n over the alphabet S that are equal to 1, then limsup_n a(n)^(1/n) is either less than or equal to 2, or greater than or equal to 2 sqrt(2). Work in collaboration with Jason Bell.