Polymath Wiki - User contributions [en]

Dhj-lown.tex

2009-06-05T12:26:58Z

98.113.21.246: commented out k=3 case of Theorem 1.3; Minor formatting changes

\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}]
%Let $S$ be a subset of the interval $[-\sqrt {n}/2, \sqrt {n}/2)$ that contains no arithmetic
%progressions of length 3, and let $B\subset\Delta_{n, 3}$ be the set
% \[ B := \{(n-s-t,s-2t,-2s+t) : s,t \in S\}.\]
%The map $(a,b,c)\mapsto (b+2c,2b+c)$ takes simplices to nonconstant arithmetic progressions,
%and takes $B$ to $\{-3(s,t)\colon s,t \in S\}$, which is a set %containing no nonconstant
%arithmetic progressions. Thus, $B$ is a Fujimora set and so does not contain any combinatorial lines.
%
%If all of $a,b,c$ are within $C_1\sqrt{n}$ of $n/3$, then $ | \Gamma_ {a, b, c} | \geq C 3^n/n$
%(where $C$ depends on $C_1$) by the central limit theorem. By %our choice of $S$ and applying~\eqref{cn3}, we obtain
% $$ c_ {n, 3}\geq C |S| ^2 3^n/n. $$
%One can take $S$ to have cardinality $r_ 3 (\sqrt {n}) $, which from the results of Elkin~\cite {elkin}
%(see also~\cite{greenwolf,obryant}) satisfies (for all sufficiently %large $n$)
% $$ r_ 3 (\sqrt {n})\geq\sqrt {n} (\log n)^{1/4}\exp_ 2 (-2\sqrt {\log_ 2 n}),$$
%which completes the proof.
%\end {proof}

\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,2,\dots,k-1)$, and so on. Note that $M$ has nonzero determinant by well-known properties of circulant matrices.

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})= \det(M) M^{-1}\vec{s} , \vec{s}\in S^{k-1}\}.\]
The map $(m,a_1,\dots,a_{k-1}) \mapsto M (a_1,\dots,a_{k-1})$ takes simplices to nonconstant arithmetic progressions in ${\mathbb Z}^{k-1}$, and takes $B$ to $\{det(M) \, \vec{s} \colon \vec{s} \in S^{k-1}\}$, which is a set containing no nonconstant arithmetic progressions. Thus, $B$ is a Fujimora 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}, 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}

Dhj-lown.tex

2009-06-03T19:46:07Z

98.113.21.246:

\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}]
Assume, for now, that $n$ is a multiple of $k$. Let $S$ be a subset of the interval $ (-3\sqrt {n}/2, 3\sqrt {n}/2)\cap {3\mathbb Z} $ that contains no arithmetic progressions of length 3. Next, let $B\subset\Delta_{n, 3}$ be the set
\[ B := \{(n-s-t,2s-t,2t-s) : s,t \in S\}.\]
The map $(a,b,c)\mapsto (c-a,b-a)$ takes simplices to nonconstant arithmetic progressions, and takes $B$ to $\{(3t-n,3s-n)\colon s,t \in S\}$, which is a set containing no nonconstant arithmetic progressions. Thus, $B$ is a Fujimora set and so does not contain any combinatorial lines.

If all of $a,b,c$ are with $C_1\sqrt{n}$ of $n/3$, then $ | \Gamma_ {a, b, c} | \geq C_2 3^n/n$ (where $C_2$ depends on $C_1$) by the central limit theorem. By our choice of $S$ and applying~\eqref{cn3}, we obtain
$$ c_ {n, 3}\geq C_2 | 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 {\log_ 2 n}),$$
which completes the proof for $n$ a multiple of $3$. But in view of the inequalities $c_ {n, 3}\leq c_ {n + 1, 3}\leq 3 c_ {n, 3} $, we can handle $n$ that are not multiples of 3 by replacing $C_2$ with $C_2/9$.
\end {proof}