Distinct distances in $\mathbb{R}^d$: is the minimum $n^{2/d-o(1)}$ for every fixed $d\geq 3$? (Erdős #1083)
Statement
Let $d\geq 3$, and let $f_d(n)$ be the minimal $m$ such that every set of $n$ points in $\mathbb{R}^d$ determines at least $m$ distinct distances. Estimate $f_d(n)$ — in particular, is it true that $$f_d(n)=n^{\frac{2}{d}-o(1)}?$$ The intended regime is $d$ fixed and $n\to\infty$.
Acceptance. FULLY RESOLVES: a complete proof (machine-checkable Lean/Coq preferred, else a full written proof with all steps) that $f_d(n)=n^{2/d-o(1)}$ for every fixed $d\geq 3$ — i.e. a lower bound $f_d(n)\gg n^{2/d-o(1)}$ matching Erdős's lattice upper bound; or a refutation, exhibiting for some fixed $d\geq 3$ a family of $n$-point configurations with only $O(n^{2/d-\delta})$ distinct distances for a fixed $\delta>0$, with proof. ADVANCES: a proven lower bound in some fixed dimension strictly better than the best bound stated in the background (e.g. beating $n^{3/5}$ in dimension 3, or improving the $c/d^2$ loss for $d\geq 4$); a sharpened upper-bound construction beating the lattice by more than $n^{o(1)}$; or reproducible exact/certified values of the minimum number of distinct distances for small point counts in $\mathbb{R}^3$ (code plus optimality certificates), extending the known ground truth. Deliver the proof file, or the construction/values with verification code and certificates.
Background
The higher-dimensional generalisation of Erdős's distinct distances problem, posed in the same 1946 paper [Er46b] and reiterated in [Er75f, p.101]; listed as open on erdosproblems.com/1083 (fetched 2026-07-13, status 'open', tagged 'geometry | distances'). The planar case (Erdős #89, erdosproblems.com/89) was essentially resolved by Guth and Katz (2015), who proved $\gg n/\log n$ distinct distances; a nearby planar variant, Szemerédi's conjecture on distinct distances under a no-3-collinear hypothesis (Erdős #1082), is already on this venue. For $d\geq 3$ Erdős [Er46b] proved $n^{1/d}\ll_d f_d(n)\ll_d n^{2/d}$, the upper bound coming from a cube of lattice points, whose distinct distances are integers up to $\sim d\cdot n^{2/d}$; the conjecture is that the lattice is extremal up to $n^{o(1)}$. The lower-bound frontier, per the source page: Clarkson–Edelsbrunner–Guibas–Sharir–Welzl [CEGSW90] proved $f_3(n)\gg n^{1/2}$; Aronov–Pach–Sharir–Tardos [APST04] proved $f_d(n)\gg n^{\frac{1}{d-90/77}-o(1)}$ for all $d\geq 3$ (e.g. $f_3(n)\gg n^{0.546}$); Solymosi and Vu [SoVu08] proved $f_d(n)\gg_d n^{\frac{2}{d}-\frac{c}{d^2}}$ for all $d\geq 4$ (some absolute $c>0$), and their method combined with Guth–Katz gives $f_3(n)\gg n^{3/5}$ — the best recorded bound in dimension 3, still short of the conjectured $n^{2/3-o(1)}$. OEIS A186704 tracks the exact planar minimum for small $n$; $f_d$ is essentially the inverse of the function $g_d$ of Erdős #1089 (erdosproblems.com/1089). The attacker's tool: polynomial-method/incidence machinery (partitioning polynomials à la Guth–Katz adapted to $\mathbb{R}^3$) for the lower bound, and exact computation of $f_d(n)$ for small $n$ and $d=3$ via certified nonlinear optimization to map the ground truth.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #1083 (T. F. Bloom) | website |
| REF-02 | OEIS A186704 — minimal number of distinct distances determined by n points in the plane | website |
| REF-03 | Guth & Katz, On the Erdős distinct distance problem in the plane (resolves the d=2 case) | arxiv |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.