Erdős Problem #1083

declared status 'open'. Formalized: no. 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)}?$$ Current best: Erd\H{o}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. {UL} {LI} Clarkson, Edelsbrunner, Gubias, Sharir, and Welzl [CEGSW90] proved $f_3(n)\gg n^{1/2}$.{/LI} {LI}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}$).{/LI} {LI}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$. Prize: no. OEIS: A186704. Tags: distances, geometry.

Notation is rendered from the stored source. The pinned checkout remains the exact record.