Improved lower bounds for van der Waerden numbers

Abstract

Recently, Ben Green proved that the two-color van der Waerden number $w(3,k)$ is bounded from below by $k^{b_0(k)}$ where $b_0(k)=c_0{\left(\frac{\log k}{\log \log k}\right)}^{1/3}$. We prove a new lower bound of $k^{b(k)}$ with $b(k)=\frac{c\log k}{\log \log k}$. This is done by modifying Green's argument, replacing a complicated result about random quadratic forms with an elementary probabilistic result.

24 pages, comments welcome! (miscellaneous typos corrected)