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
| CREATOR | Zach Hunter, Cosmin Pohoata, Jacques Verstraete, Shengtong Zhang |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 114 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
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