Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated Oct 8

Problem 138

claims/: The 5 claim pages of Problem 138, one per claimant's result; the problem's standing derives from them.

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

Formulation. The request to improve the bounds is read against the bounds the site's commentary cites as the current records: Berlekamp's $W(p+1)\ge p2^p$ for primes $p$ [Be68], Gowers's tower upper bound [Go01] and Kozik and Shabanov's $W(k)\gg2^k$ [KoSh16]. The site credits them as the known bounds and labels the problem OPEN. They are the baseline the request asks to beat, and they settle none of the questions the problem and its commentary pose. The formal-conjectures file linked under Formalization restates Berlekamp's and Gowers's bounds as solved variants (erdos_138.variants.prime, erdos_138.variants.upper) with no formal proof.

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

Source. erdosproblems.com/138, accessed 2026-09-04. Cite as: T. F. Bloom, Erdős Problem #138, https://www.erdosproblems.com/138.

References.

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

Formalization. Statement in formal-conjectures at its commit of 2026-10-06, linked, which states the question $W(k)^{1/k}\to\infty$ as erdos_138 with answer(sorry) and a sorry body and no formal_proof attribute; two of its variants, $W(k+1)-W(k)\to\infty$ and $W(k)/2^k\to\infty$ , are marked solved with formal_proof attributes pointing to Lean files outside the repository: a proof by the DeepMind prover agent (Tsoukalas et al., arXiv:2605.22763) in a fork of formal-conjectures, and a Lean proof derived from the Atlas proofs of facebookresearch/atlas-lean. Neither was built by this corpus, neither is a formalization of the accepted OpenAI claim under Claims, and each is linked from its claim page.

Claims. Five results have claim pages. The OpenAI mathematics release of 23 September 2026 proves $W_r(k)>k^{k\lfloor\log_2r\rfloor/100000}$ for every $r\ge2$ and every $k$ above an absolute threshold, so $W(k)^{1/k}\to\infty$ , the example question the problem names; the result is accepted as a partial claim on its claim page, on Lean declarations this corpus built and audited, and the open-ended request to improve the bounds stays open, with no upper bound touched. Four further results on the questions the site's entry records are claimed on their own pages: Campos, Fox and Schildkraut's lower bound $W(k)\ge(1-o(1))k2^{k-1}$ , which also gives $W(k)/2^k\to\infty$ (claim page); a Lean proof of $W(k)/2^k\to\infty$ in Meta's atlas-lean repository (claim page); the DeepMind prover agent's $W(k+1)\ge W(k)+k$ , which answers the difference question of [Er81] (claim page); and the notes that Nat Sothanaphan linked from the site's thread on 2026-04-10, written with GPT-5.4 Thinking, which refine the difference bound to $W_r(k+1)-W_r(k)\ge k+\min(k,F(r))+1$ for $r$ colors with an explicit $F(r)=\Theta(r\log\log r)$ ; at $r=2$ this is $W(k+1)-W(k)\ge k+1$ (claim page). The record bounds named under Formulation have no claim pages; the results that improve them do. Fox and Hunter's $W_3(k)^{1/k}\ge C^{\log_*k}$ [FoHu26] concerns three colors, not the problem's two-color number, and has no page.

Progress

Not yet compiled.

Known Results

Not yet compiled.

Linked library material

These entries are derived from explicit links on library pages. They are navigation only and do not by themselves record mathematical progress.

Linked from (31)

DeepMind's Lean proof that W(k+1) exceeds W(k) by at least k Sothanaphan's refinement of the van der Waerden difference bound Campos, Fox and Schildkraut's lower bound k 2^(k-1) for W(k)Meta's Atlas Lean proof that W(k) over 2 to the k tends to infinity OpenAI's superexponential lower bound for van der Waerden numbers problems/additive_combinatorics/E0138/claims Problem 190 Fox and Hunter's bound H(k) at least k to the (1-o(1))k log k Sumsets and Arithmetic Progressions Problem 176 OpenAI's superexponential van der Waerden bound rules out the case c = 1 Sumsets and Arithmetic Progressions additive_combinatorics/berlekamp_1968_construction_partitions_which_avoid_long_arithmetic Theorem 1 (p. 409): a Galois-field partition with no long progression, for prime-power k Theorem 2 (p. 410): W(2,t) > t 2^t for prime t additive_combinatorics/erdos_1979_old_new_problems_results_combinatorial_number additive_combinatorics/fox_2026_three_color_van_der_waerden_numbers additive_combinatorics/kozik_2016_improved_algorithms_colorings_simple_hypergraphs_applications Theorem 1 (p. 3): simple n-uniform hypergraphs with maximum edge degree at most α n r^(n-1) are r-colorable Theorem 2 (p. 3): W(n,r) ≥ β r^(n-1) for every r ≥ 2 and n ≥ 3 additive_combinatorics/openai_2026_quantitative_superexponential_bounds_van_der_waerden_numbers Corollary 7.3: log W_r(k)/(k log r) → ∞ uniformly in r, and log W_r(k)/log r → ∞ uniformly in k Theorem 1.1: W_r(k) > k^(ck⌊log₂ r⌋) with c = 10⁻⁵ for all r ≥ 2 and k ≥ K₀ distance_problems/graham_1994_recent_trends_euclidean_ramsey_theory Conjecture (p. 127): the two-color van der Waerden function is at most a tower of n twos ramsey_theory/beck_1980_remark_concerning_arithmetic_progressions ramsey_theory/brown_1999_monochromatic_arithmetic_progressions_large_differences ramsey_theory/green_2022_new_lower_bounds_van_der_waerden ramsey_theory/hunter_2022_improved_lower_bounds_van_der_waerden ramsey_theory/schoen_2021_subexponential_upper_bound_van_der_waerden set_systems/erdos_1981_combinatorial_problems_which_i_would_most

Graph