%%%% THIS FILE IS AUTOMATICALLY GENERATED %%%% DO NOT EDIT THIS FILE DIRECTLY, %%%% ONLY EDIT THE SOURCE, tom-4.5/document.tex. %%%% %% Standard package list \documentclass[letterpaper]{article} \usepackage[utf8]{inputenc} \usepackage[T1]{fontenc} \usepackage[english]{babel} \usepackage[top=3cm, bottom=3cm, left=3.5cm, right=3.5cm]{geometry} \usepackage[onehalfspacing]{setspace} \usepackage{amsmath,amssymb,amsthm,wasysym} \usepackage{nicefrac,booktabs} \usepackage{mathptmx} \usepackage{cite} \usepackage[colorlinks=true]{hyperref} %% Various helpers for Tom's papers \newcommand{\gs}{\textnormal{gs}} \newcommand{\ord}{\textnormal{ord}} \newcommand{\Exp}{\textnormal{Exp}} \newcommand{\Log}{\textnormal{Log}} \newcommand{\lcm}{\textnormal{lcm}} \newcommand{\range}{\textnormal{range}} \newcommand{\NR}{\textnormal{NR}} \newcommand{\Mod}[1]{\left(\textnormal{mod}~#1\right)} \newcommand{\ap}[2]{\left\langle #1;#2 \right\rangle} \newcommand{\summ}[1]{\sum_{k=1}^m{#1}} \newcommand{\bt}[1]{{{#1}\mathbb{N}}} \newcommand{\fp}[1]{{\left\lbrace{#1}\right\rbrace}} \newcommand{\intv}[1]{{\left[1,{#1}\right]}} %% Lifted from http://stackoverflow.com/questions/2767389/referencing-a-theorem-like-environment-by-its-name %% This lets me do things like "Theorem A" and have the references work properly. \makeatletter \let\@old@begintheorem=\@begintheorem \def\@begintheorem#1#2[#3]{% \gdef\@thm@name{#3}% \@old@begintheorem{#1}{#2}[#3]% } \def\namedthmlabel#1{\begingroup \edef\@currentlabel{\@thm@name}% \label{#1}\endgroup } \makeatother % end lift \newtheoremstyle{namedthrm} {}{}{}{}{}{}{ } % This last space needs to be there {\bf\thmname{#1} \thmnote{#3}.} %% End reference hack %% Document start \date{} \begin{document} %% Content start \newtheorem{thrm}{Theorem} \newtheorem{corl}[thrm]{Corollary} \newtheorem{prop}[thrm]{Proposition} \theoremstyle{definition} \newtheorem*{rmrk}{Remark} \newcommand{\ceil}[1]{{\left\lceil{#1}\right\rceil}} \newcommand{\floor}[1]{{\left\lfloor{#1}\right\rfloor}} \title{Bounds on some van der Waerden numbers} \author{ Tom C. Brown\footnote{Department of Mathematics and Statistics, ¶ˇĎăÔ°AV, Burnaby, BC Canada V5A 1S6. \texttt{tbrown@sfu.ca}.}, Bruce M. Landman\footnote{Department of Mathematics, University of West Georgia, Carrollton, GA 30118, USA}, Aaron Robertson\footnote{Department of Mathematics, Colgate University, Hamilton, NY 13346, USA}} \maketitle \begin{center}{\small {\bf Citation data:} T.C. {Brown}, Bruce M. Landman, and Aaron Robertson, \emph{Bounds on some van der Waerden numbers}, J. Combin. Theory Ser. A.}\bigskip\end{center} \begin{abstract}For positive integers $s$ and $k_1, k_2,\ldots, k_s$, the van der Waerden number $w(k_1, k_2, \ldots, k_s ; s)$ is the minimum integer $n$ such that for every $s$-coloring of set $\{1, 2, \ldots, n\}$, with colors $1, 2, \ldots, s$, there is a $k_i$-term arithmetic progression of color $i$ for some $i$. We give an asymptotic lower bound for $w(k, m; 2)$ for fixed $m$. We include a table of values of $w(k, 3; 2)$ that are very close to this lower bound for $m = 3$. We also give a lower bound for $w(k, k, \ldots, k; s)$ that slightly improves previously-known bounds. Upper bounds for $w(k, 4; 2)$ and $w(4, 4, \ldots, 4; s)$ are also provided. \end{abstract} \section{Introduction\label{s1}} Two fundamental theorems in combinatorics are van der Waerden’s theorem \cite{vanderwaerden1927} and Ramsey's theorem \cite{ramsey1930}. The theorem of van der Waerden says that for all positive integers $s$ and $k_1, k_2, \ldots, k_s$, there exists a least positive integer $n = w(k_1, k_2, \ldots, k_s; s)$ such that whenever $[1, n] = \{1, 2, \ldots, n\}$ is $s$-colored (i.e., partitioned into $s$ sets), there is a $k_i$-term arithmetic progression with color $i$ for some $i$, $1 \leq i\leq s$. Similarly, Ramsey’s theorem has an associated ``threshold'' function $R(k_1, k_2, \ldots, k_s; s)$ (which we will not define here). The order of magnitude of $R(k, 3; 2)$ is known to be $\frac{k^2}{\log k}$ \cite{kim1995}, while the best known upper bound on $R(k, m; 2)$ is fairly close to the best known lower bound. In contrast, the order of magnitude of $w(k, 3; 2)$ is not known, and the best known lower and upper bounds on $w(k, k; 2)$ are \[ (k-1)2^{(k-1)} \leq w(k,k;2) < 2^{2^{2^{2^{2^{(k+9)}}}}}, \] the lower bound known only when $k-1$ is prime. The lower bound is due to Berlekamp \cite{berlekamp1968} and the upper bound is a celebrated result of Gowers \cite{gowers2001}, which answered a long-standing question of Ron Graham. Graham currently offers 1000 USD for a proof or disproof of $w(k,k; 2) < 2^{k^2}$ \cite{chung+erdos+graham2002}. Several other open problems are stated in \cite{landman+robertson2004}. Recently, there have been some further breakthroughs in the study of the van der Waerden function $w(k, m; 2)$. One was the amazing calculation that $w(6,6;2) = 1132$ by Kouril \cite{kouril2006}, extending the list of previously known values $w(3, 3; 2) = 9$, $w(4, 4; 2) = 35$, and $w(5, 5; 2) = 178$. A list of other known exact values of $w(k, m; 2)$ appears in \cite{landman+robertson+culver2005}. Improved lower bounds on several specific values of $w(k, k; s)$ are given in \cite{dransfield+liu+marek+truszczynski2004} and \cite{herwig+heule+vanlambalgen+vanmaaren2007}. In another direction, Graham \cite{graham2006} gives an elegant proof that if one defines $w_1(k, 3)$ to be the least $n$ such that every 2-coloring of $[1, n]$ gives either $k$ consecutive integers in the first color or a 3-term arithmetic progression in the second color, then \[ k^{c\log k} < w_1(k,3) < k^{dk^2}, \] for suitable constants $c,d>0$. This immediately gives $w(k,3;2 k^{(2-o(1))}$. Although this may seem weak, we do know that $w(k, 3; 2) < k^2$ for $5\leq k\leq16$ (i.e., for all known values of $w(k, 3; 2)$ with $k\geq 5$; see Table \ref{tab1}). More generally, we give a lower bound on $w(k, m; 2)$ for arbitrary fixed $m$. We also present a lower bound for the classical van der Waerden numbers $w(k,k, \ldots, k; s)$ that is a slight improvement over previously published bounds. In addition, we present an upper bound for $w(k, 4; 2)$ and an upper bound for $w(4, 4, \ldots, 4; s)$. \section{Upper and lower bounds for certain van der Waerden functions\label{s2}} We shall need several definitions, which we collect here. For positive integers $k$ and $n$, \[ r_k(n) = \max_{S\subseteq[1,n]} \{|S| : \text{ $S$ contains no $k$-term arithmetic progression } \}. \] For positive integers $k$ and $m$, denote by $\chi_k(m)$ the minimum number of colors required to color $[1, m]$ so that there is no monochromatic $k$-term arithmetic progression. The function $w_1(k, 3)$ has been defined in Section \ref{s1}. Similarly, we define $w_1(k, 4)$ to be the least $n$ such that every 2-coloring of $[1, n]$ has either $k$ consecutive integers in the first color or a 4-term arithmetic progression in the second color. We begin with an upper bound for $w_1(k, 4)$. The proof is essentially the same as the proof given by Graham \cite{graham2006} of an upper bound for $w_1(k, 3)$. For completeness, we include the proof here. We will make use of a recent result of Green and Tao \cite{green+tao}, who showed that for some constant $c > 0$, \begin{equation} r_4(n) < ne^{-c\sqrt{\log\log n}} \label{eq1} \end{equation} for all $n\geq3$. \begin{prop} There exists a constant $c>0$ such that $w_1(k,4) < e^{k^{c\log k}}$ for all $k\geq2$.\end{prop} \begin{proof} Suppose we have a 2-coloring of $[1, n]$ (assume $n\geq4$) with no 4-term arithmetic progression of the second color and no $k$ consecutive integers of the first color. Let $t_1 < t_2 < \cdots < t_m$ be the integers of the second color. Hence, $m < r_4 (n)$. Let us define $t_0 = 0$ and $t_{m+1} = n$. Then there must be some $i$, $1\leq i\leq m$, such that \[ t_{i+1} - t_i > \frac{n}{2r_4(n)}. \] (Otherwise, using $r_4(n) \geq3$, we would have $n=\sum_{i=0}^m(t_{i+1}-t_i)\leq \frac{n(m+1)}{2r_4(n)} \leq \frac{n(r_4(n)+1)}{2r_4(n)} \leq \frac{n}2 + \frac{n}6$.) Using \eqref{eq1}, we now have an $i$ with \[ t_{i+1} - t_i > \frac{n}{2r_4(n)} > \frac12e^{c\sqrt{\log\log n}}. \] If $n\geq e^{k^{d\log k}}$, $d = c^{-2}$, then $\frac12e^{c\sqrt{\log\log n}}\geq k$ and we have $k$ consecutive integers of the first color, a contradiction. Hence, $n < e^{k^{d\log k}}$ and we are done.\end{proof} Clearly $w(k,4;2) \leq w_1(k,4)$. Consequently, we have the following result. \begin{corl}\label{c2} There exists a constant $d > 0$ such that $w(k, 4; 2) < e^{k^{d \log k}}$ for all $k\geq 2$.\end{corl} Using Green and Tao's result, it is not difficult to obtain an upper bound for $w(4, 4, \ldots, 4; s)$. \begin{prop}\label{p3} There exists a constant $d > 0$ such that $w(4, 4, \ldots, 4; s) < e^{s^{d\log s}}$ for all $s\geq 2$.\end{prop} \begin{proof}Consider a $\chi_4 (m)$-coloring of $[1, m]$ for which there is no monochromatic 4-term arithmetic progression. Some color must be used at least $\frac{m}{\chi_4(m)}$ times, and hence $\frac{m}{\chi_4(m)} \leq r_4(m)$ so that $\frac{m}{r_4(m)} \leq \chi_4(m)$. Let $c > 0$ be such that \eqref{eq1} holds for all $n\geq3$, and let $m = e^{s^{d\log s}}$, where $d = c^{-2}$. Then $\chi_4(m) \geq \frac{m}{r_4(m)} > e^{c\sqrt{\log\log m}} = s$. This means that every $s$-coloring of $[1,m]$ has a monochromatic 4-term arithmetic progression. Since $m = e^{s^{d\log s}}$, the proof is complete.\end{proof} It is interesting that the bounds in Corollary \ref{c2} and Proposition \ref{p3} have the same form. The following theorem gives a lower bound on $w(k, k, \ldots, k; s)$. It is deduced without too much difficulty from the Symmetric Hypergraph Theorem as it appears in \cite{graham+rothschild+spencer1990}, combined with an old result of Rankin \cite{rankin1961}. To the best of our knowledge it has not appeared in print before, even though it is better, for large $s$, than the standard lower bound $\frac{cs^k}{k}(1 + o(1))$ (see \cite{graham+rothschild+spencer1990}), as well as the lower bounds $s^{k+1} - \sqrt{c(k + 1)\log(k + 1)}$ and $\frac{ks^k}{e(k+1)^2}$ due to Erd\H{o}s and Rado \cite{erdos+rado1952}, and Everts \cite{everts1977}, respectively. We give the proof in some detail. The proof makes use of the following facts: \begin{equation} \chi_k(n) < \frac{2n\log n}{r_k(n)}(1 + o(1)), \label{eq2}\end{equation} which appears in \cite{graham+rothschild+spencer1990} as a consequence of the Symmetric Hypergraph Theorem; and \begin{equation} r_k(n) > ne^{-c(\log n)^{\frac1{\floor{\log_2k}+1}}}, \label{eq3}\end{equation} which, for some constant $c > 0$, holds for all $n \geq3$ (this appears in \cite{rankin1961}). \begin{thrm}\label{t4} Let $k\geq3$ be fixed, and let $z=\floor{\log_2k}$. There exists a constant $d > 0$ such that $w(k, k,\ldots, k; s) > s^{d(\log s)^z}$ for all sufficiently large $s$.\end{thrm} \begin{proof}We make use of the observation that for positive integers $s$ and $m$, if $s\geq\chi_k (m)$, then $w(k, k,\ldots, k; s) > m$, which is clear from the definitions. For large enough $m$, \eqref{eq2} gives \begin{equation}\label{eq4} \chi_k(m) < \frac{2m\log m}{r_k(m)}\left(1 + \frac12\right) = \frac{3m\log m}{r_k(m)}. \end{equation} Now let $d = \left(\frac1{2c}\right)^{z+1}$, where $c$ is from \eqref{eq3}, and let $m = s^{d(\log s)^z}$, where $s$ is large enough so that \eqref{eq4} holds. By \eqref{eq3}, noting that $\log m = d(\log s)^{z+1} = \left(\frac{\log s}{2c}\right)^{z+1}$, we have \[ \frac{m}{r_k(m)} < e^{c(\log m)^{\frac1{z+1}}} = e^{c\cdot\frac{\log s}{2c}} = \sqrt{s}. \] Therefore, \[ \frac{3m\log m}{r_k(m)} < 3d\sqrt{s}(\log s)^{z+1} < s \] for sufficiently large $s$. Thus, for sufficiently large $s$, \[ \chi_k(m) < \frac{3m\log m}{r_k(m)} < s. \] According to the observation at the beginning of the proof, this implies that $w(k, k, \ldots, k; s) > m = s^{d(\log s)^z}$, as required.\end{proof} We now give a lower bound on $w(k, m; 2)$. We make use of the Lov\'asz Local Lemma (see \cite{graham+rothschild+spencer1990} for a proof), which will be implicitly stated in the proof. \begin{thrm}\label{t5} Let $m\geq3$ be fixed. Then for all sufficiently large $k$, \[ w(k,m;2) > k^{m-1-\frac1{\log\log k}}. \] \end{thrm} \begin{proof} Given $m$, choose $k>m$ large enough so that \begin{equation}\label{eq5} k^{\frac1{2m\log\log k}} > \left(m - \frac1{2\log\log k}\right)\log k \end{equation} and \begin{equation}\label{eq6} 6 < \frac{\log k}{\log\log k}. \end{equation} Next, let $n = \floor{k^{m-1-\frac1{\log\log k}}}$. To prove the theorem, we will show that there exists a (red, blue)-coloring of $[1, n]$ for which there is no red $k$-term arithmetic progression and no blue $m$-term arithmetic progression. For the purpose of using the Lov\'asz Local Lemma, randomly color $[1, n]$ in the following way. For each $i \in [1, n]$, color $i$ red with probability $p = 1 - k^{\alpha-1}$ where \[ \alpha := \frac1{2m\log\log k}, \] and color it blue with probability $1 - p$. Let $\mathcal{P}$ be any $k$-term arithmetic progression. Then, since $1+x \leq e^x$, the probability that $\mathcal{P}$ is red is \[ p^k = (1 - k^{\alpha-1})^k \leq \left(e^{-k^{\alpha-1}}\right)^k = e^{-k^\alpha}. \] Hence, applying \eqref{eq5}, we have \[ p^k < \left(\frac1e\right)^{\left(m - \frac1{2\log\log k}\right)\log k} = \frac1{k^{m-\frac1{2\log\log k}}}. \] Also, for any $m$-term arithmetic progression $\mathcal{Q}$, the probability that $\mathcal{Q}$ is blue is \[ (1 - p)^m = (k^{\alpha-1})^m = \frac1{k^{m-\frac1{2\log\log k}}}. \] Now let $\mathcal{P}_1, \mathcal{P}_2, \ldots, \mathcal{P}_t$ be all of the arithmetic progressions in $[1, n]$ with length $k$ or $m$. So that we may apply the Lov\'asz Local Lemma, we form the ``dependency graph'' $G$ by setting $V(G) = \{\mathcal{P}_1, \mathcal{P}_2, \ldots, \mathcal{P}_t\}$ and $E(G) = \{\{\mathcal{P}_i, \mathcal{P}_j\}: i = j, \mathcal{P}_i \cap \mathcal{P}_j \neq \varnothing\}$. For each $\mathcal{P}_i \in V(G)$, let $d(\mathcal{P}_i)$ denote the degree of the vertex $\mathcal{P}_i$ in $G$, i.e., $|\{e \in E(G): \mathcal{P}_i \in e\}|$. We now estimate $d(\mathcal{P}_i)$ from above. Let $x\in [1, n]$. The number of $k$-term arithmetic progressions $\mathcal{P}$ in $[1, n]$ that contain $x$ is bounded above by $k\cdot\frac{n}{k-1}$, since there are $k$ positions that $x$ may occupy in $\mathcal{P}$ and since the gap size of $\mathcal{P}$ cannot exceed $\frac{n}{k-1}$. Similarly, the number of $m$-term arithmetic progressions $\mathcal{Q}$ in $[1, n]$ that contain $x$ is bounded above by $m\cdot\frac{n}{m-1}$. Let $\mathcal{P}_i$ be any $k$-term arithmetic progression contained in $[1, n]$. The total number of $k$-term arithmetic progressions $\mathcal{P}$ and $m$-term arithmetic progressions $\mathcal{Q}$ in $[1, n]$ that may have nonempty intersection with $\mathcal{P}_i$ is bounded above by \begin{equation}\label{eq7} k\left(k\cdot\frac{n}{k-1} + m\cdot\frac{n}{m-1}\right) < kn\left(2 + \frac2{m-1}\right), \end{equation} since $k > m$. Thus, $d(\mathcal{P}_i) < kn(2 + \frac2{m-1})$ when $|\mathcal{P}_i| = k$. Likewise, $d(\mathcal{P}_i) < mn(2 + \frac2{m-1})$ when $|\mathcal{P}_i | = m$. Thus, for all vertices $\mathcal{P}_i$ of $G$, we have $d(\mathcal{P}_i) < kn(2 + \frac2{m-1})$. To finish setting up the hypotheses for the Lov'asz Local Lemma, we let $X_i$ denote the event that the arithmetic progression $\mathcal{P}_i$ is red if $|\mathcal{P}_i| = k$, or blue if $|\mathcal{P}_i| = m$, and we let $d = \max_{1\leq \leq t} d(\mathcal{P}_i)$. We have seen above that for all $i$, $1\leq i\leq t$, the probability that $X_i$ occurs is at most \[ q := \frac1{k^{m-\frac1{2\log\log k}}}, \] while from \eqref{eq7} we have $d < 2kn(1 + \frac1{m-1})$. We are now ready to apply the Lov\'asz Local Lemma, which says that in these circumstances, if the condition $eq(d + 1) < 1$ is satisfied, then there is a (red, blue)-coloring of $[1, n]$ such that no event $X_i$ occurs, i.e., such that there is no red $k$-term arithmetic progression and no blue $m$-term arithmetic progression. This will imply \[ w(k,m;2) > n = k^{m-1-\frac1{\log\log k}}, \] as desired. Thus, the proof will be complete when we verify that $eq(d + 1) < 1$. Using $m\geq3$, we have $d < 3kn$, so that $d + 1 < 3kn + 1 < e^2kn$. Hence, it is sufficient to verify that \begin{equation} e^3qkn < 1. \label{eq8} \end{equation} Since $q = \frac1{k^{m-\frac1{2\log\log k}}}$ and $n\leq k^{m-1-\frac1{\log\log k}}$, inequality \eqref{eq8} may be reduced to \eqref{eq6}, and the proof is now complete.\end{proof} \begin{rmrk} As long as $k>e^{m^6}$, the inequality of Theorem \ref{t5} holds. To show this, we need only to show that conditions \eqref{eq5} and \eqref{eq6} hold if $k>e^{m^6}$. That \eqref{eq6} holds is obvious. For \eqref{eq5}, it suffices to have $k^{\frac1{2m\log\log k}} > m\log k$; that is $\log k > 2m\log \log k(\log m + \log\log k)$. When $k\geq e^{m^6}$, we have $2m\log\log k(\log m + \log\log k)\leq 2(\log k)^{1/6}\log\log k(\frac16\log\log k + \log\log k) = \frac73(\log k)^{1/6}(\log\log k)^2$. Since $(\log \log k) < (\log k)^{7/20}$ for $k\geq e^{m^6}$ we have $2m\log\log k(\log m + \log\log k)\leq \frac73 (\log k)^{13/15}$. Finally, since $(\log k)^{2/15}\geq\frac73$ for $k\geq e^{m^6}$, condition \eqref{eq5} is satisfied.\end{rmrk} We end with a table of computed values. These were all computed with a standard backtrack algorithm except for $w(14, 3; 2)$, $w(15, 3; 2)$, and $w(16, 3; 2)$, which are due to Michal Kouril \cite{kouril2007}. The values $w(k, 3; 2)$, $k\leq12$, appeared previously in \cite{landman+robertson+culver2005}. \begin{table}\label{tab1} \caption{Small values of $w(k,3)$ and $w_1(k,3)$} \begin{tabular}{llllllllllllllll} \hline k & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 \\ \hline $w(k,3;2)$ & 6 & 9 & 18 & 22 & 32 & 46 & 58 & 77 & 97 & 114 & 135 & 160 & 186 & 218 & 238 \\ $w_1(k,3)$ & 9 & 23 & 34 & 73 & 113 & 193 & ? & ? & ? & ? & ? & ? & ? & ? & ? \\ \hline \end{tabular}\end{table} \bibliographystyle{amsplain} \bibliography{tom-all} \end{document}