Approximate Representations and Approximate Homomorphisms

Understand

Approximate algebraic structures play a defining role in arithmetic combinatorics and have found remarkable applications to basic questions in number theory and pseudorandomness.

• Here we study approximate representations of finite groups: functions f:G -> U_d such that Pr[f(xy) = f(x) f(y)] is large, or more generally Exp_{x,y} ||f(xy) - f(x)f(y)||^2$ is small, where x and y are uniformly random elements of the group G and U_d denotes the unitary group of degree d.
• We bound these quantities in terms of the ratio d / d_min where d_min is the dimension of the smallest nontrivial representation of G.
• As an application, we bound the extent to which a function f : G -> H can be an approximate homomorphism where H is another finite group.