The ab-normal reach of norm-al proofs in non-abelian Fourier analysis

Fourier analysis over (not necessarily abelian) groups is a cool proof technique that yields many results of interest to theoretical computer science. Often the goal is to show “mixing” or “pseudo/quasi randomness” of appropriate distributions. This post isn’t about the formal statements or applications or proofs or even the credit of these results; for some of this you can see e.g. the references below, or a survey of mine [Vio19], or a survey [Gow17] by Gowers.

Instead this post is about an uncanny development of the proofs of some of these results. Whereas the original proofs were somewhat complicated, in some cases involving heavy mathematical machinery, later there emerged proofs that I propose to call norm-al (or normal for simplicity) because they only involve manipulations that can be cast as norm inequalities, such as Cauchy-Schwarz. Normal proofs I view as just a little up in complexity from proofs that are simply opening up definitions. They can involve the latter, or norm inequalities, and they need not be tight. An example of an ab-norm-al proof would be one that involves induction or iterative arguments, or probabilistic/double-counting/pigeon-hole methods. Making this a little more precise seems to require a lot of discussion, and may not even be possible, so let me stop here and move on with the examples of the proofs which became norm-al. They all involve quasirandom groups [Gow08], but even non-quasirandom groups mix in a certain sense [GV22] and the proofs there are again norm-al (it’s just that I don’t know of earlier proofs in this case).

The first example concerns the quintessential mixing result in this area: If you’ve got independent distributions X and Y, and if each distribution is uniform over say a constant fraction of the group, then the the product XY (a.k.a. convolution, a.k.a. sample from each and output the product) is close to uniform over the entire group. A norm-al proof appears in [Gow17] which also contains pointers to previous proofs.

The second is mixing of three-term progressions. A norml-al proof appears in [BHR22]. From their abstract: “Surprisingly, unlike the proofs of Tao and Peluse, our proof is elementary and only uses basic facts from nonabelian Fourier analysis.”

The third is interleaved mixing, see a recent preprint with Derksen.

Moreover, in the second and third example the proofs are not only simpler, they are also more general in that they apply to any quasirandom group whereas previous proofs only applied to prominent special cases.

Why is all of this happening? One can only speculate that the reach of norml-al proofs in non-abelian Fourier analysis is still just emerging.

References

[BHR22]   Amey Bhangale, Prahladh Harsha, and Sourya Roy. Mixing of 3-term progressions in quasirandom groups. In Mark Braverman, editor, ACM Innovations in Theoretical Computer Science conf. (ITCS), volume 215 of LIPIcs, pages 20:1–20:9. Schloss Dagstuhl – Leibniz-Zentrum f�r Informatik, 2022.

[Gow08]    W. T. Gowers. Quasirandom groups. Combinatorics, Probability & Computing, 17(3):363–387, 2008.

[Gow17]    W. T. Gowers. Generalizations of Fourier analysis, and how to apply them. Bull. Amer. Math. Soc. (N.S.), 54(1):1–44, 2017.

[GV22]    W. T. Gowers and Emanuele Viola. Mixing in non-quasirandom groups. In ACM Innovations in Theoretical Computer Science conf. (ITCS), 2022.

[Vio19]    Emanuele Viola. Non-abelian combinatorics and communication complexity. SIGACT News, Complexity Theory Column, 50(3), 2019.