Problem 138

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$ .

Source: erdosproblems.com/138

Additive combinatorics

Wiki page

Status

Open

No claim settles this problem.

OPEN, the site's label (page last edited 2 June 2026).

Be68: Berlekamp, E. R., A construction for partitions which avoid long arithmetic progressions. Canad. Math. Bull. 11 (1968), no. 3, 409-414.
Er80: Erdős, Paul, A survey of problems in combinatorial number theory. Ann. Discrete Math. (1980), 89-115.
Er81: Erdős, P., On the combinatorial problems which I would most like to see solved. Combinatorica (1981), 25-42.
FoHu26: J. Fox and Z. Hunter, Three-color van der Waerden numbers grow super-exponentially. arXiv:2606.02541 (2026).
Go01: Gowers, W. T., A new proof of Szemerédi's theorem. Geom. Funct. Anal. (2001), 465-588.
KoSh16: Kozik, Jakub and Shabanov, Dmitry, Improved algorithms for colorings of simple hypergraphs and applications. J. Combin. Theory Ser. B (2016), 312-332.

Problem 138

Status

Proof claims

Discussion