Intro.tex

\begin{abstract} The Hales-Jewett theorem asserts that for every $r$ and every $k$ there exists $n$ such that every colouring of the $n$-dimensional grid $[k]^n$ contains a combinatorial line. This result is a generalization of van der Waerden's theorem, and it is one of the fundamental results of Ramsey theory. The van der Waerden's theorem has a famous density version, conjectured by Erd\H os and Tur\'an in 1936, proved by Szemer\'edi in 1975 and given a different proof by Furstenberg in 1977. The Hales-Jewett theorem has a density version as well, proved by Furstenberg and Katznelson in 1991 by means of a significant extension of the ergodic techniques that had been pioneered by Furstenberg in his proof of Szemer\'edi's theorem. In this paper, we give the first purely combinatorial proof of the theorem of Furstenberg and Katznelson. The proof is surprisingly simple: indeed, it gives what is probably the simplest known proof of Szemer\'edi's theorem. \end{abstract}

\section{Introduction}

The purpose of this paper is to give the first fully combinatorial proof of a theorem of Furstenberg and Katznelson that has the same relation to the Hales-Jewett theorem as Szemer\'edi's theorem has to van der Waerden's theorem. Before we go any further, let us state all four theorems. We shall use the notation $[k]$ to stand for the set $\{1,2,\dots,k\}$ (or sometimes, particularly when $k$ is small, for the set $\{0,1,\dots,k-1\}$). If $X$ is a set and $r$ is a positive integer, then an $r$-\textit{colouring} of $X$ will mean a function $\kappa:X\rightarrow C$ for some set $C$ of size $r$. A subset $Y$ of $X$ is called \textit{monochromatic} if $\kappa(y)$ is the same for every $y\in Y$.

First, let us state van der Waerden's theorem and Szemer\'edi's theorem.

\begin{theorem} \label{vdw} For every pair of positive integers $k$ and $r$ there exists $N$ such that for every $r$-colouring of $[N]$ there is a monochromatic arithmetic progression of length $k$. \end{theorem}

\begin{theorem}\label{szem} For every positive integer $k$ and every $\delta>0$ there exists $N$ such that every subset $A\subset[N]$ of size at least $\delta N$ contains an arithmetic progression of length $k$. \end{theorem}

It is usually better to focus on the \textit{density} $|A|/N$ of a subset $A\subset[N]$ than on its cardinality, since this gives us a parameter that we can think of independently of $N$. Szemer\'edi's theorem is often referred to as \textit{the density version} of van der Waerden's theorem.

To state the Hales-Jewett theorem, we need a little more notation. Let $x=(x_1,\dots,x_n)$ be an element of $[k]^n$, let $W\subset[n]$ and let $j\in[k]$. Let us write $x\oplus jW$ for the sequence $(y_1,\dots,y_n)$ such that $y_i=x_i$ if $i\notin A$ and $y_i=j$ if $i\in A$. That is, we take the sequence $x$ and overwrite the terms with index in $W$ with a $j$. For example, if $k=3$, $n=5$, then \begin{equation*} (1,1,3,2,1)+2\{1,4,5\}=(2,1,3,2,2). \end{equation*} The \textit{combinatorial line} $x\oplus[k]W$ is the set $\{x\oplus jW:j\in [k]\}$. For instance, \begin{equation*} (1,1,3,2,1)\oplus[3]\{1,4,5\}=\{(1,1,3,1,1),(2,1,3,2,2),(3,1,3,3,3)\}. \end{equation*} It may seem strange that the combinatorial line $x\oplus [k]W$ does not depend on the values of $x_i$ with $i\in A$, but this turns out to be a useful convention and makes it possible to state results in a concise way.

We are now ready to state the Hales-Jewett theorem. \begin{theorem}\label{hj} For every pair of positive integers $k$ and $r$ there exists $n$ such that for every $r$-colouring of the set $[k]^n$ there is a monochromatic combinatorial line. \end{theorem} The theorem of Furstenberg and Katznelson that we shall prove in a different way in this paper is the following density version of the Hales-Jewett theorem. \begin{theorem}\label{dhj} For every $k$ and every $\delta>0$ there exists $n$ such that every subset of $[k]^n$ of size at least $\delta k^n$ contains a combinatorial line. \end{theorem}

