The polymath project

Tim Gower’s experiment in massively collaborative mathematics is now underway. He’s dubbed it the “polymath project” – if you want to see posts related to the project, I suggest looking here.

The problem to be attacked can be understood (though probably not solved) with only a little undergraduate mathematics. It concerns a result known as the Density Hales-Jewett theorem. This theorem asks us to consider the set [tex][ 3 ]^n[/tex] of all length [tex]n[/tex] strings over the alphabet [tex]1, 2, 3[/tex]. So, for example, [tex]11321[/tex] is in [tex][3]^5[/tex]. The theorem concerns the existence of combinatorial lines in subsets of [tex][3]^n[/tex]. A combinatorial line is a set of three points in [tex][3]^n[/tex], formed by taking a string with one or more wildcards in it, e.g., [tex]112*1**3\ldots[/tex], and replacing those wildcards by [tex]1[/tex], [tex]2[/tex] and [tex]3[/tex], respectively. In the example I’ve given, the resulting combinatorial line is:

[tex] \{ 11211113\ldots, 11221223\ldots, 11231333\ldots \} [/tex]

The Density Hales-Jewett theorem asserts that for any [tex]\delta > 0[/tex], for sufficiently large [tex]n = n(\delta)[/tex], all subsets of [tex][3]^n[/tex] of size at least [tex]\delta 3^n[/tex] contain a combinatorial line,

Apparently, the original proof of the Density Hales-Jewett theorem used ergodic theory; Gowers’ challenge is to find a purely combinatorial proof of the theorem. More background can be found here. Serious discussion of the problem starts here.