Problem Statement
Let $f_d(n)$ be minimal such that in any collection of $n$ points in $\mathbb{R}^d$, all of distance at least $1$ apart, there are at most $f_d(n)$ many pairs of points which are distance $1$ apart. Estimate $f_d(n)$.
Categories:
Geometry Distances
Progress
It is easy to see that $f_1(n)=n-1$ and $f_2(n)<3n$ (since there can be at most $6$ points of distance $1$ from any point). Erdős [Er46b] showed\[f_2(n)<3n-cn^{1/2}\]for some constant $c>0$, which the triangular lattice shows is the best possible up to the value of $c$. In [Er75f] he speculated that the triangular lattice is exactly the best possible, and in particular\[f_2(3n^2+3n+1)=9n^2+6n.\]In [Er75f] he claims the existence of $c_1,c_2>0$ such that\[6n-c_1n^{2/3}< f_3(n) < 6n-c_2n^{2/3}.\]See [223] for the analogous problem with maximal distance $1$.Source: erdosproblems.com/1084 | Last verified: January 19, 2026