Quantum expanders and growth of group representations

Abstract

Let $\pi$ be a finite dimensional unitary representation of a group $G$ with a generating symmetric $n$-element set $S\subset G$. Fix $\vp>0$. Assume that the spectrum of $|S{|}^{-1}{\sum }_{s\in S}\pi (s)\otimes \overline{\pi (s)}$ is included in $ [-1, 1-\vp]$ (so there is a spectral gap $\ge \vp$). Let $r_N^{\prime }(\pi )$ be the number of distinct irreducible representations of dimension $\le N$ that appear in $\pi$. Then let $R_{n,\vp}'(N)=\sup r'_N(π)$ where the supremum runs over all $\pi$ with ${n,\vp}$ fixed. We prove that there are positive constants $δ_\vp$ and $c_\vp$ such that, for all sufficiently large integer $n$ (i.e. $n\ge n_0$ with $n_0$ depending on $\vp$) and for all $N\ge 1$, we have $\exp{δ_\vp nN^2} \le R'_{n,\vp}(N)\le \exp{c_\vp nN^2}$. The same bounds hold if, in $r_N^{\prime }(\pi )$, we count only the number of distinct irreducible representations of dimension exactly $=N$.

Main addition: A remark due to Martin Kassabov showing that the numbers R(N) grow faster than polynomial. v3: Minor clarifications