Skip to content

Erdős Problem #188

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (not automatically the live result).
Subject areas: geometry, ramsey theory.

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

Colour every point of the Euclidean plane red or blue, subject to the restriction that no two red points have distance exactly one. Erdős and Graham asked how long a unit-spaced blue arithmetic progression can be avoided, where a progression of length \(k\) consists of \(k\) collinear blue points

\[ x,\ x+v,\ldots,x+(k-1)v,\qquad |v|=1. \]

The currently formulated question asks for the smallest length \(k\) that is unavoidable in every admissible colouring. A progression with merely some arbitrary nonzero step is a different statement.

A small example

If an admissible colouring makes a point red, every point of the unit circle around it must be blue. On a horizontal line, red points can never be adjacent by unit spacing. This yields many blue points, but the absence of unit-spaced blue runs of a specified length is a two-dimensional constraint; checking one line alone is insufficient.

The colour of every point in the plane matters. A finite grid experiment tests only candidate restrictions; it cannot prove that all entire-plane colourings must exhibit a particular blue progression.

What is known

The unit-step problem remains OPEN. Erdős, Graham, Montgomery, Rothschild, Spencer and Straus (1975) showed the threshold is at least five; Tsaturian (2017) improved the bound to at least six, through constructions avoiding shorter blue runs. Erdős and Graham conjectured a very large finite upper bound, informally around ten million, but the maintained source explicitly notes that they offered no proof.

A significant statement-capture defect remains: the historical Erdős–Graham papers did not explicitly restrict the common difference of the blue progression to unit length. Noga Alon observed that with arbitrary positive step, the colouring problem has no analogous finite avoidance threshold. Restricting a line to integer points, red cannot appear at neighbouring integers, so sufficiently structured blue sets yield arbitrarily long progressions by van der Waerden's theorem. The source now presents the unit-step formulation as the likely intended one, not a verbatim historical quotation. This needs a semantic comparison to the pinned provider statement.

GCL's current state

The pinned and maintained #188, last edited October 2025, label the unit-step problem OPEN. Original issue: #1457. The locked Formal Conjectures provider includes 188.lean, but its exact step and quantifier definitions require a fidelity replay against the originals.

The original issue contains an authenticated RESULT/1 source report. This is unadjudicated source evidence only, not independent mathematical certification or editorial admission.

What remains

A bounded task reads the frozen 188.lean statement and tests whether unit Euclidean distance is imposed on the red forbidden pairs and on the blue common difference. Enumerate colourings of finite rational grids under both interpretations and exhibit where their constraints differ. Acceptance: exact source-commit comparison and a finite countermodel separating the two predicates where available. Stop at semantic verification; finite computations do not settle the whole-plane question.

Sources and claim boundaries

The unit-step restriction is a qualified source interpretation. No new plane-colouring theorem, independent proof replay or editorial admission is claimed.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #1457 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
  • GCL triage: PROTECTED_READY_BACKLOG.
  • 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