Two non-similar n-point sets minimising distinct distances: prove non-uniqueness for large n (Erdős #91)
Statement
Let $n$ be a sufficiently large integer. Suppose $A\subset\mathbb{R}^2$ has $\lvert A\rvert=n$ and minimises the number of distinct distances between points of $A$ — that is, no other $n$-point set in the plane determines strictly fewer distinct distances. Prove that there are at least two (and probably many) such minimising sets $A$ which are non-similar, i.e. no similarity transformation of the plane (composition of scaling, rotation, reflection, translation) maps one onto the other.
Acceptance. FULLY RESOLVES: a proof that for all sufficiently large $n$ (or all $n\ge n_0$ for an explicit $n_0$) there exist at least two non-similar $n$-point sets in $\mathbb{R}^2$ minimising the number of distinct distances — machine-checkable (Lean, e.g. building on the formal-conjectures statement of #91) preferred, else a complete written proof with all steps. A disproof — a proof that for infinitely many $n$ the minimiser is unique up to similarity — also fully resolves. ADVANCES: a rigorous, reproducible determination of ALL minimising configurations for a specific $n\ge 6$ (code plus a certificate that the enumeration/optimisation is exhaustive, e.g. interval-arithmetic branch-and-bound over configurations modulo similarity), verifying or refuting Erdős's claim of two non-similar optima for $6\le n\le 9$; or a proof of non-uniqueness for an infinite subsequence of $n$; or a machine-checked formalisation of the $n=5$ uniqueness proof of Kovács. Deliver the proof file, or the search code with its exhaustiveness certificate and the resulting list of optimal configurations.
Background
Posed by Erdős [Er87b, p.171] and repeated in [Er90] and [Er97e]; listed as open on erdosproblems.com/91 (fetched 2026-07-13, status 'open', tagged 'geometry | distances'). The value of the minimum itself is Erdős's celebrated distinct-distances problem (Erdős #89, erdosproblems.com/89): Guth–Katz proved every $n$-point planar set determines $\gg n/\log n$ distinct distances, while sections of the triangular lattice give $O(n/\sqrt{\log n})$ — the conjectured extremals are lattice-like, which is the heuristic behind expecting many non-similar optima. Known small cases: for $n=3$ the equilateral triangle is the unique minimiser; for $n=4$ there are already two non-similar minimisers (the square, and two equilateral triangles glued along an edge); for $n=5$ the regular pentagon is again the UNIQUE minimiser (with two distinct distances) — Erdős attributed the proof to 'a colleague from Zagreb' whose letter he lost, and the first published proof is by Kovács [Ko24c]. Erdős asserted in [Er87b] that at least two non-similar minimisers exist for each $6\le n\le 9$. OEIS A186704 records the minimal number of distinct distances determined by $n$ points in the plane. The site flags unincorporated partial-result claims in its comment thread (7 comments, not captured here), and the statement is already formalised in Lean in DeepMind's formal-conjectures repository. The attacker's tools: rigorous certified enumeration of optimal configurations for small $n$ (global optimisation with interval arithmetic over the configuration space modulo similarity) to confirm and extend Erdős's $6\le n\le 9$ claim, structural/perturbation arguments for general $n$, or Lean formalisation of the small-case proofs.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #91 (T. F. Bloom) | website |
| REF-02 | OEIS A186704 — minimal number of distinct distances determined by n points in the plane | website |
| REF-03 | Formalised Lean statement of Erdős #91 (google-deepmind/formal-conjectures) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.