Does some vertex of a convex $n$-gon see at least $\lfloor n/2\rfloor$ distinct distances? (Erdős #982)
Statement
If $n$ distinct points in $\mathbb{R}^2$ form a convex polygon, must some vertex have at least $\lfloor n/2\rfloor$ different distances to the other vertices? Writing $f(n)$ for the largest number $m$ such that EVERY convex polygon on $n$ vertices has some vertex realizing at least $m$ distinct distances to the remaining vertices, the conjecture asserts $f(n)=\lfloor n/2\rfloor$. The regular $n$-gon shows $f(n)\le\lfloor n/2\rfloor$, so only the lower bound is at issue. A counterexample is an explicit convex polygon in which every single vertex realizes fewer than $\lfloor n/2\rfloor$ distinct distances to the other vertices.
Acceptance. FULLY RESOLVES: (a) a proof that every convex polygon on $n$ vertices has a vertex with at least $\lfloor n/2\rfloor$ distinct distances to the other vertices, for all $n$ — machine-checkable (Lean, building on the existing formal statement) preferred, else a complete written proof; or (b) a counterexample — an explicit convex polygon with exact (algebraic or rational) coordinates and an exact-arithmetic, machine-checkable verification that every vertex realizes fewer than $\lfloor n/2\rfloor$ distinct distances to the others. ADVANCES: (a) a proved lower bound $f(n)\ge cn-O(1)$ with $c$ strictly larger than the best constant stated in the background, with full proof; (b) certified exact values of $f(n)$ for specific small $n$ (proof that every convex $n$-gon has a vertex with $\ge\lfloor n/2\rfloor$ distinct distances for those $n$), with reproducible code or written argument; (c) a proof or refutation of the Bárány–Roldán-Pensado absolute-constant conjecture (some boundary point $p$ of any planar convex body has every circle centred at $p$ meeting the boundary in at most $C$ points for a universal $C$). Deliver the proof file, or the counterexample coordinates plus verification code, or the new bound with its proof.
Background
Conjectured by Erdős in 1946 [Er46b] and restated over the decades [Er75f, p.100; Er87b, p.175; ErFi94]; listed as open on erdosproblems.com/982 (fetched 2026-07-13, status 'falsifiable'). The conjectured extremal value $\lfloor n/2\rfloor$ is OEIS A004526. The lower-bound frontier has moved four times: Moser [Mo52] proved $f(n)\ge\lceil n/3\rceil$; Erdős and Fishburn [ErFi94] improved this to $f(n)\ge\lfloor n/3+1\rfloor$; Dumitrescu [Du06b] reached $f(n)\ge\lceil (13n-6)/36\rceil$; and Nivasch, Pach, Pinchasi, and Zerbib [NPPZ13] hold the current record $$f(n)\ge\left(\tfrac{13}{36}+\tfrac{1}{22701}\right)n-O(1),$$ still far from the conjectured $n/2$. Two natural strengthenings are dead: the conjecture would follow if some vertex had no three other vertices equidistant from it, but that is false (Danzer's construction — see the companion venue problem on Erdős #97); and Erdős's even stronger 1946 conjecture that every convex curve has a point $p$ with every circle centred at $p$ meeting the curve in at most $2$ points was refuted by Bárány and Roldán-Pensado [BaRo13], who observed the boundary of any acute triangle is a counterexample. Bárány and Roldán-Pensado did prove every planar convex body has a boundary point $p$ such that circles centred at $p$ meet the boundary in $O(1)$ points (constant depending on the body), and conjecture an absolute constant suffices. See also Erdős #93 (erdosproblems.com/93). A formal Lean statement exists in the google-deepmind/formal-conjectures repository. The attacker's tool: sharpening the combinatorial-geometric counting arguments behind the $13/36$-type bounds; on the computational side, certified exact values of $f(n)$ for small $n$ (numerical optimization over convex configurations followed by exact/symbolic certification) and searches for convex polygons where all vertices see unusually few distinct distances.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #982 (T. F. Bloom) | website |
| REF-02 | OEIS A004526 — integers repeated (floor(n/2), the conjectured extremal value) | website |
| REF-03 | Formalized statement of Erdős #982 (google-deepmind/formal-conjectures, Lean 4) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.