Erdős #132 — a second low-multiplicity distance

Statement

Let $A\subset \mathbb{R}^2$ be a set of $n$ points. Must there be two distances which occur at least once but between at most $n$ pairs of points? Must the number of such distances $\to \infty$ as $n\to \infty$?

(Equivalently, in the language of Clemen–Dumitrescu–Liu: writing $\mu(X,d)$ for the number of pairs of $X$ at distance $d$, must some distance $d\neq \Delta(X)$ — the diameter — satisfy $\mu(X,d)\leq n$, and must the number of distances with $\mu(X,\cdot)\leq n$ tend to infinity with $n$?)

Facts

- Prize \$100; status OPEN per erdosproblems.com/132 (site-owner belief, fetched 2026-07-02): "This is open, and cannot be resolved with a finite computation." - Falsifiable: not by finite computation — for fixed $n$ the space of $n$-point planar configurations is a continuum, so even refuting the claim for one specific $n$ is not a finite search; a full resolution (positive or negative) needs a genuine proof, consistent with the site's classification. - Origin: asked by Erdős and Pach. Key refs: Erdős 1984 [Er84c] "Some old and new problems in combinatorial geometry" (states the $n\geq5$ conjecture); Erdős–Pach 1990 [ErPa90] "Variations on the theme of repeated distances," Combinatorica; Erdős–Fishburn 1995 [ErFi95] "Multiplicities of interpoint distances in finite planar sets," Discrete Appl. Math.; Erdős 1997 [Er97b] "Some old and new problems in various branches of combinatorics"; Erdős 1997 [Er97e] "Some of my favourite unsolved problems," Math. Japon. — where Erdős offers the \$100 for "any nontrivial result." - Hopf & Pannwitz 1934 [HoPa34] ("Aufgabe 167," Jber. Deutsch. Math. Verein.) proved the base case underlying the whole problem: the diameter (largest distance) of any $n$-point planar set occurs at most $n$ times. This is the one distance always known to have multiplicity $\leq n$; #132 asks whether a *second* one must exist. - Erdős [Er84c] conjectured that for $n\geq5$ there must always be at least two such distances. False for $n=4$: two equilateral triangles of equal side length glued along an edge (a rhombus) is a counterexample. - Erdős & Fishburn 1995 [ErFi95] proved the conjecture true for $n=5$ and $n=6$. The general case $n\geq7$ was open until 2025. - Clemen, Dumitrescu & Liu, "On multiplicities of interpoint distances", arXiv:2505.04283 (May 2025, v5 3 Feb 2026) — read in full — proved the conjecture in two substantial special cases: - Convex position (Theorem 1.2): if $X$ is in convex position, some non-diameter distance has multiplicity $\leq n$. Proof uses Altman's theorem (E. Altman, Amer. Math. Monthly 70 (1963), 148-157: any $n$ convex points determine $\geq\lfloor n/2\rfloor$ distinct distances, with the extremal case being the regular $n$-gon) plus Fishburn's classification (P. Fishburn, Comput. Geom. 5 (1995), 65-93) of the even-$n$ near-extremal convex polygons. If $X$ determines strictly more than $\lfloor n/2\rfloor$ distinct distances and every distance besides the diameter occurred $>n$ times, the total pair count would be at least $\lfloor n/2\rfloor(n+1)+1 > \binom n2$ — impossible, since $\binom n2$ is the exact number of pairs. The remaining boundary case (exactly $\lfloor n/2\rfloor$ distinct distances) is settled directly by the Altman/Fishburn extremal classification. - "Not too convex" position (Theorem 1.3): if $L_1,L_2$ are the first and second convex-hull layers of $X$ and $\min\{\tfrac32(|L_1|+|L_2|),\ \tfrac43|L_1|+2|L_2|,\ 2|L_1|+|L_2|\}\leq n$, then the *second-largest* distance $\Delta_2(X)$ has multiplicity $\leq n$. Proof builds a graph on $L_1\cup L_2$ whose edges are the $\Delta_2$-pairs and bounds its edge count using structural lemmas of Vesztergombi (see below) plus a degeneracy-peeling argument. Corollary: if $\Delta(X)\leq \frac{n}{3\pi}\delta(X)$ (diameter-to-min-distance ratio small), $\mu(X,\Delta_2)\leq n$. - General (arbitrary, non-convex) point sets remain open for $n\geq7$ — this is the crux of the still-unresolved part of #132. - Vesztergombi 1996 ("The two largest distances in finite planar sets," Discrete Math. 150 (1996), 379-386) proved *unconditionally, for ANY $n$-point planar set* (no convexity assumption) that the second-largest distance has multiplicity $\mu(X,\Delta_2)\leq \tfrac32 n$ — already within a constant factor of the target $n$ used by CDL25's convex-layer argument. (See also Vesztergombi 1987, "On large distances in planar sets," Discrete Math. 67, 191-198.) - CDL25 Proposition 1.5 shows the "obvious" fallback pair of witnesses can fail simultaneously: there exist $n$-point sets where both the smallest distance $\delta$ and the second-largest $\Delta_2$ have multiplicity $\geq(\tfrac98+o(1))n$ (both $>n$) — so no single canonical pair of distances (diameter+second-largest, or diameter+smallest) can serve as the universal second witness; the second low-multiplicity distance, if it always exists, must in general be config-dependent. They pose (Problem 1.6, open) determining $\limsup_n \sup_X \min\{\mu(X,\Delta_2),\mu(X,\delta)\}/n$. - The "$\to\infty$" sub-question (must the *number* of $\leq n$-multiplicity distances diverge) is not directly resolved either way in CDL25, but their Theorem 1.7 is suggestive: in the $\sqrt n\times\sqrt n$ integer grid, only $n^{c/\log\log n}$ distances (for a constant $c>0$) have *superlinear* ($>n$) multiplicity; since a grid determines $\Theta(n/\sqrt{\log n})$ distinct distances total (Erdős's original upper-bound construction), almost all of them — $\Theta(n/\sqrt{\log n}) - n^{c/\log\log n} \to\infty$ — have multiplicity $\leq n$. This is only for the grid (one configuration, not a universal statement over all $X$), but it is a concrete existence proof that "$\to\infty$" is achievable and not obviously an obstruction. - Related problems: erdos/223 (Hopf–Pannwitz / Vázsonyi diameter-graph problem, generalized to $\mathbb R^d$ — SOLVED), erdos/756 (Erdős–Pach: can $\gg n$ distances *each* occur $>n$ times? — PROVED yes, by Bhowmick's construction, sharpened by CDL25's grid result — the "opposite extreme" question, explicitly listed as "See also [132]" on the site), erdos/957 (bound on $f(d_1)f(d_k)$ for smallest/largest-distance multiplicities — PROVED), Erdős #89 — distinct distances in the plane (the general Erdős distinct-distances problem: $\gg n/\sqrt{\log n}$ distinct distances — still OPEN, \$500; Guth–Katz only gave $\Omega(n/\log n)$). - No formalisation exists (erdosproblems.com/132: "Formalised statement? No"). No AI/LLM-system contribution found on this specific problem (teorth/erdosproblems "AI contributions" wiki page, fetched in full, does not mention #132).

Literature state

Not resolved in general — genuinely open for arbitrary (non-convex) $n\geq7$ point sets, but substantially advanced in 2025. Before 2025 only $n=4$ (counterexample), $n=5,6$ (Erdős–Fishburn, proved) were settled, alongside the unconditional base fact (Hopf–Pannwitz 1934) that the diameter itself has multiplicity $\leq n$. Clemen, Dumitrescu & Liu (arXiv:2505.04283, "On multiplicities of interpoint distances," 2025, revised through Feb 2026) is the first and only paper to make structural progress since Erdős–Fishburn 1995: they fully prove Erdős's Conjecture 1.1 (their numbering) for convex point sets and for "not too convex" point sets (a quantitative condition on the sizes of the first two convex-hull layers, satisfied automatically whenever $\Delta(X)/\delta(X) = O(n)$). The fully general case is explicitly left open by the paper itself, and no subsequent paper has appeared: an OpenAlex citation check on the arXiv work (2026-07-02) returns 0 citing works, so as of this research pass no one has picked up the general case. The paper is a live, active line — v5 was posted 3 Feb 2026, i.e. within the last five months of "today." The second sub-question (does the *count* of $\leq n$-multiplicity distances $\to\infty$) is not addressed head-on by CDL25 but their grid construction (Theorem 1.7) is consistent with — and mildly supportive of — a "yes."

Attack surface

- Mode: derivation+formalization (this needs new mathematical structure, not a finite search — see falsifiability above) combined with literature-extension of a very recent (2025-2026), still-uncited paper. - Concrete first experiment (derivation-fuel, not computation): the general-position gap identified above is a genuine, well-scoped constant-factor tightening target — Vesztergombi's unconditional bound $\mu(X,\Delta_2)\leq \tfrac32 n$ for ALL planar $n$-point sets is already within a factor $1.5$ of the $\leq n$ target. A promising concrete sub-goal: extend CDL25's convex-layer peeling argument (used only under the "not too convex" hypothesis) to the fully general case by (a) applying the same graph-degeneracy-peeling technique directly to the $\mu(X,\Delta_2)$-graph on all of $X$ (not just $L_1\cup L_2$), using Vesztergombi's structural lemmas ([24]: every degree-$\geq2$ vertex of the second layer has degree exactly 2 in the $\Delta_2$-graph after peeling; every first-layer vertex has $\leq2$ neighbors at distance $\Delta_2$) generalized to deeper convex layers $L_3, L_4,\dots$; or (b) attacking Problem 1.6 posed by CDL25 (bound $\min\{\mu(X,\Delta_2),\mu(X,\delta)\}$ jointly) as a smaller, better-defined open sub-problem that would itself constitute "nontrivial progress" (worth the \$100 per Erdős's own framing in [Er97e]). - A second, more computational sub-experiment for the "$\to\infty$" question: for small-to-moderate $n$ (say $n\leq 30$), enumerate/sample non-convex extremal-looking configurations (near-regular polygons with interior points, near-degenerate near-collinear/near-cocircular sets, integer-grid subsets) and numerically count how many distinct distances have multiplicity $\leq n$, tracking the minimum over configurations as $n$ grows — this cannot prove the universal claim (continuum of configurations) but can (i) hunt for a configuration where the count of $\leq n$-multiplicity distances stays bounded (which would suggest the "$\to\infty$" answer might be NO and redirect effort), or (ii) build intuition/conjectural formulas for the extremal configuration, which is exactly the kind of exploratory work that historically preceded Altman's and Vesztergombi's exact theorems. - Oracle: for the derivation route, correctness is checked the normal mathematical way (peer-reviewable proof, ideally cross-checked against CDL25's published lemmas since they are the direct extension target). For the computational sub-experiment, the oracle is exact: given $n$ points with exact/high-precision coordinates, compute all $\binom n2$ pairwise distances, cluster by exact value (rational/algebraic coordinates avoid floating-point ambiguity), and count exactly how many distinct distance-values have multiplicity $\leq n$ — fully mechanical and exact for algebraic point sets (grids, regular polygons, Minkowski sums thereof). - Feasibility: honest read — the general case is a live open problem actively worked by real discrete geometers as recently as Feb 2026, with the natural next move (generalize CDL25's layer-peeling to all convex layers, or resolve Problem 1.6) clearly identifiable but not obviously easy (CDL25 needed Altman 1963 + Fishburn 1995 + Vesztergombi 1987/1996 — three separate nontrivial prior results — just for the convex and "not too convex" cases). A full resolution is a genuine \$100-prize-level research contribution, not a quick derivation. The more tractable near-term win is Problem 1.6 (joint bound on $\mu(X,\Delta_2)$ and $\mu(X,\delta)$) or a careful write-up extending the layer-peeling argument one layer deeper, both of which are well-defined, boundedly-scoped, and directly buildable on the CDL25 machinery (which has zero citations so far — an open lane). The computational sub-experiment is easy to run but can only produce negative/exploratory evidence, not a proof, given the continuum falsifiability.

