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_{3,n}$ is a Fujimura set (i.e. a subset of $\Delta_{3,n} = \{ (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.

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_{3,n}: 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_{3,n}$); 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_{3,n}$ 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.

{\bf need discussion here of how one can get lower bounds for higher $n$, e.g. $n=100$.}

Now we prove Theorem \ref{dhj-lower}.

\begin{proof}[Proof of Theorem \ref{dhj-lower}] In view of the obvious inequality $c_{n,3} \leq c_{n+1,3}$ we may assume that $n$ is a multiple of $3$. Let $R$ be a subset of the interval $(-3\sqrt{n}/2,3\sqrt{n}/2)\cap {\mathbb Z}$ consisting entirely of multiples of 3, and which contains no arithmetic progressions of length 3. Next, let $B \subset \Delta_{n,3}$ be the set $$ B := \{ (\frac{n-r-s}{3}, \frac{n+2r-s}{3}, \frac{n-r+2s}{3}): r,s \in R \}.$$ Observe that if $(a,b,c) \in B$, then $c-a \in R$. On the other hand, the map $(a,b,c) \mapsto c-a$ maps any equilateral triangle $(a+r,b,c), (a,b+r,c), (a,b,c+r)$ to an arithmetic progression of length three. Since $R$ does not have any such progressions by construction, $B$ is a Fujimura set, and therefore does not contain any combinatorial lines.

On the other hand, from Stirling's formula we see that $|\Gamma_{a,b,c}| \geq C 3^n / n$ for all $(a,b,c) \in B$ and some absolute constant $C$. Applying \eqref{cn3} we obtain $$ c_{n,3} \geq C |R|^2 3^n / n$$. One can take $R$ to have cardinality $r_3(\sqrt{n})$, which from the results of Elkin~\cite{elkin} (see also~\cite{greenwolf} and~\cite{obryant}) satisfies (for all sufficiently large $n$) $$ r_3(\sqrt{n}) \geq \sqrt{n} (\log n)^{1/4} \exp_2(-2 \sqrt{2} \sqrt{\log_2 n}),$$ which completes the proof. \end{proof}