Near optimal bounds for the Erdős distinct distances problem in high dimensions (Q949786)

One of Erdős' most famous questions in combinatorial geometry is to determine \(g_d(n)\), the minimum number of distinct distances that can occur between \(n\) points in \(\mathbb R^d\). An appropriately scaled integer lattice shows that \(g_d(n)=O(n^{2/d})\). It is conjectured that \(g_d(n)\) is not far from this bound when \(d\) is large. In this paper it is shown that \(g_3(n)=\Omega(n^{0.5643})\) and \(g_d(n)=\Omega(n^{\frac{2}{d}-\frac{2}{d(d+2)}})\) for all \(d\geq 4\). These bounds improve the previous records of \textit{B. Aronov, J. Pach, M. Sharir}, and \textit{G. Tardos} [Comb. Probab. Comput. 13, 283-293 (2004; Zbl 1052.52010)]. In fact, slightly better bounds are proven which follow from two recursive lower bounds that depend on the maximum number of points that lie on a hyperplane of codimension \(1\) and codimension \(2\), respectively. The proof is a clever counting argument based on a modification of the cutting lemma of \textit{B. Chazelle} and \textit{J. Friedman} [Combinatorica 10, 229-449 (1990; Zbl 0715.68036)].