Polymath1 and three new proofs of the density Hales-Jewett theorem

This week I gave a talk at UCLA on some aspects of polymath1 project, and specifically on the three new combinatorial proofs of the density Hales-Jewett theorem that have been obtained as a consequence of that project. (There have been a number of other achievements of this project, including some accomplished on the polymath1 threads hosted on this blog, but I will have to postpone a presentation of those to a later post.) It seems that at least two of the proofs will extend to prove this theorem for arbitrary alphabet lengths, but for this talk I will focus on the case. The theorem to prove is then

Theorem 1 ( density Hales-Jewett theorem) Let . Then if is a sufficiently large integer, any subset of the cube of density at least contains at least one combinatorial line , where is a string of s, s, s, and ‘s containing at least one “wildcard” , and is the string formed from by replacing all ‘s with ‘s.

The full density Hales-Jewett theorem is the same statement, but with replaced by for some . (The case is trivial, and the case follows from Sperner’s theorem.)

This theorem was first proven by Furstenberg and Katznelson, by first converting it to a statement in ergodic theory; the original paper of Furstenberg-Katznelson argument was for the case only, and gave only part of the proof in detail, but in a subsequent paper a full proof in general was provided. The remaining components of the original argument were later completed in unpublished notes of McCutcheon. One of the new proofs is essentially a finitary translation of this argument; in principle one could also finitise the significantly more complicated argument of Furstenberg and Katznelson for general , but this has not been properly carried out yet (the other two proofs are likely to generalise much more easily to higher ). The result is considered quite deep; for instance, the general case of the density Hales-Jewett theorem already implies Szemerédi’s theorem, which is a highly non-trivial theorem in its own right, as a special case.

Another of the proofs is based primarily on the density increment method that goes back to Roth, and also incorporates some ideas from a paper of Ajtai and Szemerédi establishing what we have called the “corners theorem” (and which is also implied by the case of the density Hales-Jewett theorem). A key new idea involved studying the correlations of the original set with special subsets of , such as -insensitive sets, or intersections of -insensitive and -insensitive sets. Work is currently ongoing to extend this argument to higher , and it seems that there are no major obstacles in doing so.

This correlations idea inspired a new ergodic proof of the density Hales-Jewett theorem for all values of by Austin, which is in the spirit of the triangle removal lemma (or hypergraph removal lemma) proofs of Roth’s theorem (or the multidimensional Szemerédi theorem). A finitary translation of this argument in the case has been sketched out; I believe it also extends in a relatively straightforward manner to the higher case (in analogy with some proofs of the hypergraph removal lemma ).