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

Advertisements