Skip to content

Erdős Problem #1090

Editorial depth: Authored explanatory DRAFT — NOT editorially accepted.
Snapshot classification: proved (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.

UNACCEPTED DRAFT — mathematical editorial review pending

This material is a provisional, source-qualified manuscript published for line-by-line scrutiny and real HTML/LaTeX testing. It has NOT received separate GCL editorial acceptance or independent mathematical certification. Its presence on this website is not evidence of a solution, reviewed coverage, or final publication.

Review the underlying draft on GitHub.

The question in plain language

For every integer \(k\ge3\), is there a finite collection of points in the plane with this property: no matter how the points are coloured red or blue, some straight line contains at least \(k\) of the points, and every point of the collection on that line is the same colour?

Erdős Problem #1090 is stronger than merely finding \(k\) same-colour points on one line. Extra points of the other colour would invalidate the requested line.

The answer is yes, using the Hales–Jewett theorem and a carefully chosen planar projection.

A small example

A combinatorial line in the discrete cube \(\{0,1,2\}^3\) consists of three strings obtained by varying the same symbol in one or more chosen coordinates. For example,

\[ (0,1,0),\quad(1,1,1),\quad(2,1,2) \]

form a line.

We independently checked a finite geometric illustration: map a string \((x,y,z)\) to

\[ L(x,y,z)=(x+7y+49z,\ x+13y+169z). \]

All 27 grid points have distinct images. Among the \(\binom{27}{3}=2925\) triples, exactly 49 are collinear in the original three-dimensional grid, and no additional triple becomes collinear under this projection.

This does not assert that dimension three is already large enough for the two-colour Hales–Jewett conclusion. It verifies the separate projection mechanism on a bounded example.

What is known

The Hales–Jewett theorem guarantees that a sufficiently high-dimensional discrete grid, under every two-colouring, contains a monochromatic combinatorial line.

The final geometric step matters. Given the finite grid \(B=\{0,\dots,k-1\}^N\), select a linear map \(L:\mathbb R^N\to\mathbb R^2\) injective on \(B\) and preserving every triple that is noncollinear in the original space. Such a map exists: each unwanted collision or new collinearity imposes a nonzero polynomial equation in the projection's matrix entries. A finite union of proper algebraic zero sets cannot cover all matrices.

A combinatorial line contains exactly \(k\) grid points on its affine support. Under the chosen projection, no additional grid point can lie on its planar image line, since doing so would introduce new collinearity with two of the original points. Thus the Hales–Jewett monochromatic line satisfies the entire strengthened conclusion.

The maintained catalogue attributes the \(k=3\) historical case to Graham and Selfridge, and Zach Hunter's general observation to generic projection. It also reports an external Lean proof of the strengthened statement.

GCL's current state

Authenticated source audit #2361 reconstructed the standard generic-projection reduction and tested the 27-point example.

The 2026 discussion identifies a previous formal statement that omitted the all-points-on-line condition, followed by a claimed corrected Lean proof. The frozen Lean source links an external theorem, but its own body contains an unproved placeholder.

This problem belongs to the mandatory 20-article critical sample. Source verification and independent Lean replay have not been completed.

What remains

Review Erdős's 1975 statement and the original Hales–Jewett proof interface. Compare the actual final external Lean theorem with the stronger literal quantifier, then kernel-check its exact dependency closure and conduct independent critical review. The standard mathematical reduction is not a new GCL theorem.

Sources and claim boundaries

Erdős Problem #1090; formal-statement discussion; frozen external Lean reference; authenticated audit #2361. Externally proved, not independently kernel-certified by GCL. Unaccepted draft; critical review pending.

Catalogue and evidence provenance

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