Distinct distances in homogeneous sets in Euclidean space (Q2498934): Difference between revisions

The distinct distance problem goes back to Erdős and asks for the minimal number~\(g_d(n)\) of distinct distances determined by \(n\) points in \(d\)-space. The example of the \(d\)-dimensional integer grid \([1,2,\dots,n^{1/d}]^d\) shows that \(g_d(n)=O(n^{2/d})\) for \(n\geq 2\), and in particular \(g_2(n)=O(n/\sqrt{\log n})\). An initial lower bound of \(g_2(n)=\Omega(\sqrt{n})\) by Erdős was subsequently improved by various authors; the most recent result along these lines is by \textit{László A. Székely} [Comb. Probab. Comput. 6, No. 3, 353--358 (1997; Zbl 0882.52007)]. In this paper, the authors prove that homogeneous sets of \(n\) points in \(d\)-space determine at least \[ \Omega( n^{2d/(d^2+1)} / \log^{(1-d^2)/(d^2+1)}n) \] distinct distances. In their terminology, a finite point set \(P\subset\mathbb R^d\) is homogeneous if every axis-parallel unit cube in~\(\mathbb R^d\) contains at most \(O(1)\)~points, and the entire point set \(P\) is contained in an axis-parallel cube of volume \(| P| \). In dimension \(d=3\), they provide a slightly better lower bound of \[ \Omega(n^{53/87})= \Omega(n^{0.6091}) \] distinct distances determined by \(P\). A key lemma is an extension of an earlier result of \textit{József Solymosi} and \textit{Van Vu} [Contemp. Math. 342, 259--268 (2004; Zbl 1064.52011)], to the effect that for any \(d,k\in \mathbb N\), \(1\leq k<d\), there is a constant \(c_{d,k}\) such that \[ f_{d,k}(n,m)\leq c_{d,k}\frac{n^{k+1}}{m^{d+1}}, \] where \(f_{d,k}(n,m)\) is the maximum over all homogeneous \(n\)-point sets \(P\subset\mathbb R^d\) of the maximal number of \(k\)-flats containing \(m\) points of~\(P\).