TR21-017 Authors: Timothy Gowers, Emanuele Viola

Publication: 19th February 2021 21:59

Downloads: 577

Keywords:

We initiate a systematic study of mixing in non-quasirandom groups.

Let $A$ and $B$ be two independent, high-entropy distributions over

a group $G$. We show that the product distribution $AB$ is statistically

close to the distribution $F(AB)$ for several choices of $G$ and

$F$, including:

(1) $G$ is the affine group of $2\times2$ matrices, and $F$ sets

the top-right matrix entry to a uniform value,

(2) $G$ is the lamplighter group, that is the wreath product of $\Z_{2}$

and $\Z_{n}$, and $F$ is multiplication by a certain subgroup,

(3) $G$ is $H^{n}$ where $H$ is non-abelian, and $F$ selects a

uniform coordinate and takes a uniform conjugate of it.

The obtained bounds for (1) and (2) are tight.

This work is motivated by and applied to problems in communication

complexity. We consider the 3-party communication problem of deciding

if the product of three group elements multiplies to the identity.

We prove lower bounds for the groups above, which are tight for the

affine and the lamplighter groups.