Difference between revisions of "Moser-lower.tex"

From Polymath1Wiki
Jump to: navigation, search
Line 5: Line 5:
 
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$.
 
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
+
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.  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}.$$
 
$$ 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
 
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'_{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$.  {\bf where was this bound first observed?}
 
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
 
Applying Stirling's formula, we see that this lower bound takes the form
Line 17: Line 17:
  
 
One can do slightly better by considering the sets
 
One can do slightly better by considering the sets
$$ A := S_{i-1,n} \cup S_{i,n}^o \cup A'$$
+
$$ 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}^e$.  By the previous discussion we see that this is a Moser set, and we have the lower bound
+
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
$$ c'_{n,3} \geq \binom{n+1}{i} 2^{i-1} + |A'|.$$
+
\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}$:
 
This gives some improved lower bounds for $c'_{n,3}$:
  
 
\begin{itemize}
 
\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=4$, $i=3$, and $A' = \{ 1111, 3331, 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$.
+
\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}
 
\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}.
+
This gives the lower bounds in Theorem \ref{moser} up to $n=5$, but gives an inferior lower bound for $n=6$; the lower bound $c'_{6,3} \geq 353$ was located instead by a genetic algorithm, see Appendix \ref{genetic-alg}.  This suggests that greedily filling in spheres is no longer the optimal strategy in dimensions six and higher.  In any event, bounds such as \eqref{cnn} only seem to offer a minor improvement over \eqref{binom} at best, 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}.
+

Revision as of 08:05, 3 June 2009

\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}^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. 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; c'_{6,3} \geq 336$$ 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}^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 gives an inferior lower bound for $n=6$; the lower bound $c'_{6,3} \geq 353$ was located instead by a genetic algorithm, see Appendix \ref{genetic-alg}. This suggests that greedily filling in spheres is no longer the optimal strategy in dimensions six and higher. In any event, bounds such as \eqref{cnn} only seem to offer a minor improvement over \eqref{binom} at best, and in particular we have been unable to locate a bound which is asymptotically better than \eqref{cpn3}.