Skip to content

Erdős Problem #102

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (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

Given a configuration of \(n\) distinct points in the plane, call a line rich if it contains at least four of those points. Fix a constant \(c>0\) and suppose the configuration determines at least \(cn^2\) distinct rich lines.

Erdős and Purdy's #102 asks whether this much incidence forces at least one line to contain more and more points as \(n\) grows. More precisely, if \(h_c(n)\) is the greatest lower bound on the maximum number of collinear points guaranteed under the hypothesis, must

\[ h_c(n)\longrightarrow\infty \]

for each feasible fixed \(c>0\)? The richness condition is four points per line, and the \(cn^2\) count concerns distinct lines, not incidences or point pairs.

A small example

Take four collinear points. They produce a single four-rich line, even though all six unordered pairs lie on it. Thus the number of point pairs is not the number of rich lines.

Each pair of distinct planar points determines a unique line. Since a four-rich line contains at least \(\binom42=6\) pairs, and different lines never share a pair, a configuration with \(L\) rich lines satisfies

\[ 6L\le\binom n2. \]

Consequently \(L\le n(n-1)/12\). In particular a fixed density \(c\ge1/12\) is impossible for any positive finite \(n\) under the literal \(L\ge cn^2\) hypothesis. Only feasible small positive \(c\) are relevant to the asymptotic problem; otherwise the implication is vacuous.

What is known

The intended question remains OPEN. The maintained Erdős #102 explicitly reports that even the guarantee \(h_c(n)\ge5\) is unknown in the interesting regime. The related #101 is a distinct, already-accepted catalogue entry and must not be confused with this problem.

The same maintained source describes a construction noted by Zach Hunter: high-dimensional grids have very many rich lines but no line with more than \(O_d(n^{1/d})\) points, and a generic projection into the plane can preserve the finite collinearity structure. This defeats an earlier suggested lower bound \(h_c(n)\gg_c\sqrt n\); it does not disprove unbounded growth of \(h_c(n)\). The precise density constants and projection-genericity conditions of the Hunter construction have not been independently written out as a complete proof.

GCL's current state

The pinned catalogue and the maintained problem page classify #102 OPEN. Its GCL source issue is #1371. The six-pairs-per-rich-line bound is independently checked. The full Hunter asymptotic construction and Erdős's original 1992 and 1995 papers remain source leads, not new GCL mathematical certifications.

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 verification task is to formalize \(6L\le\binom n2\) by assigning each unordered point pair to at most one line, with exactly six pairs already present on every four-rich line. Enumerate rational point configurations of limited size and count each distinct rich line once, by a primitive integer line-equation normalization. Acceptance: the four-collinear-point fixture reports one line, not six; the necessary \(c<1/12\) asymptotic restriction follows. Stop without inferring any growing lower bound on \(h_c(n)\).

Sources and claim boundaries

No proof of \(h_c(n)\to\infty\), independently verified Hunter construction or editorial admission is claimed.

Catalogue and evidence provenance

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