The true complexity of a system of linear equations

W. T. Gowers*, J. Wolf

*Corresponding author for this work

Research output: Contribution to journalArticle (Academic Journal)peer-review

40 Citations (Scopus)

Abstract

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 alpha and all Fourier coefficients of the characteristic function of A are significantly smaller than alpha (except the one at zero, which equals alpha), then A contains approximately alpha(3)vertical bar G vertical bar(2) triples of the form (a, a+d, a+2d). This is 'expected' in the sense that a random set A of density alpha has approximately alpha(3)vertical bar G vertical bar(2) such triples with very high probability. More generally, it was shown by the first author (in the case G = Z(N) for N prime, but the proof generalizes) that a set A of density alpha has about alpha(k)vertical bar G vertical bar(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 U(k-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 U(k+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 U(2)-norm, whereas the result of Green and Tao requires the stronger hypothesis of U(3)-control. We say that a system of m linear forms L(1), ..., L(m) 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 alpha and almost minimal U(k+1)-norm, the number of d-tuples (x(1), ..., x(d)) such that L(i)(x(1), ..., x(d)) is an element of A for every i is approximately alpha(m)vertical bar G vertical bar(d). We conjecture that the true complexity k is the smallest positive integer s for which the functions L1s+1, ... ,Lms+1 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 F(pn) 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.

Original languageEnglish
Pages (from-to)155-176
Number of pages22
JournalProceedings of the London Mathematical Society
Volume100
Issue number1
DOIs
Publication statusPublished - Jan 2010

Keywords

  • ARITHMETIC PROGRESSIONS
  • THEOREM
  • SZEMEREDI
  • AVERAGES
  • PROOF

Cite this