“Density Hales-Jewett and Moser numbers” – nearing the final draft

After a hiatus of several months, I’ve made an effort to advance the writing of the second Polymath1 paper, entitled “Density Hales-Jewett and Moser numbers“.  This is in part due to a request from the Szemeredi 60th 70th birthday conference proceedings (which solicited the paper) to move the submission date up from April to February.  (Also, the recent launch of Polymath5 on Tim Gowers blog reminds me that I should get this older project out of the way.)

The current draft of the paper is here, with source files here.  I have been trimming the paper, in particular replacing some of the auxiliary or incomplete material in the paper with references to pages on the polymath wiki instead.  Nevertheless this is still a large paper, at 51 pages.  It is now focused primarily on the computation of the Density Hales-Jewett numbers and the Moser numbers for all n up to 6, with the latter requiring a significant amount of computer assistance.

There are a number of minor issues remaining with the paper:

1. A picture of a Fujimura set for the introduction would be nice.
2. In the proof of Theorem 1.3 (asymptotic lower bound for DHJ numbers), it is asserted without proof that the circulant matrix with first row 1,2,…,k-1 is nonsingular.  One can prove this claim by computing the Fourier coefficients for all t, but is there a slicker way to see this (e.g. by citing a reference?).
3. Reference [15] (which is Komlos’s lower bound on the Moser numbers) is missing a volume number.  The reference is currently given as
   J. Komlos, solution to problem P.170 by Leo Moser, Canad. Math.. Bull. vol  ???  (1972), 312-313, 1970.

Finally, the text probably needs to be proofread one or two more times before it is ready to go, hopefully by early February.  There is still also one last opportunity to propose non-trivial restructuring of the paper (in particular, if there are other ways to trim the size of the paper, this may be worth looking into).

Two quick updates

1. In a previous post, I noted John Baez’s thread discussing his incipient article for the Notices of the AMS, entitled “What do mathematicians need to know about blogging?”.  John has now completed an initial draft of his article and is welcoming comments on it here. [Update, Oct 2: the article has now been submitted, incorporating much of the feedback.]
2. In another previous post, I talked about the forthcoming Google Wave platform being developed currently by Google, and its potential usefulness for online mathematical collaborative projects, such as the polymath projects.  My brother, who is one of the developers for this project, has just informed me that there are now a limited number of invites available to others who would like to develop specific Wave extensions or other projects (see for instance his own blog post, aimed at the GNOME community).  As I understand it, the Wave platform is not yet ready for general use, so these invites would be intended for technical developers (or preferably, a group of developers) who would be working on specific projects.  (For instance, I understand that there is already a preliminary extension for encoding LaTeX in a Wave, but it could be developed further.)  If any readers are interested, one can request an invite directly from the Google Wave page, or I can forward requests to my brother.  [At some point, I may ask for help in trying to build a Wave platform for the next generation of Polymath projects, but this will probably not occur for several months yet, due to a large number of other things on my plate (including existing Polymath projects).]

“Poincaré’s legacies” now published

My two-volume book, “Poincaré’s legacies: pages from year two of a mathematical blog“, which was based on the 2008 posts of this blog, has now been published by the American Mathematical Society.

[Update, Aug 3: Actually, only the first volume has been published so far.  The second volume of this book will be available on Aug 10.]

A draft version of the blog book

A few months ago, I announced that I was going to convert a significant fraction of my 2007 blog posts into a book format. For various reasons, this conversion took a little longer than I had anticipated, but I have finally completed a draft copy of this book, which I have uploaded here; note that this is a moderately large file (1.5MB 1.3MB 1.1MB), as the book is 374 pages 287 pages 270 pages long. There are still several formatting issues to resolve, but the content has all been converted.

It may be a while before I hear back from the editors at the American Mathematical Society as to the status of the book project, but in the meantime any comments on the book, ranging from typos to suggestions as to the format, are of course welcome.

[Update, April 21: New version uploaded, incorporating contributed corrections. The formatting has been changed for the internet version to significantly reduce the number of pages. As a consequence, note that the page numbering for the internet version of the book will differ substantially from that in the print version.]

[Update, April 21: As some readers may have noticed, I have placed paraphrased versions of some of the blog comments in the book, using the handles given in the blog comments to identify the authors. If any such commenters wish to change one's handle (e.g. to one's full name) or to otherwise modify or remove any comments I have placed in the book, you are welcome to contact me by email to do so.]

