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

(New page: This is where we will discuss lower bounds on Moser sets in $k=3$. Please edit at http://michaelnielsen.org/polymath1/index.php?title=moser-lower.tex) |
|||

Line 1: | Line 1: | ||

− | + | \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}. |

## Revision as of 17:41, 31 May 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}^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}.