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

Continue reading

Advertisements

Incidences in d-dimensional Spaces

In this post and in the following one I will present a bound on the maximum number of incidences between points and varieties in {\mathbb R}^d  , for any d \ge 2  . This week Martin Sombra stated it as an open conjecture during his very nice talk at IPAM, while presenting a joint work with Saugata Basu. We actually had this result hidden in our basement for a while, and this seems to be a good the time to present it. The bound will appear in a more general form in a paper by Jacob Fox, János Pach, Andrew Suk, Joshua Zahl, and myself. My plan is to discuss this incidences bound and to present some of the required preliminaries in this post, and then to give a full proof in a following post (after I return from a one week vacation).

Sombrabasu
Martin Sombra and Saugata Basu.

Let us first recall a general incidences result in the plane.
Theorem 1 (Pach and Sharir `98). Consider a set \cal P  of m  points , a set \Gamma  of n  simple curves, both in {\mathbb R}^2  , and two constant positive integers k  and s  , such that (i) For every k  points of \cal P  there are at most s  curves of \Gamma  that are incident to each of the k  points, and (ii) Every two curves of \Gamma  intersect in at most s  points. Then I({\cal P},\Gamma) = O(m^{k/(2k-1)}n^{(2k-2)/(2k-1)}+m+n),  where the constant of proportionality depends on k  and s  .
Does there exist such a general bound when the dimension is larger than 2? At first, it might not be immediately clear how the higher-dimensional question should be formulated, even for the simple case of hyperplanes. On one hand, if we ask every pair of hyperplanes to intersect in at most some constant number of points, we allow only the boring case of a set of parallel hyperplanes. On the other hand, if we completely remove the condition concerning common intersection points, we obtain a different boring scenario – all of the hyperplanes can intersect in a common line that contains all of the points. That is, we can have \Theta(mn)  incidences.

PlaneCommonLine

So how can we properly formulate an incidence problem between points and varieties in {\mathbb R}^d  ? The natural (and popular) formulation is to add the restriction that the incidence graph does not contain a copy of K_{r,s}  (that is, that for every subset of r  points of \cal P  , at most s-1  of the varieties can be incident to all of the points of the subset). Notice that this restriction forbids the problematic situation of many hyperplanes through a common line, while not forcing a degenerate structure of the arrangement of the hyperplanes.
Let us now return to our question: Does there exist such a general bound when the dimension is larger than 2? In fact, such a bound was already known for a while, though it is somewhat hidden inside a paper by Elekes and Szabó. If we slightly change the proof of Theorem 9 in that paper, we obtain the following d  -dimensional bound.
Theorem 2 (Elekes and Szabó). 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_{r,s}  (for some constants r,s  ). Then for any \varepsilon>0

I({\cal P},{\cal V}) = O(m^{2(d-1)r/(2dr-1)+r\varepsilon}n^{d(2r-1)/(2dr-1)-\varepsilon}+m+n).

To prove this theorem, Elekes and Szabó relied on the cutting technique. This technique has an inefficiency in dimensions d \ge 5  , which yielded the various 2’s in the exponents of the bound of Theorem 2. By replacing the cutting with polynomial partitioning, we obtain the following improved bound.
Theorem 3 (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_{r,s}  (for some constants r,s  ). Then for any \varepsilon>0

I({\cal P},{\cal V}) = O(m^{(d-1)r/(dr-1)+\varepsilon}n^{d(r-1)/(dr-1)}+m+n).

Theorem 3 generalizes many of the existing incidences bounds, up to the extra \varepsilon  in the exponent. Some examples:

  • When d=2  , we obtain the Pach-Sharir bound of Theorem 1.
  • When d=3  , we obtain the bounds by Zahl and by Kaplan, Matoušek, Safernová, and Sharir.
  • When d=4  , we obtain the bound derived by Basu and Sombra (and presented by Martin in his recent IPAM talk).
  • Edelsbrunner, Guibas, and Sharir considered point-plane incidences in {\mathbb R}^3  , where no three points are collinear. Theorem 3 generalizes this result to {\mathbb R}^d  , where no d  points are contained in a common (d-2)  -flat. A further generalization is to other types of hypersurfaces, such as spheres.
Basu and Sombra derived their bound without the extra \varepsilon  in the exponent, for the specific case of hypersurfaces in {\mathbb R}^4  . Their technique is based on Hilbert polynomials. Hopefully their technique can be extended to the general case.
In the upcoming paper, we prove Theorem 3 by relying on bounds for Hilbert polynomials, using a previous result by Martin. In the following post, I will present a rather different proof, based on cylindrical algebraic decompositions.
Given a hypersurface S  in {\mathbb R}^d  , we say that a patch of S  is a (possibly open) continuous piece of S  of any dimension. We say that a patch S'  of S  is monotone if there exists a hyperplane \pi_{S'}  such that S'  can be injectively projected onto \pi  .
A cylindrical algebraic decomposition (or CAD for short) partitions a hypersurface S \subset {\mathbb R}^d  into monotone patches. Some of the patches in the CAD partitioning might be of a dimension smaller than d-1  and can thus be injectively projected onto a lower dimensional flat. However, we do not require this property, and project each of the patches on a (d-1)  -dimensional hyperplane. One may also assume that all of the corresponding hyperplanes have the same normal direction, but we do not require this property either. The following theorem and additional details can be found in Chapters 5 and 11 of the book Algorithms in Real Algebraic Geometry by Basu, Pollack, and Roy.
Theorem 4. Let S  be a hypersurface in {\mathbb R}^d  of degree D  . Then S  can be partitioned into O_{D,d}(1)  monotone patches.

Random Stories from IPAM – Part1

Since my previous post, I moved from freezing New York to sunny LA. I am participating in a semester on Algebraic Techniques for Combinatorial and Computational Geometry, at the IPAM institute. The lack of posts on the blog in the past several weeks is due to the constant activities and the large number of interesting people to interact with. This post contains some random stories from my stay at IPAM.

IMG_2181
During pie day (March 14th), all of the food served in IPAM was round.

So far the main events were a week of tutorials and another week consisting of a workshop about “Combinatorial Geometry Problems at the Algebraic Interface”. These contained many interesting talks, which were also videotaped. Once the videos will be online, I will post a link in the blog. Here I only mention one talk which gave me quite a surprise – Larry Guth‘s talk.

At the beginning of his talk, Larry stated that he will present a significantly simpler variant of part the distinct distances proof (the one by Katz and himself). You might remember that, using the Elekes-Sharir framework, the distinct distances problem is reduced to a point-line incidences problem in {\mathbb R}^3  : Given a set of n  lines, such that every point is incident to at most O(\sqrt{n})  of the lines and that every plane and regulus contain at most O(\sqrt{n})  of the lines, what is the maximum number of points that can be incident to at least k  of the lines (where 2\le k \le \sqrt{n}  ). Larry’s new technique proves the following slightly weaker incidences bound.

Theorem (Guth `14). Consider a set \cal L  of n  lines in {\mathbb R}^3  , so that any surface of degree at most c_\varepsilon  (a constant that depends only on \varepsilon  ) contains at most \sqrt{n}  lines of L  . Then for any \varepsilon>0  and 2 \le r \le \sqrt{n}  , the number of points of {\mathbb R}^3  that are contained in at least r  lines of L  is O(\frac{n^{3/2+\varepsilon}}{r^2}).

The surprising part is that the new proof was based on constant sized partitioning polynomials (on which I plan to write a couple of expository posts, as part of my expository series about the polynomial method). When using such polynomials for problems of this sort, one encounters a difficultly. It is hard to describe this difficulty without first explaining the technique, but my impression is that this difficulty was the main issue in various other recent incidences-related projects, and that now we might see various other works that rely on Larry’s technique. In his talk, Larry also mentioned that this technique can work for other types of curves, which immediately implies a series of improved point-curve incidence bounds in {\mathbb R}^3  .

TaoTalk
A talk by Tao in IPAM. How many of the mathematicians in the audience can you recognize?

And for something completely different: I had an issue with my visa, and was told that I should exit and reenter the country. This resulted in a 13-hour bus trip to Tijuana and back to LA. My only souvenir from this trip is the following picture of a pharmacy for people that are waiting in line to enter the US. I wonder sort of things people buy at a pharmacy while waiting to go through immigration…

IMG_2184

There’s a lot more to tell, so more IPAM stories later on.