New lower bounds for van der Waerden numbers

Abstract

We show that there is a red-blue colouring of $[N]$ with no blue 3-term arithmetic progression and no red arithmetic progression of length $e^{C(\log N{)}^{3/4}(\log \log N{)}^{1/4}}$. Consequently, the two-colour van der Waerden number $w(3,k)$ is bounded below by $k^{b(k)}$, where $b(k)=c(\frac{\log k}{\log \log k}{)}^{1/3}$. Previously it had been speculated, supported by data, that $w(3,k)=O(k^2)$.

68 pages, accepted for publication in Forum of Math, Pi. Minor changes in the light of referee reports