Do $n$ points whose pairwise distances differ by at least 1 force diameter $(1+o(1))n^2$? (Erdős #670)
Statement
Let $A\subseteq \mathbb{R}^d$ be a set of $n$ points such that all $\binom{n}{2}$ pairwise distances differ from one another by at least $1$ (any two distinct pairs of points determine distances at least $1$ apart). Is the diameter of $A$ at least $(1+o(1))n^2$? The intended regime is $d$ fixed and $n\to\infty$ (the $o(1)$ rate may depend on $d$).
Acceptance. FULLY RESOLVES: a complete proof (machine-checkable Lean/Coq preferred, else a full written proof) that for each fixed $d$, every $n$-point set in $\mathbb{R}^d$ whose pairwise distances mutually differ by at least $1$ has diameter at least $(1+o(1))n^2$; OR a disproof for some fixed $d$ — an explicit family of configurations (coordinates given, or an exactly described construction) valid for infinitely many $n$ with all pairwise distance gaps at least $1$ and diameter at most $(1-\delta)n^2$ for a fixed $\delta>0$, with a certificate (exact arithmetic or verified interval arithmetic) that the separation and diameter claims hold. ADVANCES: a proof improving the trivial constant for some fixed $d$ (e.g. diameter $\geq (c+o(1))n^2$ with $c>1/2$ in the plane), strictly better than the best bound stated in the background; or an extension of the Ho-type counterexample regime to dimensions growing more slowly than $n^2-n$; or verified extremal configurations for small $n$ in the plane (minimum-diameter $1$-separated sets) with reproducible optimization code and certificates. Deliver the proof file, or the construction/coordinates plus the verification code and its output.
Background
Posed by Erdős [Er97f, p.6]; listed as open on erdosproblems.com/670 (fetched 2026-07-13, status 'open', tagged 'geometry | distances'). Since the $\binom{n}{2}$ pairwise distances are pairwise separated by at least $1$, the largest of them — hence the diameter — is trivially at least about $\binom{n}{2}\approx n^2/2$; the question is whether the geometry of $\mathbb{R}^d$ forces roughly double that. Erdős himself proved the $(1+o(1))n^2$ bound in dimension $d=1$ [Er97f]. The quantifiers in the original are slightly ambiguous, but the fixed-$d$ reading is the accepted one, because the high-dimensional version is now FALSE: Ho [Ho26] showed that for infinitely many $n$, taking $d=n^2-n$, there is a set $A\subset\mathbb{R}^d$ with all pairwise distances differing by at least $1$ and diameter at most $(1-\tfrac{1}{\pi^2}+o(1))n^2\approx 0.898\,n^2$. The problem therefore lives in fixed dimension, with $d=2$ the first genuinely open case: nothing better than the trivial $\sim n^2/2$ lower bound is recorded on the page for the plane, and no sub-$n^2$ fixed-dimension construction is known. The attacker's tool: numerical/combinatorial search for planar (or fixed-$d$) configurations with $1$-separated distance sets and diameter below $(1-\delta)n^2$ via nonlinear optimization over point coordinates, and, on the proof side, sharpening the packing/counting argument that works for $d=1$ to improve the constant $1/2$ toward $1$ in the plane.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #670 (T. F. Bloom) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.