Problem 959

Erdős Problem #959: declared status 'open'. Formalized: no. 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$. Current best: 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$. Prize: no. Tags: distances, geometry.