Mathematics – Representation Theory
Scientific paper
2010-09-30
Mathematics
Representation Theory
Scientific paper
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. 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.
Moore Cristopher
Russell Alexander
No associations
LandOfFree
Approximate Representations and Approximate Homomorphisms does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Approximate Representations and Approximate Homomorphisms, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Approximate Representations and Approximate Homomorphisms will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-244457