Sum-difference exponent II (more differences than sums)

# Sum-difference exponent II: more differences than sums ## Goal `construct.py` exposes `construct(max_size: int, time_budget: float, seed: int) -> list[int]`: a list of **distinct integers** `A` with `2 <= len(A) <= max_size`. Maximise C(A) = log|A-A| / log|A+A| where `A+A = {a+b : a, b in A}` and `A-A = {a-b : a, b in A}`. This is problem 43 of the AlphaEvolve repository of problems ("Sum-difference problem II", section 6.25 of *Mathematical Exploration and Discovery at Scale*, arXiv:2511.02864): let `C` be the least constant with `|A-A| <= |A+A|^C` for every finite `A ⊂ Z`; every explicit set is a lower bound for `C`. Freiman-Pigarev / Ruzsa give `C <= 4/3`. ## Instances | label | constraint | best-known lower bound | construction | source | status | |---|---|---|---|---|---| | `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 | Because the record is a limit, ratio 1.0 is not reachable by copying the known construction: the finite simplices give 1.1475 (`d = 4`), 1.1924 (`d = 8`), 1.2036 (`d = 10`, 3003 elements) and converge slowly. A single finite set scoring above 1.2715533 is a new lower bound for `C` and the `records_beaten` flag. Anything above about 1.21 already beats what AlphaEvolve found. ## Metric metric = C(A) / 1.2715533 The eval recomputes `|A+A|` and `|A-A|` exactly from the list you return; nothing you print or report is used. Invalid answers (duplicates, non-ints, too many elements) fail the run. `ZT_EVAL_SEED` only changes the `seed` handed to your solver. ## Verification limits Exact counting in pure Python has to finish in well under a minute, so: - `len(A) <= 20000`, every `|a| <= 2^62`; - if `max(A) - min(A) > 2^27`, then `len(A) <= 4000`. The eval counts with shifted bit masks when the set is dense (`span < 213 * len(A)`), a pair loop into byte arrays otherwise, and plain sets for sets wider than `2^27`. The baseline's 3003-element simplex verifies in about 1 s; the worst allowed cases (20 000 sparse elements, or 4000 elements wider than `2^27`) take 10-60 s. Base-`b` embeddings of `d`-dimensional sets have span `b^d`, so high-dimensional constructions hit the 4000-element rule: the baseline's `d = 10, m = 5` simplex (base 11, span `11^10`) is the largest simplex that fits. Fitting a bigger simplex means finding a Freiman-isomorphic embedding into `[0, 2^27]`. ## Constraints - Standard library only. No numpy. The eval rejects other imports. - Respect `time_budget` (seconds, per call). Deterministic given `seed`: use `random.Random(seed)`. ## Iteration tips - `ZT_EVAL_PER_INSTANCE_SECONDS=5` shortens the solver budget for quick runs; `ZT_EVAL_INSTANCES` accepts the single label `open`. With the default 60 s budget a solver that searches for the whole budget makes the full eval take about 60 s plus verification; the baseline returns its simplex instantly, so its eval takes about 1.5 s. - Product sets multiply: `|(A x B) + (A x B)| = |A+A| |B+B|` and likewise for differences, so `C(A x B)` is a weighted mean of `C(A)` and `C(B)`; a base-`b` embedding with `b` larger than the coordinate ranges of `A+A` and `A-A` makes this exact in `Z`. Any small set with a high exponent is therefore also a building block, but products never exceed their best factor. - The simplex wins because its difference set (`sum of positive parts <= m` and `sum of negative parts <= m`) is far bigger than its sumset (`sum <= 2m`). Truncated, perturbed or unioned simplices, and sets whose "shape" is a different convex body, are the natural search space. - Score evaluation is `O(|A|^2)`: keep working sets small while searching, and only expand (product, dilation-union) at the end. Write one honest line in `NOTES.md`: the idea, and what it changed. Simpler is better: all else equal prefer the shorter solver, and treat removing code for an equal score as a win. Log every experiment, including discards, in your results.tsv.