{"id":"nikodym-fp3","name":"Smallest Nikodym sets in F_p^3","family":"finite-geometry","description":"Find a subset of F_p^3 such that every point lies on a line whose other p-1 points are all in the set, as small as possible, for 14 primes 31 <= p <= 89. Scored against the AlphaEvolve record sizes (problem 1 of the AlphaEvolve repository), about p^3 - 8p^2.","metric":"record_ratio","direction":"maximize","tolerance":0.05,"eval_timeout_seconds":300,"agent_timeout_seconds":1800,"mutable":["nikodym.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 Nikodym sets in F_p^3\n\n## Goal\n\nA Nikodym set in F_p^3 is a set N such that every point x of F_p^3 lies on some line l with the\npunctured line l \\ {x} contained in N (x itself need not be in N). Find one that is as small as\npossible; equivalently, remove as many points from F_p^3 as you can while keeping the property.\n\n`nikodym.py` exposes\n\n    nikodym_set(p: int, time_budget: float, seed: int) -> list[tuple[int, int, int]]\n\nReturn the points of N as integer triples; coordinates are reduced mod p and duplicates are counted\nonce. The eval checks the punctured-line condition exactly for all p^3 points and then counts the\ndistinct points. Any uncovered point 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_nikodym.ipynb`, 3D section. The\nwork led to T. Tao, \"New Nikodym set constructions over finite fields\" (arXiv:2511.07721), which\ngives Nikodym sets in F_q^3 of size q^3 - (1/log 2 + 1 + o(1)) q^2 log q asymptotically; no explicit\nsizes for specific p are published there, so the records below are the explicit AlphaEvolve sets.\n\n## Metric\n\n    metric = mean over p in INSTANCES of  record(p) / |N_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\nThe record construction removes from F_p^3 the union of the surfaces\n`{(t, t^k, t^(k+s)) : t in F_p^*, k}` for shifts s in {+-1, +-2, +-3, +-4}, plus the diagonal\n(t, t, t) and the three plane diagonals (t, t, 0), (t, 0, t), (0, t, t), t != 0. The notebook's\nDeep Think note `nikodym.tex` estimates its size as p^3 - 8p^2 + O(p). The notebook lists sizes for\np >= 47; the final program was re-run here for every prime and produced exactly those numbers, and\nis also a valid Nikodym set for p = 31, 37, 41, 43 (it is not for p <= 29, which is why those primes\nare absent). None of these is proven optimal. Tao's construction removes\n(1/log 2 + 1 + o(1)) p^2 log p, about 2.44 p^2 log p, points asymptotically, which nominally exceeds\n8p^2 for every p here; the o(1) term is not quantified, so whether an explicit version beats these\nsets at these p is open, and there is real room.\n\n| p | record | source |\n|---|---|---|\n| 31 | 26312 | AlphaEvolve final program re-run and verified here |\n| 37 | 45264 | re-run, verified |\n| 41 | 61704 | re-run, verified |\n| 43 | 72288 | re-run, verified |\n| 47 | 91492 | listed in the notebook; re-run reproduces it |\n| 53 | 134908 | listed; reproduced |\n| 59 | 185656 | listed; reproduced |\n| 61 | 214008 | listed; reproduced |\n| 67 | 281940 | listed; reproduced |\n| 71 | 336144 | listed; reproduced |\n| 73 | 367900 | listed; reproduced |\n| 79 | 466440 | listed; reproduced |\n| 83 | 532096 | listed; reproduced |\n| 89 | 666520 | listed; reproduced |\n\n## Constraints\n\n- Standard library only. No numpy. The eval rejects other imports.\n- Respect `time_budget` (seconds, per prime). Verification (up to about 3 s at p = 89) is not\n  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=31,47` runs only those primes (the default set is all 14 primes above).\n- `ZT_EVAL_PER_INSTANCE_SECONDS=1` shortens the per-prime budget (default 5 s; the full eval takes\n  about 100 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- Think in terms of the complement C = F_p^3 \\ N. A point x is fine iff some line through x meets\n  C in no point other than x. So C must be \"line-avoidable\" from everywhere; unions of low-degree\n  curves and surfaces inside (F_p^*)^3 are, because a line meets such a surface in boundedly many\n  points and there are p^2 + p + 1 directions to choose from.\n- The baseline removes the three coordinate planes minus the axes (|N| = (p-1)^3 + 3p - 2) and\n  scores 0.94-0.99. The record removes about 8p^2 points; Tao's construction shows about\n  2.44 p^2 log p is possible asymptotically, and random greedy removal (add points to C while the\n  property survives) is a cheap way to look for it at these sizes.\n- More surfaces: shifts s beyond +-4 make the construction invalid for small p because too many\n  points fail; check which shift sets survive for each p, and try surfaces z = y * x^s with other\n  exponent patterns, or monomial surfaces in other coordinate pairs.\n- Verification is exact and fast; a local search that removes a point and checks is feasible for\n  p <= 43 and gives a target for a closed form.\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 nikodym-fp3: Nikodym sets in F_p^3. Prints one JSON line: {\"metric\": record_ratio, ...}.\n\nEnv:\n  ZT_EVAL_SEED                    seed handed to nikodym_set()\n  ZT_EVAL_PER_INSTANCE_SECONDS    time budget per prime p (default 5)\n  ZT_EVAL_INSTANCES               comma-separated primes p to run (default \"31,37,41,43,47,53,59,61,67,71,73,79,83,89\")\n\nThe metric is the mean over p of record(p) / |N_p|, where |N_p| is the number of distinct points in\nthe set the solver returns, counted here after an exact check that every point of F_p^3 lies on a\nline whose other p-1 points are all in the set. The solver's own opinion of its size is never used.\n\"\"\"\n\nfrom __future__ import annotations\n\nimport ast\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\", \"5\"))\nINSTANCES = [int(x) for x in os.environ.get(\"ZT_EVAL_INSTANCES\", \"31,37,41,43,47,53,59,61,67,71,73,79,83,89\").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\n# Best-known sizes of Nikodym sets in F_p^3. Source: the AlphaEvolve repository of problems,\n# problem 1 (\"Kakeya and Nikodym sets in finite fields\"), experiments/finite_field_nikodym_problem/\n# finite_field_nikodym.ipynb, 3D section: the \"best_score_p<p>_d3\" values (p >= 47) and, for\n# 31 <= p <= 43, the size of the set produced by the notebook's final program, re-run and verified\n# with this eval (it reproduces the listed values exactly for p >= 47 and is invalid for p <= 29).\n# Update when a hub-verified submission beats one.\nRECORDS = {31: 26312, 37: 45264, 41: 61704, 43: 72288, 47: 91492, 53: 134908, 59: 185656, 61: 214008,\n           67: 281940, 71: 336144, 73: 367900, 79: 466440, 83: 532096, 89: 666520}\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 nikodym.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 Nikodym check\n#\n# Work with the complement C = F_p^3 \\ N. A point x is covered iff some line through x meets C in\n# no point other than x. For each direction, the lines are the fibres of a projection onto a\n# 2-dimensional slice; C's slices are p^2-bit masks, so \"which fibres contain 0 / exactly 1 / >= 2\n# points of C\" is a handful of shifted ORs and ANDs. Points on empty fibres are covered; a point of\n# C on a fibre containing exactly one point of C (itself) is covered. Everything is exact.\n\n\ndef _rot(m: int, k: int, P: int, FULL: int) -> int:\n    return ((m << k) | (m >> (P - k))) & FULL if k else m\n\n\ndef uncovered_point(pts: list, p: int):\n    \"\"\"Return None if pts (distinct triples over F_p) is a Nikodym set, else a point with no punctured line.\"\"\"\n    total = p ** 3\n    if len(pts) == total:\n        return None\n    P = p * p\n    FULL = (1 << P) - 1\n    B0 = p\n    # masks for cyclic shifts of the fast coordinate within each row of p bits\n    rep = FULL // ((1 << p) - 1)\n    hi = [0] + [(((1 << (p - dz)) - 1) << dz) * rep for dz in range(1, p)]\n    lo = [0] + [((1 << dz) - 1) * rep for dz in range(1, p)]\n\n    def zshift(m: int, dz: int) -> int:\n        if dz == 0 or m == 0:\n            return m\n        return ((m << dz) & hi[dz]) | ((m >> (p - dz)) & lo[dz])\n\n    inN = bytearray(total)\n    for x in pts:\n        inN[x[0] * P + x[1] * p + x[2]] = 1\n    comp_pts = [(i // P, (i // p) % p, i % p) for i in range(total) if not inN[i]]\n    covered_sets = []\n    for j in range(3):  # direction classes: (1,a,b) sliced by x; (0,1,c) sliced by y; (0,0,1) sliced by z\n        order = [j, (j + 1) % 3, (j + 2) % 3]\n        f = 2 - j\n        cb = [bytearray(P // 8 + 1) for _ in range(p)]\n        for x in comp_pts:\n            idx = x[order[1]] * p + x[order[2]]\n            cb[x[order[0]]][idx >> 3] |= 1 << (idx & 7)\n        C = [int.from_bytes(b, \"little\") for b in cb]\n        covered = [0] * p\n        if f == 0:\n            seen = twice = 0\n            for t in range(p):\n                m = C[t]\n                twice |= seen & m\n                seen |= m\n            once = seen & ~twice\n            free = FULL ^ seen\n            for s in range(p):\n                covered[s] = free | (once & C[s])\n        else:\n            for b in (range(p) if f == 2 else (0,)):\n                Cs = [zshift(C[t], (-b * t) % p) for t in range(p)] if f == 2 else C\n                for a in range(p):\n                    seen = twice = 0\n                    for t in range(p):\n                        m = _rot(Cs[t], ((-a * t) % p) * B0, P, FULL)\n                        twice |= seen & m\n                        seen |= m\n                    once = seen & ~twice\n                    free = FULL ^ seen\n                    for s in range(p):\n                        k = ((a * s) % p) * B0\n                        fr = _rot(free, k, P, FULL)\n                        on = _rot(once, k, P, FULL)\n                        if f == 2:\n                            db = (b * s) % p\n                            fr = zshift(fr, db)\n                            on = zshift(on, db)\n                        covered[s] |= fr | (on & C[s])\n                if all(c == FULL for c in covered):\n                    return None\n        covered_sets.append((order, covered))\n        if all(c == FULL for c in covered):\n            return None\n    cov = bytearray(total)\n    for order, covered in covered_sets:\n        for s in range(p):\n            m = covered[s]\n            while m:\n                low = m & -m\n                idx = low.bit_length() - 1\n                m ^= low\n                y1, y2 = divmod(idx, p)\n                coords = [0, 0, 0]\n                coords[order[0]] = s\n                coords[order[1]] = y1\n                coords[order[2]] = y2\n                cov[coords[0] * P + coords[1] * p + coords[2]] = 1\n    for i in range(total):\n        if not cov[i]:\n            return (i // P, (i // p) % p, i % p)\n    return None\n\n\ndef validate(points, p: int) -> int:\n    \"\"\"Check the returned object is a Nikodym set in F_p^3; return its number of distinct points.\"\"\"\n    if not isinstance(points, (list, tuple, set, frozenset)):\n        fail(f\"nikodym_set({p}) must return a list of triples, got {type(points).__name__}\", \"wrong_answer\")\n    if len(points) > 2 * p ** 3:\n        fail(f\"nikodym_set({p}) returned {len(points)} entries for a space of {p ** 3} points\", \"wrong_answer\")\n    pts = set()\n    for q in points:\n        try:\n            if len(q) != 3:\n                raise ValueError\n            pts.add(tuple(int(c) % p for c in q))\n        except Exception:\n            fail(f\"nikodym_set({p}) returned a non-point {q!r}\", \"wrong_answer\")\n    if not pts:\n        fail(f\"nikodym_set({p}) returned no points\", \"wrong_answer\")\n    pts = sorted(pts)\n    x = uncovered_point(pts, p)\n    if x is not None:\n        fail(f\"nikodym_set({p}): no line through {x} has its other points in the set\", \"wrong_answer\")\n    return len(pts)\n\n\ndef main() -> None:\n    here = Path(__file__).parent\n    check_imports(here / \"nikodym.py\")\n    sys.path.insert(0, str(here))\n    try:\n        import nikodym as cand  # noqa: E402\n    except SystemExit:\n        raise\n    except Exception as e:\n        fail(f\"import nikodym.py failed: {e!r}\", \"compile_error\")\n    if not hasattr(cand, \"nikodym_set\"):\n        fail(\"nikodym.py must define nikodym_set(p, time_budget, seed)\", \"compile_error\")\n\n    seed_int = random.Random(f\"nikodym-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.nikodym_set(p, BUDGET, seed_int)\n        except SystemExit:\n            raise\n        except Exception as e:\n            fail(f\"nikodym_set({p}) raised {e!r}\", \"runtime_error\")\n        elapsed = time.perf_counter() - t0\n        if elapsed > 1.25 * BUDGET + 3:\n            fail(f\"nikodym_set({p}) 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":{"nikodym.py":"\"\"\"Baseline: all points with no zero coordinate, plus the three coordinate axes.\n\nSize (p-1)^3 + 3p - 2. Why it is a Nikodym set: a point x with all coordinates non-zero lies on\nthe line through the origin, whose other points are s*x (s != 1): non-zero coordinates for s != 0\nand the origin for s = 0, all in the set. A point (0, b, c) with b, c != 0 uses direction (1, 0, 0),\na point (0, 0, c) uses direction (1, 1, 0), and the origin uses direction (1, 1, 1); the other two\naxes are symmetric. Scores 0.94-0.99 of the records. Beat it.\nIgnores the time budget and the seed (it is deterministic and instant).\"\"\"\n\nimport itertools\n\n\ndef nikodym_set(p: int, time_budget: float, seed: int) -> list[tuple[int, int, int]]:\n    pts = set(itertools.product(range(1, p), repeat=3))\n    for t in range(p):\n        pts.add((t, 0, 0))\n        pts.add((0, t, 0))\n        pts.add((0, 0, t))\n    return sorted(pts)\n"}}