Smallest Kakeya sets in F_p^5

# Smallest Kakeya sets in F_p^5 ## Goal A Kakeya set in F_p^5 is a set K that contains a full line `{x + t v : t in F_p}` for every non-zero direction v ((p^5 - 1)/(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, int, int]] `d` is always 5 in this pack (the argument lets one solver serve the F_p^3 and F_p^4 packs too). Return the points of K as integer 5-tuples; 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`, 5D 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: the `best_score_p<p>_d5` values listed in the notebook's 5D experiments (both experiments agree). Every one was reproduced here by re-running the experiment-2 construction and verified by this eval. None is proven optimal (the best lower bound known to us is of the order p^5/16, Bukh and Chao 2021); the values are about p^5/16 + 0.4 p^4. | p | record | source | |---|---|---| | 5 | 510 | AlphaEvolve experiment 2; reproduced | | 7 | 2187 | reproduced | | 11 | 16427 | reproduced | | 13 | 35278 | reproduced | | 17 | 123029 | reproduced | | 19 | 207639 | reproduced | The record construction: for j = 5 down to 1, take all points (y_1, ..., y_{j-1}, t, 0, ..., 0) with each y_i in {t m - m^2 + m : m in F_p}. Part j covers the directions whose last non-zero coordinate is the j-th; the parts overlap in the coordinate hyperplanes. ## Constraints - Standard library only. No numpy. The eval rejects other imports. - Respect `time_budget` (seconds, per prime). Verification (about 10 s at p = 19) is not charged to you. - Deterministic given `seed`: use `random.Random(seed)` if you randomise anything. - Return at most 2 p^5 entries. ## Iterating - `ZT_EVAL_INSTANCES=5,11` runs only those primes (the default set is all 6 primes above). - `ZT_EVAL_PER_INSTANCE_SECONDS=1` shortens the per-prime budget (default 8 s; the full eval takes about 70 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 K_5 = {(t, t m_i - m_i^2)} union {0} x K_4 and scores 0.95 at p = 5, 0.995 at p = 19. The record differs from it only by the linear term "+ m" in the quadratic, which changes how the parts overlap in the coordinate hyperplanes. All the remaining room is in the p^4 and lower terms. - Try other quadratics per level (a t m + b m^2 + c m + e), different ones for different levels, and different lifting slices for the lower-dimensional part; the size of the union can be computed by inclusion-exclusion far faster than by building the set. - Use the F_p^3 and F_p^4 packs' journals: an idea that improves the p^{d-1} term there usually lifts. - p = 5 and 7 verify instantly; use them to screen ideas, then confirm on 11 and 13. 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.