Groupe de travail "Transcendance et combinatoire"

What do we know about the cogrowth sequence?

by Prof. Igor Pak (UCLA, Los Angeles)

Europe/Paris
amphithéâtre Darboux (Institut Henri Poincaré )

amphithéâtre Darboux

Institut Henri Poincaré

11 Rue Pierre et Marie Curie, 75005 Paris
Description

Take a group and a set of generators. Denote by a(n) the number of words in the generators with product 1 of length n (these are loops in the corresponding Cayley graph). The cogrowth sequence {a(n)} is the main object of our study. Turns out, it carries remarkably rich information about the group, as one considers arithmetic and asymptotic properties of a(n), as well as algebraic properties of the generating function for {a(n)}. In the first half of the talk I will review what is known about the problem from different points of view: combinatorics, group theory and computational complexity. In the second half, I will present our recent work on the subject (joint with David Soukup), where we obtain the first negative result for the cogrowth sequence of nilpotent groups in the most unexpected way. This talk is aimed at the general audience and no background will be assumed.

Organized by

Alin Bostan, Lucia Di Vizio, Kilian Raschel