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.

We now generalize this construction to curves that are defined by polynomials of the form (where is a positive integer). In this case, we set and . We define the point set as

We define the set of curves as

As before, we have

Notice that the curves of are irreducible, and thus two of these curves cannot have a common component. Also as before, every curve of is incident to exactly points of . Thus,

This bound is asymptotically larger than when is asymptotically larger than (for ). Since for any , this does not violate the conjecture that the number of incidences between curves and constant-degree curves is .

Advertisements

Hey Adam,

These examples can be found in Elekes’s “SUMS versus PRODUCTS” survey, Example 1.25. Far less detail, though.

I really like your lower bounds series, I’m happy these constructions are finally gathered somewhere.

Here is another “construction” for curves: Take Elekes’s construction with lines y=ax+b, and apply the transformation (x,y)->(x, x^2+y). Then the line parametrized by (t,at+b) is sent to (t, t^2+at+b), which is the parabola y=x^2+ax+b.

Different transformations will give different classes of curves.

Thank you for the comments Frank! They are very helpful. Regarding gathering all of the constructions somewhere, I am also turning these into a pdf file and will put it online somewhere. If you think of any other relevant things for it, please tell.

I actually heard about this construction from Jozsef and completely forgot about it (in fact, I think that you were also there). So perhaps there needs to be another planar post. If I recall correctly, he mentioned that there are only five (?) types of curves that this works for. Do you know anything about this?

Yes, I got that from Jozsef, but pretty long ago, and I don’t remember exactly. I don’t think it’s written down anywhere. I will ask him about it and let you know.

Pingback: Incidences: Lower Bounds (part 6) | Some Plane Truths

Pingback: Incidences: Lower Bounds (part 8) | Some Plane Truths