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 and , and if each distribution is uniform over say a constant fraction of the group, then the the product (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