Even more new results!

I just wrote about the new distinct distances result of Pach and de Zeeuw, and already two new related papers appeared on arXiv. The rate of new papers that deal with distinct distances and incidence problems (mainly by applying algebraic tools) is becoming a bit crazy.

One of the new arXiv papers is a distinct distances result by Sharir and Solymosi. I plan to write a post about this paper soon. The other paper, which I will describe in this post, is an incidence result by Wang, Yang, and Zhang. Thanks to Joshua Zahl and to Frank de Zeeuw for pointing out these papers out to me (and do tell me about other related results if you happen to notice any! I am planning to set up a webpage that lists all of the papers that are related to the recent polynomial method/algebraic method).

The following theorem is a classic incidence result that was published by Pach and Sharir in 1998.

Theorem 1. Consider a point set \cal P  , a set of simlpe curves \Gamma  , both in {\mathbb R}^2  , and two constant positive integers k  and s  , such that
  • For every k  points of \cal P  there are at most s  curves of \Gamma  that are incident to each of the k  points.
  • Every two curves of \Gamma  intersect in at most s  points.
Then I({\cal P},\Gamma) = O(|{\cal P}|^{k/(2k-1)}|\Gamma|^{(2k-2)/(2k-1)}+|{\cal P}|+|\Gamma|),  where the constant of proportionality depends on k  and s  .

For example, consider the case where \Gamma  is a set of unit circles (i.e., circles with a radius of 1). A pair of points can have at most two common unit circles through them and every two unit circles intersect in at most 2 points. Therefore, by applying Theorem 1 with k=2  and s=2  , we obtain the best known bound I({\cal P},\Gamma) = O(|{\cal P}|^{2/3}|\Gamma|^{2/3}+|{\cal P}|+|\Gamma|).  Similarly, for circles with arbitrary radii, we can apply Theorem 1 with k=3  and s=2  .

UnitCircles

To stress how useful Theorem 1 is, notice that it has been used in the new paper of Pach and de Zeeuw, in the new paper of Sharir and solymosi, in the six months old paper by Sharir, Solymosi, and myself, and so on…

What happens if we have less information about \Gamma  ? For example, if we know that all of the curves of \Gamma  have a degree of at most D  , but we are having a hard time determining the value of k  ? If the curves are allowed to have common components, then we can have I({\cal P},\Gamma) = \Theta(|{\cal P}| |\Gamma|)  when all the points of \cal P  are incident to a component that is contained in all of the curves of \Gamma  . To make the situation less trivial, assume that no two curves of \Gamma  share a common component. In this case, Bézout’s theorem tells us that every two curves of \Gamma  can share at most d^2  common points. Therefore, we can apply Theorem 1 with k=d^2+1  and s=d^2  .

The paper of Wang, Yang, and Zhang derives the following improved theorem.

Theorem 2. Let D  be a positive integer, let A = \binom{D+2}{2} -1  , let \Gamma  be a finite set of algebraic curves in {\mathbb R}^2  of degree at most D  among which there are no repeated components, and let \cal P  be a finite set of points in {\mathbb R}^2  . Then I({\cal P},\Gamma) = O(|{\cal P}|^{A/(2A-1)}|\Gamma|^{(2A-2)/(2A-1)}+|{\cal P}|+|\Gamma|),  where the constant of proportionality depends on D  .

Theorems 1 and 2 imply the same bound for the case of general curves of degree at most 1 or 2. Already for curves of degree at most 3 Theorem 2 implies a stronger bound, and as the maximum degree increases, the bound of Theorem 2 becomes significantly better. The paper presents another result, for cases where we have some more information on \Gamma  , beyond the maximum degree D  .

For any positive integer D>0  , let E_D  denote the set of real bivariate polynomial equations of degree at most D  , where two equations are considered to be equivalent if one is a constant multiple of the other. It can be easily verified that the number of nonconstant monomials in {\mathbb R}[x,y]  of degree at most D  (i.e., the number of distinct nonconstant monomials in the equations of E_D  ) is A_D = \binom{D+2}{2}-1  . We consider the following correspondence between the equations of E_D  and the points of the A_D  -dimensional projective space {\mathbb R}\mathbf{P}^{A_D}  :

\tau: \sum_{i,j \ge 0 \atop i+j\le D} a_{ij}x^iy^j \to (a_{ij}).

Notice that the projective coordinates work well, since we may always assume that the constant term of an equation is either 0 or 1. Given a subset of equations S\subset E_D  , we say its corresponding (projective) point set is \tau(S)  . We can now present another theorem by Wang, Yang, and Zhang.

Theorem 3. Consider a positive constant D  . Let \cal P  be a finite set of points in {\mathbb R}^2  , let \Gamma  be a set of polynomials of degree at most D  in {\mathbb R}[x,y]  , and let E_\text{curves}  be the set of equations of the form \gamma=0  for every \gamma\in\Gamma  . If no two curves of \Gamma  share a common factor and \tau(E_\text{curves})\subset {\mathbb R}\mathbf{P}^{A_D}  is contained in a projective variety of dimension k  (and some constant degree d  ), then I({\cal P},\Gamma) = O(|{\cal P}|^{k/(2k-1)}|\Gamma|^{(2k-2)/(2k-1)}+|{\cal P}|+|\Gamma|),  where the constant of proportionality depends on D, k, d  .

As an example, assume that we have a set of curves of degree at most D  that are parameterized by k  parameters. Then we know the the points in {\mathbb R}\mathbf{P}^{A_D}  that correspond to these curves are contained in a k  -dimensional projective variety. The paper also derives extensions of these bounds to complex and finite fields, but I do not discuss these here.

While the proof of Theorem 1 by Pach and Sharir is based on the crossing lemma technique, as introduced by Székely (a nice introduction to this technique can be found in this post by Tao), the new proofs rely on polynomial partitionings (which I just discussed in this series of posts; more advanced posts about this topic should appear soon).

Advertisements

Leave a Reply

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

WordPress.com Logo

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