Incidences in Higher Dimensions: A Conjecture

I recently added to the incidence theory book two chapters about incidences in {\mathbb R}^d  (Chapters 8 and 9). At the moment incidence bounds in {\mathbb R}^d  are known for several different cases, and it is rather unclear how a general incidence bound in {\mathbb R}^d  should look like. In this post I would like to state what I believe this bound should look like. This conjecture is in part a result of conversations with Joshua Zahl over several years (I do not know whether Josh agrees with everything in this post). The post assumes some familiarity with incidence problems.

zahl_photo
Joshua Zahl. A common name in this blog.

Let us start by stating some known bounds for incidences in {\mathbb R}^d  . The first general incidence bound that relied on polynomial techniques was by Solymosi and Tao.

Theorem 1. Let {\cal P}  be a set of m  points and let {\cal V}  be a set of n  varieties, both in {\mathbb R}^d  . The varieties of {\cal V}  are of degree at most k  and dimension at most d/2  . The incidence graph of {\cal P}\times {\cal V}  contains no copy of K_{s,t}  . Also, whenever two varieties U_1,U_2 \in {\cal V}  are incident to a point p\in {\cal P}  , the tangent spaces of U_1  and U_2  at p  intersect at a single point. Then for any \varepsilon>0

I({\cal P},{\cal V}) = O_{k,s,t,d,\varepsilon}\left(m^{\frac{s}{2s-1}+\varepsilon}n^{\frac{2s-2}{2s-1}}+m+n\right).

While Theorem 1 provides a nice incidence bound, the varieties in it are somewhat restricted. A result of Fox et al. holds for varieties of any dimension and without the restriction on the tangent spaces, at the cost of having a weaker bound.

Theorem 2. Let \cal P  be a set of m  points and let \cal V  be a set of n  varieties of degree at most k  , both in {\mathbb R}^d  . Assume that the incidence graph of {\cal P}\times {\cal V}  contains no copy of K_{s,t}  . Then for any \varepsilon>0

I({\cal P},{\cal V}) = O_{k,s,t,d,\varepsilon}\left(m^{\frac{(d-1)s}{ds-1}+\varepsilon}n^{\frac{d(s-1)}{ds-1}}+m+n\right).

Finally, a result of Sharir et al. provides a stronger bound for the special case of varieties of dimension one that do not cluster in a low degree surface (for brevity, the following is a simplified weaker variant).

Theorem 3. For every \varepsilon>0  there exists a constant c_\varepsilon  that satisfies the following. Let \cal P  be a set of m  points and let \cal V  be a set of n  irreducible varieties of dimension one and degree at most k  , both in {\mathbb R}^d  . Assume that the incidence graph of {\cal P}\times {\cal V}  contains no copy of K_{s,t}  , and that every variety of dimension two and degree at most c_\varepsilon  contains at most q  elements of \cal V  . Then

I({\cal P},{\cal V}) = O_{k,s,t,d,\varepsilon}\left(m^{\frac{s}{ds-d+1} +\varepsilon}n^{\frac{ds-d}{ds-d+1}} + m^{\frac{s}{2s-1}+\varepsilon}n^{\frac{ds-d}{(d-1)(2s-1)}}q^{\frac{(s-1)(d-2)}{(d-1)(2s-1)}}+m+n\right).

The incidence theory book describes in detail how to prove the three above bounds. With these result in mind, we are now ready to make a somewhat vague general conjecture.

Conjecture 4. Let \cal P  be a set of m  points and let \cal V  be a set of n  varieties of degree at most k  and dimension d'  , both in {\mathbb R}^d  . Assume that the incidence graph contains no copy of K_{s,t}  and that the varieties of \cal V  satisfy some “reasonable conditions”. Then for any \varepsilon>0

I({\cal P},{\cal V}) = O_{k,s,t,d,\varepsilon}\left(m^{\frac{sd'}{ds-d+d'}+\varepsilon}n^{\frac{ds-d}{ds-d+d'}} + m + n\right).

Note that we already have three cases of conjecture 4:

  • Theorem 1 obtains the conjecture for varieties of dimension d/2  .
  • Theorem 2 obtains the conjecture for varieties of dimension d-1  .
  • Theorem 3 obtains the conjecture for varieties of dimension 1  .
For varieties of dimension smaller than d/2  , the proof of Theorem 1 projects the configuration to a space of dimension that is twice the dimension of the varieties (forcing the dimension of the varieties to be exactly half the dimension of the space). This seems to be an inefficient step, which makes it likely that the theorem is not tight for varieties of dimension smaller than d/2  . Indeed, Theorem 3 already obtains a stronger bound for the case of varieties of dimension one. For similar reasons, the proof of Theorem 2 seems not to be tight for varieties of dimension smaller than d-1  .

A recent work reduces the distinct distances problem in {\mathbb R}^d  to an incidence problem between points and (d-1)  -dimensional planes in {\mathbb R}^{2d-1}  . Combining this reduction with the bound stated in Conjecture 4 would lead to an asymptotically tight bound for the distinct distances problem in dimension d\ge3  . Other problems also reduce to incidence problems with the same dimensions. Thus, the case of d' = (d-1)/2  (for odd d  ) seems to be a main open case.

While conjecture 4 is known for the cases of varieties of dimension 1,d/2  , and d-1  , so far all of the other cases are open. The bound in the conjecture was not obtained by interpolating the three known cases — there is a better approach that leads to it. Recall that in the polynomial partitioning technique we partition {\mathbb R}^d  into cells, bound the number of incidences in each cell, and then bound the number of incidences that are on the partition (not in any cell). The bound stated in Conjecture 4 is obtained by applying this technique while ignoring the incidences on the partition (since bounding the number of incidences in the cells is much easier).

Recently discovered configurations of points and varieties achieve the bound of the conjecture up to extra \varepsilon  ‘s in the exponents. Thus, in its most general form the bound of the conjecture is tight. However, these constructions give a tight bound only for certain families of varieties of dimension d-1  , for certain ranges of m  and n  , and when s=2  . It seems plausible that the bound of the conjecture is not tight in some other interesting cases. In particular, in {\mathbb R}^2  a stronger bound is already known when s\ge 3  , and it seems reasonable that the same technique would also work for varieties of dimension one in {\mathbb R}^d  . At the moment, it is difficult to guess what should happen with varieties of dimension larger than one. Either way, Conjecture 4 seems to be a reasonable bound for the limits of the current polynomial partitioning technique. It seems that this specific technique could not yield better bounds without major changes.

Let us briefly discuss what the expression “reasonable conditions” in the statement of Conjecture 4 means. We already have two examples of conditions that are considered reasonable:

  • A non-clustering condition: Not too many varieties of \cal V  are contained in a common higher-dimensional variety. For example, this restriction was used in Theorem 3, and more famously in the Guth–Katz proof of the planar distinct distances problem.
  • A transversality condition: When two varieties meet at a point p  , their tangent spaces at p  intersect only at one point. This condition was used in Theorem 1.
It is not clear what the “natural” restrictions are. For example, when studying incidences with two-dimensional planes in {\mathbb R}^4  most works rely on the transversality condition. In this case, the condition is equivalent to asking every two planes to intersect in at most one point. I recently noticed that the same incidence bound holds with a much weaker restriction of not too many planes in a hyperplane.

There is more to say about Conjecture 4, but this post is already getting longer than I intended.

Advertisements