Lewko's blog

Thin sets of primes and the Goldbach property

Posted in Fourier Analysis, math.NT, Uncategorized by Mark Lewko on November 19, 2009

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 {E} is the set of positive even integers that cannot be expressed as the sum of two primes then

 \displaystyle |[0,N]\cap E| \leq |N|^{1-\delta}

for some positive constant {\delta>0}. 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 {S} has the Goldbach property (GP) if the sumset {S+S} 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 {S} (of positive integers) with the GP must satisfy

 \displaystyle \liminf_{N\rightarrow\infty} \frac{[0,N]\cap S}{\sqrt{N}} > 0.

This is to say that a set of positive integers with the GP must satisfy {[0,N]\cap S \gg \sqrt{N}} for all large {N}. Recall that the prime number theorem gives us that {|[0,N]\cap\mathcal{P}| \approx N/\ln(N)} for the set of primes {\mathcal{P}}. 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 {\mathcal{Q}} such that {\mathcal{Q}+\mathcal{Q}} has positive density in the integers and

\displaystyle \limsup_{N\rightarrow\infty} \frac{[0,N]\cap \mathcal{Q}}{\sqrt{N}} < \infty.


Tagged with: ,

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) <p< 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…)

Lattice points in l^{1} balls

Posted in math.CO, math.NT by Mark Lewko on July 31, 2009

For positive integers {n} and {m}, let {L(n,m)} denote the number of points {x = (x_1, \ldots, x_n) \in \mathbb{Z}^n} such that {\sum_{i=1}^n |x_i| \leq m}.  In other words, {L(n,m)} is the number of lattice points in an n-dimensional l^1-ball of radius mBump, Choi, Kurlberg and Vaaler have observed that the function {L(n,m)} enjoys the following symmetry

\displaystyle {L(n,m) = L(m,n)}

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

\displaystyle \sum_{n=1}^{\infty}\sum_{m=1}^{\infty}L(m,n)x^m y^n = (1-x-y-xy)^{-1}

and noting that it is symmetric in x and y.  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. 


Tagged with:

Hello world

Posted in admin by Mark Lewko on July 31, 2009

I am a graduate student in Mathematics at the University of Texas at Austin, where I study analysis and its applications.  

I intend for this blog to be mathematically oriented, with a focus on results and problems related to my research interests.  I imagine that my attention will vary as I need to devote time to other projects, and there might be long stretches of inactivity.

My hope is that (at least some of) the posts will be of interest to others and lead to lively discussion.  As such, I welcome all comments, criticisms, corrections and suggestions.

You may contact me by leaving a comment below, or by email at mlewko<at>gmail.com