Skip to content

Erdős Problem #98

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (not automatically the live result).
Subject areas: geometry, 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

How many distinct distances must \(n\) points in the plane determine if they are in general position in the following strong sense: no three are collinear and no four lie on one circle? Write \(h(n)\) for the largest lower bound guaranteed for every such set.

Erdős #98 asks whether

\[ \frac{h(n)}{n}\longrightarrow\infty. \]

It is not enough to exhibit individual point sets with many distances. The conjecture claims a superlinear number of distances in every sufficiently large configuration satisfying both restrictions.

A small example

Take the four points \((i,i^2)\) with \(i=1,2,3,4\). They are not collinear three at a time: a straight line intersects the parabola \(y=x^2\) in at most two points. Nor are they concyclic: substituting \(y=x^2\) into an arbitrary circle equation produces a monic quartic whose cubic coefficient is zero. Four positive distinct roots would have a positive sum, contradicting Vieta's formula.

The same proof gives, for any \(n\), a concrete integer-coordinate family \((i,i^2)\), \(1\le i\le n\), with neither three collinear nor four concyclic. For indices \(i\ne j\), the squared distance is exactly

\[ d_{ij}^2=(i-j)^2\bigl[1+(i+j)^2\bigr]. \]

This is a useful exact test family, not a sharp extremal construction.

What is known

The conjecture remains OPEN. The maintained Erdős #98 attributes a construction with fewer than \(n^{\log_2 3}\) distinct distances to Pach, and a stronger upper construction of order

\[ n\exp\bigl(C\sqrt{\log n}\bigr) \]

to Erdős, Füredi, Pach and Ruzsa. Their primary paper The grid revisited, Discrete Mathematics 111 (1993), 189–196, explicitly states in its published abstract that planar general-position sets can have \(o(n^{1+\varepsilon})\) distances for every fixed \(\varepsilon>0\). These are upper examples for the minimum \(h(n)\), not lower bounds proving superlinearity.

A simple elementary lower bound comes from the no-four-concyclic hypothesis. For any fixed distance, each point has at most three others at that distance, so its multiplicity among unordered pairs is at most \(3n/2\). As there are \(\binom n2\) pairs, at least \((n-1)/3\) distinct distances are needed. This is still only linear.

GCL's current state

The pinned 2025 catalogue and maintained #98 classify it as OPEN. The original issue is #1367. The original Erdős–Füredi–Pach–Ruzsa abstract and exact general-position assumptions were checked; the full 1993 construction has not been independently rebuilt.

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 formalize the Vieta argument for the parabola example and the degree-three equal-distance incidence bound. Acceptance: for each \(n\le10\), enumerate the exact squared distances \(d_{ij}^2\), verify no collinear triples or concyclic quadruples, and check the lower bound \((n-1)/3\) for every input. Stop without inferring \(h(n)/n\to\infty\) from finite samples.

Sources and claim boundaries

No new superlinear universal lower bound, full original-proof verification or editorial admission is claimed.

Catalogue and evidence provenance

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