Group representations that resist random sampling

Publication date 13 November 2015

Abstract: We show that there exists a family of groups

G_{n}

and nontrivial irreducible representations

h o_{n}

such that, for any constant

t

, the average of

h o_{n}

over

t

uniformly random elements

g_{1}, l d o t s, g_{t} i n G_{n}

has operator norm

1

with probability approaching 1 as

n i g h t a r r o w i n f t y

. More quantitatively, we show that there exist families of finite groups for which

O m e g a (l o g l o g | G |)

random elements are required to bound the norm of a typical representation below

1

. This settles a conjecture of A. Wigderson.

Recommendations

Cites work

Cited in

(4)

This page was built for publication: Group representations that resist random sampling