Proceedings of the London Mathematical Society Advance Access published online on June 20, 2009
Proceedings of the London Mathematical Society, doi:10.1112/plms/pdp019
© 2009 London Mathematical Society
The true complexity of a system of linear equations
Department of Pure Mathematics and Mathematical Statistics
Wilberforce Road, Cambridge
CB3 0WB
United Kingdom
w.t.gowers@dpmms.cam.ac.uk
Department of Pure Mathematics and Mathematical Statistics
Wilberforce Road, Cambridge
CB3 0WB
United Kingdom
Current address:
Institute for Advanced Study
School of Mathematics
Einstein Drive, Princeton NJ 08540
USA
Received 2 November 2007. Revision received 10 March 2009.
In this paper we look for conditions that are sufficient to guarantee that a subset A of a finite Abelian group G contains the ‘expected’ number of linear configurations of a given type. The simplest non-trivial result of this kind is the well-known fact that if G has odd order, A has density 
and all Fourier coefficients of the characteristic function of A are significantly smaller than (except the one at zero, which equals ), then A contains approximately 3|G|2 triples of the form (a, a+d, a+2d). This is ‘expected’ in the sense that a random set A of density has approximately 3|G|2 such triples with very high probability. More generally, it was shown by the first author (in the case G = 
N for N prime, but the proof generalizes) that a set A of density has about k|G|2 arithmetic progressions of length k if the characteristic function of A is almost as small as it can be, given its density, in a norm that is now called the Uk–1-norm. When investigating linear equations in the primes, Green and Tao found the most general statement that follows from the technique used to prove this result, introducing a notion that they call the complexity of a system of linear forms. They prove that if A has almost minimal Uk+1-norm, then it has the expected number of linear configurations of a given type, provided that the associated complexity is at most k. The main result of this paper is that the converse is not true: in particular there are certain systems of complexity 2 that are controlled by the U2-norm, whereas the result of Green and Tao requires the stronger hypothesis of U3-control. We say that a system of m linear forms L1, ..., Lm in d variables with integer coeffcients has true complexity k if k is the smallest positive integer such that, for any set A of density and almost minimal Uk+1-norm, the number of d-tuples (x1, ..., xd) such that Li(x1, ..., xd) 
A for every i is approximately m|G|d. We conjecture that the true complexity k is the smallest positive integer s for which the functions L
, ... ,L
are linearly independent. Using the ‘quadratic Fourier analysis’ of Green and Tao we prove this conjecture in the case where the complexity of the system (in Green and Tao's sense) is 2, s=1 and G is the group 
for some fixed odd prime p. A closely related result in ergodic theory was recently proved independently by Leibman. We end the paper by discussing the connections between his result and ours.
2000 Mathematics Subject Classification 11T24, 11B25, 37A45.