Dhj-lown-lower.tex

\section{Lower bounds for the density Hales-Jewett problem}\label{dhj-lower-sec}

The purpose of this section is to establish various lower bounds for $c_{n,3}$, in particular establishing Theorem \ref{dhj-lower} and the lower bound component of Theorem \ref{dhj-upper}.

As observed in the introduction, if $B \subset \Delta_{n,3}$ is a Fujimura set (i.e. a subset of $\Delta_{n,3} = \{ (a,b,c) \in \N^3: a+b+c=n\}$ which contains no upward equilateral triangles $(a+r,b,c), (a,b+r,c), (a,b,c+r)$), then the set $A_B := \bigcup_{\vec a \in B} \Gamma_{a,b,c}$ is a line-free subset of $[3]^n$, which gives the lower bound \begin{equation}\label{cn3}

c_{n,3} \geq |A_B| = \sum_{(a,b,c) \in B} \frac{n!}{a! b! c!}.

\end{equation} All of the lower bounds for $c_{n,3}$ in this paper will be constructed via this device. (Indeed, one may conjecture that for every $n$ there exists a Fujimura set $B$ for which \eqref{cn3} is attained with equality; we know of no counterexamples to this conjecture.)

In order to use \eqref{cn3}, one of course needs to build Fujimura sets $B$ which are ``large in the sense that the right-hand side of \eqref{cn3} is large. A fruitful starting point for this goal is the sets $$B_{j,n} := \{ (a,b,c) \in \Delta_{n,3}: a + 2b \neq j \hbox{ mod } 3 \}$$ for $j=0,1,2$. Observe that in order for a triangle $(a+r,b,c), (a,b+r,c), (a,b,c+r)$ to lie in $B_{j,n}$, the length $r$ of the triangle must be a multiple of $3$. This already makes $B_{j,n}$ a Fujimura set for $n < 3$ (and $B_{0,n}$ a Fujimura set for $n = 3$).

When $n$ is not a multiple of $3$, the $B_{j,n}$ are all rotations of each other and give equivalent sets (of size $2 \times 3^{n-1}$). When $n$ is a multiple of $3$, the sets $B_{1,n}$ and $B_{2,n}$ are reflections of each other, but $B_{0,n}$ is not equivalent to the other two sets (in particular, it omits all three corners of $\Delta_{n,3}$); the associated set $A_{B_{0,n}}$ is slightly larger than $A_{B_{1,n}}$ and $A_{B_{2,n}}$ and thus is slightly better for constructing line-free sets.

As mentioned already, $B_{0,n}$ is a Fujimura set for $n \leq 3$, and hence $A_{B_{0,n}}$ is line-free for $n \leq 3$. Applying \eqref{cn3} one obtains the lower bounds $$ c_{0,3} \geq 1; c_{1,3} \geq 2; c_{2,3} \geq 6; c_{3,3} \geq 18.$$

For $n>3$, $B_{0,n}$ contains some triangles $(a+r,b,c), (a,b+r,c), (a,b,c+r)$ and so is not a Fujimura set, but one can remove points from this set to recover the Fujimura property. For instance, for $n \leq 6$, the only triangles in $B_{0,n}$ have side length $r=3$. One can ``delete these triangles by removing one vertex from each; in order to optimise the bound \eqref{cn3} it is preferable to delete vertices near the corners of $\Delta_{n,3}$ rather than near the centre. These considerations lead to the Fujimura sets \begin{align*} B_{0,4} &\backslash \{ (0,0,4), (0,4,0), (4,0,0) \}\\ B_{0,5} &\backslash \{ (0,4,1), (0,5,0), (4,0,1), (5,0,0) \}\\ B_{0,6} &\backslash \{ (0,1,5), (0,5,1), (1,0,5), (0,1,5), (1,5,0), (5,1,0) \} \end{align*} which by \eqref{cn3} gives the lower bounds $$ c_{4,3} \geq 52; c_{5,3} \geq 150; c_{6,3} \geq 450.$$ Thus we have established all the lower bounds needed for Theorem \ref{dhj-upper}.

One can of course continue this process by hand, for instance the set $$ B_{0,7} \backslash \{(0,1,6),(1,0,6),(0,5,2),(5,0,2),(1,5,1),(5,1,1),(1,6,0),(6,1,0) \}$$ gives the lower bound $c_{7,3} \geq 1302$, which we tentatively conjecture to be the correct bound.

A simplification was found when $n$ is a multiple of $3$. Observe that for $n=6$, the sets excluded from $B_{0,6}$ are all permutations of $(0,1,5)$. So the remaining sets are all the permutations of $(1,2,3)$ and $(0,2,4)$. In the same way, sets for $n=9$, $12$ and $15$ can be described as: \begin{itemize} \item $n=9$: $(2,3,4),(1,3,5),(0,4,5)$ and permutations; \item $n=12$: $(3,4,5),(2,4,6),(1,5,6),(0,2,10),(0,5,7)$ and permutations; \item $n=15$: $(4,5,6),(3,5,7),(2,6,7),(1,3,11),(1,6,8),(0,4,11),(0,7,8)$ and permutations. \end{itemize}

When $n$ is not a multiple of $3$, say $n=3m-1$ or $n=3m-2$, one first finds a solution for $n=3m$. Then for $n=3m-1$, one restricts the first digit of the $3m$ sequence to equal $1$. This leaves exactly one-third as many points for $3m-1$ as for $3m$. For $n=3m-1$, one restricts the first two digits of the $3m$ sequence to be $12$. This leaves roughly one-ninth as many points for $3m-2$ as for $3m$.

