PROVED (LEAN)
This has been solved in the affirmative and the proof verified in Lean.
If $n$ distinct points in $\mathbb{R}^2$ form a convex polygon then they determine at least $\lfloor \frac{n}{2}\rfloor$ distinct distances.
Solved by Altman
[Al63]. The stronger variant that says there is one point which determines at least $\lfloor \frac{n}{2}\rfloor$ distinct distances (see
[982]) is still open. Fishburn in fact conjectures that if $R(x)$ counts the number of distinct distances from $x$ then\[\sum_{x\in A}R(x) \geq \binom{n}{2}.\]Szemerédi conjectured a stronger form in which the convexity is replaced by the assumption that there are no three points on a line - see
[1082].
See also
[660].
View the LaTeX source
This page was last edited 19 October 2025. View history
|
Likes this problem
|
None
|
|
Interested in collaborating
|
None
|
|
Currently working on this problem
|
None
|
|
This problem looks difficult
|
None
|
|
This problem looks tractable
|
None
|
|
The results on this problem could be formalisable
|
None
|
|
I am working on formalising the results on this problem
|
None
|
When referring to this problem, please use the original sources of Erdős. If you wish to acknowledge this website, the recommended citation format is:
T. F. Bloom, Erdős Problem #93, https://www.erdosproblems.com/93, accessed 2026-04-11