Why is it interesting to give a new proof of this result? There are two main reasons. The first is connected with the history of results in this area. One of the main benefits of Furstenberg's proof of Szemer\'edi's theorem was that it introduced a technique that could be developed in many directions, which did not seem to be the case with Szemer\'edi's proof. As a result, many far-reaching generalizations of Szemer\'edi's theorem were proved, and for a long time nobody could prove them in any other way than by using Furstenberg's methods. In the last few years that has changed, and a programme has developed to find new and finitary proofs of the results that were previously known only by infinitary ergodic methods. Giving a non-ergodic proof of the density Hales-Jewett theorem was seen as a key goal for this programme: on the ergodic side it appeared to be significantly harder than Szemer\'edi's theorem, and this seemed to be reflected by certain significant combinatorial difficulties that we shall discuss later in this paper.

A second reason is that the density Hales-Jewett theorem implies Szemer\'edi's theorem, and finding a new proof of Szemer\'edi's theorem seems always to be illuminating---or at least this has been the case for the four main approaches discovered so far. In retrospect, one can add to this the fact that the proof we have discovered is, against all our expectations, \textit{simpler} than the previous approaches to Szemer\'edi's theorem: it seems that by looking at a more general problem we have removed some of the difficulty. Related to this is another surprise. We started out by trying to prove the first difficult case of the theorem, which is when $k=3$. The experience of all four of the earlier proofs of Szemer\'edi's theorem has been that interesting ideas are needed to prove results about progressions of length $3$, but significant extra difficulties arise when one tries to generalize an argument from the length-$3$ case to the general case. However, it turned out that once we had proved the case $k=3$ of the density Hales-Jewett theorem, it was straightforward to generalize the argument to the general case. We still do not have a convincing explanation of why our proof should differ from all the others in this respect.

Here, briefly, is how to deduce Szemer\'edi's theorem from the density Hales-Jewett theorem. Given $k$ and $\delta$, let $n$ be such that the density Hales-Jewett theorem holds for $k$ and $\delta$ and let $N=k^n$. Thinking of $[k]$ as the set $\{0,1,\dots,k-1\}$ and $[N]$ as the set $\{0,1,\dots,N-1\}$, let $\phi:[k]^n\rightarrow[N]$ be the map that takes the sequence $(x_1,\dots,x_n)$ to the number $x_1+x_2k+x_3k^2+\dots+x_nk^{n-1}$, and note that $\phi$ is a bijection. Now let $A\subset[N]$ be a set of density $\delta$. Then $\phi^{-1}(A)$ is a subset of $[k]^n$ of density $\delta$, so by the density Hales-Jewett theorem it contains a combinatorial line. It is easy to see that the image of a combinatorial line under $\phi$ is an arithmetic progression of length $k$: indeed, if the combinatorial line is $x\oplus[k]W$, then the first term of the arithmetic progression is $\phi(x\oplus 0W)$ and the common difference is $\sum_{i\in W}k^i$. A very similar argument shows that the Hales-Jewett theorem implies van der Waerden's theorem.

We remark here that it is also possible to deduce the multidimensional Szemer\'edi theorem from the density Hales-Jewett theorem. Previously there were two known approaches: the ergodic approach and approaches that use hypergraph regularity.

=====================================

\noindent \textbf{Possible additions} \medskip

1. Perhaps it is worth giving the deduction of multidimensional Szemer\'edi as it is an excuse to introduce the notion of a combinatorial subspace, which we will need later. \medskip

2. Somewhere we should mention Tim Austin's work and how it relates to ours. Perhaps Terry is best placed to do this. \medskip

3. I also think it would be appropriate to write a paragraph or two about Polymath and how the proof was discovered.