Incidences: Lower Bounds (part 5)

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 n  points and n  constant-degree polynomial curves with no common components is O(n^{4/3})  , 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.

Sharir2
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 m  and n  (i.e., the required sizes for the point set and of the parabola set, respectively) we set r=m^{1/2}/(3^{1/2}n^{1/6})  and s=(3n/m)^{1/2}  .

We define the point set as

{\cal P} = \left\{\ (i,j)\ | \ 1 \le i \le r \quad \text{ and } \quad 1 \le j \le 3r^2s \ \right\}.

We define the parabola set as

\Gamma = \left\{\ y=ax^2+bx+c \ | \ 1 \le a \le s,  \quad 1 \le b \le rs, \quad \text{ and } \quad 1 \le c\le r^2s \ \right\}.

Notice that we indeed have

|{\cal P}| = 3r^3s = 3\cdot \frac{m^{3/2}}{3^{3/2}n^{1/2}} \cdot (3n/m)^{1/2} = m,
|\Gamma|  = r^3s^3 = \frac{m^{3/2}}{3^{3/2}n^{1/2}} \cdot (3n/m)^{3/2} = n.

Consider a parabola \gamma  that is defined by the equation y=ax^2+bx+c  , for some constants a,b,c  that satisfy the constraints of \Gamma  . Notice that for any value of x  in \{1,\ldots,r\}  , there exists a corresponding value of y  in the range \{1,\ldots, 3r^2s\}  such that the point (x,y)  is incident to \gamma  . That is, every parabola of \Gamma  is incident to exactly r  points of \cal P  , and thus

I({\cal P},\Gamma) = r \cdot |\Gamma| =  \frac{m^{1/2}}{3^{1/2}n^{1/6}} \cdot n = 3^{-1/2}m^{1/2}n^{5/6}.

Notice that this bound is asymptotically larger than m^{2/3}n^{2/3}  when n  is asymptotically larger than m  . That is, we cannot expect an upper bound of O(m^{2/3}n^{2/3})  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 y=a_0x^k+a_1x^{k-1} +a_2x^{k-2}+ \cdots +a_k  (where k  is a positive integer). In this case, we set r=m^{2/(k+2)}/\left((k+1)^{2/(k+2)}n^{2/(k+1)(k+2)}\right)  and s=(k+1)^{k/(k+2)}n^{2/(k+2)}/m^{k/(k+2)}  . We define the point set as

{\cal P} = \left\{\ (i,j)\ | \ 1 \le i \le r \quad \text{ and } \quad 1 \le j \le (k+1)r^{k}s \ \right\}.

We define the set of curves as

\Gamma = \left\{\ y=a_0x^k+a_1x^{k-1}+\cdots+a_k \ | \ 1 \le a_i \le sr^i, \quad \text{ for every } 0 \le i \le k \ \right\}.

As before, we have

|{\cal P}| = (k+1)r^{k+1}s = (k+1)\cdot \frac{m^{2(k+1)/(k+2)}}{(k+1)^{2(k+1)/(k+2)}n^{2/(k+2)}} \cdot \frac{(k+1)^{k/(k+2)}n^{2/(k+2)}}{m^{k/(k+2)}}=m,
|\Gamma| = r^{k(k+1)/2}s^{k+1} = \frac{m^{k(k+1)/(k+2)}}{(k+1)^{k(k+1)/(k+2)}n^{k/(k+2)}} \cdot \frac{(k+1)^{k(k+1)/(k+2)}n^{2(k+1)/(k+2)}}{m^{k(k+1)/(k+2)}} = n.

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

I({\cal P},\Gamma) = r \cdot |\Gamma| =  \frac{m^{2/(k+2)}}{(k+1)^{2/(k+2)}n^{2/(k+1)(k+2)}} \cdot n = \Theta\left(m^{2/(k+2)}n^{k(k+3)/(k+1)(k+2)}\right).

This bound is asymptotically larger than m^{2/3}n^{2/3}  when n  is asymptotically larger than m^{2(k+1)/(k+4)}  (for k\ge 2  ). Since 2(k+1)/(k+4) \ge 1  for any k\ge 2  , this does not violate the conjecture that the number of incidences between n  curves and n constant-degree curves is O(n^{4/3})  .

Advertisements

5 thoughts on “Incidences: Lower Bounds (part 5)

  1. 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.

  2. 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.

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

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

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