Erdős Problem #1084

declared status 'open'. Formalized: yes. 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)$. Current best: Erd\H{o}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$. Prize: no. OEIS: A045945. Tags: distances, geometry.

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