Higher-order Fourier analysis and applications

Arnab Bhattacharyya

Abstract

Regularity is a notion of 'pseudorandomness' that allows one to decompose a given object into a collection of simpler objects which appear random according to certain statistics. The famous regularity lemma of Szemeredi [Sze75, Sze78] says that any dense graph can be partitioned into a collection of bounded number of 'pseudorandom' bipartite graphs. The Szemeredi regularity lemma has numerous applications in combinatorics and property testing.

In a sequence of developments stemming from Gowers' proof of Szemeredi's theorem, Green and Tao introduced a notion of regularity for a collection of polynomials. Variants of these ideas were famously used by Green and Tao to prove that the primes contain arbitrarily long arithmetic progressions. Over finite fields, the theory extends previously used concepts in theoretical computer science, such as low-biased random variables and Fourier analysis over