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.
Alin Bostan, Lucia Di Vizio, Kilian Raschel
