Skip to content

Erdős Problem #211

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

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

Suppose \(n\) distinct points lie in the real plane and no line contains more than \(n-k\) of them, where \(1\le k<n\). Erdős asked whether these points must determine at least a constant multiple of \(kn\) distinct lines:

\[ \#\{\text{lines through at least two points}\}\gg kn. \]

The lines counted here need at least two points, unlike #210, which counts exactly two. If almost all points lie on one line, the parameter \(k\) measures how far the configuration is from that degeneracy.

A small example

Take \(n-1\) points on the \(x\) axis and one point off the axis. The maximum collinearity is \(n-1\), so \(k=1\). The off-axis point determines \(n-1\) distinct lines with the on-axis points, together with the \(x\) axis itself: exactly \(n\) distinct lines. This realizes order \(kn\) when \(k=1\).

By contrast, if no three points are collinear, each of the \(\binom n2\) point pairs defines a distinct line, matching order \(n^2\) for \(k\) close to \(n\).

What is known

PROVED by József Beck and independently by Endre Szemerédi and William Trotter, both in 1983. Their incidence-geometric results show that an absolute constant \(c>0\) satisfies

\[ \#\{\text{spanned lines}\}\ge ckn \]

subject to the maximum-collinearity hypothesis. For \(2n\) points with at most \(n\) on any line, the result yields quadratically many distinct lines.

Erdős speculated about the sharper coefficient \((1+o(1))kn/6\), but identified the possibility as optimistic. The sixth-factor is constrained by configurations with about \(n^2/6\) three-point lines due to Burr, Grünbaum and Sloane and Füredi–Palásti. The order-of-magnitude theorem is settled; the historical coefficient speculation should not be presented as proved.

GCL's current state

Pinned and maintained Erdős #211 mark the principal claim PROVED. Original issue #1480. The 1983 provenance is established by the catalogue; full proof details and optimal leading constants were not independently audited. The pinned formal provider has no statement file.

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 enumerates spanned lines for rational-coordinate point configurations with specified maximum collinearity, including one point off a line of \(n-1\) vertices and a set with no three collinear. Acceptance: confirm the exact counts \(n\) and \(\binom n2\), normalize lines by rational coefficients, and verify the threshold \(n-k\) exactly. Stop before inferring an absolute constant from finite examples.

Sources and claim boundaries

No new point-line incidence theorem, independently proved optimal coefficient or editorial admission is claimed.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #1480 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
  • GCL triage: OUTSIDE_STRICT_OPEN_TRIAGE.
  • Formal-statement coverage: No statement was confirmed in GCL's pinned formal-provider 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