Large point-line matchings and small Nikodym sets

Abstract

For any integer $d\ge 2$ and prime power $q$, we construct unexpectedly large induced matchings in the point-line incidence graph of ${\mathbb{F}}_q^d$ by leveraging a new connection with the Furstenberg-Sárközy problem from arithmetic combinatorics. In particular, we significantly improve the previously well-known baselines when $q$ is prime, showing that ${\mathbb{F}}_q^2$ contains matchings of size $q^{1.233}$ and ${\mathbb{F}}_q^d$ contains matchings of size $q^{d-o_d(1)}$. These results and their proofs have several applications. First, we also obtain new constructions for finite field Nikodym sets in dimension $d\ge 2$, improving recent results of Tao by polynomial factors. For example, when $q$ is prime, we show the existence of Nikodym sets in ${\mathbb{F}}_q^d$ of size $q^d-q^{d-o_d(1)}$. Second, we construct a new minimal blocking set in $\mathrm{PG}(2,q)$, solving a longstanding problem in finite geometry. Third, we obtain new constructions for the minimal distance problem (in ${\mathbb{R}}^2$ and also in higher dimensions), improving a recent result of Logunov-Zakharov. We also obtain analogous results for general finite fields with large characteristics. In particular, in one of our constructions we introduce a new special set of points inside the norm hypersurface in ${\mathbb{F}}_q^d$, which directly generalizes the classical Hermitian unital and which may be of independent interest for applications.

45 pages, 1 figure