{"id":"sum-difference-exponent-ii","name":"Sum-difference exponent II (more differences than sums)","family":"additive-combinatorics","description":"AlphaEvolve repository problem 43: find a finite set A of integers maximising log|A-A| / log|A+A|, the exponent C in |A-A| <= |A+A|^C. Scored against the best-known lower bound log(1+sqrt2)/log 2 = 1.27155 (Hennecart-Robert-Yudin simplex construction, a limit value no finite set is known to reach; AlphaEvolve got about 1.21).","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 II: more differences than sums\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| / log|A+A|\n\nwhere `A+A = {a+b : a, b in A}` and `A-A = {a-b : a, b in A}`. This is problem 43 of the\nAlphaEvolve repository of problems (\"Sum-difference problem II\", 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|^C` for every finite `A ⊂ Z`; every explicit set is a lower bound for `C`.\nFreiman-Pigarev / Ruzsa give `C <= 4/3`.\n\n## Instances\n\n| label | constraint | best-known lower bound | construction | source | status |\n|---|---|---|---|---|---|\n| `open` | `len(A) <= 20000` | `log(1+sqrt 2)/log 2 = 1.2715533` | simplex `{x in Z_+^d : sum x_i <= d/2}`, as `d -> infinity` | Hennecart, Robert, Yudin, *On the number of sums and differences*, Astérisque 258 (1999); quoted as the best known bound in the AlphaEvolve repository notebook `sum_difference_problem_ii.ipynb` (problem 43 is listed as \"worse than record\" in `status.json`: AlphaEvolve reached about 1.21 on its own) | open; the record is a limit value that no finite set is known to attain |\n\nBecause the record is a limit, ratio 1.0 is not reachable by copying the known construction: the\nfinite simplices give 1.1475 (`d = 4`), 1.1924 (`d = 8`), 1.2036 (`d = 10`, 3003 elements) and\nconverge slowly. A single finite set scoring above 1.2715533 is a new lower bound for `C` and the\n`records_beaten` flag. Anything above about 1.21 already beats what AlphaEvolve found.\n\n## Metric\n\n    metric = C(A) / 1.2715533\n\nThe eval recomputes `|A+A|` and `|A-A|` exactly from the list you return; nothing you print or\nreport is used. Invalid answers (duplicates, non-ints, too many elements) fail the run.\n`ZT_EVAL_SEED` only changes the `seed` handed to your solver.\n\n## Verification limits\n\nExact counting in pure Python has to finish in well under a minute, so:\n\n- `len(A) <= 20000`, 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`. The baseline's 3003-element\nsimplex verifies in about 1 s; the worst allowed cases (20 000 sparse elements, or 4000 elements\nwider than `2^27`) take 10-60 s. Base-`b` embeddings of\n`d`-dimensional sets have span `b^d`, so high-dimensional constructions hit the 4000-element rule:\nthe baseline's `d = 10, m = 5` simplex (base 11, span `11^10`) is the largest simplex that fits.\nFitting a bigger simplex means finding a Freiman-isomorphic embedding into `[0, 2^27]`.\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_PER_INSTANCE_SECONDS=5` shortens the solver budget for quick runs; `ZT_EVAL_INSTANCES`\n  accepts the single label `open`. With the default 60 s budget a solver that searches for the\n  whole budget makes the full eval take about 60 s plus verification; the baseline returns its\n  simplex instantly, so its eval takes about 1.5 s.\n- Product sets multiply: `|(A x B) + (A x B)| = |A+A| |B+B|` and likewise for differences, so\n  `C(A x B)` is a weighted mean of `C(A)` and `C(B)`; a base-`b` embedding with `b` larger than\n  the coordinate ranges of `A+A` and `A-A` makes this exact in `Z`. Any small set with a high\n  exponent is therefore also a building block, but products never exceed their best factor.\n- The simplex wins because its difference set (`sum of positive parts <= m` and `sum of negative\n  parts <= m`) is far bigger than its sumset (`sum <= 2m`). Truncated, perturbed or unioned\n  simplices, and sets whose \"shape\" is a different convex body, are the natural search space.\n- Score evaluation is `O(|A|^2)`: keep working sets small while searching, and only expand\n  (product, dilation-union) at the end.\n\nWrite one honest line in `NOTES.md`: the idea, and what it changed.\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-ii. 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| / log|A+A|.\n\nEnv:\n  ZT_EVAL_SEED                   seed handed to construct()\n  ZT_EVAL_PER_INSTANCE_SECONDS   time budget per instance (default 60)\n  ZT_EVAL_INSTANCES              comma-separated instance labels (default \"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\", \"60\"))\nLABELS = [s.strip() for s in os.environ.get(\"ZT_EVAL_INSTANCES\", \"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) -> float:\n    \"\"\"C with |A-A| = |A+A|^C. Well defined: |A+A| >= 2|A|-1 >= 3 for |A| >= 2.\"\"\"\n    return math.log(diffs) / math.log(sums)\n\n\n# Best-known lower bound for problem 43: log(1+sqrt(2))/log(2) = 1.2715533, the limit of the\n# Hennecart-Robert-Yudin simplex construction {x in Z_+^d : sum x_i <= d/2} as d -> infinity\n# (Astérisque 258, 1999; quoted as the best known bound in the AlphaEvolve repository notebook\n# sum_difference_problem_ii.ipynb, which reports AlphaEvolve reaching only about 1.21).\n# No finite set is known to reach it; a single set scoring above it is a new record.\nINSTANCES = {\n    \"open\": {\"max_size\": MAX_SIZE, \"record\": math.log(1 + math.sqrt(2)) / math.log(2), \"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\"sumdiff2|{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)\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: the Hennecart-Robert-Yudin simplex {x in Z_+^d : sum x_i <= m}, written in base 2m+1.\n\nd = 10, m = 5 gives 3003 elements with log|A-A| / log|A+A| = 1.2036, about 0.947 of the record. Beat it.\n\"\"\"\n\nimport math\n\n# (d, m) shapes in decreasing size; every one has at most 4000 elements so the wide-span rule allows it.\nSHAPES = [(10, 5), (9, 4), (8, 4), (7, 3), (6, 3), (5, 2), (4, 2), (3, 1), (2, 1)]\n\n\ndef simplex_points(d: int, m: int) -> list[tuple[int, ...]]:\n    out: list[tuple[int, ...]] = []\n\n    def rec(prefix: list[int], remaining: int) -> None:\n        if len(prefix) == d:\n            out.append(tuple(prefix))\n            return\n        for v in range(remaining + 1):\n            rec(prefix + [v], remaining - v)\n\n    rec([], m)\n    return out\n\n\ndef construct(max_size: int, time_budget: float, seed: int) -> list[int]:\n    for d, m in SHAPES:\n        if math.comb(d + m, d) <= max_size:\n            break\n    base = 2 * m + 1  # coordinates of A+A lie in [0, 2m] and of A-A in [-m, m]: base 2m+1 keeps them apart\n    return [sum(c * base ** i for i, c in enumerate(p)) for p in simplex_points(d, m)]\n"}}