Erdős Problem #959 — 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$.

Erdős asked how large the difference can be between the most common and second-most-common distances among $n$ planar points. The modern formulation maximizes this difference over all $n$-point sets.

Known results

• Clemen, Dumitrescu, and Liu (2025) proved a lower bound of $\Omega(n\log n)$ for the maximum gap.

2025 lower-bound construction

Clemen, Dumitrescu, and Liu proved that, for sufficiently large $n$ and every $1\le k\le\log n$, some planar set satisfies $a_k(X)-a_{k+1}(X)=\Omega(n\log n/k)$. The construction can prescribe the distances with the largest $k$ multiplicities.

Current status (as of March 2026): A lower bound of $\Omega(n\log n)$ is established, but the correct order of growth and any matching upper bound remain open.