Approximate representations, approximate homomorphisms, and low-dimensional embeddings of groups

DOI10.1137/140958578zbMATH Open1327.05340arXiv1009.6230OpenAlexW2015590395MaRDI QIDQ3453573FDOQ3453573

Authors: Cristopher Moore, Alexander Russell 

Publication date: 27 November 2015

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/1009.6230

Recommendations

• Inverse and stability theorems for approximate representations of finite groups
• Approximate homomorphisms. II: Group homomorphisms
• Worst-case approximability of functions on finite groups by endomorphisms and affine maps
• On approximate group homomorphisms
• Group representations that resist random sampling

zbMATH Keywords

stability theoryadditive combinatoricsquasirandom groupshomomorphism testinglow-dimensional embeddings

Mathematics Subject Classification ID

Combinatorial aspects of representation theory (05E10)

Cited In (8)

• Approximate homomorphisms. II: Group homomorphisms
• Inverse and stability theorems for approximate representations of finite groups
• The lower and upper approximations and homomorphisms between lower approximations in quotient groups
• Locally bounded finally precontinuous finite-dimensional quasirepresentations of connected locally compact groups
• Approximate homomorphisms between the Boolean cube and groups of prime order
• Generalizations of Fourier analysis, and how to apply them
• Title not available (Why is that?)
• Approximate symmetries of Hamiltonians

This page was built for publication: Approximate representations, approximate homomorphisms, and low-dimensional embeddings of groups

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3453573)