Erdős Problem #959

Definitions and mathematical statement

Shared notation.

Unless a section says otherwise, ${\mathbb{N}}=\{1,2,\ldots\}$, ${\mathbb{Z}}$ is the ring of integers, ${\mathbb{Q}},{\mathbb{R}},{\mathbb{C}}$ are the rational, real, and complex fields, $[N]=\{1,\ldots,\lfloor N\rfloor\}$, and $\log$ is the natural logarithm. For real functions of a parameter tending to infinity, $f\ll g$ and $f=O(g)$ mean $|f|\leq Cg$ eventually for some fixed $C$; $f\gg g$ reverses this comparison; $f=o(g)$ means $f/g\to0$; $f\sim g$ means $f/g\to1$; and $f\asymp g$ means both order bounds. A subscript on $O$ or $\ll$ specifies allowed constant dependence. The expression $n^{o(1)}$ in an upper bound means growth smaller than $n^\epsilon$ for each fixed $\epsilon>0$. Local definitions govern any exception, finite-field convention, or use of the same symbol for another object. An asymptotic claim is not automatically an effective algorithm.

Count each unordered point pair once. Sort the positive distance values by these multiplicities, not by distance magnitude. For large $n$ with at least two realized distance values, the extremum is the largest gap between the first two multiplicities.

Distances are Euclidean. Distinct distances mean distinct numerical values; when a distance is said to occur a certain number of times, unordered pairs of distinct points are counted. Congruence allows any Euclidean isometry, including reflection. [S1] [S2]

Statement recorded in the supplied source.

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$. [S1]

Residual task reported by the archive.

The embedded review (2026-08-17) records: Improve the lower bound or prove a comparably sharp upper bound for max_A(f(d_1)-f(d_2)). [S1]

Short English statement

In a planar point set, how much more frequently can the most common distance occur than the second most common distance?

Sources

• S1 ULAM.AI, UnsolvedMath, supplied problems.json, record 2409 (EP-959), statement and background. The embedded literature-review date is 2026-08-17; that is the archive’s review date, not a fresh certification. Dataset landing page: https://huggingface.co/datasets/ulamai/UnsolvedMath.

• S2 T. F. Bloom, Erdős Problems, Problem 959, https://www.erdosproblems.com/959. Reference from the supplied record; the live problem page was not independently checked for this compilation.

• S3 F. C. Clemen, A. Dumitrescu, and D. Liu, On multiplicities of interpoint distances, Acta Math. Hungar. (2025),

  \nolinkurl{doi:10.1007/s10474-025-01562-y.}

  https://arxiv.org/abs/2505.04283. Bibliographic information from the supplied record.