Problem Statement
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)$.
Categories:
Geometry Distances
Progress
The most difficult cases are $d=2$ and $d=3$. 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ős [Er46b] and the upper bound by Spencer, Szemeré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ő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ős [Er60b] showed that the Erdős-Stone theorem implies\[f_d(n) \leq \left(\frac{p-1}{2p}+o(1)\right)n^2\]for $d\geq 4$.
Erdős [Er67e] determined $f_d(n)$ up to $O(1)$ for all even $d\geq 4$. Brass [Br97] determined $f_4(n)$ exactly. Swanepoel [Sw09] determined $f_d(n)$ exactly for even $d\geq 6$. For odd $d\geq 5$ Erdős and Pach [ErPa90] proved that there exist constants $c_1(d),c_2(d)>0$ such that\[\frac{p-1}{2p}n^2 +c_1n^{4/3}\leq f_d(n) \leq \frac{p-1}{2p}n^2 +c_2n^{4/3}.\]
Source: erdosproblems.com/1085 | Last verified: January 19, 2026