In the previous post we presented the second partitioning polynomial theorem. In this post we give an example of how to apply this theorem. After going over this example, it will be easier to discuss why so far this technique had been used only in .
Let be a set of points and let be a set of planes, both in . Consider a line such that all the points of lie on and all the planes of fully contain , as in the following figure.
In this case we have , which makes the problem not interesting. There exist several definitions of non-degenerate point-plane configurations, which make the problem of bounding the number of incidences more challenging (e.g., see this paper by Elekes and Toth; these non-degenerate configurations are not defined just for the sake of “making the problem less trivial”, and already have various applications). Since we are only interested in presenting the two partitioning polynomials technique, we consider the somewhat simple case where no three planes of contain a common line. This problem was already studied over 20 years ago by Edelsbrunner, Guibas, and Sharir, where partitioning of the space by cuttings has led to the bound (they study the dual setting where no three points are collinear, though it is equivalent to our setting). A more general case is studied in a yet unpublished manuscript by Abdul Basit and myself, where the assumption is that no line is contained in planes (and can also depend on ). To further simplify our scenario, we also assume that .
Theorem 1. Let be a set of points and let be a set of planes, both in , such that no line is fully contained in three planes of . Then .
Proof. We begin just as in the two-dimensional proof that was presented in this post. According to the assumption, any pair of points of can be contained in at most two planes of (or, recalling the notation that we used in the two dimensional case, the point-plane incidence graph does not contain a copy of ). Thus, the Kővári–Sós–Turán theorem implies
To partition the plane into cells, we construct an -partitioning polynomial for . According to the polynomial partitioning theorem, 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 planes of that are fully contained in , and set . For , we let denote the set of points that are contained in the -th cell and we let denote the set of planes 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 planes (that is ). This immediately implies . We next bound , for which we require an upper bound on the number of cells . We recall Warren’s theorem:
Theorem 2 (Warren’s Theorem). Given a polynomial of degree , the number of connected components of is .
In our case, Theorem 2 implies . We set and . To derive an upper bound for the number of cells that a plane can intersect, we define the curve . We can consider as a planar curve of degree in the plane , and thus Theorem 2 implies that the number of connected components of is . Since any such connected component intersects a single cell of the partitioning , we get that intersects cells of the partitioning . Therefore, . According to the Cauchy-Schwarz inequality, we have
Recalling the bound from , we obtain
It remains to bound , for which we require the second partitioning polynomial theorem from the previous post. Since the theorem only handles irreducible polynomials, we factor into irreducible factors , and apply the theorem for each separately. Notice that . For each of degree (such that ), we apply theorem to obtain a second partitioning polynomial , co-prime with and of some suitable degree , which we will specify later. (We assume that is composed only of two-dimensional components. One-dimensional and zero-dimensional components are easy to handle. Moreover, the existence of a polynomial partition that is composed strictly of two dimensional components is proved by Zahl.)
We assume that every point of is incident to exactly one of the zero sets . If a point is incident to more than one such zero set, we arbitrarily choose one of these sets and treat as if it were incident only to . Let (resp., ) denote the set of points of that are contained in but not in (resp., and in ). We say that a cell of is proper if it contains at least one point of , and denote the proper cells as . According to the second partitioning polynomial theorem, we have and the number of points of is for each . We let denote the number of planes of that intersect the proper cell , and for put . As in the analysis of the first polynomial partition, we need a bound on .
Lemma 3. Let be co-prime polynomials of degrees and , respectively, such that . Let be a plane in such that . Then the number of cells of that are intersected by is .
Let (resp. ) denote the bivariate polynomial which is the restriction of (resp., ) to the plane . Notice that is of degree at most and is of degree at most . Every cell of that is intersected by contains at least one connected component of . Thus, the number of cells is upper bounded by the number of connected components of , or equivalently, of . Each such connected component is either a full connected component of , to which we refer as a type A component, or an open portion of whose closure meets , to which we refer as a type B component. According to Harnak’s curve theorem, has connected components, so this is an upper bound on the number of type A components.
Consider a sufficiently small constant , and let and . By choosing a generic value of , we may assume that and share no nontrivial factors, and that the same holds for and . (Indeed, if and have a nonconstant common factor for two distinct values and of , then divides , which is impossible. Therefore, the number of “bad” values of is at most twice the number of components of , which is at most .) Notice that every type B component must intersect either or (or both). An example is illustrated in the following figure. (On the last part, the blue curves represent and the red dashed curves represent . On the right part, the blue curves represent and the orange curves represent and .)
This might not true if or contain zero-dimensional components, but a simple technical analysis overcomes this difficultly (Once again, by the analysis of Zahl, we may assume that consists only of two-dimensional components. Let be the direction of the normal of . Then we can replace with a copy of it that is translated by an in the direction of ). Since is of degree at most , according to Bézout’s theorem, the number of intersection points between and is (and the same holds for the number of intersection points between and ). Therefore, the number of type B components is , concluding the proof of the lemma.
By Lemma 3, for every we have . According to the Cauchy-Schwarz inequality, we have
Similarly to the preceding analysis, by applying we have
It remains to bound the number of incidences with points of .
Lemma 4. Let be co-prime polynomials of degrees and , respectively, such that . Let be a set of planes in such that no line is fully contained in three planes of and no plane of is fully contained in . Let be a set of points in such that . Then .
Proof. There are planes of that are fully contained in , and these yield incidences with the points of . Let denote the set of planes of that are not fully contained in . See the following figure for an example of a plane with the intersections of and on it (the red curves represent , the blue curves represent , the purple curves represent curves of , and the purple points represent ).
We first consider incidences between the plane and points of that are on a zero-dimensional component of . The number of zero-dimensional components of is an upper bound on the number of such incidences with . We consider the two planar curves and of degrees at most and , respectively. We remove from these two curves one-dimensional components that are common to both of them, and denote the resulting curves as and . Bézout’s theorem implies that the number of points in is . By Milnor’s theorem, the removed common components contain connected components. Thus, the overall number of zero-dimensional components in is , and summing up over all the planes of yields the bound .
It remains to consider incidences between a plane and points of that are on a one-dimensional component of . We consider a point , and bound the number of such incidences that can participate in. A curve that is fully contained in more than one plane of is a line. According to the assumption, at most two planes of can contain such a line. The intersection contains irreducible curves (one way to prove this property is by using resultants, which I plan to discuss in following posts) and each such curve is contained in at most two planes of , so planes can be incident to , with a total of incidences of this type.
Combining Lemma 4 and (and recalling that ), we have
To optimize these expressions, we set for each . The second term dominates when . Assuming that this is indeed the case, implying , we get
Otherwise, , and thus we have
Summing up over the cases where and recalling that , we have
Summing up over the cases where and applying Hölder’s inequality, we have
By combining the above, we obtain , which completes the proof.
After going over the proof of Theorem 1, it is hopefully clearer why so far the technique was used only in . For example, when applying the technique in we expect the intersection of the two partitions to be a set of two-dimensional surfaces. It is currently unclear how to bound the number of incidences on these surfaces. One approach would be to partition these surfaces by considering a third partitioning polynomial that shares no common factors with each of the first two polynomials. However, it is not known whether such a third polynomial with a sufficiently small degree exists. Similarly, when considering an incidence problem in , we would like to use partitioning polynomials with no factors that are contained in more than one of these polynomials. Proving that the existence of such polynomials of sufficiently small degrees is currently one of the main challenges in the study of polynomial partitioning.