Group representations that resist worst-case sampling

Abstract

Motivated by expansion in Cayley graphs, we show that there exist infinitely many groups $G$ with a nontrivial irreducible unitary representation whose average over every set of $o(\log \log |G|)$ elements of $G$ has operator norm $1-o(1)$. This answers a question of Lovett, Moore, and Russell, and strengthens their negative answer to a question of Wigderson. The construction is the affine group of ${\mathbb{F}}_p$ and uses the fact that for every $A\subset {\mathbb{F}}_p\setminus \{0\}$, there is a set of size $\exp (\exp (O(|A|)))$ that is almost invariant under both additive and multiplicatpive translations by elements of $A$.

arXiv comment4 pages