Erdős Problem #138
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (not automatically the live result).
Subject areas: additive combinatorics.
Read this status correctly
The status above is reproduced from GCL's immutable external-catalogue snapshot. It is not a new claim of current mathematical resolution, a source-semantic review, an independent proof check, or GCL certification. A published proof and a GCL replay are separate events.
The question in plain language
Let \(W_2(k)\) be the smallest \(N\) for which every two-colouring of \(\{1,\ldots,N\}\) contains a monochromatic arithmetic progression of length \(k\). Erdős #138 asks whether
Equivalently, does \(W_2(k)\) eventually exceed \(C^k\) for every fixed \(C>1\)? This is much stronger than saying van der Waerden numbers are exponentially large, and the full limit is stronger than a limsup claim.
A small example
The two-colour van der Waerden number \(W_2(3)=9\): every binary colouring of nine consecutive integers contains a monochromatic three-term progression, whereas some colouring of eight avoids one. A distinct three-colour example is
which avoids monochromatic three-term progressions on nine positions. Yet merging its three colours down to two in any of the eight possible binary relabellings creates such a progression. The GCL audit checked all 16 candidate progressions and all relabellings. A result for three colours therefore does not automatically give one for two.
What is known
Berlekamp's 1968 construction gives a lower bound of the form \(W_2(p+1)\ge p\,2^p\) for prime \(p\). This is an exponential-scale bound on a subsequence, not proof of superexponential growth. Later work concerns stronger multi-colour variants; a proof that \(W_3(k)\) grows superexponentially does not by itself settle the two-colour question.
For \(r,s\ge2\), a useful composition inequality is
It follows by viewing a colour from an alphabet with \(rs\) possibilities as a pair, first finding a progression monochromatic in its first coordinate, then a subprogression monochromatic in the second. The inequality places the larger-colour quantity below an iterate; it does not provide the missing lower bound on \(W_2(k)\).
GCL's current state
Source audit #1407 checks the pinned formal statement, finite examples and the colour-composition lemma. It notes a particularly important transcription error: an adjacent formal-source description prints a tower \(p^{2^p}\) whereas the actual auxiliary theorem is the product \(p\,2^p\). The historical DOI and source-volume discrepancies in earlier returns are also corrected by this audit. None is a kernel-certified proof of the headline.
What remains
Find genuinely superexponential lower bounds for the two-colour quantity with sufficiently uniform control over all large \(k\), or refute the proposed full-limit divergence. Transfers that apply only to more colours or an iterated argument leave a substantive gap.
Sources and claim boundaries
- Erdős Problems #138, history.
- Berlekamp (1968), publisher article, Canadian Mathematical Bulletin 11, 409–414. The correct lower bound uses multiplication, not a tower.
- Erdős (1980), original author archive, Annals of Discrete Mathematics 6, 89–115. Some original full-limit versus limsup wording remains a documented source-normalization boundary.
- GCL source audit #1407: finite checks and statement reconciliation, not a proof of the global conjecture.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1407 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: FIRST_RECONNAISSANCE_TRANCHE.
- Formal-statement coverage: A provider statement was included in the pinned snapshot. Presence does not mean the statement or proof has been checked.
- External mathematical status: consult current problem page and its dated bibliography.