On distinct sums and distinct distances.

The paper (Discrete Comput. Geom. 25 (2001) 629) of Solymosi and Tóth implicitly raised the following arithmetic problem. Consider 𝑛 pairwise disjoint s element sets and form all (s2)n sums of pairs of elements of the same set. What is the minimum number of distinct sums one can get this way? This paper proves that the number of distinct sums is at least 𝑛ds, where ds=1/c⌈s/2⌉ is defined in the paper and tends to e−1 as s goes to infinity. Here e is the base of the natural logarithm. As an application we improve the Solymosi–Tóth bound on an old Erdo&x030B;s problem: we prove that n distinct points in the plane determine Ω(n4e5e−1−ϵ) distinct distances, where ϵ>0 is arbitrary. Our bound also finds applications in other related results in discrete geometry. Our bounds are proven through an involved calculation of entropies of several random variables. [Copyright &y& Elsevier]