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

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}$. | + | 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 | ||

+ | $c'_{n,3}\geq \vert S_{i,n}\vert$ | ||

+ | 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 3^n / \sqrt{n} | ||

+ | \end{equation} for some absolute constant $C>0$. | ||

+ | In particular $c'_{3,3} \geq 12, c'_{4,3}\geq 24, c'_{5,3}\geq 80, | ||

+ | 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 | ||

+ | 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}$ | + | 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. | + | As a consequence, we see that $S_{i-1,n} \cup S_{i,n}^e$ (or $S_{i-1,n} |

− | $$ c'_{n,3} \geq \binom{n}{i-1} 2^{i-1} + \binom{n}{i} 2^{i-1} = \binom{n+1}{i} 2^{i-1}.$$ | + | \cup S_{i,n}^o$) is a Moser set for any $1 \leq i \leq n$, since any two |

− | 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}. | + | distinct elements $S_{i,n}^e$ are separated by a Hamming distance of at |

− | $$ 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$$ | + | least two. |

− | which gives the right lower bounds for $n=2,3$, but is slightly off for $n=4,5$. | + | (Recall Section \ref{notation-sec} for definitions), |

− | + | This leads to the lower bound $$ c'_{n,3} \geq \binom{n}{i-1} | |

− | \begin{equation}\label{ | + | 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$. | ||

+ | |||

+ | Chv\'{a}tal \cite{chvatal1} observed that one can iterate this. | ||

+ | Let us translate his work 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} | \end{equation} | ||

− | |||

− | + | With the following values for $A(n,d)$: | |

− | $$ A := S_{i-1,n} \cup S_{i,n}^e \cup A'$$ | + | {\tiny{ |

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

+ | \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\\ | ||

+ | \end{array} | ||

+ | \] | ||

+ | }} | ||

+ | |||

+ | 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}$. | ||

+ | 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: | ||

+ | with $k=2$ | ||

+ | \[ | ||

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

+ | \] | ||

+ | With k=3 | ||

+ | \[ | ||

+ | \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,3)&=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,3)&=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,3)&=7880. | ||

+ | \end{array}\] | ||

+ | With k=4 | ||

+ | $$c'_{10,3}\geq \binom{10}{0}A(9,5)+\binom{10}{1}A(9,4)+\binom{10}{2}A(8,3) | ||

+ | + \binom{10}{3}A(7,4)+\binom{10}{4}A(6,5)=22232.$$ | ||

+ | |||

+ | 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 proved | ||

+ | \cite{chvatal1}) that the expression in \eqref{cnchvatal} is also | ||

+ | $O\left( \frac{3^n}{\sqrt{n}}\right)$. | ||

+ | |||

+ | |||

+ | 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 the following: | ||

+ | |||

+ | 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} | \begin{equation}\label{cnn} | ||

− | + | c'_{n,3} \geq \binom{n+1}{i} 2^{i-1} + |A'|. | |

− | \end{equation} | + | \end{equation} This gives some improved lower bounds for $c'_{n,3}$: |

− | 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 | + | 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. The lower bound $c'_{6,3} \geq | ||

+ | 353$ was located by a genetic algorithm, see Appendix | ||

+ | \ref{genetic-alg}. This suggests that greedily filling in spheres, | ||

+ | semispheres or codes is no | ||

+ | longer the optimal strategy in dimensions six and higher. | ||

+ | The current record | ||

+ | In any event, | ||

+ | bounds such as \eqref{cnchvatal} or | ||

+ | \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 06:27, 5 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$. 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 $c'_{n,3}\geq \vert S_{i,n}\vert$

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 3^n / \sqrt{n} \end{equation} for some absolute constant $C>0$. In particular $c'_{3,3} \geq 12, c'_{4,3}\geq 24, c'_{5,3}\geq 80, 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

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 $$ 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$.

Chv\'{a}tal \cite{chvatal1} observed that one can iterate this. Let us translate his work 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}

With the following values for $A(n,d)$: {\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\\ \end{array} \] }}

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}$. 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:
with $k=2$
\[
\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}
\]
With k=3
\[
\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,3)&=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,3)&=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,3)&=7880.
\end{array}\]
With k=4
$$c'_{10,3}\geq \binom{10}{0}A(9,5)+\binom{10}{1}A(9,4)+\binom{10}{2}A(8,3)
+ \binom{10}{3}A(7,4)+\binom{10}{4}A(6,5)=22232.$$

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 proved \cite{chvatal1}) that the expression in \eqref{cnchvatal} is also $O\left( \frac{3^n}{\sqrt{n}}\right)$.

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 the following:

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. The lower bound $c'_{6,3} \geq

353$ was located by a genetic algorithm, see Appendix \ref{genetic-alg}. This suggests that greedily filling in spheres, semispheres or codes is no longer the optimal strategy in dimensions six and higher. The current record In any event, bounds such as \eqref{cnchvatal} or \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}.