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 Ak, 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⊂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 An.
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 α,β and γ, then as long as αβγ>m−1 there exist x∈A, y∈B and z∈C such that xy=z. In particular, when G is the alternating group An, we have m=n−1 (when n≥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(logn)7/2, which is best possible up to the log factor. More generally, it shows that if A, B and C are subsets of An of densities α, β and γ, and if all of αβ, βγ and αγ are at least Cn−1(logn)7, then the probability that a random triple (x,y,z) with xy=z belongs to A×B×C is at least αβγ(1−c), where c→0 as C→∞.
The rather remarkable proof uses a sophisticated combination of ideas and tools, from Fourier analysis to geometric inequalities and novel concentration of measure arguments.