A relative Szemerédi theorem

Abstract

The celebrated Green-Tao theorem states that there are arbitrarily long arithmetic progressions in the primes. One of the main ingredients in their proof is a relative Szemerédi theorem which says that any subset of a pseudorandom set of integers of positive relative density contains long arithmetic progressions. In this paper, we give a simple proof of a strengthening of the relative Szemerédi theorem, showing that a much weaker pseudorandomness condition is sufficient. Our strengthened version can be applied to give the first relative Szemerédi theorem for $k$-term arithmetic progressions in pseudorandom subsets of ${\mathbb{Z}}_N$ of density $N^{-c_k}$. The key component in our proof is an extension of the regularity method to sparse pseudorandom hypergraphs, which we believe to be interesting in its own right. From this we derive a relative extension of the hypergraph removal lemma. This is a strengthening of an earlier theorem used by Tao in his proof that the Gaussian primes contain arbitrarily shaped constellations and, by standard arguments, allows us to deduce the relative Szemerédi theorem.

22 pages

References in corpus (6)

• A Szemeredi-type regularity lemma in abelian groups, with applications
• Extremal results for random discrete structures
• On the KŁR conjecture in random graphs
• An arithmetic transference proof of a relative Szemerédi theorem
• A short proof of the multidimensional Szemerédi theorem in the primes
• Linear forms from the Gowers uniformity norm

Cited by in corpus (22)

• An $L^p$ theory of sparse graph convergence I: limits, sparse random graph models, and power law distributions
• Combinatorial theorems relative to a random set
• The Green-Tao theorem: an exposition
• Minor arcs, mean values, and restriction theory for exponential sums over smooth numbers
• Four variants of the Fourier-analytic transference principle
• A Multidimensional Szemerédi Theorem in the primes
• Counting results for sparse pseudorandom hypergraphs II
• Polynomial patterns in the primes
• Counting results for sparse pseudorandom hypergraphs I
• Regularity inheritance in hypergraphs
• Szemerédi's theorem in the primes
• A multi-dimensional Szemerédi theorem for the primes via a correspondence principle
• Linear forms from the Gowers uniformity norm
• Constellations in prime elements of number fields
• Resilience for tight Hamiltonicity
• Corners in dense subsets of P^d
• A transference principle for systems of linear equations, and applications to almost twin primes
• Arithmetic properties of sparse subsets of ${\mathbb{Z}}^n$
• A counterexample to the Bollobás-Riordan conjectures on sparse graph limits
• Narrow arithmetic progressions in the primes
• The Green-Tao theorem for affine curves over F_q
• Removal lemmas and approximate homomorphisms