Quantum expanders and growth of group representations
Annales de la Faculté des sciences de Toulouse : Mathématiques, Série 6, Tome 26 (2017) no. 2, pp. 451-462.

Soit π une représentation unitaire de dimension finie d’un groupe G munie d’un ensemble générateur symétrique SG à n-éléments. Fixons ε>0 et supposons que le spectre de |S| -1 sS π(s)π(s) ¯ est inclus dans [-1,1-ε] (il y a donc un trou spectral ε). Soit r N ' (π) le nombre de représentations irréductibles distinctes de dimension N qui apparaissent dans la décomposition de π. Soit alors R n,ε ' (N)=supr N ' (π) où le sup court sur toutes les π possibles avec n,ε fixés. Nous démontrons l’existence de constantes positives δ ε et c ε telles que, pour tout entier n suffisamment grand (i.e. nn 0 ou n 0 peut dépendre de ε) et pour tout N1, on a expδ ε nN 2 R n,ε ' (N)expc ε nN 2 . Les mêmes bornes sont valables si, dans r N ' (π), on compte seulement le nombre de représentations irréductibles distinctes de dimension exactement =N.

Let π be a finite dimensional unitary representation of a group G with a generating symmetric n-element set SG. Fix ε>0. Assume that the spectrum of |S| -1 sS π(s)π(s) ¯ is included in [-1,1-ε] (so there is a spectral gap ε). Let r N ' (π) be the number of distinct irreducible representations of dimension N that appear in π. Then let R n,ε ' (N)=supr N ' (π) where the supremum runs over all π with n,ε fixed. We prove that there are positive constants δ ε and c ε such that, for all sufficiently large integer n (i.e. nn 0 with n 0 depending on ε) and for all N1, we have expδ ε nN 2 R n,ε ' (N)expc ε nN 2 . The same bounds hold if, in r N ' (π), we count only the number of distinct irreducible representations of dimension exactly =N.

Publié le :
DOI : https://doi.org/10.5802/afst.1541
@article{AFST_2017_6_26_2_451_0,
     author = {Pisier, Gilles},
     title = {Quantum expanders and growth of group representations},
     journal = {Annales de la Facult\'e des sciences de Toulouse : Math\'ematiques},
     pages = {451--462},
     publisher = {Universit\'e Paul Sabatier, Toulouse},
     volume = {Ser. 6, 26},
     number = {2},
     year = {2017},
     doi = {10.5802/afst.1541},
     language = {en},
     url = {http://www.numdam.org/articles/10.5802/afst.1541/}
}
Pisier, Gilles. Quantum expanders and growth of group representations. Annales de la Faculté des sciences de Toulouse : Mathématiques, Série 6, Tome 26 (2017) no. 2, pp. 451-462. doi : 10.5802/afst.1541. http://www.numdam.org/articles/10.5802/afst.1541/

[1] Bekka, Bachir; de la Harpe, Pierre; Valette, Alain Kazhdan’s property (T), New Mathematical Monographs, 11, Cambridge University Press, 2008, 486 pages

[2] Ben-Aroya, Avraham; Schwartz, Oded; Ta-Shma, Amnon Quantum expanders: motivation and construction, Theory Comput., Volume 6 (2010), pp. 47-79 (electronic) | Article

[3] Ben-Aroya, Avraham; Ta-Shma, Amnon Quantum expanders and the quantum entropy difference problem (2007) (https://arxiv.org/abs/quant-ph/0702129)

[4] Bourgain, Jean; Gamburd, Alex Uniform expansion bounds for Cayley graphs of SL 2 (F p ), Ann. Math., Volume 167 (2008) no. 2, pp. 625-642 | Article

[5] Ershov, Mikhail; Jaikin-Zapirain, Andrei Property (T) for noncommutative universal lattices, Invent. Math., Volume 179 (2010) no. 2, pp. 303-347 | Article

[6] de la Harpe, Pierre; Robertson, A. Guyan; Valette, Alain On the spectrum of the sum of generators for a finitely generated group, Isr. J. Math., Volume 81 (1993) no. 1–2, pp. 65-96 | Article

[7] Harrow, Aram W. Quantum expanders from any classical Cayley graph expander, Quantum Inf. Comput., Volume 8 (2008) no. 8–9, pp. 715-721

[8] Hastings, Matthew B. Random unitaries give quantum expanders, Phys. Rev. A, Volume 76 (2007) no. 3 (ID 032315, 11 pages) | Article

[9] Hastings, Matthew B.; Harrow, Aram W. Classical and quantum tensor product expanders, Quantum Inf. Comput., Volume 9 (2009) no. 3–4, pp. 336-360

[10] Hoory, Shlomo; Linial, Nathan; Wigderson, Avi Expander graphs and their applications, Bull. Am. Math. Soc., Volume 43 (2006) no. 4, pp. 439-561 | Article

[11] Kassabov, Martin Symmetric groups and expander graphs, Invent. Math., Volume 170 (2007) no. 2, pp. 327-354 | Article

[12] Kassabov, Martin Universal lattices and unbounded rank expanders, Invent. Math., Volume 170 (2007) no. 2, pp. 297-326 | Article

[13] Kassabov, Martin; Lubotzky, Alexander; Nikolov, Nikolay Finite simple groups as expanders, Proc. Natl. Acad. Sci. USA, Volume 103 (2006) no. 16, pp. 6116-6119 | Article

[14] Kassabov, Martin; Nikolov, Nikolay Cartesian products as profinite completions, Int. Math. Res. Not., Volume 2006 (2006) no. 20 (ID 72947, 17 pages)

[15] Larsen, Michael; Lubotzky, Alexander Representation growth of linear groups, J. Eur. Math. Soc., Volume 10 (2008) no. 2, pp. 351-390 | Article

[16] Lubotzky, Alexander Discrete groups, expanding graphs and invariant measures, Progress in Mathematics, 125, Birkhäuser, 1994, xi+195 pages

[17] Lubotzky, Alexander Expander graphs in pure and applied mathematics, Bull. Am. Math. Soc., Volume 49 (2012) no. 1, pp. 113-162 | Article

[18] Meshulam, Roy; Wigderson, Avi Expanders in group algebras, Combinatorica, Volume 24 (2004) no. 4, pp. 659-680 | Article

[19] Pisier, Gilles The volume of Convex Bodies and Banach Space Geometry, Cambridge Tracts in Mathematics, 94, Cambridge University Press, 1989, xv+250 pages

[20] Pisier, Gilles Quantum Expanders and Geometry of Operator Spaces, J. Eur. Math. Soc., Volume 16 (2014) no. 6, pp. 1183-1219 | Article

[21] Wang, P. S. On isolated points in the dual spaces of locally compact groups, Math. Ann., Volume 218 (1975), pp. 19-34 | Article

[22] Wassermann, Simon C * -algebras associated with groups with Kazhdan’s property T, Ann. Math., Volume 134 (1991) no. 2, pp. 423-431 | Article

[23] Wigderson, Avi lecture notes for the 22nd mcgill invitational workshop on computational complexity (Bellairs Institute Holetown, Barbados Lecturers: Ben Green and Avi Wigderson)