{"id":"kakeya-fp5","name":"Smallest Kakeya sets in F_p^5","family":"finite-geometry","description":"Find a subset of F_p^5 containing a line in every direction, as small as possible, for 6 primes 5 <= p <= 19. Scored against the AlphaEvolve record sizes (problem 1 of the AlphaEvolve repository), about p^5/16 + 0.4 p^4.","metric":"record_ratio","direction":"maximize","tolerance":0.05,"eval_timeout_seconds":300,"agent_timeout_seconds":1800,"mutable":["kakeya.py"],"runtime":"python>=3.11, standard library only (math, random, itertools, functools, collections, heapq, time)","decomposable":true,"status":"active","captain":null,"parent_problem":null,"program_md":"# Smallest Kakeya sets in F_p^5\n\n## Goal\n\nA 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\ndirection v ((p^5 - 1)/(p - 1) directions up to scaling). Find one that is as small as possible.\n\n`kakeya.py` exposes\n\n    kakeya_set(p: int, d: int, time_budget: float, seed: int) -> list[tuple[int, int, int, int, int]]\n\n`d` is always 5 in this pack (the argument lets one solver serve the F_p^3 and F_p^4 packs too).\nReturn the points of K as integer 5-tuples; coordinates are reduced mod p and duplicates are\ncounted once. The eval checks exactly, direction by direction, that K contains a line in every\ndirection, then counts the distinct points. Any missing direction is a failed run.\n\nThis is problem 1 of the AlphaEvolve repository of problems (\"Kakeya and Nikodym sets in finite\nfields\", flagged there as a world record), notebook `finite_field_kakeya.ipynb`, 5D section.\n\n## Metric\n\n    metric = mean over p in INSTANCES of  record(p) / |K_p|\n\n1.0 means matching every record; above 1.0 means at least one record was beaten (listed in\n`records_beaten`). The size that is scored is the one the eval counts, never a number you report.\n\n## Records\n\nBest-known sizes: the `best_score_p<p>_d5` values listed in the notebook's 5D experiments (both\nexperiments agree). Every one was reproduced here by re-running the experiment-2 construction and\nverified by this eval. None is proven optimal (the best lower bound known to us is of the order\np^5/16, Bukh and Chao 2021); the values are about p^5/16 + 0.4 p^4.\n\n| p | record | source |\n|---|---|---|\n| 5 | 510 | AlphaEvolve experiment 2; reproduced |\n| 7 | 2187 | reproduced |\n| 11 | 16427 | reproduced |\n| 13 | 35278 | reproduced |\n| 17 | 123029 | reproduced |\n| 19 | 207639 | reproduced |\n\nThe record construction: for j = 5 down to 1, take all points (y_1, ..., y_{j-1}, t, 0, ..., 0)\nwith each y_i in {t m - m^2 + m : m in F_p}. Part j covers the directions whose last non-zero\ncoordinate is the j-th; the parts overlap in the coordinate hyperplanes.\n\n## Constraints\n\n- Standard library only. No numpy. The eval rejects other imports.\n- Respect `time_budget` (seconds, per prime). Verification (about 10 s at p = 19) is not charged\n  to you.\n- Deterministic given `seed`: use `random.Random(seed)` if you randomise anything.\n- Return at most 2 p^5 entries.\n\n## Iterating\n\n- `ZT_EVAL_INSTANCES=5,11` runs only those primes (the default set is all 6 primes above).\n- `ZT_EVAL_PER_INSTANCE_SECONDS=1` shortens the per-prime budget (default 8 s; the full eval takes\n  about 70 s with the default set).\n- `ZT_EVAL_SEED` only changes the `seed` handed to your solver.\n\n## Ideas that are known to matter (check the journal before repeating one)\n\n- The baseline is the textbook quadratic construction K_5 = {(t, t m_i - m_i^2)} union {0} x K_4\n  and scores 0.95 at p = 5, 0.995 at p = 19. The record differs from it only by the linear term\n  \"+ m\" in the quadratic, which changes how the parts overlap in the coordinate hyperplanes. All\n  the remaining room is in the p^4 and lower terms.\n- Try other quadratics per level (a t m + b m^2 + c m + e), different ones for different levels,\n  and different lifting slices for the lower-dimensional part; the size of the union can be\n  computed by inclusion-exclusion far faster than by building the set.\n- Use the F_p^3 and F_p^4 packs' journals: an idea that improves the p^{d-1} term there usually\n  lifts.\n- p = 5 and 7 verify instantly; use them to screen ideas, then confirm on 11 and 13.\n\nWrite one honest line in `NOTES.md`: the idea, and which p it helped.\n\nSimpler is better: all else equal prefer the shorter solver, and treat removing code for an equal\nscore as a win. Log every experiment, including discards, in your results.tsv.\n","eval_py":"\"\"\"Eval for kakeya-fp5: Kakeya sets in F_p^5. Prints one JSON line: {\"metric\": record_ratio, ...}.\n\nEnv:\n  ZT_EVAL_SEED                    seed handed to kakeya_set()\n  ZT_EVAL_PER_INSTANCE_SECONDS    time budget per prime p (default 8)\n  ZT_EVAL_INSTANCES               comma-separated primes p to run (default \"5,7,11,13,17,19\")\n\nThe metric is the mean over p of record(p) / |K_p|, where |K_p| is the number of distinct points\nin the set the solver returns, counted here after an exact check that it contains a line in every\ndirection. The solver's own opinion of its size is never used.\n\"\"\"\n\nfrom __future__ import annotations\n\nimport ast\nimport itertools\nimport json\nimport os\nimport random\nimport sys\nimport time\nfrom pathlib import Path\n\nSEED = os.environ.get(\"ZT_EVAL_SEED\", \"dev-seed\")\nBUDGET = float(os.environ.get(\"ZT_EVAL_PER_INSTANCE_SECONDS\", \"8\"))\nINSTANCES = [int(x) for x in os.environ.get(\"ZT_EVAL_INSTANCES\", \"5,7,11,13,17,19\").split(\",\")]\nSTDLIB_ALLOW = {\"math\", \"random\", \"itertools\", \"functools\", \"collections\", \"heapq\", \"time\", \"sys\", \"typing\", \"operator\"}\nFORBIDDEN_NAMES = {\"__import__\", \"importlib\", \"builtins\", \"__builtins__\", \"open\", \"exec\", \"eval\", \"compile\",\n                   \"globals\", \"__loader__\", \"__spec__\", \"breakpoint\", \"input\", \"memoryview\", \"vars\"}\n\nD = 5\n\n# Best-known sizes of Kakeya sets in F_p^5. Source: the AlphaEvolve repository of problems,\n# problem 1 (\"Kakeya and Nikodym sets in finite fields\"), experiments/finite_field_kakeya_problem/\n# finite_field_kakeya.ipynb, 5D section: the smallest \"best_score_p<p>_d5\" listed across the\n# experiments' PREVIOUS CONSTRUCTIONS blocks. See program.md for which values were reproduced here.\n# Update when a hub-verified submission beats one.\nRECORDS = {5: 510, 7: 2187, 11: 16427, 13: 35278, 17: 123029, 19: 207639}\n\n\ndef fail(msg: str, kind: str = \"error\") -> None:\n    print(json.dumps({\"metric\": 0.0, \"error\": msg, \"kind\": kind}))\n    sys.exit(1)\n\n\ndef check_imports(path: Path) -> None:\n    try:\n        tree = ast.parse(path.read_text(encoding=\"utf-8\"))\n    except SyntaxError as e:\n        fail(f\"syntax error in kakeya.py: {e}\", \"compile_error\")\n    for node in ast.walk(tree):\n        names = []\n        if isinstance(node, ast.Import):\n            names = [a.name.split(\".\")[0] for a in node.names]\n        elif isinstance(node, ast.ImportFrom) and node.module:\n            names = [node.module.split(\".\")[0]]\n        for nm in names:\n            if nm not in STDLIB_ALLOW:\n                fail(f\"import of '{nm}' is not allowed (stdlib subset only: {sorted(STDLIB_ALLOW)})\", \"compile_error\")\n        # dynamic imports and raw file/process access are not part of the problem either\n        ident = node.id if isinstance(node, ast.Name) else node.attr if isinstance(node, ast.Attribute) else None\n        if ident in FORBIDDEN_NAMES:\n            fail(f\"use of '{ident}' is not allowed in a solver\", \"compile_error\")\n        if isinstance(node, ast.ImportFrom) and node.level:\n            fail(\"relative imports are not allowed in a solver\", \"compile_error\")\n\n\n# ---------------------------------------------------------------------------- exact Kakeya check\n#\n# Points of F_p^d are stored as bitmasks over the (d-1)-dimensional slices x_j = t. For a direction\n# whose first non-zero coordinate is j, a line through the start s in slice 0 lies in K iff s lies in\n# every slice t shifted back by -t*a. Intersecting the first K shifted slices leaves a handful of\n# candidate starts, which are then checked point by point. Everything is exact; nothing is sampled.\n\n\nclass _Torus:\n    \"\"\"Bitmasks over F_p^n, row-major, coordinate 0 slowest, with cyclic coordinate shifts.\"\"\"\n\n    def __init__(self, p: int, n: int):\n        self.p, self.n = p, n\n        self.P = p ** n\n        self.B = [p ** (n - 1 - i) for i in range(n)]\n        self.FULL = (1 << self.P) - 1\n        self.hi = [None] * n\n        self.lo = [None] * n\n        for i in range(1, n):\n            blk = self.B[i]\n            rep = self.FULL // ((1 << (p * blk)) - 1)\n            hi_i, lo_i = [0] * p, [0] * p\n            for delta in range(1, p):\n                hi_i[delta] = (((1 << ((p - delta) * blk)) - 1) << (delta * blk)) * rep\n                lo_i[delta] = ((1 << (delta * blk)) - 1) * rep\n            self.hi[i], self.lo[i] = hi_i, lo_i\n\n    def shift(self, m: int, i: int, delta: int) -> int:\n        \"\"\"new[y + delta e_i] = old[y] (cyclic in coordinate i).\"\"\"\n        if delta == 0 or m == 0:\n            return m\n        blk = self.B[i]\n        if i == 0:\n            k = delta * blk\n            return ((m << k) | (m >> (self.P - k))) & self.FULL\n        return ((m << (delta * blk)) & self.hi[i][delta]) | ((m >> ((self.p - delta) * blk)) & self.lo[i][delta])\n\n    def decode(self, idx: int) -> list[int]:\n        out = []\n        for blk in self.B:\n            q, idx = divmod(idx, blk)\n            out.append(q)\n        return out\n\n\ndef missing_direction(pts: list, p: int, d: int):\n    \"\"\"Return None if pts (distinct d-tuples over F_p) is a Kakeya set, else a direction with no line.\"\"\"\n    total = p ** d\n    rho = len(pts) / total\n    n = d - 1\n    torus = _Torus(p, n)\n    P, FULL = torus.P, torus.FULL\n    wcan = [p ** (d - 1 - k) for k in range(d)]\n    flat = bytearray(total)\n    for x in pts:\n        e = 0\n        for c, w in zip(x, wcan):\n            e += c * w\n        flat[e] = 1\n    if rho >= 1.0:\n        K = p\n    else:\n        K = 2\n        while K < p and P * rho ** K > 2.0:\n            K += 1\n    for j in range(d):  # direction class: first non-zero coordinate is j (scaled to 1)\n        order = list(range(j, d)) + list(range(j))\n        f = d - 1 - j\n        nbytes = P // 8 + 1\n        slice_bits = [bytearray(nbytes) for _ in range(p)]\n        wperm = torus.B\n        for x in pts:\n            idx = 0\n            for k in range(1, d):\n                idx += x[order[k]] * wperm[k - 1]\n            slice_bits[x[j]][idx >> 3] |= 1 << (idx & 7)\n        slices = [int.from_bytes(b, \"little\") for b in slice_bits]\n        del slice_bits\n        Kj = p if f == 0 else K\n        wperm_can = [wcan[order[k]] for k in range(1, d)]\n        wslice_can = wcan[j]\n        B0 = torus.B[0]\n        for tail in itertools.product(range(p), repeat=max(f - 1, 0)):\n            M = [None] * Kj\n            for t in range(1, Kj):\n                m = slices[t]\n                for i in range(1, f):\n                    m = torus.shift(m, i, (-tail[i - 1] * t) % p)\n                M[t] = m\n            for a0 in (range(p) if f >= 1 else (0,)):\n                cand = slices[0]\n                for t in range(1, Kj):\n                    m = M[t]\n                    if f >= 1:\n                        k = ((-a0 * t) % p) * B0\n                        if k:\n                            m = ((m << k) | (m >> (P - k))) & FULL\n                    cand &= m\n                    if not cand:\n                        break\n                v = tuple([0] * j + [1] + ([a0] + list(tail) if f >= 1 else []))\n                if not cand:\n                    return v\n                if Kj >= p:\n                    continue\n                a = [a0] + list(tail)\n                found = False\n                while cand:\n                    low = cand & -cand\n                    idx = low.bit_length() - 1\n                    cand ^= low\n                    y = torus.decode(idx)\n                    ok = True\n                    for t in range(Kj, p):\n                        e = t * wslice_can\n                        for i in range(f):\n                            e += ((y[i] + a[i] * t) % p) * wperm_can[i]\n                        for i in range(f, n):\n                            e += y[i] * wperm_can[i]\n                        if not flat[e]:\n                            ok = False\n                            break\n                    if ok:\n                        found = True\n                        break\n                if not found:\n                    return v\n    return None\n\n\ndef validate(points, p: int) -> int:\n    \"\"\"Check the returned object is a set of points of F_p^D containing a line in every direction; return its size.\"\"\"\n    if not isinstance(points, (list, tuple, set, frozenset)):\n        fail(f\"kakeya_set({p}, {D}) must return a list of {D}-tuples, got {type(points).__name__}\", \"wrong_answer\")\n    if len(points) > 2 * p ** D:\n        fail(f\"kakeya_set({p}, {D}) returned {len(points)} entries for a space of {p ** D} points\", \"wrong_answer\")\n    pts = set()\n    for q in points:\n        try:\n            if len(q) != D:\n                raise ValueError\n            pts.add(tuple(int(c) % p for c in q))\n        except Exception:\n            fail(f\"kakeya_set({p}, {D}) returned a non-point {q!r}\", \"wrong_answer\")\n    if not pts:\n        fail(f\"kakeya_set({p}, {D}) returned no points\", \"wrong_answer\")\n    pts = sorted(pts)\n    v = missing_direction(pts, p, D)\n    if v is not None:\n        fail(f\"kakeya_set({p}, {D}): the set contains no line in direction {v}\", \"wrong_answer\")\n    return len(pts)\n\n\ndef main() -> None:\n    here = Path(__file__).parent\n    check_imports(here / \"kakeya.py\")\n    sys.path.insert(0, str(here))\n    try:\n        import kakeya as cand  # noqa: E402\n    except SystemExit:\n        raise\n    except Exception as e:\n        fail(f\"import kakeya.py failed: {e!r}\", \"compile_error\")\n    if not hasattr(cand, \"kakeya_set\"):\n        fail(\"kakeya.py must define kakeya_set(p, d, time_budget, seed)\", \"compile_error\")\n\n    seed_int = random.Random(f\"kakeya-fp5|{SEED}\").getrandbits(32)\n    per_instance, beaten = {}, []\n    for p in INSTANCES:\n        if p not in RECORDS:\n            fail(f\"no record for p={p} (known: {sorted(RECORDS)})\", \"error\")\n        t0 = time.perf_counter()\n        try:\n            points = cand.kakeya_set(p, D, BUDGET, seed_int)\n        except SystemExit:\n            raise\n        except Exception as e:\n            fail(f\"kakeya_set({p}, {D}) raised {e!r}\", \"runtime_error\")\n        elapsed = time.perf_counter() - t0\n        if elapsed > 1.25 * BUDGET + 3:\n            fail(f\"kakeya_set({p}, {D}) took {elapsed:.1f}s against a {BUDGET:.0f}s budget\", \"timeout\")\n        t1 = time.perf_counter()\n        size = validate(points, p)\n        ratio = RECORDS[p] / size\n        per_instance[p] = {\"size\": size, \"record\": RECORDS[p], \"ratio\": round(ratio, 6),\n                           \"seconds\": round(elapsed, 2), \"verify_seconds\": round(time.perf_counter() - t1, 2)}\n        if size < RECORDS[p]:\n            beaten.append(p)\n    metric = sum(v[\"ratio\"] for v in per_instance.values()) / len(per_instance)\n    print(json.dumps({\"metric\": round(metric, 6), \"per_instance\": per_instance, \"records_beaten\": beaten}))\n\n\nif __name__ == \"__main__\":\n    main()\n","baseline":{"kakeya.py":"\"\"\"Baseline: the textbook quadratic construction, built one dimension at a time.\n\nK_1 = F_p.  K_i = {(t, t*m_1 - m_1^2, ..., t*m_{i-1} - m_{i-1}^2) : t, m_j in F_p}  U  {0} x K_{i-1}.\n\nThe first part contains, for every direction (1, m_1, ..., m_{i-1}), the line through\n(0, -m_1^2, ..., -m_{i-1}^2); the second part covers directions whose first coordinate is 0.\nEach slice t of the first part is a product of (p+1)/2-element sets, so |K_d| is about p^d / 2^(d-1)\nplus lower-order terms. The records beat this only in those lower-order terms: this baseline is\nalready within a few percent of them, and the game is entirely about the p^(d-1) and p^(d-2) terms.\nIgnores the time budget and the seed (it is deterministic and instant).\"\"\"\n\nimport itertools\n\n\ndef kakeya_set(p: int, d: int, time_budget: float, seed: int) -> list[tuple[int, ...]]:\n    K = {(t,) for t in range(p)}\n    for i in range(2, d + 1):\n        image = [sorted({(t * m - m * m) % p for m in range(p)}) for t in range(p)]\n        new = set()\n        for t in range(p):\n            for rest in itertools.product(image[t], repeat=i - 1):\n                new.add((t,) + rest)\n        for x in K:\n            new.add((0,) + x)\n        K = new\n    return sorted(K)\n"}}