Convexity, Elementary Methods, and Distances

Abstract

This paper considers an extremal version of the Erdős distinct distances problem. For a point set $P\subset {\mathbb{R}}^d$, let $\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$ and $d\ge 5$, then there exists $A^{\prime }\subset A$ with $|A^{\prime }|\ge |A|/2$ such that $|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)|$ 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 \[ | Δ(A^{2k+3})| \leq |A|^n \] then there exists $A^{\prime }\subset A$ with $|A^{\prime }|\ge |A|/2$ and \[ | kA'- kA'| \leq k^2|A|^{2n-3}\log|A|. \] These results are higher dimensional analogues of a result of Hanson, who considered the two-dimensional case.