Erdős #1083 — distinct distances in R^d (d≥3) is OPEN; the solved d=2 case (#89, Guth–Katz) is the literal numerical input to every known partial bound, via Solymosi–Vu's dimension-reduction recursion

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 pairwise distances. Estimate $f_d(n)$ — in particular, is it true that $$f_d(n) = n^{\frac2d - o(1)}?$$ (erdosproblems.com/1083, citing [Er46b] P. Erdős, "On sets of distances of $n$ points," Amer. Math. Monthly 53 (1946), 248–250, and [Er75f, p.101].) **This is a direct generalization of the classical planar distinct-distances problem, Erdős #89 — distinct distances in the plane, to dimension $d\geq3$.**

Status: erdos/1083 is OPEN in every dimension $d\geq3$ (erdosproblems.com, fetched 2026-07-02: "This is open, and cannot be resolved with a finite computation.") This page documents (a) why it is open — the size of the remaining gap in each dimension — and (b) the one piece of it that *is* solved and does all the load-bearing work in the current record bounds: the planar case $d=2$ (a separate numbered problem, Erdős #89 — distinct distances in the plane), resolved up to a $\sqrt{\log n}$ factor by Guth & Katz (2015), and the dimension-reduction recursion (Solymosi–Vu 2008) that is the transferable machine converting that one solved 2D fact into a bound in *every* higher dimension simultaneously.

Facts

- Trivial bounds (Erdős, 1946, same paper as the planar problem): $n^{1/d} \ll_d f_d(n) \ll_d n^{2/d}$. The upper bound is witnessed by the integer lattice: a $d$-dimensional grid $\{1,\dots,n^{1/d}\}^d$ has squared distances that are sums of $d$ squares each $<d\,n^{2/d}$, so $f_d(n)=O(n^{2/d})$ — this is the conjectured-tight construction. - Clarkson, Edelsbrunner, Guibas, Sharir, Welzl [CEGSW90] ("Combinatorial complexity bounds for arrangements of curves and spheres," Discrete Comput. Geom. 5 (1990)): $f_3(n) \gg n^{1/2}$ — the first (and for over a decade only) improvement over the trivial $n^{1/3}$ in $d=3$. - Aronov, Pach, Sharir, Tardos [APST04] ("Distinct distances in three and higher dimensions," STOC 2003 / Combin. Probab. Comput. 13 (2004), 283–293): $f_d(n) \gg n^{\frac{1}{d-90/77}-o(1)}$ for every $d\geq3$, e.g. $f_3(n)\gg n^{77/141-\epsilon}=n^{0.546\ldots}$. Technique: bound point–sphere incidences (the set of spheres centered at points of $P$ through another point of $P$) via a Chazelle–Friedman-style cutting/partition, with a delicate case split to handle "bad" configurations (many points on a circle whose axis also carries many points). Read directly from the paper's PDF (extracted via pypdf). - Solymosi, Vu [SoVu08] ("Near optimal bounds for the Erdős distinct distances problem in high dimensions," Combinatorica 28 (2008), 113–125): proved, *as a black-box recursion*, that any lower-bound exponent $\alpha_{d_0}$ known in dimension $d_0$ propagates to $$\alpha_d = \frac{2d}{(d+d_0+1)(d-d_0)+2d_0/\alpha_{d_0}}\quad(\text{codim-1 recursion, all }d\geq d_0),$$ with a sharper codim-2 variant for $d-d_0$ even. Plugging in the best 2008-era planar exponent, Tardos's $\alpha_2=0.8635$, gives $g_3(n)=\Omega(n^{0.5643})$ (their own headline Corollary 1.2, later pushed to $0.566$ "using additional arguments" not published in that note) and, in the limit of large $d$, the asymptotically-near-optimal $f_d(n) \gg_d n^{2/d - c/d^2}$ for all $d\geq4$ and some absolute $c>0$ (their abstract's own bound: $\Omega(n^{2/d-2/(d(d+2))})$) — matching the conjectured exponent $2/d$ up to a lower-order correction that $\to0$ as $d\to\infty$. - The current record, $d=3$: $f_3(n)\gg n^{3/5}$. This is *not* what Solymosi–Vu's 2008 paper itself proves (their own paper predates Guth–Katz by 7 years and only reaches $n^{0.5643}$). It is what erdosproblems.com explicitly records as "the consequence of combining [Solymosi–Vu's] method with the work of Guth and Katz on [89]": feed the (nearly) solved planar exponent $\alpha_2\to1$ (Guth–Katz, $\Omega(n/\log n)$) into the same codim-1 recursion formula above with $d=3,d_0=2$: $\alpha_3 = \tfrac{3\cdot1}{3\cdot1+2}=\tfrac35$. The improvement from $0.546$/$0.5643$ to $3/5$ for $d=3$ is entirely a consequence of the planar problem being solved — no new higher-dimensional argument was needed. - The gap that remains: conjectured $f_3(n)=n^{2/3-o(1)}$ (grid construction $\Theta(n^{2/3})$), current lower bound $n^{3/5}=n^{0.6}$ — still short of $n^{2/3}\approx n^{0.667}$. In general $d$, the recursion converts *any* future improvement to the planar exponent (i.e. any progress on closing Guth–Katz's remaining $\sqrt{\log n}$ gap, Erdős #89 — distinct distances in the plane) into an automatic, mechanical improvement in *every* dimension $d\geq3$ — but even feeding in the conjectured-optimal planar exponent $\alpha_2=1$ exactly (not just $1-o(1)$) does not, by this recursion alone, reach the conjectured $2/d$ exponent for any fixed finite $d$; it only approaches it as $d\to\infty$ (Corollary 1.4 of [SoVu08]: $g_d(n)=\Omega(n^{2/d-2/(d(d+2))})$ for $d\geq4$, which $\to n^{2/d}$ only in the limit). No published result found (search through 2026) closes this residual gap in any single fixed dimension $d\geq3$, and no post-2008 paper improving the Solymosi–Vu recursion's exponents themselves (as opposed to its 2D input) was found. - $f_d(n)$ is "essentially the inverse function" of $g_d(n)$, a *different*, separately numbered and already-solved Erdős problem erdos/1089 — but on the orthogonal asymptotic axis (fixed $n$, $d\to\infty$, vs. #1083's fixed $d$, $n\to\infty$); erdosproblems.com is explicit that the two problems' emphases are different regimes of the same underlying inverse relationship, so #1089 being solved does not resolve #1083. - No AI-system attempt on #1083 was surfaced in this search, and it is not marked formalized in Lean (erdosproblems.com/1083: "Formalised statement? No").

Solution

This page's "solution" is not to #1083 itself (open) but to its load-bearing input, #89, plus the transferable machine that exports that input to every dimension.

**1. The solved base case ($d=2$, Erdős #89 — distinct distances in the plane): Guth–Katz 2015.** L. Guth, N. Katz, "On the Erdős distinct distance problem in the plane," Annals of Math. 181(1) (2015), 155–190 (arXiv:1011.4105) proved $D(n)=\Omega(n/\log n)$ — the sharp polynomial exponent $1$, closing a gap open since 1946 except for a $\sqrt{\log n}$ log-factor. Technique (see Erdős #89 — distinct distances in the plane for full detail): the Elekes–Sharir reduction turns the distance problem into a point–line incidence problem in the group $SE(2)$ of planar rigid motions; a polynomial ham-sandwich cell decomposition partitions space so each cell meets few of the incidence-lines; the classical flecnode polynomial (Salmon, 19th c.) bounds points lying on many lines by showing those lines must lie on a low-degree ruled surface. This "polynomial method" is the origin event for a technique family later exported across incidence geometry (Kakeya-type and Zarankiewicz-type bounds).

2. The transferable idea that #1083 (and every $d\geq3$) borrows: Solymosi–Vu's dimension-reduction recursion, treating the lower-dimensional bound as a pluggable black box. The mechanism (full derivation in [SoVu08] §2, read directly from the PDF): - Given a point set $A\subset\mathbb R^d$, let $m$ be the largest number of points of $A$ lying on any single hyperplane (codimension 1). - Case $m$ large: that hyperplane, with $m$ points, is a copy of $\mathbb R^{d-1}$ — so the already-known $(d-1)$-dimensional bound $t_{d-1}(m)=\Omega(m^{\alpha_{d-1}})$ applies directly. - Case $m$ small: use a Chazelle–Friedman-style hyperplane/sphere space-partition (cutting $\mathbb R^d$ into $r$ cells so each is crossed by only $O(k/r^{1/d})$ of the relevant spheres) to show $t(A)=\Omega(n/m^{(d-1)/d})$ directly, with no dimension-reduction needed. - Optimizing the trade-off between the two cases via convexity (choosing $m$ to balance $n/m^{(d-1)/d}$ against $m^{\alpha_{d-1}}$) gives the closed-form recursion $$\alpha_d = \frac{d\,\alpha_{d-1}}{d\,\alpha_{d-1}+(d-1)}$$ (Corollary 2.3/2.4, Fact 2.5 of [SoVu08]), and an analogous sharper codimension-2 recursion for parity-matched $d-d_0$. - Why this is the "transferable" part: the recursion makes *no reference at all* to how $\alpha_{d_0}$ (the base-case exponent) was obtained — it is a pure black-box bootstrap. This means: the instant the 2D exponent improves (as it did in 2015, from Tardos's $0.8635$ to Guth–Katz's $1-o(1)$), the $d=3,4,5,\dots$ bounds improve automatically, by simply re-evaluating the same closed-form formula with the new $\alpha_2$ — no new $d\geq3$-specific geometric argument is required. This is exactly what happened with the $n^{3/5}$ record: it is Guth–Katz's *result*, not their *technique*, propagating through Solymosi–Vu's *technique*, not their *result*.

3. Bottom line for downstream use. Any future attack on #1083 in a *fixed* dimension $d\geq3$ has (at least) two independent levers, both already identified in the literature: (i) improve the *planar* input $\alpha_2$ further (attack Erdős #89 — distinct distances in the plane's residual $\sqrt{\log n}$ gap, or the strictly-harder pinned variant Erdős #604 — pinned distinct-distances at a single point) and re-run the existing Solymosi–Vu recursion — free, mechanical, no new $d\geq3$ mathematics; this is the concept page to link as `concept/dimension-reduction-recursion`; (ii) find a genuinely $d$-specific improvement to the recursion's *exponent formula itself* (Theorem 2.1/2.2 of [SoVu08]) — e.g. a better cutting/partition bound, or a smarter case split than the "large $m$ vs. small $m$" dichotomy — which would improve every dimension at once without touching the 2D base case. No published attempt at (ii) was found through 2026. Even in the best case ($\alpha_2$ pushed all the way to the conjectured optimum $1$), the recursion formula alone provably cannot reach the conjectured $2/d$ exponent in any fixed dimension (only asymptotically as $d\to\infty$) — so closing #1083 in, say, $d=3$ specifically requires *either* a third, currently-unknown lever, *or* a proof that the recursion itself is not tight.

Related

- Erdős #89 — distinct distances in the plane — the $d=2$ base case; solved up to a $\sqrt{\log n}$ factor (Guth–Katz 2015, arXiv:1011.4105); its exponent is the literal numeric input that determines the current record in every $d\geq3$ via the Solymosi–Vu recursion documented above. - Erdős #604 — pinned distinct-distances at a single point — the pinned/single-point distance problem in the plane; still stuck at the pre-Guth-Katz Katz–Tardos bound $n^{0.8641}$; any future improvement here would be a *second* possible 2D input to re-run the #1083 recursion with. - Erdős #661 — bipartite distinct-distances o(n/√log n) question is OPEN ($50); the underlying two-set function D(m,n) is SOLVED up to a log factor (Elekes construction 1995/1999, matching lower bounds by Mathialagan 2019) — bipartite/two-point-set distinct-distances variant in the plane. - erdos/1089 — the *inverse* function $g_d(n)$ (minimal point-set size forcing $n$ distinct distances); this sibling problem is solved (erdosproblems.com marks it SOLVED, via Bannai–Bannai–Stanton upper bound + a construction of Aletheia generalizing erdos/502) but on the orthogonal fixed-$n$/$d\to\infty$ axis, so its resolution does not transfer to #1083. - Polynomial method / slice rank (Croot-Lev-Pach, Ellenberg-Gijswijt) — Guth–Katz's cell-decomposition/flecnode-polynomial technique that solved the $d=2$ input. - Elekes–Sharir(–Guth–Katz) reduction: distinct distances → point-line incidences in SE(2) — the point–line-incidence-in-$SE(2)$ reduction underlying the $d=2$ solution. - concept/dimension-reduction-recursion — Solymosi–Vu's black-box hyperplane-section recursion (Combinatorica 28 (2008), 113–125): the transferable machinery that converts *any* improvement to a lower-dimensional distinct-distances exponent into an automatic improvement in every higher dimension; this is the concept every future #1083 attack should reuse rather than re-derive. - Incidence geometry: Szemerédi–Trotter theorem, the crossing lemma, and Zarankiewicz-type bounds — the broader point–sphere/point–line incidence-bound toolkit (Chazelle–Friedman cuttings, Szemerédi–Trotter-type theorems) used by both [APST04] and [SoVu08] to prove their respective recursive steps.