Point sets whose distinct distances differ by at least 1: must the diameter grow linearly in n? (Erdős #100)
Statement
Let $A$ be a set of $n$ points in $\mathbb{R}^2$ such that all pairwise distances are at least $1$, and such that any two distinct pairwise distances differ by at least $1$. Is the diameter of $A$ necessarily $\gg n$, i.e. at least $cn$ for some absolute constant $c>0$?
Acceptance. FULLY RESOLVES: a proof that the diameter is $\gg n$ (or the stronger $\ge n-1$ for all sufficiently large $n$), machine-checkable (Lean/Coq) preferred, else a complete written proof; OR a disproof — an explicit infinite family of configurations satisfying both distance conditions with diameter $o(n)$, given by exact (rational or algebraic) coordinates with a verifiable check of the separation conditions and diameter. ADVANCES: (a) a lower bound on the diameter asymptotically strictly better than the $\gg n/\log n$ bound stated in the background, with proof; (b) certified configurations beating the trivial diameter for new values of $n$ (extending Piepmeyer's 9-point, diameter-$<5$ example), or exact minimal diameters for small $n$ established by exhaustive reproducible search; (c) a proof of the $\gg n$ bound under an additional structural hypothesis (e.g. all distances integers). Deliver the proof file, or the configurations with exact coordinates plus verification code, or the search code and certified small-$n$ table.
Background
Posed by Erdős in [Er90] and repeated in [Er92e], [Er95] and [Er97f]; listed as open on erdosproblems.com/100 (fetched 2026-07-13, status 'open', tagged 'geometry | distances'). Erdős suggested the diameter might even be $\ge n-1$ for sufficiently large $n$ — the collinear arrangement $\{0,1,\dots,n-1\}$ achieves exactly $n-1$ — but this fails for small $n$: Piepmeyer found $9$ such points with diameter $<5$. The key observation linking this to distinct distances: since all distances lie in $[1,D]$ ($D$ = diameter) and any two distinct distances differ by at least $1$, the set determines at most $D$ distinct distances. Kanold proved the diameter is $\ge n^{3/4}$; the Guth–Katz theorem [GuKa15] on Erdős's distinct-distances problem (Erdős #89, erdosproblems.com/89) — every $n$-point set determines $\gg n/\log n$ distinct distances — immediately gives the current record lower bound of $\gg n/\log n$. Thus the problem sits exactly one logarithm away from resolution, and any improvement must exploit the arithmetic separation of the distance set beyond its mere cardinality. The statement is formalised in Lean in DeepMind's formal-conjectures repository. The attacker's tools: incidence-geometry or additive-structure arguments to remove the $\log$ factor; and on the construction side, computer search (constraint solving / global optimisation with exact certification) for dense small-diameter configurations with $1$-separated distance sets, extending Piepmeyer's example and mapping the small-$n$ extremal landscape.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #100 (T. F. Bloom) | website |
| REF-02 | L. Guth, N. H. Katz — On the Erdős distinct distance problem in the plane [GuKa15] | arxiv |
| REF-03 | Formalised Lean statement of Erdős #100 (google-deepmind/formal-conjectures) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.