Degenerate 4-point subsets (a repeated distance among the six): is the count $n^{3+o(1)}$? (Erdős #1087)
Statement
Call a set of four points in $\mathbb{R}^2$ degenerate if some two of the six distances it determines are equal (two pairs of its points are the same distance apart). Let $f(n)$ be minimal such that every set of $n$ points in $\mathbb{R}^2$ contains at most $f(n)$ degenerate four-point subsets. Estimate $f(n)$ — in particular, is it true that $f(n)\leq n^{3+o(1)}$?
Acceptance. FULLY RESOLVES: a complete proof (machine-checkable Lean/Coq preferred, else a full written proof with all steps) that $f(n)\leq n^{3+o(1)}$, matching the Erdős–Purdy lower bound and pinning the order of $f(n)$ up to $n^{o(1)}$; OR a refutation — a family of $n$-point configurations with at least $n^{3+\delta}$ degenerate four-point subsets for a fixed $\delta>0$, with proof of the count. ADVANCES: (a) a proven upper bound $f(n)\ll n^{7/2-\delta}$ for a fixed $\delta>0$, strictly better than the best bound stated in the background; (b) a proven improvement to the maximum number of isosceles triangles spanned by $n$ planar points (which transfers directly to $f$ via the decomposition in the background), strictly better than the best published isosceles-triangle bound, clearly stated and compared; (c) a sharpened lower-bound construction with proven count $\gg n^3(\log n)^{1+\delta}$ or better; (d) reproducible certified counts of degenerate quadruples for explicit structured families or exact extremal values for small $n$, with code and verification. Deliver the proof file, or the construction/counting code with its certificates and attained bounds.
Background
A question of Erdős and Purdy [ErPu71], reiterated by Erdős [Er75f, p.104]; listed as open on erdosproblems.com/1087 (fetched 2026-07-13, status 'open', tagged 'geometry | distances'). Erdős and Purdy proved $$n^3\log n \ll f(n) \ll n^{7/2},$$ and the conjecture is that the lower bound's exponent is the truth. Structurally the count splits in two: quadruples whose repeated distance is realized by two disjoint pairs are controlled by the number of 'distance quadruples' $(p_1,p_2,p_3,p_4)$ with $|p_1p_2|=|p_3p_4|$, which Guth and Katz bounded by $O(n^3\log n)$ in their resolution of the planar distinct distances problem; quadruples whose repeated distance shares a vertex are exactly (isosceles triangle) $\times$ (free fourth point), contributing on the order of $n\cdot I(n)$ where $I(n)$ is the maximum number of isosceles triangles spanned by $n$ planar points. Given the Guth–Katz control of the disjoint-pair term, the $n^{3+o(1)}$ question essentially reduces to the open problem of whether $I(n)\leq n^{2+o(1)}$; the $\sqrt{n}\times\sqrt{n}$ integer grid shows $I(n)\gg n^2\log n$, matching the lower bound for $f$. The attacker's tool: incidence geometry / polynomial partitioning aimed at the isosceles-triangle count, and computational work — exact counting of degenerate quadruples and isosceles triples on lattice sections and perturbed families to calibrate constants and test candidate extremal structures, plus certified extremal values for small $n$.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #1087 (T. F. Bloom) | website |
| REF-02 | Guth & Katz, On the Erdős distinct distance problem in the plane (source of the $O(n^3\log n)$ distance-quadruples bound) | arxiv |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.