On rich lines in grids (Q972613)

The authors prove that for every \(\epsilon > 0\), there exists \(\delta > 0\) so that the following holds for all \(n\in \mathbb{N}\) sufficiently large: Suppose that \(A\) and \(B\) are sets of real numbers of size \(n\), and that one has a family of lines such that {\parindent5mm \begin{itemize}\item[1)] there are at least \(n^{\epsilon}\) different slopes among them; and, \item[2)] every line is parallel to at least \(n^{\epsilon}\) other lines. \end{itemize}} Then, at least one of the lines must hit the grid \(A \times B\) in fewer than \(n^{1-\delta}\) points. In this case it is said that at least one of the lines of this family (with size al least \(n^{2 \epsilon}\)) must fail to be ``rich''. One of the ingredients of the proof is the Szemerédi-Trotter inequality, but the proof makes also use of several methods in additive combinatorics in a quite intricate and technical way. The result proved in this paper is considerably stronger than some previous results obtained before. This theorem also immediately implies non-trivial sum-product inequalities.