Skip to content

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

\[ \lim_{k\to\infty} W_2(k)^{1/k}=+\infty. \]

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

\[ 0,0,1,0,0,1,1,2,2, \]

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

\[ W_{rs}(k)\le W_r(W_s(k)). \]

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

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.

Back to catalogue · Compendium introduction