Convexity, Elementary Methods, and Distances

This paper considers an extremal version of the Erdős distinct distances problem. For a point set P ⊂ Rᵈ, let $Δ(P)$ denote the set of all Euclidean distances determined by P. Our main result is the following: if Δ(Aᵈ) |A|² and d ≥ 5, then there exists A' ⊂ A with |A'| ≥ |A|/2 such that |A'-A'| |A| log |A|. This is one part of a more general result, which says that, if the growth of |Δ(Aᵈ)| 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²ᵏ⁺³)| ≤ |A|^n \] then there exists A' ⊂ A with |A'| ≥ |A|/2 and \[ | kA'- kA'| ≤ k^2|A|²ⁿ⁻³log|A|. \] These results are higher dimensional analogues of a result of Hanson, who considered the two-dimensional case.