科研之友
微信
新浪微博
Facebook
分享链接
摘要
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 psi : G -> U-d such that Pr[psi(xy) = psi(x) psi(y)] is large or, more generally, such that the expected l(2) norm squared E-x,E-y parallel to psi(xy) - psi(x) psi(y)parallel to(2)(2) is small, where x, y are uniformly random elements of the group G and U-d denotes the group of unitary operators on C-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. These results demonstrate that if G is quasi-random in the sense of Gowers, that is, if dmin 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.
- 出版日期2015
