Cap sets in F_3^n

# Cap sets in F_3^n ## Goal A *cap set* is a subset of `F_3^n` (vectors of length `n` over `{0, 1, 2}`, addition mod 3) that contains no three distinct points on a line. Lines in `F_3^n` have exactly three points and `{x, y, z}` is a line iff `x + y + z = 0`, so the condition is: for every two distinct points `x, y` of the set, `-(x + y)` (coordinatewise `(-(x_i + y_i)) mod 3`) is not in the set. Equivalently, no three-term arithmetic progression. The card game SET is the case `n = 4`. Build the largest cap set you can for `n = 6, 7, 8, 9`. `capset.py` exposes cap(n: int, time_budget: float, seed: int) -> list returning the points of the set, each either a tuple/list of `n` digits in `{0, 1, 2}` or an integer `v` in `[0, 3^n)` read in base 3 (coordinate `i` is `(v // 3**i) % 3`). Mixing the two forms is fine. The eval refuses to verify more than `record + 50` points. ## Metric metric = mean over n in {6, 7, 8, 9} of size(n) / record(n) Verification is exact and trusts nothing the solver reports: points are normalised, duplicates are rejected, and for every unordered pair the third point of the line is looked up in the set (bitmask encoding, `O(size^2)` with a hash lookup: under a second for 1082 points). A set with three collinear points on any `n` fails the whole run (`wrong_answer`). Any `n` whose size exceeds the record is listed under `records_beaten`. `ZT_EVAL_SEED` only changes the `seed` handed to `cap`; the instance set is fixed. ## Records | n | best known | proven optimal | source | |---|---|---|---| | 6 | 112 | yes | Potechin, "Maximal caps in AG(6,3)", Des. Codes Cryptogr. 46 (2008): the doubled Hill cap is the unique maximum. Calibration instance. | | 7 | 236 | no (no 289-cap exists: arXiv:2206.09804) | Calderbank & Fishburn, "Maximal three-independent subsets of {0,1,2}^n", Des. Codes Cryptogr. 4 (1994); still the best known per Bierbrauer & Edel, "Large caps in projective Galois spaces" (2012) and Romera-Paredes et al., Nature 625 (2024), Fig. 4a | | 8 | 512 | no | FunSearch: Romera-Paredes et al., "Mathematical discoveries from program search with large language models", Nature 625 (2024) 468-475, Fig. 4 and SI Appendix E.2 (explicit construction); previous best 496 (Edel 2004) | | 9 | 1082 | no | Edel's generalized product construction, "Extensions of generalized product caps", Des. Codes Cryptogr. 31 (2004); FunSearch's SI Fig. C.5 gives a priority function reproducing 1082 and its notebook calls it the largest known | Why no `n = 10`: the number 2474 is widely quoted for it, but on 2026-09-07 no primary source stating it could be reached (Edel's site no longer hosts the affine table; the TU Delft thesis on upper bounds lists only the product bound 2240; FunSearch stops at `n = 9`). Rather than pin an unverifiable record, the instance is left out; add it to `RECORDS` in `eval.py` once a citation is in hand. ## Constraints - Standard library only (`math`, `random`, `itertools`, `functools`, `collections`, `heapq`, `time`). The eval rejects other imports. - Respect `time_budget` (seconds, per call). The default is 20 s per instance, about 90 s for a full eval including verification. - Deterministic given `seed`: use `random.Random(seed)`. ## Iterating quickly - `ZT_EVAL_INSTANCES` is a comma-separated subset of `6,7,8,9`; the full set is the default. - `ZT_EVAL_PER_INSTANCE_SECONDS` is the budget handed to `cap` per instance (default 20). ``` ZT_EVAL_INSTANCES=6,7 ZT_EVAL_PER_INSTANCE_SECONDS=5 python eval.py ``` ## Ideas that are known to matter (check the journal before repeating one) - **Products.** If `A` is a cap in `F_3^a` and `B` a cap in `F_3^b`, then `A x B` (concatenate coordinates) is a cap in `F_3^(a+b)`. With the exact small caps (2, 4, 9, 20, 45, 112 for `n = 1..6`) this gives 224 for `n = 7`, 448 for `n = 8`, 1008 for `n = 9`. The baseline only finds its factors greedily; hard-coding the Pellegrino 20-cap and the 112-cap already helps. - **Doubling.** An `m`-cap in `PG(d, 3)` gives a `2m`-cap in `AG(d+1, 3)`: the 56-point Hill cap in `PG(5, 3)` is how the 112-cap in dimension 6 arises. Ovoids (`q^2 + 1` points in `PG(3, q)`) are the other classical ingredient. - **The 512-cap has structure.** FunSearch's explicit construction (Nature 2024, Fig. 4c and SI E.2) is a union of four 128-point pieces: all vectors with no zero entries satisfying a reflection condition (entry `i` versus entry `-i`), plus vectors of half support on chosen support patterns. Priority functions that score a vector by counts of zeros, by `(v[i], v[-i])` reflections and by support patterns, then greedily add in priority order, are what found it; that search space is small and cheap to evaluate. - **Edel's generalized product / admissible sets** underlie 1082 and every asymptotic record (Tyrrell 2023, FunSearch, X-evolve). Symmetric "admissible sets" combined with the 112-cap give caps in dimensions that are multiples of 6 plus small offsets. - **Local search.** Keep the set of forbidden points (`-(x+y)` over pairs) incrementally; remove a few points, re-add greedily by a priority, keep if not smaller (tabu on recently removed points). Extending a cap by one point is possible iff the point is outside the forbidden set, so "complete" caps are easy to detect and swaps are cheap. - Beating 236, 512 or 1082 would be a new record in a well-studied table; expect the last few points to be hard and treat any `ratio > 1` as a bug until the hub's exact re-verification agrees. Write one honest line in `NOTES.md`: the idea, and which `n` 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.