New Nikodym set constructions over finite fields

What's new 2025-11-12

I have uploaded to the arXiv my paper “New Nikodym set constructions over finite fields“. This is a spinoff of my previous project with Bogdan Georgiev, Javier Gómez–Serrano, and Adam Zsolt Wagner that I recently posted about. In that project we experimented with using AlphaEvolve (and other tools, such as DeepThink and AlphaProof) to explore various mathematical problems which were connected somehow to an optimization problem. For one of these — the finite field Nikodym set problem — these experiments led (by a somewhat convoluted process) to an improved asymptotic construction of such sets, the details of which are written up (by myself rather than by AI tools) in this paper.

Let ${{\mathbb F}_q}$ be a finite field of some order ${q}$ (which must be a prime or a power of a prime), and let ${d}$ be a fixed dimension. A Nikodym set in ${{\mathbb F}_q^d}$ is a subset ${N}$ of ${{\mathbb F}_q^d}$ with the property that for every point ${x \in {\mathbb F}_q^d}$ , there exists a line ${\ell}$ passing through ${x}$ such that all points of ${\ell}$ other than ${x}$ lie in ${N}$ . Such sets are close cousins of Kakeya sets (which contain a line in every direction); indeed, roughly speaking, applying a random projective transformation to a Nikodym set will yield (most of) a Kakeya set. As a consequence, any lower bound on Kakeya sets implies a similar bound on Nikodym sets; in particular, one has a lower bound

$\displaystyle |N| \geq \frac{q^d}{2^{d-1}} + O(q^{d-1})$

on the size of a Nikodym set ${N}$ , coming from a similar bound on Kakeya sets due to Bukh and Chao using the polynomial method.

For Kakeya sets, Bukh and Chao showed this bound to be sharp up to the lower order error ${O(q^{d-1})}$ ; but for Nikodym sets it is conjectured that in fact such sets should asymptotically have full density, in the sense that

$\displaystyle |N| \geq q^d - o(q^d).$

This is known in two dimensions thanks to work by Szönyi et al. on blocking sets, and was also established in bounded torsion cases (and in particular for even ${q}$ ) by Guo, Kopparty, and Sudan by combining the polynomial method with the theory of linear codes. But in other cases this conjecture remains open in three and higher dimensions.

In our experiments we focused on the opposite problem of constructing Nikodym sets of size as small as possible. In the plane ${d=2}$ , constructions of size

$\displaystyle |N| = q^2 - q^{3/2} + O(q \log q) \ \ \ \ \ (1)$

when ${q}$ is a perfect square were constructed by Blokhuis et al, again using the theory of blocking sets; by taking Cartesian products of such sets, one can also make similar constructions in higher dimensions, again assuming ${q}$ is a perfect square. Apart from this, though, there are few such constructions in the literature.

We set AlphaEvolve to try to optimize the three dimensional problem with a variable field size ${q}$ (which we took to be prime for simplicity), with the intent to get this tool to come up with a construction that worked asymptotically for large ${q}$ , rather than just for any fixed value of ${q}$ . After some rounds of evolution, it arrived at a construction which empirically had size about ${q^3 - 8q^2}$ . Inspecting the code, it turned out that AlphaEvolve had constructed a Nikodym set ${N}$ by (mostly) removing eight low-degree algebraic surfaces (all of the form ${\{ (x,y,x^i y)\}}$ for various ${i}$ ). We used the tool DeepThink to confirm the Nikodym property and to verify the construction, and then asked it to generalize the method. By removing many more than eight surfaces, and using some heuristic arguments based on the Chebotarev density theorem, DeepThink claimed a construction of size

$\displaystyle |N| = q^3 - 2 q^2 \log q + o(q^2 \log q) \ \ \ \ \ (2)$

formed by removing several higher degree surfaces, but it acknowledged that the arguments were non-rigorous.

The arguments can be sketched here as follows. Let ${V}$ be a random surface of degree ${D}$ , and let ${x}$ be a point in ${{\mathbb F}_q^3}$ which does not lie in ${V}$ . A random line through ${x}$ then meets ${V}$ in a number of points, which is basically the set of zeroes in ${{\mathbb F}_q}$ of a random polynomial of degree ${D}$ . The (function field analogue of the) Chebotarev density theorem predicts that the probability that this polynomial has no roots in ${{\mathbb F}_q}$ is about ${\delta_D}$ , where

$\displaystyle \delta_D = 1 - \frac{1}{1!} + \frac{1}{2!} - \dots + \frac{(-1)^D}{D!}$

