Skip to content

Erdős Problem #96

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

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

Put \(n\) distinct points in strictly convex position in the Euclidean plane: they are all vertices of a convex polygon, with no three collinear. How many pairs of vertices can be exactly one unit apart?

Erdős and Moser conjectured that this number is at most \(Cn\) for some universal constant \(C\), independent of the polygon and \(n\). The present problem asks whether the maximum number of unit-distance unordered vertex pairs is \(O(n)\), and the sharper proposed bound is \(2n\).

A small example

The regular \(n\) gon can be rescaled to make its sides length one. This gives \(n\) unit-distance pairs. The number of edges of the polygon is always \(n\), but unit-distance pairs can also join nonconsecutive vertices: restricting attention to the boundary edges would answer the wrong question.

For a unit square, there are four unit-distance pairs (the four sides), and two diagonals of length \(\sqrt2\) do not count. This does not approach the best known lower-bound constructions.

What is known

The linear conjecture remains OPEN. Füredi proved a universal \(O(n\log n)\) upper bound in 1990. Amol Aggarwal's On unit distances in a convex polygon, Discrete Mathematics 338 (2015), 88–92, improves it to

\[ U(n)\le n\log_2 n+4n, \]

where \(U(n)\) denotes the maximum number of pairs at one fixed distance among vertices of a convex polygon. This is still superlinear by a logarithm.

Edelsbrunner and Hajnal's original 1991 paper, Journal of Combinatorial Theory A 56, 312–316, proves that for every \(n\ge4\) there is a convex polygon with \(2n-7\) unit-distance pairs. The primary publisher abstract was directly checked. Thus an older conjectured upper bound of \((5/3)n+O(1)\) is false; it does not refute the \(2n\) or \(O(n)\) versions.

Problem #97 proposes a local equal-radius degree restriction that would, through an induction argument, supply the desired linear upper bound; this conditional implication is not itself a solution.

GCL's current state

The maintained Erdős #96 and pinned catalogue mark it OPEN. Original GCL source issue #1365 requires bounded source work, not a new protected Solve launch. The 1991 and 2015 publisher records were inspected; complete arguments and the asserted exact coefficient for Aggarwal's result remain subject to a full primary-page proof audit.

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 computational test is to enumerate pairwise squared lengths of exact regular polygons for small \(n\), after normalizing the side length to one, then count all pairs at that length. Acceptance: for the unit square the count is exactly four, and each unordered pair contributes only once. Independently check the cardinality of the Edelsbrunner–Hajnal construction using their original geometric parameters. This is not a proof that every convex polygon has only \(O(n)\) unit pairs.

Sources and claim boundaries

No new universal linear upper bound, primary full-proof certification or editorial admission is claimed.

Catalogue and evidence provenance

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