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

(In this and my change two days ago I reformulated Chvatal's construction into modern notation, thus improving the eralier bound, leading to values that improve the current spreadsheet.) |
|||

(27 intermediate revisions by 3 users not shown) | |||

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 | + | Just as for the density Hales-Jewett problem, we found that Gamma sets $\Gamma_{a,b,c}$ were useful in providing large lower bounds for the Moser problem. This is despite the fact that the symmetries of the cube do not respect Gamma sets. |

+ | |||

+ | Observe that if $B \subset \Delta_n$, then the set $A_B := \bigcup_{\vec a \in B} \Gamma_{a,b,c}$ is a Moser set as long as $B$ does not contain any ``isosceles triangles'' $(a+r,b,c+s), (a+s,b,c+r), (a,b+r+s,c)$ for any $r,s \geq 0$ not both zero; in particular, $B$ cannot contain any ``vertical line segments'' $(a+r,b,c+r), (a,b+2r,c)$. An example of such a set is provided by selecting $0 \leq i \leq n-3$ and letting $B$ consist of the triples $(a, n-i, i-a)$ when $a \neq 3 \mod 3$, $(a,n-i-1,i+1-a)$ when $a \neq 1 \mod 3$, $(a,n-i-2,i+2-a)$ when $a=0 \mod 3$, and $(a,n-i-3,i+3-a)$ when $a=2 \mod 3$. Asymptotically, this set includes about two thirds of the spheres $S_{n,i}$, $S_{n,i+1}$ and one third of the spheres $S_{n,i+2}, S_{n,i+3}$ and (setting $i$ close to $n/3$) gives a lower bound \eqref{cpn3} with $C = 2 \times \sqrt{\frac{9}{4\pi}}$. | ||

+ | |||

+ | An integer program was run to obtain the optimal lower bounds achievable by the $A_B$ construction (using \eqref{cn3}, of course). The results for $1 \leq n \leq 20$ are displayed in Figure \ref{nlow-moser}. More complete data, including the list of optimisers, can be found at | ||

+ | |||

+ | \centerline{{\tt http://abel.math.umu.se/$\sim$klasm/Data/HJ/}.} | ||

+ | |||

+ | |||

+ | \begin{figure}[tb] | ||

+ | \centerline{ | ||

+ | \begin{tabular}{|ll|ll|} | ||

+ | \hline | ||

+ | $n$ & lower bound & $n$ & lower bound \\ | ||

+ | \hline | ||

+ | 1 & 2 &11& 71766\\ | ||

+ | 2 & 6 & 12& 212423\\ | ||

+ | 3 & 16 & 13& 614875\\ | ||

+ | 4 & 43 & 14& 1794212\\ | ||

+ | 5 & 122& 15& 5321796\\ | ||

+ | 6 & 353& 16& 15455256\\ | ||

+ | 7 & 1017& 17& 45345052\\ | ||

+ | 8 & 2902&18& 134438520\\ | ||

+ | 9 & 8622&19& 391796798\\ | ||

+ | 10& 24786& 20& 1153402148\\ | ||

+ | \hline | ||

+ | \end{tabular}} | ||

+ | \caption{Lower bounds for $c'_{n,3}$ obtained by the $A_B$ construction.} | ||

+ | \label{nlow-moser} | ||

+ | \end{figure} | ||

+ | |||

+ | |||

+ | \begin{figure}[tb] | ||

+ | \centerline{\includegraphics{moser353new.png}} | ||

+ | \caption{One of the examples of $353$-point sets in $[3]^6$ (elements of the set being indicated by white squares). This example was generated by a genetic algorithm.} | ||

+ | \label{moser353-fig} | ||

+ | \end{figure} | ||

+ | |||

+ | Unfortunately, we have been unable to locate a lower bound which is asymptotically better than \eqref{cpn3}. Indeed, any method based purely on the $A_B$ construction cannot do asymptotically better than the previous constructions: | ||

+ | |||

+ | \begin{proposition} Let $B \subset \Delta_n$ be such that $A_B$ is a Moser set. Then $|A_B| \leq (2 \sqrt{\frac{9}{4\pi}} + o(1)) \frac{3^n}{\sqrt{n}}$. | ||

+ | \end{proposition} | ||

+ | |||

+ | \begin{proof} By the previous discussion, $B$ cannot contain any pair of the form $(a,b+2r,c), (a+r,b,c+r)$ with $r>0$. In other words, for any $-n \leq h \leq n$, $B$ can contain at most one triple $(a,b,c)$ with $c-a=h$. From this and \eqref{cn3}, we see that | ||

+ | $$ |A_B| \leq \sum_{h=-n}^n \max_{(a,b,c) \in \Delta_n: c-a=h} \frac{n!}{a! b! c!}.$$ | ||

+ | From the Chernoff inequality (or the Stirling formula computation below) we see that $\frac{n!}{a! b! c!} \leq \frac{1}{n^{10}} 3^n$ unless $a,b,c = n/3 + O( n^{1/2} \log^{1/2} n )$, so we may restrict to this regime, which also forces $h = O( n^{1/2}\log^{1/2} n)$. If we write $a = n/3 + \alpha$, $b = n/3 + \beta$, $c = n/3+\gamma$ and apply Stirling's formula $n! = (1+o(1)) \sqrt{2\pi n} n^n e^{-n}$, we obtain | ||

+ | $$ \frac{n!}{a! b! c!} = (1+o(1)) \frac{3^{3/2}}{2\pi n} 3^n \exp( - (\frac{n}{3}+\alpha) \log (1 + \frac{3\alpha}{n} ) - (\frac{n}{3}+\beta) \log (1 + \frac{3\beta}{n} ) - (\frac{n}{3}+\gamma) \log (1 + \frac{3\gamma}{n} ) ).$$ | ||

+ | From Taylor expansion one has | ||

+ | $$ -(\frac{n}{3}+\alpha) \log (1 + \frac{3\alpha}{n} ) = -\alpha - \frac{3}{2} \frac{\alpha^2}{n} + o(1)$$ | ||

+ | and similarly for $\beta,\gamma$; since $\alpha+\beta+\gamma=0$, we conclude that | ||

+ | $$ \frac{n!}{a! b! c!} = (1+o(1)) \frac{3^{3/2}}{2\pi n} 3^n \exp( - \frac{3}{2n} (\alpha^2+\beta^2+\gamma^2) ).$$ | ||

+ | If $c-a=h$, then $\alpha^2+\beta^2+\gamma^2 = \frac{3\beta^2}{2} + \frac{h^2}{2}$. Thus we see that | ||

+ | $$ \max_{(a,b,c) \in \Delta_n: c-a=h} \frac{n!}{a! b! c!} \leq (1+o(1)) \frac{3^{3/2}}{2\pi n} 3^n \exp( - \frac{3}{4n} h^2 ).$$ | ||

+ | Using the integral test, we thus have | ||

+ | $$ |A_B| \leq (1+o(1)) \frac{3^{3/2}}{2\pi n} 3^n \int_\R \exp( - \frac{3}{4n} x^2 )\ dx.$$ | ||

+ | Since $\int_\R \exp( - \frac{3}{4n} x^2 )\ dx = \sqrt{\frac{4\pi n}{3}}$, we obtain the claim. | ||

+ | \end{proof} | ||

+ | |||

+ | Actually it is possible to improve upon these bounds by a slight amount. Observe that if $B$ is a maximiser for the right-hand side of \eqref{cn3} (subject to $B$ not containing isosceles triangles), then any triple $(a,b,c)$ not in $B$ must be the vertex of a (possibly degenerate) isosceles triangle with the other vertices in $B$. If this triangle is non-degenerate, or if $(a,b,c)$ is the upper vertex of a degenerate isosceles triangle, then no point from $\Gamma_{a,b,c}$ can be added to $A_B$ without creating a geometric line. However, if $(a,b,c) = (a'+r,b',c'+r)$ is only the lower vertex of a degenerate isosceles triangle $(a'+r,b',c'+r), (a',b'+2r,c')$, then one can add any subset of $\Gamma_{a,b,c}$ to $A_B$ and still have a Moser set as long as no pair of elements in that subset is separated by Hamming distance $2r$. For instance, in the $n=5$ case, we can start with the 122-point set built from | ||

+ | $$B = \{ (0 0 5),(0 2 3),(1 1 3 ),(1 2 2 ),(2 2 1 ),(3 1 1 ),(3 2 0 ),(5 0 0))\}$$, and add a point each from (1 0 4) and (4 0 1). | ||

+ | This gives an example of the maximal, 124-point solution. Again, in the $n=10$ case, the set | ||

+ | \begin{align*} | ||

+ | B &= \{(0 0 10),(0 2 8 ),(0 3 7 ),(0 4 6 ),(1 4 5 ),(2 1 7 ),(2 3 5 ), | ||

+ | (3 2 5 ),(3 3 4 ),(3 4 3 ),(4 4 2 ),(5 1 4 ), \\ | ||

+ | &\quad (5 3 2 ),(6 2 2 ), | ||

+ | (6 3 1 ),(6 4 0 ),(8 1 1 ),(9 0 1 ),(9 1 0 ) \} | ||

+ | \end{align*} | ||

+ | |||

+ | generates the lower bound $c'_{10,3} \geq 24786$ given above (and, up to reflection $a \leftrightarrow c$, is the only such set that does so); but by adding the following twelve elements from $\Gamma_{5,0,5}$ one can increase the lower bound slightly to $24798$: $1111133333$, $1111313333$, | ||

+ | $1113113333$, $1133331113$, $1133331131$, $1133331311$, $3311333111$, | ||

+ | $3313133111$, $3313313111$, $3331111133$, $3331111313$, $3331111331$ | ||

+ | |||

+ | A more general form goes with the $B$ set described at the start of this section. Include points from $\Gamma_{(a,n-i-4,i+4-a)}$ when $a=1 (\operatorname{mod}\ 3)$, subject to no two points being included if they differ by the interchange of a $1$ and a $3$. Each of these Gamma sets is the feet of a degenerate isosceles triangle with vertex $\Gamma_{(a-1,n-i-2,a+3-a)}$. | ||

+ | |||

+ | \begin{lemma} If $A$ is a subset of $\Gamma_{(a,b,c)}$ such that no two points of $A$ differ by the interchange of a $1$ and a $3$, then $|A| \leq |\Gamma_{a,b,c}|/(1+\max(a,c))$. | ||

+ | \end{lemma} | ||

+ | \begin{proof} | ||

+ | Say that two points of $\Gamma_{a,b,c}$ are neighbours if they differ by the exchange of a $1$ and a $3$. Each point of $A$ has $ac$ neighbours, none of which are in $A$. Each point of $\Gamma_{(a,b,c)}\backslash A$ has $ac$ neighbours, but only $min(a,c)$ of them may be in $A$. So for each point of $A$ there are on average $ac/\min(a,c) = \max(a,c)$ points not in $A$. So the proportion of points of $\Gamma_{(a,b,c)}$ that are in $A$ is at most one in $1+\max(a,c)$. | ||

+ | \end{proof} | ||

+ | |||

+ | The proportion of extra points for each of the cells $\Gamma_{(a,n-i-4,i+4-a)}$ is no more than $2/(i+6)$. Only one cell in three is included from the $b=n-i-4$ layer, so we expect no more than $\binom{n}{i+4}2^{i+5}/(3i+18)$ new points, all from $S_{n,i+4}$. One can also find extra points from $S_{n,i+5}$ and higher spheres. | ||

+ | |||

+ | Earlier solutions may also give insight into the problem. 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$. | $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 | The first lower bounds may be due to Koml\'{o}s \cite{komlos}, who observed | ||

Line 7: | Line 89: | ||

(see Section \ref{notation-sec} for definition), | (see Section \ref{notation-sec} for definition), | ||

is a Moser set, so that | is a Moser set, so that | ||

− | + | \begin{equation}\label{cin} | |

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

+ | \end{equation} | ||

+ | 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 | applying Stirling's formula, we see that this lower bound takes the form | ||

\begin{equation}\label{cpn3} | \begin{equation}\label{cpn3} | ||

− | c'_{n,3} \geq C 3^n / \sqrt{n} | + | c'_{n,3} \geq (C-o(1)) 3^n / \sqrt{n} |

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

+ | for some absolute constant $C>0$; in fact \eqref{cin} gives \eqref{cpn3} with $C := \sqrt{\frac{9}{4\pi}}$. | ||

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

c'_{6,3}\geq 240$. | c'_{6,3}\geq 240$. | ||

− | + | ||

− | + | These 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$, | Observe that if $\{w(1),w(2),w(3)\}$ is a geometric line in $[3]^n$, | ||

Line 30: | Line 115: | ||

least two. | least two. | ||

(Recall Section \ref{notation-sec} for definitions), | (Recall Section \ref{notation-sec} for definitions), | ||

− | + | This leads to the lower bound | |

− | 2^{i-1} + \binom{n}{i} 2^{i-1} = \binom{n+1}{i} 2^{i-1}. | + | \begin{equation}\label{cn3-low} |

+ | c'_{n,3} \geq \binom{n}{i-1} | ||

+ | 2^{i-1} + \binom{n}{i} 2^{i-1} = \binom{n+1}{i} 2^{i-1}. | ||

+ | \end{equation} | ||

+ | It is not | ||

hard to see that $\binom{n+1}{i+1} 2^{i} > \binom{n+1}{i} 2^{i-1}$ if | 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 = | and only if $3i < 2n+1$, and so this lower bound is maximised when $i = | ||

Line 38: | Line 127: | ||

c'_{3,3} \geq 16; c'_{4,3} \geq 40; c'_{5,3} \geq 120; c'_{6,3} \geq | 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 | 336$$ which gives the right lower bounds for $n=2,3$, but is slightly | ||

− | off for $n=4,5$. | + | off for $n=4,5$. Asymptotically, Stirling's formula and \eqref{cn3-low} then |

+ | give the lower bound \eqref{cpn3} with $C = \frac{3}{2} \times \sqrt{\frac{9}{4\pi}}$, which is asymptotically $50\%$ better than the bound \eqref{cin}. | ||

The work of Chv\'{a}tal \cite{chvatal1} | The work of Chv\'{a}tal \cite{chvatal1} | ||

Line 44: | Line 134: | ||

which we here translate into the usual notation of coding theory: | which we here translate into the usual notation of coding theory: | ||

Let $A(n,d)$ denote the size of the largest binary code of length $n$ | Let $A(n,d)$ denote the size of the largest binary code of length $n$ | ||

− | + | and minimal distance $d$. | |

Then | Then | ||

Line 51: | Line 141: | ||

\end{equation} | \end{equation} | ||

− | + | The following values of $A(n,d)$ for small $n,d$ are known, see \cite{Brower}: | |

{\tiny{ | {\tiny{ | ||

\[ | \[ | ||

Line 74: | Line 164: | ||

A(13,1)=8192&A(13,2)=4096& A(13,3)=512& A(13,4)=256&A(13,5)=64&A(12,6)=32 | A(13,1)=8192&A(13,2)=4096& A(13,3)=512& A(13,4)=256&A(13,5)=64&A(12,6)=32 | ||

&A(13,7)=8&A(13,8)=4\\ | &A(13,7)=8&A(13,8)=4\\ | ||

− | |||

− | |||

\end{array} | \end{array} | ||

\] | \] | ||

}} | }} | ||

− | + | In addition, one has the general identities $A(n,1)=2^n, A(n,2)=2^{n-1}, A(n-1,2e-1)=A(n,2e)$, and $A(n,d)=2$, | |

− | + | ||

if $d>\frac{2n}{3}$. | if $d>\frac{2n}{3}$. | ||

− | |||

− | |||

− | |||

− | |||

− | + | Inserting this data into \eqref{cnchvatal} for $k=2$ we obtain the lower bounds | |

− | + | ||

\[ | \[ | ||

\begin{array}{llll} | \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) | 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 | + | =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) | 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 | + | =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) | 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. | =1\cdot 8+6 \cdot 16+15\cdot 16&=344. | ||

\end{array} | \end{array} | ||

\] | \] | ||

− | + | Similarly, with $k=3$ we obtain | |

\[ | \[ | ||

\begin{array}{llll} | \begin{array}{llll} | ||

Line 105: | Line 187: | ||

+ \binom{7}{3}A(4,1)&=960.\\ | + \binom{7}{3}A(4,1)&=960.\\ | ||

c'_{8,3}&\geq &\binom{8}{0}A(8,4)+\binom{8}{1}A(7,3)+\binom{8}{2}A(6,2) | 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,1)&=2832 | + | + \binom{8}{3}A(5,1)&=2832\\ |

c'_{9,3}&\geq & \binom{9}{0}A(9,4)+\binom{9}{1}A(8,3)+\binom{9}{2}A(7,2) | 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,1)&=7880 | + | + \binom{9}{3}A(6,1)&=7880 |

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

− | + | and for $k=4$ we have | |

\[ | \[ | ||

\begin{array}{llll} | \begin{array}{llll} | ||

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

− | + \binom{10}{3}A(7,2)+\binom{10}{4}A(6,1)&=22232 | + | + \binom{10}{3}A(7,2)+\binom{10}{4}A(6,1)&=22232\\ |

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

− | + \binom{11}{3}A(8,2)+\binom{11}{4}A(7,1)&=66024 | + | + \binom{11}{3}A(8,2)+\binom{11}{4}A(7,1)&=66024\\ |

c'_{12,3}&\geq &\binom{12}{0}A(12,5)+\binom{12}{1}A(11,4)+\binom{12}{2}A(10,3) | c'_{12,3}&\geq &\binom{12}{0}A(12,5)+\binom{12}{1}A(11,4)+\binom{12}{2}A(10,3) | ||

+ \binom{12}{3}A(9,2)+\binom{12}{4}A(8,1)&=188688.\\ | + \binom{12}{3}A(9,2)+\binom{12}{4}A(8,1)&=188688.\\ | ||

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

− | + | and for $k=5$ we have | |

\[ c'_{13,3}\geq 539168.\] | \[ c'_{13,3}\geq 539168.\] | ||

Line 127: | Line 209: | ||

The maximum value appears to occur for $k=\lfloor\frac{n+2}{3}\rfloor$, | The maximum value appears to occur for $k=\lfloor\frac{n+2}{3}\rfloor$, | ||

− | so that using | + | so that using Stirling's formula and explicit bounds on $A(n,d)$ the |

− | Stirling's formula and explicit bounds on $A(n,d)$ the | + | |

best possible value known to date | best possible value known to date | ||

− | of the constant $C$ in | + | of the constant $C$ in equation \eqref{cpn3} can be worked out, but we refrain from doing this here. |

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

− | Using the | + | |

\cite{chvatal1} proved that the expression on the right hand side of | \cite{chvatal1} proved that the expression on the right hand side of | ||

\eqref{cnchvatal} is also | \eqref{cnchvatal} is also | ||

Line 138: | Line 218: | ||

above gains a constant factor over the initial construction only. | above gains a constant factor over the initial construction only. | ||

− | |||

− | |||

− | |||

For $n=4$ the above does not yet give the exact value. | 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}. | The value $c'_{4,3}=43$ was first proven by Chandra \cite{chandra}. | ||

A uniform way of describing examples for the optimum values of | A uniform way of describing examples for the optimum values of | ||

− | $c'_{4,3}=43$ and $c'_{5,3}=124$ is | + | $c'_{4,3}=43$ and $c'_{5,3}=124$ is as follows. |

Let us consider the sets $$ A := S_{i-1,n} | Let us consider the sets $$ A := S_{i-1,n} | ||

Line 161: | Line 238: | ||

\item By taking $n=6$, $i=5$, and $A' = \{ 111111, 111113, 111331, | \item By taking $n=6$, $i=5$, and $A' = \{ 111111, 111113, 111331, | ||

111333, 331111, 331113\}$, we obtain $c'_{6,3} \geq 342$. \end{itemize} | 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$ | + | the bound for $n=6$ is inferior to the lower bound $c'_{6,3}\geq 344$ given above. |

− | + | ||

− | + | ||

− | \ | + | \subsection{Higher $k$ values} |

− | + | ||

− | + | We now consider lower bounds for $c'_{n,k}$ for some values of $k$ larger than $3$. Here we will see some further connections between the Moser problem and the density Hales-Jewett problem. | |

− | + | ||

− | + | For $k=4$, we have the lower bounds $c'_{n,4} \ge \binom{n}{n/2}2^n$. To see this, observe that the set of points with $a$ $1$s,$b$ $2$s,$c$ $3$s and $d$ $4$s, where $a+d$ has the constant value $n/2$, does not form geometric lines because points at the ends of a geometric line have more $a$ or $d$ values than points in the middle of the line. | |

− | + | ||

− | \ | + | The following lower bound is asymptotically twice as large. Take all points with $a$ $1$s, $b$ $2$s, $c$ $3$s and $d$ $4$s, for which: |

− | \ | + | |

− | + | \begin{itemize} | |

+ | \item Either $a+d = q$ or $q-1$, $a$ and $b$ have the same parity; or | ||

+ | \item $a+d = q-2$ or $q-3$, $a$ and $b$ have opposite parity. | ||

+ | \end{itemize} | ||

+ | |||

+ | This includes half the points of four adjacent layers, and therefore may include $(1+o(1))\binom{n}{n/2}2^{n+1}$ points. | ||

+ | |||

+ | We also have a lower bound for $c'_{n,5}$ similar to Theorem \ref{dhj-lower}, namely $c'_{n,5} = 5^{n-O(\sqrt{\log n})}$. Consider points with $a$ $1$s, $b$ $2$s, $c$ $3$s, $d$ $4$s and $e$ $5$s. For each point, take the value $a+e+2(b+d)+3c$. The first three points in any geometric line give values that form an arithmetic progression of length three. | ||

+ | |||

+ | Select a set of integers with no arithmetic progression of length $3$. Select all points whose value belongs to that sequence; there will be no geometric line among those points. By the Behrend construction\cite{behrend}, it is possible to choose these points with density $\exp{-O(\sqrt{\log n})}$. | ||

+ | |||

+ | For $k=6$, we observe that the asymptotic $c'_{n,6} = o(6^n)$ would imply the $k=3$ density Hales-Jewett theorem $c_{n,3}=o(3^n)$. Indeed, any $k=3$ combinatorial line-free set can be ``doubled up'' into a $k=6$ geometric line-free set of the same density by pulling back the set from the map that maps $1, 2, 3, 4, 5, 6$ to $1, 2, 3, 3, 2, 1$ respectively; note that this map sends $k=6$ geometric lines to $k=3$ combinatorial lines. So $c'_{n,6} \geq 2^n c_{n,3}$, and more generally, $c'_{n,2k} \geq 2^n c_{n,k}$. |

## Latest revision as of 02:34, 20 January 2010

\section{Lower bounds for the Moser problem}\label{moser-lower-sec}

Just as for the density Hales-Jewett problem, we found that Gamma sets $\Gamma_{a,b,c}$ were useful in providing large lower bounds for the Moser problem. This is despite the fact that the symmetries of the cube do not respect Gamma sets.

Observe that if $B \subset \Delta_n$, then the set $A_B := \bigcup_{\vec a \in B} \Gamma_{a,b,c}$ is a Moser set as long as $B$ does not contain any ``isosceles triangles* $(a+r,b,c+s), (a+s,b,c+r), (a,b+r+s,c)$ for any $r,s \geq 0$ not both zero; in particular, $B$ cannot contain any ``vertical line segments* $(a+r,b,c+r), (a,b+2r,c)$. An example of such a set is provided by selecting $0 \leq i \leq n-3$ and letting $B$ consist of the triples $(a, n-i, i-a)$ when $a \neq 3 \mod 3$, $(a,n-i-1,i+1-a)$ when $a \neq 1 \mod 3$, $(a,n-i-2,i+2-a)$ when $a=0 \mod 3$, and $(a,n-i-3,i+3-a)$ when $a=2 \mod 3$. Asymptotically, this set includes about two thirds of the spheres $S_{n,i}$, $S_{n,i+1}$ and one third of the spheres $S_{n,i+2}, S_{n,i+3}$ and (setting $i$ close to $n/3$) gives a lower bound \eqref{cpn3} with $C = 2 \times \sqrt{\frac{9}{4\pi}}$.

An integer program was run to obtain the optimal lower bounds achievable by the $A_B$ construction (using \eqref{cn3}, of course). The results for $1 \leq n \leq 20$ are displayed in Figure \ref{nlow-moser}. More complete data, including the list of optimisers, can be found at

\centerline{{\tt http://abel.math.umu.se/$\sim$klasm/Data/HJ/}.}

\begin{figure}[tb]
\centerline{
\begin{tabular}{|ll|ll|}
\hline
$n$ & lower bound & $n$ & lower bound \\
\hline
1 & 2 &11& 71766\\
2 & 6 & 12& 212423\\
3 & 16 & 13& 614875\\
4 & 43 & 14& 1794212\\
5 & 122& 15& 5321796\\
6 & 353& 16& 15455256\\
7 & 1017& 17& 45345052\\
8 & 2902&18& 134438520\\
9 & 8622&19& 391796798\\
10& 24786& 20& 1153402148\\
\hline
\end{tabular}}
\caption{Lower bounds for $c'_{n,3}$ obtained by the $A_B$ construction.}
\label{nlow-moser}
\end{figure}

\begin{figure}[tb]
\centerline{\includegraphics{moser353new.png}}
\caption{One of the examples of $353$-point sets in $[3]^6$ (elements of the set being indicated by white squares). This example was generated by a genetic algorithm.}
\label{moser353-fig}
\end{figure}

Unfortunately, we have been unable to locate a lower bound which is asymptotically better than \eqref{cpn3}. Indeed, any method based purely on the $A_B$ construction cannot do asymptotically better than the previous constructions:

\begin{proposition} Let $B \subset \Delta_n$ be such that $A_B$ is a Moser set. Then $|A_B| \leq (2 \sqrt{\frac{9}{4\pi}} + o(1)) \frac{3^n}{\sqrt{n}}$. \end{proposition}

\begin{proof} By the previous discussion, $B$ cannot contain any pair of the form $(a,b+2r,c), (a+r,b,c+r)$ with $r>0$. In other words, for any $-n \leq h \leq n$, $B$ can contain at most one triple $(a,b,c)$ with $c-a=h$. From this and \eqref{cn3}, we see that $$ |A_B| \leq \sum_{h=-n}^n \max_{(a,b,c) \in \Delta_n: c-a=h} \frac{n!}{a! b! c!}.$$ From the Chernoff inequality (or the Stirling formula computation below) we see that $\frac{n!}{a! b! c!} \leq \frac{1}{n^{10}} 3^n$ unless $a,b,c = n/3 + O( n^{1/2} \log^{1/2} n )$, so we may restrict to this regime, which also forces $h = O( n^{1/2}\log^{1/2} n)$. If we write $a = n/3 + \alpha$, $b = n/3 + \beta$, $c = n/3+\gamma$ and apply Stirling's formula $n! = (1+o(1)) \sqrt{2\pi n} n^n e^{-n}$, we obtain $$ \frac{n!}{a! b! c!} = (1+o(1)) \frac{3^{3/2}}{2\pi n} 3^n \exp( - (\frac{n}{3}+\alpha) \log (1 + \frac{3\alpha}{n} ) - (\frac{n}{3}+\beta) \log (1 + \frac{3\beta}{n} ) - (\frac{n}{3}+\gamma) \log (1 + \frac{3\gamma}{n} ) ).$$ From Taylor expansion one has $$ -(\frac{n}{3}+\alpha) \log (1 + \frac{3\alpha}{n} ) = -\alpha - \frac{3}{2} \frac{\alpha^2}{n} + o(1)$$ and similarly for $\beta,\gamma$; since $\alpha+\beta+\gamma=0$, we conclude that $$ \frac{n!}{a! b! c!} = (1+o(1)) \frac{3^{3/2}}{2\pi n} 3^n \exp( - \frac{3}{2n} (\alpha^2+\beta^2+\gamma^2) ).$$ If $c-a=h$, then $\alpha^2+\beta^2+\gamma^2 = \frac{3\beta^2}{2} + \frac{h^2}{2}$. Thus we see that $$ \max_{(a,b,c) \in \Delta_n: c-a=h} \frac{n!}{a! b! c!} \leq (1+o(1)) \frac{3^{3/2}}{2\pi n} 3^n \exp( - \frac{3}{4n} h^2 ).$$ Using the integral test, we thus have $$ |A_B| \leq (1+o(1)) \frac{3^{3/2}}{2\pi n} 3^n \int_\R \exp( - \frac{3}{4n} x^2 )\ dx.$$ Since $\int_\R \exp( - \frac{3}{4n} x^2 )\ dx = \sqrt{\frac{4\pi n}{3}}$, we obtain the claim. \end{proof}

Actually it is possible to improve upon these bounds by a slight amount. Observe that if $B$ is a maximiser for the right-hand side of \eqref{cn3} (subject to $B$ not containing isosceles triangles), then any triple $(a,b,c)$ not in $B$ must be the vertex of a (possibly degenerate) isosceles triangle with the other vertices in $B$. If this triangle is non-degenerate, or if $(a,b,c)$ is the upper vertex of a degenerate isosceles triangle, then no point from $\Gamma_{a,b,c}$ can be added to $A_B$ without creating a geometric line. However, if $(a,b,c) = (a'+r,b',c'+r)$ is only the lower vertex of a degenerate isosceles triangle $(a'+r,b',c'+r), (a',b'+2r,c')$, then one can add any subset of $\Gamma_{a,b,c}$ to $A_B$ and still have a Moser set as long as no pair of elements in that subset is separated by Hamming distance $2r$. For instance, in the $n=5$ case, we can start with the 122-point set built from $$B = \{ (0 0 5),(0 2 3),(1 1 3 ),(1 2 2 ),(2 2 1 ),(3 1 1 ),(3 2 0 ),(5 0 0))\}$$, and add a point each from (1 0 4) and (4 0 1). This gives an example of the maximal, 124-point solution. Again, in the $n=10$ case, the set \begin{align*} B &= \{(0 0 10),(0 2 8 ),(0 3 7 ),(0 4 6 ),(1 4 5 ),(2 1 7 ),(2 3 5 ), (3 2 5 ),(3 3 4 ),(3 4 3 ),(4 4 2 ),(5 1 4 ), \\ &\quad (5 3 2 ),(6 2 2 ), (6 3 1 ),(6 4 0 ),(8 1 1 ),(9 0 1 ),(9 1 0 ) \} \end{align*}

generates the lower bound $c'_{10,3} \geq 24786$ given above (and, up to reflection $a \leftrightarrow c$, is the only such set that does so); but by adding the following twelve elements from $\Gamma_{5,0,5}$ one can increase the lower bound slightly to $24798$: $1111133333$, $1111313333$, $1113113333$, $1133331113$, $1133331131$, $1133331311$, $3311333111$, $3313133111$, $3313313111$, $3331111133$, $3331111313$, $3331111331$

A more general form goes with the $B$ set described at the start of this section. Include points from $\Gamma_{(a,n-i-4,i+4-a)}$ when $a=1 (\operatorname{mod}\ 3)$, subject to no two points being included if they differ by the interchange of a $1$ and a $3$. Each of these Gamma sets is the feet of a degenerate isosceles triangle with vertex $\Gamma_{(a-1,n-i-2,a+3-a)}$.

\begin{lemma} If $A$ is a subset of $\Gamma_{(a,b,c)}$ such that no two points of $A$ differ by the interchange of a $1$ and a $3$, then $|A| \leq |\Gamma_{a,b,c}|/(1+\max(a,c))$. \end{lemma} \begin{proof} Say that two points of $\Gamma_{a,b,c}$ are neighbours if they differ by the exchange of a $1$ and a $3$. Each point of $A$ has $ac$ neighbours, none of which are in $A$. Each point of $\Gamma_{(a,b,c)}\backslash A$ has $ac$ neighbours, but only $min(a,c)$ of them may be in $A$. So for each point of $A$ there are on average $ac/\min(a,c) = \max(a,c)$ points not in $A$. So the proportion of points of $\Gamma_{(a,b,c)}$ that are in $A$ is at most one in $1+\max(a,c)$. \end{proof}

The proportion of extra points for each of the cells $\Gamma_{(a,n-i-4,i+4-a)}$ is no more than $2/(i+6)$. Only one cell in three is included from the $b=n-i-4$ layer, so we expect no more than $\binom{n}{i+4}2^{i+5}/(3i+18)$ new points, all from $S_{n,i+4}$. One can also find extra points from $S_{n,i+5}$ and higher spheres.

Earlier solutions may also give insight into the problem. 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 \begin{equation}\label{cin} c'_{n,3}\geq \vert S_{i,n}\vert \end{equation} 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-o(1)) 3^n / \sqrt{n} \end{equation} for some absolute constant $C>0$; in fact \eqref{cin} gives \eqref{cpn3} with $C := \sqrt{\frac{9}{4\pi}}$. In particular $c'_{3,3} \geq 12, c'_{4,3}\geq 24, c'_{5,3}\geq 80, c'_{6,3}\geq 240$.

These 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 \begin{equation}\label{cn3-low} c'_{n,3} \geq \binom{n}{i-1} 2^{i-1} + \binom{n}{i} 2^{i-1} = \binom{n+1}{i} 2^{i-1}. \end{equation} 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$. Asymptotically, Stirling's formula and \eqref{cn3-low} then give the lower bound \eqref{cpn3} with $C = \frac{3}{2} \times \sqrt{\frac{9}{4\pi}}$, which is asymptotically $50\%$ better than the bound \eqref{cin}.

The work of Chv\'{a}tal \cite{chvatal1} already contained a refinement of this idea which we here translate 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}

The following values of $A(n,d)$ for small $n,d$ are known, see \cite{Brower}: {\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\\ A(11,1)=2048&A(11,2)=1024& A(11,3)=144& A(11,4)=72&A(11,5)=24&A(11,6)=12 &A(11,7)=2&A(11,8)=2\\ A(12,1)=4096&A(12,2)=2048& A(12,3)=256& A(12,4)=144&A(12,5)=32&A(12,6)=24 &A(12,7)=4&A(12,8)=2\\ A(13,1)=8192&A(13,2)=4096& A(13,3)=512& A(13,4)=256&A(13,5)=64&A(12,6)=32 &A(13,7)=8&A(13,8)=4\\ \end{array} \] }} In addition, one has the general identities $A(n,1)=2^n, A(n,2)=2^{n-1}, A(n-1,2e-1)=A(n,2e)$, and $A(n,d)=2$, if $d>\frac{2n}{3}$.

Inserting this data into \eqref{cnchvatal} for $k=2$ we obtain the lower bounds \[ \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} \] Similarly, with $k=3$ we obtain \[ \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,1)&=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,1)&=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,1)&=7880 \end{array}\] and for $k=4$ we have \[ \begin{array}{llll} c'_{10,3}&\geq &\binom{10}{0}A(10,5)+\binom{10}{1}A(9,4)+\binom{10}{2}A(8,3) + \binom{10}{3}A(7,2)+\binom{10}{4}A(6,1)&=22232\\ c'_{11,3}&\geq &\binom{11}{0}A(11,5)+\binom{11}{1}A(10,4)+\binom{11}{2}A(9,3) + \binom{11}{3}A(8,2)+\binom{11}{4}A(7,1)&=66024\\ c'_{12,3}&\geq &\binom{12}{0}A(12,5)+\binom{12}{1}A(11,4)+\binom{12}{2}A(10,3) + \binom{12}{3}A(9,2)+\binom{12}{4}A(8,1)&=188688.\\ \end{array}\] and for $k=5$ we have \[ c'_{13,3}\geq 539168.\]

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 \cite{chvatal1} proved that the expression on the right hand side of \eqref{cnchvatal} is also $O\left( \frac{3^n}{\sqrt{n}}\right)$, so that the refinement described above gains a constant factor over the initial construction only.

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 as follows.

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.

\subsection{Higher $k$ values}

We now consider lower bounds for $c'_{n,k}$ for some values of $k$ larger than $3$. Here we will see some further connections between the Moser problem and the density Hales-Jewett problem.

For $k=4$, we have the lower bounds $c'_{n,4} \ge \binom{n}{n/2}2^n$. To see this, observe that the set of points with $a$ $1$s,$b$ $2$s,$c$ $3$s and $d$ $4$s, where $a+d$ has the constant value $n/2$, does not form geometric lines because points at the ends of a geometric line have more $a$ or $d$ values than points in the middle of the line.

The following lower bound is asymptotically twice as large. Take all points with $a$ $1$s, $b$ $2$s, $c$ $3$s and $d$ $4$s, for which:

\begin{itemize} \item Either $a+d = q$ or $q-1$, $a$ and $b$ have the same parity; or \item $a+d = q-2$ or $q-3$, $a$ and $b$ have opposite parity. \end{itemize}

This includes half the points of four adjacent layers, and therefore may include $(1+o(1))\binom{n}{n/2}2^{n+1}$ points.

We also have a lower bound for $c'_{n,5}$ similar to Theorem \ref{dhj-lower}, namely $c'_{n,5} = 5^{n-O(\sqrt{\log n})}$. Consider points with $a$ $1$s, $b$ $2$s, $c$ $3$s, $d$ $4$s and $e$ $5$s. For each point, take the value $a+e+2(b+d)+3c$. The first three points in any geometric line give values that form an arithmetic progression of length three.

Select a set of integers with no arithmetic progression of length $3$. Select all points whose value belongs to that sequence; there will be no geometric line among those points. By the Behrend construction\cite{behrend}, it is possible to choose these points with density $\exp{-O(\sqrt{\log n})}$.

For $k=6$, we observe that the asymptotic $c'_{n,6} = o(6^n)$ would imply the $k=3$ density Hales-Jewett theorem $c_{n,3}=o(3^n)$. Indeed, any $k=3$ combinatorial line-free set can be ``doubled up* into a $k=6$ geometric line-free set of the same density by pulling back the set from the map that maps $1, 2, 3, 4, 5, 6$ to $1, 2, 3, 3, 2, 1$ respectively; note that this map sends $k=6$ geometric lines to $k=3$ combinatorial lines. So $c'_{n,6} \geq 2^n c_{n,3}$, and more generally, $c'_{n,2k} \geq 2^n c_{n,k}$.*