Skip to content

Erdős Problem #101

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

Take \(n\) points in the real plane with no five on one line. How many different straight lines can each contain exactly four of the points? Let \(M_4(n)\) be the maximum. Erdős #101 asks whether

\[ \lim_{n\to\infty}\frac{M_4(n)}{n^2}=0. \]

Thus the question is whether four-point-rich lines are subquadratic, uniformly over all admissible planar configurations. It does not say that only finitely many such lines can exist.

A small example

A four-point line uses \(\binom42=6\) point pairs. Since each distinct pair determines exactly one line, the simple counting bound is

\[ 6M_4(n)\le\binom n2,\qquad M_4(n)\le\frac{n(n-1)}{12}. \]

This is only \(O(n^2)\) and does not give the required \(o(n^2)\).

An exact 30-point construction in the GCL source audit starts with integer points \((x,y,z)\) satisfying \(x^2+y^2+z^2\in\{1,5\}\) and applies \((x,y,z)\mapsto(x+100z,y+10000z)\). Its checked geometry yields 12 four-point lines, with no five collinear. It is a finite illustration, not an asymptotic counterexample.

What is known

Solymosi and Stojaković, Many Collinear k-Tuples with no k+1 Collinear Points, Discrete & Computational Geometry 50 (2013), 811–820, arXiv:1107.0327, construct nearly quadratic numbers of lines with exactly \(k\) points for fixed \(k\ge4\). For \(k=4\) their lower bounds have exponent approaching 2, while still being consistent with \(M_4(n)=o(n^2)\). This rules out any fixed power-saving upper bound \(O(n^{2-\delta})\) with \(\delta>0\).

The original formulation in Erdős, Research problems, Periodica Mathematica Hungarica 15 (1984), Problem 36, covers all fixed \(k>3\) and also asks a separate growth-rate question; #101 isolates its four-point subquadratic question.

GCL's current state

Source audit #1370 reconciles the pinned formal statement, corrects older erroneous bibliographic identifiers for Solymosi–Stojaković, and provides a finite exact collinearity-preserving projection. It expressly rejects an unsupported attempt to exclude all algebraic-group constructions by a degree argument. The global asymptotic claim remains unproved in this record.

What remains

One must improve the universal quadratic bound to a quantity that is \(o(n^2)\) without contradicting constructions with \(n^{2-o(1)}\) rich lines. Abstract pair-counting and finite pictures cannot bridge that difference.

Sources and claim boundaries

Catalogue and evidence provenance

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