The Szemerédi–Trotter theorem is usually presented in one of the two following formulations.
Theorem 1. Given a set of points and a set of lines, both in , the number of incidences between the two sets is .
Theorem 2. Given a set of lines in , the number of points in that are incident to at least of the lines is (for ).
A third formulation, symmetric to the one in Theorem 2, considers the number of lines that are incident to at least points of a given point set. We ignore this formulation here.
Many papers mention that the statements of Theorems 1 and 2 are equivalent, and some also show how Theorem 2 can be easily derived from Theorem 1 (including this Wikipedia page). On the other hand, I could not locate a single source that shows how to derive Theorem 1 from Theorem 2. At first it might seem as if a simple dyadic decomposition would do the trick. However, this approach leads to an extra logarithmic factor in the bound.
This post presents a simple elegant argument that leads to an extra logarithmic factor. It then present a longer proof that does not yield this extra factor. The latter proof was recently presented to me by Noam Solomon. If you have a more elegant proof, I would be very happy to hear about it.
Proof with extra logarithmic factor. Consider a set of points and a set of lines. Let denote the number of points of that are incident to more than lines of and to at most such lines. We set . Since obviously holds for every and by applying Theorem 2, we have
We now move to the proof that does not yield an extra logarithmic factor.
Full proof. Let denote the constant in the -notation in the bound of Theorem 2, and assume that . We prove by induction on that for every set of points and set of lines, for a sufficiently large constant . For the induction basis, the claim holds for small values of (say, ) by taking to be sufficiently large. For the induction step, let denote the set of points of that are incident to less than lines of . By taking to be larger than , we have
Let denote the points of that are incident to at least lines of . If , then by the induction hypothesis we have . By combining this with we get .
It remains to consider the case where . Since every point of is incident to at least lines of , by Theorem 2 we have
By recalling that , we have , which in turn leads to . By plugging this into the bound (obtained by a simple application of the Cauchy-Schwarz inequality) and taking to be sufficiently large with respect to the constant in the -notation, we obtain . Combining this bound with completes the proof.