Moser-lower.tex
\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 $c'_{0,3}=1$ and $c'_{1,3}=2$, so we focus on the case $n \ge 2$.
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}$ (which was defined in Section \ref{notation-sec}), 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}^o$ (or $S_{i-1,n} \cup S_{i,n}^e$) is a Moser set for any $1 \leq i \leq n$, since any two distinct elements $S_{i,n}^o$ are separated by a Hamming distance of at least two. This leads to the lower bound $$ c'_{n,3} \geq \binom{n}{i-1} 2^{i-1} + \binom{n}{i} 2^{i-1} = \binom{n+1}{i} 2^{i-1}.$$ 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$$ which gives the right lower bounds for $n=2,3$, but is slightly off for $n=4,5$. {\bf where was this bound first observed?} Applying Stirling's formula, we see that this lower bound takes the form \begin{equation}\label{cpn3}
c'_{n,3} \geq C 3^n / \sqrt{n}
\end{equation} for some absolute constant $C>0$.
One can do slightly better by considering the sets $$ A := S_{i-1,n} \cup S_{i,n}^o \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}^e$. By the previous discussion we see that this is a Moser set, and we have the lower bound $$ c'_{n,3} \geq \binom{n+1}{i} 2^{i-1} + |A'|.$$ This gives some improved lower bounds for $c'_{n,3}$:
\begin{itemize} \item By taking $n=4$, $i=3$, and $A' = \{ 1111, 1333, 3333\}$, we obtain $c'_{4,3} \geq 43$; \item By taking $n=5$, $i=4$, and $A' = \{ 13111, 13113, 31311, 13333 \}$, we obtain $c'_{5,3} \geq 124$. \end{itemize}
This gives the lower bounds in Theorem \ref{moser} up to $n=5$. One could continue this sort of procedure for higher $n$, but the improvements over \eqref{binom} are rather minor, and in particular we have been unable to locate a bound which is asymptotically better than \eqref{cpn3}.
The lower bound $c'_{6,3} \geq 353$ was located by a genetic algorithm; see Appendix \ref{genetic-alg}.
