My good friend Tim Gowers has just started an experimental “massively collaborative mathematical project” over at his blog. The project is entitled “A combinatorial approach to density Hales-Jewett“, and the aim is to see if progress can be made on this problem by many small contributions by a large number of people, as opposed to the traditional model of a few very large contributions by a small number of people (see this article for more on the “rules of the game”, and this article for why this particular project was picked as a test project). I think this is an interesting experiment, and hopefully a successful one, though it is far too early to tell as yet.
I can describe the problem here. Let n be a large integer, and let be the set of all strings of length n using the alphabet , thus for instance . A combinatorial line in is a triple of points in that can be formed by taking a string of length n using the alphabet with at least one occurrence of the “wildcard” x, and then substituting the values of 1, 2, 3 for the wildcard. For instance, the string would lead to the combinatorial line in . The (k=3) case of the density Hales-Jewett theorem of Furstenberg and Katznelson asserts:
Density Hales-Jewett theorem. Let . Then if n is sufficiently large depending on , every subset of of density at least contains a combinatorial line.
[Furstenberg and Katznelson handled the case of general k in a subsequent paper. The k=1 case is trivial, and as pointed out in this post by Gil Kalai, the k=2 case follows from Sperner’s theorem.]
Furstenberg and Katznelson’s proof uses ergodic theory, and in particular does not obviously give any bound as to how large n has to be depending on before the theorem takes effect. No other proofs of this theorem are currently known. So it would be desirable to have a combinatorial proof of the k=3 density Hales-Jewett theorem. Since this theorem implies Roth’s theorem, and Roth’s theorem has a combinatorial proof based on the triangle removal lemma (see e.g. my Simons lecture on the subject, or Tim Gowers’ background article for the project), it is thus natural to ask whether the density Hales-Jewett theorem has a proof based on something similar to the triangle removal lemma. This is basically the question being explored in the above project. (Some further motivation for this problem can be found here.)
Further articles on this project are collected at this page.
4 comments
Comments feed for this article
7 February, 2009 at 8:45 am
Upper and lower bounds for the density Hales-Jewett problem « What’s new
[…] 5 February, 2009 in math.CO | Tags: polymath1 | by Terence Tao This is a continuation of several threads from Tim Gowers’ massively collaborative mathematics project, “A combinatorial approach to density Hales-Jewett“, which I discussed in my previous post. […]
7 February, 2009 at 9:59 am
Mathematics, Science, and Blogs « Combinatorics and more
[…] blog describing the project, its rules and motivation, and interesting discussions also over What’s new and in In theory. The project itself is fairly focused; Let me mention another connection which is […]
19 February, 2009 at 4:15 pm
A quick review of the polymath project « What Is Research?
[…] from distinguished mathematicians such as Terence Tao. Tao has his own blog, and he published a post giving the background of the Hales-Jewett theorem and a later post with some of his own ideas about the […]
28 April, 2009 at 12:28 pm
Un blog concentra a cientos de matemáticos en la demostración conjunta de un teorema « Francis (th)E mule Science’s News
[…] idea del proyecto era obtener una nueva demostración del teorema de la densidad de Hales-Jewett (muy bien descrito por Terence aquí), que no hiciera uso de la teoría ergódica, necesaria en la única demostración conocida hasta […]