Simple groups, interleaved products and conjectures of Gowers and Viola

Aner Shalev

Published 2016-01-05Version 1

We study the distribution of products of conjugacy classes in finite simple groups. Our results, combined with work of Gowers and Viola, lead to the solution of recent conjectures they posed on interleaved products and related complexity lower bounds, extending their work on the groups SL$(2,q)$ to all (nonabelian) finite simple groups. In particular it follows that, if $G$ is a finite simple group, and $A, B \subseteq G^2$ are subsets of fixed positive densities, then, as $a = (a_1,a_2) \in A$ and $b = (b_1,b_2) \in B$ are chosen uniformly, the interleaved product $a \bullet b := a_1b_1a_2b_2$ is almost uniform on $G$ with respect to the $\ell_{\infty}$-norm. It also follows that the communication complexity of an old decision problem related to interleaved products of $a, b \in G^t$ is at least $\Omega(t \log |G|)$ when $G$ is a finite simple group of Lie type of bounded rank, and at least $\Omega(t \log \log |G|)$ when $G$ is any finite simple group. Both these bounds are best possible.