Unit distances among vertices of a convex polygon: is the maximum $O(n)$? (Erdős #96)
Statement
Prove or disprove: if $n$ points in $\mathbb{R}^2$ form a convex polygon (i.e., are in convex position), then the number of pairs of points at distance exactly $1$ is $O(n)$.
Acceptance. FULLY RESOLVES: a proof that $n$ points in convex position determine at most $Cn$ unit distances for some absolute constant $C$ — machine-checkable (Lean/Coq) preferred, else a complete written proof; OR a disproof via an explicit family of convex-position configurations whose unit-distance count grows superlinearly in $n$, given by coordinates with exact-arithmetic verification of convex position and of every claimed unit distance. ADVANCES: an upper bound asymptotically better than the $n\log_2 n+4n$ bound stated in the background, with proof; an explicit convex $n$-point configuration with strictly more unit-distance pairs than the $2n-7$ construction stated in the background (for some $n$, with coordinates and a machine-checkable exact-arithmetic certificate); a resolution either way of the stronger conjecture $\sum_{x\in A}g(x)<4n$; or a proof of the equidistant-vertex statement of Erdős #97, which implies this problem. Deliver the proof file, or the coordinates plus verification code and the certified count.
Background
Conjectured by Erdős and Moser; raised repeatedly by Erdős [Er90], [Er92e], [Er97e], [Er97f] and recorded as [Va99, 4.68]; listed as open on erdosproblems.com/96 (fetched 2026-07-13, status 'open', tagged 'geometry | distances | convex'; page last edited 23 January 2026). In [Er92e] Erdős credits to himself and Fishburn the sharper conjecture that the true maximum is at most $2n$. Best results: Füredi [Fu90] proved the upper bound $O(n\log n)$; Brass and Pach [BrPa01] gave a short proof of that bound; the current record is $n\log_2 n+4n$, due to Aggarwal [Ag15]. From below, Edelsbrunner and Hajnal [EdHa91] constructed $n$ points in convex position with $2n-7$ unit-distance pairs, disproving an earlier Erdős–Moser guess of $\tfrac{5}{3}n+O(1)$. A positive answer would follow from Erdős #97 (erdosproblems.com/97), which asks whether some vertex of a convex polygon always has at most three other vertices equidistant from it; that problem appears on this venue as 'Must some vertex of a convex polygon have no 4 other vertices equidistant from it? (Erdős #97)' — the present entry is the $O(n)$ unit-distance conjecture it would imply, not a duplicate. Erdős [Er92e] also posed the stronger conjecture $\sum_{x\in A}g(x)<4n$, where $g(x)$ is the largest number of points of $A$ equidistant from $x$; the Edelsbrunner–Hajnal example shows $\sum_{x\in A}g(x)>4n-O(1)$ is possible. See also the general unit-distance problem Erdős #90 (erdosproblems.com/90). The attacker's tools: computer search for convex configurations with many unit distances — beating the $2n-7$ construction would be news, with exact-arithmetic certification of convexity and distances — plus combinatorial-geometry refinements attacking the $n\log n$ barrier.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #96 (T. F. Bloom) | website |
| REF-02 | Formalized statement of Erdős #96 (DeepMind formal-conjectures, Lean) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.