Difference bases: longest interval from k integers

# Difference bases: longest interval from k integers ## Goal A **difference basis** for `{1, ..., n}` is a set `B` of integers such that every `1 ≤ d ≤ n` is `b - b'` for some `b, b' ∈ B`. The elements are *unrestricted*: they may lie anywhere (this is the variant of AlphaEvolve repository problem 7; the restricted variant, marks confined to `[0, n]`, is the `sparse-ruler-marks` pack). Let `Δ(n)` be the smallest possible `|B|`. Rédei–Rényi and Leech showed `Δ(n)² / n` converges to a constant `C`, with 2.434... ≤ C ≤ 128² / 6166 = 2.6571... (Leech 1956; Golay 1972) until AlphaEvolve found 360 integers covering `1..49109`, i.e. `C ≤ 2.6390` (Georgiev, Gómez-Serrano, Tao, Wagner, *Mathematical exploration and discovery at scale*, 2025, §6.3). This pack turns the problem around per size: for each element budget `k`, cover the longest possible interval. `basis.py` exposes difference_basis(k: int, time_budget: float, seed: int) -> list[int] returning **at most k** distinct integers (`|x| ≤ 10^12`, any order). The eval forms every pairwise difference itself and takes the largest `n` such that all of `1..n` appear. Nothing you report is trusted; a set that does not even represent 1 fails the submission. ## Metric The eval runs `difference_basis` on the fixed budget set below, each with the given time budget (8 s by default), verifies the set, and reports metric = mean over k of n(k) / record_n(k) so 1.0 means matching every best-known length and anything above 1.0 on a `k` is a new record. Per-instance detail (`n`, elements used, `k2_over_n = |B|²/n`, ratio, seconds) is in `per_instance`; `records_beaten` lists any `k` you beat, and `constant_beaten` is true when any returned set has `|B|²/n < 360²/49109`, which improves the AlphaEvolve bound on `C` even if it does not beat the record of its own `k`. `ZT_EVAL_SEED` only changes the `seed` handed to your solver. ## Records | k | best-known n | |B|²/n | source | proven | |---|---|---|---|---| | 10 | 37 | 2.703 | Miller (1971), quoted in OEIS A005488 | no | | 11 | 45 | 2.689 | Miller (1971), OEIS A005488 | no | | 12 | 51 | 2.824 | Miller (1971), OEIS A005488 | no | | 13 | 61 | 2.770 | Miller (1971), OEIS A005488 | no | | 14 | 70 | 2.800 | Miller (1971), OEIS A005488 | no | | 15 | 79 | 2.848 | Miller (1971), OEIS A005488 | no | | 16 | 93 | 2.753 | Miller (1971), OEIS A005488 | no | | 17 | 101 | 2.861 | Miller (1971), OEIS A005488 | no | | 18 | 113 | 2.867 | Miller (1971), OEIS A005488 | no | | 19 | 127 | 2.843 | Miller (1971), OEIS A005488 | no | | 128 | 6166 | 2.6571 | Golay's bound `Δ(6166) ≤ 128`, quoted in Georgiev et al. (2025) §6.3 and Banakh–Gavrylkiv (2019) | no | | 360 | 49109 | 2.6390 | AlphaEvolve, repository of problems, problem 7 (world record; construction re-verified for this pack) | no | OEIS A005488 lists Miller's values as lower bounds on the maximal length (Bermond 1978 quotes them as exact); the entry for k = 9 (n = 29) was only proven optimal in 2022, so k = 10 onward is open. For comparison, the best restricted rulers (OEIS A004137) reach 36, 43, 50, 58, 68, 79, 90, 101, 112, 123 for k = 10..19, and Wichmann rulers give only `≈ 3` for `|B|²/n` at large k, so the large instances are where algebra beats combinatorial search. If you beat one, the set is the evidence: it is in the eval log. Say so in your notes so the hub can update the table and forward the set. ## Iterating - Start on one or two budgets: `ZT_EVAL_INSTANCES=10,11 ZT_EVAL_PER_INSTANCE_SECONDS=2 python eval.py` runs in seconds; `ZT_EVAL_INSTANCES=360` exercises the large construction alone. The full set takes about 96 s of solver time plus verification (which is instant: at most C(360, 2) differences). - Respect `time_budget` (seconds, per call). The eval kills the run if a call overruns it by more than 25% + 3 s. Be deterministic given `seed`: use `random.Random(seed)`. - Only the standard library is available (`math, random, itertools, functools, collections, heapq, time`). - Leech's construction: if `A` is a difference basis for `{1..a}` and `D` is a perfect difference set mod `m` (every nonzero residue is a difference of two elements of `D` exactly once; Singer sets give `|D| = q + 1`, `m = q² + q + 1` for prime powers `q`), then `{x·m + d : x ∈ A, d ∈ D}` has `|A|·|D|` elements and covers roughly `(a - 1)·m`. AlphaEvolve's record is exactly this with `A = {0, 1, 4, 6}` and `q = 89`, but *which* Singer set (translate and multiplier equivalents cover different prefixes: the baseline's naive choice reaches 48160, AlphaEvolve's 49109) and what `A` is used matter. Try other `A`, other `q`, Singer sets from prime powers (needs GF(q³) arithmetic over a prime-power field), and post-hoc repair by moving a few elements. - For small `k` the problem is combinatorial: branch-and-bound or simulated annealing over element positions, seeded with Miller-style patterns, is the tool. Even a one-step improvement on any k = 10..19 is a new entry for OEIS. Write one honest line in `NOTES.md`: the idea, and which `k` it helped. Simpler is better: all else equal prefer the shorter solver. Log every experiment, including discards, in your results.tsv.