The true complexity of a system of linear equations
by
Julia Wolf
Institute for Advanced Study
Coauthors: W.T. Gowers

Szemeredi’s Theorem states that any sufficiently dense subset of the integers contains arbitrarily long arithmetic progressions, and as such forms a crucial ingredient in Green and Tao’s celebrated result on long arithmetic progressions in the primes.

At the heart of the analytic proof of Szemeredi’s Theorem lies the fact that if a subset A of a finite Abelian group G satisfies a quasi-randomness property called ”uniformity of degree k”, then it contains roughly the ”expected” number of arithmetic progressions of length k + 2. (By the ”expected” number we mean the number of progressions one would expect in a random subset of G of the same density as A.)

One is naturally led to ask which degree of uniformity is required of A in order to control the number of solutions to a general system of linear equations. Using so-called "quadratic" Fourier analysis, we show that certain linear systems that were previously thought to require higher-degree control are in fact governed by degree 1 uniformity (that is, ordinary Fourier analysis). Moreover, we give a precise classification of such systems according to a simple and easily verifiable criterion.

We shall also outline the connections with recent develop ments in ergodic theory, in particular the work of Host and Kra and Leibman.

The talk aims to be accessible to a general audience, and covers joint work with Tim Gowers.

Date received: May 30, 2008