On a condition of the Szemerédi–Trotter theorem

Question

In the original paper from Szemerédi and Trotter: https://link.springer.com/article/10.1007/BF02579194

They state the theorem $1$ only if $\sqrt{n} \leq t \leq \binom{n}{2}$. Where $t$ is the number of lines and $n$ is the number of points.

In further sources this condition does not appear, for example Wikipedia: https://en.wikipedia.org/wiki/Szemer%C3%A9di%E2%80%93Trotter_theorem

Also in the paper "Crossing Numbers and Hard Erdős Problems in Discrete Geometry", https://www.cs.umd.edu/~gasarch/TOPICS/erdos_dist/szekely.pdf, it is gone.

So is the condition not needed? Is this due to a better proof strategy, better methods? And can this also be shown by the methods Szemerédi and Trotter used?

Answer 1

The two different formulations of the theorem are actually equivalent to each other. To prove this, I will adopt Wikipedia's convention of using $n$ for the number of points and $m$ for the number of lines.

Szemerédi and Trotter's formulation: $$ \text{# incidences is }\quad O(n^{2/3}m^{2/3}) \quad \text{when} \quad \sqrt n < m<\binom n2\tag 1 $$ Wikipedia's and Székely's formulation: $$ \text{# incidences is }\quad O(n^{2/3}m^{2/3}+n+m) \tag2 $$

---

$(1)\implies (2)$:

Suppose that the number of incidences is at most $C_1 n^{2/3}m^{2/3}$ whenever $n^{1/2}<m<\binom n2$. Obviousouly, this is also less than $C_1(n^{2/3}m^{2/3}+n+m)$ whenever $n^{1/2}<m<\binom n2$. What about the other possible ranges for $m$?

• When $m<n^{1/2}$, we have $$C_1 n^{2/3}m^{2/3}<C_1n^{2/3}(n^{1/2})^{2/3}=C_1n<C_1(n^{2/3}m^{2/3}+n+m)$$

• Assume $m > \binom n2$. This implies $m>(n-1)^2/2$, so $n<1+\sqrt{2m}$. We have $$ C_1n^{2/3}m^{2/3}< C_1 \Big(1+\sqrt{2m}\Big)^{2/3}m^{2/3} $$ This last quantity is $O(\color{red}{m})$, so is also $O(n^{2/3}m^{2/3}+n+\color{red}m)$.

---

$(2)\implies (1)$

Suppose the number of incidences is at most $C(n^{2/3}m^{2/3}+n+m)$. We need to prove the number of incidences is also at most $C_1(n^{2/3}m^{2/3})$ when $n^{1/2}<m<\binom n2$. To do this, write $$ n^{2/3}m^{2/3}+n+m=n^{2/3}m^{2/3}+n^{2/3}\cdot \color{blue}{n^{1/3}}+m^{2/3}\cdot \color{brown}{m^{1/3}}\tag3 $$ Since $n^{1/2}<m$, we have $$ \color{blue}{n^{1/3}<m^{2/3}}\tag 4 $$ Since $m<\binom n2 < n^2/2$, we ahve $$ \color{brown}{m^{1/3}<n^{2/3}/2^{2/3}}\tag5 $$ Apply the bounds in $(4)$ and $(5)$ to the expression in $(3)$, we see that $(3)$ is at most $$ n^{2/3}m^{2/3}+n^{2/3}\cdot \color{blue}{m^{2/3}}+m^{2/3}\cdot \color{brown}{n^{2/3}/2^{2/3}} $$ Since this expression is $O(n^{2/3}m^{2/3})$, we have proved $(1)$.

Answer 2

Thanks to Mikes Comment here is the proof that both statements are equivalent.

Let $I(m,n)$ denote the maximal number of incidences for $n$ points and $m$ lines, then $I(m,n) \leq I(m',n)$ if $m \leq m'$, since we only add lines.

"1) => 2)" For some constant $c$: $c n^{2/3}m^{2/3}\geq I(n,m) \geq I(n,m')$ for all $m' \leq m$. If $m = \sqrt{n}$ then $n^{2/3}m^{2/3} =n$, so for some $c$: $c n \geq I(n,m)$ for all $\sqrt{n}\geq m$. If $m > \begin{pmatrix} n \\ 2 \end{pmatrix}$ then there are more points as intersection points of lines, since there are maximally $\begin{pmatrix} n \\ 2 \end{pmatrix}$ intersection points. So each extra point can lie exactly on one line, so $I(n,m) \in O(n^{2/3}m^{2/3}+m)$ in this case, since either the number of incidences in the intersection points dominates, which we can controll, or the number of extra points on the lines dominates. Putting all cases together in on formula yields $I(n,m) \in O(n^{2/3}m^{2/3}+n+m)$

"2) => 1)": For some constant $c$: $I(n,m)\leq c(n^{2/3}m^{2/3}+n+m)$ if $m \geq \sqrt{n}$ we have $n^{2/3}m^{2/3}\geq n$ so $I(n,m) \in O(n^{2/3}m^{2/3}) $ for $m\geq \sqrt{n}$.