A Szemerédi-Trotter Theorem in Arbitrary Fields

Let $k$ be a field of characteristic $p>0$. We prove that $m$ points and $n$ lines in $k^2$ determine $O((mn{)}^{2\mathrm{/}3}+m+n+mn\mathrm{/}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(\mathrm{m}\mathrm{o}\mathrm{d}4)$ we obtain the $L^2\to L^r$ extension estimate for the paraboloid in $F_p^3$ for $r>10\mathrm{/}3$, and we show that Bourgain’s paraboloid extractor extracts from independent sources of any min-entropy rate greater than $3\mathrm{/}8=0.375$ with exponentially small error. We also improve sum-product estimates for small sets in positive characteristic.