Incidences in d-dimensional Spaces – Part 2

In the previous post, I described a general incidences result in {\mathbb R}^d  , 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 \cal P  of m  points and a set \cal V  of n  constant-degree algebraic varieties, both in {\mathbb R}^d  , such that the incidences graph does not contain a copy of K_{s,t}  (for some constants s,t  ). Then for any \varepsilon>0

I({\cal P},{\cal V}) \le \alpha_{1,d,D} m^{(d-1)s/(ds-1)+\varepsilon}n^{d(s-1)/(ds-1)}+ \alpha_{2,d}(m+n).

In this bound, \alpha_{1,d,D}  and \alpha_{2,d}  are sufficiently large constants with respect to d,D,\varepsilon  . 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 d  , and in every dimension we induct over the size of the problem m+n  .

We begin by considering the induction base. If d=2  , then the theorem is immediately implied by the Pach-Sharir incidences bound (stated in the previous post). For larger values of d  , the case where m  and n  are sufficiently small can be handled by choosing sufficiently large values of \alpha_{1,d,D}  and \alpha_{2,d}  .

Since the incidences graph does not contain a copy of K_{s,t}  , the Kővári–Sós–Turán theorem implies I({\cal P},{\cal V}) = O(mn^{1-1/s})  . When m=O(n^{1/s})  , this implies the bound I({\cal P},{\cal V}) = O(n)  , and thus we may assume that

n=O(m^s) \qquad \qquad (1).

Partitioning the space. Let f  be an r  -partitioning polynomial, for a sufficiently large constant r  . The dependencies between the various constants in the proof are

2^{1/\varepsilon} \ll r \ll \alpha_{2,d} \ll \alpha_{1,d,D}.

According to the polynomial partitioning theorem (e.g., see here), we have \deg f = O(r^{1/d}).  Denote the cells of the partition as C_1, \ldots, C_\gamma  , where according to Warren’s theorem (e.g., see here), \gamma=O(r)  . Let {\cal V}_i  denote the set of varieties of \cal V  that intersect the interior of C_i  and let {\cal P}_i  denote the set of points that are contained in C_i  . We set m_i=|{\cal P}_i|  , \sum_i m_i = m'  , and n_i=|{\cal V}_i|  . Notice that m_i\le m/r  , for every 1\le i \le \gamma  . According to Theorem A.2 in this paper by Solymosi and Tao , every variety of \cal C  intersects O(r^{(d-1)/d})  cells of {\mathbb R}^3\setminus Z(f)  . Therefore, \sum_i n_i = O(nr^{(d-1)/d})  , and according to Hölder’s inequality we have

\qquad \qquad \sum_{i=1}^\gamma n_i^{\frac{d(s-1)}{ds-1}} = \left(\sum_{i=1}^\gamma n_i\right)^{\frac{d(s-1)}{ds-1}} \left(\sum_{i=1}^\gamma 1\right)^{\frac{d-1}{ds-1}}

=O\left(\left(nr^{\frac{d-1}{d}}\right)^{\frac{d(s-1)}{ds-1}}r^{\frac{d-1}{ds-1}}\right) =O(n^{\frac{d(s-1)}{ds-1}}r^{\frac{(d-1)s}{ds-1}}).

By the induction hypothesis, we have

