Group representations that resist random sampling. Issue 3 (9th June 2014) - Lovett, Shachar
Abstract We show that there exists a family of groups Gn and nontrivial irreducible representations ρn such that, for any constant t, the average of ρn over t uniformly random elements g1, …, gt∈Gn has operator norm 1 with probability approaching 1 as n→∞. More quantitatively, we show that there exist families of finite groups for which Ω(loglog|G|) random elements are required to bound the norm of a typical representation below 1. This settles a conjecture of A. Wigderson. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 605–614, 2015