On rich lines in grids

DOI10.1007/S00454-010-9250-7zbMATH Open1192.52026arXiv0807.2420OpenAlexW2091642380MaRDI QIDQ972613FDOQ972613

Authors: Evan Borenstein, Ernie Croot 

Publication date: 21 May 2010

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Abstract: In this paper we show that if one has a grid A x 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^epsilon distinct slopes, and where each line is parallel to n^epsilon others (so, at least n^(2 epsilon) lines in total), then at least one of these lines must fail to be ``rich. This result immediately implies non-trivial sum-product 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|.

Full work available at URL: https://arxiv.org/abs/0807.2420

Recommendations

• Sets of rich lines in general position
• Upper and lower bounds for rich lines in grids
• On the number of rich lines in truly high dimensional sets
• On grids in point-line arrangements in the plane
• scientific article; zbMATH DE number 4015582

zbMATH Keywords

additive combinatoricspoint-line configurationssum-product inequalitiesErdös-type problemsSzemerédi-Trotter inequality

Mathematics Subject Classification ID

Erd?s problems and related topics of discrete geometry (52C10) Planar arrangements of lines and pseudolines (aspects of discrete geometry) (52C30)

Cites Work

• A sum-product estimate in finite fields, and applications
• On the number of sums and products
• Extremal problems in discrete geometry
• Title not available (Why is that?)
• Title not available (Why is that?)
• Mapping incidences
• Growth and generation in \(\text{SL}_2(\mathbb{Z}/p\mathbb{Z})\).

Cited In (7)

• Geometric progressions in sumsets over finite fields
• Upper and lower bounds for rich lines in grids
• A note on rich lines in truly high dimensional sets
• Formulas for the number of gridlines
• Title not available (Why is that?)
• Sets of rich lines in general position
• On grids in point-line arrangements in the plane

This page was built for publication: On rich lines in grids

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q972613)