Large point-line matchings and small Nikodym sets

Zach Hunter, Cosmin Pohoata, Jacques Verstraete, Shengtong Zhang · 2026

Read Large point-line matchings and small Nikodym sets by Zach Hunter, Cosmin Pohoata, Jacques Verstraete, Shengtong Zhang (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-19879.txt.

Introduction

Zach Hunter, Cosmin Pohoata, Jacques Verstraete, and Shengtong Zhang connect two problems in combinatorics. One concerns point-line incidences: points and lines in a finite geometry, and the graph recording which points lie on which lines. The other is the Furstenberg-Sárközy problem from arithmetic combinatorics, about patterns in dense sets of integers.

Using that connection, the authors construct unexpectedly large induced matchings in the incidence graph. A matching pairs points with lines exclusively; induced means no extra incidences sneak in. Large matchings in turn yield small Nikodym sets, sets that contain a full line in every direction. Such constructions test the limits of finite geometry. They often feed back into number theory and theoretical computer science.

Catalog record

CREATORZach Hunter, Cosmin Pohoata, Jacques Verstraete, Shengtong Zhang
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE114 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2601-19879

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Large point-line matchings and small Nikodym sets Thanks: Department of Mathematics, ETH, Zurich, Switzerland. Email: [email protected] . Thanks: Department of Mathematics, Emory University, Atlanta, GA. Email: [email protected] . Thanks: Department of Mathematics, UCSD, San Diego, CA. Email: [email protected] . Thanks: Department of Mathematics, Stanford University, Stanford, CA. Email: [email protected] . Zach Hunter, Cosmin Pohoata, Jacques Verstraete, Shengtong Zhang Abstract . For any integer d ≥ 2 d\geq 2 and prime power q q , we construct unexpectedly large induced matchings in the point-line incidence graph of 𝔽 q d \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 q is prime, showing that 𝔽 q 2 \mathbb{F}_{q}^{2} contains matchings of size q 1.233 q^{1.233} and 𝔽 q d \mathbb{F}_{q}^{d} contains matchings of size q d − o d ​ ( 1 ) 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 ≥ 2 d\geq 2 , improving recent results of Tao by polynomial factors. For example, when q q is prime, we show the existence of Nikodym sets in 𝔽 q d \mathbb{F}_{q}^{d} of size q d − q d − o d ​ ( 1 ) q^{d}-q^{d-o_{d}(1)} . Second, we construct a new minimal blocking set in PG ⁡ ( 2 , q ) \mathrm{PG}(2,q) , solving a longstanding problem in finite geometry. Third, we obtain new constructions for the minimal distance problem (in ℝ 2 \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 𝔽 q d \mathbb{F}_{q}^{d} , which directly generalizes the classical Hermitian unital and which may be of independent interest for applications. 1. Introduction 1.1. Induced matchings and Nikodym sets For an integer d\geq 1 and prime power q , let \mathbb{F}_{q}^{d} denote the d -dimensional vector space over the finite field \mathbb{F}_{q} of order q . Let \mathcal{I}_{q}^{(d)} be the bipartite graph whose left vertex set is the set of points in \mathbb{F}_{q}^{d} , whose right vertex set is the set of affine lines in \mathbb{F}_{q}^{d} , and where a point is adjacent to a line if and only if it lies on that line. The object that we will be studying in this paper is the following parameter. Definition 1.1 (Induced matchings) . Let \mathrm{IM}(d,q) be the maximum size of an induced matching in \mathcal{I}_{q}^{(d)} . Equivalently, \mathrm{IM}(d,q) denotes the largest m for which there exist pairs (p_{1},\ell_{1}),\dots,(p_{m},\ell_{m}) with p_{i}\in\ell_{j} if and only if i=j . We will be interested in the regime where the dimension d is fixed and q is large. The problem of estimating \mathrm{IM}(2,q) was recently highlighted by Cohen–Pohoata–Zakharov [ 11 ] , in a surprising connection with the Heilbronn triangle problem. As noted in [ 11 , §1.5] , a Szemerédi–Trotter type incidence theorem of Vinh [ 45 ] implies the general upper bound \mathrm{IM}(2,q)\leq q^{3/2}+q. (1) When q=p^{2} is a square, ( 1 ) is sharp up to constants, because of the so-called Hermitian unitals defined on the affine plane by P:=\{(a,b)\in\mathbb{F}_{q}^{2}:\ a^{p+1}+b^{p+1}=1\}. (2) It is well-known that |P|=p^{3}-p=q^{3/2}-q^{1/2} . Through each (a,b)\in P there is a unique tangent line \ell_{a,b} meeting P only at (a,b) ; in affine coordinates one may take \ell_{a,b}=\{(a,b)+t(b^{p},-a^{p}):t\in\mathbb{F}_{q}\}=\{(x,y)\in\mathbb{F}_{q}^{2}:\ a^{p}x+b^{p}y=1\}. (3) Thus the pairs \{((a,b),\ell_{a,b}):(a,b)\in P\} form an induced matching in \mathcal{I}_{q} of size |P| , giving \mathrm{IM}(2,q)\geq q^{3/2}-q^{1/2} . Hermitian unitals have recently been featured in several constructions in extremal combinatorics, most notably in the recent paper of Mattheus–Verstraëte [ 33 ] on the asymptotics of the off-diagonal Ramsey R(4,t) . That being said, the unital construction is not applicable when q is not a perfect square, and the best known lower bound for \mathrm{IM}(2,q) prior to this work has been of the form \mathrm{IM}(2,q)\gg q\log q 1 1 1 Throughout the paper, we will write f\gg g or f=\Omega(g) or if there exists a positive constant C such that |f(x)|\geq Cg(x) for all x . We will also write f\ll g or f=O(g) if g\gg f , and f\asymp g if f\gg g and f\ll g both hold. We say f=o(g) if for any \varepsilon>0 , |f(x)|\leq\varepsilon g(x) for all sufficiently large x . . This is achieved by either choosing the point set randomly or lifting a clique from the Paley graph (see Section 2 for the important backstory). Our foundational result improves upon this “baseline bound” by a polynomial factor for all prime q . Theorem 1.2 . For all primes q , we have \mathrm{IM}(2,q)\gg q^{1.2334}. For d\geq 3 , no analogue of ( 1 ) is known, and it is in fact an open problem to show \mathrm{IM}(d,q)=o(q^{d}) . This question is typically stated in a different language, in terms of so-called Nikodym sets . We next formally define Nikodym sets and state their connections. Fix d\geq 2 and a prime power q . For x\in\mathbb{F}_{q}^{d} and v\in\mathbb{F}_{q}^{d}\setminus\{0\} , write \ell(x,v):=\{x+tv:\ t\in\mathbb{F}_{q}\} for the affine line through x with direction v , and \ell(x,v)^{\!*}:=\ell(x,v)\setminus\{x\} for the corresponding punctured line. Definition 1.3 (Nikodym set) . A set N\subset\mathbb{F}_{q}^{d} is a Nikodym set if for every x\in\mathbb{F}_{q}^{d} there exists v\in\mathbb{F}_{q}^{d}\setminus\{0\} such that \ell(x,v)^{\!*}\subset N . Let \mathrm{Nikodym}(d,q) be the size of the smallest Nikodym set in \mathbb{F}_{q}^{d} . Nikodym sets are a finite-field analogue of the classical Euclidean Nikodym problem, and are closely related (via projective transformations) to Kakeya sets. See, for instance, Dvir’s beautiful survey [ 13 ] and the references therein. From this perspective, point–line matchings can be regarded as a weaker version of Nikodym sets, where only points outside N are required to have a punctured line contained in N . Definition 1.4 (Weak Nikodym set) . A set N\subset\mathbb{F}_{q}^{d} is a weak Nikodym set if for every x\in\mathbb{F}_{q}^{d}\setminus N there exists v\in\mathbb{F}_{q}^{d}\setminus\{0\} such that \ell(x,v)^{\!*}\subset N . To keep a clear picture, we summarize the relationship between Nikodym sets and weak Nikodym sets in the following simple proposition. See Section 7 for the complete proof. Proposition 1.5 . 1) Any Nikodym set is a weak Nikodym set, but not vice versa. 2) A set in \mathbb{F}_{q}^{d} is a weak Nikodym set if and only if its complement is contained in an induced matching in \mathcal{I}_{q}^{(d)} . 3) If a set N\subset\mathbb{F}_{q}^{d} is a weak Nikodym set, then the set N\times\mathbb{F}_{q}\subset\mathbb{F}_{q}^{d+1} is a Nikodym set. Part 2) and 3) shows the implications \mathrm{IM}(d,q)=o(q^{d})\Longrightarrow\mathrm{Nikodym}(d,q)=q^{d}-o(q^{d})\Longrightarrow\mathrm{IM}(d-1,q)=o(q^{d-1}). The problem of showing \mathrm{Nikodym}(d,q)=q^{d}-o(q^{d}) is a well-known open problem in the area, see for example [ 30 ] . We will next establish new lower bounds for the quantity \mathrm{IM}(d,q) when d\geq 3 , which due to Proposition 1.5 will also come with new constructions for Nikodym sets in \mathbb{F}_{q}^{d} . 1.2. Large induced matchings in higher dimensions In higher dimensions, the “baseline bound” is \mathrm{IM}(d,q)\gg q^{d-1}\log q . We will discuss the history of this bound in the next subsection. Before our work, the only known improvement upon the baseline bound when q is a

Read the complete text