Group representations that resist random sampling

Abstract

We show that there exists a family of groups $G_n$ and nontrivial irreducible representations ${\rho }_n$ such that, for any constant $t$, the average of ${\rho }_n$ over $t$ uniformly random elements $g_1,\dots ,g_t\in G_n$ has operator norm $1$ with probability approaching 1 as $n\to \infty$. More quantitatively, we show that there exist families of finite groups for which $\Omega (\log \log |G|)$ random elements are required to bound the norm of a typical representation below $1$. This settles a conjecture of A. Wigderson.

Cited by in corpus (1)

• Eigenvalues of Cayley graphs