Upper and lower bounds for rich lines in grids

Research output: Contribution to journalArticle (Academic Journal)peer-review

Abstract

We prove upper and lower bounds for the number of lines in general position that are rich in a Cartesian product point set. This disproves a conjecture of Solymosi and improves work of Elekes, Borenstein and Croot, and Amirkhanyan, Bush, Croot, and Pryby. The upper bounds are based on a version of the asymmetric Balog-Szemeredi-Gowers theorem for group actions combined with product theorems for the affine group. The lower bounds are based on a connection between rich lines in Cartesian product sets and amenability (or expanding families of graphs in the finite field case). As an application of our upper bounds for rich lines in grids, we give a geometric proof of the asymmetric sum-product estimates of Bourgain and Shkredov.
Original languageEnglish
JournalAmerican Journal of Mathematics
Publication statusSubmitted - 29 Sep 2017

Keywords

  • math.CO

Fingerprint Dive into the research topics of 'Upper and lower bounds for rich lines in grids'. Together they form a unique fingerprint.

Cite this