Difference between revisions of "Polymath.tex"

From Polymath1Wiki
Jump to: navigation, search
(fix section formatting error)
 
(22 intermediate revisions by 6 users not shown)
Line 3: Line 3:
 
\usepackage{amscd}
 
\usepackage{amscd}
 
%\usepackage{psfig}
 
%\usepackage{psfig}
 +
\usepackage{graphicx}
 
%\usepackage{showkeys}   
 
%\usepackage{showkeys}   
 
% uncomment this when editing cross-references
 
% uncomment this when editing cross-references
Line 35: Line 36:
  
 
\newcommand\E{\mathbb{E}}
 
\newcommand\E{\mathbb{E}}
 +
\newcommand\R{\mathbb{R}}
 +
\newcommand\Z{\mathbb{Z}}
 +
\newcommand\N{\mathbb{N}}
 
\renewcommand\P{\mathbb{P}}
 
\renewcommand\P{\mathbb{P}}
  
Line 44: Line 48:
  
  
\title{Density Hales-Jewett and Moser numbers in low dimensions}
+
\title{Density Hales-Jewett and Moser numbers}
  
 
\author{D.H.J. Polymath}
 
\author{D.H.J. Polymath}
 
\address{http://michaelnielsen.org/polymath1/index.php}
 
\address{http://michaelnielsen.org/polymath1/index.php}
\email{???}
+
%\email{}
  
\subjclass{???}
+
\subjclass{05D05, 05D10}
  
 
\begin{abstract}   
 
\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}.
+
For any $n \geq 0$ and $k \geq 1$, the \emph{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$.  
+
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,6$ is $1,2,6,16,43,124,353$. We also prove 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$, and also establishing the asymptotic lower bound $c_{n,k} \geq k^n \exp\left( - O(\sqrt[\ell]{\log n})\right)$ where $\ell$ is the largest integer such that $2k > 2^\ell$.  
 
\end{abstract}
 
\end{abstract}
  
Line 61: Line 65:
 
%\today
 
%\today
  
\setcounter{tocdepth}{1}
+
%\setcounter{tocdepth}{1}
\tableofcontents
+
%\tableofcontents
 
+
  
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Introduction}
+
\input{introduction}
 +
\input{dhj-lown-lower}
 +
\input{dhj-lown}
 +
\input{moser-lower}
 +
\input{moser}
 +
%\input{fujimura}
 +
%\input{higherk}
 +
% \input{coloring}
  
...
+
%\appendix
  
 +
%\input{genetic}
 +
%\input{integer}
  
In Sections \ref{moser-lower-sec}, \ref{moser-upper-sec} we will show
+
\begin{thebibliography}{10}
  
\begin{theorem}[Values of $c'_{n,3}$ for small $n$]\label{moser}  We have $c'_{0,3} = 1$, $c'_{1,3} = 2$, $c'_{2,3} = 6$, $c'_{3,3} = 16$, $c'_{4,3} = 43$, $c'_{5,3} = 124$, and $353 \leq c'_{6,3} \leq 361$.
+
\bibitem{ajtai} M. Ajtai, E. Szemer\'edi, \emph{Sets of lattice points that form no squares}, Studia Scientiarum Mathematicarum Hungarica, \textbf{9} (1974-1975), 9--11.  
\end{theorem}
+
  
\begin{remark} The values of $c'_{n,3}$ for $n=0,1,2$ are easily verified. The quantity $c'_{3,3}$ was first computed in \cite{chvatal2}, while the quantity $c'_{4,3}$ was computed in \cite{chandra}; we will give alternate proofs of these results here. The bounds for $c'_{5,3}$ and $c'_{6,3}$ are new.
+
\bibitem{austin} T. Austin, \emph{Deducing the density Hales-Jewett theorem from an infinitary removal lemma}, preprint, available at {\tt arxiv.org/abs/0903.1633}.
\end{remark}
+
  
\section{Lower bounds for the Moser problem}\label{moser-lower-sec}
+
\bibitem{beck} J. Beck, Combinatorial Games: Tic-Tac-Toe Theory. Cambridge University Press, 2008, Cambridge.
  
...
+
\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.
  
(Here we prove the lower bounds in Theorem \ref{moser}.)
+
\bibitem{Brower}
 +
A. Brower, {\tt www.win.tue.nl/$\sim$aeb/codes/binary-1.html}.
  
\section{Upper bounds for the $k=3$ Moser problem in small dimensions}\label{moser-upper-sec}
+
\bibitem{chandra}
 +
A. Chandra, \emph{On the solution of Moser's problem in four dimensions}, Canad. Math. Bull. \textbf{16} (1973), 507--511.
  
\include{moser}
+
\bibitem{chvatal1} V. Chv\'{a}tal, \emph{Remarks on a problem of Moser}, Canad. Math. Bull., \textbf{15} (1972) 19--21.
  
+
\bibitem{chvatal2} V. Chv\'{a}tal, \emph{Edmonds polytopes and a hierarchy of combinatorial problems}, Discrete Math. \textbf{4} (1973) 305--337.
\appendix
+
  
\section{Genetic algorithms}
+
\bibitem{elkin}
 +
M. Elkin, \emph{An Improved Construction of Progression-Free Sets}, preprint.
  
\include{genetic}
+
\bibitem{fuji}
 +
K. Fujimura, {\tt www.puzzles.com/PuzzlePlayground/CoinsAndTriangles/CoinsAndTriangles.htm}
  
\begin{thebibliography}{10}
+
\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. \textbf{75} (1989), 227–-241.
  
\bibitem{austin} T. Austin, \emph{Deducing the density Hales-Jewett theorem from an infinitary removal lemma}, preprint.  
+
\bibitem{fk2} H. Furstenberg, Y. Katznelson, \emph{A density version of the Hales-Jewett theorem}, J. Anal. Math. \textbf{57} (1991), 64–-119.  
  
\bibitem{chandra}
+
\bibitem{kra}
A. Chandra, \emph{On the solution of Moser's problem in four dimensions}, Canad. Math. Bull. \textbf{16} (1973), 507--511.
+
D. Geller, I. Kra, S. Popescu, S. Simanca, \emph{On circulant matrices}, {\tt www.math.sunysb.edu/$\sim$sorin/eprints/circulant.pdf}
  
\bibitem{chvatal1} V. Chvatal, \emph{Remarks on a problem of Moser}, Canadian Math Bulletin, Vol 15, 1972, 19--21.
+
\bibitem{greenwolf}
 +
B. Green, J. Wolf, \emph{A note on Elkin's improvement of Behrend's construction}, preprint, available at {\tt arxiv.org/abs/0810.0732}.
  
\bibitem{chvatal2} V. Chvatal, \emph{Edmonds polytopes and a hierarchy of combinatorial problems}, Discrete Math. 4 (1973) 305-337.
+
\bibitem{heule} M. Heule, presentation at {\tt www.st.ewi.tudelft.nl/sat/slides/waerden.pdf}
  
\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{komlos}
 +
J. Koml\'{o}s, solution to problem P.170 by Leo Moser, Canad. Math. Bull. \textbf{15} (1972), 312--313, 1970.
  
\bibitem{fk2} H. Furstenberg, Y. Katznelson, \emph{A density version of the Hales-Jewett theorem}, J. Anal. Math. 57 (1991), 64–-119. MR1191743
+
%\bibitem{Krisha} K. Krishna, M. Narasimha Murty, \emph{Genetic $K$-means algorithm}, Systems, Man, and Cybernetics, Part B: Cybernetics, IEEE Transactions on , vol.29, no.3, pp.433-439, Jun 1999
  
\bibitem{komlos}
+
\bibitem{markstrom} K. Markstrom, {{\tt abel.math.umu.se/$\sim$klasm/Data/HJ/}}
J. Komlos, solution to problem P.170 by Leo Moser, Canad. Math.. Bull. vol (??check) (1972), 312-313, 1970.
+
 
 +
\bibitem{moser} L. Moser, Problem P.170 in Canad. Math. Bull. \textbf{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, available at {\tt arxiv.org/abs/0811.3057}.
 +
 
 +
\bibitem{oeis}
 +
N. J. A. Sloane, Ed. (2008), The On-Line Encyclopedia of Integer Sequences, {\tt www.research.att.com/$\sim$njas/sequences/}
 +
 
 +
\bibitem{potenchin}
 +
A. Potechin, \emph{Maximal caps in $AG(6, 3)$}, Des. Codes Cryptogr., \textbf{46} (2008), 243--259.
  
\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{poly} D.H.J. Polymath, \emph{A new proof of the density Hales-Jewett theorem}, preprint, available at {\tt arxiv.org/abs/0910.3926}.
  
\bibitem{moser} L. Moser, Problem P.170 in Canad. Math. Bull. 13 (1970), 268. 
+
\bibitem{polywiki} D.H.J. Polymath, {\tt michaelnielsen.org/polymath1/index.php?title=Polymath1}
  
\bibitem{mcc} R. McCutcheon, \emph{The conclusion of the proof of the density Hales-Jewett theorem for k=3}, unpublished.  
+
\bibitem{rankin}  
 +
R. A. Rankin, \emph{Sets of integers containing not more than a given number of terms in arithmetical progression}, Proc. Roy. Soc. Edinburgh Sect. A \textbf{65} (1960/1961), 332–-344.  
  
\bibitem{poly} D.H.J. Polymath, ???, preprint.
+
\bibitem{roth}
 +
K. Roth, \emph{On certain sets of integers, I}, J. Lond. Math. Soc. \textbf{28} (1953), 104-–109.
  
\bibitem{Rothlauf} F. Rothlauf, D. E. Goldberg, Representations for Genetic and Evolutionary Algorithms. Physica-Verlag, 2002.
+
%\bibitem{Rothlauf} F. Rothlauf, D. E. Goldberg, Representations for Genetic and Evolutionary Algorithms. Physica-Verlag, 2002.
  
 +
\bibitem{shelah} S. Shelah, \emph{Primitive recursive bounds for van der Warden numbers}, J. Amer. Math. Soc. \textbf{28} (1988), 683-–697.
  
 +
\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{thebibliography}

Latest revision as of 19:37, 25 January 2010

\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\R{\mathbb{R}} \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}

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

\subjclass{05D05, 05D10}

\begin{abstract} For any $n \geq 0$ and $k \geq 1$, the \emph{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,6$ is $1,2,6,16,43,124,353$. We also prove 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$, and also establishing the asymptotic lower bound $c_{n,k} \geq k^n \exp\left( - O(\sqrt[\ell]{\log n})\right)$ where $\ell$ is the largest integer such that $2k > 2^\ell$. \end{abstract}

\maketitle %\today

%\setcounter{tocdepth}{1} %\tableofcontents

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

%\appendix

%\input{genetic} %\input{integer}

\begin{thebibliography}{10}

\bibitem{ajtai} M. Ajtai, E. Szemer\'edi, \emph{Sets of lattice points that form no squares}, Studia Scientiarum Mathematicarum Hungarica, \textbf{9} (1974-1975), 9--11.

\bibitem{austin} T. Austin, \emph{Deducing the density Hales-Jewett theorem from an infinitary removal lemma}, preprint, available at {\tt arxiv.org/abs/0903.1633}.

\bibitem{beck} J. Beck, Combinatorial Games: Tic-Tac-Toe Theory. Cambridge University Press, 2008, Cambridge.

\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{Brower} A. Brower, {\tt www.win.tue.nl/$\sim$aeb/codes/binary-1.html}.

\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}, Canad. Math. Bull., \textbf{15} (1972) 19--21.

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

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

\bibitem{fuji} K. Fujimura, {\tt www.puzzles.com/PuzzlePlayground/CoinsAndTriangles/CoinsAndTriangles.htm}

\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. \textbf{75} (1989), 227–-241.

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

\bibitem{kra} D. Geller, I. Kra, S. Popescu, S. Simanca, \emph{On circulant matrices}, {\tt www.math.sunysb.edu/$\sim$sorin/eprints/circulant.pdf}

\bibitem{greenwolf} B. Green, J. Wolf, \emph{A note on Elkin's improvement of Behrend's construction}, preprint, available at {\tt arxiv.org/abs/0810.0732}.

\bibitem{heule} M. Heule, presentation at {\tt www.st.ewi.tudelft.nl/sat/slides/waerden.pdf}

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

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

\bibitem{markstrom} K. Markstrom, Template:\tt abel.math.umu.se/$\sim$klasm/Data/HJ/

\bibitem{moser} L. Moser, Problem P.170 in Canad. Math. Bull. \textbf{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, available at {\tt arxiv.org/abs/0811.3057}.

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

\bibitem{potenchin} A. Potechin, \emph{Maximal caps in $AG(6, 3)$}, Des. Codes Cryptogr., \textbf{46} (2008), 243--259.

\bibitem{poly} D.H.J. Polymath, \emph{A new proof of the density Hales-Jewett theorem}, preprint, available at {\tt arxiv.org/abs/0910.3926}.

\bibitem{polywiki} D.H.J. Polymath, {\tt michaelnielsen.org/polymath1/index.php?title=Polymath1}

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

\bibitem{roth} K. Roth, \emph{On certain sets of integers, I}, J. Lond. Math. Soc. \textbf{28} (1953), 104-–109.

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

\bibitem{shelah} S. Shelah, \emph{Primitive recursive bounds for van der Warden numbers}, J. Amer. Math. Soc. \textbf{28} (1988), 683-–697.

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