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 , a set of simlpe curves , both in , and two constant positive integers and , such that
- For every points of there are at most curves of that are incident to each of the points.
- Every two curves of intersect in at most points.
For example, consider the case where 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 and , we obtain the best known bound Similarly, for circles with arbitrary radii, we can apply Theorem 1 with and .
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 ? For example, if we know that all of the curves of have a degree of at most , but we are having a hard time determining the value of ? If the curves are allowed to have common components, then we can have when all the points of are incident to a component that is contained in all of the curves of . To make the situation less trivial, assume that no two curves of share a common component. In this case, Bézout’s theorem tells us that every two curves of can share at most common points. Therefore, we can apply Theorem 1 with and .
The paper of Wang, Yang, and Zhang derives the following improved theorem.
Theorem 2. Let be a positive integer, let , let be a finite set of algebraic curves in of degree at most among which there are no repeated components, and let be a finite set of points in . Then where the constant of proportionality depends on .
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 , beyond the maximum degree .
For any positive integer , let denote the set of real bivariate polynomial equations of degree at most , 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 of degree at most (i.e., the number of distinct nonconstant monomials in the equations of ) is . We consider the following correspondence between the equations of and the points of the -dimensional projective space :
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 , we say its corresponding (projective) point set is . We can now present another theorem by Wang, Yang, and Zhang.
Theorem 3. Consider a positive constant . Let be a finite set of points in , let be a set of polynomials of degree at most in , and let be the set of equations of the form for every . If no two curves of share a common factor and is contained in a projective variety of dimension (and some constant degree ), then where the constant of proportionality depends on .
As an example, assume that we have a set of curves of degree at most that are parameterized by parameters. Then we know the the points in that correspond to these curves are contained in a -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).