Distinct distances among vertices of a convex polyhedron in 3-space: at least $(1-o(1))n/2$? (Erdős #660)
Statement
Let $x_1,\ldots,x_n\in\mathbb{R}^3$ be the vertices of a convex polyhedron. Must the points determine at least $$(1-o(1))\frac{n}{2}$$ distinct distances? That is, must $|\{\|x_i-x_j\| : 1\leq i<j\leq n\}|\geq (1-o(1))\,n/2$?
Acceptance. FULLY RESOLVES: a proof that the vertex set of every convex polyhedron in $\mathbb{R}^3$ on $n$ vertices determines at least $(1-o(1))n/2$ distinct distances — machine-checkable (Lean/Coq) preferred, else a complete written proof; OR a disproof: an explicit infinite family of convex polyhedra whose $n$ vertices determine at most $cn$ distinct distances for some explicit constant $c<1/2$, given by exact coordinates with machine-checkable verification that all points are vertices of their convex hull and of the distinct-distance count. ADVANCES: a proven lower bound of the form $cn$ for any explicit constant $c>0$, or any lower bound strictly better than what published general-point-set distinct-distance bounds in $\mathbb{R}^3$ already give (state and cite the comparison bound); a rigorous proof of the $\gg n$ claim Erdős attributed to Altman; or a certified construction establishing the best-known upper bound on the extremal count, with exact-arithmetic verification. Deliver the proof file, or the coordinates plus verification code.
Background
Posed by Erdős [Er97e, p.531]; listed as open on erdosproblems.com/660 (fetched 2026-07-13, status 'open', tagged 'geometry | distances | convex'; page last edited 01 January 2026). The planar analogue is a theorem of Altman [Al63]: $n$ points in convex position in $\mathbb{R}^2$ always determine at least $n/2$ distinct distances (Erdős #93, erdosproblems.com/93). In [Er75f] Erdős asserts that Altman also proved that the vertices of a convex polyhedron determine $\gg n$ distinct distances, but he gives no reference and no such proof is known. Because Erdős's original wording does not pin down the exact intended statement, a solver should fix a precise reading (the one above) and flag any divergence from Erdős's original text. Related venue problems (distinct, not duplicates): Erdős #982 (some vertex of a convex $n$-gon seeing $\lfloor n/2\rfloor$ distinct distances) and Erdős #1082 (Szemerédi's conjecture for point sets with no 3 collinear). The attacker's tools: adapting Altman-style convexity arguments from the plane to $\mathbb{R}^3$; certified extremal constructions — explicit convex polyhedra with few distinct distances, with exact-arithmetic verification of convexity and of the distance multiset — to probe sharpness of the $n/2$ constant; even a first proven bound linear in $n$ would be a substantial advance.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #660 (T. F. Bloom) | website |
| REF-02 | Erdős Problem #93 (Altman's theorem: distinct distances in convex position in the plane) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.