Szemerédi–Trotter theorem
Template:Short description The Szemerédi–Trotter theorem is a mathematical result in the field of Discrete geometry. It asserts that given Template:Mvar points and Template:Mvar lines in the Euclidean plane, the number of incidences (i.e., the number of point-line pairs, such that the point lies on the line) is
<math display=block>O \left ( n^{2/3} m^{2/3} + n + m \right ).</math>
This bound cannot be improved, except in terms of the implicit constants in its big O notation. An equivalent formulation of the theorem is the following. Given Template:Mvar points and an integer Template:Math, the number of lines which pass through at least Template:Mvar of the points is
<math display=block>O \left( \frac{n^2}{k^3} + \frac{n}{k} \right ).</math>
The original proof of Endre Szemerédi and William T. Trotter was somewhat complicated, using a combinatorial technique known as cell decomposition.<ref name="Szemerédi">Template:Cite journal</ref><ref>Template:Cite journal</ref> Later, László Székely discovered a much simpler proof using the crossing number inequality for graphs.<ref name="Székely">Template:Cite journal</ref> This method has been used to produce the explicit upper bound <math>2.5n^{2/3} m^{2/3} + n + m</math> on the number of incidences.<ref>Template:Cite journal</ref> Subsequent research has lowered the constant, coming from the crossing lemma, from 2.5 to 2.44.<ref>Template:Cite journal</ref> On the other hand, this bound would not remain valid if one replaces the coefficient 2.44 with 0.42.<ref>Template:Cite journal</ref>
The Szemerédi–Trotter theorem has a number of consequences, including Beck's theorem in incidence geometry and the Erdős-Szemerédi sum-product problem in additive combinatorics.
Proof of the first formulation
We may discard the lines which contain two or fewer of the points, as they can contribute at most Template:Math incidences to the total number. Thus we may assume that every line contains at least three of the points.
If a line contains Template:Mvar points, then it will contain Template:Math line segments which connect two consecutive points along the line. Because Template:Math after discarding the two-point lines, it follows that Template:Math, so the number of these line segments on each line is at least half the number of incidences on that line. Summing over all of the lines, the number of these line segments is again at least half the total number of incidences. Thus if Template:Mvar denotes the number of such line segments, it will suffice to show that
<math display=block>e = O \left ( n^{2/3} m^{2/3} + n + m \right).</math>
Now consider the graph formed by using the Template:Mvar points as vertices, and the Template:Mvar line segments as edges. Since each line segment lies on one of Template:Mvar lines, and any two lines intersect in at most one point, the crossing number of this graph is at most the number of points where two lines intersect, which is at most Template:Math. The crossing number inequality implies that either Template:Math, or that Template:Math. In either case Template:Math, giving the desired bound
- <math>e = O \left ( n^{2/3} m^{2/3} + n + m \right ).</math>
Proof of the second formulation
Since every pair of points can be connected by at most one line, there can be at most Template:Math lines which can connect at Template:Mvar or more points, since Template:Math. This bound will prove the theorem when Template:Mvar is small (e.g. if Template:Math for some absolute constant Template:Mvar). Thus, we need only consider the case when Template:Mvar is large, say Template:Math.
Suppose that there are m lines that each contain at least Template:Mvar points. These lines generate at least Template:Mvar incidences, and so by the first formulation of the Szemerédi–Trotter theorem, we have
<math display=block>mk = O \left ( n^{2/3} m^{2/3} + n + m \right ),</math>
and so at least one of the statements <math>mk = O( n^{2/3} m^{2/3} ), mk = O(n)</math>, or <math>mk = O(m)</math> is true. The third possibility is ruled out since Template:Mvar was assumed to be large, so we are left with the first two. But in either of these two cases, some elementary algebra will give the bound <math>m = O( n^2 / k^3 + n/k )</math> as desired.
Optimality
Except for its constant, the Szemerédi–Trotter incidence bound cannot be improved. To see this, consider for any positive integer <math>N\in \mathbb{N}</math> a set of points on the integer lattice
<math display=block>P = \left \{ (a, b) \in \mathbb{Z}^2 \ : \ 1 \leq a \leq N; 1 \leq b \leq 2N^2 \right \},</math>
and a set of lines
<math display=block>L = \left \{ (x, mx + b) \ : \ m, b \in \mathbb{Z}; 1 \leq m \leq N; 1 \leq b \leq N^2 \right \}.</math>
Clearly, <math>|P| = 2N^3</math> and <math>|L| = N^3</math>. Since each line is incident to Template:Mvar points (i.e., once for each <math>x \in \{1, \cdots, N\}</math>), the number of incidences is <math>N^4</math> which matches the upper bound.<ref>{{#invoke:citation/CS1|citation |CitationClass=web }}</ref>
Generalization to <math>\mathbb{R}^d</math>
One generalization of this result to arbitrary dimension, <math>\mathbb{R}^d</math>, was found by Agarwal and Aronov.<ref>Template:Cite journal</ref> Given a set of Template:Mvar points, Template:Mvar, and the set of Template:Mvar hyperplanes, Template:Mvar, which are each spanned by Template:Mvar, the number of incidences between Template:Mvar and Template:Mvar is bounded above by
<math display=block>O \left (m^{2/3}n^{d/3}+n^{d-1} \right ),</math>
provided <math> n^{d-2} < m < n^{d}</math>. Equivalently, the number of hyperplanes in Template:Mvar containing Template:Mvar or more points is bounded above by
<math display=block>O\left( \frac{n^d}{k^3} + \frac{n^{d-1}}{k} \right ).</math>
A construction due to Edelsbrunner shows this bound to be asymptotically optimal.<ref>Template:Cite book</ref>
József Solymosi and Terence Tao obtained near sharp upper bounds for the number of incidences between points and algebraic varieties in higher dimensions, when the points and varieties satisfy "certain pseudo-line type axioms". Their proof uses the Polynomial Ham Sandwich Theorem.<ref>Template:Cite journal</ref>
In <math>\mathbb{C}^2</math>
Many proofs of the Szemerédi–Trotter theorem over <math>\mathbb{R}</math> rely in a crucial way on the topology of Euclidean space, so do not extend easily to other fields. e.g. the original proof of Szemerédi and Trotter; the polynomial partitioning proof and the crossing number proof do not extend to the complex plane.
Tóth successfully generalized the original proof of Szemerédi and Trotter to the complex plane <math>\mathbb{C}^2</math> by introducing additional ideas.<ref>Template:Cite journal</ref> This result was also obtained independently and through a different method by Zahl.<ref>Template:Cite journal</ref> The implicit constant in the bound is not the same in the complex numbers: in Tóth's proof the constant can be taken to be <math>10^{60}</math>; the constant is not explicit in Zahl's proof.
When the point set is a Cartesian product, Solymosi and Tardos show that the Szemerédi-Trotter bound holds using a much simpler argument.<ref>Template:Cite book</ref>
In finite fields
Let <math>\mathbb{F}</math> be a field.
A Szemerédi-Trotter bound is impossible in general due to the following example, stated here in <math>\mathbb{F}_p</math>: let <math>\mathcal{P} = \mathbb{F}_p\times \mathbb{F}_p</math> be the set of all <math>p^2</math> points and let <math>\mathcal{L}</math> be the set of all <math>p^2</math> lines in the plane. Since each line contains <math>p</math> points, there are <math>p^3</math> incidences. On the other hand, a Szemerédi-Trotter bound would give <math>O((p^2)^{2/3} (p^2)^{2/3} + p^2) = O(p^{8/3})</math> incidences. This example shows that the trivial, combinatorial incidence bound is tight.
Bourgain, Katz and Tao<ref>Template:Cite journal</ref> show that if this example is excluded, then an incidence bound that is an improvement on the trivial bound can be attained.
Incidence bounds over finite fields are of two types: (i) when at least one of the set of points or lines is `large' in terms of the characteristic of the field; (ii) both the set of points and the set of lines are `small' in terms of the characteristic.
Large set incidence bounds
Let <math>q</math> be an odd prime power. Then Vinh<ref>Template:Cite journal</ref> showed that the number of incidences between <math>n</math> points and <math>m</math> lines in <math>\mathbb{F}_q^2</math> is at most
<math display=block>\frac{nm}{q} + \sqrt{qnm}.</math>
Note that there is no implicit constant in this bound.
Small set incidence bounds
Let <math>\mathbb{F}</math> be a field of characteristic <math>p\neq 2</math>. Stevens and de Zeeuw<ref>Template:Cite journal</ref> show that the number of incidences between <math>n</math> points and <math>m</math> lines in <math>\mathbb{F}^2</math> is
<math display=block>O\left(m^{11/15}n^{11/15}\right)</math>
under the condition <math>m^{-2}n^{13} \leq p^{15}</math> in positive characteristic. (In a field of characteristic zero, this condition is not necessary.) This bound is better than the trivial incidence estimate when <math>m^{7/8} < n < m^{8/7}</math>.
If the point set is a Cartesian Product, then they show an improved incidence bound: let <math>\mathcal{P} = A\times B \subseteq \mathbb{F}^2</math> be a finite set of points with <math>|A|\leq |B|</math> and let <math>\mathcal{L} </math> be a set of lines in the plane. Suppose that <math>|A||B|^2 \leq |\mathcal{L}|^3</math> and in positive characteristic that <math>|A||\mathcal{L}|\leq p^2</math>. Then the number of incidences between <math>\mathcal{P}</math> and <math>\mathcal{L} </math> is
<math display=block>O\left(|A|^{3/4}|B|^{1/2} |\mathcal{L}|^{3/4} + |\mathcal{L}| \right).</math>
This bound is optimal. Note that by point-line duality in the plane, this incidence bound can be rephrased for an arbitrary point set and a set of lines having a Cartesian product structure.
In both the reals and arbitrary fields, Rudnev and Shkredov<ref>Template:Cite journal</ref> show an incidence bound for when both the point set and the line set has a Cartesian product structure. This is sometimes better than the above bounds.
See also
- Hopcroft's problem, the algorithmic problem of detecting a point-line incidence