A relative Szemerédi theorem

By David Conlon, Jacob Fox, Yufei Zhao. 2013

62 citations recorded by the source corpus.

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}$$ZN of density $${N^{-c_k}}$$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.

Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics, Geometry and Topology

View Paper: https://www.semanticscholar.org/paper/29f4c346ffe4bd43b63dd88bf89fcc3c5c26b7d2

How researchers see this paper

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

In Computational Theory and Mathematics

In Discrete Mathematics and Combinatorics

In Geometry and Topology

Citations in the corpus

Large gaps between consecutive prime numbers (2014, background): “Note, however, that by the work of Conlon, Fox and Zhao [4] one could in principle dispense with the need for this condition entirely.”
Diagonal Ramsey via effective quasirandomness (2020, background): “[10, 1, 3, 19, 6, 7]) in connection with extremal graph theory and additive combinatorics.”