Intro.tex - Revision history

Ryanworldwide at 20:24, 8 July 2009

2009-07-08T20:24:06Z

← Older revision		Revision as of 13:24, 8 July 2009
Line 2:		Line 2:

	\subsection{Basic theorem statements}		\subsection{Basic theorem statements}
	The purpose of this paper is to give the first elementary~~, quantitative~~ 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$.		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.		First, let us state van der Waerden's theorem and Szemer\'edi's theorem.
Line 14:		Line 14:
	\end{named}		\end{named}

	It is usually better to focus on the \textit{density} $\|A\|/N$ of a subset $A\subseteq [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 the \textit{density version} of van der Waerden's theorem.		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 ~~taking~~ $x^{(i)}$ to be the point given by changing ~~all the~~ ``wildcard ~~symbols~~'' $\wild$ in $\lambda$ to $i$'s. 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:		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}\}.		\{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:~~concepts~~}.)		(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{		\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		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
Line 35:		Line 35:
	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}$.		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}		\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 $\|A\|/k^n$. The following theorem was first proved by Furstenberg and Katznelson.		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}		\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}$.		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}		\end{named}

	We sometimes write ``DHJ($k$)'' to mean the $k$ case of this theorem. 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}$.		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:		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)$ \~~noteryan{explain notation?} and~~ $\dhj{k}{\delta} ~~= XXX~~$\noteryan{~~fill in~~} ~~for $k \geq 4$.~~		\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}		\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 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.		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.		} (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}		\subsection{Some discussion}
	Why is it interesting to give a new proof of this result? There are two main reasons. ~~\noteryan{There is another reason: one may desire quantitative bounds, and such were previously unknown. A paragraph on this provides a good opportunity to cite the other paper.}~~ 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~~\noteryan{namely,~~ 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?} 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?}		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, \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 :)}\\		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{		\ignore{
Line 61:		Line 62:

	\notetim{Somewhere we should mention Tim Austin's work and how it relates to ours. Perhaps Terry is best placed to do this.}		\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

Ryanworldwide: Undo revision 1763 by 67.186.58.92 (Talk)

2009-07-08T20:09:10Z

Undo revision 1763 by 67.186.58.92 (Talk)

← Older revision		Revision as of 13:09, 8 July 2009
Line 2:		Line 2:

	\subsection{Basic theorem statements}		\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$.		The purpose of this paper is to give the first elementary, quantitative 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.		First, let us state van der Waerden's theorem and Szemer\'edi's theorem.
Line 14:		Line 14:
	\end{named}		\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.		It is usually better to focus on the \textit{density} $\|A\|/N$ of a subset $A\subseteq [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 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:		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 taking $x^{(i)}$ to be the point given by changing all the ``wildcard symbols'' $\wild$ in $\lambda$ to $i$'s. 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}\}.		\{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~~}.)		(We exclude \emph{degenerate} combinatorial lines, those that arise from templates with no $\wild$'s. More formal definitions are given in Section~\ref{sec:concepts}.)
	\ignore{		\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		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
Line 35:		Line 35:
	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}$.		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}		\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.		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 $\|A\|/k^n$. The following theorem was first proved by Furstenberg and Katznelson.
	\begin{named}{Density Hales--Jewett theorem} \label{thm:dhj}		\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}$.		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}		\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}$.		We sometimes write ``DHJ($k$)'' to mean the $k$ case of this theorem. 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:		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~~}		\begin{theorem} \label{thm:our-dhj} In the density Hales--Jewett theorem, one may take $\dhj{3}{\delta} = 2 \upuparrows O(1/\delta^3)$ \noteryan{explain notation?} and $\dhj{k}{\delta} = XXX$\noteryan{fill in} for $k \geq 4$.
	\end{theorem}		\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.		We add that it is not 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.		} (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}		\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}		Why is it interesting to give a new proof of this result? There are two main reasons. \noteryan{There is another reason: one may desire quantitative bounds, and such were previously unknown. A paragraph on this provides a good opportunity to cite the other paper.} 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\noteryan{namely, 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?} 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?}

	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 :)}		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, \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{		\ignore{
Line 62:		Line 61:

	\notetim{Somewhere we should mention Tim Austin's work and how it relates to ours. Perhaps Terry is best placed to do this.}		\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~~

67.186.58.92 at 04:20, 25 June 2009

2009-06-25T04:20:10Z

← Older revision		Revision as of 21:20, 24 June 2009
Line 2:		Line 2:

	\subsection{Basic theorem statements}		\subsection{Basic theorem statements}
	The purpose of this paper is to give the first elementary~~, quantitative~~ 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$.		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.		First, let us state van der Waerden's theorem and Szemer\'edi's theorem.
Line 14:		Line 14:
	\end{named}		\end{named}

	It is usually better to focus on the \textit{density} $\|A\|/N$ of a subset $A\subseteq [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 the \textit{density version} of van der Waerden's theorem.		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 ~~taking~~ $x^{(i)}$ to be the point given by changing ~~all the~~ ``wildcard ~~symbols~~'' $\wild$ in $\lambda$ to $i$'s. 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:		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}\}.		\{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:~~concepts~~}.)		(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{		\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		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
Line 35:		Line 35:
	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}$.		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}		\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 $\|A\|/k^n$. The following theorem was first proved by Furstenberg and Katznelson.		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}		\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}$.		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}		\end{named}

	We sometimes write ``DHJ($k$)'' to mean the $k$ case of this theorem. 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}$.		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:		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)$ \~~noteryan{explain notation?} and~~ $\dhj{k}{\delta} ~~= XXX~~$\noteryan{~~fill in~~} ~~for $k \geq 4$.~~		\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}		\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 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.		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.		} (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}		\subsection{Some discussion}
	Why is it interesting to give a new proof of this result? There are two main reasons. ~~\noteryan{There is another reason: one may desire quantitative bounds, and such were previously unknown. A paragraph on this provides a good opportunity to cite the other paper.}~~ 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~~\noteryan{namely,~~ 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?} 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?}		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, \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 :)}\\		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{		\ignore{
Line 61:		Line 62:

	\notetim{Somewhere we should mention Tim Austin's work and how it relates to ours. Perhaps Terry is best placed to do this.}		\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

Ryanworldwide at 19:56, 12 June 2009

2009-06-12T19:56:41Z

@@ Line 16: / Line 16: @@
 It is usually better to focus on the \textit{density} $|A|/N$ of a subset $A\subseteq [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 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 taking $x^{(i)}$ to be the point given by changing all the $\wild$'s in $\lambda$ to $i$'s.  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:
+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 taking $x^{(i)}$ to be the point given by changing all the ``wildcard symbols'' $\wild$ in $\lambda$ to $i$'s.  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\boldsymbol{1}\boldsymbol{1}221\boldsymbol{1}, 13\boldsymbol{2}\boldsymbol{2}221\boldsymbol{2}, 1\boldsymbol{3}\boldsymbol{3}3221\boldsymbol{3}\}.
+\{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:definitions}.)
+(We exclude \emph{degenerate} combinatorial lines, those that arise from templates with no $\wild$'s. More formal definitions are given in Section~\ref{sec:concepts}.)
 \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
@@ Line 44: / Line 35: @@
 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 $|A|/k^n$.  The following theorem was first proved by Furstenberg and Katznelson, and we give a new proof in this paper.
+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 $|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 remark that the first nontrivial case, $k = 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, we may temporarily interpret $[m]$ as $\{0, 1, \dotsc, m-1\}$ rather than $\{1, 2, \dotsc, m\}$.  We 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}$.
+We sometimes write ``DHJ($k$)'' to mean the $k$ case of this theorem.  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}$.
 \subsection{Some discussion}
@@ Line 62: / Line 61: @@
 \notetim{Somewhere we should mention Tim Austin's work and how it relates to ours. Perhaps Terry is best placed to do this.}

Ryanworldwide at 00:09, 12 June 2009

2009-06-12T00:09:14Z

Show changes

Ryanworldwide at 20:04, 11 June 2009

2009-06-11T20:04:58Z

← Older revision		Revision as of 13:04, 11 June 2009
Line 54:		Line 54:

	\textbf{[[Tim:		\textbf{[[Tim:
	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. \noteryan{Yes; might also be convenient to identify $\star$ with $k+1$ and then one gets an easy way to define subspaces (the ~~character~~ $k+2$ gives the coordinates in the second dimension, etc.)} 2. Somewhere we should mention Tim Austin's work and how it relates to ours. Perhaps Terry is best placed to do this.]]}		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. \noteryan{Yes; might also be convenient to identify $\star$ with $k+1$ and then one gets an easy way to define subspaces (the symbol $k+2$ gives the coordinates in the second dimension, etc.)} 2. Somewhere we should mention Tim Austin's work and how it relates to ours. Perhaps Terry is best placed to do this.]]}

Ryanworldwide at 01:22, 19 May 2009

2009-05-19T01:22:01Z

← Older revision		Revision as of 18:22, 18 May 2009
Line 67:		Line 67:
	\]		\]
	\end{definition}		\end{definition}

			\begin{fact} \label{fact:tv-mix} Let $(\nu_\kappa)_{\kappa \in K}$ be a family of distributions on $\Omega$, let $\lambda$ be a distribution on $K$, and let $\mu$ be the associated mixture distribution, given by drawing $\kappa \sim \lambda$ and then drawing from $\nu_\kappa$. Then\noteryan{need to prove? It's just the triangle inequality}
			\[
			\dtv{\pi}{\mu} \leq \Ex_{\kappa \sim \lambda}[\dtv{\pi}{\nu_\kappa}].
			\]
			\end{fact}

Ryanworldwide at 13:41, 18 May 2009

2009-05-18T13:41:47Z

@@ Line 40: / Line 40: @@
 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 nondegenerate combinatorial line.
+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 nondegenerate combinatorial line.\noteryan{Would be good to point out somewhere that as soon as it works for one $n$ it works for all larger $n$ too.}
 \end{theorem}
@@ Line 55: / Line 55: @@
 \textbf{[[Tim:
 . 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.  \noteryan{Yes; might also be convenient to identify $\star$ with $k+1$ and then one gets an easy way to define subspaces (the character $k+2$ gives the coordinates in the second dimension, etc.)} 2. Somewhere we should mention Tim Austin's work and how it relates to ours. Perhaps Terry is best placed to do this.]]}

Ryanworldwide at 18:51, 17 May 2009

2009-05-17T18:51:39Z

← Older revision		Revision as of 11:51, 17 May 2009
Line 19:		Line 19:
	\{\chg{\lambda}{\star}{1}, \dots, \chg{\lambda}{\star}{k}\}.		\{\chg{\lambda}{\star}{1}, \dots, \chg{\lambda}{\star}{k}\}.
	\]		\]
	Here we have introduced the notation $\chg{z}{a}{b}$ for the string formed by changing all occurrences of symbol $a$ to symbol $b$ in string $z$. For instance, when $k = 3$ and $\lambda = \star 1 3 \!\star \!\star$, the associated combinatorial line is the following set of $3$ points:		Here we have introduced the notation $\chg{z}{i}{j}$ for the string formed by changing all occurrences of symbol $i$ to symbol $j$ in string $z$. For instance, when $k = 3$ and $\lambda = \star 1 3 \!\star \!\star$, the associated combinatorial line is the following set of $3$ points:
	\[		\[
	\{11311, 21322, 31333\}.		\{11311, 21322, 31333\}.

Ryanworldwide at 21:30, 14 May 2009

2009-05-14T21:30:20Z

← Older revision		Revision as of 14:30, 14 May 2009
Line 47:		Line 47:
	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.		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.\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.		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.}

	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.		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.
Line 53:		Line 53:
	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. 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 URL is \url{http://michaelnielsen.org/polymath1/}.\\		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. 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 URL is \url{http://michaelnielsen.org/polymath1/}.\\

	~~{\tiny~~ \textbf{[[Tim:		\textbf{[[Tim:
	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. 2. Somewhere we should mention Tim Austin's work and how it relates to ours. Perhaps Terry is best placed to do this.]]		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. \noteryan{Yes; might also be convenient to identify $\star$ with $k+1$ and then one gets an easy way to define subspaces (the character $k+2$ gives the coordinates in the second dimension, etc.)} 2. Somewhere we should mention Tim Austin's work and how it relates to ours. Perhaps Terry is best placed to do this.]]}
	}}