Problem 1085

Erdős Problem #1085: declared status 'open'. Formalized: yes. Let $f_d(n)$ be minimal such that, in any set of $n$ points in $\mathbb{R}^d$, there exist at most $f_d(n)$ pairs of points which distance $1$ apart. Estimate $f_d(n)$. Current best: When $d=2$ this is the unit distance problem [90], and the best known bounds are$$n^{1+\frac{c}{\log\log n}}< f_2(n) \ll n^{4/3}$$for some constant $c>0$, the lower bound by Erd\H{o}s [Er46b] and the upper bound by Spencer, Szemer\'{e}di, and Trotter [SST84]. When $d=3$ the best known bounds are$$n^{4/3}\log\log n \ll f_3(n) \ll n^{3/2}\beta(n)$$where $\beta(n)$ is a very slowly growing function, the lower bound by Erd\H{o}s [Er60b] and the upper bound by Clarkson, Edelsbrunner, Guibas, Sharir, and Welzl [CEGSW90]. A construction of Lenz (taking points on orthogonal circles) shows that, for $d\geq 4$,$$f_d(n)\geq \frac{p-1}{2p}n^2-O(1)$$with $p=\lfloor d/2\rfloor$. Erd\H{o}s [Er60b] showed that the Erd\H{o}s-Stone theorem implies$$f_d(n) \leq \left(\frac{p-1}{2p}+o(1)\right)n^2$$for $d\geq 4$. Prize: no. OEIS: A186705. Tags: distances, geometry.