# Difference between revisions of "Moser-lower.tex"

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}^ | + | 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}^ | + | $$ 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}^ | + | 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}$: | This gives some improved lower bounds for $c'_{n,3}$: | ||

\begin{itemize} | \begin{itemize} | ||

− | \item By taking $n=4$, $i=3$, and $A' = \{ 1111, | + | \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' = \{ | + | \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$ | + | 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}. |

− | + | ||

− | + |

## Revision as of 15: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}.