Bounds on Van der Waerden Numbers and Some Related Functions

For positive integers $s$ and $k_1,k_2,\mathrm{.}\mathrm{.}\mathrm{.},k_s$, let $w(k_1,k_2,\mathrm{.}\mathrm{.}\mathrm{.},k_s)$ be the minimum integer $n$ such that any $s$-coloring ${1,2,…,n} \to {1,2,…,s}$admitsa$k_i$-termarithmeticprogressionofcolor$i$forsome$i$,$1 \leq i \leq s$\mathrm{.}Inthecasewhen$k_1=k_2=…=k_s=k$wesimplywrite$w(k;s)$. That such a minimum integer exists follows from van der Waerden’s theorem on arithmetic progressions. In the present paper we give a lower bound for $w(k,m)$ for each fixed $m$. We include a table with values of $w(k,3)$ which match this lower bound closely for $5\le k\le 16$. We also give an upper bound for $w(k,4)$, an upper bound for $w(4;s)$, and a lower bound for $w(k;s)$ for an arbitrary fixed $k$. We discuss a number of other functions that are closely related to the van der Waerden function.