Friday, April 1, 2011
3:30 pm, MC 5158

Cris Moore
University of New Mexico and the Santa Fe Institute

Approximate Representations and Approximate Homomorphisms

Approximate algebraic structures play a defining role in arithmetic combinatorics. I will discuss approximate representations of finite groups: functions from G to the unitary group U(d) that act like homomorphisms within some error. We bound the expected error in terms of d/d_min, where d_min is the dimension of the smallest nontrivial genuine representation of G. As an application, we bound the extent to which a function f from G to another finite group H can be an approximate homomorphism. We show that if H's representations are significantly smaller than G's, no such f can be "much more homomorphic" than a random function.
We interpret these results as showing that if G is quasirandom, that is, if d_min is large, then G cannot be embedded in a small number of dimensions, or in a less-quasirandom group, without significant distortion of G's multiplicative structure. We also prove that our bounds are tight by showing that minors of genuine representations and their polar decompositions are essentially optimal approximate representations.

This is joint work with Alex Russell of the University of Connecticut.