%%%% 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, Simon Fraser University, 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}