Difference between revisions of "Moser-lower.tex"

From Polymath1Wiki
Jump to: navigation, search
Line 72: Line 72:
  
 
A more general form goes with the $B$ set described at the start of this section.  Include points from $(a,n-i-4,i+4-a)$ when $a=1 (mod 3)$, subject to no two points being included if they differ by the interchange of a $1$ and a $3$.  This introduces no more than $\frac{2}{3(i+6)}\binom(n,i+4)2^{i+4}$ new points, all from $S_{n,i+4}$.  One can continue with points from $S_{n,i+5}$ and higher spheres.
 
A more general form goes with the $B$ set described at the start of this section.  Include points from $(a,n-i-4,i+4-a)$ when $a=1 (mod 3)$, subject to no two points being included if they differ by the interchange of a $1$ and a $3$.  This introduces no more than $\frac{2}{3(i+6)}\binom(n,i+4)2^{i+4}$ new points, all from $S_{n,i+4}$.  One can continue with 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$.
 
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
 
\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}
 
 
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\\
 
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}
 
\]
 
}}
 
 
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,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}\]
 
With k=4
 
\[
 
\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}\]
 
With $k=5$
 
\[ 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 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.
 
 
  
 
\subsection{Higher k values}
 
\subsection{Higher k values}
One can consider subsets of $[k]{}^n$ that contain no geometric lines.  Section \ref{moser-lower-sec} has considered the case $k=3$.  Let $c'_{n,k}$ be the greatest number of points in $[k]{}^n$ with no geometric line.  For example, $c'_{n,3} = c'_n$.  We have the following lower bounds:
+
We now consider subsets of $[k]{}^n$ that contain no geometric lines.  Section \ref{moser-lower-sec} has considered the case $k=3$.  Let $c'_{n,k}$ be the greatest number of points in $[k]{}^n$ with no geometric line.  For example, $c'_{n,3} = c'_n$.  We have the following lower bounds:
  
$c'_{n,4} \ge \binom{n}{n/2}2^n$.
+
$c'_{n,4} \ge \binom{n}{\lfloor n/2\rfloor}2^{n+1}$.
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 point in the middle of the line.
+
Firstly, 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 point in the middle of the line.
 
+
One can show a lower bound that, asymptotically, is twice as large as $\binom{n}{n/2}2^n$.  Take all points with $a$ $1$s, $b$ $2$s, $c$ $3$s and $d$ $4$s, for which:
+
 
+
Either $a+d = q or q-1$, $a$ and $b$ have the same parity;
+
  
 +
But one has a lower bound that, asymptotically, is twice as large.  Take all points with $a$ $1$s, $b$ $2$s, $c$ $3$s and $d$ $4$s, for which:
 +
\begin{itemize}
 +
$a+d = q or q-1$, $a$ and $b$ have the same parity;
 +
\item
 
Or    $a+d = q-2 or q-3$, $a$ and $b$ have opposite parity.
 
Or    $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.
+
This includes half the points of four adjacent layers, and therefore includes $(1+o(1))\binom{n}{\lfloor n/2\rfloor}2^{n+1}$ points.
  
We also have a DHJ(3)-like lower bound for $c'_{n,5}$, namely $c'_{n,5} = 5^{n-O(\sqrt{\log n})}$.
+
We have a DHJ(3)-like lower bound for $c'_{n,5}$, 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.   
 
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 Behrend theory, it is possible to choose these points with density $\exp{-O(\sqrt{\log n})}$.
 
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 Behrend theory, it is possible to choose these points with density $\exp{-O(\sqrt{\log n})}$.
 +
 +
The Moser sets of side $k=6$ are related to the DHJ sets of side $k=3$.  If we have a coordinate-line-free subset of $[3]{}^n$ with $P$ points, we can double it up along each dimension, and get a geometric-line-free subset of $[6]{}^n$ with $2^nP$ points.  So $c'_{n,6}\geq 2^n c_n$.

Revision as of 20:04, 25 June 2009

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

Just as for the DHJ 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}:

\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$ obtained by the $A_B$ construction.} \label{nlow-moser} \end{figure}

More complete data, including the list of optimisers, can be found at {\tt http://abel.math.umu.se/~klasm/Data/HJ/}.

Note that the lower bound $c'_{6,3} \geq 353$ was first located by a genetic algorithm: see Appendix \ref{genetic-alg}.

\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).} \label{moser353-fig} \end{figure}

However, 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 $$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 ),(5 3 2 ),(6 2 2 ), (6 3 1 ),(6 4 0 ),(8 1 1 ),(9 0 1 ),(9 1 0 ) \}$$

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 $(a,n-i-4,i+4-a)$ when $a=1 (mod 3)$, subject to no two points being included if they differ by the interchange of a $1$ and a $3$. This introduces no more than $\frac{2}{3(i+6)}\binom(n,i+4)2^{i+4}$ new points, all from $S_{n,i+4}$. One can continue with points from $S_{n,i+5}$ and higher spheres.

\subsection{Higher k values} We now consider subsets of $[k]{}^n$ that contain no geometric lines. Section \ref{moser-lower-sec} has considered the case $k=3$. Let $c'_{n,k}$ be the greatest number of points in $[k]{}^n$ with no geometric line. For example, $c'_{n,3} = c'_n$. We have the following lower bounds:

$c'_{n,4} \ge \binom{n}{\lfloor n/2\rfloor}2^{n+1}$. Firstly, 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 point in the middle of the line.

But one has a lower bound that, asymptotically, is twice as large. Take all points with $a$ $1$s, $b$ $2$s, $c$ $3$s and $d$ $4$s, for which: \begin{itemize}

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

\item Or $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 includes $(1+o(1))\binom{n}{\lfloor n/2\rfloor}2^{n+1}$ points.

We have a DHJ(3)-like lower bound for $c'_{n,5}$, 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 Behrend theory, it is possible to choose these points with density $\exp{-O(\sqrt{\log n})}$.

The Moser sets of side $k=6$ are related to the DHJ sets of side $k=3$. If we have a coordinate-line-free subset of $[3]{}^n$ with $P$ points, we can double it up along each dimension, and get a geometric-line-free subset of $[6]{}^n$ with $2^nP$ points. So $c'_{n,6}\geq 2^n c_n$.