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.
- Crossing Numbers and Hard Erdős Problems in Discrete Geometry
- Crossing-Free Subgraphs
- Distinct distances in the plane
- Extremal problems in discrete geometry
- scientific article; zbMATH DE number 1017008 (Why is no real title available?)
- Isosceles triangles determined by a planar point set
- On characterization of entropy function via information inequalities
- On Sets of Distances of n Points
- On the Different Distances Determined by n Points
- The number of different distances determined by a set of points in the Euclidean plane
- The number of different distances determined by n points in the plane
- Extremal problems on triangle areas in two and three dimensions
- On distinct distances among points in general position and other related problems
- Distinct distances and arithmetic progressions
- On distinct distances between a variety and a point set
- A new upper bound for the size of \(s\)-distance sets in boxes
- On an application of Guth-Katz theorem
- Finite point configurations in the plane, rigidity and Erdős problems
- On bipartite distinct distances in the plane
- Distinct distances on non-ruled surfaces and between circles
- Bisector energy and few distinct distances
- Partition-equivalent n-points configurations with two distances
- scientific article; zbMATH DE number 2145235 (Why is no real title available?)
- scientific article; zbMATH DE number 2145244 (Why is no real title available?)
- On the Erdős distinct distances problem in the plane
- Distinct distances in the complex plane
- Incidences in three dimensions and distinct distances in the plane
- On Erdős chains in the plane
- A note on the number of distinct distances
- Distinct distances with \(\ell_p\) metrics
- On the Minkowski distances and products of sum sets
- Near optimal bounds for the Erdős distinct distances problem in high dimensions
- A note on the number of different inner products generated by a finite set of vectors
- On distinct distances and \(\lambda \)-free point sets
This page was built for publication: On distinct sums and distinct distances.
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1418004)
