Two nearly equal distances in R^d

arXiv1901.01055MaRDI QIDQ6311998FDOQ6311998

Authors: Péter L. Erdős, E. jun. Makai, János Pach 

Publication date: 4 January 2019

Abstract: A set $calP$ of $n$ points in $R^d$ is separated if all distances of distinct points are at least~$1$. Then we may ask how many of these distances, with multiplicity, lie in an interval $[t,t+1]$. The authors and J. Spencer proved that the maximum is $(n^2/2)(1-1/d)+O(1)$. The authors showed that for $d=2$ and $calP$ separated, the maximal number of distances, with multiplicity, in the union of $k$ unit intervals is $(n^2/2)$ $(1-1/(k+1)+o(1))$. (In these papers the unit intervals could be replaced by intervals of length $ext{const}_{d}cdot{n}^{1/d}$.) In this paper we show that for $k=2$, and for any $n$, this maximal number is $(n^2/2)(1-1/m_{d-1}+o(1))$, where $m_{d-1}$ is the maximal size of a two-distance set in $R^{d-1}$. (The value of $m_{d-1}$ is known for $d-1leq8$, and for each $d$ it lies in $left[left(datop2ight),left(d+1atop2ight)ight]$. For $deq4,5$ we can replace unit intervals by intervals of length $ext{const}_{d}cdot{n}^{1/d}$, and the maximum is the respective Tur'an number, for $ngeqn(d)$.) We also investigate a variant of this question, namely with $k$ intervals of the form $[t,t(1+varepsilon)]$, for $varepsilon<varepsilon(d,k)$, and for $n>n(d,k)$. Here the maximal number of distances, with multiplicity, in the union of $k$ such intervals is the Tur'an number $T(n,(d+1{)}^k+1)$. Several of these results were announced earlier by Makai-Pach-Spencer.

Mathematics Subject Classification ID

Erd?s problems and related topics of discrete geometry (52C10)

This page was built for publication: Two nearly equal distances in $R^d$

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6311998)