Quasirandom groups enjoy interleaved mixing

- Department of Mathematics, University of Michigan
- More about Harm Derksen

- Khoury College of Computer Sciences, Northeastern University
- More about Emanuele Viola

*Discrete Analysis*, September. https://doi.org/10.19086/da.84738.

### Editorial introduction

Quasirandom groups enjoy interleaved mixing, Discrete Analysis 2023:14, 4 pp.

In 1985 Babai and Sós asked whether there is a constant c>0 such that every group of order n>1 has a product-free subset of size at least cn, where this means a set A such that it is not possible to find a,b,c∈A with ab=c. A fairly straightforward argument shows that if the group is Abelian, then the answer is yes with c=3/7. (The constant comes from the fact that if the group is cyclic and n is even then the odd elements form a sum-free set of size n/2, while for odd n one can check that a suitable “middle third” of elements gives an example of size ⌊(n+1)/3⌋. These examples are best possible, and the smallest ratio happens to occur when n=7.) However, for general groups there is no obvious construction, and in a 2008 paper Gowers showed that the answer is in general negative. More precisely, he defined a d-*quasirandom group* to be a group with no non-trivial representation of dimension less than d, and proved that the largest product-free subset of a d-quasirandom group has cardinality O(nd−1/3). This, combined with the fact that d-quasirandom groups exist with arbitrarily large d (in fact, the group PSL2(q), which is of order roughly q3, is q-quasirandom, so one can take d to be of order of magnitude n1/3), gives the negative answer in a strong form.

In a later paper, motivated by an application to cryptography, Gowers and Viola (the second author of this paper) obtained an extension of the above result for the group G=SL2(q), and with less good bounds for all non-Abelian simple groups, which are quasirandom. (The bounds in the latter case were improved by Shalev.) In qualitative terms, their result stated that if t is a fixed positive integer and A and B are large subsets of Gt, and if we pick (a1,…,at) and (b1,…,bt) uniformly and independently at random from At and Bt, respectively, then the “interleaved product” a1b1a2b2…atbt is approximately uniformly distributed in the strong sense that the probability that for every x∈G the probability that it takes the value x is approximately 1/|G|.

The proof was somewhat complicated, as it required a detailed analysis of the conjugacy classes of SL2(q) and a use of the Lang-Weil theorem. In this paper, the authors give a much simpler proof, with the added benefit that it applies not just to SL2(q) and to non-Abelian simple groups, but to all quasirandom groups, with a good dependence on the quasirandomness parameter in all cases.

There have been various other cases of results first established for specific quasirandom groups, and only later proved for all quasirandom groups, usually with simpler arguments. It is a pleasant surprise each time this happens. The argument in this paper is a particularly good example of the phenomenon: indeed, it seems appropriate to say that it is the “book proof” of the result.