OPEN
This is open, and cannot be resolved with a finite computation.
Let $A\subset \mathbb{R}^2$ be a set of size $n$ and let $\{d_1,\ldots,d_k\}$ be the set of distinct distances determined by $A$. Let $f(d)$ be the number of times the distance $d$ is determined, and suppose the $d_i$ are ordered such that\[f(d_1)\geq f(d_2)\geq \cdots \geq f(d_k).\]Estimate\[\max (f(d_1)-f(d_2)),\]where the maximum is taken over all $A$ of size $n$.
More generally, one can ask about\[\max (f(d_r)-f(d_{r+1})).\]Clemen, Dumitrescu, and Liu
[CDL25], have shown that\[\max (f(d_1)-f(d_2))\gg n\log n.\]More generally, for any $1\leq k\leq \log n$, there exists a set $A$ of $n$ points such that\[f(d_r)-f(d_{r+1})\gg \frac{n\log n}{r}.\]They conjecture that $n\log n$ can be improved to $n^{1+c/\log\log n}$ for some constant $c>0$.
View the LaTeX source
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 #959, https://www.erdosproblems.com/959, accessed 2025-11-16
All comments are the responsibility of the user. Comments appearing on this page are not verified for correctness. Please keep posts mathematical and on topic.