\sum_{i=1}^\gamma I({\cal P}_i,{\cal V}_i) \le \sum_{i=1}^\gamma \left(\alpha_{1,d,D} m_i^{\frac{(d-1)s}{ds-1}+\varepsilon}n_i^{\frac{d(s-1)}{ds-1}}+\alpha_{2,d}(m_i+n_i)\right)
\le O\left(\alpha_{1,d,D} \frac{m^{\frac{(d-1)s}{ds-1}+\varepsilon}}{r^{\frac{(d-1)s}{ds-1}+\varepsilon}} \sum_{i=1}^\gamma n_i^{\frac{d(s-1)}{ds-1}} \right) + \sum_{i=1}^\gamma \alpha_{2,d}(m_i+n_i)
= O\left(\alpha_{1,d,D} \frac{m^{\frac{(d-1)s}{ds-1}+\varepsilon}n^{\frac{d(s-1)}{ds-1}}}{r^{\varepsilon}}   \right) + \alpha_{2,d}\left(m'+O(nr^{(d-1)/d})\right).

According to (1)  , we have n=O\left(m^{\frac{(d-1)s}{ds-1}}n^{\frac{d(s-1)}{ds-1}}\right)  . Thus, when \alpha_{1,d,D}  is sufficiently large with respect to r  and \alpha_{2,d}  , we have

\sum_i I({\cal P}_i,{\cal V}_i) = O\left(\alpha_{1,d,D} \frac{m^{\frac{(d-1)s}{ds-1}+\varepsilon}n^{\frac{d(s-1)}{ds-1}}}{r^{\varepsilon}}   \right) + \alpha_{2,d}m'.

When r  is sufficiently large with respect to \varepsilon  and to the constant of the O()  -notation, we have

\sum_i I({\cal P}_i,{\cal V}_i) \le \frac{\alpha_{1,d,D}}{3} m^{\frac{(d-1)s}{ds-1}+\varepsilon}n^{\frac{d(s-1)}{ds-1}} + \alpha_{2,d}m'. \qquad \qquad (2)

Incidences on the partitioning. It remains to bound incidences with points that are on Z(f)  . Set {\cal P}_0= {\cal P} \cap Z(f)  and m_0=|{\cal P}_0|=m-m'  . We may assume that every component of Z(f)  is (d-1)  -dimensional. More precisely, if the partitioning contains a lower dimensional component A  , we can always replace A  with a (d-1)  -dimensional component that fully contains A  and does not increase the degree of the partitioning.

We now consider the number of incidences between a point p\in{\cal P}_0 and a variety V\in{\cal V}  such that V  fully contains a component of Z(F)  that contains p  . Every irreducible component of Z(f)  that contains at least s  points of {\cal P}_0  is fully contained in at most t-1  varieties of \cal V  , since otherwise the incidences graph would contain a copy of K_{s,t}  . Thus, the number of incidences between points of {\cal P}_0  on such components of Z(f)  and varieties of \cal V  that fully contain the respective component is O(rm_0) \le \alpha_{2,d}\frac{m_0}{2}  . On the other hand, since there is a constant number of irreducible components of Z(f)  that contain fewer than s  points of {\cal P}_0  , the points on these components yield O(sn) \le \frac{\alpha_{1,d,D}}{3} m^{\frac{(d-1)s}{ds-1}}n^{\frac{d(s-1)}{ds-1}}  incidences with the varieties of \cal V  (by also applying (1)  ). Summing up, the number of incidences between points of {\cal P}_0  and varieties of \cal V  that fully contain the respective component of Z(f)  is

\frac{\alpha_{2,d}}{2}m_0 + \frac{\alpha_{1,d,D}}{3} m^{\frac{(d-1)s}{ds-1}}n^{\frac{d(s-1)}{ds-1}}. \qquad (3)

Finally, we consider the incidences between points of {\cal P}_0  and varieties of \cal V  that do not fully contain any component of Z(f)  that contains the respective points (that is, varieties that properly intersect the respective components). We denote the set of these varieties as {\cal V}'  . By the cylindrical algebraic decomposition theorem that was stated at the end of the previous post, we can apply a CAD that partitions Z(f)  into \gamma_r  (a constant that depends only on r  ) monotone patches. We project each patch on its corresponding hyperplane. For 1\le i \le \gamma_r  , let us denote the points of {\cal P}_0  that are contained in the i  -th patch as {\cal P}_0^{(i)}  , and set m_{0,i} = |{\cal P}_0^{(i)}|  . Consider such a patch C  , and notice that each variety of {\cal V}'  intersects C  in a variety of dimension at most d-2  and degree at most D'=\max\{r^{1/d},D\}  . The projection of such a variety onto the hyperplane that corresponds to C  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 \delta n   irreducible varieties, where \delta \ge 1  depends on r,d,D  . In each hyperplane we apply the induction hypothesis to obtain the bound

I({\cal P}_0^{(i)},{\cal V}') \le \alpha_{1,d-1,D'} m_{0,i}^{\frac{(d-2)s}{(d-1)s-1}+\varepsilon}(\delta n)^{\frac{(d-1)(s-1)}{(d-1)s-1}}+\alpha_{2,d-1}(m_{0,i}+\delta n)
\le 2\alpha_{1,d-1,D'} m^{\frac{(d-2)s}{(d-1)s-1}+\varepsilon}(\delta n)^{\frac{(d-1)(s-1)}{(d-1)s-1}}+\alpha_{2,d-1}m_{0,i},

where in the second transition we applied n=O\left(m^{\frac{(d-2)s}{(d-1)s-1}}n^{\frac{(d-1)(s-1)}{(d-1)s-1}}\right)  , implied by (1)  . Also implied by (1)  is the bound

m^{\frac{(d-2)s}{(d-1)s-1}}n^{\frac{(d-1)(s-1)}{(d-1)s-1}} = O\left(m^{\frac{(d-1)s}{ds-1}}n^{\frac{d(s-1)}{ds-1}} \right).

By combining the above bounds and by choosing \alpha_{1,d,D} \ge 6\gamma_r\alpha_{1,d-1,D'}\delta^{\frac{(d-1)(s-1)}{(d-1)s-1}}  and \alpha_{2,d} \ge 2\alpha_{2,d-1}  , we obtain

\sum_i I({\cal P}_0^{(i)},{\cal V}') \le \gamma_r 2\alpha_{1,d-1,D'} m^{\frac{(d-2)s}{(d-1)s-1}+\varepsilon}(\delta n)^{\frac{(d-1)(s-1)}{(d-1)s-1}}+\alpha_{2,d-1}m_{0}
\le \frac{\alpha_{1,d,D}}{3} m^{(d-1)s/(ds-1)}n^{d(s-1)/(ds-1)}+ \frac{\alpha_{2,d}}{2}m_0. \qquad (4)

By summing up (2)  , (3)  , and (4)  , we obtain

I({\cal P},{\cal V}) \le \alpha_{1,d,D} m^{(d-1)s/(ds-1)+\varepsilon}n^{d(s-1)/(ds-1)}+\alpha_{2,d,D}(m+n).

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

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.


Leave a Reply

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

You are commenting using your 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