Higher-order Fourier analysis with applications to additive combinatorics and theoretical computer science

Abstract

Fourier analysis has been used for over one hundred years as a tool to study certain additive patterns. For example, Vinogradov used Fourier-analytic techniques (known in this context as the Hardy-Littlewood circle method) to show that every sufficiently-large odd integer can be written as the sum of three primes, while van der Corput similarly showed that the primes contain infinitely-many three-term arithmetic progressions.

Over the past two decades, a theory of higher-order Fourier analysis has been developed to study additive patterns which are not amenable to classical Fourier-analytic techniques. For example, while three-term arithmetic progressions can be studied with Fourier analysis, all longer arithmetic progressions require higher-order techniques. These techniques have led to a new proof of Szemerédi's theorem in addition to results such as counts of k-term arithmetic progressions in the primes.

This thesis contains five results in the field of higher-order Fourier analysis. In the first half, we use these techniques to give applications in additive combinatorics and theoretical computer science. We prove an induced arithmetic removal lemma first in complexity 1 and then for patterns of all complexities. This latter result solves a central problem in property testing known as the classification of testable arithmetic properties. We then study a class of multidimensional patterns and show that many of them satisfy the popular difference property analogously to the one-dimensional case. However there is a surprising spectral condition which we prove necessarily appears in higher dimensions that is not present in the one-dimensional problem.

In the second half of this thesis, we further develop the foundations of higher-order Fourier analysis. We determine the set of higher-order characters necessary over [mathematical notation], showing that classical polynomials suffice in the inverse theorem for the Gowers Uᵏ-norm when k≤p+1, but that non-classical polynomials are necessary whenever k>p+1. Finally, we prove the first quantitative bounds on the U⁴-inverse theorem in the low-characteristic regime p<5.