← All papers
First page of A Szemerédi-Trotter Theorem in Arbitrary Fields

A Szemerédi-Trotter Theorem in Arbitrary Fields

Mark Lewko

math.CO Sep 22, 2026 · v3 math.CA math.NT
The four explicit-constant incidence bounds of the main Szemerédi–Trotter theorem over arbitrary fields are formalized in Lean, with a public repository.
Let $k$ be a field of characteristic $p\ge0$. 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.

The goal is an explicit Szemerédi–Trotter incidence bound for points and lines in the plane over an arbitrary field. In positive characteristic an extra term of order mn/p is necessary.

The proof uses the polynomial method. A nonzero polynomial S(x,y,z) is built that vanishes on every line, with the variable z specialized to the line's slope. Incidences are converted into root multiplicities on distinct parallel auxiliary lines, and a multiplicity lemma bounds these sums by d(d-1) for squarefree polynomials of degree below the characteristic. The four resulting incidence bounds (characteristic zero, general positive characteristic, mn ≤ p^3, and the prime field) are formalized in Lean, with AI assistants used to develop and check the formalization.

m points and n lines determine at most 3(mn)^{2/3}+m+n+2mn/p incidences, with coefficient 1 on mn/p over F_p; for m=n the bound is sharp up to an absolute constant over prime fields. Applications include restriction estimates for the paraboloid in F_p^3, error bounds for Bourgain's two-source extractor, improved sum-product estimates, and projection and Furstenberg estimates.