Combinatorics Seminar
When: Sunday, March 18, 10am
Where: Schreiber 309
Speaker: Doron Puder, Hebrew University
Title: Uniform Words are Primitive
Abstract:
Let G be a finite group, and let a,b,c,... be random elements of G, chosen
at uniform distribution. What is the distribution of the element obtained
by a fixed word in the letters a,b,c,..., such as ab,a^2, a^2bc^2b, or
aba^(-2)b^(-1)? More concretely, do these new random elements have uniform
distribution? In general, a free word w in the free group F_k is called
uniform if for every finite group G, the word map $w: G^k \to G$ induces
uniform distribution on G (given uniform distribution on G^k). So which
words are uniform? This question is strongly connected to the notion of
primitive words in the free group F_k. The word w is called primitive
if it belongs to some basis, i.e. a free generating set. It is an easy
observation that a primitive word is uniform. It was conjectured that the
converse is also true. We prove it for F_2, and more recently in a joint
work with O. Parzanchevski, we manage to prove the conjecture in full.
The symmetric group S_n plays a crucial role in the proof, and mostly
the average number of fixed points in a random permutation induced by
some fixed word w. Much of the talk will be dedicated to the translation
of the problem to a problem about random coverings of finite graphs.
I will try to define and explain all notions, as much as time
permits.