[Update, April 23: Another new version uploaded, incorporating contributed corrections and shrinking the page size a little further.]

[Update, May 8: A few additional corrections to the book.]

The Dantzig selector: Statistical estimation when p is much larger than n

Over two years ago, Emmanuel Candés and I submitted the paper “The Dantzig selector: Statistical estimation when is much
larger than ” to the Annals of Statistics. This paper, which appeared last year, proposed a new type of selector (which we called the Dantzig selector, due to its reliance on the linear programming methods to which George Dantzig, who had died as we were finishing our paper, had contributed so much to) for statistical estimation, in the case when the number of unknown parameters is much larger than the number of observations. More precisely, we considered the problem of obtaining a reasonable estimate for an unknown vector of parameters given a vector of measurements, where is a known predictor matrix and is a (Gaussian) noise error with some variance . We assumed that the predictor matrix X obeyed the restricted isometry property (RIP, also known as UUP), which roughly speaking asserts that has norm comparable to whenever the vector is sparse. This RIP property is known to hold for various ensembles of random matrices of interest; see my earlier blog post on this topic.

Our selection algorithm, inspired by our previous work on compressed sensing, chooses the estimated parameters to have minimal norm amongst all vectors which are consistent with the data in the sense that the residual vector obeys the condition

, where (1)

(one can check that such a condition is obeyed with high probability in the case that , thus the true vector of parameters is feasible for this selection algorithm). This selector is similar, though not identical, to the more well-studied lasso selector in the literature, which minimises the norm of penalised by the norm of the residual.

A simple model case arises when n=p and X is the identity matrix, thus the observations are given by a simple additive noise model . In this case, the Dantzig selector is given by the hard soft thresholding formula

The mean square error for this selector can be computed to be roughly

(2)

and one can show that this is basically best possible (except for constants and logarithmic factors) amongst all selectors in this model. More generally, the main result of our paper was that under the assumption that the predictor matrix obeys the RIP, the mean square error of the Dantzig selector is essentially equal to (2) and thus close to best possible.

After accepting our paper, the Annals of Statistics took the (somewhat uncommon) step of soliciting responses to the paper from various experts in the field, and then soliciting a rejoinder to these responses from Emmanuel and I. Recently, the Annals posted these responses and rejoinder on the arXiv:

An update on the inverse conjecture for the Gowers norm over finite fields

Recently, I had tentatively announced a forthcoming result with Ben Green establishing the “Gowers inverse conjecture” (or more accurately, the “inverse conjecture for the Gowers uniformity norm”) for vector spaces over a finite field , in the special case when p=2 and when the function for which the inverse conjecture is to be applied is assumed to be a polynomial phase of bounded degree (thus , where is a polynomial of some degree ). See my FOCS article for some further discussion of this conjecture, which has applications to both polynomiality testing and to various structural decompositions involving the Gowers norm.

This conjecture can be informally stated as follows. By iterating the obvious fact that the derivative of a polynomial of degree at most d is a polynomial of degree at most d-1, we see that a function is a polynomial of degree at most d if and only if

for all . From this one can deduce that a function bounded in magnitude by 1 is a polynomial phase of degree at most d if and only if the Gowers norm

is equal to its maximal value of 1. The inverse conjecture for the Gowers norm, in its usual formulation, says that, more generally, if a function bounded in magnitude by 1 has large Gowers norm (e.g. ) then f has some non-trivial correlation with some polynomial phase g (e.g. for some ). Informally, this conjecture asserts that if a function has biased derivatives, then one should be able to “integrate” this bias and conclude that the function is biased relative to a polynomial of degree d. The conjecture has already been proven for . There are analogues of this conjecture for cyclic groups which are of relevance to Szemerédi’s theorem and to counting linear patterns in primes, but I will not discuss those here.

At the time of the announcement, our paper had not quite been fully written up. This turned out to be a little unfortunate, because soon afterwards we discovered that our arguments at one point had to go through a version of Newton’s interpolation formula, which involves a factor of d! in the denominator and so is only valid when the characteristic p of the field exceeds the degree. So our arguments in fact are only valid in the range , and in particular are rather trivial in the important case ; my previous announcement should thus be amended accordingly.