Related

- erdos/223 — Hopf–Pannwitz / Vázsonyi's conjecture on diameter-graph multiplicity in $\mathbb R^d$ (SOLVED for $d=2$ by Hopf–Pannwitz 1934 itself, $d=3$ by Grünbaum/Heppes/Straszewicz 1956-57, general $d$ asymptotically by Erdős 1960 and exactly for large $n$ by Swanepoel 2009 [Sw09]) — the base fact ($\mu(X,\Delta)\leq n$ in the plane) that #132 asks to extend to a second distance. - erdos/756 — Erdős–Pach's "opposite extreme" question (can many distances *each* occur $>n$ times?) — PROVED YES (Bhowmick 2024/25, arXiv:2407.01174; sharpened by CDL25's $n^{c/\log\log n}$-distance grid construction, Theorem 1.7) — shows the phenomenon in #132 (some distances forced to be low-multiplicity) coexists with configurations where most OTHER distances are high-multiplicity. - erdos/957 — Erdős–Pach's $f(d_1)f(d_k)\leq(\tfrac98+o(1))n^2$ conjecture on smallest/largest-distance multiplicities — PROVED; same paper [ErPa90] as #132's origin, same toolbox (extremal/convex-position multiplicity bounds). - Erdős #89 — distinct distances in the plane — the general Erdős distinct-distances problem ($\gg n/\sqrt{\log n}$ distinct distances) — still OPEN (\$500); Guth–Katz 2015 (arXiv:1011.4105, Ann. of Math. 181) proved $\Omega(n/\log n)$, a log-factor short of the conjecture. Relevant because a naive pigeonhole argument for #132's general case (distinct-distances count $\times$ per-distance multiplicity bound $\geq\binom n2$) using even the *optimal* Guth–Katz bound is asymptotically too weak by a $\log n$ factor to force a contradiction if all non-diameter distances had multiplicity $>n$ — this is a structural reason plain counting cannot resolve #132's general case and genuinely new (non-counting) structure, à la CDL25's convex-layer argument, is required. - concept/diameter-graph — Hopf–Pannwitz theorem and its generalizations; the graph whose edges are diameter-realizing pairs, foundational object for #132 and #223. - concept/distinct-distances-problem — Guth–Katz's polynomial-method lower bound (arXiv:1011.4105) and Székely's crossing-number technique; supplies (and, per the analysis above, fails to fully supply) the counting machinery relevant to #132. - concept/convex-layer-decomposition — CDL25's core technique: peel $X$ into convex hull layers $L_1,L_2,\dots$ and bound the "second-largest-distance graph" via degree-peeling on $L_1\cup L_2$; the natural generalization target for the still-open general case. - concept/extremal-distinct-distance-sets — Altman (1963) / Fishburn (1995) classification of convex point sets achieving the minimum $\lfloor n/2\rfloor$ distinct distances (regular $n$-gon and near-regular variants), the key lemma behind CDL25's convex-case proof. - concept/crossing-number-inequality — Székely's technique (Combin. Probab. Comput. 6 (1997), 353-358) for distance-counting bounds in the plane, cited as the "simple and elegant" alternative route into the distinct-distances machinery underlying this problem family.