On point line incidences

Question

Given a set of $n$ points $P_1, \ldots, P_n$ and $n$ lines $L_1, \ldots, L_n$ in $\mathbb{F}^2$, consider the set $I=\{(p_i, L_j)|L_j\text{ contains }p_i\}$ of point line incidences. The famous Szemeredi Trotter theorem says that if $\mathbb{F} = \mathbb{R}$ then $|I| = O(n^{4/3})$. I have read somewhere that an upper bound of $O(n^{3/2})$ is very easy to prove and works for any field. However i cannot seem to figure out how to prove this. How does one prove this? The best I got after a bit of thought is the trivial $|I| \leq \binom{n}{2}\dfrac{n}{n - 1}$.

Answer 1

Suppose that $L_i$ has $m_i$ points on it, for $1\le i\le n$. There are $\binom{m_i}2$ pairs of points on $L_I$. Furthermore, for $i\neq j$, there cannot exist a pair of points which lies on both $L_i$ and $L_j$ (lines intersect in at most one point). Therefore, these sets of pairs of points are actually disjoint, so we conclude $$ \sum_{i=1}^n \binom {m_i}2\le \binom n2 $$ Since $x\mapsto x(x-1)/2$ is a convex function, you can apply Jensen's inequality to the LHS to attain $$\frac1n\sum_{i=1}^n \binom{m_i}2\ge \binom{\frac1n(m_1+\dots+m_n)}2=\binom{|I|/n}2.$$ Combining this with the previous inequality, you get $n\binom{|I|/n}{2}\le \binom n2$, which implies $|I| \in O(n^{3/2})$.

This bound is tight, and is attained when the points and lines form a projective plane.