How many incongruent diameter-minimising sets of n unit-separated points are there? Does h(n) → ∞? (Erdős #103)
Statement
For $n$ points in $\mathbb{R}^2$ subject to the constraint $d(x,y)\ge 1$ for all distinct points $x\neq y$, consider the configurations minimising the diameter. Let $h(n)$ count the number of such minimising configurations up to congruence (isometries of the plane). Is it true that $h(n)\to\infty$ as $n\to\infty$?
Acceptance. FULLY RESOLVES: a proof that $h(n)\to\infty$, machine-checkable (Lean/Coq) preferred, else a complete written proof; OR a disproof — a proof that $h(n)$ is bounded, or that $h(n)=1$ for infinitely many $n$. ADVANCES: (a) a proof that $h(n)\ge 2$ for all sufficiently large $n$ (explicitly noted on the site as itself open); (b) exact values of $h(n)$ for small $n$, obtained by an exhaustive, reproducible enumeration of all diameter-minimising configurations with a certificate of exhaustiveness (e.g. verified branch-and-bound), extending what follows from the Bezdek–Fodor small-$n$ analysis stated in the background; (c) a certified example of a single $n$ with two provably optimal, incongruent configurations, where optimality carries a rigorous certificate; (d) a proof of $h(n)\to\infty$ along an explicit infinite subsequence of $n$. Deliver the proof file, or the enumeration code with certificates and the resulting table of $h(n)$ values / optimal configurations.
Background
Posed by Erdős in [Er94b]; listed as open on erdosproblems.com/103 (fetched 2026-07-13, status 'open', tagged 'geometry | distances'). Strikingly little is known: it is not even known whether $h(n)\ge 2$ for all large $n$ — i.e. whether the optimal 'spreading points' configuration is ever eventually unique. This is the uniqueness-counting companion of Erdős #99 (erdosproblems.com/99), which asks whether these same diameter-minimising configurations must contain a unit equilateral triangle; the relevant structure theory there: Thue's theorem implies the minimal diameter is achieved asymptotically by triangular-lattice points intersected with a disc, Erdős believed minimisers must contain $(1-o(1))n$ points of a triangular lattice, and the exact minimisers for small $n$ were investigated by Bezdek and Fodor [BeFo99]. Heuristically, the freedom in choosing which boundary lattice points to include suggests many incongruent optima for most $n$, but certifying even two distinct global optima for a single large $n$ requires exact control of the optimisation problem. Erdős #91 raises the same non-uniqueness theme for distinct-distance minimisers. The attacker's tools: rigorous global optimisation (interval-arithmetic branch-and-bound over configuration space modulo congruence, as in certified circle-packing work) to exhaustively enumerate ALL diameter minimisers for small $n$ and compute $h(n)$ exactly, plus lattice/boundary combinatorics for the asymptotic count.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #103 (T. F. Bloom) | website |
| REF-02 | Erdős Problem #99 — companion problem on the same diameter-minimising configurations | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.