# 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.

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.

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.

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$