Convexity, Elementary Methods, and Distances

This paper considers an extremal version of the Erdős distinct distances problem. For a point set \(P \subset {\mathbb {R}}^d\) $P\subset {\mathbb{R}}^d$ , let \(\Delta (P)\) $\mathrm{\Delta }(P)$ denote the set of all Euclidean distances determined by P. Our main result is the following: if \(\Delta (A^d) \ll |A|^2\) $\mathrm{\Delta }(A^d)\ll {|A|}^2$ and \(d \ge 5\) $d\ge 5$ , then there exists \(A' \subset A\) $A^{\prime }\subset A$ with \(|A'| \ge |A|/2\) $|A^{\prime }|\ge |A|/2$ such that \(|A'-A'| \ll |A| \log |A|\) $|A^{\prime }-A^{\prime }|\ll |A|log|A|$ . This is one part of a more general result, which says that, if the growth of \(|\Delta (A^d)|\) $|\mathrm{\Delta }(A^d)|$ is restricted, it must be the case that A has some additive structure. More specifically, for any two integers k, n, we have the following information: if \(\begin{aligned} | \Delta (A^{2k+3})| \le |A|^n \end{aligned}\) $$\begin{array}{c}\hfill |\mathrm{\Delta }(A^{2k+3}){|\le |A|}^n\end{array}$$ then there exists \(A' \subset A\) $A^{\prime }\subset A$ with \(|A'| \ge |A|/2\) $|A^{\prime }|\ge |A|/2$ and \(\begin{aligned} | kA'- kA'| \le k^2|A|^{2n-3}\log |A|. \end{aligned}\) $$\begin{array}{c}\hfill |k{A}^{\prime }-k{A}^{\prime }|\le k^2{|A|}^{2n-3}log|A|.\end{array}$$ These results are higher dimensional analogues of a result of Hanson [4], who considered the two-dimensional case.