In the previous post, I described a general incidences result in , and some of the basics that are required for proving it. This post presents a proof of that result. Let us begin by stating what we wish to prove.
Theorem 1 (Fox, Pach, Suk, Sheffer, and Zahl). Consider a set of points and a set of constant-degree algebraic varieties, both in , such that the incidences graph does not contain a copy of (for some constants ). Then for any
In this bound, and are sufficiently large constants with respect to . As already stated in the previous post, this is actually a special case of a more general result that will appear in the paper. Moreover, the proof here is very different from the more general one that will appear in the paper. This alternative proof was not verified by my coauthors and any mistakes in it are solely mine.
Proof. We prove the theorem by a two-step induction, where we first induct over the dimension , and in every dimension we induct over the size of the problem .
We begin by considering the induction base. If , then the theorem is immediately implied by the Pach-Sharir incidences bound (stated in the previous post). For larger values of , the case where and are sufficiently small can be handled by choosing sufficiently large values of and .
Since the incidences graph does not contain a copy of , the Kővári–Sós–Turán theorem implies . When , this implies the bound , and thus we may assume that
Partitioning the space. Let be an -partitioning polynomial, for a sufficiently large constant . The dependencies between the various constants in the proof are
According to the polynomial partitioning theorem (e.g., see here), we have Denote the cells of the partition as , where according to Warren’s theorem (e.g., see here), . Let denote the set of varieties of that intersect the interior of and let denote the set of points that are contained in . We set , , and . Notice that , for every . According to Theorem A.2 in this paper by Solymosi and Tao , every variety of intersects cells of . Therefore, , and according to Hölder’s inequality we have
By the induction hypothesis, we have
According to , we have . Thus, when is sufficiently large with respect to and , we have
When is sufficiently large with respect to and to the constant of the -notation, we have
Incidences on the partitioning. It remains to bound incidences with points that are on . Set and . We may assume that every component of is -dimensional. More precisely, if the partitioning contains a lower dimensional component , we can always replace with a -dimensional component that fully contains and does not increase the degree of the partitioning.
We now consider the number of incidences between a point and a variety such that fully contains a component of that contains . Every irreducible component of that contains at least points of is fully contained in at most varieties of , since otherwise the incidences graph would contain a copy of . Thus, the number of incidences between points of on such components of and varieties of that fully contain the respective component is . On the other hand, since there is a constant number of irreducible components of that contain fewer than points of , the points on these components yield incidences with the varieties of (by also applying ). Summing up, the number of incidences between points of and varieties of that fully contain the respective component of is
Finally, we consider the incidences between points of and varieties of that do not fully contain any component of that contains the respective points (that is, varieties that properly intersect the respective components). We denote the set of these varieties as . By the cylindrical algebraic decomposition theorem that was stated at the end of the previous post, we can apply a CAD that partitions into (a constant that depends only on ) monotone patches. We project each patch on its corresponding hyperplane. For , let us denote the points of that are contained in the -th patch as , and set . Consider such a patch , and notice that each variety of intersects in a variety of dimension at most and degree at most . The projection of such a variety onto the hyperplane that corresponds to does not increase its degree. While such a projection might result in an object that is not a variety, this should not happen for a generic projection (for a more formal argument, see for example Lemma 4.2 of this paper). Thus, by partitioning the projected varieties into irreducible components, we obtain that each such hyperplane contains at most irreducible varieties, where depends on . In each hyperplane we apply the induction hypothesis to obtain the bound
where in the second transition we applied , implied by . Also implied by is the bound
By combining the above bounds and by choosing and , we obtain
By summing up , , and , we obtain
This completes the induction step and thus the proof.
After finishing this post, it seems to me that the use of CADs can be removed from it, resulting in an even more elementary proof. However, I will not state it here.