PaperlayerView exact revision on arXiv

Source-linked AI summary

New Nikodym set constructions over finite fields

Terence Tao

arXiv:2511.07721v2math.CO

TL;DR

The paper addresses the lack of non-trivial upper bounds for higher-dimensional Nikodym sets when q has unbounded characteristic and is not a perfect square. It develops constructions inspired by AlphaEvolve and DeepThink, then proves them with human-generated arguments. The resulting bounds improve the naive random construction for odd prime powers and recover the known two-dimensional perfect-square bound under stated conditions.

  • Problem

    Non-trivial upper bounds for Nikodym sets in dimensions d>2 remained open when q has unbounded characteristic and is not a perfect square.

    Source: §1 · p. 3

  • Method

    The paper combines probabilistic and algebraic constructions discovered through AlphaEvolve and DeepThink explorations with complete human-generated proofs.

    Source: §1 · p. 4

  • Results

    For d≥3 and odd prime-power q, the paper proves a new asymptotic upper bound, while in dimension two it obtains q^2 − q^3/2 + O(q log q) for qualifying perfect squares.

    Source: §1 · p. 4

  • Takeaways & Limitations

    The results show that purely random sets are not optimal in the odd-q higher-dimensional regime and extend non-trivial constructions beyond the previously settled cases.

    Source: §1 · pp. 3–4

    The improved heuristic bound (1.8) is not proved, and the paper leaves it as an open conjecture; the asymptotic notation also fixes dimension and parameters while q→∞.

    Source: §1.1 · p. 5, §2.1 · p. 6

Abstract

from arXiv · show

For any fixed dimension $d \geq 3$ we construct a Nikodym set in $F_q^d$ of cardinality $q^d - (\frac{d-2}{\log 2} +1+o(1)) q^{d-1} \log q$ in the limit $q \to \infty$, when $q$ is an odd prime power. This improves upon the naive random construction, which gives a set of cardinality $q^d - (d-1+o(1)) q^{d-1} \log q$, and is new in the regime where $F_q$ has unbounded characteristic and $q$ not a perfect square. While the final proofs are completely human generated, the initial ideas of the construction were inspired by output from the tools \texttt{AlphaEvolve} and \texttt{DeepThink}. We also present a simple construction of Nikodym sets in $F_q^2$ for $q$ a perfect square that is a special case of known unital-based constructions, and matches the existing bounds of $q^2 - q^{3/2} + O(q \log q)$, assuming that $q$ is not the square of a prime $p \equiv 3 \pmod{4}$.

1. INTRODUCTION

The paper develops new small Nikodym sets beyond the perfect-square and bounded-characteristic regimes, while clarifying the gap from Kakeya constructions and the role of computer-assisted discovery.

1. INTRODUCTION

  • A projective transformation gives that, up to lower-order error, the smallest Nikodym set is at least as large as the smallest Kakeya set, despite an expected significant gap between them.The paper summarizes this gap through known upper and lower bounds.Source: §1 · p. 2
  • The main open regime is d>2 with unbounded characteristic and q not a perfect square, where prior results left non-trivial upper bounds unresolved.This regime is distinct from known results for d≤2, bounded characteristic, or perfect-square q.Source: §1 · p. 3
  • The construction was inspired by AlphaEvolve and DeepThink explorations, but the stronger heuristic bound remained unproved and is posed as an open conjecture.Human inspection converted some computationally generated ideas into a rigorous probabilistic argument, while the improved bound (1.8) was not established.Source: §1 · pp. 3–4
  • The paper improves the odd-q bound obtained from the probabilistic method when d≥3, showing that purely random sets are not optimal in this regime.The stronger result applies to odd q; for even q or perfect-square q, other known bounds can be superior.Source: §1 · p. 4
  • For fixed d≥3 and odd prime-power q, the paper proves a new asymptotic upper bound for Nikodym sets as q→∞.The proof is complete and human-generated, although computational exploration helped discover the construction.Source: §1 · p. 4
  • In two dimensions, the paper gives a perfect-square construction of cardinality q^2 − q^3/2 + O(q log q), recovering the known upper bound under a prime-square exclusion.The construction is a special case of a known unital-based construction and is verified by a human-written proof.Source: §1 · p. 4

2. THE PROBABILISTIC METHOD

The probabilistic method gives a rigorous random Nikodym-set bound, while heuristic variety-removal arguments motivate a stronger conjectural construction. A projective-invariance-based modification of the probabilistic method overcomes the main algebraic-geometric obstacle and establishes an intermediate bound.

2. THE PROBABILISTIC METHOD

  • The probabilistic proof applies Bennett’s inequality to the random set size, obtaining exponentially small lower-tail probability before controlling the Nikodym property.The relevant lower-tail failure probability is ≪ exp(−c_ε q^{d−1} log q).Source: §2 · pp. 5–6
  • For sufficiently large q, the construction produces a Nikodym set of size at most q^d − (d−1 + 2ε)q^(d−1) log q with positive probability, without requiring q to be odd.Source: §2 · pp. 5–6

