On distinct sums and distinct distances. (Q1418004): Difference between revisions

For a real \(n\) by \(s\) matrix \(A=(a_{ij})\) consider \(S(A)=\{a_{ij}+a_{ik}:1 \leq i\leq n,\;1\leq j<k\leq s\}\), the set of pairwise sums of entries from the same row. Let \(f_{s}(n)\) be the minimum size of \(S(A)\) for an \(n\) by \(s\) matrix with all its \(ns\) entries being pairwise disjoint. The main result of this paper is \(f_{s}(n)\geq n^{d_{s}}\), where \(d_{s}\) is defined explicitly and tends to \(e^{-1}\) as \(s\) goes to infinity. This is applied to the Erdős problem on the minimum number of distinct distances among \(n\) points in the plane. It is shown that this number is \(\Omega (n^{4e/(5e-1)-\varepsilon })\), where \(\varepsilon >0\) is arbitrary, thereby improving the bound \(\Omega (n^{6/7})\) of \textit{J. Solymosi} and \textit{Cs. D. Tóth} [Discrete Comput. Geom. 25, No. 4, 629--634 (2001; Zbl 0988.52027)]. The proof of the main result uses entropies and linear programs. For some small values of \(s,\) the numbers \(f_{s}(n)\) are determined more precisely by elementary methods.