A Szemeredi-type regularity lemma in abelian groups, with applications

Abstract

Szemeredi's regularity lemma is an important tool in graph theory which has applications throughout combinatorics. In this paper we prove an analogue of Szemeredi's regularity lemma in the context of abelian groups and use it to derive some results in additive number theory. One is a structure theorm for sets which are almost sum-free. If A is a subset of [N] which contains just o(N^2) triples (x,y,z) such that x + y = z then A may be written as the union of B and C, where B is sum-free and |C| = o(N). Another answers a question of Bergelson, Host and Kra. If alpha, epsilon > 0, if N > N_0(alpha,epsilon) and if A is a subset of {1,...,N} of size alpha N, then there is some non-zero d such that A contains at least (alpha^3 - epsilon)N three-term arithmetic progressions with common difference d.

31 pages. New version has an extra section and some remarks reflecting recent developments

Cited by in corpus (19)

• Hypergraph containers
• Linear forms and higher-degree uniformity for functions on ${\mathbb{F}}_p^n$
• Extremal results in sparse pseudorandom graphs
• A relative Szemerédi theorem
• A quantitative version of the idempotent theorem in harmonic analysis
• The Growth Rate of Tri-Colored Sum-Free Sets
• A group version of stable regularity
• Monochromatic sums and products
• On the structure of large sum-free sets of integers
• Popular differences for matrix patterns
• Approximate groups and doubling metrics
• A Noisy-Influence Regularity Lemma for Boolean Functions
• Stability results for random discrete structures
• Patterns without a popular difference
• Testing linear-invariant properties
• Induced arithmetic removal: complexity 1 patterns over finite fields
• Approximate subgroups with bounded VC-dimension
• The Erdos-Moser sum-free set problem
• On linear configurations in subsets of compact abelian groups, and invariant measurable hypergraphs