Dvir, Zeev ;
Gopi, Sivakanth
On the Number of Rich Lines in Truly High Dimensional Sets
Abstract
We prove a new upper bound on the number of rrich lines (lines with at least r points) in a 'truly' ddimensional configuration of points v_1,...,v_n over the complex numbers. More formally, we show that, if the number of rrich lines is significantly larger than n^2/r^d then there must exist a large subset of the points contained in a hyperplane. We conjecture that the factor r^d can be replaced with a tight r^{d+1}. If true, this would generalize the classic SzemerediTrotter theorem which gives a bound of n^2/r^3 on the number of rrich lines in a planar configuration. This conjecture was shown to hold in R^3 in the seminal work of Guth and Katz and was also recently proved over R^4 (under some additional restrictions) by Solomon and Sharir. 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 ddimensional grid achieves the largest number of rterm 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 r2 Veronese embedding takes rcollinear points to r linearly dependent images. Hence, each collinear rtuple of points, gives us a dependent rtuple of images. We then use the designmatrix method of Barak et al. 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.
BibTeX  Entry
@InProceedings{dvir_et_al:LIPIcs:2015:5111,
author = {Zeev Dvir and Sivakanth Gopi},
title = {{On the Number of Rich Lines in Truly High Dimensional Sets}},
booktitle = {31st International Symposium on Computational Geometry (SoCG 2015)},
pages = {584598},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897835},
ISSN = {18688969},
year = {2015},
volume = {34},
editor = {Lars Arge and J{\'a}nos Pach},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/5111},
URN = {urn:nbn:de:0030drops51110},
doi = {10.4230/LIPIcs.SOCG.2015.584},
annote = {Keywords: Incidences, Combinatorial Geometry, Designs, Polynomial Method, Additive Combinatorics}
}
12.06.2015
Keywords: 

Incidences, Combinatorial Geometry, Designs, Polynomial Method, Additive Combinatorics 
Seminar: 

31st International Symposium on Computational Geometry (SoCG 2015)

Issue date: 

2015 
Date of publication: 

12.06.2015 