Introduction.tex
\section{Introduction}
For any integers $k \geq 1$ and $n \geq 0$, let $[k] := \{1,\ldots,k\}$, and define $[k]^n$ to be the cube of words of length $n$ with alphabet in $[k]$. Thus for instance $[3]^2 = \{11,12,13,21,22,23,31,32,33\}$.
We define a \emph{combinatorial line} in $[k]^n$ to be a set of the form $\{ w(i): i = 1,\ldots,k\} \subset [k]^n$, where $w \in ([k] \cup \{x\})^n \backslash [k]^n$ is a word of length $n$ with alphabet in $[k]$ together with a ``wildcard letter $x$ which appears at least once, and $w(i) \in [k]^n$ is the word obtained from $w$ by replacing $x$ by $i$; we often abuse notation and identify $w$ with the combinatorial line $\{ w(i): i = 1,\ldots,k\}$ it generates. Thus for instance, in $[3]^2$ we have $x2 = \{12,22,32\}$ and $xx = \{11,22,33\}$ as typical examples of combinatorial lines. In general, $[k]^n$ has $k^n$ words and $(k+1)^n-k^n$ lines.
\begin{figure}[tb] \centerline{\includegraphics{AllLinesIn3n.pdf}} \caption{Combinatorial lines in $[3]^2$.} \label{fig1} \end{figure}
A set $A \subset [k]^n$ is said to be \emph{line-free} if it contains no combinatorial lines. Define the \emph{$(n,k)$ density Hales-Jewett number} $c_{n,k}$ to be the maximum cardinality $|A|$ of a line-free subset of $[k]^n$. Clearly, one has the trivial bound $c_{n,k} \leq k^n$. A deep theorem of Furstenberg and Katznelson~\cite{fk1}, \cite{fk2} asserts that this bound can be asymptotically improved:
\begin{theorem}[Density Hales-Jewett theorem]\label{dhj} For any fixed $k \geq 2$, one has $\lim_{n \to \infty} c_{n,k}/k^n = 0$. \end{theorem}
\begin{remark} The difficulty of this theorem increases with $k$. For $k=1$, one clearly has $c_{n,1}=1$. For $k=2$, a classical theorem of Sperner~\cite{sperner} asserts, in our language, that $c_{n,2} = \binom{n}{\lfloor n/2\rfloor}$. The case $k=3$ is already non-trivial (for instance, it implies Roth's theorem~\cite{roth} on arithmetic progressions of length three) and was first established in \cite{fk1} (see also \cite{mcc}). The case of general $k$ was first established in~\cite{fk2} and has a number of implications, in particular implying Szemer\'edi's theorem~\cite{szem} on arithmetic progressions of arbitrary length. \end{remark}
The Furstenberg-Katznelson proof of Theorem~\ref{dhj} relied on ergodic-theory techniques and did not give an explicit decay rate for $c_{n,k}$. Recently, two further proofs of this theorem have appeared, by Austin~\cite{austin} and by the sister Polymath project to this one~\cite{poly}. The proof of~\cite{austin} also used ergodic theory, but the proof in~\cite{poly} was combinatorial and gave effective bounds for $c_{n,k}$ in the limit $n \to \infty$. {\bf Note - need to ask what those explicit bounds are!} However, these bounds are not believed to be sharp, and in any case are only non-trivial in the asymptotic regime when $n$ is sufficiently large depending on $k$.
Our first result is the following asymptotic lower bound. The construction is based on the recent refinements \cite{elkin,greenwolf,obryant} of a well-known construction of Behrend~\cite{behrend} and Rankin~\cite{rankin}. The proof of Theorem~\ref{dhj-lower} is in Section~\ref{dhj-lower-sec}. Let $r_k(n)$ be the maximum size of a subset of $[n]$ that does not contain a $k$-term arithmetic progression.
\begin{theorem}[Asymptotic lower bound for $c_{n,k}$]\label{dhj-lower} For each $k$\geq 3$, there is an absolute constant $C>0$ such that
\[ c_{n,k} \geq C k^n \left(\frac{r_k(\sqrt{n})}{\sqrt{n}}\right)^{k-1} = k^n \exp\left( - O(\sqrt[\ell]{\log n}) \right), \]
where $\ell$ is the largest integer satisfying $2k>2^{\ell}$. Specifically,
\[ c_{n,k} \geq C k^{n-\alpha(k) \sqrt[\ell]{\log n} + \beta(k) \log\log n},\]
where all logarithms are base-$k$, and $\alpha(k) = (\log 2)^{1-1/\ell} \ell 2^{(\ell-1)/2-1/\ell}$ and $\beta(k)=(k-1)/(2\ell)$. \end{theorem}
In the case of small $n$, we focus primarily on the first non-trivial case $k=3$. We have computed the following explicit values of $c_{n,3}$:
\begin{theorem}[Explicit values of $c_{n,3}$]\label{dhj-upper} We have $c_{0,3} = 1$, $c_{1,3} = 2$, $c_{2,3} = 6$, $c_{3,3} = 18$, $c_{4,3} = 52$, $c_{5,3}=150$, and $c_{6,3}=450$. (This has been entered in the OEIS~\cite{oeis} as A156762.) \end{theorem}
This result is established in Sections~\ref{dhj-lower-sec},~\ref{dhj-upper-sec}. Initially these results were established by an integer program (see Appendix~\ref{integer-sec}, but we provide completely computer-free proofs here. The constructions used in Theorem~\ref{dhj-upper} give reasonably efficient constructions for larger values of $n$; for instance, they show that $3^{99} \leq c_{100,3} \leq 2 \times 3^{99}$. See Section~\ref{dhj-lower-sec} for further discussion.
We also have several partial results for higher values of $k$: see Section~\ref{higherk-sec}. For results on the closely related \emph{Hales-Jewett numbers} $HJ(k,r)$, see Section~\ref{coloring-sec}.
A variant of the density Hales-Jewett theorem has also been studied in the literature. Define a \emph{geometric line} in $[k]^n$ to be any set of the form $\{ a+ir: i=1,\ldots,k\}$ in $[k]^n$, where we identify $[k]^n$ with a subset of $\Z^n$, and $a, r \in \Z^n$ with $r \neq 0$. Equivalently, a geometric line takes the form $\{ w( i, k+1-i ): i =1,\ldots,k \}$, where $w \in ([k] \cup \{x,\overline{x}\})^n \backslash [k]^n$ is a word of length $n$ using the numbers in $[k]$ and two wildcards $x, \overline{x}$ as the alphabet, with at least one wildcard occuring in $w$, and $w(i,j) \in [k]^n$ is the word formed by substituting $i,j$ for $x,\overline{x}$ respectively. Thus for instance $[3]^2$ contains the geometric lines $2x = 2\overline{x} = \{21,22,23\}$, $xx = \overline{x}\overline{x}=\{11,22,33\}$, and $x\overline{x}=\overline{x}x=\{13,22,31\}$. Clearly every combinatorial line is a geometric line, but not conversely.
{\bf a picture contrasting combinatorial and geometric lines?}
Define a \emph{Moser set} in $[k]^n$ to be a subset of $[k]^n$ that contains no geometric lines, and let $c'_{n,k}$ be the maximum cardinality $|A|$ of a Moser set in $[k]^n$. Clearly one has $c'_{n,k} \leq c_{n,k}$, so in particular from Theorem~\ref{dhj} one has $c'_{n,k}/k^n \to 0$ as $n \to \infty$. (Interestingly, there is no known proof of this fact that does not go through Theorem~\ref{dhj}, even for $k=3$.) Again, $k=3$ is the first non-trivial case: it is clear that $c'_{n,1}=0$ and $c'_{n,2}=1$ for all $n$.
The question of computing $c'_{n,3}$ was first posed by Moser~\cite{moser}. Prior to our work, the values $$ c'_{0,3}=1; c'_{1,3}=2; c'_{2,3}=6; c'_{3,3}=16; c'_{4,3}=43$$ were known~\cite{chvatal2},~\cite{chandra} (this is Sequence A003142 in the OEIS~\cite{oeis}). We extend this sequence slightly:
\begin{theorem}[Values of $c'_{n,3}$ for small $n$]\label{moser} We have $c'_{0,3} = 1$, $c'_{1,3} = 2$, $c'_{2,3} = 6$, $c'_{3,3} = 16$, $c'_{4,3} = 43$, $c'_{5,3} = 124$, and $353 \leq c'_{6,3} \leq 361$. \end{theorem}
This result is established in Sections \ref{moser-lower-sec}, \ref{moser-upper-sec}. The bounds here were initially computer-assisted by an integer program (see Appendix \ref{integer-sec}), but is now mostly computer-free, with the exception the $c'_{6,3}$ bounds, as well as one fact concerning Moser sets in $[3]^3$ (Lemma \ref{paretop}) which can be easily checked by brute force computer search but which can probably also be derived in a computer-free manner also.
As for lower bounds, it is known that \begin{equation}\label{binom} c'_{n,3} \geq \binom{n+1}{\lfloor \frac{2n+1}{3} \rfloor} 2^{\lfloor \frac{2n+1}{3} \rfloor - 1} \end{equation} for $n \geq 2$. This bound is not quite optimal; for instance, it gives a lower bound of $c'_{5,3}=120$. For $n=6,7$, the best lower bounds we have been able to locate were computed by a genetic algorithm; see Appendix \ref{genetic-alg}.
As mentioned earlier, the sharp bound on $c_{n,2}$ comes from Sperner's theorem. It is known that Sperner's theorem can be refined to the \emph{Lubell-Meshalkin-Yamamoto (LMY) inequality}, which in our language asserts that $$ \sum_{a_1,a_2 \geq 0; a_1+a_2 = n} \frac{|A \cap \Gamma_{a_1,a_2}|}{|\Gamma_{a_1,a_2}|} \leq 1 $$ for any line-free subset $A \subset [2]^n$, where the \emph{cell} $\Gamma_{a_1,\ldots,a_k} \subset [k]^n$ is the set of words in $[k]^n$ which contain exactly $a_i$ $i$'s for each $i=1,\ldots,k$. It is natural to ask whether this inequality can be extended to higher $k$. Let $\Delta_{k,n}$ denote the set of all tuples $(a_1,\ldots,a_k)$ of non-negative integers summing to $n$, define a \emph{simplex} to be a set of $k$ points in $\Delta_{k,n}$ of the form $(a_1+r,a_2,\ldots,a_k), (a_1,a_2+r,\ldots,a_k),\ldots,(a_1,a_2,\ldots,a_k+r)$ for some $0 < r \leq n$ and $a_1,\ldots,a_k$ summing to $n-r$, and define a \emph{Fujimura set} to be a subset $B \subset \Delta_{k,n}$ which contains no simplices. Observe that if $w$ is a combinatorial line in $[k]^n$, then $$ w(1) \in \Gamma_{a_1+r,a_2,\ldots,a_k}, w(2) \in \Gamma_{a_1,a_2+r,\ldots,a_k}, \ldots, w(k) = \Gamma_{a_1,a_2,\ldots,a_k+r}$$ for some simplex $(a_1+r,a_2,\ldots,a_k), (a_1,a_2+r,\ldots,a_k),\ldots,(a_1,a_2,\ldots,a_k+r)$. Thus, if $B$ is a Fujimura set, then $A := \bigcup_{\vec a \in B} \Gamma_{\vec a}$ is line-free. Note also that $$ \sum_{\vec a \in \Delta_{k,n}} \frac{|A \cap \Gamma_{\vec a}|}{|\Gamma_{\vec a}|} = |B|. $$ This motivates a ``hyper-optimistic conjecture:
{\bf a picture showing a Fujimura set?}
\begin{conjecture}\label{hoc} For any $k \geq 1$ and $n \geq 0$, and any line-free subset $A$ of $[k]^n$, one has $$ \sum_{\vec a \in \Delta_{k,n}} \frac{|A \cap \Gamma_{\vec a}|}{|\Gamma_{\vec a}|} \leq c^\mu_{k,n},$$ where $c^\mu_{k,n}$ is the maximal size of a Fujimura set in $\Delta_{k,n}$. \end{conjecture}
One can show that this conjecture for a fixed value of $k$ would imply Theorem \ref{dhj} for the same value of $k$, in much the same way that the LYM inequality is known to imply Sperner's theorem. The LYM inequality asserts that Conjecture \ref{hoc} is true for $k \leq 2$. As far as we know this conjecture could hold in $k=3$. However, we know that it fails for $k=4$; see ???. {\bf do we know it fails for higher k also?}
The problem of computing $c^\mu_{k,n}$ was essentially proposed by Fujimura ({\bf reference?}). In Section \ref{fujimura-sec} we give some bounds on these numbers. {\bf be more specific here!}
\subsection{Notation}\label{notation-sec}
There are several subsets of $[k]^n$ which will be useful in our analysis. We have already introduced combinatorial lines, geometric lines, and cells. One can generalise the notion of a combinatorial line to that of a \emph{combinatorial subspace} in $[k]^n$ of dimension $d$, which is indexed by a word $w$ in $([k] \cup \{x_1,\ldots,x_d\})^n$ containing at least one of each wildcard $x_1,\ldots,x_d$, and which forms the set $\{ w(i_1,\ldots,i_d): i_1,\ldots,i_d \in [k]\}$, where $w(i_1,\ldots,i_d) \in [k]^d$ is the word formed by replacing $x_1,\ldots,x_d$ with $i_1,\ldots,i_d$ respectively. Thus for instance, in $[3]^3$, we have the two-dimensional combinatorial subspace $xxy = \{111,112,113,221,222,223,331,332,333\}$. We similarly have the notion of a \emph{geometric subspace} in $[k]^n$ of dimension $d$, which is defined similarly but with $d$ wildcards $x_1,\ldots,x_d,\overline{x_1},\ldots,\overline{x_d}$, with at least one of either $x_i$ or $\overline{x_i}$ appearing in the word $w$ for each $1 \leq i \leq d$, and the space taking the form $\{ w(i_1,\ldots,i_d,k+1-i_1,\ldots,k+1-i_d): i_1,\ldots,i_d \in [k] \}$. Thus for instance $[3]^3$ contains the two-dimensional geometric subspace $x\overline{x}y = \{ 131, 132, 133, 221, 222, 223, 311, 312, 313\}$.
An important class of combinatorial subspaces in $[k]^n$ will be the \emph{slices} consisting of $n-1$ distinct wildcards and one fixed coordinate. We will denote the distinct wildcards here by asterisks, thus for instance in $[3]^3$ we have $2** = \{ 211, 212, 213, 221, 222, 223, 231, 232, 233\}$. Two slices are \emph{parallel} if their fixed coordinate are in the same position, thus for instance $1**$ and $2**$ are parallel, and one can subdivide $[k]^n$ into $k$ parallel slices, each of which is isomorphic to $[k]^{n-1}$. In the analysis of Moser slices with $k=3$, we will make a distinction between \emph{centre slices}, whose fixed coordinate is equal to $2$, and \emph{side slices}, in which the fixed coordinate is either $1$ or $3$, thus $[3]^n$ can be partitioned into one centre slice and two side slices.
Another important set in the study of $k=3$ Moser sets are the \emph{spheres} $S_{i,n} \subset [3]^n$, defined as those words in $[3]^n$ with exactly $n-i$ $2$'s (and hence $i$ letters that are $1$ or $3$). Thus for instance $S_{1,3} = \{ 122, 322, 212, 232, 221, 223\}$. Observe that $[3]^n = \bigcup_{i=0}^n S_{i,n}$, and each $S_{i,n}$ has cardinality $|S_{i,n}| = \binom{n}{i} 2^{i}$.
It is also convenient to subdivide each sphere $S_{i,n}$ into two components $S_{i,n} = S_{i,n}^o \cup S_{i,n}^e$, where $S_{i,n}^o$ are the words in $S_{i,n}$ with an odd number of $1$'s, and $S_{i,n}^e$ are the words with an even number of $1$'s. Thus for instance $S_{1,3}^o = \{122,212,221\}$ and $S_{1,3}^e = \{322,232,223\}$. Observe that for $i>0$, $S_{i,n}^o$ and $S_{i,n}^e$ both have cardinality $\binom{n}{i} 2^{i-1}$.
The \emph{Hamming distance} between two words $w,w'$ is the number of coordinates in which $w, w'$ differ, e.g. the Hamming distance between $123$ and $321$ is two. Note that $S_{i,n}$ is nothing more than the set of words whose Hamming distance from $2\ldots2$ is $i$, which justifies the terminology ``sphere.
In the density Hales-Jewett problem, there are two types of symmetries on $[k]^n$ which map combinatorial lines to combinatorial lines (and hence line-free sets to line-free sets). The first is a permutation of the alphabet $[k]$; the second is a permutation of the $n$ coordinates. Together, this gives a symmetry group of order $k!n!$ on the cube $[k]^n$, which we refer to as the \emph{combinatorial symmetry group} of the cube $[k]^n$. Two sets which are related by an element of this symmetry group will be called (combinatorially) \emph{equivalent}, thus for instance any two slices are combinatorially equivalent.
For the analysis of Moser sets in $[k]^n$, the symmetries are a bit different. One can still permute the $n$ coordinates, but one is no longer free to permute the alphabet $[k]$. Instead, one can \emph{reflect} an individual coordinate, for instance sending each word $x_1 \ldots x_n$ to its reflection $x_1 \ldots x_{i-1} (k+1-x_i) x_{i+1} \ldots x_n$. Together, this gives a symmetry group of order $2^k n!$ on the cube $[k]^n$, which we refer to as the \emph{geometric symmetry group} of the cube $[k]^n$; this group maps geometric lines to geometric lines, and thus maps Moser sets to Moser sets. Two Moser sets which are related by an element of this symmetry group will be called (geometrically) \emph{equivalent}. For instance, a sphere $S_{i,n}$ is equivalent only to itself, and $S_{i,n}^o$, $S_{i,n}^e$ are equivalent only to each other.
