_d3` across its three experiments). None is proven optimal: the best lower bound\nknown 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).\n\n| p | record | what it is |\n|---|---|---|\n| 5 | 53 | (2p^3+7p^2-1)/8; formula proved in the notebook's Deep Think note `kakeya2.tex`; construction reproduced and verified here |\n| 7 | 128 | AlphaEvolve search result; reproduced here by exhaustive search over the 4 offsets of the experiment-3 construction |\n| 11 | 438 | as p = 7 (reproduced) |\n| 13 | 697 | (2p^3+7p^2-1)/8, reproduced |\n| 19 | 2031 | AlphaEvolve search result, not reproduced |\n| 23 | 3505 | AlphaEvolve search result, not reproduced |\n| 29 | 6833 | (2p^3+7p^2-1)/8, reproduced |\n| 31 | 8290 | AlphaEvolve search result, not reproduced |\n| 37 | 13861 | (2p^3+7p^2-1)/8, reproduced |\n| 41 | 18701 | (2p^3+7p^2-1)/8, reproduced |\n| 43 | 21495 | AlphaEvolve search result (experiment 2), not reproduced |\n| 47 | 27892 | AlphaEvolve search result, not reproduced |\n| 53 | 39677 | (2p^3+7p^2-1)/8, reproduced |\n| 59 | 54396 | AlphaEvolve search result, not reproduced |\n| 61 | 60001 | (2p^3+7p^2-1)/8, reproduced |\n| 67 | 79126 | AlphaEvolve search result, not reproduced |\n| 71 | 93895 | AlphaEvolve search result, not reproduced |\n\nFor p = 1 (mod 4) the record is exactly (2p^3 + 7p^2 - 1)/8 and comes from an explicit\nconstruction (below). For p = 3 (mod 4) the records are the outputs of AlphaEvolve's parameter\nsearches, sit within a few units of (2p^3 + 7p^2 - 1)/8, and look the most beatable: nobody has\nproved a formula for that case.\n\nThe record construction for p = 1 (mod 4), with S the squares in F_p including 0 and g = (p-1)/4:\n\n K_A = { (x, (q1+q2)/2 - x^2 - g, (q1-q2)/2) : x in F_p, q1, q2 in S }\n K_0B = { (0, y, z) : y + z^2 in S }\n K_0C = { (0, y, 0) : y in F_p }\n\nK_A handles every direction with a non-zero first coordinate (each slice x = t is an affine image\nof S x S), and the plane x = 0 carries a 2D Kakeya set for the rest. The whole art is in making the\nthree pieces overlap as much as possible.\n\n## Constraints\n\n- Standard library only. No numpy. The eval rejects other imports.\n- Respect `time_budget` (seconds, per prime). The verification time is not charged to you.\n- Deterministic given `seed`: use `random.Random(seed)` if you randomise anything.\n- Return at most 2 p^3 entries.\n\n## Iterating\n\n- `ZT_EVAL_INSTANCES=7,23` runs only those primes (the default set is all 17 primes above).\n- `ZT_EVAL_PER_INSTANCE_SECONDS=1` shortens the per-prime budget (default 4 s; the full eval takes\n about 80 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 and already scores about 0.99. Everything\n left is in the p^2 and p terms: how the \"x != 0\" part and the x = 0 plane overlap, and how the\n 2D Kakeya set inside the plane x = 0 is chosen.\n- Parametrise: affine offsets in each piece (the gammas of the notebook's experiment 3), shears\n and rotations of the (y, z) coordinates, and which quadratic character sets are used. Compute the\n size of the union analytically (inclusion-exclusion) so you can search thousands of parameter\n choices per prime, then build the best one.\n- For p = 3 (mod 4), -1 is a non-square, which changes the intersection counts; a construction\n tuned to that case may beat the search results.\n- Local search: start from a valid set, try removing a point, and repair by re-adding the cheapest\n points that restore the missing directions. Small p first; the eval is exact and fast.\n- Sanity-check any claimed improvement on several p before spending the whole budget on it.\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-fp3: Kakeya sets in F_p^3. 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 4)\n ZT_EVAL_INSTANCES comma-separated primes p to run (default \"5,7,11,13,19,23,29,31,37,41,43,47,53,59,61,67,71\")\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\", \"4\"))\nINSTANCES = [int(x) for x in os.environ.get(\"ZT_EVAL_INSTANCES\", \"5,7,11,13,19,23,29,31,37,41,43,47,53,59,61,67,71\").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 = 3\n\n# Best-known sizes of Kakeya sets in F_p^3. 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, 3D section: the smallest \"best_score_p
_d3\" 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: 53, 7: 128, 11: 438, 13: 697, 19: 2031, 23: 3505, 29: 6833, 31: 8290, 37: 13861, 41: 18701,\n 43: 21495, 47: 27892, 53: 39677, 59: 54396, 61: 60001, 67: 79126, 71: 93895}\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-fp3|{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"}}