Approximate Representations, Approximate Homomorphisms, and Low-Dimensional Embeddings of Groups

Approximate algebraic structures play a defining role in additive number theory and have found remarkable applications to questions in theoretical computer science, including in pseudorandomness and probabilistically checkable proofs. Here we study approximate representations of finite groups: functions ψ : G → Ud such that [ψ(xy) = ψ(x) \,ψ(y)] is large or, more generally, such that the expected ₂ norm squared Ex,y \| ψ(xy) - ψ(x) \,ψ(y) \|₂² is small, where $x, y$ are uniformly random elements of the group G and Ud denotes the group of unitary operators on Cᵈ. We bound these quantities in terms of the ratio d / dₘᵢₙ where dₘᵢₙ 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. 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. These results demonstrate that if G is quasi-random in the sense of Gowers, that is, if dₘᵢₙ is large, then G cannot be embedded in a small number of dimensions, or in a less-quasi-random 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.