This is the second in my series of posts about the basics of polynomial partitioning. In the first post of the series we presented the basics of polynomial partitioning and showed how the technique can be used to prove the Szemerédi-Trotter theorem. In this post we present Guth and Katz’s proof of the polynomial partitioning theorem. We first repeat the statement of the theorem.
Theorem 1 (Polynomial partitioning). Let be a set of points in . Then for every , there exists an -partitioning polynomial of degree .
To prove Theorem 1, we recall the discrete version of the ham sandwich theorem (e.g., see this paper). A hyperplane in bisects a finite point set if each of the two open halfspaces bounded by contains at most points of . The bisecting hyperplane may contain any number of points of .
Theorem 2. Every finite point sets can be simultaneously bisected by a hyperplane.
A planar example of Theorem 2 is depicted in the following figure, where both the blue set and the orange set are bisected.
We use Theorem 2 to prove the following theorem, which is the discrete version of the polynomial ham sandwich theorem. A polynomial in bisects a finite point set if for at most points and for at most points . The zero set may contain any number of points of .
Theorem 3 (Stone and Tukey). Let be finite point sets, and let be the smallest integer such that . Then there exists a nonzero polynomial of degree at most that simultaneously bisects all of the sets .
Proof. The number of monomials that a polynomial of degree at most in can have is ; this is illustrated in the following figure.
Set , the number of nonconstant monomials, and let
clearly The Veronese map is defined as
Every coordinate in corresponds to a nonconstant monomial of degree at most in , and maps a point in to the tuple of the values of these monomials at . For , we set . That is, every is a finite point set in . By Theorem 2, since , there exists a hyperplane that simultaneously bisects all of the sets . If we denote the coordinates of as , for , then can be defined as the zero set of a linear equation of the form , for a suitable set of constants .
Returning to , we obtain the polynomial . Consider a point and let . Notice that . That is, for every point , (resp., ) if and only if is in the positive side of (resp., in the negative side of ). Since bisects every , then bisects every .
In other words, Theorem 3 implies the existence of a bisecting polynomial of degree at most
Recent uses of the polynomial ham sandwich theorem already appeared before Guth and Katz’s distinct distances paper (e.g., see Gromov and Guth). However, Guth and Katz were the first to apply the polynomial ham sandwich theorem to obtain a polynomial partitioning. We now present a variant of their proof.
Proof of Theorem 1. Let . To prove the theorem, we show that there exists a sequence of polynomials such that the degree of is smaller than and every connected component of contains at most points of . An example is depicted in the following figure.
This would complete the proof since we can then choose , where is the minimum integer satisfying .
We prove the existence of by induction. The existence of is immediately implied by Theorem 2. For the induction step, assume that there exists a polynomial of degree smaller than such that every connected component of contains at most points of . Since , the number of these connected components that contain more than points of is smaller than . Let be the subsets of that are contained in each of these connected components (that is, for each , and ). By Theorem 3 (and the remark following it), there is a polynomial of degree smaller than that simultaneously bisects every . We can set , since every connected component of contains at most points of and is a polynomial of degree smaller than
This completes the induction step, and thus also the proof.