The polymath1 project has just uploaded to the arXiv the paper “A new proof of the density Hales-Jewett theorem“, to be submitted shortly. Special thanks here go to Ryan O’Donnell for performing the lion’s share of the writing up of the results, and to Tim Gowers for running a highly successful online mathematical experiment.

I’ll state the main result in the first non-trivial case for simplicity, though the methods extend surprisingly easily to higher (but with significantly worse bounds). Let be the size of the largest subset of the cube that does not contain any combinatorial line. The density Hales-Jewett theorem of Furstenberg and Katznelson shows that . In the course of the Polymath1 project, the explicit values

were established, as well as the asymptotic lower bound

(actually we have a slightly more precise bound than this). The main result of this paper is then

**Theorem.** ( version) .

Here is the inverse tower exponential function; it is the number of times one has to take (natural) logarithms until one drops below 1. So it does go to infinity, but extremely slowly. Nevertheless, this is the first explicitly quantitative version of the density Hales-Jewett theorem.

The argument is based on the density increment argument as pioneered by Roth, and also used in later papers of Ajtai-Szemerédi and Shkredov on the corners problem, which was also influential in our current work (though, perhaps paradoxically, the generality of our setting makes our argument *simpler* than the above arguments, in particular allowing one to avoid use of the Fourier transform, regularity lemma, or Szemerédi’s theorem). I discuss the argument in the first part of this previous blog post.

I’ll end this post with an open problem. In our paper, we cite the work of P. L. Varnavides, who was the first to observe the elementary averaging argument that showed that Roth’s theorem (which showed that dense sets of integers contained at least one progression of length three) could be amplified (to show that there was in some sense a “dense” set of arithmetic progressions of length three). However, despite much effort, we were not able to expand “P.” into the first name. As one final task of the Polymath1 project, perhaps some readers with skills in detective work could lend a hand in finding out what Varnavides’ first name was? *Update, Oct 22:* Mystery now solved; see comments.

### Like this:

Like Loading...

## 10 comments

Comments feed for this article

22 October, 2009 at 3:21 pm

Thomas SauvagetIt’s great to see the project worked out so well!

As for Varnavides, it seems the name is Panaylotis L Varnavides, born in 1912, then B.A. in Athens, then PhD at University College in London in 1948, see this excerpt of a British Who’s Who on Google Books (was indeed a bit hard to find).

22 October, 2009 at 3:30 pm

Thomas SauvagetOops, on second reading it’s Panayiotis L Varnavides (i not l), apologies.

22 October, 2009 at 5:57 pm

Ryan O'DonnellAmazing, nice find!

22 October, 2009 at 4:29 pm

Klas MarkströmThis reminds me that I have a bit of writing to do for the second polymath paper. But it will have to wait until I get back to Sweden.

What is the general status of the second paper now?

22 October, 2009 at 4:45 pm

Polymath paper up on ArXiV « An Ergodic Walk[…] Posted by asarwate under Uncategorized | Tags: mathematics, web | Leave a Comment From Terence Tao’s blog, I see that they have finished writing the first polymath project on A new proof of the density […]

22 October, 2009 at 5:55 pm

Terence TaoThomas: Thanks for the speedy detective work!

Klas: Well, we have a series of drafts at

http://michaelnielsen.org/polymath1/index.php?title=Outline_of_second_paper

the most recent one being dated July 25. We have a deadline of April to submit it for the forthcoming Szemeredi birthday conference proceedings, so there is plenty of time still to refine it. You are of course welcome to make any corrections to the source files that you spot… in a month or two I may try to more actively shepherd this project towards completion.

22 October, 2009 at 6:01 pm

Ryan O'DonnellBy the way, I noticed today that I botched a trivial calculation, and our main theorem is actually very slightly better: .

[Updated, thanks – T.]23 October, 2009 at 12:46 pm

Andreas VarnavidesYes his first name was Panayiotis, born in Paphos Cyprus. He was my uncle

24 October, 2009 at 10:52 pm

Mathematics, Science, and Blogs « Combinatorics and more[…] in the new proof and the only reference to his first name was the initial P. ) Terry Tao asked it on his blog and in a short time the mystery was resolved when Thomas Sauvaget found the answer. The next […]

7 January, 2012 at 5:53 am

Réenchanter la science, collectivement | Matières Vivantes[…] la discussion en commentaires sur la meilleure façon de les résoudre collectivement. Le premier projet Polymath résolu a été mis sur l’arXiv en Octobre […]