Polynomial partitioning: the basics (part 2)

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 \cal P  be a set of m  points in {\mathbb R}^d  . Then for every 1< r \le m  , there exists an r  -partitioning polynomial f \in {\mathbb R}[x_1,\ldots, x_d]  of degree O(r^{1/d})  .

To prove Theorem 1, we recall the discrete version of the ham sandwich theorem (e.g., see this paper). A hyperplane h  in {\mathbb R}^d  bisects a finite point set S\subset {\mathbb R}^d  if each of the two open halfspaces bounded by h  contains at most |S|/2  points of S  . The bisecting hyperplane may contain any number of points of S  .

Theorem 2. Every d  finite point sets S_1,\ldots,S_d \subset {\mathbb R}^d  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.

PlanarBisection

We use Theorem 2 to prove the following theorem, which is the discrete version of the polynomial ham sandwich theorem. A polynomial f  in {\mathbb R}[x_1,\ldots,x_d]  bisects a finite point set S\subset {\mathbb R}^d  if f(p) > 0  for at most |S|/2  points p \in S  and f(p) < 0  for at most |S|/2  points p\in S  . The zero set Z(f)  may contain any number of points of S  .

Theorem 3 (Stone and Tukey). Let S_1,\ldots, S_t \subset {\mathbb R}^d  be t  finite point sets, and let D  be the smallest integer such that \binom{D+d}{d}-1\ge t  . Then there exists a nonzero polynomial f\in {\mathbb R}[x_1,\ldots,x_d]  of degree at most D  that simultaneously bisects all of the sets S_i  .

Proof.     The number of monomials that a polynomial of degree at most D in {\mathbb R}[x_1,\ldots,x_d]  can have is \binom{D+d}{d}  ; this is illustrated in the following figure.

MonomialsCount

Set m=\binom{D+d}{d}-1  , the number of nonconstant monomials, and let

U = \{ (i_1,\ldots,i_d) \mid 1 \le i_1 + \cdots + i_d \le D \}  ;

clearly |U|=m.  The Veronese map \nu:{\mathbb R}^d \to {\mathbb R}^m  is defined as

\nu(x_1,\ldots,x_d) := (x_1^{u_1}x_2^{u_2}\cdots x_d^{u_d})_{u\in U}\ .

Every coordinate in {\mathbb R}^m  corresponds to a nonconstant monomial of degree at most D  in {\mathbb R}[x_1,\ldots,x_d]  , and \nu(\cdot)  maps a point p  in {\mathbb R}^d  to the tuple of the values of these monomials at p  . For 1 \le i \le t  , we set S'_i = \nu(S_i)  . That is, every S_i'  is a finite point set in {\mathbb R}^m  . By Theorem 2, since m\ge t  , there exists a hyperplane h\subset {\mathbb R}^m  that simultaneously bisects all of the sets S'_i  . If we denote the coordinates of {\mathbb R}^m  as y_u  , for u\in U  , then h  can be defined as the zero set of a linear equation of the form h_0 + \sum_{u\in U}y_uh_u  , for a suitable set of constants h_u  .

Returning to {\mathbb R}^d  , we obtain the polynomial f(x_1,\ldots,x_d) = h_0 + \sum_{u\in U} h_ux_1^{u_1}x_2^{u_2}\cdots x_d^{u_d}  . Consider a point a\in {\mathbb R}^d  and let a' = \nu(a)  . Notice that h_0+(h_u)_{u\in U}\cdot a' = f(a)  . That is, for every point a \in {\mathbb R}^d  , f(a)>0  (resp., f(a)<0  ) if and only if \nu(a)  is in the positive side of h  (resp., in the negative side of h  ). Since h  bisects every S'_i  , then Z(f)  bisects every A_i  .     \Box

In other words, Theorem 3 implies the existence of a bisecting polynomial of degree at most

D\le\lceil(d!\cdot(t+1))^{1/d}\rceil \le 2(d!\cdot t)^{1/d}.

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 c_d = 2(d!)^{1/d}  . To prove the theorem, we show that there exists a sequence of polynomials f_1,f_2,\ldots  such that the degree of f_i  is smaller than c_d 2^{(i+1)/d}/(2^{1/d}-1)  and every connected component of {\mathbb R}^d\setminus Z(f_i)  contains at most m/2^i  points of \cal P  . An example is depicted in the following figure.

PartitioningSteps

This would complete the proof since we can then choose f=f_t  , where t  is the minimum integer satisfying 2^t>r  .

We prove the existence of f_1,f_2,\ldots  by induction. The existence of f_1  is immediately implied by Theorem 2. For the induction step, assume that there exists a polynomial f_i  of degree smaller than c_d 2^{(i+1)/d}/(2^{1/d}-1)  such that every connected component of {\mathbb R}^d\setminus Z(f_i)  contains at most m/2^i  points of \cal P  . Since |{\cal P}|=m  , the number of these connected components that contain more than m/2^{i+1}  points of \cal P  is smaller than 2^{i+1}  . Let S_1,\ldots,S_n \subset {\cal P}  be the subsets of \cal P  that are contained in each of these connected components (that is, |S_i|>m/2^{i+1}  for each i  , and n<2^{i+1}  ). By Theorem 3 (and the remark following it), there is a polynomial g_i  of degree smaller than c_d2^{(i+1)/d}  that simultaneously bisects every S_i  . We can set f_{i+1} = f_i \cdot g_i  , since every connected component of {\mathbb R}^d\setminus Z(f_i \cdot g_i)  contains at most m/2^{i+1}  points of \cal P  and f_i \cdot g_i  is a polynomial of degree smaller than

\frac{c_d 2^{(i+1)/d}}{2^{1/d}-1} + c_d2^{(i+1)/d} = c_d2^{(i+1)/d}\cdot \left(\frac{1}{2^{1/d}-1}+1\right)  = \frac{c_d2^{(i+2)/d}}{2^{1/d}-1}.

This completes the induction step, and thus also the proof.     \Box

Advertisements

One thought on “Polynomial partitioning: the basics (part 2)

  1. Pingback: Polynomial partitioning: the basics (part 3) | Some Plane Truths

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s