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

From MaRDI portal
scientific article
Language Label Description Also known as
English
Near optimal bounds for the Erdős distinct distances problem in high dimensions
scientific article

    Statements

    Near optimal bounds for the Erdős distinct distances problem in high dimensions (English)
    0 references
    0 references
    0 references
    21 October 2008
    0 references
    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)].
    0 references
    distinct distance problem
    0 references
    Erdős problem
    0 references
    cutting lemma
    0 references
    combinatorial geometry
    0 references

    Identifiers