{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:36:47Z","timestamp":1787323007618,"version":"build-2736575974"},"reference-count":15,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2015,1]]},"abstract":"<jats:p>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 \\to \\textsf{U}_d$ such that $\\Pr[\\psi(xy) = \\psi(x) \\,\\psi(y)]$ is large or, more generally, such that the expected $\\ell_2$ norm squared $\\mathbb{E}_{x,y} \\left\\| \\psi(xy) - \\psi(x) \\,\\psi(y) \\right\\|_2^2$ is small, where $x, y$ are uniformly random elements of the group $G$ and $\\textsf{U}_d$ denotes the group of unitary operators on $\\mathbb{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 \\to 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_{\\min}$ 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.<\/jats:p>","DOI":"10.1137\/140958578","type":"journal-article","created":{"date-parts":[[2015,1,29]],"date-time":"2015-01-29T09:38:10Z","timestamp":1422524290000},"page":"182-197","source":"Crossref","is-referenced-by-count":9,"title":["Approximate Representations, Approximate Homomorphisms, and Low-Dimensional Embeddings of Groups"],"prefix":"10.1137","volume":"29","author":[{"given":"Cristopher","family":"Moore","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alexander","family":"Russell","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2015,1,29]]},"reference":[{"key":"atypb1","doi-asserted-by":"crossref","unstructured":"L. Babai and K. Friedl,\n                      Approximate representation theory of finite groups\n                      , in 32nd Annual Symposium of Foundations of Computer Science, IEEE Computer Society Press, Los Alamitos, CA, 1991, pp. 733-742.","DOI":"10.1109\/SFCS.1991.185442"},{"key":"atypb2","unstructured":"L. Babai, K. Friedl, and A. Luka\u0301cs,\n                      Near Representations of Finite Groups\n                      , manuscript, 2003."},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1109\/18.556674"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20182"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(93)90044-W"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1007\/s11856-012-0050-z"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1955-0067841-7"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548307008826"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.27.4.222"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1007\/BF02761236"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1978-0507327-1"},{"key":"atypb12","doi-asserted-by":"crossref","unstructured":"J.P. Serre,\n                      Linear Representations of Finite Groups\n                      , Grad. Texts in Math. 42, Springer, New York, 1977.","DOI":"10.1007\/978-1-4684-9458-7"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1007\/BF02675591"},{"key":"atypb14","doi-asserted-by":"crossref","unstructured":"A. M. Turing,\n                      Finite Approximations to Lie Groups\n                      , Ann. Math. (2), 39 (1938), pp. 105-111.","DOI":"10.2307\/1968716"},{"key":"atypb15","unstructured":"S. M. Ulam,\n                      A Collection of Mathematical Problems\n                      , Interscience Publishers, New York, 1960."}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/140958578","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:36:48Z","timestamp":1787319408000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/140958578"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,1]]},"references-count":15,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2015,1]]}},"alternative-id":["10.1137\/140958578"],"URL":"https:\/\/doi.org\/10.1137\/140958578","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,1]]}}}