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.)

Hölder’s inequality via complex analysis

In this post I will give a complex variables proof of Hölder’s inequality due to Rubel. The argument is very similar to Thorin’s proof of the Riesz-Thorin interpolation theorem. I imagine that there is a multilinear form of Riesz-Thorin that provides a common generalization of the two arguments, however we won’t explore this here. We start by establishing the well-known three lines lemma.

Lemma (three lines lemma) Let be a bounded analytic function in the strip . Furthermore, assume that extends to a continuous function on the boundary of and satisfies

for . Then, for , we have that

Proof: Let and consider the function (analytic in )

One easily checks that if or . Furthermore, since is uniformly bounded for , we must have that

for . We now claim that, for sufficiently large, for where . This follows by the previous remarks on the boundary of , and by the maximum modulus principle in its interior. This completes the proof.

We are now ready to give a complex variables proof of Hölder’s Inequality.

Theorem (Hölder’s Inequality)Let be a measure space, such that . If and then

Proof: By a standard limiting argument (preformed first with, say, fixed) it will suffice to assume that and are simple functions. If we let we may now rewrite Hölder’s inequality as

Indeed, . Using the fact that and are simple, we can define a function, , analytic in the strip by

It follows that , and that is bounded on the closure of . We record that and . Now, by the three lines lemma, we have that

Taking we recover Hölder’s inequality.

Updated 10/13/2009: typos corrected

Updated 10/14/2009: the statement of the three lines lemma was truncated in the original post

Update 10/31/2009: typo in definition of B.

Condemned prisoners and random permutations

In this post I will present one of my favorite logic puzzles. As with many great logic puzzles (see the blue-eyed islanders puzzle, for example), the mathematics is embedded in a gruesome storyline. The puzzle can be stated as follows:

There are 100 prisoners. The warden places 100 wooden boxes in a row in an empty room. He writes the name of each prisoner on 100 separate slips of paper and places one of these slips into each of the 100 boxes, in a manner of his choosing.

Each prisoner is lead into the room, one at a time. The prisoner is allowed to open up to 50 boxes. If the prisoner does not find his own name, all prisoners are executed. If a prisoner finds his own name, the prisoner must reset the boxes exactly as he found them. The process then continues onto the next prisoner. If all 100 prisoners find their own name, all of the prisoners will be released the next morning.

The prisoners are allowed to agree on a strategy before this process starts, however they may not communicate in any way after the process has started. What strategy should the prisoners use to minimize the chance of execution?

Notice that if each of the prisoners open 50 randomly selected boxes, then each prisoner will find his own name with probability . Thus the prisoners will escape execution with probability

This is roughly 1 divided by the number of grams of matter composing the Earth. Below the fold we present a strategy that succeeds with probability about .307 (highlight to see probability).

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.

Fefferman’s ball multiplier counterexample

In the previous post we saw the connection between the ball multiplier and spherical convergence of Fourier transforms. Recall that the operator is defined in dimensions by the relation

where denotes the -dimensional unit ball.  The focus of this post will be to prove the following result

Theorem 1 (Fefferman, 1971) The operator is not bounded on if and .

 

L^{p} convergence of Fourier transforms

Let denote the characteristic function of the unit ball in dimensions. For a smooth function of rapid decay, say , we can define the linear operator by the relation

 

where denotes the Fourier transform of , as usual. This operator naturally arises in problems regarding the convergence of Fourier transforms (which we discuss below). A fundamental problem regarding this operator is to determine for which values of and  we can extended to a bounded linear operator on . The -dimensional case of this problem was settled around 1928 by M. Riesz, however the higher dimensional cases proved to be much more subtle. In 1954 Herz showed that was a necessary condition for the boundedness of , and sufficient in the special case of radial functions. It was widely conjectured that these conditions were also sufficient in general (this was known as the disc conjecture). However,  in 1971 Charles Fefferman proved, for , that does not extend to a bounded operator on any space apart from the trivial case when (which follows from Parseval’s identity). Recently, I needed to look at Fefferman’s proof and decided to spend some time trying to figure out what is really going on. I will attempt to give a motivated account of Fefferman’s result, in a two post presentation. In this (the first) post I will describe the motivation for the problem, as well as develop some tools needed in the proof. The problems discussed here were first considered in the context of Fourier series (i.e. functions on the -dimensional torus ). It turns out, however, that these problems are slightly easier to address on Euclidean space, and are equivalent thanks to a result of de Leeuw. In light of this, we will work exclusively on .