Problem 138 — Visual explainer (undergrad)
==========================================

Problem statement
---------------
Let the van der Waerden number $W(k)$ be such that whenever $N\geq W(k)$ and $\{1,\ldots,N\}$ is $2$-coloured there must exist a monochromatic $k$-term arithmetic progression. Improve the bounds for $W(k)$ - for example, prove that $W(k)^{1/k}\to \infty$.

Picture
-------
Number line picture of an arithmetic progression (equal spacing):

---o-----o-----o-----o-----o---
   a    a+d   a+2d  a+3d  a+4d

Conjecture / Task: what to look at
------------------------
- Restate the problem as: given the constraint, what asymptotic bound or
  structure must follow?
- Use the comments as benchmarks (best known bounds / constructions).

Context
-------
Area hint: additive combinatorics / additive number theory.

Benchmarks / known results (from comments)
----------------------------------------
- When $p$ is prime Berlekamp has proved $W(p+1)\geq p2^p$.
- Gowers has proved\[W(k) \leq 2^{2^{2^{2^{2^{k+9}}}}}.\]The best general
  lower bound is $W(k)\gg 2^k$, due to Kozik and Shabanov.
- In Erd\H{o}s further asks whether $W(k+1)/W(k)\to \infty$, or
  $W(k+1)-W(k)\to \infty$.
- In Erd\H{o}s asks whether $W(k)/2^k\to \infty$, and offers \$500 for a proof
  or disproof of $W(k)^{1/k}\to \infty$.