You are currently browsing the monthly archive for April 2009.

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 {k=3} case. The theorem to prove is then

Theorem 1 ({k=3} density Hales-Jewett theorem) Let {0 < \delta \leq 1}. Then if {n} is a sufficiently large integer, any subset {A} of the cube {[3]^n = \{1,2,3\}^n} of density {|A|/3^n} at least {\delta} contains at least one combinatorial line {\{ \ell(1), \ell(2), \ell(3)\}}, where {\ell \in \{1,2,3,x\}^n \backslash [3]^n} is a string of {1}s, {2}s, {3}s, and {x}‘s containing at least one “wildcard” {x}, and {\ell(i)} is the string formed from {\ell} by replacing all {x}‘s with {i}‘s.

The full density Hales-Jewett theorem is the same statement, but with {[3]} replaced by {[k]} for some {k \geq 1}. (The case {k=1} is trivial, and the case {k=2} 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 {k=3} case only, and gave only part of the proof in detail, but in a subsequent paper a full proof in general {k} was provided. The remaining components of the original {k=3} argument were later completed in unpublished notes of McCutcheon. One of the new proofs is essentially a finitary translation of this {k=3} argument; in principle one could also finitise the significantly more complicated argument of Furstenberg and Katznelson for general {k}, but this has not been properly carried out yet (the other two proofs are likely to generalise much more easily to higher {k}). The result is considered quite deep; for instance, the general {k} 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 {k=3} case of the density Hales-Jewett theorem). A key new idea involved studying the correlations of the original set {A} with special subsets of {[3]^n}, such as {ij}-insensitive sets, or intersections of {ij}-insensitive and {ik}-insensitive sets. Work is currently ongoing to extend this argument to higher {k}, 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 {k} 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 {k=3} case has been sketched out; I believe it also extends in a relatively straightforward manner to the higher {k} case (in analogy with some proofs of the hypergraph removal lemma ).

Read the rest of this entry »