A set $cal P$ 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 $cal P$ 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 $text{const}_dcdot 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 - 1 leq 8$, and for each $d$ it lies in $left[left({datop 2}right), left({d + 1atop 2}right)right]$. For $d eq 4,5$ we can replace unit intervals by intervals of length $text{const}_d cdot n^{1/d}$, and the maximum is the respective Turan number, for $n geq n(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 Turan number $T(n, (d + 1)^k + 1)$. Several of these results were announced earlier by Makai-Pach-Spencer.
Download