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 ).