A Szemerédi-type regularity lemma in abelian groups, with applications

By Ben Joseph Green. 2003

274 citations recorded by the source corpus.

Abstract.Szemerédi’s regularity lemma is an important tool in graph theory which has applications throughout combinatorics. In this paper we prove an analogue of Szemerédi’s regularity lemma in the context of abelian groups and use it to derive some results in additive number theory. One is a structure theorem for sets which are almost sum-free. If $$A \subseteq \{1,\ldots,N\}$$ has δ N2 triples (a1, a2, a3) for which a1 + a2 = a3 then A = B ∪ C, where B is sum-free and |C| = δ′N, and $$\delta^{\prime} \rightarrow 0$$ as $$\delta \rightarrow 0.$$ Another answers a question of Bergelson, Host and Kra. If $$\alpha, \epsilon > 0,$$ if $$N\,>\,N_{0}(\alpha, \epsilon)$$ and if $$A \subseteq \{1,\ldots,N\}$$ has size α N, then there is some d ≠ 0 such that A contains at least $$(\alpha^{3}-\epsilon)N$$ three-term arithmetic progressions with common difference d.

Subfields: Discrete Mathematics and Combinatorics, Geometry and Topology

View Paper: https://www.semanticscholar.org/paper/0335c2ad004630f023a9a781b2369ad91dcc65c3

How researchers see this paper

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

In Discrete Mathematics and Combinatorics

In Geometry and Topology

Citations in the corpus

An Arithmetic Regularity Lemma, An Associated Counting Lemma, and Applications (2010, methodology): “This was previously considered in [23].”
The primes contain arbitrarily long arithmetic progressions (2004, background): “This is no coincidence: there is in fact a close connection between regularity lemmas such as those in [20], [22], [39] and ergodic theory of the type we have brushed up against in this paper.”
The growth rate of tri-colored sum-free sets (2016, background): “In particular, Green [16] proved an “arithmetic removal lemma” for abelian groups which implies that for every ǫ > 0, there is a δ > 0 such that for any abelian group G and three subsets A,B,C, either there are at least δ|G|2 distinct triples (a, b, c) ∈ A×B×C satisfying a+b+c = 0, or one can elimin”
Hypergraph containers (2012, methodology): “A well-known instance of this question is to find the number of subsets S ⊂ [N ] containing no solution to x + y = z; the asymptotic answer, conjectured by Cameron and Erdős [11], was given by Green [24] and by Sapozhenko [46].”
The dichotomy between structure and randomness, arithmetic progressions, and the primes (2005, methodology): “A more refined structure theorem was given in [23] (see also [35]), which was termed an “arithmetic regularity lemma” in analogy with the Szemerédi regularity lemma which we discuss in the next section.”
On a Generalization of Szemerédi's Theorem (2005, background): “Another construction of Bohr sets (so-called smoothed Bohr sets) was given in [15] and [7].”
A relative Szemerédi theorem (2013, result): “One of the immediate advantages of this theorem is that it simplifies the proof of the Green-Tao theorem.”
Multiple ergodic averages for three polynomials and applications (2006, unknown): “Every system ( X, X , µ, T ) has an ergodic decomposition , meaning that we can write µ = (cid:11) µ t dλ ( t ), where λ is a probability measure on [0 , 1] and µ t are T -invariant probability measures on ( X, X ) such that the systems ( X, X , µ t , T ) are ergodic for t ∈ [0 , 1].”
Decompositions, approximate structure, transference, and the Hahn–Banach theorem (2008, methodology): “This is a lemma of Green and Tao that we stated as Lemma 4.6.”