Group representations that resist random sampling

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

No reviews yet.

No comments yet.