An integer program\footnote{Details of the integer programming used in this paper can be found at the page {\tt Integer.tex} at \cite{polywiki}.} was run to obtain the maximum lower bound one could establish from \eqref{cn3}. The results for $1 \leq n \leq 20$ are displayed in Figure \ref{nlow}:

\begin{figure}[tb] \centerline{ \begin{tabular}{|ll|ll|} \hline $n$ & lower bound & $n$ & lower bound \\ \hline 1 & 2 &11& 96338\\ 2 & 6 & 12& 287892\\ 3 & 18 & 13& 854139\\ 4 & 52 & 14& 2537821\\ 5 & 150& 15& 7528835\\ 6 & 450& 16& 22517082\\ 7 & 1302& 17& 66944301\\ 8 & 3780&18& 198629224\\ 9 & 11340&19& 593911730\\ 10& 32864& 20& 1766894722\\ \hline \end{tabular}} \caption{Lower bounds for $c_n$ obtained by the $A_B$ construction.} \label{nlow} \end{figure}

More complete data, including the list of optimisers, can be found at \cite{markstrom}.

For medium values of $n$, in particular for integers $21 \leq n \leq 999$ that are a multiple of $3$, $n=3m$, the best general lower bound for $c_{n,3}$ was found by applying \eqref{cn3} to the following Fujimura set construction It is convenient to write $[a,b,c]$ for the point $(m+a,m+b,m+c)$, together with its permutations, with the convention that $[a,b,c]$ is empty if these points do not lie in $\Delta_{n,3}$. Then a Fujimura set can be constructed by taking the following groups of points:

\begin{enumerate} \item The thirteen groups of points $$[-7,-3,+10], [-7, 0,+7], [-7,+3,+4], [-6,-4,+10], [-6,-1,+7], [-6,+2,+4]$$ $$[-5,-1,+6],[-5,+2,+3],[-4,-2,+6], [-4,+1,+3], [-3,+1,+2], [-2,0,+2], [-1,0,+1];$$ \item The four families of groups $$[-8-y-2x,-6+y-2x,14+4x], [-8-y-2x,-3+y-2x,11+4x], $$ $$[-8-y-2x,x+y,8+x], [-8-2x,3+x,5+x]$$ for $x \geq 0$ and $y=0,1$. \end{enumerate}

Numerical computation shows that this construction gives a line-free set in $[3]^n$ of density approximately $2.7 \sqrt{\frac{\log n}{n}}$ for $n \leq 1000$; for instance, when $n=99$, it gives a line-free set of density at least $1/3$. Some additional constructions of this type can be found at the page {\tt Upper and lower bounds} at \cite{polywiki}.

However, the bounds in Theorem \ref{dhj-lower}, which we now prove, are asymptotically superior to these constructions.

\begin{proof}[Proof of Theorem \ref {dhj-lower}] Let $M$ be the circulant matrix with first row $(1,2,\ldots,k-1)$, second row $(k-1,1,2,\dots,k-2)$, and so on. Note that $M$ has nonzero determinant by well-known properties\footnote{For instance, if we let $A_i$ denote the $i^{th}$ row, we see that $(A_1-A_2)+(A_{i+1}-A_i)$ is of the form $(0,\ldots,0,-k+1,0,\ldots,0,k-1)$, and so the row space spans all the vectors whose coordinates to zero; but the first row has a non-zero coordinate sum, so the rows in fact span the whole space.} of circulant matrices, see e.g. \cite[Theorem 3]{kra}.

Let $S$ be a subset of the interval $[-\sqrt {n}/2, \sqrt {n}/2)$ that contains no nonconstant arithmetic progressions of length $k$, and let $B\subset\Delta_{n, k}$ be the set

   \[ B := \{(n-\sum_{i=1}^{k-1} a_i ,a_1,a_2,\dots, a_{k-1}) : 
           (a_1,\dots,a_{k-1})= c + \det(M) M^{-1} s , s\in S^{k-1}\},\]

where $c$ is the $k-1$-dimensional vector, all of whose entries are equal to $\lfloor n/k \rfloor$. The map $(m,a_1,\dots,a_{k-1}) \mapsto M (a_1,\dots,a_{k-1})$ takes simplices in $\Delta_{n,k}$ to nonconstant arithmetic progressions in ${\mathbb Z}^{k-1}$, and takes $B$ to $\{M c +\det(M) \, s \colon s \in S^{k-1}\}$, which is a set containing no nonconstant arithmetic progressions. Thus, $B$ is a Fujimura set and so does not contain any combinatorial lines.

If all of $a_1,\ldots,a_k$ are within $C_1\sqrt{n}$ of $n/k$, then $|\Gamma_{\vec{a}}| \geq C k^n/n^{(k-1)/2}$ (where $C$ depends on $C_1$) by the central limit theorem. By our choice of $S$ and applying~\eqref{cn3} (or more precisely, the obvious generalisation of \eqref{cn3} to other values of $k$), we obtain

    $$ c_ {n, k}\geq C k^n/n^{(k-1)/2} |S|^{k-1} = C k^n \left( \frac{|S|}{\sqrt{n}} \right)^{k-1}. $$

One can take $S$ to have cardinality $r_ k (\sqrt {n}) $, which from the results of O'Bryant~\cite {obryant} satisfies (for all sufficiently large $n$, some $C>0$, and $\ell$ the largest integer satisfying $k> 2^{\ell-1}$)

    $$ \frac{r_k (\sqrt{n})}{\sqrt{n}} \geq C  (\log n)^{1/(2\ell)}\exp_2 (-\ell 2^{(\ell-1)/2-1/\ell} \sqrt[\ell]{\log_2 n}),$$

which completes the proof. \end {proof}