Difference between revisions of "Moser-lower.tex"

From Polymath1Wiki
Jump to: navigation, search
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}$. Clearly we have $c'_{0,3}=1$ and $c'_{1,3}=2$, so we focus on the case $n \ge 2$.
+
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}$ (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}$,  
 +
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
+
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}. This leads to the lower bounds
+
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$. {\bf where was this bound first observed?}
+
(Recall Section \ref{notation-sec} for definitions),
Applying Stirling's formula, we see that this lower bound takes the form
+
This leads to the lower bound $$ c'_{n,3} \geq \binom{n}{i-1}  
\begin{equation}\label{cpn3}
+
2^{i-1} + \binom{n}{i} 2^{i-1} = \binom{n+1}{i} 2^{i-1}.$$ It is not  
c'_{n,3} \geq C 3^n / \sqrt{n}  
+
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}
for some absolute constant $C>0$.
 
  
One can do slightly better by considering the sets
+
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$. By the previous discussion we see that this is a Moser set, and we have the lower bound
+
\[
 +
\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'|.
+
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}
  
\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}.
+
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}.