Difference between revisions of "Moser-lower.tex"

From Polymath1Wiki
Jump to: navigation, search
 
(23 intermediate revisions by 3 users not shown)
Line 1: Line 1:
 
\section{Lower bounds for the Moser problem}\label{moser-lower-sec}
 
\section{Lower bounds for the Moser problem}\label{moser-lower-sec}
  
In this section we discuss lower bounds for $c'_{n,3}$. Clearly we have  
+
Just as for the density Hales-Jewett problem, we found that Gamma sets $\Gamma_{a,b,c}$ were useful in providing large lower bounds for the Moser problem.  This is despite the fact that the symmetries of the cube do not respect Gamma sets.
 +
 
 +
Observe that if $B \subset \Delta_n$, then the set $A_B := \bigcup_{\vec a \in B} \Gamma_{a,b,c}$ is a Moser set as long as $B$ does not contain any ``isosceles triangles'' $(a+r,b,c+s), (a+s,b,c+r), (a,b+r+s,c)$ for any $r,s \geq 0$ not both zero; in particular, $B$ cannot contain any ``vertical line segments'' $(a+r,b,c+r), (a,b+2r,c)$.  An example of such a set is provided by selecting $0 \leq i \leq n-3$ and letting $B$ consist of the triples $(a, n-i, i-a)$ when $a \neq 3 \mod 3$, $(a,n-i-1,i+1-a)$ when $a \neq 1 \mod 3$, $(a,n-i-2,i+2-a)$ when $a=0 \mod 3$, and $(a,n-i-3,i+3-a)$ when $a=2 \mod 3$.  Asymptotically, this set includes about two thirds of the spheres $S_{n,i}$, $S_{n,i+1}$ and one third of the spheres $S_{n,i+2}, S_{n,i+3}$ and (setting $i$ close to $n/3$) gives a lower bound \eqref{cpn3} with $C = 2 \times \sqrt{\frac{9}{4\pi}}$.
 +
 
 +
An integer program was run to obtain the optimal lower bounds achievable by the $A_B$ construction (using \eqref{cn3}, of course).  The results for $1 \leq n \leq 20$ are displayed in Figure \ref{nlow-moser}. More complete data, including the list of optimisers, can be found at
 +
 
 +
