Michael Nielsen

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 of all length strings over the alphabet . So, for example, is in . The theorem concerns the existence of combinatorial lines in subsets of . A combinatorial line is a set of three points in , formed by taking a string with one or more wildcards in it, e.g., , and replacing those wildcards by , and , respectively. In the example I’ve given, the resulting combinatorial line is:

The Density Hales-Jewett theorem asserts that for any , for sufficiently large , all subsets of of size at least 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.