Lewko's blog

The dense model theorem

Posted in expository, math.IT, math.NT by Mark Lewko on December 14, 2009

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.) (more…)

Hölder’s inequality via complex analysis

Posted in expository, math.CA by Mark Lewko on October 13, 2009

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 ${\phi(z)}$ be a bounded analytic function in the strip ${B=\{z : 0<\Re(z)<1\}}$. Furthermore, assume that $\phi(z)$ extends to a continuous function on the boundary of $B$ and satisfies

$\displaystyle |\phi(it)|\leq M_{0} \hspace{1cm}\text{and}\hspace{1cm} |\phi(1+it)|\leq M_{1}$

for $t\in \mathbb{R}$. Then, for $0\leq \sigma \leq 1$, we have that

$\displaystyle|\phi(\sigma+it)|\leq M^{1-\sigma}_{0}M^{\sigma}_{1}.$

Proof: Let $\epsilon>0$ and consider the function (analytic in $B$)

$\displaystyle \phi_{\epsilon}(z)=\phi(z)M_{0}^{z-1}M_{1}^{-z} e^{\epsilon z(z-1)}.$

One easily checks that ${\phi_{\epsilon}(z)\leq 1}$ if ${\Re(z)=0}$ or ${\Re(z)=1}$. Furthermore, since ${|\phi(z)|}$ is uniformly bounded for ${z \in \overline{B}}$, we must have that

$\displaystyle \lim_{\Im{z}\rightarrow\infty}|\phi_{\epsilon}(z)|=0$

for ${ 0 < \Re z < 1}$. We now claim that, for ${A}$ sufficiently large, ${|\phi_{\epsilon}(z)|\leq 1}$ for ${z \in B_{A}}$ where ${B_{A}=\{z : 0\leq\Re(z)\leq 1, -A \leq \Im(z) \leq A\}}$. This follows by the previous remarks on the boundary of ${B_{A}}$, and by the maximum modulus principle in its interior. This completes the proof. $\Box$

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

Theorem (Hölder’s Inequality)Let ${(X, \mathcal{M}, \mu)}$ be a measure space, ${p,q\in [1,\infty]}$ such that ${\frac{1}{p}+\frac{1}{q}=1}$. If ${f \in L^p(X)}$ and ${g \in L^q(X)}$ then

$\displaystyle ||fg||_{L^1} \leq ||f||_{L^p}||g||_{L^q}.$

Proof: By a standard limiting argument (preformed first with, say, ${g}$ fixed) it will suffice to assume that ${f}$ and ${g}$ are simple functions. If we let ${z=1/q}$ we may now rewrite Hölder’s inequality as

$\displaystyle \int_{X}|f|^{p(1-z)}|g|^{qz}d\mu \leq ||f||_{L^p}^{p(1-z)}||g||_{L^q}^{qz}$

Indeed, ${p(1-z)=p/p=1}$. Using the fact that ${f}$ and ${g}$ are simple, we can define a function, ${\phi(z)}$, analytic in the strip ${B}$ by

$\phi(z)=\int_{X}|f|^{p(1-z)}|g|^{qz}d\mu=\sum_{n=1}^{N}\sum_{m=1}^{M}a_n b_m e^{\lambda_n p(1-z)}e^{\kappa_m q z}.$

It follows that ${|\phi(\sigma+it)| \leq |\phi(\sigma)|}$, and that ${\phi(z)}$ is bounded on the closure of ${B}$. We record that ${|\phi(it)| \leq |\phi(0)| = \int_{X}|f|^{p}d\mu}$ and ${|\phi(1+it)| \leq \phi(1) = \int_{X}|g|^{q}d\mu }$. Now, by the three lines lemma, we have that

$\displaystyle \int_{X}|f|^{p(1-\sigma)}|g|^{q\sigma}d\mu=|\phi(\sigma)|\leq (\int_{X}|f|^{p}d\mu)^{1-\sigma}(\int_{X}|g|^{q}d\mu)^{\sigma}.$

Taking ${\sigma=1/q}$ we recover Hölder’s inequality. $\Box$

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

Posted in expository, math.CO by Mark Lewko on September 2, 2009

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 ${1/2}$. Thus the prisoners will escape execution with probability

$\displaystyle \left(1/2\right)^{100}\approx 0.7888609052\times 10^{-30}.$

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). (more…)

The sharp large sieve inquality

Posted in expository, Fourier Analysis, math.NT, Uncategorized by Mark Lewko on August 31, 2009

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 $N+\delta^{-1}$ in Theorem 1 below by $N-1+\delta^{-1}$.  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

Posted in expository, Fourier Analysis, math.CA by Mark Lewko on August 4, 2009

In the previous post we saw the connection between the ball multiplier ${S_{1}}$ and spherical ${L^{p}}$ convergence of Fourier transforms. Recall that the operator ${S_{1}}$ is defined in ${d}$ dimensions by the relation

$\displaystyle \widehat{S_{1}f}(\xi) = \chi_{B}(\xi)\hat{f}(\xi)$

where ${B}$ denotes the ${d}$-dimensional unit ball.  The focus of this post will be to prove the following result

Theorem 1 (Fefferman, 1971) The operator ${S_{1}}$ is not bounded on ${L^{p}(\mathbb{R}^d)}$ if ${d>1}$ and ${p\neq2}$.

L^{p} convergence of Fourier transforms

Posted in expository, Fourier Analysis, math.CA by Mark Lewko on August 3, 2009

Let ${\chi_{B}(x)}$ denote the characteristic function of the unit ball ${B}$ in ${d}$ dimensions. For a smooth function of rapid decay, say ${f}$, we can define the linear operator ${S_{1}}$ by the relation

$\displaystyle \widehat{S_{1}f}(\xi) = \chi_{B}(\xi)\hat{f}(\xi)$

where ${\hat{f}(\xi)}$ denotes the Fourier transform of ${f}$, 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 ${p}$ and ${d}$ we can extended ${S_{1}}$ to a bounded linear operator on ${L^{p}(\mathbb{R}^d)}$. The ${1}$-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 $2d/(d+1) was a necessary condition for the boundedness of $S_{1}$, 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 ${d\geq2}$, that ${S_{1}}$ does not extend to a bounded operator on any ${L^p}$ space apart from the trivial case when ${p=2}$ (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 ${d}$-dimensional torus ${\mathbb{T}^d}$). 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 ${\mathbb{R}^d}$. (more…)