The true complexity of a system of linear equations

By William T. Gowers, Julia Wolf. 2007

100 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Discrete Mathematics and Combinatorics, Electrical and Electronic Engineering

View Paper: https://www.semanticscholar.org/paper/b4931a4536f4acefc2d4b7fcdc7bc6dc0f2eb0d3

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Discrete Mathematics and Combinatorics

In Electrical and Electronic Engineering

Citations in the corpus

An Arithmetic Regularity Lemma, An Associated Counting Lemma, and Applications (2010, background): “n joint work). A counterexample example of Ruzsa in the appendix to [4] shows that Theorem 1.12 fails when k> 5. Finally, in §7, we establish a generalisation of a recent result of Gowers and Wolf [20, 21, 22] regarding the “true” complexity of a system of linear forms. Theorem 1.13. Let Ψ = (ψ1,”
Pointwise ergodic theorems for non-conventional bilinear polynomial averages (2020, background): “ibility of the minor arc contribution; in the language of additive combinatorics, this re ects the fact that the pattern (x;x n;x P(n)) has \true complexity zero" in the sense of Gowers and Wolf [34]. Is there some analogue of these methods that can cover patterns of higher complexity? A natura”
Decompositions, approximate structure, transference, and the Hahn–Banach theorem (2008, methodology): “A special case of this result was proved in [9] using ‘quadratic Fourier analysis’, which we shall discuss in Subsection 2.”
The Inverse Conjecture for the Gowers Norm over Finite Fields in Low Characteristic (2011, unknown): “9 to compute the true complexity of a system (a concept introduced in [14]) of linear equations in sufficiently high characteristic.”
Linear Forms and Higher-Degree Uniformity for Functions On $${\mathbb{F}^{n}_{p}}$$ (2010, methodology): “2 was proved by Leibman [Lei07] independently of our work in [GW09a] and at about the same time.”
Finite configurations in sparse sets (2013, background): “In the particular case of 3-term arithmetic progressions, the appropriate conditions take a Fourier analytic form [29]; a more recent (and much deeper) result is that Fourier analytic conditions can also be used to control more general finite configurations of “true complexity” [10].”