Incidences: Lower Bounds (part 8)

We continue to survey the known lower bounds for incidence problems (the previous post in this series can be found here). After a couple of posts in {\mathbb R}^3  we now return to {\mathbb R}^2  , to introduce a new technique that I recently learned about. This technique was discovered by Jozsef Solymosi, and is described in a work of Solymosi and Endre Szabó that is unpublished at this point. As seems to often be the case with results of Solymosi, it is quite simple and elegent. In {\mathbb R}^2  this technique yields bounds that can also be obtained from Elekes’ technique (discussed in a previous post), but in higher dimensions it leads to new bounds that are also tight (which would hopefully discuss in a future post). I would like to thank Jozsef Solymosi for allowing me to describe his technique in this blog, and to Frank de Zeeuw for discussions that led to this post.

Jozsef Solymosi.

To introduce the technique, we first consider the case of axis-parallel parabolas. We begin by considering a construction of m  points, n  lines, and \Theta(m^{2/3}n^{2/3})  incidences (such as the constructions that were presented in the first couple of posts of this series). We consider the bijection \phi(x,y) =(x,y+x^2)  from {\mathbb R}^2  to itself, and apply \phi  on the point-line configuration. This bijection takes every line into an axis parallel parabola. Indeed, consider a line \ell that is parameterized as (x,ax+b)  and notice that \phi(\ell)  is the parabola that is parameterized as (x,x^2+ax+b)  . We thus have a point-parabola configuration with \Theta(m^{2/3}n^{2/3})  incidences.

In the above example we did not rely on any properties that are specific to parabolas. For any k\ge 2  , by considering the bijection \phi(x,y) =(x,y+x^k)  we get a construction with curves of degree k and \Theta(m^{2/3}n^{2/3})  incidences. Similarly, we may consider more involved bijections such as \phi(x,y) =(x,y+x^4+5x^3+2x-1)  .

To see why the bounds that this technique implies in {\mathbb R}^2  are subsumed by those of Elekes, let us again consider the case of parabolas that are parameterized as (x,x^2+ax+b)  . We can apply the analysis that we have seen in the post about Elekes’ technique to such parabolas as follows. We set r=(m^2/9n)^{1/3}  and s=(3n^2/m)^{1/3}  , and define the point set to be

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

We define the parabola set to be

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

It can be easily verified that |{\cal P}|=m  , |\Gamma|=n  , and I({\cal P},\Gamma)=\Theta(m^{2/3}n^{2/3})  . Moreover, the two techniques give the same construction (up to small changes). To see this, we apply the inverse bijection \phi^{-1}(x,y) =(x,y-x^k)  on \cal P  and \Gamma  from the above construction. The set \phi^{-1}({\cal P})  is an m  -point subset of an r \times (3rs+r^2)  section of the integer lattice. The set \phi^{-1}(\Gamma)  consists of n  lines, each incident to one point of each column of the lattice. This is almost identical to the construction that was presented in the second post of this series, although the number of rows in the lattice becomes larger as r  becomes larger than s  (i.e., as m  becomes larger than n  ).

When considering incidences with varieties of dimension at least two, Elekes’ method seems to break down while Solymosi’s method remains valid. I plan to discuss this in a future post of this series.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your 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