OPEN
This is open, and cannot be resolved with a finite computation.
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)$.
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$.
View the LaTeX source
This page was last edited 15 October 2025.
When referring to this problem, please use the original sources of Erdős. If you wish to acknowledge this website, the recommended citation format is:
T. F. Bloom, Erdős Problem #1084, https://www.erdosproblems.com/1084, accessed 2026-01-16
