The true complexity of a system of linear equations

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 α 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 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 𝔽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.

Locations

• Proceedings of the London Mathematical Society - View
• arXiv (Cornell University) - View - PDF
• HAL (Le Centre pour la Communication Scientifique Directe) - View
• DataCite API - View