The second-partitioning-polynomial technique (part 1)

Thanks to Micha Sharir for helping in the preparation of this series of posts.

In a previous series of posts we introduced the basics of polynomial partitioning (see also the pdf version here). However, by presenting an example in ${\mathbb R}^2$, we avoided the main difficulty in applying the technique, which arises only in dimensions $d\ge 3$ – bounding the number of incidences on the partitioning itself (i.e., on the zero set of the partitioning polynomial). In the plane, the partitioning is a one-dimensional curve, which is relatively simple to handle. Already when dealing with point-curve incidences in ${\mathbb R}^3$, the partitioning is a two-dimensional surface which can fully contain all of the points and all of the curves, and curves that are fully contained in the partitioning can intersect in non-trivial ways.

Recently, two techniques for overcoming these difficulties in several special cases were introduced:

• Using a constant-degree partitioning polynomial. This approach was introduced by Solymosi and Tao.
• Applying a second polynomial partitioning that partitions the first partitioning. This approach was independently introduced both by Zahl and by Kaplan, Matoušek, Safernová, and Sharir (though Zahl was the first to upload his results to arXiv, exposing the technique to the community).
In a recent result by Abdul Basit and myself (which was submitted but is not yet available online), the two techniques are combined together to obtain an upper bound for the number of incidences between points and “restricted” configurations of spheres and planes. In this series of posts we discuss the technique of applying a second partitioning polynomial. The main idea in this technique is to partition the surfaces of a polynomial partitioning by using a second partitioning polynomial. The second partitioning should not overlap the first one in a $(d-1)$-dimensional patch, for otherwise no further partitioning would take place.

The technique is based on the following theorem. (As before, we regard the dimension $d$ of the ambient space as a constant, and ignore the dependence on $d$ of the various constants of proportionality in the bounds.)

Theorem 1 (Second polynomial partitioning). Given an irreducible polynomial $f\in{\mathbb R}[x_1,\ldots,x_d]$ of degree $D$, a parameter $E\ge D$, and a finite point set $\cal P$ in ${\mathbb R}^3$, there exists a polynomial $g\in{\mathbb R}[x_1,\ldots,x_d]$ of degree at most $E$, co-prime with $f$, which partitions $\cal P$ into subsets $Q_0 \subset Z(g)$ and $Q_1,\ldots,Q_t$, for $t=O(DE^{d-1})$, so that each $Q_i$, for $i=1,\ldots,t$, lies in a distinct component of ${\mathbb R}^d\setminus Z(g)$, and $|Q_i|=O(|Q|/t)$.

The two proofs of Theorem 1, by Zahl and by Kaplan, Matoušek, Safernová, and Sharir, are quite different from each other. The latter is based on a simple combinatorial trick, while the former is more algebraic and is based on real varieties (not to be confused with varieties in a real space). In this post we present the simpler combinatorial proof. The algebraic proof is also interesting and has the advantage of yielding a partition whose components are all $(d-1)$-dimensional (the approach of Kaplan et al. also allows lower dimensional components).

Proof.     Recall that in the proof of the existence of a polynomial partitioning, we build the polynomial as the product of logaritmically many bisecting polynomials, each obtained by applying the polynomial ham sandwich theorem (e.g., see here, here, and here). The current proof goes along the same lines, except that we use a variant of the ham sandwich theorem. Specifically, we want to ensure that each of the bisecting polynomials is not divisible by $f$; since $f$ is irreducible, this ensures the co-primality of $f$ and $g$.

Recalling the construction of the original partitioning polynomial, we notice that all that is needed is to come up with some sufficiently large finite set of monomials, of an appropriate maximum degree, so that no nontrivial linear combination of these monomials is divisible by $f$. We then use a restriction of the Veronese map defined by this subset of monomials, and the standard (discrete) ham-sandwich theorem in the resulting high-dimensional space, to obtain the desired polynomial.

Let $x_1^{\ell_1}x_2^{\ell_2}\cdots x_d^{\ell_d}$ be the leading term of $f$, in the sense that $\sum_{i=1}^d \ell_i = D$ and $(\ell_1,\ldots,\ell_d)$ is largest in the lexicographical order among all $d$-tuples of exponents of monomials of $f$ of degree $D$. Let $q$ be the desired number of sets that we want a single polynomial to bisect. For that we need $q$ monomials whose degrees are not too large (while not spanning any polynomial that is divisible by $f$). We take the monomials $x_1^{e_1}x_2^{e_2}\cdots x_d^{e_d}$ for which there exists an $1 \le i \le d$ such that $e_i < \ell_i$ and $\max\{e_1,\ldots,e_d \} \le D'$, for an integer $D'$ that will be determined later. Any polynomial $h$ which is a combination of such monomials cannot be divisible by $f$, since the leading term of $f$ does not divide any of the monomials of $h$ (for more details about polynomial divisibility, see Section 2.3 of the book Ideals, Varieties, and Algorithms). The number of monomials in this set is $\Theta(\ell_1D'^{d-1} + \ldots + \ell_dD'^{d-1}) = \Theta(DD'^{d-1})$ (while we count some monomials several times, this has no effect on the asymptotical value). By setting $D' = \Theta\left((q/D)^{1/(d-1)}\right)$, with a suitable choice of the constant of proportionality, we indeed get $q$ monomials. In this case, the degree of the resulting polynomial is at most $dD' = \Theta\left((q/D)^{1/(d-1)}\right)$.

We now build the required partitioning polynomial $g$ as the product of about $\log t$ polynomials $g=g_0g_1\cdots$, where $g_i$ bisects $q_i\le 2^i$ subsets of $\cal P$ that form the partition induced by $g_0g_1\cdots g_{i-1}$. By the above, we have $\deg(g_i) = O\left((q_i/D)^{1/(d-1)}\right) = O\left(2^{i/(d-1)}/D^{1/(d-1)}\right)$. We thus have

$\deg(g) = O\left( \sum_{i=1}^t 2^{i/(d-1)}/D^{1/(d-1)} \right) = O\left((t/D)^{1/(d-1)}\right).$

If we require this degree bound to be no larger than $E$, we need to set $t=O(DE^{d-1})$. Since $f$ does not divide any $g_i$, it also does not divide $g$.     $\Box$

So far, the method of applying a second polynomial partitioning was used only for bounding numbers of incidences between points and two-dimensional objects in ${\mathbb R}^3$. For the case of points and curves in ${\mathbb R}^3$, it seems that a single partitioning suffices. In the next post we discuss the problems that arise in dimensions $d\ge 4$. Before getting to these problems, we will present an example illustrating the application of a second polynomial partitioning to a problem concerning incidences between points and planes in ${\mathbb R}^3$.