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$, let $\mathrm{\Delta }(P)$ denote the set of all Euclidean distances determined by $P$. Our main result is the following: if $\mathrm{\Delta }(A^d)\ll \mathrm{\mid }A{\mathrm{\mid }}^2$ and $d\ge 5$, then there exists $A^{\mathrm{\prime }}\subset A$ with $\mathrm{\mid }{A}^{\mathrm{\prime }}\mathrm{\mid }\ge \mathrm{\mid }A\mathrm{\mid }\mathrm{/}2$ such that $\mathrm{\mid }{A}^{\mathrm{\prime }}-A^{\mathrm{\prime }}\mathrm{\mid }\ll \mathrm{\mid }A\mathrm{\mid }\log \mathrm{\mid }A\mathrm{\mid }$. This is one part of a more general result, which says that, if the growth of $\mathrm{\mid }\mathrm{\Delta }(A^d)\mathrm{\mid }$ 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 $$\mathrm{\mid }\mathrm{\Delta }(A^{2k+3})\mathrm{\mid }\le \mathrm{\mid }A{\mathrm{\mid }}^n$$ then there exists $A^{\mathrm{\prime }}\subset A$ with $\mathrm{\mid }{A}^{\mathrm{\prime }}\mathrm{\mid }\ge \mathrm{\mid }A\mathrm{\mid }\mathrm{/}2$ and $$\mathrm{\mid }k{A}^{\mathrm{\prime }}-k{A}^{\mathrm{\prime }}\mathrm{\mid }\le k^2\mathrm{\mid }A{\mathrm{\mid }}^{2n-3}\log \mathrm{\mid }A\mathrm{\mid }\mathrm{.}$$ These results are higher dimensional analogues of a result of Hanson, who considered the two-dimensional case.