Problem Statement
Let $f_d(n)$ be the minimal $m$ such that any set of $m$ points in $\mathbb{R}^d$ contains a set of $n$ points such that any two determined distances are distinct. Estimate $f_d(n)$. In particular, is it true that, for fixed $n\geq 3$,\[f_d(n)=2^{o(d)}?\]
Categories:
Geometry
Progress
It is easy to prove that $f_d(n) \leq n^{O_d(1)}$. Erdős [Er75f] claimed that he and Straus proved $f_d(n)\leq c_n^d$ for some constant $c_n>0$.When $d=1$ this is the subject of [530], and $f_1(n)\asymp n^2$.
When $n=3$ this is the subject of [503]. Erdős could prove $f_2(3)=7$ and Croft [Cr62] proved $f_3(3)=9$. The results described at [503] demonstrate that $f_d(3)=d^2/2+O(d)$.
Source: erdosproblems.com/1088 | Last verified: January 19, 2026