A Szemerédi-Trotter Theorem in Arbitrary Fields

Source abstract

Let $k$ be a field of characteristic $p>0$. We prove that $m$ points and $n$ lines in $k^2$ determine $O((mn)^{2/3}+m+n+mn/p)$ incidences. In characteristic zero the last term is omitted. The proof uses the polynomial method, and for $m=n$ the bound is sharp over prime fields. As applications, over prime fields with $p\equiv 3\pmod4$ we obtain the $L^2\to L^r$ extension estimate for the paraboloid in $F_p^3$ for $r>10/3$, and we show that Bourgain's paraboloid extractor extracts from independent sources of any min-entropy rate greater than $3/8=0.375$ with exponentially small error. We also improve sum-product estimates for small sets in positive characteristic.