On Rich Lines in Grids

On Rich Lines in Grids: "

Abstract In this paper we show that if one has a grid A×B, where A and B are sets of n real numbers, then there can be only very few “rich” lines in certain quite small families. Indeed, we show that if the family
has lines taking on n

^ε
distinct slopes, and where each line is parallel to n

^ε
others (so, at least n
^2ε
lines in total), then at least one of these lines must fail to be “rich”. This result immediately implies non-trivial sumproduct
inequalities; though, our proof makes use of the Szemeredi-Trotter inequality, which Elekes used in his argument for lower
bounds on |C+C|+|C.C|.

• Content Type Journal Article
• DOI 10.1007/s00454-010-9250-7
• Authors
  
  
  • Evan Borenstein, Georgia Institute of Technology School of Mathematics 103 Skiles Atlanta GA 30332 USA
  • Ernie Croot, Georgia Institute of Technology School of Mathematics 103 Skiles Atlanta GA 30332 USA
  
  

• Journal Discrete and Computational Geometry
• Online ISSN 1432-0444
• Print ISSN 0179-5376

"