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.

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{fk}, \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{fk} (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$.

In this paper we focus primarily on the first non-trivial case $k=3$. Our first result is the following asymptotic lower bound:

\begin{theorem}[Asymptotic lower bound for $c_{n,3}$]\label{dhj-lower} There exists an absolute constant $C > 0$ such that $$ c_{n,3} \geq C 3^{n - 4\sqrt{\log_3 2}\sqrt{\log_3 n}+\frac 12 \log_3 \log_3 n}$$ for all sufficiently large $n$. In particular, in asymptotic notation we have $c_{n,3} \geq 3^n \exp( - O( \sqrt{\log n} ) )$ for sufficiently large $n$. \end{theorem}

This theorem is based in the recent refinement \cite{elkin}, \cite{greenwolf}, \cite{obryant} of a well-known construction of Behrend\cite{behrend}, and is proven in Section \ref{dhj-lower-sec}.

In the case of small $n$, we have computed the following explicit values of $c_{n,k}$:

\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} = 52$, $c_{6,3}=150$, and $c_{7,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,n\}$ 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, n+1-i ): i =1,\ldots,n \}$, 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.

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}=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}), 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}{q} 2^{n-q} \end{equation} where $q$ is the nearest integer to $n/3$. 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:

\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}

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 $n$ 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^{n-i}$.

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

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.