Favorite Distances in High Dimensions

Let S be a set of n points in $${\mathbb{R}}^{d}$$ . Assign to each x ∈ S an arbitrary distance r(x) > 0. Let e r (x, S) denote the number of points in S at distance r(x) from x. Avis, Erdős, and Pach (1988) introduced the extremal quantity $${f}_{d}(n) =\max \sum\limits_{\mathbf{x}\in S}{e}_{r}(\mathbf{x},S)$$ , where the maximum is taken over all n-point subsets S of $${\mathbb{R}}^{d}$$ and all assignments $$r: S \rightarrow (0,\infty )$$ of distances. We give a quick derivation of the asymptotics of the error term of f d (n) using only the analogous asymptotics of the maximum number of unit distance pairs in a set of n points: $${f}_{d}(n) = \left(1 - \frac{1} {\lfloor d/2\rfloor }\right){n}^{2}+\left\{\begin{array}{@{}l@{\quad }l@{}} \Theta (n) \quad &\text{ if}\ d\ \text{ is even,} \\ \Theta {((n/d))}^{4/3})\quad &\text{ if}\ d\ \text{ is odd.} \end{array} \right.$$ The implied constants are absolute. This improves on previous results of Avis, Erdős, and Pach (1988) and Erdős and Pach (1990). Then we prove a stability result for d ≥ 4, asserting that if (S, r) with $$\left\vert S\right\vert = n$$ satisfies $${e}_{r}(S) = {f}_{d}(n) - o({n}^{2})$$ , then, up to o(n) points, S is a Lenz construction with r constant. Finally, we use stability to show that for n sufficiently large (depending on d), the pairs (S, r) that attain f d (n) are up to scaling exactly the Lenz constructions that maximize the number of unit distance pairs with r ≡ 1, with some exceptions in dimension 4. Analogous results hold for the furthest-neighbor digraph, where r is fixed to be $$r(\mathbf{x}) {=\max }_{\mathbf{y}\in S}\vert \mathbf{x}\mathbf{y}\vert$$ for x ∈ S.