Guth and Katz’s seminal work provided an almost tight bound for Erdős’s planar distinct distances problem. One can regard the proof of this bound as consisting of four main tools:
- A reduction from the distinct distances problem to a problem about line intersections in . This part is referred to as the Elekes-Sharir reduction or as the Elekes-Sharir framework.
- The introduction of polynomial partitioning.
- Applying 19th century analytic geometry tools that are related to ruled surfaces, such as flecnode polynomials.
- The polynomial technique presented in Guth and Katz’s previous paper. (That is, relying on the existence of a polynomial of a small degree that vanishes on a given point set to reduce incidence problems between points and lines to the interactions between the lines and the algebraic variety which is the zero set of the polynomial.)
We already discussed the Elekes-Sharir framework from item (i) here, here, and here (and due to several new developments, I might write more posts about this subject soon). This series of posts surveys the polynomial partitioning technique from item (ii). Basically, this is a technique for partitioning a -dimensional Euclidean space into a small number of “well behaved” cells. While the technique was originally introduced by Guth and Katz to solve the planar distinct distances problem, it already has several additional applications and extensions: a slightly improved upper bound for the three-dimensional unit distances problem (see here and here), improved bounds for various incidence problems (e.g., see here, here, and here), an alternative proof for the existence of a spanning tree with a low crossing number, and even a new range searching algorithm. Several recent works survey the basics of polynomial partitioning such as Zeev Dvir’s survey, Larry Guth’s lecture notes, this paper by Kaplan, Matoušek, and Sharir, and this blog post by Terry Tao.
In what follows, we regard the dimension of the ambient space as a (small) constant, and ignore the dependence on of the various constants of proportionality in the bounds. Consider a set of points in . Given a polynomial , we define the zero set of to be . For , we say that is an -partitioning polynomial for if no connected component of contains more than points of . Notice that there is no restriction on the number of points of that lie in . In the following figure, the blue curve is the zero set of a 5-partitioning polynomial, since and every cell contains at most two points.
The following result is due to Guth and Katz.
Theorem 1 (Polynomial partitioning). Let be a set of points in . Then for every , there exists an -partitioning polynomial of degree .
In the remainder of this post we show how to apply the polynomial partitioning theorem by presenting an algebraic proof for the Szemerédi-Trotter theorem (for the planar point-line incidence problem). In the following two posts, we prove the polynomial partitioning theorem and compare polynomial partitioning to the previous partitioning technique called cuttings. Parts of these posts are loosely based on parts of this paper by Kaplan, Matoušek, and Sharir. I also plan to discuss, in future posts, more advanced topics related to polynomial partitionings, such as the techniques of using a second partitioning polynomial (see here and here) and of using constant sized partitioning polynomials (introduced by Solymosi and Tao). Thanks to Micha Sharir for helping with the preparation of all three posts.
An algebraic proof of the Szemerédi-Trotter theorem
Let be a set of distinct points and let be a set of distinct lines, both in the plane . An incidence is a pair such that the point is contained in the line . We denote by the number of incidences in . We put where the maximum is taken over all sets of points and all sets of lines.
Theorem 2 (Szemerédi-Trotter). .
The lower bound in the theorem was originally derived by Erdös (e.g., see this survey, which is also a good reference for additional information about incidence theory). We now prove the upper bound by using polynomial partitioning (a slightly different proof can be found here).
The following lemma from extremal graph theory is very useful in incidence theory (we only present a special case; for more details, see Section 4.5 in the book Lectures on discrete geometry by Matoušek).
Lemma 1 (Kővári–Sós–Turán). Let be a bipartite graph with vertex sets such that and . If does not contain a copy of (a complete bipartite graph with vertex sets of sizes and ) such that the vertices belong to and the the vertices belong to , then the number of edges in is , where the constant of proportionality depends on and .
The incidence graph of and is a bipartite graph on the two vertex sets such that contains a vertex for every point in and contains a vertex for every line in . There is an edge in between the vertices and if and only if the point that corresponds to is incident to the line that corresponds to . An example is depicted in the following figure.
Since two distinct lines have at most one point in common, does not contain a copy of . Thus, according to Lemma 1, has edges. Since there is a bijection between the edges of and the incidences in , we have
This is still far from the bound implied by Theorem 2 (unless , in which case both bounds are ).
A common trick in incidence theory is to obtain a weak bound on the number of incidences, as we just did, and then to “amplify” it. This is done by partitioning the plane (or, more generally, the space) into “well behaved” cells, and then applying the weak bound in each cell. Intuitively, when considering the bound from , we can say that every point of contributes to the bound an amount equal to the square root of . By partitioning the plane into cells and applying in each cell, each point of contributes only the square root of the number of lines that cross the relevant cell. Thus, we expect such a partitioning to imply an improved bound. An example is depicted in the following figure, where the blue dashed lines are the lines of and the red curves form the partitioning of the plane.
Before Guth and Katz introduced polynomial partitioning, the partitioning of the ambient space was commonly done by using cuttings (e.g., see Chapter 4 of the book Lectures on discrete geometry by Matoušek). As already mentioned, in one of the following posts we will discuss the differences and similarities between these two techniques.
For simplicity, we only consider the case where . That is, we consider a point set and a set of lines such that (the general case can be proved in a similar manner). To partition the plane into cells, we construct an -partitioning polynomial for . According to Theorem 1, the degree of is and every cell in is an open set that contains at most points of . Let denote the number of cells in (i.e., connected components of) .
We denote by the set of points of that are contained in . Similarly, we denote by the set of lines that are fully contained in . For , let denote the set of points that are contained in the -th cell and let denote the set of lines that intersect the -th cell. Notice that
We bound each of these three expressions separately. By factoring into irreducible factors, we notice that it has linear factors, and thus fully contains only lines; that is . This immediately implies
Consider a line that is defined as (for constants ). Notice that there is a bijection between the points in and the roots of the polynomial . Since this is a univariate polynomial of degree , there are at most intersection points between and , which in turn implies
It remains to bound , for which we require an upper bound on the number of cells .
Theorem 3 (Warren). Given a polynomial of degree , the number of connected components of is .
References for the theorem can be found here and here. In our case, Theorem 3 implies . We set and . Since every line of intersects in points, we have . According to the Cauchy-Schwarz inequality, we have
Recalling the bound from , we obtain
which completes the proof.