{"id":"difference-basis-length","name":"Difference bases: longest interval from k integers","family":"additive-combinatorics","description":"AlphaEvolve repository problem 7: choose at most k integers whose pairwise differences cover 1..n with n as large as possible. Instances k = 10..19 (Miller 1971), 128 (Golay's 2.6571 bound) and 360 (AlphaEvolve's 2.6390 bound). Exact verification.","metric":"record_ratio","direction":"maximize","tolerance":0.05,"eval_timeout_seconds":300,"agent_timeout_seconds":1800,"mutable":["basis.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":"# Difference bases: longest interval from k integers\n\n## Goal\n\nA **difference basis** for `{1, ..., n}` is a set `B` of integers such that every `1 ≤ d ≤ n` is\n`b - b'` for some `b, b' ∈ B`. The elements are *unrestricted*: they may lie anywhere (this is the\nvariant of AlphaEvolve repository problem 7; the restricted variant, marks confined to `[0, n]`, is\nthe `sparse-ruler-marks` pack). Let `Δ(n)` be the smallest possible `|B|`. Rédei–Rényi and Leech\nshowed `Δ(n)² / n` converges to a constant `C`, with\n\n    2.434... ≤ C ≤ 128² / 6166 = 2.6571...   (Leech 1956; Golay 1972)\n\nuntil AlphaEvolve found 360 integers covering `1..49109`, i.e. `C ≤ 2.6390`\n(Georgiev, Gómez-Serrano, Tao, Wagner, *Mathematical exploration and discovery at scale*, 2025,\n§6.3). This pack turns the problem around per size: for each element budget `k`, cover the longest\npossible interval.\n\n`basis.py` exposes\n\n    difference_basis(k: int, time_budget: float, seed: int) -> list[int]\n\nreturning **at most k** distinct integers (`|x| ≤ 10^12`, any order). The eval forms every pairwise\ndifference itself and takes the largest `n` such that all of `1..n` appear. Nothing you report is\ntrusted; a set that does not even represent 1 fails the submission.\n\n## Metric\n\nThe eval runs `difference_basis` on the fixed budget set below, each with the given time budget\n(8 s by default), verifies the set, and reports\n\n    metric = mean over k of  n(k) / record_n(k)\n\nso 1.0 means matching every best-known length and anything above 1.0 on a `k` is a new record.\nPer-instance detail (`n`, elements used, `k2_over_n = |B|²/n`, ratio, seconds) is in\n`per_instance`; `records_beaten` lists any `k` you beat, and `constant_beaten` is true when any\nreturned set has `|B|²/n < 360²/49109`, which improves the AlphaEvolve bound on `C` even if it does\nnot beat the record of its own `k`. `ZT_EVAL_SEED` only changes the `seed` handed to your solver.\n\n## Records\n\n| k | best-known n | |B|²/n | source | proven |\n|---|---|---|---|---|\n| 10 | 37 | 2.703 | Miller (1971), quoted in OEIS A005488 | no |\n| 11 | 45 | 2.689 | Miller (1971), OEIS A005488 | no |\n| 12 | 51 | 2.824 | Miller (1971), OEIS A005488 | no |\n| 13 | 61 | 2.770 | Miller (1971), OEIS A005488 | no |\n| 14 | 70 | 2.800 | Miller (1971), OEIS A005488 | no |\n| 15 | 79 | 2.848 | Miller (1971), OEIS A005488 | no |\n| 16 | 93 | 2.753 | Miller (1971), OEIS A005488 | no |\n| 17 | 101 | 2.861 | Miller (1971), OEIS A005488 | no |\n| 18 | 113 | 2.867 | Miller (1971), OEIS A005488 | no |\n| 19 | 127 | 2.843 | Miller (1971), OEIS A005488 | no |\n| 128 | 6166 | 2.6571 | Golay's bound `Δ(6166) ≤ 128`, quoted in Georgiev et al. (2025) §6.3 and Banakh–Gavrylkiv (2019) | no |\n| 360 | 49109 | 2.6390 | AlphaEvolve, repository of problems, problem 7 (world record; construction re-verified for this pack) | no |\n\nOEIS A005488 lists Miller's values as lower bounds on the maximal length (Bermond 1978 quotes them\nas exact); the entry for k = 9 (n = 29) was only proven optimal in 2022, so k = 10 onward is open.\nFor comparison, the best restricted rulers (OEIS A004137) reach 36, 43, 50, 58, 68, 79, 90, 101,\n112, 123 for k = 10..19, and Wichmann rulers give only `≈ 3` for `|B|²/n` at large k, so the\nlarge instances are where algebra beats combinatorial search.\n\nIf you beat one, the set is the evidence: it is in the eval log. Say so in your notes so the hub\ncan update the table and forward the set.\n\n## Iterating\n\n- Start on one or two budgets: `ZT_EVAL_INSTANCES=10,11 ZT_EVAL_PER_INSTANCE_SECONDS=2 python eval.py`\n  runs in seconds; `ZT_EVAL_INSTANCES=360` exercises the large construction alone. The full set\n  takes about 96 s of solver time plus verification (which is instant: at most C(360, 2) differences).\n- Respect `time_budget` (seconds, per call). The eval kills the run if a call overruns it by more\n  than 25% + 3 s. Be deterministic given `seed`: use `random.Random(seed)`.\n- Only the standard library is available (`math, random, itertools, functools, collections, heapq, time`).\n- Leech's construction: if `A` is a difference basis for `{1..a}` and `D` is a perfect difference\n  set mod `m` (every nonzero residue is a difference of two elements of `D` exactly once; Singer\n  sets give `|D| = q + 1`, `m = q² + q + 1` for prime powers `q`), then `{x·m + d : x ∈ A, d ∈ D}`\n  has `|A|·|D|` elements and covers roughly `(a - 1)·m`. AlphaEvolve's record is exactly this with\n  `A = {0, 1, 4, 6}` and `q = 89`, but *which* Singer set (translate and multiplier equivalents\n  cover different prefixes: the baseline's naive choice reaches 48160, AlphaEvolve's 49109) and\n  what `A` is used matter. Try other `A`, other `q`, Singer sets from prime powers (needs GF(q³)\n  arithmetic over a prime-power field), and post-hoc repair by moving a few elements.\n- For small `k` the problem is combinatorial: branch-and-bound or simulated annealing over\n  element positions, seeded with Miller-style patterns, is the tool. Even a one-step improvement on\n  any k = 10..19 is a new entry for OEIS.\n\nWrite one honest line in `NOTES.md`: the idea, and which `k` it helped. Simpler is better: all else\nequal prefer the shorter solver. Log every experiment, including discards, in your results.tsv.\n","eval_py":"\"\"\"Eval for difference-basis-length. Prints one JSON line: {\"metric\": record_ratio, ...}.\n\nVerification is exact: the solver returns at most k distinct integers, the eval forms every\npairwise difference itself and finds the largest n with {1, ..., n} all represented. Nothing the\nsolver reports is trusted. Environment:\n  ZT_EVAL_SEED                    seed handed to difference_basis() (the instance set is fixed)\n  ZT_EVAL_INSTANCES               comma-separated element budgets k (default \"10,11,12,13,14,15,16,17,18,19,128,360\")\n  ZT_EVAL_PER_INSTANCE_SECONDS    time budget handed to difference_basis() per instance (default 8)\n\"\"\"\n\nfrom __future__ import annotations\n\nimport ast\nimport hashlib\nimport json\nimport os\nimport sys\nimport time\nfrom pathlib import Path\n\n# Best-known covered length n for at most k elements (unrestricted difference bases).\n#   k = 10..19: J. C. P. Miller, \"Difference bases: three problems in additive number theory\" (1971),\n#               as quoted in OEIS A005488 (best-known, not proven; a(9) = 29 was only proven in 2022).\n#   k = 128:    Delta(6166) <= 128, the 128^2/6166 = 2.6571 bound of Golay, quoted from\n#               Georgiev, Gomez-Serrano, Tao, Wagner, \"Mathematical exploration and discovery at scale\"\n#               (arXiv:2511.02864), section 6.3, and Banakh-Gavrylkiv (2019).\n#   k = 360:    AlphaEvolve, repository of problems, problem 7 (world record): A = {0,1,4,6} times a\n#               Singer perfect difference set mod 8011 covers 1..49109, 360^2/49109 = 2.6390.\nRECORDS = {\"10\": 37, \"11\": 45, \"12\": 51, \"13\": 61, \"14\": 70, \"15\": 79, \"16\": 93, \"17\": 101, \"18\": 113, \"19\": 127,\n           \"128\": 6166, \"360\": 49109}\nRECORD_CONSTANT = 360 * 360 / 49109   # best-known upper bound on inf_n Delta(n)^2 / n\nSEED = os.environ.get(\"ZT_EVAL_SEED\", \"dev-seed\")\nINSTANCES = [x.strip() for x in os.environ.get(\"ZT_EVAL_INSTANCES\", \"10,11,12,13,14,15,16,17,18,19,128,360\").split(\",\") if x.strip()]\nBUDGET = float(os.environ.get(\"ZT_EVAL_PER_INSTANCE_SECONDS\", \"8\"))\nMAX_ABS = 10 ** 12\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\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 {path.name}: {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 verify(k: int, elems) -> tuple[int, int]:\n    \"\"\"Exact check. Returns (number of elements used, covered length n).\"\"\"\n    if not isinstance(elems, (list, tuple)) or not elems:\n        raise ValueError(\"difference_basis must return a non-empty list of integers\")\n    if len(elems) > k:\n        raise ValueError(f\"{len(elems)} elements returned for a budget of {k}\")\n    S = []\n    for x in elems:\n        if isinstance(x, bool) or not isinstance(x, int):\n            raise ValueError(f\"element {x!r} is not an int\")\n        if abs(x) > MAX_ABS:\n            raise ValueError(f\"element {x} exceeds |x| <= {MAX_ABS}\")\n        S.append(x)\n    if len(set(S)) != len(S):\n        raise ValueError(\"elements are not distinct\")\n    S.sort()\n    diffs = set()\n    for i in range(len(S)):\n        si = S[i]\n        for j in range(i + 1, len(S)):\n            diffs.add(S[j] - si)\n    n = 0\n    while n + 1 in diffs:\n        n += 1\n    if n == 0:\n        raise ValueError(\"the set does not represent 1 as a difference\")\n    return len(S), n\n\n\ndef main() -> None:\n    here = Path(__file__).parent\n    check_imports(here / \"basis.py\")\n    sys.path.insert(0, str(here))\n    try:\n        import basis as mod  # noqa: E402\n    except SystemExit:\n        raise\n    except Exception as e:\n        fail(f\"import basis.py failed: {e!r}\", \"compile_error\")\n    if not hasattr(mod, \"difference_basis\"):\n        fail(\"basis.py must define difference_basis(k, time_budget, seed)\", \"compile_error\")\n    for lab in INSTANCES:\n        if lab not in RECORDS:\n            fail(f\"unknown instance {lab}; known: {list(RECORDS)}\", \"compile_error\")\n    seed = int(hashlib.sha256(SEED.encode()).hexdigest()[:8], 16)\n    per, ratios, beaten = {}, [], []\n    best_constant = None\n    t_start = time.time()\n    for lab in INSTANCES:\n        k = int(lab)\n        t0 = time.time()\n        try:\n            elems = mod.difference_basis(k, BUDGET, seed)\n        except SystemExit:\n            raise\n        except Exception as e:\n            fail(f\"difference_basis({k}) raised {e!r}\", \"runtime_error\")\n        elapsed = time.time() - t0\n        if elapsed > BUDGET * 1.25 + 3.0:\n            fail(f\"difference_basis({k}) took {elapsed:.1f}s for a {BUDGET:.1f}s budget\", \"timeout\")\n        try:\n            used, n = verify(k, elems)\n        except ValueError as e:\n            fail(f\"difference_basis({k}): {e}\", \"wrong_answer\")\n        ratio = n / RECORDS[lab]\n        ratios.append(ratio)\n        c = used * used / n\n        best_constant = c if best_constant is None else min(best_constant, c)\n        per[lab] = {\"n\": n, \"elements\": used, \"record\": RECORDS[lab], \"k2_over_n\": round(c, 6),\n                    \"ratio\": round(ratio, 6), \"seconds\": round(elapsed, 2)}\n        if n > RECORDS[lab]:\n            beaten.append(lab)\n        print(f\"k={k}: covers 1..{n} with {used} elements (record {RECORDS[lab]}), ratio {ratio:.4f}, {elapsed:.1f}s\", flush=True)\n    metric = sum(ratios) / len(ratios)\n    print(json.dumps({\"metric\": round(metric, 6), \"instances\": INSTANCES, \"per_instance\": per,\n                      \"records_beaten\": beaten, \"best_k2_over_n\": round(best_constant, 6),\n                      \"constant_beaten\": bool(best_constant < RECORD_CONSTANT - 1e-12),\n                      \"seconds\": round(time.time() - t_start, 1)}))\n\n\nif __name__ == \"__main__\":\n    main()\n","baseline":{"basis.py":"\"\"\"Baseline: Leech's construction {0,1,4,6} x (Singer perfect difference set mod q^2+q+1) when four\ncopies fit in the budget, then greedy extension; plain randomised greedy for small k.\nReaches roughly 0.75 of the small records and 0.97-0.98 of the two large ones. Beat it.\"\"\"\n\nimport random\n\n\ndef difference_basis(k: int, time_budget: float, seed: int) -> list[int]:\n    rng = random.Random(seed)\n    best = []\n    q = max((p for p in range(2, k) if 4 * (p + 1) <= k and is_prime(p)), default=None)\n    if q is not None:\n        D, m = singer(q)\n        if D:\n            best = extend(sorted({a * m + b for a in (0, 1, 4, 6) for b in D}), k, rng)\n    if k <= 40:\n        for _ in range(200):\n            cand = extend([0], k, rng)\n            if covered(cand) > covered(best):\n                best = cand\n    return best\n\n\ndef covered(S: list[int]) -> int:\n    diffs = {abs(a - b) for a in S for b in S}\n    n = 0\n    while n + 1 in diffs:\n        n += 1\n    return n\n\n\ndef extend(S: list[int], k: int, rng: random.Random) -> list[int]:\n    \"\"\"Add elements one at a time, each chosen (from those that represent the first missing\n    distance) to push the covered prefix furthest; ties broken at random.\"\"\"\n    S = list(S)\n    diffs = {abs(a - b) for a in S for b in S}\n    while len(S) < k:\n        p = 0\n        while p + 1 in diffs:\n            p += 1\n        cands = list({s + p + 1 for s in S} | {s - p - 1 for s in S})\n        rng.shuffle(cands)\n        best_x, best_p = None, -1\n        for x in cands:\n            if x in S:\n                continue\n            new = {abs(x - s) for s in S}\n            r = p + 1\n            while r + 1 in diffs or r + 1 in new:\n                r += 1\n            if r > best_p:\n                best_x, best_p = x, r\n        S.append(best_x)\n        diffs |= {abs(best_x - s) for s in S}\n    return sorted(S)\n\n\ndef is_prime(p: int) -> bool:\n    return p > 1 and all(p % d for d in range(2, int(p ** 0.5) + 1))\n\n\ndef singer(q: int) -> tuple[list[int], int]:\n    \"\"\"Singer perfect difference set: {i : x^i has no x^2 term} in GF(q)[x]/(cubic), a (q+1)-set\n    whose differences hit every nonzero residue mod m = q^2 + q + 1 exactly once.\"\"\"\n    m = q * q + q + 1\n    for a in range(q):\n        for b in range(q):\n            for c in range(1, q):\n                if any((x ** 3 - a * x * x - b * x - c) % q == 0 for x in range(q)):\n                    continue  # reducible cubic\n                v, D = (1, 0, 0), []\n                for i in range(m):\n                    if v[2] == 0:\n                        D.append(i)\n                    v = ((v[2] * c) % q, (v[0] + v[2] * b) % q, (v[1] + v[2] * a) % q)\n                if len(D) == q + 1:\n                    return D, m\n    return [], m\n"}}