7 Incidence
\(C = C_2 + 1\)
\(\operatorname{\varepsilon }(\beta ) = \operatorname{\varepsilon _2}(\beta ) / 3\)
Let there be a set \(P\) of points and a set \(L\) of lines over a prime field, with \(|P| \leq n, |L| \leq n\) and \(p^\beta \leq n \leq p^{2 - \beta }\). Then the number of intersections is at most \( C n^{\frac32 - \operatorname{\varepsilon }(\beta )} \).
We reduce this to 7.5, by removing all points contained in at most \(n^{\frac12 - \operatorname{\varepsilon }(\beta )}\) lines. This removes at most \(n^{\frac32 - \operatorname{\varepsilon }(\beta )}\) points, which is corrected for with \(C = C_2 + 1\).
\(C_2 = \sqrt{2(C_3 + \frac{\sqrt2}4)}\)
Let there be a set \(P\) of points and a set \(L\) of lines over a prime field, with \(|P| \leq n, |L| \leq n\) and \(p^\beta \leq n \leq p^{2 - \beta }\), and each point intersecting with at least \(n^{\frac12 - \operatorname{\varepsilon }(\beta )}\) lines. Then the number of intersections is at most \(C_2 n^{\frac32 - \operatorname{\varepsilon }(\beta )}\).
We reduce this to 7.6, by removing all points contained in more than \(4 n^{\frac12 + \operatorname{\varepsilon }(\beta )}\) lines. There can be at most \(n^{1 - 2 \operatorname{\varepsilon }(\beta )} \frac{\sqrt2}4\) such points, by 5.5. Therefore, there are still many remaining points, and because each point has at least \(n^{\frac12 - \operatorname{\varepsilon }(\beta )}\) lines there are still many intersections.
Let there be a set \(P\) of points and a set \(L\) of lines over a prime field, with \(|P| \leq n, |L| \leq n\) and \(p^\beta \leq n \leq p^{2 - \beta }\), and each point contained in at least \(n^{\frac12 - \operatorname{\varepsilon }(\beta )}\) lines and at most \(4 n^{\frac12 + \operatorname{\varepsilon }(\beta )}\). Then the number of intersections is at most \(C_3 n^{\frac32 - \operatorname{\varepsilon _2}(\beta )}\).
We use ?? to claim that there exist two points, \(a, b\) such that for a large number of points they are both on a line from \(a\) and a line from \(b\). We only keep those, and because all points are contained in \(n^{\frac12 - \operatorname{\varepsilon }(\beta )}\) lines there are still many intersections. Then we remove all points on the line between \(a\) and \(b\). Because all lines, expect maybe one, intersect at most one such point, this step doesn’t remove many intersections. Now we can apply 7.7.
Let there be a set \(P\) of points and a set \(L\) of lines over a prime field, with \(|P| \leq n, |L| \leq n\) and \(p^\beta \leq n \leq p^{2 - \beta }\), two different points \(p_1, p_2\), which are both contained in at most \(4 n^{\frac12 + \operatorname{\varepsilon }(\beta )}\) lines, with no points in \(P\) on the line \(p_1 p_2\), and all points in \(P\) on an intersection of some line from \(p_1\) and some line from \(p_2\). Then the number of intersections is at most \(C' n^{\frac32 - \operatorname{\varepsilon '}(\beta )}\).
Let there be two sets \(A, B\) and a set \(L\) of lines over a prime field, with \(|A| \leq 4n^{\frac12 + 2\operatorname{\varepsilon }(\beta )}, |B| \leq 4n^{\frac12 + 2\operatorname{\varepsilon }(\beta )}, |L| \leq n\) and \(p^\beta \leq n \leq p^{2 - \beta }\). Then the number of intersections is at most \(C' n^{\frac32 - \operatorname{\varepsilon '}(\beta )}\).
We reduce to 7.9 by removing all lines which contain too few points.
Let there be two sets \(A, B\) and a set \(L\) of lines over a prime field, with \(|A| \leq 4n^{\frac12 + 2\operatorname{\varepsilon }(\beta )}, |B| \leq 4n^{\frac12 + 2\operatorname{\varepsilon }(\beta )}, |L| \leq n\) and \(p^\beta \leq n \leq p^{2 - \beta }\). Additionally, suppose there are at least \(n^{\frac12 - \operatorname{\varepsilon '}(\beta )}\) points on each line. Then the number of intersections is at most \(C'_2 n^{\frac32 - \operatorname{\varepsilon '}(\beta )}\).
We now remove all horizontal lines, to reduce to 7.10. This doesn’t remove many intersections because each point can intersect at most one horizontal line.
Let there be two sets \(A, B\) and a set \(L\) of non-horizontal lines over a prime field, with \(|A| \leq 4n^{\frac12 + 2\operatorname{\varepsilon }(\beta )}, |B| \leq 4n^{\frac12 + 2\operatorname{\varepsilon }(\beta )}, |L| \leq n\) and \(p^\beta \leq n \leq p^{2 - \beta }\). Additionally, suppose there are at least \(n^{\frac12 - \operatorname{\varepsilon '}(\beta )}\) points on each line. Then the number of intersections is at most \(C'_2 n^{\frac32 - \operatorname{\varepsilon '}(\beta )}\).
We apply ?? to get two values \(b_1, b_2 \in B\) such that many lines pass through these rows. Because there are many points on each line, only keeping those still gives many incidences. Now, a line can be described as two points \(a_1, a_2\), and the line would be the line passing through \((a_1, b_1), (a_2, b_2)\). Suppose it passes through a given point \((a, b)\). This gives \(a = \frac{b_2 - b}{b_2 - b_1} a_1 + \frac{b - b_1}{b_2 - b_1} a_2\), so \(\frac{b_2 - b}{b_2 - b_1} a_1 + \frac{b - b_1}{b_2 - b_1} a_2 \in A\). Equivalently, there are many (\(N^{3/2 - \epsilon }\)) triplets \((b, a_1, a_2) \in B \times A \times A\) such that \(\frac{b_2 - b}{b_2 - b_1} a_1 + \frac{b - b_1}{b_2 - b_1} a_2 \in A\). This implies that there must be many (\(N^{1/2 - \epsilon }\)) values of \(b\) such that there is a large number of pairs \((a_1, a_2)\) with this property. Now we can only keep those, remove \(b_1, b_2\), and apply 7.11
Let there be two sets \(A, B\) and a set \(L\) of non-horizontal lines over a prime field, with \(|A| \leq 4n^{\frac12 + 2\operatorname{\varepsilon }(\beta )}, |B| \leq 4n^{\frac12 + 2\operatorname{\varepsilon }(\beta )}, |L| \leq n\) and \(p^\beta \leq n \leq p^{2 - \beta }\). Suppose there are at least \(n^{\frac12 - \operatorname{\varepsilon '}(\beta )}\) points on each line, and lastly, suppose there are two values \(b_1, b_2 \notin B\), TODO. Then \(|B|\) is at most \(C'_5 n^{1/2 - \operatorname{\varepsilon '_2}(\beta ) - \operatorname{\varepsilon '}(\beta ) - 4 \operatorname{\varepsilon }(\beta )}\).
TODO