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

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})$.

## 6 thoughts on “Incidences: Lower Bounds (part 5)”

1. Frank de Zeeuw |