## What's new:

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.