New Proofs of the Green-Tao-Ziegler Dense Model Theorem: An Exposition

arXiv0806.0381MaRDI QIDQ6209760FDOQ6209760

Authors: Omer Reingold, Luca Trevisan, Madhur Tulsiani, Salil Vadhan 

Publication date: 2 June 2008

Abstract: Green, Tao and Ziegler prove ``Dense Model Theorems of the following form: if R is a (possibly very sparse) pseudorandom subset of set X, and D is a dense subset of R, then D may be modeled by a set M whose density inside X is approximately the same as the density of D in R. More generally, they show that a function that is majorized by a pseudorandom measure can be written as a sum of a bounded function having the same expectation plus a function that is ``indistinguishable from zero. This theorem plays a key role in the proof of the Green-Tao Theorem that the primes contain arbitrarily long arithmetic progressions. In this note, we present a new proof of the Green-Tao-Ziegler Dense Model Theorem, which was discovered independently by ourselves and Gowers. We refer to our full paper for variants of the result with connections and applications to computational complexity theory, and to Gowers' paper for applications of the proof technique to ``decomposition, ``structure, and ``transference theorems in arithmetic and extremal combinatorics (as well as a broader survey of such theorems).

This page was built for publication: New Proofs of the Green-Tao-Ziegler Dense Model Theorem: An Exposition

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6209760)