Lower Bounds on Some Van Der Waerden Numbers Based on Quadratic Residues

Abstract

The van der Waerden number $W(r,k)$ is the least integer $N$ such that every $r$-coloring of $\{1,2,\dots ,N\}$ contains a monochromatic arithmetic progression of length at least $k$. Rabung gave a method to obtain lower bounds on $W(2,k)$ based on quadratic residues, and performed computations on all primes no greater than $20117$. By improving the efficiency of the algorithm of Rabung, we perform the computation for all primes up to $6\times {10}^7$, and obtain lower bounds on $W(2,k)$ for $k$ between $11$ and $23$.