Sum-difference exponent I (more sums than differences)

# Sum-difference exponent I: more sums than differences ## 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| / |A|) / log(|A-A| / |A|) where `A+A = {a+b : a, b in A}` and `A-A = {a-b : a, b in A}`. This is problem 42 of the AlphaEvolve repository of problems ("Sum-difference problem I", section 6.25 of *Mathematical Exploration and Discovery at Scale*, arXiv:2511.02864): let `C` be the least constant with `|A+A|/|A| <= (|A-A|/|A|)^C` for every finite `A ⊂ Z`; every explicit set is a lower bound for `C`. Sets with `|A+A| > |A-A|` (MSTD sets, "more sums than differences") are exactly the sets scoring above 1. The Plünnecke-Ruzsa inequality gives `C <= 2`; the true value is open. ## Instances | label | constraint | best-known `C(A)` | set | source | status | |---|---|---|---|---|---| | `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) | | `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 | The `n8` record is an exact anchor: a solver returning Conway's set scores ratio 1.0 there. The `open` record was found by a mutation search in 1000 s, so it is a soft target: beat 1.1219357 and you have a record candidate for problem 42. ## Metric metric = mean over instances of C(A_instance) / record_instance `records_beaten` lists the instances where you exceed the record. 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 whole 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 per instance, so: - `len(A) <= max_size` (`20000` on `open`), 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`. A 309-element set verifies in milliseconds; the worst allowed case (20 000 sparse elements) takes 30-60 s. ## 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_INSTANCES=open` restricts the eval to one instance; `ZT_EVAL_PER_INSTANCE_SECONDS=5` shortens the solver budget. With defaults (`n8,open`, 40 s each) a solver that uses its whole budget on `open` makes the full eval take about 40 s plus verification (the baseline returns Conway's set instantly on `n8`). - AlphaEvolve's winning search kept a current set and applied mutations: nudge one element, add an element, remove one, splice in a short arithmetic or geometric progression; accept if the score does not drop. Its record set has 309 elements in `[-434, 386]`, i.e. it is dense (about 38% of the interval), with a small far-away cluster. - Classical MSTD constructions (Hegarty; Nathanson; Martin-O'Bryant) glue a symmetric middle to asymmetric "fringes" that kill a few differences while filling in sums. Product-like constructions (`A x B` embedded in `Z` with a large base) do **not** help this normalised exponent: `C(A x B)` is a weighted mean of `C(A)` and `C(B)`. - Score evaluation is `O(|A|^2)`: keep working sets small and evaluate many candidates, or maintain sum/difference multiplicity counters and update them incrementally on single-element moves. Write one honest line in `NOTES.md`: the idea, and which instance it helped. 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.