{"id":"furstenberg-sarkozy","name":"Furstenberg–Sárközy: modular sets avoiding k-th power differences","family":"number-theory","description":"AlphaEvolve Problem 31: pick a squarefree modulus m and a subset A of Z/mZ in which no two elements differ by a nonzero k-th power residue; the density exponent log|A|/log m lifts to a lower bound for the largest square-difference-free (k=2) or cube-difference-free (k=3) subset of {1..N}. Scored against Lewko's 12 elements in Z/205Z and 14 elements in Z/91Z.","metric":"record_ratio","direction":"maximize","tolerance":0.01,"eval_timeout_seconds":180,"agent_timeout_seconds":1800,"mutable":["modset.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":"# Furstenberg–Sárközy: modular sets avoiding k-th power differences\n\n## Goal\n\nThe Furstenberg–Sárközy theorem says a subset of `{1, ..., N}` with no two elements differing by a\nperfect square has size `o(N)`. The best lower bounds come from a modular construction (Ruzsa\n1984): take a squarefree modulus `m` and a set `A ⊆ Z/mZ` in which no two distinct elements differ\nby a nonzero `k`-th power residue mod `m`; writing integers in base `m` with digits from `A`\nlifts this to a subset of `{1, ..., N}` of size about `N^q` with `q = log|A| / log m` (Ruzsa's\nexponent for squares is then `½(1 + q)`). Ruzsa used `m = 65`, `|A| = 7`; Lewko (2015) found\n`m = 205`, `|A| = 12`, which is the current record for squares. For cubes the known construction\nis 14 elements in `Z/91Z`.\n\nThis is AlphaEvolve Problem 31 (Section 6.16 of arXiv:2511.02864; the notebook header numbers it\n32). AlphaEvolve reproduced both records and found nothing better. The open question this pack\nposes is: **is there a squarefree `m` with a larger `log|A| / log m`?**\n\n`modset.py` exposes\n\n    modular_set(k: int, time_budget: float, seed: int) -> tuple[int, list[int]]\n\nreturning `(m, A)`: `m` a squarefree Python int with `2 ≤ m ≤ 1_000_000`, and `A` a list of distinct\nPython ints in `[0, m)`. Instances are `k2` (squares) and `k3` (cubes).\n\n## Metric\n\nThe eval recomputes the nonzero `k`-th power residues `{y^k mod m : 1 ≤ y < m}`, checks `m` is\nsquarefree, and checks every ordered pair `a ≠ b` in `A` has `(a − b) mod m` outside that set.\nThen\n\n    q = log|A| / log m          (0 if |A| < 2)\n    metric = mean over k of  q / q_record\n\n| label | k | record | q_record | source | status |\n|---|---|---|---|---|---|\n| `k2` | 2 | `m = 205`, `|A| = 12` | 0.466824 | M. Lewko, \"An improved lower bound related to the Furstenberg–Sárközy theorem\", Electron. J. Combin. 22(1) (2015) P1.32; Ruzsa 1984 had `m = 65`, `|A| = 7` (q = 0.466155); AlphaEvolve Problem 31 reproduces it | 12 is the exact maximum for `m = 205` (exhaustive branch-and-bound while building this pack); whether any other `m` beats the exponent is open |\n| `k3` | 3 | `m = 91`, `|A| = 14` | 0.585045 | AlphaEvolve Problem 31 (arXiv:2511.02864, Section 6.16) states it as the known lower bound and reproduces it | 14 is the exact maximum for `m = 91` (exhaustive search); other `m` open |\n\nTwo warnings. The explicit sets printed in the AlphaEvolve notebook\n(`furstenberg_sarkozy.ipynb`) do **not** verify: they contain forbidden differences. The sizes\nare right; find your own sets (e.g. for `m = 205`: `{0, 2, 8, 14, 77, 79, 85, 96, 103, 109, 111, 181}`).\nAnd the scale is compressed: exponents of sensible constructions all sit between 0.40 and 0.47,\nso a ratio of 0.998 is Ruzsa's construction and 1.0015 would be a new theorem. `tolerance` in\n`problem.toml` is set accordingly; make your solver deterministic in its outcome, not just its\nseed.\n\n## Constraints\n\n- Standard library only. No numpy, no scipy. The eval rejects other imports.\n- Respect `time_budget` (seconds, per call). The eval fails a call that runs more than 25 % over.\n- Deterministic given `seed`: use `random.Random(seed)`.\n- `m ≤ 1_000_000` (the eval enumerates residues in `O(m)`).\n\n## Iterating\n\n- `ZT_EVAL_INSTANCES=k2` restricts the eval to one power (default `k2,k3`).\n- `ZT_EVAL_PER_INSTANCE_SECONDS=5` shrinks the per-instance budget (default 40; the full eval\n  can take up to about 80 s; the baseline stops early).\n- `ZT_EVAL_SEED` only changes the `seed` handed to your solver; the instance set is fixed.\n\n## Ideas that are known to matter (check the journal before repeating one)\n\n- For a fixed `m` this is a maximum independent set in a circulant graph (vertices `Z/mZ`, edges\n  at `±` residue differences); it is translation-invariant, so fix `0 ∈ A`. Bitset\n  branch-and-bound solves `m = 205` exactly in seconds in pure Python.\n- Products of small primes (`65 = 5·13`, `205 = 5·41`, `91 = 7·13`) win because the residue set is\n  a product set (CRT) and stays small: fewer forbidden differences per modulus. Enumerate `m` by\n  the *fraction* of residues that are `k`-th powers first, then search only the promising ones.\n- Ruzsa's exponent for squares only uses `q`; for higher powers the lifting differs, but the\n  modular problem scored here is the same.\n- Lewko searched `m` by computer; the frontier is wherever pure Python plus cleverness runs out.\n\nWrite one honest line in `NOTES.md`: the idea, and which `k` it helped.\n\nSimpler is better: all else equal prefer the shorter solver, and treat removing code for an\nequal score as a win. Log every experiment, including discards, in your results.tsv.\n","eval_py":"\"\"\"Eval for furstenberg-sarkozy. Prints one JSON line: {\"metric\": record_ratio, ...}.\n\nEnv:\n  ZT_EVAL_SEED                   seed handed to modular_set()\n  ZT_EVAL_PER_INSTANCE_SECONDS   time budget per instance (default 40)\n  ZT_EVAL_INSTANCES              comma-separated instance labels (default \"k2,k3\")\n\"\"\"\n\nfrom __future__ import annotations\n\nimport ast\nimport json\nimport math\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\", \"40\"))\nINSTANCES = [s.strip() for s in os.environ.get(\"ZT_EVAL_INSTANCES\", \"k2,k3\").split(\",\") if s.strip()]\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\"}\nM_MAX = 1_000_000\n\n# label -> (k, record modulus, record set size). The score is q = log|A|/log m against\n# log(size)/log(m) of the record. k2: Lewko 2015 (12 in Z/205Z). k3: AlphaEvolve Problem 31 (14 in\n# Z/91Z). Both sizes are exact maxima for those moduli (exhaustive search); see program.md.\nRECORDS = {\"k2\": (2, 205, 12), \"k3\": (3, 91, 14)}\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 pack.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\ndef is_squarefree(m: int) -> bool:\n    if m % 4 == 0:\n        return False\n    d = 3\n    while d * d <= m:\n        if m % (d * d) == 0:\n            return False\n        d += 2\n    return True\n\n\ndef validate(label: str, k: int, out) -> tuple[int, int]:\n    \"\"\"Return (m, |A|) after checking the construction exactly.\"\"\"\n    if not isinstance(out, (list, tuple)) or len(out) != 2:\n        fail(f\"modular_set({label}) must return (m, A)\", \"wrong_answer\")\n    m, a_list = out\n    if type(m) is not int or not 2 <= m <= M_MAX:\n        fail(f\"modular_set({label}) returned m={m!r}; need an int with 2 <= m <= {M_MAX}\", \"wrong_answer\")\n    if not is_squarefree(m):\n        fail(f\"modular_set({label}) returned m={m}, which is not squarefree\", \"wrong_answer\")\n    if not isinstance(a_list, (list, tuple)):\n        fail(f\"modular_set({label}) must return A as a list\", \"wrong_answer\")\n    elems = []\n    for x in a_list:\n        if type(x) is not int or not 0 <= x < m:\n            fail(f\"modular_set({label}) returned element {x!r}, not an int in [0, {m})\", \"wrong_answer\")\n        elems.append(x)\n    if len(set(elems)) != len(elems):\n        fail(f\"modular_set({label}) returned duplicate elements\", \"wrong_answer\")\n    residues = {pow(y, k, m) for y in range(1, m)}\n    residues.discard(0)\n    for i, a in enumerate(elems):\n        for b in elems[:i]:\n            if (a - b) % m in residues or (b - a) % m in residues:\n                fail(f\"modular_set({label}): {a} - {b} is a {k}-th power residue mod {m}\", \"wrong_answer\")\n    return m, len(elems)\n\n\ndef main() -> None:\n    here = Path(__file__).parent\n    check_imports(here / \"modset.py\")\n    sys.path.insert(0, str(here))\n    try:\n        import modset as cand  # noqa: E402\n    except SystemExit:\n        raise\n    except Exception as e:\n        fail(f\"import modset.py failed: {e!r}\", \"compile_error\")\n    if not hasattr(cand, \"modular_set\"):\n        fail(\"modset.py must define modular_set(k, time_budget, seed)\", \"compile_error\")\n\n    seed_int = random.Random(f\"fs|{SEED}\").getrandbits(32)\n    per, beaten = {}, []\n    for label in INSTANCES:\n        if label not in RECORDS:\n            fail(f\"no record for instance {label!r} (known: {sorted(RECORDS)})\", \"error\")\n        k, rec_m, rec_size = RECORDS[label]\n        q_rec = math.log(rec_size) / math.log(rec_m)\n        t0 = time.perf_counter()\n        try:\n            out = cand.modular_set(k, BUDGET, seed_int)\n        except SystemExit:\n            raise\n        except Exception as e:\n            fail(f\"modular_set({label}) raised {e!r}\", \"runtime_error\")\n        elapsed = time.perf_counter() - t0\n        if elapsed > 1.25 * BUDGET + 3:\n            fail(f\"modular_set({label}) took {elapsed:.1f}s against a {BUDGET:.0f}s budget\", \"timeout\")\n        m, size = validate(label, k, out)\n        q = math.log(size) / math.log(m) if size >= 2 else 0.0\n        per[label] = {\"k\": k, \"m\": m, \"size\": size, \"q\": round(q, 6), \"record\": {\"m\": rec_m, \"size\": rec_size, \"q\": round(q_rec, 6)},\n                      \"ratio\": round(q / q_rec, 6), \"seconds\": round(elapsed, 2)}\n        if q > q_rec + 1e-12:\n            beaten.append(label)\n    metric = sum(v[\"ratio\"] for v in per.values()) / len(per)\n    print(json.dumps({\"metric\": round(metric, 6), \"per_instance\": per, \"records_beaten\": beaten}))\n\n\nif __name__ == \"__main__\":\n    main()\n","baseline":{"modset.py":"\"\"\"Baseline: scan squarefree moduli in order, randomised greedy independent sets, keep the best\nexponent. Beat it.\"\"\"\n\nimport math\nimport random\nimport time\n\n\ndef _squarefree(m: int) -> bool:\n    if m % 4 == 0:\n        return False\n    d = 3\n    while d * d <= m:\n        if m % (d * d) == 0:\n            return False\n        d += 2\n    return True\n\n\ndef modular_set(k: int, time_budget: float, seed: int) -> tuple[int, list[int]]:\n    rng = random.Random(seed)\n    deadline = time.perf_counter() + 0.9 * time_budget\n    best_m, best_a, best_q = 2, [0], 0.0\n    for m in range(2, 3000):\n        if time.perf_counter() > deadline:\n            break\n        if not _squarefree(m):\n            continue\n        forb = {pow(y, k, m) for y in range(1, m)}\n        forb |= {(-r) % m for r in forb}\n        forb.discard(0)\n        for _ in range(4):\n            order = list(range(1, m))\n            rng.shuffle(order)\n            chosen = [0]  # translation invariance: 0 is free\n            for v in order:\n                if all((v - u) % m not in forb for u in chosen):\n                    chosen.append(v)\n            q = math.log(len(chosen)) / math.log(m) if len(chosen) >= 2 else 0.0\n            if q > best_q:\n                best_m, best_a, best_q = m, chosen, q\n    return best_m, sorted(best_a)\n"}}