is the proportion of permutations on ${D}$ elements that are derangements (no fixed points). So, if one removes ${k}$ random surfaces of degrees ${D_1,\dots,D_k}$ , the probability that a random line avoids all of these surfaces is about ${\delta_{D_1} \dots \delta_{D_k}}$ . If this product is significantly greater than ${1/q^2}$ , then the law of large numbers (and concentration of measure) then predicts (with high probability) that out of the ${\sim q^2}$ lines through ${x}$ , at least one will avoid the removed surfaces, thus giving (most of) a Nikodym set. The Lang-Weil estimate predicts that each surface has cardinality about ${q^2}$ , so this should give a Nikodym set of size about ${q^3 - kq^2}$ .

DeepThink took the degrees ${D_1,\dots,D_k}$ to be large, so that the derangement probabilities ${\delta_{D_i}}$ were close to ${1/e}$ . This led it to predict that ${k}$ could be taken to be as large as ${2 \log q}$ , leading to the claimed bound (2). However, on inspecting this argument we realized that these moderately high degree surfaces were effectively acting as random sets, so one could dramatically simplify DeepThink’s argument by simply taking ${N}$ to be a completely random set of the desired cardinality (2), in which case the verification of the Nikodym set property (with positive probability) could be established by a standard Chernoff bound-type argument (actually, I ended up using Bennett’s inequality rather than Chernoff’s inequality, but this is a minor technical detail).

On the other hand, the derangement probabilities ${\delta_D}$ oscillate around ${1/e}$ , and in fact are as large as ${1/2}$ when ${D=2}$ . This suggested that one could do better than the purely random construction if one only removed quadratic surfaces instead of higher degree surfaces, and heuristically predicted the improvement

$\displaystyle |N| = q^3 - \frac{2}{\log 2} q^2 \log q + o(q^2 \log q). \ \ \ \ \ (3)$

However, our experiments with both AlphaEvolve and DeepThink to try to make this idea work either empirically, heuristically, or rigorously were all unsuccessful! Eventually Deepthink discovered the problem: random quadratic polynomials often had two or zero roots (depending on whether the discriminant was a non-zero quadratic residue, or a nonresidue), but would only very rarely have just one root (the discriminant would have to vanish). As a consequence, if ${x}$ happened to lie on one of the removed quadratic surfaces ${V}$ , it was extremely likely that most lines through ${x}$ would intersect ${V}$ in a further point; only the small minority of lines that were tangent to ${V}$ and ${x}$ would avoid this. None of the AI tools we tried were able to overcome this obstacle.

However, I realized that one could repair the construction by adding back a small random portion of the removed quadratic surfaces, to allow for a non-zero number of lines through ${x}$ to stay inside the putative Nikodym set even when ${x}$ was in one of the surfaces ${V}$ , and the line was not tangent to ${V}$ . Pursuing this idea, and performing various standard probabilistic calculations and projective changes of variable, the problem essentially reduced to the following: given ${k}$ random quadratic polynomials in the plane ${{\mathbb F}_q^2}$ , is it true that these polynomials simultaneously take quadratic residue values for ${\gg 2^{-k}}$ of the points in that plane? Heuristically this should be true even for ${2^{-k}}$ close to ${1/q^2}$ . However, it proved difficult to accurately control this simultaneous quadratic residue event; standard algebraic geometry tools such as the Weil conjectures seemed to require some vanishing of étale cohomology groups in order to obtain adequate error terms, and this was not something I was eager to try to work out. However, by exploiting projective symmetry (and the ${2}$ -transitive nature of the projective linear group), I could get satisfactory control of such intersections as long as ${2^{-k}}$ was a little bit larger than ${1/q}$ rather than ${1/q^2}$ . This gave an intermediate construction of size

$\displaystyle |N| = q^3 - (\frac{1}{\log 2} + 1) q^2 \log q + o(q^2 \log q),$

which still beat the purely random construction, but fell short of heuristic predictions. This argument (generalized to higher dimensions) is what is contained in the paper. I pose the question of locating a construction with the improved bound (3) (perhaps by some modification of the strategy of removing quadratic varieties) as an open question.

We also looked at the two-dimensional case to see how well AlphaEvolve could recover known results, in the case that ${q}$ was a perfect square. It was able to come up with a construction that was slightly worse than the best known construction, in which one removed a large number of parabolas from the plane; after manually optimizing the construction we were able to recover the known bound (1). This final construction is somewhat similar to existing constructions (it has a strong resemblance to a standard construction formed by taking the complement of a Hermitian unital), but is still technically a new construction, so we have also added it to this paper.