Skip to main content

On the Number of Rich Lines in Truly High Dimensional Sets

Author(s): Dvir, Zeev; Gopi, Sivakanth

Download
To refer to this page use: http://arks.princeton.edu/ark:/88435/pr1qq2r
Full metadata record
DC FieldValueLanguage
dc.contributor.authorDvir, Zeev-
dc.contributor.authorGopi, Sivakanth-
dc.date.accessioned2018-07-20T15:06:22Z-
dc.date.available2018-07-20T15:06:22Z-
dc.date.issued2015en_US
dc.identifier.citationDvir, Z, Gopi, S. (2015). On the Number of Rich Lines in Truly High Dimensional Sets. 34 (584 - 598. doi:10.4230/LIPIcs.SOCG.2015.584en_US
dc.identifier.urihttp://arks.princeton.edu/ark:/88435/pr1qq2r-
dc.description.abstractWe prove a new upper bound on the number of r-rich lines (lines with at least r points) in a truly d-dimensional configuration of points v1, . . . , vn ε ℂd. More formally, we show that, if the number of r-rich lines is significantly larger than n2/rd then there must exist a large subset of the points contained in a hyperplane. We conjecture that the factor rd can be replaced with a tight rd+1. If true, this would generalize the classic Szemerédi-Trotter theorem which gives a bound of n2/r3 on the number of r-rich lines in a planar configuration. This conjecture was shown to hold in R3 in the seminal work of Guth and Katz [7] and was also recently proved over R4 (under some additional restrictions) [14]. For the special case of arithmetic progressions (r collinear points that are evenly distanced) we give a bound that is tight up to lower order terms, showing that a d-dimensional grid achieves the largest number of r-term progressions. The main ingredient in the proof is a new method to find a low degree polynomial that vanishes on many of the rich lines. Unlike previous applications of the polynomial method, we do not find this polynomial by interpolation. The starting observation is that the degree r - 2 Veronese embedding takes r-collinear points to r linearly dependent images. Hence, each collinear r-tuple of points, gives us a dependent r-tuple of images. We then use the design-matrix method of [1] to convert these local linear dependencies into a global one, showing that all the images lie in a hyperplane. This then translates into a low degree polynomial vanishing on the original set.en_US
dc.format.extent584 - 598en_US
dc.language.isoen_USen_US
dc.relation.ispartof31st International Symposium on Computational Geometry, SoCG 2015en_US
dc.rightsAuthor's manuscripten_US
dc.titleOn the Number of Rich Lines in Truly High Dimensional Setsen_US
dc.typeConference Articleen_US
dc.identifier.doidoi:10.4230/LIPIcs.SOCG.2015.584-
dc.date.eissued2015en_US
pu.type.symplectichttp://www.symplectic.co.uk/publications/atom-terms/1.0/journal-articleen_US

Files in This Item:
File Description SizeFormat 
On the Number of Rich Lines in Truly High Dimensional Sets.pdf199.89 kBAdobe PDFView/Download


Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.