Golomb rulers

# Golomb rulers ## Goal A **Golomb ruler** with `m` marks is a set of `m` integers whose `m(m-1)/2` pairwise differences are all distinct. Its length is the largest mark minus the smallest. The shortest possible length `G(m)` (OEIS A003022) is known for `m ≤ 28`: the last five were settled by distributed.net's OGR project, OGR-28 (length 585) finishing in November 2022 after eight years. For `m ≥ 29` the best rulers known all come from the finite-field constructions of Singer (1938, projective plane), Bose–Chowla (affine plane) and Ruzsa; nobody knows whether they are optimal. Here you build rulers for `m = 29 .. 40` as short as you can. `ruler.py` exposes ruler(m: int, time_budget: float, seed: int) -> list[int] returning the `m` marks (distinct non-negative ints, any order; the eval subtracts the smallest, so the ruler need not start at 0). Verification is exact: every pairwise difference is recomputed and must be distinct. A wrong ruler fails the whole submission rather than scoring low. ## Metric The eval runs `ruler` on the fixed set `m = 29, 30, ..., 40`, each with the given time budget (8 s by default), verifies the ruler, and reports metric = mean over m of record_length(m) / length(m) so 1.0 means matching every best-known ruler and anything above 1.0 on an `m` is a new record. Per-instance detail (length, record, ratio, seconds) is in `per_instance`; any `m` you beat is listed under `records_beaten`, and every ruler's marks are printed in the log. `ZT_EVAL_SEED` only changes the `seed` handed to your solver. ## Records Best-known lengths from James B. Shearer's "Table of lengths of shortest known Golomb rulers" (IBM Research, 1998; archived at https://web.archive.org/web/20170625090514/http://www.research.ibm.com/people/s/shearer/grtab.html) and, agreeing on every row, the data file behind Tomas Rokicki and Gil Dogon's "Larger Golomb rulers" (G4G12, 2015; http://cube20.org/golomb/, file `golomb-all-00`, which also gives the construction and the prime power `q` used). Rokicki and Dogon exhaustively re-ran all three constructions for every `q` and every multiplier, so these are the shortest rulers those constructions can give; they offer a reward for beating any of their lengths from 36 marks on. `m ≤ 28` is proven optimal (Wikipedia's Golomb ruler table, distributed.net OGR-24 .. OGR-28). **None of the lengths below is proven optimal.** | m | best-known length | construction | proven | |---|---|---|---| | 29 | 623 | projective plane, q = 29 | no | | 30 | 680 | projective plane, q = 29 | no | | 31 | 747 | projective plane, q = 31 | no | | 32 | 784 | projective plane, q = 31 | no | | 33 | 859 | projective plane, q = 32 | no | | 34 | 938 | projective plane, q = 37 | no | | 35 | 987 | affine plane, q = 37 | no | | 36 | 1005 | affine plane, q = 37 | no | | 37 | 1099 | projective plane, q = 37 | no | | 38 | 1146 | projective plane, q = 37 | no | | 39 | 1252 | projective plane, q = 41 | no | | 40 | 1282 | affine plane, q = 41 | no | Rokicki and Dogon note that only six small orders have optimal rulers shorter than any construction gives; whether that ever happens again is the open question. Beating an entry means a ruler shorter than every Singer, Bose–Chowla and Ruzsa ruler with that many marks. If you beat one, the marks are the evidence: they are in the eval log. Say so in your notes so the hub can update the table and tell distributed.net and Rokicki–Dogon. ## Iterating - Start on one or two orders: `ZT_EVAL_INSTANCES=29,30 ZT_EVAL_PER_INSTANCE_SECONDS=2 python eval.py` runs in seconds. The full set takes about 100 s of solver time; verification is instant. - 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`). - The eval refuses rulers longer than four times the record. - All three constructions give *modular* Golomb rulers (distinct differences mod `M`), and the recipe is the same: build the modular set, multiply by every unit `k` mod `M` (each product is again a modular ruler), sort, and take the shortest window of `m` consecutive marks around the circle; also drop marks from sets with more than `m` elements. - Ruzsa (the baseline): prime `p`, primitive root `g`; `{ p·i + (p-1)·g^i mod p(p-1) : 1 ≤ i < p }` has `p-1` marks mod `p(p-1)`. - Bose–Chowla (affine plane): prime power `q`, `θ` a primitive element of `GF(q²)`; `{ a : θ^a - θ ∈ GF(q) }` has `q` marks mod `q²-1`. - Singer (projective plane): `θ` primitive in `GF(q³)`; the exponents `a` whose `θ^a` lies in a fixed 2-dimensional `GF(q)`-subspace of `GF(q³)` form `q+1` marks mod `q²+q+1`, a perfect difference set. Prime `q` needs only integer arithmetic mod `q` with a cubic irreducible; `q = 32` (the 33-mark record) needs `GF(2^15)`. Every record above is one of these with the `q` shown; reproducing them is the first milestone, and a search over `q`, multiplier and window is small enough to finish within the budget. - To beat a record you need something else: local search from a construction (move one mark, repair collisions), branch and bound with the distance bitmap (how OGR is searched, hopeless alone at these sizes but useful to close a nearly-complete ruler), or truncating/extending a construction ruler with a few free marks. Write one honest line in `NOTES.md`: the idea, and which orders it helped. Simpler is better: all else equal prefer the shorter solver. Log every experiment, including discards, in your results.tsv.