Erdős #1083 · geometry / distances

A generalisation of the distinct distance problem [89] to higher dimensions. Erdős [Er46b] proved

the upper bound construction being given by a set of lattice points.

• Clarkson, Edelsbrunner, Gubias, Sharir, and Welzl [CEGSW90] proved $f_3(n)\gg n^{1/2}$.
• Aronov, Pach, Sharir, and Tardos [APST04] proved $f_d(n)\gg n^{\frac{1}{d-90/77}-o(1)}$ for any $d\geq 3$ (for example, $f_3(n)\gg n^{0.546}$).
• Solymosi and Vu [SoVu08] proved $f_3(n) \gg n^{3/5}$ and

for all $d\geq 4$ for some constant $c>0$. (The result in their paper for $d=3$ is slightly weaker than stated here, but uses as a black box the bound for distinct distances in $2$ dimensions; we have recorded the consequence of combining their method with the work of Guth and Katz on [89].) The function $f_d(n)$ is essentially the inverse of the function $g_d(n)$ considered in [1089] - with our definitions, $g_d(n)>m$ if and only if $f_d(m)<n$. The emphasis in this problem is, however, on the behaviour as $d$ is fixed and $n\to \infty$.

The source labels this entry OPEN in the 2026-09-08 snapshot. Editorial progress notes are reproduced as source commentary, not independently verified results. Prize amounts and Lean badges at the source are not local awards or verification.