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.

Advertisements

Very nice! This has bothered me for a long time too. A slight shorter proof, based on the same principles is as follows: let P_1 denote the set of points incident to at most |L|^1/2 lines, and let P_2 denote the set of points incident to more than |L|^1/2 lines. Then I(P,L) = I(P_1,L) + I(P_2,L). Apply the dyadic decomposition proof the first quantity (but summing only over $2^i<|L|^1/2$, where the first term $n^2/k^3$ dominates), and use the Cauchy-Schwarz bound on the second quantity, using the fact that |P_2|<<|L|^1/2 to obtain I(P_2,L) < |P_2||L|^1/2 + |L| << |L|.

Nice one Brendan. That does simplify the proof. I’m polishing my lecture notes now, and will add this proof.