Group representations that resist random sampling. Issue 3 (9th June 2014) - Lovett, Shachar; Moore, Cristopher; Russell, Alexander
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 <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj2f9tvbmw" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />g1, …, gt∈Gn</alternatives> has operator norm 1 with probability approaching 1 as <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj2f9tvbkb" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />n→∞</alternatives>. More quantitatively, we show that there exist families of finite groups for which <alternatives><inline-graphic mimetype="image" xlink:href="ark:/27927/pgj2f9tvbqj" xlink:type="simple" xmlns:xlink="http://www.w3.org/1999/xlink" />Ω(loglog|G|)</alternatives> 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