A relative Szemerédi theorem
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 ℤ_N of density N^(−ck). 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.
Additional Information© 2015 Springer Basel. Received 10 September 2014; accepted 20 October 2014; first online 17 March 2015. The first author was supported by a Royal Society University Research Fellowship, the second author was supported by a Simons Fellowship, NSF grant DMS-1069197, by an Alfred P. Sloan Fellowship, and by an MIT NEC Corporation Fund Award, and the third author was supported by a Microsoft Research PhD Fellowship. We would like to thank Tom Bohman and Ben Green for helpful discussions.
Submitted - 1305.5440.pdf