Smallest Kakeya sets in F_p^4

# Smallest Kakeya sets in F_p^4 ## Goal A Kakeya set in F_p^4 is a set K that contains a full line `{x + t v : t in F_p}` for every non-zero direction v (p^3 + 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, int]] `d` is always 4 in this pack (the argument lets one solver serve the F_p^3 and F_p^5 packs too). Return the points of K as integer 4-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`, 4D 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 smallest `best_score_p<p>_d4` across the notebook's three 4D experiments. None is proven optimal (the best lower bound known to us is of the order p^4/8, Bukh and Chao 2021). The values are about p^4/8 + 0.6 p^3. The notebook's final experiment-3 program (a union of lines, one per direction, through the start (v_1^2, 2 v_2^2, 3 v_3^2, 4 v_4^2)) was re-run here and its sizes verified; experiment 1 reported slightly smaller sets for 11 <= p <= 37 that were not reproduced. | p | record | source | |---|---|---| | 5 | 162 | all three experiments; reproduced and verified here | | 7 | 527 | all three experiments; reproduced | | 11 | 2687 | experiment 1 (experiments 2 and 3: 2688, reproduced) | | 13 | 4966 | experiments 1 and 2 (experiment 3: 4973, reproduced) | | 17 | 13514 | experiments 1 and 2 (experiment 3: 13538, reproduced) | | 19 | 20583 | experiment 1 (experiment 3: 20589, reproduced) | | 23 | 42534 | experiment 1 (experiment 3: 42542, reproduced) | | 29 | 103387 | experiment 1 (experiment 3: 103426, reproduced) | | 31 | 133746 | experiments 1 and 2 (experiment 3: 133755, reproduced) | | 37 | 265175 | experiment 1 (experiment 3: 265199, reproduced) | | 41 | 395292 | experiment 3; reproduced and verified here | ## Constraints - Standard library only. No numpy. The eval rejects other imports. - Respect `time_budget` (seconds, per prime). Verification (up to about 5 s at p = 41) is not charged to you. - Deterministic given `seed`: use `random.Random(seed)` if you randomise anything. - Return at most 2 p^4 entries. ## Iterating - `ZT_EVAL_INSTANCES=7,19` runs only those primes (the default set is all 11 primes above). - `ZT_EVAL_PER_INSTANCE_SECONDS=1` shortens the per-prime budget (default 5 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, K_4 = {(t, t m_i - m_i^2)} union {0} x K_3, and scores 0.94 at p = 5 and 0.999 at p = 41. The records differ from it only in the p^3 and lower terms; that is where the work is. - Union-of-lines: pick, for every direction v, one start point s(v) and take the union of the lines. Quadratic start rules with different coefficients per coordinate (the notebook's (k+1) v_k^2) make the lines share points; search over the coefficient pattern. - Recursive constructions with a different quadratic per level (t m - m^2, t m + m^2, shifted variants) and a chosen slice for the lifted lower-dimensional set: enumerate combinations, keep the smallest union. Compute sizes of unions analytically where you can. - Small p first (verification is instant there), then check that an improvement persists for the larger primes before spending the budget on them. 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.