A new lower bound for two-color van der Waerden numbers

Abstract

The van der Waerden number $w(k)$ is the smallest positive integer $N$ such that every two-coloring of $\{1,2,\dots ,N\}$ contains a monochromatic $k$-term arithmetic progression. We prove that $w(k)\ge (1-o(1))k{2}^{k-1}$ holds for all positive integers $k$. This verifies a conjecture of Erdős. In 1968, Berlekamp proved the same result when $k-1$ is prime. The coloring for general $k$ can be viewed as a product of Berlekamp's colorings for various primes. It was found by ChatGPT 5.6 Sol Pro.

arXiv comment5 pages