Skip to content

Erdős Problem #104

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 \(n\) distinct points in the plane, consider circles of radius exactly one passing through at least three of them. How many distinct such circles can there be? Erdős #104 asks whether their maximum, \(U_3(n)\), is subquadratic:

\[ U_3(n)=o(n^2). \]

Two circles with different centres count separately, even when they contain overlapping groups of points. The radius and the requirement of at least three points are fixed; counting all possible radii is a different problem.

A small example

Three vertices of an equilateral triangle of side \(\sqrt3\) lie on a single circle of radius one: its circumradius is \(1\). A triangle with side one has circumradius \(1/\sqrt3\), not one, and therefore contributes no such unit circle through all three vertices.

A circle containing exactly \(t\ge3\) of the points contains \(\binom{t}{2}\) point pairs. Each pair at distance at most two lies on at most two circles of radius one. Double-count the incidences between point pairs and qualifying circles to obtain

\[ 3U_3(n)\le \sum_C\binom{|C\cap A|}{2} \le 2\binom n2, \qquad U_3(n)\le\frac{n(n-1)}3. \]

This improves the rough \(O(n^2)\) upper bound, but the result still has quadratic order.

What is known

The conjecture is OPEN. Erdős showed that a linear number of unit circles can occur. György Elekes, n points in the plane can determine n^{3/2} unit circles, Combinatorica (1984), gave configurations with \(\gg n^{3/2}\) qualifying circles. That reference is recorded in the maintained catalogue; the complete original construction was not independently reproduced for this audit.

Harborth and Mengersen's 1986 work clarified the constant in the elementary pair-incidence upper bound, \(n(n-1)/3\), rather than the weaker \(n(n-1)\) sometimes cited in Erdős's earlier accounts. Neither the lower exponent \(3/2\) nor this upper bound resolves \(o(n^2)\). The sharper \(O(n^{3/2})\) proposal is another, stronger question.

GCL's current state

The pinned catalogue and maintained Erdős #104 report OPEN. The original authenticated task is #1373. The elementary pair-incidence inequality has been independently checked, but the 1984 construction remains a bibliographic/source-replay task, not a new theorem or proof certification.

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

Implement a rational-coordinate checker that enumerates circles determined by triples, retains only circumcircles of squared radius one, and deduplicates by exact rational centres. Acceptance: for every input, each reported circle contains at least three points, and the count obeys \(3U_3(n)\le2\binom n2\). A fixture with one equilateral \(\sqrt3\) triangle must report one unit circle. Stop at finite verification; do not infer a subquadratic asymptotic bound.

Sources and claim boundaries

No new subquadratic theorem, primary 1984 proof certification or editorial admission is claimed.

Catalogue and evidence provenance

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