\centerline{{\tt http://abel.math.umu.se/$\sim$klasm/Data/HJ/}.}
 +
 
 +
 
 +
\begin{figure}[tb]
 +
\centerline{
 +
\begin{tabular}{|ll|ll|}
 +
\hline
 +
$n$ & lower bound & $n$ & lower bound \\
 +
\hline
 +
1 & 2 &11& 71766\\
 +
2 & 6 & 12& 212423\\
 +
3 & 16 & 13& 614875\\
 +
4 & 43 & 14& 1794212\\
 +
5 & 122& 15& 5321796\\
 +
6 & 353& 16& 15455256\\
 +
7 & 1017& 17& 45345052\\
 +
8 & 2902&18& 134438520\\
 +
9 & 8622&19& 391796798\\
 +
10& 24786& 20& 1153402148\\
 +
\hline
 +
\end{tabular}}
 +
\caption{Lower bounds for $c'_{n,3}$ obtained by the $A_B$ construction.}
 +
\label{nlow-moser}
 +
\end{figure}
 +
 
 +
 
 +
\begin{figure}[tb]
 +
\centerline{\includegraphics{moser353new.png}}
 +
\caption{One of the examples of $353$-point sets in $[3]^6$ (elements of the set being indicated by white squares).  This example was generated by a genetic algorithm.}
 +
\label{moser353-fig}
 +
\end{figure}
 +
 
 +
Unfortunately, we have been unable to locate a lower bound which is asymptotically better than \eqref{cpn3}.  Indeed, any method based purely on the $A_B$ construction cannot do asymptotically better than the previous constructions:
 +
 
 +
\begin{proposition}  Let $B \subset \Delta_n$ be such that $A_B$ is a Moser set.  Then $|A_B| \leq (2 \sqrt{\frac{9}{4\pi}} + o(1)) \frac{3^n}{\sqrt{n}}$.
 +
\end{proposition}
 +
 
 +
\begin{proof}  By the previous discussion, $B$ cannot contain any pair of the form $(a,b+2r,c), (a+r,b,c+r)$ with $r>0$.  In other words, for any $-n \leq h \leq n$, $B$ can contain at most one triple $(a,b,c)$ with $c-a=h$.  From this and \eqref{cn3}, we see that
 +
$$ |A_B| \leq \sum_{h=-n}^n \max_{(a,b,c) \in \Delta_n: c-a=h} \frac{n!}{a! b! c!}.$$
 +
From the Chernoff inequality (or the Stirling formula computation below) we see that $\frac{n!}{a! b! c!} \leq \frac{1}{n^{10}} 3^n$ unless $a,b,c = n/3 + O( n^{1/2} \log^{1/2} n )$, so we may restrict to this regime, which also forces $h = O( n^{1/2}\log^{1/2} n)$.  If we write $a = n/3 + \alpha$, $b = n/3 + \beta$, $c = n/3+\gamma$ and apply Stirling's formula $n! = (1+o(1)) \sqrt{2\pi n} n^n e^{-n}$, we obtain
 +
$$ \frac{n!}{a! b! c!} = (1+o(1)) \frac{3^{3/2}}{2\pi n} 3^n \exp( - (\frac{n}{3}+\alpha) \log (1 + \frac{3\alpha}{n} ) - (\frac{n}{3}+\beta) \log (1 + \frac{3\beta}{n} ) - (\frac{n}{3}+\gamma) \log (1 + \frac{3\gamma}{n} ) ).$$
 +
From Taylor expansion one has
 +
$$ -(\frac{n}{3}+\alpha) \log (1 + \frac{3\alpha}{n} ) = -\alpha - \frac{3}{2} \frac{\alpha^2}{n} + o(1)$$
 +
and similarly for $\beta,\gamma$; since $\alpha+\beta+\gamma=0$, we conclude that
 +
$$ \frac{n!}{a! b! c!} = (1+o(1)) \frac{3^{3/2}}{2\pi n} 3^n \exp( - \frac{3}{2n} (\alpha^2+\beta^2+\gamma^2) ).$$
 +
If $c-a=h$, then $\alpha^2+\beta^2+\gamma^2 = \frac{3\beta^2}{2} + \frac{h^2}{2}$.  Thus we see that
 +
$$ \max_{(a,b,c) \in \Delta_n: c-a=h} \frac{n!}{a! b! c!} \leq (1+o(1)) \frac{3^{3/2}}{2\pi n} 3^n \exp( - \frac{3}{4n} h^2 ).$$
 +
Using the integral test, we thus have
 +
$$ |A_B| \leq (1+o(1)) \frac{3^{3/2}}{2\pi n} 3^n  \int_\R \exp( - \frac{3}{4n} x^2 )\ dx.$$
 +
Since $\int_\R \exp( - \frac{3}{4n} x^2 )\ dx = \sqrt{\frac{4\pi n}{3}}$, we obtain the claim.
 +
\end{proof}
 +
 
 +
Actually it is possible to improve upon these bounds by a slight amount.  Observe that if $B$ is a maximiser for the right-hand side of \eqref{cn3} (subject to $B$ not containing isosceles triangles), then any triple $(a,b,c)$ not in $B$ must be the vertex of a (possibly degenerate) isosceles triangle with the other vertices in $B$.  If this triangle is non-degenerate, or if $(a,b,c)$ is the upper vertex of a degenerate isosceles triangle, then no point from $\Gamma_{a,b,c}$ can be added to $A_B$ without creating a geometric line. However, if $(a,b,c) = (a'+r,b',c'+r)$ is only the lower vertex of a degenerate isosceles triangle $(a'+r,b',c'+r), (a',b'+2r,c')$, then one can add any subset of $\Gamma_{a,b,c}$ to $A_B$ and still have a Moser set as long as no pair of elements in that subset is separated by Hamming distance $2r$.  For instance, in the $n=5$ case, we can start with the 122-point set built from
 +
$$B = \{ (0 0 5),(0 2 3),(1 1 3 ),(1 2 2 ),(2 2 1 ),(3 1 1 ),(3 2 0 ),(5 0 0))\}$$, and add a point each from (1 0 4) and (4 0 1).
 +
This gives an example of the maximal, 124-point solution.  Again, in the $n=10$ case, the set
 +
\begin{align*}
 +
B &= \{(0 0 10),(0 2 8 ),(0 3 7 ),(0 4 6 ),(1 4 5 ),(2 1 7 ),(2 3 5 ),
 +
(3 2 5 ),(3 3 4 ),(3 4 3 ),(4 4 2 ),(5 1 4 ), \\
 +
&\quad (5 3 2 ),(6 2 2 ),
 +
(6 3 1 ),(6 4 0 ),(8 1 1 ),(9 0 1 ),(9 1 0 ) \}
 +
\end{align*}
 +
 
 +
generates the lower bound $c'_{10,3} \geq 24786$ given above (and, up to reflection $a \leftrightarrow c$, is the only such set that does so); but by adding the following twelve elements from $\Gamma_{5,0,5}$ one can increase the lower bound slightly to $24798$: $1111133333$, $1111313333$,
 +
$1113113333$, $1133331113$, $1133331131$, $1133331311$, $3311333111$,
 +
$3313133111$, $3313313111$, $3331111133$, $3331111313$, $3331111331$
 +
 
 +
A more general form goes with the $B$ set described at the start of this section.  Include points from $\Gamma_{(a,n-i-4,i+4-a)}$ when $a=1 (\operatorname{mod}\ 3)$, subject to no two points being included if they differ by the interchange of a $1$ and a $3$.  Each of these Gamma sets is the feet of a degenerate isosceles triangle with vertex $\Gamma_{(a-1,n-i-2,a+3-a)}$. 
 +
 
 +
\begin{lemma} If $A$ is a subset of $\Gamma_{(a,b,c)}$ such that no two points of $A$ differ by the interchange of a $1$ and a $3$, then $|A| \leq |\Gamma_{a,b,c}|/(1+\max(a,c))$.
 +
\end{lemma}
 +
\begin{proof}
 +
Say that two points of $\Gamma_{a,b,c}$ are neighbours if they differ by the exchange of a $1$ and a $3$.  Each point of $A$ has $ac$ neighbours, none of which are in $A$. Each point of $\Gamma_{(a,b,c)}\backslash A$ has $ac$ neighbours, but only $min(a,c)$ of them may be in $A$. So for each point of $A$ there are on average $ac/\min(a,c) = \max(a,c)$ points not in $A$. So the proportion of points of $\Gamma_{(a,b,c)}$ that are in $A$ is at most one in $1+\max(a,c)$.
 +
\end{proof}
 +
 
 +
The proportion of extra points for each of the cells $\Gamma_{(a,n-i-4,i+4-a)}$ is no more than $2/(i+6)$.  Only one cell in three is included from the  $b=n-i-4$ layer, so we expect no more than $\binom{n}{i+4}2^{i+5}/(3i+18)$ new points, all from $S_{n,i+4}$.  One can also find extra points from $S_{n,i+5}$ and higher spheres.
 +
 
 +
Earlier solutions may also give insight into the problem.  In this section we discuss lower bounds for $c'_{n,3}$. Clearly we have  
 
$c'_{0,3}=1$ and $c'_{1,3}=2$, so we focus on the case $n \ge 2$.
 
$c'_{0,3}=1$ and $c'_{1,3}=2$, so we focus on the case $n \ge 2$.
 
The first lower bounds may be due to Koml\'{o}s \cite{komlos}, who observed  
 
The first lower bounds may be due to Koml\'{o}s \cite{komlos}, who observed  
Line 10: Line 92:
 
c'_{n,3}\geq \vert S_{i,n}\vert
 
c'_{n,3}\geq \vert S_{i,n}\vert
 
\end{equation}
 
\end{equation}
holds for all $i$. Choosing $i=\lfloor \frac{2n}{3}\rfloor$  and  
+
holds for all $i$. Choosing $i=\lfloor \frac{2n}{3}\rfloor$  and  
 
applying Stirling's formula, we see that this lower bound takes the form  
 
applying Stirling's formula, we see that this lower bound takes the form  
 
\begin{equation}\label{cpn3}
 
\begin{equation}\label{cpn3}
Line 18: Line 100:
 
In particular $c'_{3,3} \geq 12, c'_{4,3}\geq 24, c'_{5,3}\geq 80,  
 
In particular $c'_{3,3} \geq 12, c'_{4,3}\geq 24, c'_{5,3}\geq 80,  
 
c'_{6,3}\geq 240$.
 
c'_{6,3}\geq 240$.
Asymptotically, the best lower bounds we know of are still of this type,
+
 
but the values can be improved by studying combinations of several spheres or
+
These values can be improved by studying combinations of several spheres or
semispheres or applying elementary results from coding theory.
+
semispheres or applying elementary results from coding theory.
  
 
Observe that if $\{w(1),w(2),w(3)\}$ is a geometric line in $[3]^n$,  
 
Observe that if $\{w(1),w(2),w(3)\}$ is a geometric line in $[3]^n$,  
Line 33: Line 115:
 
least two.  
 
least two.  
 
(Recall Section \ref{notation-sec} for definitions),
 
(Recall Section \ref{notation-sec} for definitions),
this leads to the lower bound  
+
This leads to the lower bound  
 
\begin{equation}\label{cn3-low}
 
\begin{equation}\label{cn3-low}
c'_{n,3} \geq \binom{n}{i-1}  
+
c'_{n,3} \geq \binom{n}{i-1}  
 
2^{i-1} + \binom{n}{i} 2^{i-1} = \binom{n+1}{i} 2^{i-1}.
 
2^{i-1} + \binom{n}{i} 2^{i-1} = \binom{n+1}{i} 2^{i-1}.
 
\end{equation}
 
\end{equation}
Line 52: Line 134:
 
which we here translate into the usual notation of coding theory:
 
which we here translate into the usual notation of coding theory:
 
Let $A(n,d)$ denote the size of the largest binary code of length $n$
 
Let $A(n,d)$ denote the size of the largest binary code of length $n$
and minimal distance $d$.
+
and minimal distance $d$.
  
 
Then  
 
Then  
Line 59: Line 141:
 
\end{equation}
 
\end{equation}
  
With the following values for $A(n,d)$:
+
The following values of $A(n,d)$ for small $n,d$ are known, see \cite{Brower}:
 
{\tiny{
 
{\tiny{
 
\[
 
\[
Line 85: Line 167:
 
\]
 
\]
 
}}
 
}}
 
+
In addition, one has the general identities $A(n,1)=2^n, A(n,2)=2^{n-1}, A(n-1,2e-1)=A(n,2e)$, and $A(n,d)=2$,  
Generally, $A(n,1)=2^n, A(n,2)=2^{n-1}, A(n-1,2e-1)=A(n,2e), A(n,d)=2$,  
+
 
if $d>\frac{2n}{3}$.
 
if $d>\frac{2n}{3}$.
The values were taken or derived from Andries Brower's table at\\
 
http://www.win.tue.nl/$\sim$aeb/codes/binary-1.html
 
\textbf{include to references? or other book with explicit values of $A(n,d)$ }
 
 
  
For  $c'_{n,3}$ we obtain the following lower bounds:
+
Inserting this data into \eqref{cnchvatal} for $k=2$ we obtain the lower bounds
with $k=2$
+
 
\[
 
\[
 
\begin{array}{llll}
 
\begin{array}{llll}
 
c'_{4,3}&\geq &\binom{4}{0}A(4,3)+\binom{4}{1}A(3,2)+\binom{4}{2}A(2,1)
 
c'_{4,3}&\geq &\binom{4}{0}A(4,3)+\binom{4}{1}A(3,2)+\binom{4}{2}A(2,1)
=1\cdot 2+4 \cdot 4+6\cdot 4&=42.\\
+
=1\cdot 2+4 \cdot 4+6\cdot 4&=42\\
 
c'_{5,3}&\geq &\binom{5}{0}A(5,3)+\binom{5}{1}A(4,2)+\binom{5}{2}A(3,1)
 
c'_{5,3}&\geq &\binom{5}{0}A(5,3)+\binom{5}{1}A(4,2)+\binom{5}{2}A(3,1)
=1\cdot 4+5 \cdot 8+10\cdot 8&=124.\\
+
=1\cdot 4+5 \cdot 8+10\cdot 8&=124\\
 
c'_{6,3}&\geq &\binom{6}{0}A(6,3)+\binom{6}{1}A(5,2)+\binom{6}{2}A(4,1)
 
c'_{6,3}&\geq &\binom{6}{0}A(6,3)+\binom{6}{1}A(5,2)+\binom{6}{2}A(4,1)
 
=1\cdot 8+6 \cdot 16+15\cdot 16&=344.
 
=1\cdot 8+6 \cdot 16+15\cdot 16&=344.
 
\end{array}
 
\end{array}
 
\]
 
\]
With k=3
+
Similarly, with $k=3$ we obtain
 
\[
 
\[
 
\begin{array}{llll}
 
\begin{array}{llll}
Line 111: Line 187:
 
+ \binom{7}{3}A(4,1)&=960.\\
 
+ \binom{7}{3}A(4,1)&=960.\\
 
c'_{8,3}&\geq &\binom{8}{0}A(8,4)+\binom{8}{1}A(7,3)+\binom{8}{2}A(6,2)
 
c'_{8,3}&\geq &\binom{8}{0}A(8,4)+\binom{8}{1}A(7,3)+\binom{8}{2}A(6,2)
+ \binom{8}{3}A(5,1)&=2832.\\
+
+ \binom{8}{3}A(5,1)&=2832\\
 
c'_{9,3}&\geq & \binom{9}{0}A(9,4)+\binom{9}{1}A(8,3)+\binom{9}{2}A(7,2)
 
c'_{9,3}&\geq & \binom{9}{0}A(9,4)+\binom{9}{1}A(8,3)+\binom{9}{2}A(7,2)
+ \binom{9}{3}A(6,1)&=7880.
+
+ \binom{9}{3}A(6,1)&=7880
 
\end{array}\]
 
\end{array}\]
With k=4
+
and for $k=4$ we have
 
\[
 
\[
 
\begin{array}{llll}
 
\begin{array}{llll}
 
c'_{10,3}&\geq &\binom{10}{0}A(10,5)+\binom{10}{1}A(9,4)+\binom{10}{2}A(8,3)
 
c'_{10,3}&\geq &\binom{10}{0}A(10,5)+\binom{10}{1}A(9,4)+\binom{10}{2}A(8,3)
+ \binom{10}{3}A(7,2)+\binom{10}{4}A(6,1)&=22232.\\
+
+ \binom{10}{3}A(7,2)+\binom{10}{4}A(6,1)&=22232\\
 
c'_{11,3}&\geq &\binom{11}{0}A(11,5)+\binom{11}{1}A(10,4)+\binom{11}{2}A(9,3)
 
c'_{11,3}&\geq &\binom{11}{0}A(11,5)+\binom{11}{1}A(10,4)+\binom{11}{2}A(9,3)
+ \binom{11}{3}A(8,2)+\binom{11}{4}A(7,1)&=66024.\\
+
+ \binom{11}{3}A(8,2)+\binom{11}{4}A(7,1)&=66024\\
 
c'_{12,3}&\geq &\binom{12}{0}A(12,5)+\binom{12}{1}A(11,4)+\binom{12}{2}A(10,3)
 
c'_{12,3}&\geq &\binom{12}{0}A(12,5)+\binom{12}{1}A(11,4)+\binom{12}{2}A(10,3)
 
+ \binom{12}{3}A(9,2)+\binom{12}{4}A(8,1)&=188688.\\
 
+ \binom{12}{3}A(9,2)+\binom{12}{4}A(8,1)&=188688.\\
 
\end{array}\]
 
\end{array}\]
With $k=5$
+
and for $k=5$ we have
 
\[ c'_{13,3}\geq 539168.\]
 
\[ c'_{13,3}\geq 539168.\]
  
Line 133: Line 209:
  
 
The maximum value  appears to occur for $k=\lfloor\frac{n+2}{3}\rfloor$,  
 
The maximum value  appears to occur for $k=\lfloor\frac{n+2}{3}\rfloor$,  
so that using  
+
so that using Stirling's formula and explicit bounds on $A(n,d)$ the  
Stirling's formula and explicit bounds on $A(n,d)$ the  
+
 
best possible value known to date
 
best possible value known to date
of the constant $C$ in  
+
of the constant $C$ in equation \eqref{cpn3} can be worked out, but we refrain from doing this here.
equation \eqref{cpn3} can be worked out, but we refrain from doing this here.
+
Using the singleton bound $A(n,d)\leq 2^{n-d+1}$ Chv\'{a}tal   
Using the Singleton bound $A(n,d)\leq 2^{n-d+1}$ Chv\'{a}tal   
+
 
\cite{chvatal1} proved that the expression on the right hand side of
 
\cite{chvatal1} proved that the expression on the right hand side of
 
\eqref{cnchvatal} is also  
 
\eqref{cnchvatal} is also  
Line 147: Line 221:
 
The value $c'_{4,3}=43$ was first proven by Chandra \cite{chandra}.
 
The value $c'_{4,3}=43$ was first proven by Chandra \cite{chandra}.
 
A uniform way of describing examples for the optimum values of  
 
A uniform way of describing examples for the optimum values of  
$c'_{4,3}=43$ and $c'_{5,3}=124$ is the following:
+
$c'_{4,3}=43$ and $c'_{5,3}=124$ is as follows.
  
 
Let us consider the sets $$ A := S_{i-1,n}  
 
Let us consider the sets $$ A := S_{i-1,n}  
Line 168: Line 242:
 
the bound for $n=6$ is inferior to the lower bound $c'_{6,3}\geq 344$ given above.  
 
the bound for $n=6$ is inferior to the lower bound $c'_{6,3}\geq 344$ given above.  
 
   
 
   
A modification of the construction in \eqref{cn3-low} leads to a slightly better lower bound.  Observe that if $B \subset \Delta_n$, then the set $A_B := \bigcup_{\vec a \in B} \Gamma_{a,b,c}$ is a Moser set as long as $B$ does not contain any ``isosceles triangles'' $(a+r,b,c+s), (a+s,b,c+r), (a,b+r+s,c)$ for any $r,s \geq 0$ not both zero; in particular, $B$ cannot contain any ``vertical line segments'' $(a+r,b,c+r), (a,b+2r,c)$.  An example of such a set is provided by selecting $0 \leq i \leq n-3$ and letting $B$ consist of the triples $(a, n-i, i-a)$ when $a \neq 3 \mod 3$, $(a,n-i-1,i+1-a)$ when $a \neq 1 \mod 3$, $(a,n-i-2,i+2-a)$ when $a=0 \mod 3$, and $(a,n-i-3,i+3-a)$ when $a=2 \mod 3$.  Asymptotically, this set occues about two thirds of the spheres $S_{n,i}$, $S_{n,i+1}$ and one third of the spheres $S_{n,i+2}, S_{n,i+3}$ and (setting $i$ close to $n/3$) gives a lower bound \eqref{cpn3} with $C = 2 \times \frac{\sqrt{9}}{4\pi}$, which is thus superior to the previous constructions.
 
  
An integer program was run to obtain the optimal lower bounds achievable by the $A_B$ construction (using \eqref{cn3}, of course).  The results for
+
\subsection{Higher $k$ values}
$1 \leq n \leq 20$ are displayed in Figure \ref{nlow-moser}:
+
  
\begin{figure}[tb]
+
We now consider lower bounds for $c'_{n,k}$ for some values of $k$ larger than $3$. Here we will see some further connections between the Moser problem and the density Hales-Jewett problem.
\centerline{
+
\begin{tabular}{|ll|ll|}
+
\hline
+
n & lower bound & n & lower bound \\
+
\hline
+
1 & 2 &11& 71766\\
+
2 & 6 & 12& 212423\\
+
3 & 16 & 13& 614875\\
+
4 & 43 & 14& 1794212\\
+
5 & 122& 15& 5321796\\
+
6 & 353& 16& 15455256\\
+
7 & 1017& 17& 45345052\\
+
8 & 2902&18& 134438520\\
+
9 & 8622&19& 391796798\\
+
10& 24786& 20& 1153402148\\
+
\hline
+
\end{tabular}}
+
\caption{Lower bounds for $c'_n$ obtained by the $A_B$ construction.}
+
\label{nlow-moser}
+
\end{figure}
+
  
More complete data, including the list of optimisers, can be found at {\tt http://abel.math.umu.se/~klasm/Data/HJ/}.
+
For $k=4$, we have the lower bounds $c'_{n,4} \ge \binom{n}{n/2}2^n$. To see this, observe that the set of points with $a$ $1$s,$b$ $2$s,$c$ $3$s and $d$ $4$s, where $a+d$ has the constant value $n/2$, does not form geometric lines because points at the ends of a geometric line have more $a$ or $d$ values than points in the middle of the line.
  
This indicates that greedily filling in spheres,
+
The following lower bound is asymptotically twice as large.  Take all points with $a$ $1$s, $b$ $2$s, $c$ $3$s and $d$ $4$s, for which:
semispheres or codes is no longer the optimal strategy in dimensions six and higher.  The lower bound $c'_{6,3} \geq 353$ was first located by a genetic algorithm: see Appendix \ref{genetic-alg}.
+
  
\begin{figure}[tb]
+
\begin{itemize}
\centerline{\includegraphics{moser353new.png}}
+
\item Either $a+d = q$ or $q-1$, $a$ and $b$ have the same parity; or
\caption{One of the examples of $353$-point sets in $[3]^6$ (elements of the set being indicated by white squares).}
+
\item $a+d = q-2$ or $q-3$, $a$ and $b$ have opposite parity.
\label{moser353-fig}
+
\end{itemize}
\end{figure}
+
  
 +
This includes half the points of four adjacent layers, and therefore may include $(1+o(1))\binom{n}{n/2}2^{n+1}$ points.
  
Actually it is possible to improve upon these bounds by a slight amount.  Observe that if $B$ is a maximiser for the right-hand side of \eqref{cn3} (subject to $B$ not containing isosceles triangles), then any triple $(a,b,c)$ not in $B$ must be the vertex of a (possibly degenerate) isosceles triangle with the other vertices in $B$.  If this triangle is non-degenerate, or if $(a,b,c)$ is the upper vertex of a degenerate isosceles triangle, then no point from $\Gamma_{a,b,c}$ can be added to $A_B$ without creating a geometric line. However, if $(a,b,c) = (a'+r,b',c'+r)$ is only the lower vertex of a degenerate isosceles triangle $(a'+r,b',c'+r), (a',b'+2r,c')$, then one can add any subset of $\Gamma_{a,b,c}$ to $A_B$ and still have a Moser set as long as no pair of elements in that subset is separated by Hamming distance $2r$.  For instance, in the $n=8$ case, the set
+
We also have a lower bound for $c'_{n,5}$ similar to Theorem \ref{dhj-lower}, namely $c'_{n,5} = 5^{n-O(\sqrt{\log n})}$. Consider points with $a$ $1$s, $b$ $2$s, $c$ $3$s, $d$ $4$s and $e$ $5$s.  For each point, take the value $a+e+2(b+d)+3c$.  The first three points in any geometric line give values that form an arithmetic progression of length three.
$$ B = \{ (0,1,7), (0 3 5),(1 0 7), (1 2 5), (1 3 4), (1 4 3), (2 4 2), (3 1 4), (3 3 2), (4 2 2), (4 3 1),(4 4 0), (6 1 1),(7 0 1),(7 1 0) \}$$
+
generates the lower bound $c'_{8,3} \geq 2902$ given above (and, up to reflection $a \leftrightarrow c$, is the only such set that does so); but by adding the four elements $11333333, 33113333, 33331133, 33333311$ from $\Gamma_{2,0,6}$ one can increase the lower bound slightly to $2906$.
+
  
However, we have been unable to locate a lower bound which is asymptotically better than \eqref{cpn3}.  Indeed, any method based purely on the $A_B$ construction cannot do asymptotically better than the previous constructions:
+
Select a set of integers with no arithmetic progression of length $3$.  Select all points whose value belongs to that sequence; there will be no geometric line among those points.  By the Behrend construction\cite{behrend}, it is possible to choose these points with density $\exp{-O(\sqrt{\log n})}$.
  
\begin{proposition}  Let $B \subset \Delta_n$ be such that $A_B$ is a Moser set.  Then $|A_B| \leq (2 \sqrt{\frac{9}{4\pi}} + o(1)) \frac{3^n}{\sqrt{n}}$.
+
For $k=6$, we observe that the asymptotic $c'_{n,6} = o(6^n)$ would imply the $k=3$ density Hales-Jewett theorem $c_{n,3}=o(3^n)$. Indeed, any $k=3$ combinatorial line-free set can be ``doubled up'' into a $k=6$ geometric line-free set of the same density by pulling back the set from the map that maps $1, 2, 3, 4, 5, 6$ to $1, 2, 3, 3, 2, 1$ respectively; note that this map sends $k=6$ geometric lines to $k=3$ combinatorial linesSo $c'_{n,6} \geq 2^n c_{n,3}$, and more generally, $c'_{n,2k} \geq 2^n c_{n,k}$.
\end{proposition}
+
 
+
\begin{proof}  By the previous discussion, $B$ cannot contain any pair of the form $(a,b+2r,c), (a+r,b,c+r)$ with $r>0$. In other words, for any $-n \leq h \leq n$, $B$ can contain at most one triple $(a,b,c)$ with $c-a=h$.  From this and \eqref{cn3}, we see that
+
$$ |A_B| \leq \sum_{h=-n}^n \max_{(a,b,c) \in \Delta_n: c-a=h} \frac{n!}{a! b! c!}.$$
+
From the Chernoff inequality (or the Stirling formula computation below) we see that $\frac{n!}{a! b! c!} \leq \frac{1}{n^{10}} 3^n$ unless $a,b,c = n/3 + O( n^{1/2} \log^{1/2} n )$, so we may restrict to this regime, which also forces $h = O( n^{1/2}/\log^{1/2} n)$.  If we write $a = n/3 + \alpha$, $b = n/3 + \beta$, $c = n/3+\gamma$ and apply Stirling's formula $n! = (1+o(1)) \sqrt{2\pi n} n^n e^{-n}$, we obtain
+
$$ \frac{n!}{a! b! c!} = (1+o(1)) \frac{3^{3/2}}{2\pi n} 3^n \exp( - (\frac{n}{3}+\alpha) \log (1 + \frac{3\alpha}{n} ) - (\frac{n}{3}+\beta) \log (1 + \frac{3\beta}{n} ) - (\frac{n}{3}+\gamma) \log (1 + \frac{3\gamma}{n} ) ).$$
+
From Taylor expansion one has
+
$$ (\frac{n}{3}+\alpha) \log (1 + \frac{3\alpha}{n} ) = -\alpha - \frac{3}{2} \frac{\alpha^2}{n} + o(1)$$
+
and similarly for $\beta,\gamma$; since $\alpha+\beta+\gamma=0$, we conclude that
+
$$ \frac{n!}{a! b! c!} = (1+o(1)) \frac{3^{3/2}}{2\pi n} 3^n \exp( - \frac{3}{2n} (\alpha^2+\beta^2+\gamma^2) ).$$
+
If $c-a=h$, then $\alpha^2+\beta^2+\gamma^2 = \frac{3\beta^2}{2} + \frac{h^2}{2}$.  Thus we see that
+
$$ \max_{(a,b,c) \in \Delta_n: c-a=h} \frac{n!}{a! b! c!} \leq (1+o(1)) \frac{3^{3/2}}{2\pi n} 3^n \exp( - \frac{3}{4n} h^2 ).$$
+
Using the integral test, we thus have
+
$$ |A_B| \leq (1+o(1)) \frac{3^{3/2}}{2\pi} 3^n \int_\R \exp( - \frac{3}{4n} x^2 )\ dx.$$
+
Since $\int_\R \exp( - \frac{3}{4n} x^2 )\ dx = \sqrt{\frac{4\pi n}{3}}$, we obtain the claim.
+
\end{proof}
+

Latest revision as of 19:34, 19 January 2010

\section{Lower bounds for the Moser problem}\label{moser-lower-sec}

Just as for the density Hales-Jewett problem, we found that Gamma sets $\Gamma_{a,b,c}$ were useful in providing large lower bounds for the Moser problem. This is despite the fact that the symmetries of the cube do not respect Gamma sets.

Observe that if $B \subset \Delta_n$, then the set $A_B := \bigcup_{\vec a \in B} \Gamma_{a,b,c}$ is a Moser set as long as $B$ does not contain any ``isosceles triangles $(a+r,b,c+s), (a+s,b,c+r), (a,b+r+s,c)$ for any $r,s \geq 0$ not both zero; in particular, $B$ cannot contain any ``vertical line segments $(a+r,b,c+r), (a,b+2r,c)$. An example of such a set is provided by selecting $0 \leq i \leq n-3$ and letting $B$ consist of the triples $(a, n-i, i-a)$ when $a \neq 3 \mod 3$, $(a,n-i-1,i+1-a)$ when $a \neq 1 \mod 3$, $(a,n-i-2,i+2-a)$ when $a=0 \mod 3$, and $(a,n-i-3,i+3-a)$ when $a=2 \mod 3$. Asymptotically, this set includes about two thirds of the spheres $S_{n,i}$, $S_{n,i+1}$ and one third of the spheres $S_{n,i+2}, S_{n,i+3}$ and (setting $i$ close to $n/3$) gives a lower bound \eqref{cpn3} with $C = 2 \times \sqrt{\frac{9}{4\pi}}$.

An integer program was run to obtain the optimal lower bounds achievable by the $A_B$ construction (using \eqref{cn3}, of course). The results for $1 \leq n \leq 20$ are displayed in Figure \ref{nlow-moser}. More complete data, including the list of optimisers, can be found at

\centerline{{\tt http://abel.math.umu.se/$\sim$klasm/Data/HJ/}.}


\begin{figure}[tb] \centerline{ \begin{tabular}{|ll|ll|} \hline $n$ & lower bound & $n$ & lower bound \\ \hline 1 & 2 &11& 71766\\ 2 & 6 & 12& 212423\\ 3 & 16 & 13& 614875\\ 4 & 43 & 14& 1794212\\ 5 & 122& 15& 5321796\\ 6 & 353& 16& 15455256\\ 7 & 1017& 17& 45345052\\ 8 & 2902&18& 134438520\\ 9 & 8622&19& 391796798\\ 10& 24786& 20& 1153402148\\ \hline \end{tabular}} \caption{Lower bounds for $c'_{n,3}$ obtained by the $A_B$ construction.} \label{nlow-moser} \end{figure}


\begin{figure}[tb] \centerline{\includegraphics{moser353new.png}} \caption{One of the examples of $353$-point sets in $[3]^6$ (elements of the set being indicated by white squares). This example was generated by a genetic algorithm.} \label{moser353-fig} \end{figure}

Unfortunately, we have been unable to locate a lower bound which is asymptotically better than \eqref{cpn3}. Indeed, any method based purely on the $A_B$ construction cannot do asymptotically better than the previous constructions:

\begin{proposition} Let $B \subset \Delta_n$ be such that $A_B$ is a Moser set. Then $|A_B| \leq (2 \sqrt{\frac{9}{4\pi}} + o(1)) \frac{3^n}{\sqrt{n}}$. \end{proposition}

\begin{proof} By the previous discussion, $B$ cannot contain any pair of the form $(a,b+2r,c), (a+r,b,c+r)$ with $r>0$. In other words, for any $-n \leq h \leq n$, $B$ can contain at most one triple $(a,b,c)$ with $c-a=h$. From this and \eqref{cn3}, we see that $$ |A_B| \leq \sum_{h=-n}^n \max_{(a,b,c) \in \Delta_n: c-a=h} \frac{n!}{a! b! c!}.$$ From the Chernoff inequality (or the Stirling formula computation below) we see that $\frac{n!}{a! b! c!} \leq \frac{1}{n^{10}} 3^n$ unless $a,b,c = n/3 + O( n^{1/2} \log^{1/2} n )$, so we may restrict to this regime, which also forces $h = O( n^{1/2}\log^{1/2} n)$. If we write $a = n/3 + \alpha$, $b = n/3 + \beta$, $c = n/3+\gamma$ and apply Stirling's formula $n! = (1+o(1)) \sqrt{2\pi n} n^n e^{-n}$, we obtain $$ \frac{n!}{a! b! c!} = (1+o(1)) \frac{3^{3/2}}{2\pi n} 3^n \exp( - (\frac{n}{3}+\alpha) \log (1 + \frac{3\alpha}{n} ) - (\frac{n}{3}+\beta) \log (1 + \frac{3\beta}{n} ) - (\frac{n}{3}+\gamma) \log (1 + \frac{3\gamma}{n} ) ).$$ From Taylor expansion one has $$ -(\frac{n}{3}+\alpha) \log (1 + \frac{3\alpha}{n} ) = -\alpha - \frac{3}{2} \frac{\alpha^2}{n} + o(1)$$ and similarly for $\beta,\gamma$; since $\alpha+\beta+\gamma=0$, we conclude that $$ \frac{n!}{a! b! c!} = (1+o(1)) \frac{3^{3/2}}{2\pi n} 3^n \exp( - \frac{3}{2n} (\alpha^2+\beta^2+\gamma^2) ).$$ If $c-a=h$, then $\alpha^2+\beta^2+\gamma^2 = \frac{3\beta^2}{2} + \frac{h^2}{2}$. Thus we see that $$ \max_{(a,b,c) \in \Delta_n: c-a=h} \frac{n!}{a! b! c!} \leq (1+o(1)) \frac{3^{3/2}}{2\pi n} 3^n \exp( - \frac{3}{4n} h^2 ).$$ Using the integral test, we thus have $$ |A_B| \leq (1+o(1)) \frac{3^{3/2}}{2\pi n} 3^n \int_\R \exp( - \frac{3}{4n} x^2 )\ dx.$$ Since $\int_\R \exp( - \frac{3}{4n} x^2 )\ dx = \sqrt{\frac{4\pi n}{3}}$, we obtain the claim. \end{proof}

Actually it is possible to improve upon these bounds by a slight amount. Observe that if $B$ is a maximiser for the right-hand side of \eqref{cn3} (subject to $B$ not containing isosceles triangles), then any triple $(a,b,c)$ not in $B$ must be the vertex of a (possibly degenerate) isosceles triangle with the other vertices in $B$. If this triangle is non-degenerate, or if $(a,b,c)$ is the upper vertex of a degenerate isosceles triangle, then no point from $\Gamma_{a,b,c}$ can be added to $A_B$ without creating a geometric line. However, if $(a,b,c) = (a'+r,b',c'+r)$ is only the lower vertex of a degenerate isosceles triangle $(a'+r,b',c'+r), (a',b'+2r,c')$, then one can add any subset of $\Gamma_{a,b,c}$ to $A_B$ and still have a Moser set as long as no pair of elements in that subset is separated by Hamming distance $2r$. For instance, in the $n=5$ case, we can start with the 122-point set built from $$B = \{ (0 0 5),(0 2 3),(1 1 3 ),(1 2 2 ),(2 2 1 ),(3 1 1 ),(3 2 0 ),(5 0 0))\}$$, and add a point each from (1 0 4) and (4 0 1). This gives an example of the maximal, 124-point solution. Again, in the $n=10$ case, the set \begin{align*} B &= \{(0 0 10),(0 2 8 ),(0 3 7 ),(0 4 6 ),(1 4 5 ),(2 1 7 ),(2 3 5 ), (3 2 5 ),(3 3 4 ),(3 4 3 ),(4 4 2 ),(5 1 4 ), \\ &\quad (5 3 2 ),(6 2 2 ), (6 3 1 ),(6 4 0 ),(8 1 1 ),(9 0 1 ),(9 1 0 ) \} \end{align*}

generates the lower bound $c'_{10,3} \geq 24786$ given above (and, up to reflection $a \leftrightarrow c$, is the only such set that does so); but by adding the following twelve elements from $\Gamma_{5,0,5}$ one can increase the lower bound slightly to $24798$: $1111133333$, $1111313333$, $1113113333$, $1133331113$, $1133331131$, $1133331311$, $3311333111$, $3313133111$, $3313313111$, $3331111133$, $3331111313$, $3331111331$

A more general form goes with the $B$ set described at the start of this section. Include points from $\Gamma_{(a,n-i-4,i+4-a)}$ when $a=1 (\operatorname{mod}\ 3)$, subject to no two points being included if they differ by the interchange of a $1$ and a $3$. Each of these Gamma sets is the feet of a degenerate isosceles triangle with vertex $\Gamma_{(a-1,n-i-2,a+3-a)}$.

\begin{lemma} If $A$ is a subset of $\Gamma_{(a,b,c)}$ such that no two points of $A$ differ by the interchange of a $1$ and a $3$, then $|A| \leq |\Gamma_{a,b,c}|/(1+\max(a,c))$. \end{lemma} \begin{proof} Say that two points of $\Gamma_{a,b,c}$ are neighbours if they differ by the exchange of a $1$ and a $3$. Each point of $A$ has $ac$ neighbours, none of which are in $A$. Each point of $\Gamma_{(a,b,c)}\backslash A$ has $ac$ neighbours, but only $min(a,c)$ of them may be in $A$. So for each point of $A$ there are on average $ac/\min(a,c) = \max(a,c)$ points not in $A$. So the proportion of points of $\Gamma_{(a,b,c)}$ that are in $A$ is at most one in $1+\max(a,c)$. \end{proof}

The proportion of extra points for each of the cells $\Gamma_{(a,n-i-4,i+4-a)}$ is no more than $2/(i+6)$. Only one cell in three is included from the $b=n-i-4$ layer, so we expect no more than $\binom{n}{i+4}2^{i+5}/(3i+18)$ new points, all from $S_{n,i+4}$. One can also find extra points from $S_{n,i+5}$ and higher spheres.

Earlier solutions may also give insight into the problem. In this section we discuss lower bounds for $c'_{n,3}$. Clearly we have $c'_{0,3}=1$ and $c'_{1,3}=2$, so we focus on the case $n \ge 2$. The first lower bounds may be due to Koml\'{o}s \cite{komlos}, who observed that the sphere $S_{i,n}$ of elements with exactly $n-i$ 2 entries (see Section \ref{notation-sec} for definition), is a Moser set, so that \begin{equation}\label{cin} c'_{n,3}\geq \vert S_{i,n}\vert \end{equation} holds for all $i$. Choosing $i=\lfloor \frac{2n}{3}\rfloor$ and applying Stirling's formula, we see that this lower bound takes the form \begin{equation}\label{cpn3} c'_{n,3} \geq (C-o(1)) 3^n / \sqrt{n} \end{equation} for some absolute constant $C>0$; in fact \eqref{cin} gives \eqref{cpn3} with $C := \sqrt{\frac{9}{4\pi}}$. In particular $c'_{3,3} \geq 12, c'_{4,3}\geq 24, c'_{5,3}\geq 80, c'_{6,3}\geq 240$.

These values can be improved by studying combinations of several spheres or semispheres or applying elementary results from coding theory.

Observe that if $\{w(1),w(2),w(3)\}$ is a geometric line in $[3]^n$, then $w(1), w(3)$ both lie in the same sphere $S_{i,n}$, and that $w(2)$ lies in a lower sphere $S_{i-r,n}$ for some $1 \leq r \leq i \leq n$. Furthermore, $w(1)$ and $w(3)$ are separated by Hamming distance $r$.

As a consequence, we see that $S_{i-1,n} \cup S_{i,n}^e$ (or $S_{i-1,n} \cup S_{i,n}^o$) is a Moser set for any $1 \leq i \leq n$, since any two distinct elements $S_{i,n}^e$ are separated by a Hamming distance of at least two. (Recall Section \ref{notation-sec} for definitions), This leads to the lower bound \begin{equation}\label{cn3-low} c'_{n,3} \geq \binom{n}{i-1} 2^{i-1} + \binom{n}{i} 2^{i-1} = \binom{n+1}{i} 2^{i-1}. \end{equation} It is not hard to see that $\binom{n+1}{i+1} 2^{i} > \binom{n+1}{i} 2^{i-1}$ if and only if $3i < 2n+1$, and so this lower bound is maximised when $i = \lfloor \frac{2n+1}{3} \rfloor$ for $n \geq 2$, giving the formula \eqref{binom}. This leads to the lower bounds $$ c'_{2,3} \geq 6; c'_{3,3} \geq 16; c'_{4,3} \geq 40; c'_{5,3} \geq 120; c'_{6,3} \geq 336$$ which gives the right lower bounds for $n=2,3$, but is slightly off for $n=4,5$. Asymptotically, Stirling's formula and \eqref{cn3-low} then give the lower bound \eqref{cpn3} with $C = \frac{3}{2} \times \sqrt{\frac{9}{4\pi}}$, which is asymptotically $50\%$ better than the bound \eqref{cin}.

The work of Chv\'{a}tal \cite{chvatal1} already contained a refinement of this idea which we here translate into the usual notation of coding theory: Let $A(n,d)$ denote the size of the largest binary code of length $n$ and minimal distance $d$.

Then \begin{equation}\label{cnchvatal} c'_{n,3}\geq \max_k \left( \sum_{j=0}^k \binom{n}{j} A(n-j, k-j+1)\right). \end{equation}

The following values of $A(n,d)$ for small $n,d$ are known, see \cite{Brower}: {\tiny{ \[ \begin{array}{llllllll} A(1,1)=2&&&&&&&\\ A(2,1)=4& A(2,2)=2&&&&&&\\ A(3,1)=8&A(3,2)=4&A(3,3)=2&&&&&\\ A(4,1)=16&A(4,2)=8& A(4,3)=2& A(4,4)=2&&&&\\ A(5,1)=32&A(5,2)=16& A(5,3)=4& A(5,4)=2&A(5,5)=2&&&\\ A(6,1)=64&A(6,2)=32& A(6,3)=8& A(6,4)=4&A(6,5)=2&A(6,6)=2&&\\ A(7,1)=128&A(7,2)=64& A(7,3)=16& A(7,4)=8&A(7,5)=2&A(7,6)=2&A(7,7)=2&\\ A(8,1)=256&A(8,2)=128& A(8,3)=20& A(8,4)=16&A(8,5)=4&A(8,6)=2 &A(8,7)=2&A(8,8)=2\\ A(9,1)=512&A(9,2)=256& A(9,3)=40& A(9,4)=20&A(9,5)=6&A(9,6)=4 &A(9,7)=2&A(9,8)=2\\ A(10,1)=1024&A(10,2)=512& A(10,3)=72& A(10,4)=40&A(10,5)=12&A(10,6)=6 &A(10,7)=2&A(10,8)=2\\ A(11,1)=2048&A(11,2)=1024& A(11,3)=144& A(11,4)=72&A(11,5)=24&A(11,6)=12 &A(11,7)=2&A(11,8)=2\\ A(12,1)=4096&A(12,2)=2048& A(12,3)=256& A(12,4)=144&A(12,5)=32&A(12,6)=24 &A(12,7)=4&A(12,8)=2\\ A(13,1)=8192&A(13,2)=4096& A(13,3)=512& A(13,4)=256&A(13,5)=64&A(12,6)=32 &A(13,7)=8&A(13,8)=4\\ \end{array} \] }} In addition, one has the general identities $A(n,1)=2^n, A(n,2)=2^{n-1}, A(n-1,2e-1)=A(n,2e)$, and $A(n,d)=2$, if $d>\frac{2n}{3}$.

Inserting this data into \eqref{cnchvatal} for $k=2$ we obtain the lower bounds \[ \begin{array}{llll} c'_{4,3}&\geq &\binom{4}{0}A(4,3)+\binom{4}{1}A(3,2)+\binom{4}{2}A(2,1) =1\cdot 2+4 \cdot 4+6\cdot 4&=42\\ c'_{5,3}&\geq &\binom{5}{0}A(5,3)+\binom{5}{1}A(4,2)+\binom{5}{2}A(3,1) =1\cdot 4+5 \cdot 8+10\cdot 8&=124\\ c'_{6,3}&\geq &\binom{6}{0}A(6,3)+\binom{6}{1}A(5,2)+\binom{6}{2}A(4,1) =1\cdot 8+6 \cdot 16+15\cdot 16&=344. \end{array} \] Similarly, with $k=3$ we obtain \[ \begin{array}{llll} c'_{7,3}&\geq& \binom{7}{0}A(7,4)+\binom{7}{1}A(6,3)+\binom{7}{2}A(5,2) + \binom{7}{3}A(4,1)&=960.\\ c'_{8,3}&\geq &\binom{8}{0}A(8,4)+\binom{8}{1}A(7,3)+\binom{8}{2}A(6,2) + \binom{8}{3}A(5,1)&=2832\\ c'_{9,3}&\geq & \binom{9}{0}A(9,4)+\binom{9}{1}A(8,3)+\binom{9}{2}A(7,2) + \binom{9}{3}A(6,1)&=7880 \end{array}\] and for $k=4$ we have \[ \begin{array}{llll} c'_{10,3}&\geq &\binom{10}{0}A(10,5)+\binom{10}{1}A(9,4)+\binom{10}{2}A(8,3) + \binom{10}{3}A(7,2)+\binom{10}{4}A(6,1)&=22232\\ c'_{11,3}&\geq &\binom{11}{0}A(11,5)+\binom{11}{1}A(10,4)+\binom{11}{2}A(9,3) + \binom{11}{3}A(8,2)+\binom{11}{4}A(7,1)&=66024\\ c'_{12,3}&\geq &\binom{12}{0}A(12,5)+\binom{12}{1}A(11,4)+\binom{12}{2}A(10,3) + \binom{12}{3}A(9,2)+\binom{12}{4}A(8,1)&=188688.\\ \end{array}\] and for $k=5$ we have \[ c'_{13,3}\geq 539168.\]

It should be pointed out that these bounds are even numbers, so that $c'_{4,3}=43$ shows that one cannot generally expect this lower bound gives the optimum.

The maximum value appears to occur for $k=\lfloor\frac{n+2}{3}\rfloor$, so that using Stirling's formula and explicit bounds on $A(n,d)$ the best possible value known to date of the constant $C$ in equation \eqref{cpn3} can be worked out, but we refrain from doing this here. Using the singleton bound $A(n,d)\leq 2^{n-d+1}$ Chv\'{a}tal \cite{chvatal1} proved that the expression on the right hand side of \eqref{cnchvatal} is also $O\left( \frac{3^n}{\sqrt{n}}\right)$, so that the refinement described above gains a constant factor over the initial construction only.

For $n=4$ the above does not yet give the exact value. The value $c'_{4,3}=43$ was first proven by Chandra \cite{chandra}. A uniform way of describing examples for the optimum values of $c'_{4,3}=43$ and $c'_{5,3}=124$ is as follows.

Let us consider the sets $$ A := S_{i-1,n} \cup S_{i,n}^e \cup A'$$ where $A' \subset S_{i+1,n}$ has the property that any two elements in $A'$ are separated by a Hamming distance of at least three, or have a Hamming distance of exactly one but their midpoint lies in $S_{i,n}^o$. By the previous discussion we see that this is a Moser set, and we have the lower bound \begin{equation}\label{cnn} c'_{n,3} \geq \binom{n+1}{i} 2^{i-1} + |A'|. \end{equation} This gives some improved lower bounds for $c'_{n,3}$:

\begin{itemize} \item By taking $n=4$, $i=3$, and $A' = \{ 1111, 3331, 3333\}$, we obtain $c'_{4,3} \geq 43$; \item By taking $n=5$, $i=4$, and $A' = \{ 11111, 11333, 33311, 33331 \}$, we obtain $c'_{5,3} \geq 124$. \item By taking $n=6$, $i=5$, and $A' = \{ 111111, 111113, 111331, 111333, 331111, 331113\}$, we obtain $c'_{6,3} \geq 342$. \end{itemize}

This gives the lower bounds in Theorem \ref{moser} up to $n=5$, but the bound for $n=6$ is inferior to the lower bound $c'_{6,3}\geq 344$ given above.


\subsection{Higher $k$ values}

We now consider lower bounds for $c'_{n,k}$ for some values of $k$ larger than $3$. Here we will see some further connections between the Moser problem and the density Hales-Jewett problem.

For $k=4$, we have the lower bounds $c'_{n,4} \ge \binom{n}{n/2}2^n$. To see this, observe that the set of points with $a$ $1$s,$b$ $2$s,$c$ $3$s and $d$ $4$s, where $a+d$ has the constant value $n/2$, does not form geometric lines because points at the ends of a geometric line have more $a$ or $d$ values than points in the middle of the line.

The following lower bound is asymptotically twice as large. Take all points with $a$ $1$s, $b$ $2$s, $c$ $3$s and $d$ $4$s, for which:

\begin{itemize} \item Either $a+d = q$ or $q-1$, $a$ and $b$ have the same parity; or \item $a+d = q-2$ or $q-3$, $a$ and $b$ have opposite parity. \end{itemize}

This includes half the points of four adjacent layers, and therefore may include $(1+o(1))\binom{n}{n/2}2^{n+1}$ points.

We also have a lower bound for $c'_{n,5}$ similar to Theorem \ref{dhj-lower}, namely $c'_{n,5} = 5^{n-O(\sqrt{\log n})}$. Consider points with $a$ $1$s, $b$ $2$s, $c$ $3$s, $d$ $4$s and $e$ $5$s. For each point, take the value $a+e+2(b+d)+3c$. The first three points in any geometric line give values that form an arithmetic progression of length three.

Select a set of integers with no arithmetic progression of length $3$. Select all points whose value belongs to that sequence; there will be no geometric line among those points. By the Behrend construction\cite{behrend}, it is possible to choose these points with density $\exp{-O(\sqrt{\log n})}$.

For $k=6$, we observe that the asymptotic $c'_{n,6} = o(6^n)$ would imply the $k=3$ density Hales-Jewett theorem $c_{n,3}=o(3^n)$. Indeed, any $k=3$ combinatorial line-free set can be ``doubled up into a $k=6$ geometric line-free set of the same density by pulling back the set from the map that maps $1, 2, 3, 4, 5, 6$ to $1, 2, 3, 3, 2, 1$ respectively; note that this map sends $k=6$ geometric lines to $k=3$ combinatorial lines. So $c'_{n,6} \geq 2^n c_{n,3}$, and more generally, $c'_{n,2k} \geq 2^n c_{n,k}$.