Problem #1083: Let $d\geq 3$, and let $f_d(n)$ be the minimal $m$ such...

---

Progress

A generalisation of the distinct distance problem [89] to higher dimensions. Erdős [Er46b] proved\[n^{1/d}\ll_d f_d(n)\ll_d n^{2/d},\]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\[ f_d(n)\gg_d n^{\frac{2}{d}-\frac{c}{d^2}}\]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$.