Mathematics – Combinatorics
Scientific paper
2008-06-02
Mathematics
Combinatorics
Scientific paper
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).
Reingold Omer
Trevisan Luca
Tulsiani Madhur
Vadhan Salil
No associations
LandOfFree
New Proofs of the Green-Tao-Ziegler Dense Model Theorem: An Exposition does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with New Proofs of the Green-Tao-Ziegler Dense Model Theorem: An Exposition, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and New Proofs of the Green-Tao-Ziegler Dense Model Theorem: An Exposition will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-194538