Smallest Kakeya sets in F_p^3

# Smallest Kakeya sets in F_p^3 ## Goal A Kakeya set in F_p^3 is a set K that contains a full line `{x + t v : t in F_p}` for every non-zero direction v (there are p^2 + p + 1 directions up to scaling). Find one that is as small as possible. `kakeya.py` exposes kakeya_set(p: int, d: int, time_budget: float, seed: int) -> list[tuple[int, int, int]] `d` is always 3 in this pack (the argument is there so one solver can serve the F_p^4 and F_p^5 packs too). Return the points of K as integer triples; coordinates are reduced mod p and duplicates are counted once. The eval checks exactly, direction by direction, that K contains a line in every direction, then counts the distinct points. Any missing direction 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_kakeya.ipynb`, 3D section. ## Metric metric = mean over p in INSTANCES of record(p) / |K_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 Best-known sizes. All are AlphaEvolve constructions from the notebook (the smallest `best_score_p<p>_d3` across its three experiments). None is proven optimal: the best lower bound known to us is of the order p^3/4 (Bukh and Chao, 2021), and all these sets are p^3/4 + 7p^2/8 + O(p). | p | record | what it is | |---|---|---| | 5 | 53 | (2p^3+7p^2-1)/8; formula proved in the notebook's Deep Think note `kakeya2.tex`; construction reproduced and verified here | | 7 | 128 | AlphaEvolve search result; reproduced here by exhaustive search over the 4 offsets of the experiment-3 construction | | 11 | 438 | as p = 7 (reproduced) | | 13 | 697 | (2p^3+7p^2-1)/8, reproduced | | 19 | 2031 | AlphaEvolve search result, not reproduced | | 23 | 3505 | AlphaEvolve search result, not reproduced | | 29 | 6833 | (2p^3+7p^2-1)/8, reproduced | | 31 | 8290 | AlphaEvolve search result, not reproduced | | 37 | 13861 | (2p^3+7p^2-1)/8, reproduced | | 41 | 18701 | (2p^3+7p^2-1)/8, reproduced | | 43 | 21495 | AlphaEvolve search result (experiment 2), not reproduced | | 47 | 27892 | AlphaEvolve search result, not reproduced | | 53 | 39677 | (2p^3+7p^2-1)/8, reproduced | | 59 | 54396 | AlphaEvolve search result, not reproduced | | 61 | 60001 | (2p^3+7p^2-1)/8, reproduced | | 67 | 79126 | AlphaEvolve search result, not reproduced | | 71 | 93895 | AlphaEvolve search result, not reproduced | For p = 1 (mod 4) the record is exactly (2p^3 + 7p^2 - 1)/8 and comes from an explicit construction (below). For p = 3 (mod 4) the records are the outputs of AlphaEvolve's parameter searches, sit within a few units of (2p^3 + 7p^2 - 1)/8, and look the most beatable: nobody has proved a formula for that case. The record construction for p = 1 (mod 4), with S the squares in F_p including 0 and g = (p-1)/4: K_A = { (x, (q1+q2)/2 - x^2 - g, (q1-q2)/2) : x in F_p, q1, q2 in S } K_0B = { (0, y, z) : y + z^2 in S } K_0C = { (0, y, 0) : y in F_p } K_A handles every direction with a non-zero first coordinate (each slice x = t is an affine image of S x S), and the plane x = 0 carries a 2D Kakeya set for the rest. The whole art is in making the three pieces overlap as much as possible. ## Constraints - Standard library only. No numpy. The eval rejects other imports. - Respect `time_budget` (seconds, per prime). The verification time 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=7,23` runs only those primes (the default set is all 17 primes above). - `ZT_EVAL_PER_INSTANCE_SECONDS=1` shortens the per-prime budget (default 4 s; the full eval takes about 80 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) - The baseline is the textbook quadratic construction and already scores about 0.99. Everything left is in the p^2 and p terms: how the "x != 0" part and the x = 0 plane overlap, and how the 2D Kakeya set inside the plane x = 0 is chosen. - Parametrise: affine offsets in each piece (the gammas of the notebook's experiment 3), shears and rotations of the (y, z) coordinates, and which quadratic character sets are used. Compute the size of the union analytically (inclusion-exclusion) so you can search thousands of parameter choices per prime, then build the best one. - For p = 3 (mod 4), -1 is a non-square, which changes the intersection counts; a construction tuned to that case may beat the search results. - Local search: start from a valid set, try removing a point, and repair by re-adding the cheapest points that restore the missing directions. Small p first; the eval is exact and fast. - Sanity-check any claimed improvement on several p before spending the whole budget on it. 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.