What's new:
What was new in 2003? 2002?
2001?2000?1999?
Dec 26, 2004
- Uploaded:
The short story “The
Roth-Bourgain theorem”.
This is an exposition of Bourgain’s refinement of
Roth’s second most famous theorem, concerning arithmetic
progressions of length three. (The
most famous, of course, being the Thue-Siegel-Roth
theorem on Diophantine approximation).
Bourgain establishes the closest result we have to date on the
Erdos-Turan conjecture for progressions of length three, namely that
subsets of {1,…,N} with density C sqrt(log log N) / sqrt(log N) for
sufficiently large C will contain a non-trivial progression of length three. This is basically the limit of
Roth’s Fourier-analytic method, and any advance on this bound would
be quite significant (even removing the sqrt(log log N) looks
difficult). Here we present a
streamlined version of Bourgain’s argument, which revolves around
obtaining density increments in nested Bohr sets. I also have an earlier
exposition which used weighted Bohr functions instead of Bohr sets but
have since decided that Bourgain’s original approach is
superior. This result will also
appear as a section of a chapter on Szemeredi’s theorem in my
forthcoming book with Van Vu, so you can view this as another
“trailer” for this book J.
Dec 21, 2004
- Uploaded:
The short story “The
Banach-Tarski paradox”.
This is a brief writeup of the standard proof of the Banach Tarski
paradox (that one can decompose the unit ball, minus the origin, into
eight pieces, four of which can be rotated to re-create the punctured
ball, and the other four of which can also be rotated to re-create the
punctured ball).
Dec 20, 2004
- Uploaded:
“Symplectic nonsqueezing
of the KdV flow”, joint with Jim Colliander, Mark Keel, Gigliola
Staffilani, and Hideo Takaoka, submitted to Acta Mathematica. This project was announced about two
years ago (for instance in my 2002
Calderon-Zygmund lectures in Chicago)
but was delayed for a number of reasons, including “Project Gopher”
and a major revision to the paper about halfway through the project. In this paper we use the global
well-posedness theory for periodic KdV at the standard phase space
regularity H^{-1/2} developed in our earlier paper,
together with some analysis of the Miura transform (also developed
independently by Kappeler and Topalov) in order to demonstrate that the
KdV flow obeys Gromov’s symplectic non-squeezing property: a large
ball cannot be squashed under the Hamiltonian flow to a small
cylinder. Gromov’s theorem
already applies for all finite-dimensional Hamiltonian systems on a flat
phase space, and so the difficulty is purely analytic, requiring that one
approximate the infinite-dimensional KdV flow by a finite dimensional
one. More physically, this requires
that one control the extent to which the high frequencies in KdV could
disrupt the evolution of the low frequencies, for low regularity data in
the space H^{-1/2}. For other
dispersive models, notably compact perturbations of the periodic wave
equation and the periodic NLS equation, this was carried out by Kuksin and
by Bourgain respectively; however, a new difficulty arises for KdV, in
that the standard truncation to the low frequencies destroys some delicate
cancellation effects in KdV and the truncated flow does not approximate
the actual flow in the desired sense.
To solve this problem we have to apply a smooth truncation instead
of a rough one, and in order to analyze the latter truncation effectively
one has to lift the evolution up via the inverse Miura transform to a
variant of the modified KdV (mKdV) flow.
In the process we develop a number of tools for tracking movement
of energies from one frequency to another (which can be viewed as
extensions of the “I-method” we developed in earlier papers)
which may be of independent interest.
Also we develop the theory of the Miura transform and its inverse
for rough data (though as mentioned before this theory was also carried
out, in fact all the way down to H^{-1}, by Kappeler and Topalov; they
have also claimed to establish local and global well-posedness in this
range, using methods from integrable systems (notably Birkhoff normal
forms) rather than Fourier-analytic methods).
- Uploaded:
“Long-time decay
estimates for Schrodinger equations on manifolds”, joint with Igor
Rodnianski, submitted, IAS proceedings. In this paper we demonstrate a
“quantitative Enss method” which allows one to demonstrate
long-time local smoothing estimates for Schrodinger operators with metric
perturbations. To simplify the
exposition we restricted ourselves to the simple case of compact
perturbations of Euclidean space, of course assuming a geodesic
non-trapping condition. If one is
only interested in local-in-time estimates, then the problem is purely one
of controlling the high energy portions of the solution, which was done by
Craig-Kappeler-Strauss and Doi, who also demonstrated the essential nature
of the geodesic non-trapping conditions (spectrally, this corresponds to
the absence of high frequency pseudomodes which lead to bad behavior of
the resolvents. But once one
considers long time evolution, one must also analyze the behavior of the
low and medium frequencies. The low
frequencies turn out to be easily handled by an “uncertainty
principle”, which prohibits them from concentrating all their mass
and energy on the region where the metric differs from Euclidean space
(which spectrally corresponds to nonresonance of the spectrum at zero),
however the medium frequencies require significantly more attention. Here, the spectral fact we need is that
the medium portion of the spectrum contains no embedded
eigenfunctions. To quantify this,
we use the RAGE theorem and a compactness argument to establish that
medium frequency solutions must “escape” the metric
perturbation after a fixed finite time.
After that, one needs to prevent the solution from returning back
to the perturbation region, and for this we need the quantitative Enss
method, splitting the solution into incoming and outgoing parts and using
Duhamel’s principle to “shepherd” the solution towards
asymptotic spatial infinity. As it
turns out, our results here were eventually superceded by another method
we discovered later using the limiting absorption principle, and which
will appear shortly; however this method still has some interest, for
instance it was useful in obtaining new asymptotic results for
nonlinear Schrodinger equations.
Dec 5, 2004
- Uploaded:
The short story “Menger’s
theorem”. This is another
section removed from my forthcoming book “Additive
Combinatorics” with Van Vu due to space concerns; it presents two
proofs of a classical theorem from graph theory.
Dec 2, 2004
- Linked:
“Erdos
distance problem for convex metrics”, the PhD thesis of my first
graduate student, Julia
Garibaldi. Here, Julia
investigates the extent to which the known results on the Erdos distance
problem (how many distinct distances must there be from n points in the
plane?) extend to other convex metrics, including asymmetric metrics. Her first result is that Erdos’s
lower bound of sqrt(n) distances holds unconditionally, with a bound which
is completely independent on the choice of metric (including metrics with
infinitely many flat sides). She
then obtains a nearly necessary and sufficient condition as to when this
bound is sharp – it appears that one needs a pair of opposing
parallel flat edges on the unit ball.
For the case of the l^p metric, she has obtained a lower bound of
n^{4/5} by the method of Szekely, and has suggested that a further
improvement to n^{6/7} is possible.
A similar result is obtained for generic metrics, which she has
called “potato metrics”.
In addition to the new results, the thesis also reviews the
Euclidean theory and may be a useful resource for those who are interested
in learning about this fascinating problem in combinatorial incidence
geometry.
Nov 28, 2004
- Uploaded:
“Multi-parameter
paraproducts”, submitted to Revista Mat. Iber., with Camil Muscalu, Jill Pipher, and Christoph Thiele. Here we extend our previous paper to the case
of multi-parameter paraproducts in several dimensions involving multiple
functions, and with the output below L^1; the novelty here is that we use
a decomposition trick to avoid the use of Journe’s lemma, which is
what allows us to go beyond the bi-parameter case. More precisely, while we first decompose
the multipliers in the standard Littlewood-Paley manner (with compact
support in frequency and some annoying tails in space) we eventually
redecompose the other way, obtaining components that are compactly
supported in space with tails in frequency. This allows us to obtain orthogonality
estimates without recourse to Journe’s lemma.
- Uploaded:
The short story “Arithmetic
Ramsey Theory”. This was
initially intended to be a chapter in my forthcoming book “Additive
Combinatorics” with Van Vu, but it ended up being cut due to reasons
of space (and besides, Graham, Rothschild and Spencer did a better job on
this topic). So I have made it
publicly available instead. It
contains most of the standard arithmetic theorems in Ramsey theory,
including Shelah’s proof of the Hales-Jewett theorem and a sketch of
Walters’ combinatorial proof of the polynomial Hales-Jewett
theorem.
Nov 15, 2004
- Uploaded:
“Geometric
renormalization of large energy wave maps”, submitted to Forges
les Eaux conference proceedings.
This is a report on “Project Heatwave”, one of my
longer-term projects in which I aim to solve the large energy wave map
equation (for hyperbolic targets) using the harmonic map heat flow to set
a gauge to renormalize the equation.
There are four components to this argument: the algebra of the
gauge renormalization, the Morawetz-type formula that establishes a
non-concentration type result, a Tataru-type analysis that shows that the
renormalized equation behaves semilinearly, and an induction on energy
argument (as with project Gopher) that puts these three ingredients
together to conclude the full result.
The latter two are very technical and lengthy and are still work in
progress. However the first two are
relatively easy to describe, and this is the purpose of this note here. Specifically, we describe a new way of
obtaining a good gauge to work in for wave maps, which analytically
resembles my microlocal gauge transformation but has the advantage of
being completely intrinsic (coming directly from the harmonic map heat
flow – more specifically, we obtain a good co-ordinate frame for a
wave map by deforming the map via heat flow to a constant and then pulling
back a constant frame) and working for large energy maps into negatively
curved targets. It also avoids some
of the technical problems of the Coulomb gauge, which have an artificial
singularity at the frequency origin.
In my opinion it is the “right” gauge for working with
wave maps, in the sense that it is geometrically very natural and seems to
have all the right analytic properties, though it is perhaps the most
technical to work with (in particular, one must replace standard
Littlewood-Paley theory by nonlinear parabolic theory, though the theory
here is actually remarkably beautiful).
We also prove a simple Morawetz inequality which shows that in a certain
sense wave maps, if they concentrate at a point, must resemble harmonic
maps in the limit. Since negatively
curved spaces do not support non-trivial harmonic maps, this in principle
establishes non-concentration, which should give global regularity. There are however a very large number of
technical issues that need to be resolved; stay tuned for some further
developments!
Nov 11, 2004
- Uploaded:
The short story “An
informal summary of Bourgain's radial critical NLS result”,
joint with Jim Colliander,
Mark Keel, Gigliola
Staffilani, and Hideo Takaoka.
These are 2002 notes from “Project Gopher”
which predate our successful resolution of the global well-posedness and
scattering result for non-radial solutions of the energy-critical NLS;
here we are analyzing Bourgain’s radial argument and trying to
describe the approach in informal terms instead of in quantitative and
rigorous terms. For those of you
who are interested in this topic, this may help set some context for our
result; not only does it describe part of our thinking (before we solved
some other obstacles), but it links our result to the earlier work of
Bourgain. See also the earlier
short story “Viriel,
Morawetz, and interaction Morawetz inequalities” and the article
“Global
well-posedness and scattering for the higher-dimensional energy-critical
non-linear Schrodinger equation for radial data” for more
background material.
- Uploaded:
The short story “An
informal summary of Grillakis's radial critical NLS result”,
joint with Jim Colliander,
Mark Keel, Gigliola
Staffilani, and Hideo Takaoka.
These are more 2002 notes, this time describing Grillakis’s
approach to the H^1 critical radial problem. While it ended up that our final result
was based much more on Bourgain’s approach than on Grillakis’
one, there were still a number of useful ideas in that paper, notably the
use of local mass conservation laws, which were influential in our own strategy. These notes also incorporate some
corrections to the original Grillakis paper which were pointed out to us
by the author.
- Uploaded:
“Arithmetic
progressions and the primes - El Escorial lectures”, submitted
to El Escorial conference proceedings.
These are lecture notes which are (very) loosely based on the
mini-course I gave in El Escorial earlier this year on primes in
arithmetic progression; actually they are a fairly lengthy review of some
of the background material needed to establish this result. In particular we review
Szemeredi’s theorem on arithmetic progressions, focusing on
Roth’s theorem on progressions on length 3 and Gowers’ proof
of the length 4 case; we give both the Fourier-analytic and ergodic proofs
(the latter being phrased using the quantitative ergodic theory approach
used in my paper
with Ben Green on the primes, and also on my paper on
Szemeredi’s theorem), though we skim very lightly over the
arithmetic combinatorial aspects of these arguments. We then discuss the transference of
these results to the primes, though we gloss over the number-theoretic
aspects of the theory.
Nov 4, 2004
- Uploaded:
“On random
+-1 matrices: Singularity and Determinant”, joint with Van Vu, submitted, J. Amer. Math. Soc. In this paper we revisit the work of
Kahn, Komlos, Szemeredi, and others concerning the determinant det(M_n) of
a random n x n matrix with entries iid +-1 Bernoulli variables. These authors established that the
probability that this determinant is zero is somewhat small, namely (1
– 0.001 + o(1))^n. We improve
this further to (1 – 0.06 + o(1))^n [in a future paper we shall
improve this further to (3/4 + o(1))^n].
The conjecture here is (1/2 + o(1))^n, which is best possible (in
fact a more precise form for the o(1) error is conjectured). We achieve the 1 - 0.06 bound by
simplifying and streamlining the Kahn-Komlos-Szemeredi argument. The main ideas of that argument are to
re-interpret P( det(M_n) = 0) as a probability that n random variables
X_1, …, X_n on the corners of the unit cube lie on a
hyperplane. One then uses some
Fourier analytic methods of Halasz to replaces the distribution X of these
corners with another distribution Y which is more concentrated on
hyperplanes than X is, but is not so degenerate as to be mostly at the
origin, and thus estimate the probability of the X_1,..,X_n being
degenerate by that of Y_1,…,Y_n being degenerate, times an
exponential gain. We also have a
separate theorem concerning the typical value of det(M_n); we show that it
is equal to +- sqrt(n!) exp( n^{1/2 + o(1)} ) with probability
1-o(1). (Note that det(M_n) has
mean zero and standard deviation sqrt(n!)). This is achieved by a number of
elementary lemmas concerning the distance of a random vertex X of the unit
cube to a specified subspace W. We
also indicate some generalizations to other ensembles of random matrices,
and sketch the road to improving the 1 - 0.06 result to the ¾ result (let
me just mention here that Freiman’s theorem is involved!).
Oct 25, 2004
- Uploaded:
“Near Optimal Signal
Recovery From Random Projections And Universal Encoding Strategies”,
joint with Emmanuel Candes,
submitted, IEEE Inf. Theory. In
this continuation of our previous work
with Justin Romberg, we
discuss how to recover a discrete signal in R^N from some random linear
measurements (where “random” means chosen at random from a
number of measurement ensembles, such as the Gaussian, Bernoulli, or
Fourier measurement ensembles; our approach is rather abstract and thus
applies to a general class of such ensembles). More specifically, we are interested in
seeing how accurately we can recover our data from a limited number of
such measurements. In our previous
paper, we showed (in the Fourier case) that if the signal is sparse in
that it is supported on only T locations, then we can recover the data exactly from K random measurements
with high probability if K > C T log N; furthermore, the recovery
algorithm is extremely simple, namely to solve the linear programming
problem of minimizing the L^1 norm of a function which matches those K
given measurements; in the notation of the new paper, this means that the
Fourier ensemble obeys the Exact Reconstruction Property (ERP) with an
oversampling factor of C log N. In
this paper, we consider data which is not compactly supported, but is
instead compressible in the sense that it is bounded in l^1 (or in a weak
l^p norm for some 0 < p < 1).
For such data it is easy to see from information theoretic
considerations that we cannot hope to reconstruct the data exactly from K
measurements if K << N, nevertheless we can obtain a near-optimal
approximate recovery (with high probability), in the sense that the
recovered function is close to the original signal in L^2 norm by a factor
which is within a few logarithms of what one expects from Kolmogorov
entropy or Gelfand width considerations.
The new ingredient is to supplement ERP with another property,
which we term the Uniform Uncertainty Principle (UUP), which basically
asserts with high probability, K rows sampled at random from the Fourier
matrix are such that that the singular values of all the K x T rectangular subminors of these rows are close to
their average value of sqrt{K/N}.
By using some arguments of Bourgain (developed to attack the
Lambda(p) problem and related questions) we establish this UUP for the
Fourier ensemble when the oversampling factor is C log^3 N, and use the
UUP and ERP to deduce the approximation properties listed above. This procedure is in fact quite general;
any measurement ensemble which obeys both UUP and ERP will have these good
properties. Using some standard
results on random matrices, we show that the Gaussian and Bernoulli
ensembles have this property (with oversampling factor of log N).
Sep 21, 2004
- Uploaded:
“The Bicarleson
operator”, joint with Camil Muscalu and Christoph Thiele. Here we study the bi-carleson operator,
which is the natural bilinear maximal operator which generalizes both the
Carleson maximal function and the bilinear Hilbert transform; it was
inspired by the asymptotic expansions of eigenfunctions for the
Schrodinger operator, although as it turns out this particular operator
has no direct relevance to that issue thanks to a subtle change of sign
in the phase. The phase space
model for this operator is a coupled one involving both the Carleson
maximal operator model (summing over bi-tiles) and the bilinear Hilbert
transform model (summing over tri-tiles).
However, by using the concepts of size and energy and a crucial
“biest trick” relying ultimately on the transitivity of the
tile order operation, we can effectively decouple the estimates into
simpler estimates which essentially only involve one of the two halves of
the model. This trick had already
been achieved for the dyadic Walsh model of this operator in an earlier paper
but now we tackle the Fourier case (which is more complicated technically
due to Schwartz tails).
Sep 17, 2004
- Uploaded:
The expository note “A
remark on Goldston-Yildirim correlation estimates”. Here I make a comment on the correlation
estimates for the Goldston-Yildirim truncated divisor sums, which play a
key role in my work with Ben Green on long arithmetic
progressions in the primes. The
original proof of these estimates required the classical zero-free region
for the Riemann zeta function and a certain amount of multiple contour
shifting. However, if one is
willing to settle for substantially weaker error term estimates (of o(1)
type) and if one smooths out the majorant a little bit, then one can in
fact proceed in a more elementary fashion, in the sense that the only
information required from the zeta function is the Euler product formula
and the simple pole at s=1. The
point is basically that one can truncate the contour integral to stay
within a small distance of the pole without any difficulty. Also no contour shifting is required,
instead one simply inserts the crude asymptotic zeta(s) = 1/s-1 + O(1)
into the estimates. Of course,
using this simplified argument would lead to worse upper bounds on the
first occurrence of a totally prime arithmetic progression of length k
(probably increasing the tower from seven exponentials to eight). However it does highlight an interesting
aspect of this work, which is that level of analytic number theory
required for the progressions result is remarkably primitive (indeed, it
could more or less be proven using the number theoretic technology
available to Chebyshev, prior to the prime number theorem); it is the Szemeredi
theorem (and the transference principle) which do most of the work.
- Uploaded:
The expository note “Noncommutative
sum set estimates”. This
grew out of some discussions at AIM as to whether the Ruzsa-Plunnecke sum
set estimates could be extended to non-commutative settings. It turns out that (up to polynomial
losses) the answer is yes, the point being to use the
Balog-Szemeredi-Gowers lemma to totally avoid any application of Plunnecke
inequalities (which seem to break down completely in the noncommutative
setting). However the question of
whether a Freiman-type theorem exists (replacing the notion of arithmetic
progression by a set of words from a small alphabet with some length
restrictions?) is still open, even for sets for which |A.A| is very small
(e.g. |A|+O(1)), and very interesting.
Sep 2, 2004
- Uploaded:
“Multiscale analysis of
the primes”. This is a
set of slides for the IPAM
multiscale geometry and analysis tutorials. It discusses some of the background
behind the recent result that there are arbitrarily long arithmetic
progressions in the primes, without getting into too much details, and
focusing on the “multiscale” nature of the primes, and of the
various objects used to model the primes.
- Updated:
The short story “A
quantitative proof of Wiener’s theorem”. As pointed out by Thomas Strohmer, the
stronger of my two conjectures on the dependence of constants was
disproven by Stafney in 1969 (and Shapiro in 1979, by a different
argument).
Aug 19, 2004
- Uploaded:
“Sharp
Strichartz estimates on non-trapping asymptotically conic manifolds”,
joint with Andrew Hassell and Jared Wunsch, submitted, AJM. In this paper we continue our previous investigations
in obtaining sharp (in the sense of no derivative loss) local-in-time
Strichartz estimates for the Schrodinger equation on manifolds. (One could add a bounded potential term
but such a lower order term has no impact on the local-in-time theory). We assume that the manifold is asymptotically
conic (a generalization of asymptotically flat; we also allow long-range
metric perturbations), and also assume the usual geodesic non-trapping
condition (this is necessary for Strichartz estimates to hold without any
derivative losses, otherwise one encounters pseudomode counterexamples).
Here we handle all dimensions three and higher and all Strichartz
exponents (except for the q=2 endpoint).
We use the same geometric machinery as in our previous paper, but
instead of relying on “interaction Morawetz” technology, we
instead construct “local” parametrices for the Schrodinger
operator, prove Strichartz estimates for the individual parametrices, and
then patch together the parametrices using local smoothing estimates
(following the basic approach pioneered by Staffilani and Tataru, and
modified by Burq). A key feature of
the analysis is need to interpret “local” in the sense of the
compactified manifold rather than the original manifold, otherwise one
will lose an epsilon of derivatives in the final estimate; this requires
one to use “scattering” analogues of the pseudodifferential
calculus, develop “scattering” oscillatory integral operators,
and so forth. Fortunately the
geometry is very well controlled and these extensions are straightforward
(but technical).
July 27, 2004
- Uploaded:
The short story “Quantitative
spectral theory of compact operators”. These notes grew out of my attempt to
understand the Fredholm alternative for compact operators, which asserts
that if T is compact and lambda is not an eigenvalue, then T-lambda is
invertible. I was interested in
seeing to what extent one could extract a quantitative bound for the
operator norm of (T-lambda)^{-1} out of this argument. I was eventually able to obtain such a
bound, which involves only the operator norm of T, an arbitrary parameter
r less than |lambda|, the inverse of (T-lambda)^{-1} on the generalized
eigenspaces of T at energies at least r, and the r-entropy of the image of
the unit ball under T (which is necessarily finite if T is compact). Indeed, compactness is too strong an
assumption; finite r-entropy of the image of the ball for some r <
|lambda| suffices in order to obtain a Fredholm-like theory. The point seems to be that these sorts
of operators are invertible at energies larger than r “modulo a
finite-dimensional space of obstructions”, with quite quantitative
bounds available.
- Uploaded:
The short story “A
technical survey of harmonic analysis”. This started out as an attempt to
describe what is going on in harmonic analysis to a non-specialist, but somehow
the project veered off course and became quite technical. Instead, what I have now is a rather
jargon-heavy description of the types of things that are done in harmonic
analysis nowadays, and the techniques being developed to attack the
problems of interest. As such, this
note may perhaps only be of interest to people already specializing in
harmonic analysis, who are also the ones least in need of a survey, so I
abandoned this project to start over.
Nevertheless, what I have here may still be of some minor interest.
July 22, 2004
July 18, 2004
- Uploaded:
The short story “Szemeredi’s
proof of Szemeredi’s theorem”. These are basically the notes I made for
myself when trying to read Szemeredi’s original proof of his famous
theorem on arithmetic progressions.
It is an amazing argument, combining the Szemeredi regularity
lemma, the van der Waerden theorem, and a very refined version of
Roth’s density incrementation argument (which is embodied here in
the concept of progressions having close to the asymptotic upper color
density for certain colors).
Unfortunately there are a lot of very large parameters to juggle in
the argument, and one has to constantly make sure that a very large
parameter does not come in and swamp a much smaller one at a crucial juncture. This creates a great deal of complexity
in the argument. I’ve tried
to clean it up as best I could (my notes are 26 pages to Szemeredi’s
original 46, though this is somewhat unfair because I assume the
regularity lemma whereas Szemeredi introduces it in the paper for the
first time) but it is still somewhat notationally formidable. I may revisit these notes later to try
cleaning them up further, but what I have here may already be of interest.
July 10, 2004
- Uploaded:
“Robust uncertainty principles: Exact
signal reconstruction from highly incomplete frequency information”,
joint with Emmanuel Candes and Justin Romberg (Thanks to Laurent Demanet
for pointing out that this link was previously incorrect). In this paper we show how to reconstruct
a sparse signal (supported on a small set E in, say, the cyclic group
Z/NZ) from just a handful of Fourier coefficients (we need a little bit
more than |E| log N). The algorithm
is simply to minimize the L^1 norm of the signal subject to the
constraints given by the sampled Fourier coefficients. The crucial trick, however, is to sample
the Fourier coefficients randomly – when one does so, it
turns out that with very high probability (e.g. 1 – O(N^{-M}) for
any given number M) that one can reconstruct the solution exactly. This phenomenon is also supported by
numerics (and is also of interest in the noisy edge detection problem in
image processing). We give a
rigorous demonstration as to why this algorithm works; after some duality
arguments the result boils down to that of establishing good bounds for an
inverse of a random matrix related to minors of the Fourier matrix, which
we can then control by the moment method (though we need to compute very
high moments in order to get the log N bound instead of just N^eps for any
given eps). Interestingly, the
combinatorics of Stirling numbers of the
second kind play a role in this analysis, as does the golden ratio.
July 7, 2004
July 3, 2004
June 26, 2004
- Uploaded:
The short story “Fourier-analytic
proofs of the prime number theorem”. Here what I have done is taken the two
standard proofs of the prime number theorem – the contour
integration proof using Riemann zeta functions, and the Erdos-Selberg
elementary proof relying primarily on the Selberg symmetry formula –
and rephrased them in a Fourier-analytic perspective, or more precisely
viewing the problem as one of controlling various convolutions of
continuous and discrete measures on the half-line, which can be analyzed
either in physical space or in Fourier space. In this language the two proofs actually
have a lot of structural similarity and are both trying to get control of
the same thing, namely the absence of zeroes of the zeta function on the
line Re(s)=1. In both cases one has
to work both in physical space and in Fourier space.
- Updated:
“Global
well-posedness of the Benjamin-Ono equation in H^1(R)”. A minor problem involving controlling
the size of frequency envelopes has been fixed. Thanks to Martin Hadac for pointing out
the error.
June 18, 2004
- On
hold: I’ve stopped maintaining the local and global well-posedness
page due to lack of time (and an underestimation of the sheer enormity of
the task of maintainance). I have a
tentative plan to migrate this page (and several other pages on my site)
to a wiki where it can be updated collaboratively, but I have not yet
sorted out the technical details in order to perform this migration.
June 2, 2004
- Uploaded:
The short story “A
quantitative bound for prime progressions of length k”, which is
basically a quantitative accounting of the constants in my long prime
progressions paper with Ben. A
number of people have asked me what specific bound that my paper with Ben
gives on the first prime progression of length k. As it turns out our bound is reasonably
poor, but is still a tower of bounded height; more precisely, the primes
that occur in the first progression have size at most
2^2^2^2^2^2^2^2^(100k). Basically
this means that we lose a logarithm or an exponential about eight times in
the argument, but fortunately we never have to iterate an argument k or
more times which loses an exponential or more at each step, so we never
see large towers or Ackermann functions.
Still, the bound is pretty bad, considering that one eventually
expects the bound to be like 2^O(k log log k) or so. The calculation is somewhat “back
of the envelope” so I don’t vouch for its perfect accuracy
here, but it should be ballpark :-).
May 31, 2004
- Uploaded:
“Restriction
theory of the Selberg Sieve, with applications”, joint with Ben
Green. This is another
“prequel” to our paper on long progressions in the primes,
which may help explain more of the context we were working in. Here we were revisiting Ben’s
paper establishing the analogue of Roth’s theorem in the primes,
developing the approach of not studying the primes directly, but rather
thinking of them instead as a rather generic dense subset of a much more
well understood set of “almost primes”, which is pseudorandom
except for irregularities in small residue classes (or on major arcs, in
Fourier space), which can be eliminated by the “W-trick” of
passing to a coset in the small divisors; this is of course the philosophy
which underpins the long progressions paper. Here, though, we use the Selberg sieve
instead of the truncated divisor sums of Goldston and Yildirim to weight
the almost primes, as the Selberg sieve has better Fourier properties
(though the divisor sums have better combinatorial properties). As such we give a simpler proof of the
results in Ben’s paper, including restriction and Hardy-Littlewood
majorant estimates for the Selberg sieve, not just for the (almost) primes
but more generally for any sieve corresponding to a polynomial, e.g. the
sieve used to create almost twin primes.
As such we reprove Roth’s theorem in pseudorandom sets such
as the almost primes and the almost twin primes; in particular, using
Chen’s theorem that there are infinitely many Chen primes (primes p
such that p+2 is the product of at most two primes), we establish
infinitely many progressions of three Chen primes (and similarly we would
have infinitely many progressions of three twin primes, if the twin prime
conjecture was proven with the expected density of ~ 1/log^2 N). The methods here are based on Fourier
analysis (the circle method) rather than ergodic theory, and are thus
closer to traditional analytic number theory (and with harmonic analysis,
in particular Tomas-Stein restriction theory) than the long progressions
paper. Nevertheless, even if the
specific tools are different, the basic strategy is the same –
namely, using the pseudorandomness of the almost primes majorizing the
primes to decompose a normalized counting function of the primes (basically
the Von Mangoldt function) into a bounded component (constructed from the
large Fourier coefficients rather than by ergodic theory) and a
pseudorandom remainder (where the pseudorandomness is measured by small
Fourier coefficients rather than Gowers uniformity norms). This paper is fairly self-contained, and
we describe the Selberg sieve in detail (in particular reproducing some
estimates of Ramare and Ruzsa on the Fourier coefficients of this sieve);
as such it might be a good introduction to this sieve for harmonic
analysts.
- Uploaded: The short story: “The
Skolem-Mahler-Lech theorem”.
I encountered this pretty and classical theorem describing the
zeroes of exponential polynomials after some conversations with Tom
Lenagan and Kousha Etessami; this short story arose from my notes in
trying to understand this theorem.
May 22, 2004
- Updated:
The short story “A quantitative
proof of Wiener’s theorem”. I now give a quantitative bound for the
l^1 norm of the convolution inverse of an absolutely summable sequence f,
in terms of the l^1 norm of f, the minimum size of its Fourier transform,
and the width of the interval which contains the bulk of the l^1 mass of
f.
May 10, 2004
- Uploaded:
“A
quantitative ergodic theory proof of Szemeredi’s theorem”,
submitted. Electron. J. Combin.
This project predates my collaboration with Ben, but got stuck
about halfway through on technicalities.
Nevertheless, what partial progress I had made already on this
paper turned out to be essential to the primes project, and then once the
primes paper was written up, enough of the technicalities had been cleared
away, and enough insights gained on how to make ergodic theory
quantitative, so I was able to return to this paper and finish it
correctly. This paper started when
I was trying (with the help of Roman Sasyk) to understand how
Furstenberg’s ergodic theory proof of Szemeredi’s theorem
really worked. I was in particular
seeking to what extent the axiom of choice could be removed from that
proof, and whether a quantitative bound could be extracted. The task was then to translate the
ergodic theory concepts such as weakly mixing systems, almost periodic
functions, and sigma algebras into a finitary setting such as Z/NZ. Weak mixing was easy to translate
– it was clear from the start that the Gowers uniformity norms were
the key here. For almost periodic
functions, I had got as far as figuring out that dual functions would be
involved, but couldn’t take it any further than that. The finitary analogue of sigma algebras
took me much longer to work out – though the answer, obvious in
retrospect, was again a sigma algebra (i.e. a partition of Z/NZ), although
now one could not insist on the shift-invariance of these algebras and had
to rely on some sort of approximate shift invariance instead. These were enough clues to push Ben’s
prime progressions argument from length 4 to arbitrary length; in so
doing, we realized that the almost periodic functions should be forming
some sort of algebra, and with that clue I was able to figure out what the
correct definition of almost periodicity, and higher order analogues of
this concept, should be. I was
still stuck for a while as to how to prove recurrence for almost periodic
functions of higher order, but by this point Ben and I had connected
Szemeredi’s regularity lemma to this ergodic theory business (see the expository note below)
and the energy-increment strategy one could extract from that lemma turned
out to be the key. Also I had found
in a later paper of Bergelson and Leibman a simpler proof of recurrence
for almost periodic functions than the original proof which relies on Van
der Waerden’s theorem, and which is replicated here.
- Anyway,
about this paper. What I do here is
convert Furstenberg’s ergodic theory proof into a finitary setting,
working entirely in Z/NZ. This then
gives a completely elementary proof of Szemeredi’s theorem that
every subset of the integers of positive density contains arbitrarily long
arithmetic progressions. As
written, the paper is not short – it stands at 51 pages, which
actually five pages longer than Szemeredi’s original proof (and
about twice as long as Furstenberg’s proof, though only half as long
as Gowers’). However,
conceptually it is much simpler, and most of the length of the paper is
discussion and commentary, relating this proof to the other four known
proofs of Szemeredi’s theorem.
(A compressed version of the paper, measuring in at just 20 pages
but still containing a complete proof, can be found here.) Structurally, the proof splits into
three fairly independent parts: a generalized von Neumann ergodic
theorem, asserting that Gowers-uniform errors of order k-1 are
negligible for the purposes of counting arithmetic progressions of length
k; a structured recurrence theorem, establishing recurrence of
arbitrary length for almost periodic functions of order k-2 (allowing for
a moderately large L^2 error); and a structure theorem decomposing
an arbitrary function into an almost periodic part of order k-2, a very
Gowers-uniform part, and a moderately large L^2 error. Also, there is quite a lot of overlap
with the primes paper as far as shared concepts and strategies are
concerned, so if you read this paper then you will find the primes paper
much easier going (and perhaps understand the context and motivation for
our arguments), and vice versa.
(Combined, the two papers form an almost entirely self-contained
proof that the primes contain arbitrarily long arithmetic progressions,
except for the fact that we still need to use some basic facts about the
Riemann zeta function, plus a few other odds and ends such as the
Weierstrass approximation theorem).
This paper also highlights the connections and contrasts between
the other proofs of Szemeredi’s theorem, and may serve to clarify
exactly why such a theorem is (a) so hard to prove, (b) has so many
completely different proofs, and (c) why all the proofs seem to involve
this dichotomy between randomness and structure.
Apr 22, 2004
- Uploaded:
The expository note “An
information-theoretic proof of Szemeredi’s regularity lemma”. This note is intended in part to explain
some of the context that Ben and I were operating in when we worked out
our result about arbitrarily long progressions in the primes (there will
be some further papers establishing more context shortly, though arguably
our project originates in Ben’s proof of
Roth’s theorem in the primes).
Before we worked on the primes, we worked on understanding
Szemeredi’s theorem, and in particular the four apparently quite
distinct proofs of this theorem in the literature (the combinatorial and
graph-theoretic proof of Szemeredi; the probabilistic, measure-theoretic
and ergodic theoretic proof of Furstenberg; the combinatorial and Fourier
analytic proof of Gowers; and the more recent hypergraph proof of Gowers
and of Frankl and Rodl). As will
hopefully become clear with this note and the papers to follow, in order
to establish the result concerning the primes we had to understand all
four proofs, and how they were related, in order that we could blend
aspects of each in order to attack the primes. Specifically, the primes result needed
to combine the uniformity norms from Gowers Fourier work, with the
relativization to pseudorandom objects which was implicit in Gowers
hypergraph work, with the conditional expectation machinery from
Furstenberg’s work, with the regularity lemma algorithm from
Szemeredi’s work (and all four then had to be combined with the
Goldston-Yildirim result on the pseudorandomness of the almost
primes). At first glance it is not
obvious that one should be combining these five tools at all; however,
this note (and the ones to follow) will show how we discovered that
individual pairs of these tools were connected to each other. In this note we connect the conditional
expectation machinery of Furstenberg with the regularity lemma machinery
of Szemeredi to give an “information-theoretic” proof of
Szemeredi’s famous regularity lemma which gives a structural
description of an arbitrary dense graph with a very large number of
vertices. The proof is based on the
following fundamental dichotomy, which recurs through all of the papers
mentioned above: either an object is random, or it has structure. If it is random, then we are done;
otherwise, “mod out” that structure and pass to the residual
object. Here, our mechanism for
“modding out” structure is the language of conditional
expectation, as in Furstenberg’s work. However, to ensure that our algorithm
terminates in finite time we need the L^2 incrementation argument of
Szemeredi. These two tools are both
key in our primes paper, but appear here in a simplified context and may
help to elucidate part of the motivation for our primes argument.
Apr 9, 2004
- Uploaded:
“The primes
contain arbitrarily long arithmetic progressions”, joint with
Ben Green, submitted to Annals of Mathematics. In this paper we establish that for any
integer k >= 3, there exist infinitely many arithmetic progressions of
prime numbers of length k (in fact, we show that the number of such progressions
up to any large integer N is comparable to N / log^k N). This is new for k >= 4. This has been a fascinating and
educational joint project, taking many detours and containing a number of
very satisfying breakthroughs. Our
starting point was not to study the structure of the primes directly, but
rather to think of them as a dense subset of a slightly larger set, namely
the almost primes (which are much easier to study, for instance by sieve
theory methods). One is then
inspired to look at Szemeredi’s theorem, which asserts that a dense
subset of {1,...,N} will contain progressions of length k if N is large
enough depending on k and the density.
Our first approach was to look at the first open case k=4, modify
the arguments used to prove Szemeredi’s theorem (and in particular
the arithmetic combinatorial and Fourier analytic arguments of Gowers) to
then handle dense subsets of the almost primes (as was recently done for
progressions of length 3 by Ben).
This approach bore some fruit, but at the end of the day we were
faced with estimating some unappetizing quadratic exponential sums over
the primes. At this point, the next
conceptual breakthrough was to punt the whole issue of whether these sums
were controllable or not, and instead average out all the quadratic bias
(if any) from the primes using quadratic Bohr sets (similar ideas had
already been carried out in the k=3 case by Bourgain). (An intermediate strategy, to restrict
to the quadratic Bohr sets rather than average over them, was abandoned as
being even more complicated than the strategy it was intended to
supercede). At this point we were
nearing the end of the k=4 problem, but we then noticed a suspicious
similarity between our arguments and the ergodic theory proofs of
Szemeredi’s theorem, as carried out by Furstenberg and later
authors. After some work we were
able to abstract away the properties of quadratic Bohr sets, replacing
them instead by more ergodic objects.
This opened up the case of general k and also simplified the
argument substantially by removing all the Fourier analytic and arithmetic
combinatorial aspects of the proof, giving the argument the flavour of
“quantitative ergodic theory”.
However, there was one final obstruction, which was that the
pseudorandomness properties we needed for the almost primes were now a bit
stronger than what one could get from the standard Selberg sieve (we now
needed error estimates which were not only small, but in fact went to zero
as N went to infinity). This
obstruction was resolved by a fortuitous conversation with Andrew
Granville, who suggested we look at the recent works of Goldston and
Yildirim on correlation estimates for the almost primes. This turned out to be almost exactly the
device needed to finally finish the proof for general k. In the end, the final argument manages
to avoid the technical components of either Gowers’ proof or
Furstenberg’s proof of Szemeredi’s theorem, instead simply
using that theorem as a black box, and also manages to avoid the deeper
aspects of analytic number theory (the Goldston-Yildirim method relies
only on classical estimates for the Riemann zeta function). Conceptually it is very close to recent
developments in the ergodic theory of recurrence, in particular the
discovery of rather explicit characteristic factors (k-2 step nilmanifolds)
for such tasks as counting arithmetic progressions of length k. In the ergodic theory language, our
argument can be summarized as the statement that any dense subset of a
pseudorandom set (e.g. the primes as a dense subset of the almost primes)
will, when projected onto this characteristic factor, become a very
uniformly distributed function, which can then be handled by the ordinary
Szemeredi theorem. However while
our final argument is heavily inspired by ergodic theory arguments, it
does not directly use ergodic theory (in particular it does not require
the axiom of choice or any analysis on infinite measure spaces). There have been a number of spinoffs
from this project which will also appear shortly.
Mar 19, 2004
Mar 10, 2004
Feb 8, 2004
- Uploaded:
“Global
well-posedness and scattering in the energy space for the critical
nonlinear Schrodinger equation in R^3”, joint with Jim Colliander, Mark Keel, Gigliola
Staffilani, and Hideo Takaoka, submitted to Annals of
Mathematics. This has been our
largest joint project, spanning roughly two years, and went under the
codename “Project Gopher” since a key portion of the research
was carried out at the University
of Minnesota, which
has a gopher as its mascot. In this
paper we establish global existence, regularity, uniqueness, and
scattering for the quintic (i.e. energy-critical) defocusing non-linear
Schrodinger equation in R^3 for large data. For small data these results are a
well-known consequence of perturbation arguments, and for large data one
can similarly use perturbation methods to construct local solutions; the
difficulty is to ensure that the solution does not blow up in finite time. In the spherically symmetric case this
was achieved by Bourgain and Grillakis independently, using Morawetz type
estimates to prevent (certain types of) concentration near the origin,
combined with some further analysis of the mass density to eliminate the remaining
blowup scenarios. In
Bourgain’s argument an innovative new “induction on
energy” argument was also introduced to deal with the case of
sporadic concentrations. In our
work we replace the Morawetz estimate by an interaction Morawetz
inequality, used in the sub-critical setting in our earlier work;
the reason for this is that the interaction Morawetz inequality is not
localized to near the spatial origin.
However, this inequality has the wrong scaling to be directly
applicable for the critical setting, so we must work instead with a
frequency-localized variant (establishing this variant is one of the most
technical parts of the argument).
Even with this inequality, which prevents certain types of
concentration, we are not done yet; there are several other concentration
scenarios that need to be excluded.
To do this we first re-interpret Bourgain’s induction on
energy argument as a method for obtaining structural information on a
putative minimal-energy blowup solution.
Specifically, we use this method to show that any such
minimal-energy blowup solution must remain localized in both space and
frequency for each time, and also to verify a certain reverse Sobolev
inequality. Such localizations are
necessary in order to prove the frequency-localized interaction Morawetz
inequality. Combining these two
tools, we are faced with eliminating one last scenario, that of an
“energy evacuation” where the solution starts off at a low
frequency but eventually shifts almost all of its energy into the very
high frequencies (and in particular, the high frequencies will lose almost
all their mass). To show this
scenario does not actually occur, we use a variant of our
“I-method”, showing that the frequency-localized mass cannot
fluctuate in the manner described above.
- Uploaded:
“Global
well-posedness and scattering for the higher-dimensional energy-critical
non-linear Schrodinger equation for radial data”, submitted to
the New York Journal of Mathematics.
This is a spin-off of the above paper, where we consider higher
dimensions but only in the radial case.
The four-dimensional case was already considered by Bourgain, using
the induction on energy argument mentioned above. Here we revisit that argument and remove
the induction on energy step (which was used to eliminate sporadic
concentration scenarios), relying instead on Duhamel’s principle and
a certain smoothing property of the fundamental solution. In doing so we manage to extend the
argument to general dimension, and also to improve the final global
spacetime bounds for the solution substantially (to be exponential in the
energy rather than tower-exponential).
Note that in five and higher dimensions the nonlinearity is not
smooth and hence is not particularly amenable to Littlewood-Paley
analysis; instead we use Holder spaces to analyze our various fields. In six and higher dimensions there is an
additional technical difficulty as the nonlinearity becomes quadratic or
subquadratic which makes the naive perturbation theory (in which smallness
of a certain spacetime norm with no derivatives implies smallness of all
other Strichartz norms) much more delicate, requiring a nontrivial amount of
harmonic analysis (in particular, knowledge of when Sobolev’s
inequality is close to being sharp) to resolve.