We prove a new upper bound on the number of @math -rich lines (lines with at least @math points) in a truly' @math -dimensional configuration of points @math . More formally, we show that, if the number of @math -rich lines is significantly larger than @math then there must exist a large subset of the points contained in a hyperplane. We conjecture that the factor @math can be replaced with a tight @math . If true, this would generalize the classic Szemer 'edi-Trotter theorem which gives a bound of @math on the number of @math -rich lines in a planar configuration. This conjecture was shown to hold in @math in the seminal work of Guth and Katz GK10 and was also recently proved over @math (under some additional restrictions) SS14 . For the special case of arithmetic progressions ( @math collinear points that are evenly distanced) we give a bound that is tight up to low order terms, showing that a @math -dimensional grid achieves the largest number of @math -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 @math Veronese embedding takes @math -collinear points to @math linearly dependent images. Hence, each collinear @math -tuple of points, gives us a dependent @math -tuple of images. We then use the design-matrix method of BDWY12 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.
Similarly, using the results of in @cite_10 , we can prove the following theorem from which a slightly weaker version of Conjecture in @math trivially follows (see Appendix ). We are not aware of any examples where points arranged on a quadric hypersurface in @math result in significantly more rich lines than in a four dimensional grid. It is, however, possible that one needs to weaken Conjecture so that for some @math , an @math -dimensional hypersurface of constant degree (possibly depending on @math ) contains @math points.
@cite_10
326952175 1645016350 2963573981 2128943288
We prove an incidence theorem for points and planes in the projective space @math over any field @math , whose characteristic @math An incidence is viewed as an intersection along a line of a pair of two-planes from two canonical rulings of the Klein quadric. The Klein quadric can be traversed by a generic hyperplane, yielding a line-line incidence problem in a three-quadric, the Klein image of a regular line complex. This hyperplane can be chosen so that at most two lines meet. Hence, one can apply an algebraic theorem of Guth and Katz, with a constraint involving @math if @math . This yields a bound on the number of incidences between @math points and @math planes in @math , with @math as @math where @math is the maximum number of collinear planes, provided that @math if @math . Examples show that this bound cannot be improved without additional assumptions. This gives one a vehicle to establish geometric incidence estimates when @math . For a non-collinear point set @math and a non-degenerate symmetric or skew-symmetric bilinear form @math , the number of distinct values of @math on pairs of points of @math is @math . This is also the best known bound over @math , where it follows from the Szemer 'edi-Trotter theorem. Also, a set @math , not supported in a single semi-isotropic plane contains a point, from which @math distinct distances to other points of @math are attained. Let f be a polynomial of degree n in ZZ[x_1,..,x_n], typically reducible but squarefree. From the hypersurface f=0 one may construct a number of other subschemes Y by extracting prime components, taking intersections, taking unions, and iterating this procedure. We prove that if the number of solutions to f=0 in ^n is not a multiple of p, then all these intersections in ^n_ just described are reduced. (If this holds for infinitely many p, then it holds over as well.) More specifically, there is a_Frobenius splitting_ on ^n_ compatibly splitting all these subschemes Y . We determine when a Gr "obner degeneration f_0=0 of such a hypersurface f=0 is again such a hypersurface. Under this condition, we prove that compatibly split subschemes degenerate to compatibly split subschemes, and stay reduced. Our results are strongest in the case that f's lexicographically first term is i=1 ^n x_i. Then for all large p, there is a Frobenius splitting that compatibly splits f's hypersurface and all the associated Y . The Gr "obner degeneration Y' of each such Y is a reduced union of coordinate spaces (a Stanley-Reisner scheme), and we give a result to help compute its Gr "obner basis. We exhibit an f whose associated Y include Fulton's matrix Schubert varieties, and recover much more easily the Gr "obner basis theorem of [Knutson-Miller '05]. We show that in Bott-Samelson coordinates on an opposite Bruhat cell X^v_ in G B, the f defining the complement of the big cell also has initial term i=1 ^n x_i, and hence the Kazhdan-Lusztig subvarieties X^v_ w degenerate to Stanley-Reisner schemes. This recovers, in a weak form, the main result of [Knutson '08]. We prove that the determinantal complexity of a hypersurface of degree @math d>2 is bounded below by one more than the codimension of the singular locus, provided that this codimension is at least 5. As a result, we obtain that the determinantal complexity of the @math 3×3 permanent is 7. We also prove that for @math n>3, there is no nonsingular hypersurface in @math Pn of degree d that has an expression as a determinant of a @math d×d matrix of linear forms, while on the other hand for @math n≤3, a general determinantal expression is nonsingular. Finally, we answer a question of Ressayre by showing that the determinantal complexity of the unique (singular) cubic surface containing a single line is 5. Friedland's Lower Matching Conjecture asserts that if @math is a @math --regular bipartite graph on @math vertices, and @math denotes the number of matchings of size @math , then @math where @math . When @math , this conjecture reduces to a theorem of Schrijver which says that a @math --regular bipartite graph on @math vertices has at least @math perfect matchings. L. Gurvits proved an asymptotic version of the Lower Matching Conjecture, namely he proved that @math In this paper, we prove the Lower Matching Conjecture. In fact, we will prove a slightly stronger statement which gives an extra @math factor compared to the conjecture if @math is separated away from @math and @math , and is tight up to a constant factor if @math is separated away from @math . We will also give a new proof of Gurvits's and Schrijver's theorems, and we extend these theorems to @math --biregular bipartite graphs.