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:
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
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
- Erdős #211, Beck 1983, Szemerédi–Trotter 1983, Burr–Grünbaum–Sloane 1974.
- Original issue #1480.
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.