A Szemerédi-Trotter Theorem in Arbitrary Fields

Abstract

Let $k$ be a field of characteristic $p\ge 0$. We prove that $m$ points and $n$ lines in $k^2$ determine at most $3(mn{)}^{2/3}+m+n+2mn/p$ incidences, the last term being omitted in characteristic zero. Over the prime field ${\mathbb{F}}_p$ the coefficient of $mn/p$ can be replaced by $1$. The proof uses the polynomial method, and for $m=n$ the bound is sharp up to an absolute constant over prime fields. As applications, over prime fields in which $-1$ is not a square we obtain the $L^2\to L^r$ extension estimate for the paraboloid in ${\mathbb{F}}_p^3$ for $r>10/3$. Over every odd prime field, we show that a two-source extractor construction of Bourgain has exponentially small error at every min-entropy rate greater than $1/3$. We also improve sum-product estimates for small sets in positive characteristic and obtain projection and Furstenberg estimates over prime fields. The incidence inequalities with exact constants have been formalized in Lean.

arXiv comment26 pages, no figures. v3: Explicit constants are given, and a link to the Lean formalization is included