Incidences: Lower Bounds (part 1)

This is the first in a new series of posts, in which I will survey the constructions leading to the best known lower bounds for the various incidence problems. Although recently many improved upper bounds for incidence problems were proven, not much progress was made concerning the lower bounds.

We begin with the case of point-line incidences in the plane. This is of course the matching lower bound for the famous Szemerédi–Trotter Theorem.

Theorem 1 (Szemerédi and Trotter). The maximum number of incidences between a set {\cal P}  of m  points and a set {\cal L}  of n  lines, both in {\mathbb R}^2  , is

I({\cal P},{\cal L})=O\left(m^{2/3}n^{2/3}+m+n\right).

Notice that the linear terms dominate this bound when either m =O(\sqrt{n})  or m =\Omega(n^2)  . Since a point-line configuration with \Omega(m+n)  incidences is easy to construct, we focus on obtaining \Omega(m^{2/3}n^{2/3})  incidences when n^{1/2} \ll m \ll n^2  .

Today the “common” construction for the planar point-line incidence bound is by Elekes. Elekes’ construction will be described in the next post of the series. Before that, in this post we present the original construction of Erdős. While this construction is mentioned in several places (e.g., see here), I could not locate the original paper that describes it. Many years later Edelsbrunner and Welzl rediscovered this construction.

Pach and Tóth use a variant of this construction to obtain the best known constant for the lower bound for the maximum number of point-line incidences. Specifically,

I({\cal P},{\cal L}) \ge 0.42 \cdot m^{2/3}n^{2/3}+m+n.

Recall that our goal is to construct a set of m  points and a set of n  lines, for any n^{1/2} \ll m \ll n^2  . Specifically, we assume that c n^{1/2} \le m  for a sufficiently large constant c  whose value will be determined below. As our point set, we take the following subset of the integer lattice.

{\cal P} = \left\{ (i,j) | 1 \le i \le \sqrt{m} \quad \text{ and } \quad -\frac{\sqrt{m}}{2} \le j \le \frac{\sqrt{m}}{2}\right\}.

Given a pair of relatively prime integers a<b, we define the line set:

{\cal L}_{a,b} = \left\{ y-j = \frac{a}{b}(x-i) | \quad 1 \le i \le b, \quad 1 \le j \le \frac{\sqrt{m}}{4} \right\}.

Notice that |{\cal L}_{a,b}| = b\sqrt{m}/4  . Our set of lines is the union of many sets of the form {\cal L}_{a,b}  . Specifically, we set k = c'n^{1/3}/m^{1/6}  (for a constant c'  that will be set below) and

{\cal L} = \bigcup_{1 \le a < b \le k \atop gcd(a,b)=1} {\cal L}_{a,b}.

The resulting point-line configuration is depicted in the following figure.


We claim that the lines of {\cal L}  are distinct. Indeed, two lines from the same set {\cal L}_{a,b}  are distinct since they intersect the x  -axis in distinct points. Two lines from two different sets are distinct since they have distinct slopes. We recall Euler’s totient function:

\phi(b) = \left| \{\ a \ |\ 1\le a < b \quad \text{ and } \quad \gcd(a,b)=1 \ \}\right|.

Notice that

|{\cal L}| = \sum_{1 \le b \le k} \left(\phi(b) \cdot \frac{b\sqrt{m}}{4}\right).

Since \sum_{i=1}^n i\cdot\phi(i)=\Theta(n^3)  (e.g., this is a variant of the proof of Theorem 330 in this book by Hardy and Wright), we have

|{\cal L}| = \frac{\sqrt{m}}{4} \sum_{1 \le b \le k} b\cdot\phi(b) = \Theta\left(\sqrt{m} k^3 \right) = \Theta\left((c')^3n\right).

Thus, by an appropriate choice of c'  , we obtain |{\cal L}|=n  .

It remains to bound the number of incidences in {\cal P}\times{\cal L}  . Consider a line \ell\in{\cal L}  that is defined by y-j = \frac{a}{b}(x-i)  and notice that \ell  is incident to a point in every r  -th column of the integer lattice. The slope of \ell  is smaller than one and it intersects the y  -axis below the point (0,\sqrt{m}/4)  . Moreover, by setting c  to be sufficiently large (with respect to c'  ) so that cn^{1/3}/m^{1/6} < \sqrt{m}/2  , we obtain that \ell  intersects the y  -axis above the point (0,-\sqrt{m}/2)  . Combining these properties, we notice that \ell  is incident to at least \frac{\sqrt{m}}{4b}-1  points of \cal P  , and thus

I({\cal P},{\cal L}) \ge \sum_{1 \le a < b \le k \atop gcd(a,b)=1} |{\cal L}_{a,b}| \cdot \left(\frac{\sqrt{m}}{4b}-1\right)
= \sum_{1 \le b \le k} \phi(b)\frac{b\sqrt{m}}{4} \left(\frac{\sqrt{m}}{4b}-1\right)
= \Omega\left(m\sum_{1 \le b \le k} \phi(b)\right).

Since \sum_{i=1}^n \phi(i)=\Theta(n^2)  (e.g., see Theorem 330 in this book by Hardy and Wright), we have

I({\cal P},{\cal L}) = \Omega\left(mb^2\right) = \Omega(m^{2/3}n^{2/3}).

This completes Erdős’ construction.


3 thoughts on “Incidences: Lower Bounds (part 1)

  1. Pingback: Incidences: Lower Bounds (part 2) | Some Plane Truths

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

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

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