2.1. Heuristic arguments.

  • Heuristics for deleting varieties model line intersections through Chebotarev densities and suggest that quadratic varieties could improve the deletion count by a factor of 1/log 2.The quadratic heuristic predicts k approximately log(q^{d−1})/log 2 and the bound (1.8), but this remains non-rigorous.Source: §2.1 · pp. 6–7
  • The quadratic heuristic fails geometrically because non-tangent lines typically meet a quadratic variety in a second point, forcing attention toward tangent lines and weakening the construction.This flaw undermines the direct use of deleted quadratic varieties for constructing Nikodym sets.Source: §2.1 · p. 7
  • The rigorous intermediate construction randomly adds points after deleting quadratic varieties and repairs exceptional points, but Lang–Weil errors are too large for the conjectured bound.Projective linear invariance combined with the probabilistic method retains many available directions and keeps errors below o(1/q), establishing the intermediate bound without advanced étale-cohomology machinery.Source: §2.1 · p. 7

3. PROOF OF NEW UPPER BOUND

The proof builds a robust almost Nikodym set by deleting random quadratic varieties, restoring random points to handle geometric obstructions, and applying probabilistic reductions and a second-moment argument.

3.1. Step 1: Reduction to constructing an almost Nikodym set.

  • The proof reduces the target construction to an almost Nikodym set, then upgrades robustness by random thinning and finally inserts punctured lines through exceptional points.The almost-set reduction tolerates failures on a small proportion of points, while robustness supplies many candidate lines for the thinning step.Source: §3.1 · p. 8, §3.2 · pp. 8–9

3.3. Step 3: Construction of the robust almost Nikodym set.

  • Randomly deleting k quadratic varieties and adding a random set W constructs the robust almost Nikodym set N′′.Here k is chosen proportional to ((1−ε)(d−2)/log 2) log q, while W independently retains each point with probability ε.Source: §3.3 · p. 9
  • The construction has the required size with probability 1−o(1), because almost all quadratic polynomials are absolutely irreducible and the deleted varieties have controlled overlaps.The irreducibility failure rate is O(1/q^(d(d−1)/2)), and pairwise intersections are controlled when the defining quadratics are not scalar multiples.Source: §3.3 · p. 10, §3.4 · p. 10

3.4. Step 3a: Lower bounding the size of the construction.

  • The size lower bound follows from Lang–Weil estimates, Bonferroni inequalities, and a union bound over pairs of randomly chosen quadratic varieties.The pairwise estimate holds with probability 1−O(1/q) for each pair, yielding simultaneous control with probability 1−o(1).Source: §3.4 · p. 10

3.5. Step 4: Initial reductions for verifying the robust almost Nikodym property.

  • Conditioned on avoiding the deleted varieties, many directions remain available; when one quadratic vanishes at the origin, W independently repairs enough problematic directions.The argument obtains at least q^(1+2ε^2) directions before repair and at least q^(1+ε^2) successful directions afterward with high probability.Source: §3.5 · pp. 10–11

3.6. Step 5: the second moment method.

  • The second-moment step treats non-residue events for distinct directions as pairwise independent, while noting that higher-moment independence eventually breaks down.This limitation leaves open whether larger k could recover the conjectured bound.Source: §3.6 · p. 13

4. A TWO-DIMENSIONAL CONSTRUCTION

The two-dimensional construction starts from the complement of parallel parabolas and uses a probabilistic enlargement to obtain a Nikodym set with the known near-optimal cardinality.

4. A TWO-DIMENSIONAL CONSTRUCTION

  • Replacing the earlier Weil-bound analysis with a random construction improves the error term from O(q^(5/4) log q) to O(q log q).The construction is a special case of an existing unital-based probabilistic construction.Source: §4 · p. 13
  • The construction relies on a finite-field trace calculation in which Re(t^2) takes zero once and every other value √q+1 times.The calculation uses that −1 is a quadratic residue in the subfield F_√q under the stated assumption on q.Source: §4 · p. 13
  • The preliminary set N0 removes √q parallel parabolas and has cardinality q^2−q^(3/2).It is nearly Nikodym: points outside N0 have one suitable punctured line, while points inside N0 have √q+1 such lines.Source: §4 · p. 14
  • The probabilistic enlargement adds each point outside N0 independently with probability C log q/√q, producing a Nikodym set of size q^2−q^(3/2)+O(q log q).For C>2, a union-bound argument gives positive probability that every point has a required punctured line.Source: §4 · p. 14
  • The authors identify this construction as a special case of the probabilistic construction for arbitrary unitals in [5, §4.1].The relevant unital is the complement of N0, together with a point at infinity.Source: §4 · pp. 14–15

APPENDIX A. A PROJECTIVE TRANSFORMATION ARGUMENT

The appendix uses projective transformations and pigeonhole arguments to convert a suitable affine configuration into a Kakeya set, thereby obtaining the corresponding Nikodym bound.

APPENDIX A. A PROJECTIVE TRANSFORMATION ARGUMENT

  • A plane and then one of its translates are selected so that relatively few relevant lines are parallel to them.The choices use the probabilistic method or pigeonhole principle.Source: Appendix A · p. 15
  • A linear transformation sends the selected translate to the hyperplane F_q^(d−1), preserving the Nikodym property.This normalization makes the remaining direction analysis explicit.Source: Appendix A · p. 15
  • The construction handles horizontal directions directly and represents nonhorizontal directions as [x,1], assigning suitable base points for the required lines.The final cases use the origin, points in E, or points (v_x,0), depending on the direction.Source: Appendix A · pp. 15–16
Loading 2511.07721v2…