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|.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Bourgain, J., Katz, N., Tao, T.: A sum–product estimate in finite fields, and applications. Geom. Funct. Anal. 14, 27–57 (2004)
Erdős, P., Szemerédi, E.: On sums and products of integers. In: Studies in Pure Mathematics, pp. 213–218. Birkhäuser, Basel (1983)
Elekes, G.: On the number of sums and products. Acta Arith. 81, 365–367 (1997)
Elekes, G.: Sums versus products in number theory, algebra and Erdős geometry. Paul Erdős and His Mathematics, II (Budapest, 1999), Bolyai Soc. Math. Stud., vol. 11, pp. 241–290, János Bolyai Math. Soc. (2002)
Helfgott, H.: Growth and generation in SL 2(ℤ/pℤ). Ann. Math. 167, 601–623 (2008)
Helfgott, H.: Growth and generation in SL 3(ℤ/pℤ). To appear in J. Eur. Math. Soc.
Szemerédi, E., Trotter, W.T.: Extremal problems in discrete geometry. Combinatorica 3, 381–392 (1983)
Wood, M.M., Wood, P.M., Vu, V.: Mapping incidences. arXiv:0711.4407
Author information
Authors and Affiliations
Corresponding author
Additional information
E. Borenstein summer funding supported by an NSF VIGRE grant.
E. Croot supported in part by an NSF grant.
Rights and permissions
About this article
Cite this article
Borenstein, E., Croot, E. On Rich Lines in Grids. Discrete Comput Geom 43, 824–840 (2010). https://doi.org/10.1007/s00454-010-9250-7
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00454-010-9250-7