Problem Statement
Let $g_d(n)$ be minimal such that every collection of $g_d(n)$ points in $\mathbb{R}^d$ determines at least $n$ many distinct distances. Estimate $g_d(n)$. In particular, does\[\lim_{d\to \infty}\frac{g_d(n)}{d^{n-1}}\]exist?
Categories:
Geometry Distances
Progress
A question of Kelly. Erdős [Er75f] writes it is 'easy' to see that $g_d(n)\gg d^{n-1}$. Erdős and Straus proved (in unpublished work mentioned in [Er75f]) that\[g_d(n) \leq c^{d^{1-b_n}}\]for some constants $c>0$ and $b_n>0$.It is trivial that $g_1(3)=4$, and easy to see that $g_2(3)=6$. Croft [Cr62] proved $g_3(3)=7$. The vertices of a $d$-dimensional cube demonstrate that\[g_d(d+1)>2^d.\]The function $g_d(n)$ is essentially the inverse of the function $f_d(n)$ considered in [1083] - with our definitions, $g_d(n)>m$ if and only if $f_d(m)<n$. The emphasis in this problem is, however, on the behaviour for fixed $n$ as $d\to\infty$.
Source: erdosproblems.com/1089 | Last verified: January 19, 2026