Polymath Wiki - User contributions [en]

Polymath.tex

2009-06-05T14:34:23Z

81.132.196.202:

\documentclass[12pt,a4paper,reqno]{amsart}
\usepackage{amssymb}
\usepackage{amscd}
%\usepackage{psfig}
\usepackage{graphicx}
%\usepackage{showkeys}
% uncomment this when editing cross-references
\numberwithin{equation}{section}

\addtolength{\textwidth}{3 truecm}
\addtolength{\textheight}{1 truecm}
\setlength{\voffset}{-.6 truecm}
\setlength{\hoffset}{-1.3 truecm}

\theoremstyle{plain}

\newtheorem{theorem}{Theorem}[section]
%\newtheorem{theorem}[theorem]{Theorem}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{principle}[theorem]{Principle}
\newtheorem{claim}[theorem]{Claim}

\theoremstyle{definition}

%\newtheorem{roughdef}[subsection]{Rough Definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{remarks}[theorem]{Remarks}
\newtheorem{example}[theorem]{Example}
\newtheorem{examples}[theorem]{Examples}
%\newtheorem{problem}[subsection]{Problem}
%\newtheorem{question}[subsection]{Question}

\newcommand\E{\mathbb{E}}
\newcommand\Z{\mathbb{Z}}
\newcommand\N{\mathbb{N}}
\renewcommand\P{\mathbb{P}}

\parindent 0mm
\parskip 5mm

\begin{document}

\title{Density Hales-Jewett and Moser numbers in low dimensions}

\author{D.H.J. Polymath}
\address{http://michaelnielsen.org/polymath1/index.php}
\email{???}

\subjclass{???}

\begin{abstract}
For any $n \geq 0$ and $k \geq 1$, the density Hales-Jewett number $c_{n,k}$ is defined as the size of the largest subset of the cube $[k]^n$ := $\{1,\ldots,k\}^n$ which contains no combinatorial line; similarly, the Moser number $c'_{n,k}$ is the largest subset of the cube $[k]^n$ which contains no geometric line. A deep theorem of Furstenberg and Katznelson \cite{fk1}, \cite{fk2}, \cite{mcc} shows that $c_{n,k}$ = $o(k^n)$ as $n \to \infty$ (which implies a similar claim for $c'_{n,k}$; this is already non-trivial for $k = 3$. Several new proofs of this result have also been recently established \cite{poly}, \cite{austin}.

Using both human and computer-assisted arguments, we compute several values of $c_{n,k}$ and $c'_{n,k}$ for small $n,k$. For instance the sequence $c_{n,3}$ for $n=0,\ldots,6$ is $1,2,6,18,52,150,450$, while the sequence $c'_{n,3}$ for $n=0,\ldots,5$ is $1,2,6,16,43,124$. We also establish some results for higher $k$, showing for instance that an analogue of the LYM inequality (which relates to the $k = 2$ case) does not hold for higher $k$.
\end{abstract}

\maketitle
%\today

\setcounter{tocdepth}{1}
\tableofcontents

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\include{introduction}
\include{dhj-lown-lower}
\include{dhj-lown}
\include{moser-lower}
\include{moser}
\include{fujimura}
\include{higherk}
\include{coloring}

\appendix

\include{genetic}
\include{integer}

\begin{thebibliography}{10}

\bibitem{austin} T. Austin, \emph{Deducing the density Hales-Jewett theorem from an infinitary removal lemma}, preprint.

\bibitem{behrend}
F. Behrend, \emph{On the sets of integers which contain no three in arithmetic progression}, Proceedings of the National Academy of Sciences \textbf{23} (1946), 331–-332.

\bibitem{chandra}
A. Chandra, \emph{On the solution of Moser's problem in four dimensions}, Canad. Math. Bull. \textbf{16} (1973), 507--511.

\bibitem{chvatal1} V. Chv\'{a}tal, \emph{Remarks on a problem of Moser}, Canadian Math Bulletin, Vol 15, 1972, 19--21.

\bibitem{chvatal2} V. Chv\'{a}tal, \emph{Edmonds polytopes and a hierarchy of combinatorial problems}, Discrete Math. 4 (1973) 305-337.

\bibitem{elkin}
M. Elkin, \emph{An Improved Construction of Progression-Free Sets}, preprint.

\bibitem{fk1} H. Furstenberg, Y. Katznelson, \emph{A density version of the Hales-Jewett theorem for $k = 3$}, Graph Theory and Combinatorics (Cambridge, 1988). Discrete Math. 75 (1989), no. 1-3, 227–-241.

\bibitem{fk2} H. Furstenberg, Y. Katznelson, \emph{A density version of the Hales-Jewett theorem}, J. Anal. Math. 57 (1991), 64–-119. MR1191743

\bibitem{greenwolf}
B. Green, J. Wolf, \emph{A note on Elkin's improvement of Behrend's construction}, preprint.

\bibitem{komlos}
J. Koml\'{o}s, solution to problem P.170 by Leo Moser, Canad. Math.. Bull. vol {\bf (??check)} (1972), 312--313, 1970.

\bibitem{Krisha} K. Krishna, M. Narasimha Murty, "Genetic K-means algorithm," Systems, Man, and Cybernetics, Part B: Cybernetics, IEEE Transactions on , vol.29, no.3, pp.433-439, Jun 1999

\bibitem{moser} L. Moser, Problem P.170 in Canad. Math. Bull. 13 (1970), 268.

\bibitem{mcc} R. McCutcheon, \emph{The conclusion of the proof of the density Hales-Jewett theorem for k=3}, unpublished.

\bibitem{obryant}
K. O'Bryant, \emph{Sets of integers that do not contain long arithmetic progressions}, preprint.

\bibitem{oeis}
N. J. A. Sloane, Ed. (2008), The On-Line Encyclopedia of Integer Sequences, {\tt www.research.att.com/~njas/sequences/}

\bibitem{poly} D.H.J. Polymath, ???, preprint. {\bf need title}

\bibitem{rankin}
R. A. Rankin, Sets of integers containing not more than a given number of terms in arithmetical progression, Proc. Roy. Soc. Edinburgh Sect. A 65 (1960/1961), 332–344 (1960/61). MR 0142526 (26 #95)

\bibitem{roth}
K. Roth, \emph{On certain sets of integers, I}, Journal of the London Mathematical Society \textbf{28} (1953), 104-–109.

\bibitem{Rothlauf} F. Rothlauf, D. E. Goldberg, Representations for Genetic and Evolutionary Algorithms. Physica-Verlag, 2002.

\bibitem{sperner}
E. Sperner, \emph{Ein Satz \"uber Untermengen einer endlichen Menge}, Mathematische Zeitschrift \textbf{27} (1928), 544-–548.

\bibitem{szem}
E. Szemer\'edi, \emph{On sets of integers containing no k elements in arithmetic progression}, Acta Arithmetica \textbf{27} (1975), 199-–245.

\end{thebibliography}

\end{document}

Moser-lower.tex

2009-06-05T14:27:12Z

81.132.196.202:

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