The dense model theorem

A key component in the work of Green, Tao, and Ziegler on arithmetic and polynomial progressions in the primes is the dense model theorem. Roughly speaking this theorem allows one to model a dense subset of a sparse pseudorandom set by dense subset of the the ambient space. In the work of Green, Tao, and Zeigler this enabled them to model (essentially) the characteristic function of the set of primes with (essentially) the characteristic function of a set of integers with greater density. They then were able to obtain the existence of certain structures in the model set via Szemerédi’s theorem and its generalizations.   

 More recently, simplified proofs of the dense model theorem have been obtained independently by Gowers and Reingold, Trevisan, Tulsiani and Vadhan. In addition, the latter group has found applications of these ideas in theoretical computer science. In this post we give an expository proof of the dense model theorem, substantially following the paper of Reingold, Trevisan, Tulsiani and Vadhan.   

 With the exception of the min-max theorem from game theory (which can be replaced by (or proved by) the Hahn-Banach theorem, as in Gowers’ approach) the presentation is self-contained.   

(We note that the the theorem, as presented below, isn’t explictly stated in the Green-Tao paper. Roughly speaking, these ideas can be used to simplify/replace sections 7 and 8 of that paper.)

Thin sets of primes and the Goldbach property

As is well known, Goldbach conjectured that every even positive integer (greater than 2) is the sum of two primes. While this is a difficult open problem, progress has been made from a number of different directions. Perhaps most notably, Chen has shown that every sufficiently large even positive integer is the sum of a prime and an almost prime (that is an integer that is a product of at most two primes). In another direction, Montgomery and Vaughan have shown that if is the set of positive even integers that cannot be expressed as the sum of two primes then

 

for some positive constant . This is stronger than the observation (which was made much earlier) that almost every positive integer can be expressed as the sum of two primes. In this post we’ll be interested in sets of integers with the property that most integers can be expressed as the sum of two elements from the set. To be more precise we’ll say that a set of positive integers has the Goldbach property (GP) if the sumset consists of a positive proportion of the integers. From the preceding discussion we have that the set of primes has the GP. (This discussion is closely related to the theory of thin bases.)

A natural first question in investigating such sets would be to ask how thin such a set can be. Simply considering the number of possible distinct sums, the reader can easily verify that a set (of positive integers) with the GP must satisfy

 

This is to say that a set of positive integers with the GP must satisfy for all large . Recall that the prime number theorem gives us that  for the set of primes . Thus the primes are much thicker than a set with the GP needs to be (at least from naive combinatorial considerations).

Considering this, one might ask if there is a subset of the primes with the GP but having significantly lower density in the integers. I recently (re)discovered that the answer to this question is yes. In particular we have that

 Theorem 1 There exists a subset of the primes such that has positive density in the integers and

The sharp large sieve inquality

This is the first post in a short sequence related to the large sieve inequality and its applications. In this post I will give a proof of the sharp (analytic) large sieve inequality. While the main result of this post is a purely analytic statement, one can quickly obtain a large number of arithmetic consequences from it. The most famous of these is probably a theorem of Brun which states that the sum of the reciprocals of the twin primes converges. I will present this and other arithmetic applications in a following post. This post will focus on proving the sharp (analytic) large sieve inequality. Much of the work in this post could be simplified if we were willing to settle for a less than optimal constant in the inequality. This would have little impact on the the arithmetic applications, but we’ll stick to proving the sharp form of this inequality (mostly for my own benefit). I should point out that there is an alternate approach to this inequality, via Selberg-Buerling extremal functions, which gives an even sharper result.  In particular, using this method one can replace the in Theorem 1 below by .  We will not pursue this further here, however.  Much of this post will follow this paper of Montgomery, however I have made a few attempts at simplifying the  presentation, most notably I have eliminated the need to use properties of skew-hermitian forms in the proof of the sharp discrete Hilbert transform inequality.

Lattice points in l^{1} balls

For positive integers and , let  denote the number of points such that .  In other words,  is the number of lattice points in an -dimensional -ball of radius .  Bump, Choi, Kurlberg and Vaaler have observed that the function  enjoys the following symmetry

. 

This is to say that the -dimensional -ball of radius contains exactly the same number of lattice points as the -dimensional -ball of radius .  The original proof follows from establishing the generating function identity

and noting that it is symmetric in and .  Some time ago Jeff Vaaler mentioned to me that it would be nice to find a bijective proof of this fact.  In this post I will give a simple bijective proof that Allison Bishop and I found.