Product mixing in the alternating group

Product mixing in the alternating group, Discrete Analysis 2016:2, 18 pp.

Growth and mixing of subsets of groups is a major theme in group theory. The former concerns lower bounds for the sizes of product sets, especially of the form $A^k$, where $A$ is some set of generators. The latter concerns the number of times that the characteristic function of $A$ must be convolved with itself before it becomes approximately a constant function, or in more probabilistic language, the time it takes for random walks on Cayley graphs to become uniformly distributed. More generally, one can ask similar “off-diagonal” questions about sizes of product sets or of convolutions of functions when the sets or functions are not necessarily the same.

One problem that fits naturally into this theme is to determine the largest size of a product-free subset of a finite group $G$ – that is, the size of the largest $A\subset G$ that does not contain $x,y,z$ with $xy=z$. For Abelian groups it is not hard to prove that it is always possible to find a product-free subset of size proportional to that of the whole group, but simple constructions do not exist for general finite groups, leading Babai and Sós to ask in 1985 whether the maximum size could be significantly smaller, and to suggest that it probably could for natural sequences of groups such as the alternating groups $A_n$.

A general result of Gowers shows that the density of the largest product-free subset is at most $Cm^{-1/3}$, where $m$ is the smallest dimension of an irreducible representation of $G$. More generally, if $A,B$ and $C$ are three sets of density $\alpha, \beta$ and $\gamma$, then as long as $\alpha\beta\gamma>m^{-1}$ there exist $x\in A$, $y\in B$ and $z\in C$ such that $xy=z$. In particular, when $G$ is the alternating group $A_n$, we have $m=n-1$ (when $n\geq 6$), so the largest product-free set has density at most $Cn^{-1/3}$. The proofs of these results are not difficult.

This paper improves the bound to $n^{-1/2}(\log n)^{7/2}$, which is best possible up to the log factor. More generally, it shows that if $A$, $B$ and $C$ are subsets of $A_n$ of densities $\alpha$, $\beta$ and $\gamma$, and if all of $\alpha\beta$, $\beta\gamma$ and $\alpha\gamma$ are at least $Cn^{-1}(\log n)^7$, then the probability that a random triple $(x,y,z)$ with $xy=z$ belongs to $A\times B\times C$ is at least $\alpha\beta\gamma(1-c)$, where $c\to 0$ as $C\to\infty$.

The rather remarkable proof uses a sophisticated combination of ideas and tools, from Fourier analysis to geometric inequalities and novel concentration of measure arguments.