Erdős Problem #94

FORMAL RESTATEMENT

Erdős #94; reconstruction of a known proof, 2026-09-23. Let $P$ be the $n$ vertices of a strictly convex polygon. For each positive distance $r$, let $f(r)$ count unordered pairs of vertices at distance $r$. Prove $\sum_r f(r)^2=O(n^3)$. We prove the explicit, more general estimate \[ \sum_r f(r)^2\leq\frac34n^2(n-1) \tag{1} \] whenever no three points of $P$ are collinear.

QUICK LITERATURE AND CONTEXT CHECK

The source labels this problem proved and attributes the general-position result to Lefmann and Thiele $1995$. The current discussion supplies the elementary isosceles-triangle argument. The following is a reconstruction of that known argument, with its counting conventions and constants checked; it is not a new resolution. Strict convexity implies the general-position hypothesis used here.

OBJECTIVE AND ATTACK PLAN

Replace each global distance multiplicity by the sum of its degrees at individual points. Cauchy--Schwarz then reduces the problem to counting isosceles triangles. Their apices lie on perpendicular bisectors, so the restriction on collinear triples gives a uniform bound.

WORK

For $x\in P$ put $d_r(x)=|\{y\in P\setminus\{x\}:|x-y|=r\}|$. Each edge has two endpoints, hence $\sum_xd_r(x)=2f(r)$. Thus \[ 4f(r)^2\leq n\sum_xd_r(x)^2. \tag{2} \] Let $I$ count pairs consisting of an apex $x$ and an unordered two-point base $\{y,z\}$ with $x,y,z$ distinct and $|x-y|=|x-z|$. We count an equilateral triangle three times, once for each possible apex; this is the convention required by the identity \[ I=\sum_{x,r}\binom{d_r(x)}2. \] Every other vertex contributes to exactly one degree at $x$, so $\sum_{x,r}d_r(x)=n(n-1)$. Consequently \[ \sum_{x,r}d_r(x)^2=2I+n(n-1). \tag{3} \] Fix the unordered base $\{y,z\}$. Its possible apices are points of $P$ on the perpendicular bisector of $yz$. A line contains at most two points of $P$, so there are at most two apices for this base. The endpoints themselves are not on that perpendicular bisector. Therefore \[ I\leq2\binom n2=n(n-1). \tag{4} \] Summing $2$, then applying $3$ and $4$, proves $1$.

The cubic order cannot be replaced by a smaller power uniformly over convex polygons. For a regular odd $n$-gon, there are $(n-1)/2$ distances, each realized by $n$ unordered pairs, so the sum is $n^2(n-1)/2$. For a regular even $n$-gon, the first $n/2-1$ chord lengths have multiplicity $n$ and the diameter has multiplicity $n/2$, giving $n^3/2-3n^2/4$. These computations also check the factor of two in the definition of $f$.

As a consequence, if $D$ is the number of distinct distances, another application of Cauchy--Schwarz gives \[ D\geq\frac{\binom n2^2}{\sum_r f(r)^2}\geq\frac{n-1}{3}. \] This consequence is weaker than Altman's $\lfloor n/2\rfloor$ bound for convex polygons; the assertion of this problem is the stronger multiplicity control $1$.

VERIFICATION AND SCOPE

All counts above are exact and the proof is complete for every finite general-position set, including $n\leq2$. No numerical experiments or unproved geometric input are used. The word "convex" is interpreted as vertices of a convex polygon, with no extra points on its sides; the proof does not assume that arbitrary points on the boundary of a weakly convex polygon satisfy general position.

SOURCES

• Problem statement and current attribution: https://www.erdosproblems.com/94.
• H. Lefmann and T. Thiele, Point sets with distinct distances, Combinatorica 15 $1995$, 379--408: https://doi.org/10.1007/BF01299744.
• Current discussion of the elementary argument: https://www.erdosproblems.com/forum/thread/94.

CONCLUSION

Attempt status: solved by reconstruction of a known proof. The explicit bound $1$ proves the requested estimate; no novelty is claimed. Completion rate estimate: 100%.