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 \big( \frac{ \log k}{ \log\log k} \big)^{ 1/3}$. Previously it had been speculated, supported by data, that $w(3,k) = O(k^2)$.

Categories: math.CO math.NT

New lower bounds for van der Waerden numbers