Introduction.tex

From Polymath1Wiki
Jump to: navigation, search

\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{fig-line} \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$. For example, if $n$ can be written as an exponential tower $2 \uparrow 2 \uparrow 2 \uparrow \ldots \uparrow 2$ with $m$ 2s, then $c_{n,3} \le 3^n m^{-1/3}$. 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}$. More 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}$ (entered in the OEIS~\cite{oeis} as A156762):

\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$. \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, but we provide completely computer-free proofs here. The constructions used in Section~\ref{dhj-lower-sec} 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}.

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. Figure~\ref{fig-geomline} shows the eight geometric lines in $[3]^2$. Clearly every combinatorial line is a geometric line, but not conversely. In general, $[k]^n$ has $((k+2)^n-k^n)/2$ geometric lines.

\begin{figure}[tb] \centerline{\includegraphics{AllGeomLinesIn3n.pdf}} \caption{Geometric lines in $[3]^2$.} \label{fig-geomline} \end{figure}

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 $c'_{6,3} = 353$. \end{theorem}

This result is established in Sections \ref{moser-lower-sec}, \ref{moser-upper-sec}. The arguments given here are computer-assisted; however, we have found alternate (but lengthier) computer-free proofs for the above claims with the the exception of the proof of $c'_{6,3}=353$, which requires one non-trivial computation (Lemma \ref{paretop-4}). These alternate proofs are not given in this paper to save space, but can be found at \cite{polywiki}.

We establish a lower bound for this problem of $(2+o(1))\binom{n}{i}2^i\leq c'_{n,3}$, which is maximized for $i$ near $2n/3$. This bound is around one-third better than the literature. We also give methods to improve on this construction.

Earlier lower bounds were known. Indeed, let $A(n,d)$ denote the size of the largest binary code of length $n$

and minimal distance $d$. Then

\begin{equation}\label{cnchvatalintro} c'_{n,3}\geq \max_k \left( \sum_{j=0}^k \binom{n}{j} A(n-j, k-j+1)\right). \end{equation} which, with $A(n,1)=2^n$ and $A(n,2)=2^{n-1}$, implies in particular 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'_{6,3} \geq 344$.

\begin{remark} Let $c_{n,3}$ be the size of the largest subset of ${\mathbb F}_3^n$ which contains no lines $x, x+r, x+2r$ with $x,r \in {\mathbb F}_3^n$ and $r \neq 0$, where ${\mathbb F}_3$ is the field of three elements. Clearly one has $c_{n,3} \leq c'_{n,3} \leq c_{n,3}$. It is known that $$ c_{0,3}=1; c_{1,3}=2; c_{2,3}=4; c'_{3,3}=9; c'_{4,3}=20; c_{5,3}=45; c_{6,3} = 112;$$ see \cite{potenchin}. \end{remark}

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_{n,k}$ 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_{n,k}$ 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}\footnote{Fujimura actually proposed the related problem of finding the largest subset of $\Delta_{n,k}$ that contained no equilateral triangles; see \cite{fuji}. Our results for Fujimura sets can be found at the page {\tt Fujimura's problem} at \cite{polywiki}.} to be a subset $B \subset \Delta_{n,k}$ 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_{n,k}} \frac{|A \cap \Gamma_{\vec a}|}{|\Gamma_{\vec a}|} = |B|. $$ This motivates a ``hyper-optimistic conjecture:

\begin{figure}[tb] \centerline{\includegraphics{FujimuraPicture.pdf}} \caption{A Fujimura set in $\Delta_{6,3}$. The point $(a,b,c)$ is represented by a square at $(a,b)$ labeled with $c$. The Fujimura set is shown in red; its complement in $\Delta_{6,3}$ is shown in gray.} \label{fig-pic} \end{figure}

\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_{n,k}} \frac{|A \cap \Gamma_{\vec a}|}{|\Gamma_{\vec a}|} \leq c^\mu_{n,k},$$ where $c^\mu_{n,k}$ is the maximal size of a Fujimura set in $\Delta_{n,k}$. \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 found a simple counterexample for $k=4$ and $n=2$, given by the line-free set $$A := \{(1, 1), (1, 2), (1, 3), (2, 1), (2, 3), (2, 4), (3, 2), (3, 3), (3,4), (4, 1), (4, 2), (4, 4)\}$$ together with the computation that $c^\mu_{4,2}=7$. It is in fact likely that this conjecture fails for all higher $k$ also.


\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^n 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.

\subsection{About this project}

This paper is part of the \emph{Polymath project}, which was launched by Timothy Gowers in February 2009 as an experiment to see if research mathematics could be conducted by a massive online collaboration. The first project in this series, \emph{Polymath1}, was was focused on understanding the density Hales-Jewett numbers $c_{n,k}$, and was split up into two sub-projects, namely an (ultimately successful) attack on the density Hales-Jewett theorem $c_{n,k} = o(k^n)$ (resulting in the paper \cite{poly}), and a collaborative project on computing $c_{n,k}$ and related quantities (such as $c'_{n,k}$) for various small values of $n$ and $k$. This project (which was administered by Terence Tao) resulted in this current paper.

Being such a collaborative project, many independent aspects of the problem were studied, with varying degrees of success. For reasons of space (and also due to the partial nature of some of the results), this paper does not encompass the entire collection of observations and achievements made during the research phase of the project (which lasted for approximately three months). In particular, alternate proofs of some of the results here have been omitted, as well as some auxiliary results on related numbers, such as coloring Hales-Jewett numbers. However, these results can be accessed from the web site of this project at \cite{polywiki}.