Smallest Nikodym sets in F_p^3

# Smallest Nikodym sets in F_p^3 ## Goal A Nikodym set in F_p^3 is a set N such that every point x of F_p^3 lies on some line l with the punctured line l \ {x} contained in N (x itself need not be in N). Find one that is as small as possible; equivalently, remove as many points from F_p^3 as you can while keeping the property. `nikodym.py` exposes nikodym_set(p: int, time_budget: float, seed: int) -> list[tuple[int, int, int]] Return the points of N as integer triples; coordinates are reduced mod p and duplicates are counted once. The eval checks the punctured-line condition exactly for all p^3 points and then counts the distinct points. Any uncovered point is a failed run. This is problem 1 of the AlphaEvolve repository of problems ("Kakeya and Nikodym sets in finite fields", flagged there as a world record), notebook `finite_field_nikodym.ipynb`, 3D section. The work led to T. Tao, "New Nikodym set constructions over finite fields" (arXiv:2511.07721), which gives Nikodym sets in F_q^3 of size q^3 - (1/log 2 + 1 + o(1)) q^2 log q asymptotically; no explicit sizes for specific p are published there, so the records below are the explicit AlphaEvolve sets. ## Metric metric = mean over p in INSTANCES of record(p) / |N_p| 1.0 means matching every record; above 1.0 means at least one record was beaten (listed in `records_beaten`). The size that is scored is the one the eval counts, never a number you report. ## Records The record construction removes from F_p^3 the union of the surfaces `{(t, t^k, t^(k+s)) : t in F_p^*, k}` for shifts s in {+-1, +-2, +-3, +-4}, plus the diagonal (t, t, t) and the three plane diagonals (t, t, 0), (t, 0, t), (0, t, t), t != 0. The notebook's Deep Think note `nikodym.tex` estimates its size as p^3 - 8p^2 + O(p). The notebook lists sizes for p >= 47; the final program was re-run here for every prime and produced exactly those numbers, and is also a valid Nikodym set for p = 31, 37, 41, 43 (it is not for p <= 29, which is why those primes are absent). None of these is proven optimal. Tao's construction removes (1/log 2 + 1 + o(1)) p^2 log p, about 2.44 p^2 log p, points asymptotically, which nominally exceeds 8p^2 for every p here; the o(1) term is not quantified, so whether an explicit version beats these sets at these p is open, and there is real room. | p | record | source | |---|---|---| | 31 | 26312 | AlphaEvolve final program re-run and verified here | | 37 | 45264 | re-run, verified | | 41 | 61704 | re-run, verified | | 43 | 72288 | re-run, verified | | 47 | 91492 | listed in the notebook; re-run reproduces it | | 53 | 134908 | listed; reproduced | | 59 | 185656 | listed; reproduced | | 61 | 214008 | listed; reproduced | | 67 | 281940 | listed; reproduced | | 71 | 336144 | listed; reproduced | | 73 | 367900 | listed; reproduced | | 79 | 466440 | listed; reproduced | | 83 | 532096 | listed; reproduced | | 89 | 666520 | listed; reproduced | ## Constraints - Standard library only. No numpy. The eval rejects other imports. - Respect `time_budget` (seconds, per prime). Verification (up to about 3 s at p = 89) is not charged to you. - Deterministic given `seed`: use `random.Random(seed)` if you randomise anything. - Return at most 2 p^3 entries. ## Iterating - `ZT_EVAL_INSTANCES=31,47` runs only those primes (the default set is all 14 primes above). - `ZT_EVAL_PER_INSTANCE_SECONDS=1` shortens the per-prime budget (default 5 s; the full eval takes about 100 s with the default set). - `ZT_EVAL_SEED` only changes the `seed` handed to your solver. ## Ideas that are known to matter (check the journal before repeating one) - Think in terms of the complement C = F_p^3 \ N. A point x is fine iff some line through x meets C in no point other than x. So C must be "line-avoidable" from everywhere; unions of low-degree curves and surfaces inside (F_p^*)^3 are, because a line meets such a surface in boundedly many points and there are p^2 + p + 1 directions to choose from. - The baseline removes the three coordinate planes minus the axes (|N| = (p-1)^3 + 3p - 2) and scores 0.94-0.99. The record removes about 8p^2 points; Tao's construction shows about 2.44 p^2 log p is possible asymptotically, and random greedy removal (add points to C while the property survives) is a cheap way to look for it at these sizes. - More surfaces: shifts s beyond +-4 make the construction invalid for small p because too many points fail; check which shift sets survive for each p, and try surfaces z = y * x^s with other exponent patterns, or monomial surfaces in other coordinate pairs. - Verification is exact and fast; a local search that removes a point and checks is feasible for p <= 43 and gives a target for a closed form. Write one honest line in `NOTES.md`: the idea, and which p it helped. Simpler is better: all else equal prefer the shorter solver, and treat removing code for an equal score as a win. Log every experiment, including discards, in your results.tsv.