Intro.tex

\section{Introduction}

\subsection{Basic theorem statements} The purpose of this paper is to give the first elementary proof of the density Hales--Jewett theorem. This theorem, first proved by Furstenberg and Katznelson~\cite{FK89,FK91}, has the same relation to the Hales--Jewett theorem~\cite{HJ63} as Szemer\'edi's theorem~\cite{Sze75} has to van der Waerden's theorem~\cite{vdW27}. Before we go any further, let us state all four theorems. We shall use the notation $[k]$ to stand for the set $\{1,2,\dotsc,k\}$. If $X$ is a set and $r$ is a positive integer, then an $r$-\textit{colouring} of $X$ will mean a function $\kappa\colon X\rightarrow [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{named}{van der Waerden's Theorem} \label{thm: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{named}

\begin{named}{Szemer\'edi's Theorem} \label{thm:szem} For every positive integer $k$ and every $\delta>0$ there exists $N$ such that every subset $A\subseteq[N]$ of size at least $\delta N$ contains an arithmetic progression of length $k$. \end{named}

It is usually better to focus on the \textit{density} $\abs{A}/N$ of a subset $A\subseteq [N]$ rather 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 the \textit{density version} of van der Waerden's theorem.

To state the Hales--Jewett theorem, we need a little more terminology. The theorem is concerned with subsets of $[k]^n$, elements of which we refer to as \emph{points} (or \emph{strings}). Instead of looking for arithmetic progressions, the Hales--Jewett theorem looks for \emph{combinatorial lines}. A combinatorial line in $[k]^n$ is a set of $k$ points $\{x^{(1)}, \dots, x^{(k)}\}$ formed as follows: Given a line \emph{template}, which is a string $\lambda \in ([k] \cup \{\wild\})^n$, the associated combinatorial line is formed by setting $x^{(i)}$ to be the point given by changing each``wildcard symbol `$\wild$' in $\lambda$ to symbol `$i$'. For instance, when $k = 3$ and $\lambda = 1 3 \wild \wild 2 2 1 \wild$, the associated combinatorial line is the following set of $3$ points: \[ \{13\bs{1}\bs{1}221\bs{1}, 13\bs{2}\bs{2}221\bs{2}, 1\bs{3}\bs{3}3221\bs{3}\}. \] (We exclude \emph{degenerate} combinatorial lines, those that arise from templates with no $\wild$'s. More formal definitions are given in Section~\ref{sec:defs}.) \ignore{ 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{named}{Hales--Jewett theorem}\label{thm:hj} For every pair of positive integers $k$ and $r$ there exists a positive integer $\hj{k}{r}$ such that for every $r$-colouring of the set $[k]^n$ there is a monochromatic combinatorial line, provided $n \geq \hj{k}{r}$. \end{named} As with van der Waerden's theorem, we may consider the density version of the Hales-Jewett theorem, where the density of $A \subseteq [k]^n$ is $\abs{A}/k^n$. The following theorem was first proved by Furstenberg and Katznelson. \begin{named}{Density Hales--Jewett theorem} \label{thm:dhj} For every positive integer $k$ and real $\delta>0$ there exists a positive integer $\dhj{k}{\delta}$ such that every subset of $[k]^n$ of density at least $\delta$ contains a combinatorial line, provided $n \geq \dhj{k}{\delta}$. \end{named}

We sometimes write ``DHJ($k$) to mean the $k$ case of this theorem.\noteryan{A bit confusing, since $\dhj{k}{\delta}$ is a number in the above theorem. Hmm.} The first nontrivial case, DHJ($2$), is a weak version of Sperner's theorem~\cite{Spe28}; we discuss this further in Section~\ref{sec:sperner}. We also remark that the Hales--Jewett theorem immediately implies van der Waerden's theorem, and likewise for the density versions. To see this, temporarily interpret $[m]$ as $\{0, 1, \dotsc, m-1\}$ rather than $\{1, 2, \dotsc, m\}$, and identify integers in $[N]$ with their base-$k$ representation in $[k]^n$.\noteryan{(we may assume $N$ is a power of $k$)} It's then easy to see that a combinatorial line in $[k]^n$ is a length-$k$ arithmetic progression in $[N]$; specifically, if the line's template is $\lambda$, with $S = \{i : \lambda_i = \star\}$, then the progression's common difference is $\sum_{i \in S} k^{n-i}$.

In this paper, we give a new, elementary proof of the density Hales--Jewett theorem, achieving quantitative bounds: \begin{theorem} \label{thm:our-dhj} In the density Hales--Jewett theorem, one may take $\dhj{3}{\delta} = 2 \upuparrows O(1/\delta^3)$. For $k \geq 4$, the bound $\dhj{k}{\delta}$ we achieve is of Ackermann type.\noteryan{cop-out} \end{theorem} \noindent Here we use the notation $x \uparrow y$ for $x^y$, $x \uparrow^{(\ell)} y$ for $x \uparrow x \uparrow \dotsm \uparrow x \uparrow y$ (with $\ell$ many $\uparrow$'s), and $x \upuparrows y$ for $x \uparrow^{(y)} x$.

We add that it is not too hard to obtain the following extensions to this result: (i)~a \emph{multidimensional} version, in which one finds higher-dimensional combinatorial subspaces;\ignore{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. } (ii)~a \emph{probabilistic} version, in which one shows that a randomly chosen combinatorial line (from a suitable distribution) is in the subset with positive probability depending only on $k$ and $\delta$;\noteryan{name-check Varnavides?} (iii)~the combined probabilistic multidimensional version. Indeed, to prove Theorem~\ref{thm:our-dhj} we found it necessary to obtain these extensions in passing. See Section~\ref{sec:concepts} for more detailed statements.

\subsection{Some discussion} Why is it interesting to give a new proof of this result? There are two main 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---ergodic methods---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. \noteryan{Citations would be good here; which are the far-reaching generalisations? Also, Tim's paper on Szemer\'edi is maybe 9 years old now\dots does that count as ``few years?} 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.\noteryan{Which difficulties does this refer to?} Having given a purely combinatorial proof, we are able to obtain explicit bounds for how large $n$ needs to be as a function of $\delta$ and $k$ in the density Hales--Jewett theorem (although admittedly the bounds for $k \geq 4$ are terrible and even the $k = 3$ bound is not especially good). Such bounds could not be obtained via the ergodic methods even in principle, since these proofs rely on the Axiom of Choice\noteryan{I just heard someone say this; is it true?}.\noteryan{maybe expand slightly on this, and/or cite the sister paper}

A second reason is that the density Hales--Jewett theorem immediately 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.\noteryan{Citations here.} In retrospect, one can add to this the fact that the proof we have discovered is, against all our expectations\noteryan{a strong phrase\dots}, \textit{simpler} than the previous approaches to Szemer\'edi's theorem; the most advanced notion needed is that of the total variation distance between discrete probability distributions. 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.\noteryan{Perhaps we should think of one :)}

\ignore{ 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$. There is no harm in thinking of $[N]$ as the set $\{0,1,\dots,N-1\}$. Now given $A \subset [N]$ of density $\delta$, we can write the integers in $A$ in base $k$, thus thinking of it as a subset of density $\delta$ in~$[k]^n$ (where again, there is no harm in thinking of $[k]$ as $\{0, 1, \dots, k-1\}$). The density Hales--Jewett theorem gives a nondegenerate combinatorial line in $A$, and it is easy to see that this corresponds to a length-$k$ arithmetic progression: if the line's template is $\lambda$, with $S = \{i : \lambda_i = \star\}$, then the progression's common difference is $\sum_{i \in S} k^{n-i}$. \ignore{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.\noteryan{Could we say here the catchier phrase, ``write the integers in $A$ in base $k$?} 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$,\noteryan{should convert to new notation} 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.}}

Before we start working towards the proof of the theorem, we would like briefly to mention that it was proved in a rather unusual ``open source" way, which is why it is being published under a pseudonym. The work was done by several mathematicians, who wrote their thoughts, as they had them, in the form of blog comments.\noteryan{I would like to at least consider adding a link or statement that it was on Tim's blog. Otherwise, the only identifying part of the paper is the wiki's URL, which might make it seem like Michael Nielsen was the mastermind. Okay with you, Tim?} Anybody who wanted to could participate, and at all stages of the process the comments were fully open to anybody who was interested. This was in complete contrast to the usual way that results are proved in private and presented in a finished form. The blog comments are still available, so although this paper is a somewhat polished account of the argument, it is possible to read a record of the entire thought process that led to the proof. The participants also created a wiki, which contains sketches of the argument, links to the blog comments, and a great deal of related material. The wiki's URL is \url{http://michaelnielsen.org/polymath1/}.\\

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

\subsection{Outline of the paper} XXX ``table of contents paragraph to be filled in XXX