{"id":"sum-difference-exponent-i","name":"Sum-difference exponent I (more sums than differences)","family":"additive-combinatorics","description":"AlphaEvolve repository problem 42: find a finite set A of integers maximising log(|A+A|/|A|) / log(|A-A|/|A|), the exponent C in |A+A|/|A| <= (|A-A|/|A|)^C. Scored against the best-known sets: Conway's 8-element MSTD set (proven optimal for |A| <= 8) and AlphaEvolve's 309-element set (1.12194, open).","metric":"record_ratio","direction":"maximize","tolerance":0.02,"eval_timeout_seconds":300,"agent_timeout_seconds":1800,"mutable":["construct.py"],"runtime":"python>=3.11, standard library only (math, random, itertools, functools, collections, heapq, time)","decomposable":false,"status":"active","captain":null,"parent_problem":null,"program_md":"# Sum-difference exponent I: more sums than differences\n\n## Goal\n\n`construct.py` exposes `construct(max_size: int, time_budget: float, seed: int) -> list[int]`:\na list of **distinct integers** `A` with `2 <= len(A) <= max_size`. Maximise\n\n    C(A) = log(|A+A| / |A|) / log(|A-A| / |A|)\n\nwhere `A+A = {a+b : a, b in A}` and `A-A = {a-b : a, b in A}`. This is problem 42 of the\nAlphaEvolve repository of problems (\"Sum-difference problem I\", section 6.25 of *Mathematical\nExploration and Discovery at Scale*, arXiv:2511.02864): let `C` be the least constant with\n`|A+A|/|A| <= (|A-A|/|A|)^C` for every finite `A ⊂ Z`; every explicit set is a lower bound for `C`.\nSets with `|A+A| > |A-A|` (MSTD sets, \"more sums than differences\") are exactly the sets scoring\nabove 1. The Plünnecke-Ruzsa inequality gives `C <= 2`; the true value is open.\n\n## Instances\n\n| label | constraint | best-known `C(A)` | set | source | status |\n|---|---|---|---|---|---|\n| `n8` | `len(A) <= 8` | 1.0344183 | `{0,2,3,4,7,11,12,14}`, `|A+A| = 26`, `|A-A| = 25` | Conway's set; Hegarty, *Some explicit constructions of sets with more sums than differences*, Acta Arith. 130 (2007): no MSTD set has fewer than 8 elements and this is the only one of size 8 up to affine maps | proven optimal (a non-MSTD set scores at most 1) |\n| `open` | `len(A) <= 20000` | 1.1219357 | AlphaEvolve's 309-element set, `|A+A| = 1367`, `|A-A| = 1163` | AlphaEvolve repository problem 42, notebook `sums_differences_problems.ipynb` (listed as a world record in the repository's `status.json`) | open |\n\nThe `n8` record is an exact anchor: a solver returning Conway's set scores ratio 1.0 there. The\n`open` record was found by a mutation search in 1000 s, so it is a soft target: beat 1.1219357 and\nyou have a record candidate for problem 42.\n\n## Metric\n\n    metric = mean over instances of  C(A_instance) / record_instance\n\n`records_beaten` lists the instances where you exceed the record. The eval recomputes `|A+A|` and\n`|A-A|` exactly from the list you return; nothing you print or report is used. Invalid answers\n(duplicates, non-ints, too many elements) fail the whole run. `ZT_EVAL_SEED` only changes the `seed`\nhanded to your solver.\n\n## Verification limits\n\nExact counting in pure Python has to finish in well under a minute per instance, so:\n\n- `len(A) <= max_size` (`20000` on `open`), every `|a| <= 2^62`;\n- if `max(A) - min(A) > 2^27`, then `len(A) <= 4000`.\n\nThe eval counts with shifted bit masks when the set is dense (`span < 213 * len(A)`), a pair loop\ninto byte arrays otherwise, and plain sets for sets wider than `2^27`. A 309-element set verifies\nin milliseconds; the worst allowed case (20 000 sparse elements) takes 30-60 s.\n\n## Constraints\n\n- Standard library only. No numpy. The eval rejects other imports.\n- Respect `time_budget` (seconds, per call). Deterministic given `seed`: use `random.Random(seed)`.\n\n## Iteration tips\n\n- `ZT_EVAL_INSTANCES=open` restricts the eval to one instance; `ZT_EVAL_PER_INSTANCE_SECONDS=5`\n  shortens the solver budget. With defaults (`n8,open`, 40 s each) a solver that uses its whole\n  budget on `open` makes the full eval take about 40 s plus verification (the baseline returns\n  Conway's set instantly on `n8`).\n- AlphaEvolve's winning search kept a current set and applied mutations: nudge one element, add an\n  element, remove one, splice in a short arithmetic or geometric progression; accept if the score\n  does not drop. Its record set has 309 elements in `[-434, 386]`, i.e. it is dense (about 38% of\n  the interval), with a small far-away cluster.\n- Classical MSTD constructions (Hegarty; Nathanson; Martin-O'Bryant) glue a symmetric middle to\n  asymmetric \"fringes\" that kill a few differences while filling in sums. Product-like\n  constructions (`A x B` embedded in `Z` with a large base) do **not** help this normalised\n  exponent: `C(A x B)` is a weighted mean of `C(A)` and `C(B)`.\n- Score evaluation is `O(|A|^2)`: keep working sets small and evaluate many candidates, or maintain\n  sum/difference multiplicity counters and update them incrementally on single-element moves.\n\nWrite one honest line in `NOTES.md`: the idea, and which instance 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 sum-difference-exponent-i. Prints one JSON line: {\"metric\": record_ratio, ...}.\n\nThe solver returns a set A of integers. This eval recomputes |A+A| and |A-A| exactly from that\nset (never from anything the solver reports) and scores  log(|A+A|/|A|) / log(|A-A|/|A|).\n\nEnv:\n  ZT_EVAL_SEED                   seed handed to construct()\n  ZT_EVAL_PER_INSTANCE_SECONDS   time budget per instance (default 40)\n  ZT_EVAL_INSTANCES              comma-separated instance labels (default \"n8,open\")\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\"))\nLABELS = [s.strip() for s in os.environ.get(\"ZT_EVAL_INSTANCES\", \"n8,open\").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\"}\n\n# Verification limits (exact counting in pure Python must finish in about 30 s per instance):\n#   |A| <= MAX_SIZE, and if max(A) - min(A) > WIDE_SPAN then |A| <= MAX_SIZE_WIDE.\nMAX_SIZE = 20000\nMAX_SIZE_WIDE = 4000\nWIDE_SPAN = 1 << 27\nMAX_ABS = 1 << 62\n\n\ndef exponent(sums: int, diffs: int, n: int) -> float:\n    \"\"\"C with |A+A|/|A| = (|A-A|/|A|)^C. Well defined: |A-A| >= 2|A|-1 > |A| for |A| >= 2.\"\"\"\n    return math.log(sums / n) / math.log(diffs / n)\n\n\n# Best-known values, each pinned to a set whose |A+A| and |A-A| this eval reproduces.\n#   n8:   Conway's set {0,2,3,4,7,11,12,14}: |A+A| = 26, |A-A| = 25. Hegarty (2007) proved there is\n#         no MSTD set with fewer than 8 elements and that this is the only one of size 8 up to affine\n#         maps, so it is optimal for |A| <= 8 (every non-MSTD set scores <= 1).\n#   open: AlphaEvolve repository problem 42 (world record), the 309-element set in the notebook\n#         sums_differences_problems.ipynb: |A+A| = 1367, |A-A| = 1163, exponent 1.1219357.\nINSTANCES = {\n    \"n8\": {\"max_size\": 8, \"record\": exponent(26, 25, 8), \"proven\": True},\n    \"open\": {\"max_size\": MAX_SIZE, \"record\": exponent(1367, 1163, 309), \"proven\": False},\n}\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 validate(obj: object, label: str, max_size: int) -> list[int]:\n    \"\"\"Return the set as a sorted list shifted so min is 0 (sizes of A+A and A-A are affine invariants).\"\"\"\n    if not isinstance(obj, (list, tuple)):\n        fail(f\"construct({label}) must return a list of ints, got {type(obj).__name__}\", \"wrong_answer\")\n    vals = []\n    for x in obj:\n        if type(x) is not int:  # bool and floats are not integers here\n            fail(f\"construct({label}) returned a non-int element {x!r}\", \"wrong_answer\")\n        if abs(x) > MAX_ABS:\n            fail(f\"construct({label}) returned an element with |x| > 2^62\", \"wrong_answer\")\n        vals.append(x)\n    n = len(vals)\n    if n < 2:\n        fail(f\"construct({label}) must return at least 2 elements\", \"wrong_answer\")\n    if len(set(vals)) != n:\n        fail(f\"construct({label}) returned duplicate elements\", \"wrong_answer\")\n    if n > max_size:\n        fail(f\"construct({label}) returned {n} elements; this instance allows at most {max_size}\", \"wrong_answer\")\n    a = sorted(vals)\n    lo = a[0]\n    a = [x - lo for x in a]\n    if a[-1] > WIDE_SPAN and n > MAX_SIZE_WIDE:\n        fail(f\"construct({label}): sets spanning more than 2^27 may have at most {MAX_SIZE_WIDE} elements\", \"wrong_answer\")\n    return a\n\n\ndef count_sums_and_diffs(a: list[int]) -> tuple[int, int]:\n    \"\"\"Exact |A+A| and |A-A| for a sorted list with a[0] == 0. Three exact routes, chosen by cost.\"\"\"\n    n, span = len(a), a[-1]\n    if span > WIDE_SPAN:  # wide and small: plain sets\n        sums, diffs = set(), set()\n        for x in a:\n            sums.update([x + y for y in a])\n            diffs.update([x - y for y in a])\n        return len(sums), len(diffs)\n    if span < 213 * n:  # dense: OR shifted copies of the bit mask (cost ~ n * span / 8 bytes)\n        bits = bytearray(span // 8 + 1)\n        for x in a:\n            bits[x >> 3] |= 1 << (x & 7)\n        mask = int.from_bytes(bits, \"little\")\n        plus = minus = 0\n        for x in a:\n            plus |= mask << x\n            minus |= mask << (span - x)\n        return plus.bit_count(), minus.bit_count()\n    plus, minus = bytearray(2 * span + 1), bytearray(2 * span + 1)  # sparse: pair loop (cost ~ n^2)\n    for x in a:\n        for y in a:\n            plus[x + y] = 1\n            minus[x - y + span] = 1\n    return sum(plus), sum(minus)\n\n\ndef main() -> None:\n    here = Path(__file__).parent\n    check_imports(here / \"construct.py\")\n    sys.path.insert(0, str(here))\n    try:\n        import construct as cand  # noqa: E402\n    except SystemExit:\n        raise\n    except Exception as e:\n        fail(f\"import construct.py failed: {e!r}\", \"compile_error\")\n    if not hasattr(cand, \"construct\"):\n        fail(\"construct.py must define construct(max_size, time_budget, seed)\", \"compile_error\")\n\n    seed_int = random.Random(f\"sumdiff1|{SEED}\").getrandbits(32)\n    per_instance, beaten = {}, []\n    for label in LABELS:\n        if label not in INSTANCES:\n            fail(f\"unknown instance {label!r} (known: {sorted(INSTANCES)})\", \"error\")\n        inst = INSTANCES[label]\n        t0 = time.perf_counter()\n        try:\n            result = cand.construct(inst[\"max_size\"], BUDGET, seed_int)\n        except SystemExit:\n            raise\n        except Exception as e:\n            fail(f\"construct({label}) raised {e!r}\", \"runtime_error\")\n        elapsed = time.perf_counter() - t0\n        if elapsed > 1.25 * BUDGET + 3:\n            fail(f\"construct({label}) took {elapsed:.1f}s against a {BUDGET:.0f}s budget\", \"timeout\")\n        a = validate(result, label, inst[\"max_size\"])\n        sums, diffs = count_sums_and_diffs(a)\n        value = exponent(sums, diffs, len(a))\n        per_instance[label] = {\n            \"size\": len(a), \"span\": a[-1], \"sum_set\": sums, \"diff_set\": diffs,\n            \"value\": round(value, 10), \"record\": round(inst[\"record\"], 10),\n            \"ratio\": round(value / inst[\"record\"], 6), \"seconds\": round(elapsed, 2),\n        }\n        if value > inst[\"record\"] + 1e-12:\n            beaten.append(label)\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":{"construct.py":"\"\"\"Baseline: Conway's set on n8; on open, anneal membership flips of a subset of [0, 30].\n\nScores 1.0 on n8 and about 1.05 (ratio 0.94) on open; the record set has 309 elements. Beat it.\n\"\"\"\n\nimport math\nimport random\nimport time\n\nCONWAY = [0, 2, 3, 4, 7, 11, 12, 14]  # |A+A| = 26 > |A-A| = 25, the smallest MSTD set\n\n\ndef exponent(mask: int, n: int, span: int) -> float:\n    \"\"\"log(|A+A|/n) / log(|A-A|/n) for the set whose bit mask is `mask` (bit i set <=> i in A).\"\"\"\n    plus = minus = 0\n    rest = mask\n    while rest:\n        low = rest & -rest\n        x = low.bit_length() - 1\n        rest ^= low\n        plus |= mask << x\n        minus |= mask << (span - x)\n    return math.log(plus.bit_count() / n) / math.log(minus.bit_count() / n)\n\n\ndef construct(max_size: int, time_budget: float, seed: int) -> list[int]:\n    if max_size <= 8:\n        return CONWAY[:max_size]\n    rng = random.Random(seed)\n    span = min(30, max_size - 1)\n    mask = 1 | (1 << span)\n    for i in range(1, span):\n        if rng.random() < 0.5:\n            mask |= 1 << i\n    n = mask.bit_count()\n    cur = exponent(mask, n, span)\n    best_score, best_mask = cur, mask\n    t0 = time.perf_counter()\n    horizon = 0.9 * time_budget\n    while True:\n        elapsed = time.perf_counter() - t0\n        if elapsed >= horizon:\n            break\n        temp = 0.01 * (1 - elapsed / horizon)\n        cand = mask ^ (1 << rng.randint(1, span - 1))\n        m = cand.bit_count()\n        if m < 3 or m > max_size:\n            continue\n        score = exponent(cand, m, span)\n        if score >= cur or rng.random() < math.exp((score - cur) / max(temp, 1e-9)):\n            mask, n, cur = cand, m, score\n            if score > best_score:\n                best_score, best_mask = score, cand\n    return [i for i in range(span + 1) if best_mask >> i & 1]\n"}}