Skip to content

Erdős Problem #95

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

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 an arbitrary configuration of \(n\) distinct points in the plane, with no convexity requirement. For each positive distance \(u\), let \(f(u)\) be the number of unordered point pairs separated by \(u\). Erdős #95 asks whether, for every fixed \(\varepsilon>0\),

\[ \sum_u f(u)^2=O_\varepsilon(n^{3+\varepsilon}). \]

This is a distance-multiplicity bound, not merely the distinct-distance count. Unlike #94, collinear points are permitted. The constant may depend on \(\varepsilon\).

A small example

The four vertices of a unit square have four unit-distance pairs and two diagonal pairs. Therefore \(\sum f(u)^2=20\) and \(\sum f(u)=6\). These formulas are exact. If \(n\) points lie on an arithmetic progression on a straight line, the distance \(j\) between positions \(j\) apart occurs \(n-j\) times, so

\[ E(A)=\sum_{j=1}^{n-1}(n-j)^2 =\frac{n(n-1)(2n-1)}6. \]

Thus cubic growth cannot be replaced by a smaller power of \(n\) in the unrestricted problem.

What is known

PROVED. Guth and Katz's On the Erdős distinct distances problem in the plane, Annals of Mathematics 181 (2015), 155–190, yields the stronger bound

\[ E(A)=O(n^3\log n). \]

For every fixed \(\varepsilon>0\), \(\log n=O_\varepsilon(n^\varepsilon)\); hence the proven estimate implies Erdős's formulation. The original paper uses the Elekes–Sharir reduction to incidences of lines in three-dimensional space, polynomial partitioning and the geometry of ruled surfaces.

The same paper gives the related distinct-distance lower bound \(\gg n/\log n\). That latter estimate alone does not prove the cubic-logarithmic energy upper bound: the energy estimate is part of the finer incidence counting. The maintained catalogue previously attributed the convex-polygon case to Fishburn, but corrected the citation to Altman in February 2026.

GCL's current state

The pinned registry and maintained #95, edited 11 April 2026, mark this PROVED. The original source assignment is #1364. The primary Annals source and its publication information were verified. The full technical incidence proof and third-party formalization, if any, have not been independently kernel-replayed.

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 successor is to prove symbolically the exact collinear example above and verify the normalization \(f(j)=n-j\) for equally spaced points. Acceptance: compare a direct \(O(n^2)\) pair enumeration with the closed energy formula for \(2\le n\le20\); then prove \(\log n=o(n^\varepsilon)\) for every \(\varepsilon>0\). The technical Guth–Katz incidence bound remains an explicit imported theorem rather than a new proof.

Sources and claim boundaries

No new incidence bound, independent analytic proof or editorial admission is claimed.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #1364 — 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