Spring 2017

Algorithmic Dense Model Theorems and Weak Regularity

Monday, April 10th, 2017 9:30 am10:00 am

Add to Calendar

Green and Tao ([GT04]) used the existence of a dense subset indistinguishable from the primes under certain tests from a certain class to prove the existence of arbitrarily long prime arithmetic progressions. Tao and Ziegler ([TZ06]) showed some general conditions under which such a model exists. In [RTTV08], a quantitatively improved characterization was obtained using an argument based on Nisan’s proof of the Impagliazzo hard-core set theorem ([I95]) from computational complexity. Gowers ([Gow08]) independently obtained a similar improvement. 
We show that the existence of dense models can be reduced directly to the improved hardcore distri-bution results of Holenstein ([H05]). Using Holenstein’s uniform proof of an optimal density hard-core set theorem, we show that the dense models that one derives have a canonical form, with models being (sampleable from) functions defined in terms of tests from the original class. We give several applications, including generalizations of weak regularity lemmas ([FK99, K97, COCF]). For example, we show that any graph G with ∆n2 edges has a γ-cut-approximator of rank 2poly(1/γ,1/ log(1/∆), whereas direct application of [FK99] gives rank 2O(1/γ2∆2)