Largest gap between the top two distance multiplicities of an $n$-point planar set (Erdős #959)
Statement
Let $A\subset \mathbb{R}^2$ be a set of $n$ points and let $\{d_1,\ldots,d_k\}$ be the set of distinct distances determined by $A$. For a distance $d$ let $f(d)$ be the number of pairs of points of $A$ at distance exactly $d$ (its multiplicity), and order the distances so 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 sets $A$ of size $n$. More generally, estimate $\max\,(f(d_r)-f(d_{r+1}))$ for each fixed $r$.
Acceptance. FULLY RESOLVES: determine the order of magnitude of $\max(f(d_1)-f(d_2))$ over $n$-point planar sets — matching upper and lower bounds up to $n^{o(1)}$ (or up to constants), with a complete proof (machine-checkable Lean/Coq preferred, else a full written proof with all steps). ADVANCES: (a) a construction with proof pushing the lower bound strictly above the best bound stated in the background (e.g. proving the Clemen–Dumitrescu–Liu conjectured $n^{1+c/\log\log n}$, or any bound $\gg n(\log n)^{1+\delta}$); (b) a nontrivial upper bound on $f(d_1)-f(d_2)$ strictly below the unit-distance-derived $O(n^{4/3})$ ceiling stated in the background; (c) analogous improvements for the general gap $f(d_r)-f(d_{r+1})$; or (d) reproducible computations of exact maximum-gap values for explicitly parameterized construction families (with code and exact multiplicity spectra) that certify a new record gap at concrete $n$ beyond what the known constructions give. Deliver the proof file, or the construction with its multiplicity-spectrum certificate and the code that computes it.
Background
Posed by Erdős [Er84d]; listed as open on erdosproblems.com/959 (fetched 2026-07-13, status 'open', tagged 'geometry | distances'). The question sits inside the unit-distance circle of problems: $f(d_1)$ is the maximum multiplicity of a single distance, which by the Spencer–Szemerédi–Trotter unit-distance bound is $O(n^{4/3})$, so the gap $f(d_1)-f(d_2)$ is trivially $O(n^{4/3})$; Erdős's unit-distance conjecture would lower that ceiling to $n^{1+O(1/\log\log n)}$. On the lower-bound side the frontier is recent: Clemen, Dumitrescu, and Liu [CDL25] constructed $n$-point sets showing $\max(f(d_1)-f(d_2))\gg n\log n$, and more generally, for any $1\leq r\leq \log n$, sets with $f(d_r)-f(d_{r+1})\gg \frac{n\log n}{r}$. They conjecture the truth is larger: that $n\log n$ can be improved to $n^{1+c/\log\log n}$ for some constant $c>0$ (which would match the shape of the conjectured extremal unit-distance count attained by lattice sections). The problem is thus wide open between $n\log n$ and $n^{4/3}$. The attacker's tool: computer-aided construction — compute full distance-multiplicity spectra of structured families (integer-lattice sections, perturbed lattices, product sets) at scale to find families whose top multiplicities are provably separated, then prove the asymptotics of the resulting family; on the upper-bound side, incidence-geometry arguments specialized to two competing distances.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #959 (T. F. Bloom) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.