Must two distances among n planar points each occur at least once but at most n times? (Erdős #132)
Statement
Let $A \subset \mathbb{R}^2$ be a set of $n$ distinct points. Call a distance $d$ rare for $A$ if $d$ occurs as the distance between at least one and at most $n$ of the $\binom{n}{2}$ pairs of points of $A$. Must there always be at least two rare distances? And must the number of rare distances tend to infinity as $n \to \infty$?
Acceptance. FULLY RESOLVES: settle both questions. Either (i) a proof that every $n$-point planar set ($n \ge 5$, or all sufficiently large $n$, stated precisely) has at least two rare distances AND a proof or disproof that the number of rare distances tends to infinity — machine-checkable (Lean/Coq) preferred, else full written proofs; or (ii) a counterexample to the first question: an explicit $n$-point set ($n \ge 5$) given by exact (algebraic) coordinates with at most one rare distance, certified by an exact, reproducible computation of every pairwise distance multiplicity. A negative answer to the first question resolves the second as well. ADVANCES (Erdős's own bar: any nontrivial result, historically worth $100): (a) a proof of the two-rare-distances claim for $n = 7$ (or any $n \ge 7$ beyond the Erdős–Fishburn cases stated in the background), computer-assisted proofs with reproducible certificates accepted; (b) extending the convex-position result of the background to a strictly wider class of point sets, with proof; (c) a lower bound on the number of rare distances that grows with $n$ (even $\ge 3$ for all large $n$ would be new), with proof; (d) an explicit configuration family achieving unusually few rare distances, with exact verification code, as a record on the constructive side. Deliver the proof file (or compiling Lean sources), or the exact-coordinate configuration plus the verification code and its output.
Background
Asked by Erdős and Pach; Erdős returned to it in [Er84c, ErPa90, ErFi95, Er97b, Er97e], and it is listed as open on erdosproblems.com/132 (fetched 2026-07-13, status 'open', tagged 'distances'). Erdős offered $100 for 'any nontrivial result' [Er97e]. One rare distance always exists: Hopf and Pannowitz [HoPa34] proved that the maximum distance of an $n$-point planar set occurs at most $n$ times — but it is not even known that a second rare distance must exist. Erdős [Er84c] believed that at least two rare distances exist for every $n \ge 5$; this is false at $n=4$ (glue two equilateral triangles of equal side along an edge: the resulting 4-point rhombus has only one rare distance), and Erdős and Fishburn [ErFi95] proved it true for $n = 5$ and $n = 6$; the cases $n \ge 7$ are open in general. Clemen, Dumitrescu, and Liu [CDL25] proved that at least two rare distances always exist when $A$ is in convex position (no point of $A$ inside the convex hull of the others), and also for sets that are 'not too convex' in a specific technical sense. It may even be true that there are $\ge n^{1-o(1)}$ rare distances. Related problems: Erdős #223 (erdosproblems.com/223), #756, and #957. For any explicitly given configuration with algebraic coordinates, the full distance-multiplicity spectrum is exactly computable, so both counterexample hunting and small-$n$ case analysis have real computational purchase. The attacker's tool: exact computational geometry (algebraic coordinates plus certified distance-multiplicity counting) to search for configurations with few rare distances, computer-assisted case analysis / real quantifier elimination for small $n$, and the convexity-structure techniques of [CDL25] for general-position proofs.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #132 (T. F. Bloom) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.