This is the fifth in my series of posts concerning lower bounds for incidence problems (see the previous post here). This is the last post of the series that takes place in the plane. However, before moving to higher dimensional bounds, I am taking a break from this series, and moving to other topics.
In this post we generalize Elekes’ lower bound construction for lines (e.g., see this previous post) so that it would apply to an infinite family of polynomial curves. This generalization provides another example of a phenomena that we mentioned before: Although it is widely believed that the number of incidences between points and constant-degree polynomial curves with no common components is , this is not the case when the number of curves is significantly larger than the number of points. I am not aware of any references for the following, and I originally heard them from Micha Sharir.
Update (11/26/2014): Frank de Zeeuw pointed out that a brief mentioning of these bounds can be found in Elekes’ Sums versus products in Number Theory, Algebra and Erdös Geometry.
We begin by generalizing Elekes’ technique to parabolas. For any given values of and (i.e., the required sizes for the point set and of the parabola set, respectively) we set and .
We define the point set as
We define the parabola set as
Notice that we indeed have
Consider a parabola that is defined by the equation , for some constants that satisfy the constraints of . Notice that for any value of in , there exists a corresponding value of in the range such that the point is incident to . That is, every parabola of is incident to exactly points of , and thus
Notice that this bound is asymptotically larger than when is asymptotically larger than . That is, we cannot expect an upper bound of when the number of parabolas is asymptotically larger than the number of points.