Proof-Carrying Parallel Search for Optimal Golomb Rulers: Certified Partitioned UNSAT Proofs, and a Negative Result for Adaptive Decomposition

A Golomb ruler with n marks is a set of integers 0 = a₀ < … < a_{n−1} whose pairwise differences are all distinct. OGR(n), the shortest such length, is known up to n = 28. Those values were established by exhaustive branch-and-bound searches, and the largest searches (distributed.net, n = 24–28) were checked by running the computation twice, not by producing a certificate. We built a proof-carrying search framework. It has a bitset depth-first search (DFS), a CP-SAT model and CNF encodings solved by CaDiCaL with LRAT proof logging. Every UNSAT proof is checked by two independent checkers, lrat-trim and the CakeML-verified cake_lpr. The search space is split into disjoint prefix regions, and a separate program checks that the regions cover it. We report four findings. 1. Certified optimality through n = 13. Whole-instance LRAT proofs certify OGR(n) for n = 4..12. Partitioned proofs certify n = 10–13. For n = 13 the proof has 11,048 pieces, every one accepted by both checkers, with coverage verified separately: 85.9 GB of LRAT, about 3.6 CPU-hours in total and about 28 minutes for proof generation and checking on 32 single-core jobs. A whole-instance proof needs far more memory to check: cake_lpr peaked at 64.0 GiB on the whole n = 12 proof, while the largest n = 12 piece needed 2.52 GiB. 2. The central hypothesis fails at the scale tested. Adaptive splitting with a node budget did not beat a static depth-2 prefix split on the hardest instances. At 32 workers it ran at 0.30–0.89× the speed of the static split for n = 15 and 16, across node budgets from 10⁷ to 10⁹. At n = 17 it approached parity (0.95×), but at n = 18 it fell back to 0.88×, so the trend did not continue into a crossover. Its only clear wins were on small instances and on some satisfiable ones. Adaptive splitting repeats only 2–6% of the search, so the loss is overhead from task creation and the central queue, not duplicated work. 3. A solver portfolio adds nothing when a certificate is required. Every partition piece was solved by all three backends. The DFS is about 3–4 orders of magnitude cheaper per piece than SAT or CP-SAT, so a learned selection rule always picks DFS. But a DFS or CP-SAT answer is not a checkable certificate. Once the SAT proof is required anyway, always choosing SAT matches the per-piece oracle at n = 13 (14,961 CPU s), and the adaptive selector is 0.03% above it. 4. Pruning matters more than parallel strategy. The midpoint reflection rule and the sub-ruler/unused-distance bound together cut serial work 53× at n = 15. That is more than any parallel decomposition gained. We also found that drat-trim's lrat-check (commit 2e3b2dc) accepts an invalid proof. A literature audit corrected the protocol's stated frontier to 586 ≤ OGR(29) ≤ 623. No new value of OGR(n) is claimed: every order solved here was settled decades ago.

Authors

Institutions

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-11-19
DOI
https://doi.org/10.5281/zenodo.24369467
Primary Topic
Formal Methods in Verification
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Proof-Carrying Parallel Search for Optimal Golomb Rulers: Certified Partitioned UNSAT Proofs, and a Negative Result for Adaptive Decomposition

S. M. Abdulla Al Mamun
Zenodo (CERN European Organization for Nuclear Research)
Formal Methods in Verification
preprint

Proof-Carrying Parallel Search for Optimal Golomb Rulers: Certified Partitioned UNSAT Proofs, and a Negative Result for Adaptive Decomposition

S. M. Abdulla Al Mamun
preprint en

Abstract

A Golomb ruler with n marks is a set of integers 0 = a₀ < … < a_{n−1} whose pairwise differences are all distinct. OGR(n), the shortest such length, is known up to n = 28. Those values were established by exhaustive branch-and-bound searches, and the largest searches (distributed.net, n = 24–28) were checked by running the computation twice, not by producing a certificate. We built a proof-carrying search framework. It has a bitset depth-first search (DFS), a CP-SAT model and CNF encodings solved by CaDiCaL with LRAT proof logging. Every UNSAT proof is checked by two independent checkers, lrat-trim and the CakeML-verified cake_lpr. The search space is split into disjoint prefix regions, and a separate program checks that the regions cover it. We report four findings. 1. Certified optimality through n = 13. Whole-instance LRAT proofs certify OGR(n) for n = 4..12. Partitioned proofs certify n = 10–13. For n = 13 the proof has 11,048 pieces, every one accepted by both checkers, with coverage verified separately: 85.9 GB of LRAT, about 3.6 CPU-hours in total and about 28 minutes for proof generation and checking on 32 single-core jobs. A whole-instance proof needs far more memory to check: cake_lpr peaked at 64.0 GiB on the whole n = 12 proof, while the largest n = 12 piece needed 2.52 GiB. 2. The central hypothesis fails at the scale tested. Adaptive splitting with a node budget did not beat a static depth-2 prefix split on the hardest instances. At 32 workers it ran at 0.30–0.89× the speed of the static split for n = 15 and 16, across node budgets from 10⁷ to 10⁹. At n = 17 it approached parity (0.95×), but at n = 18 it fell back to 0.88×, so the trend did not continue into a crossover. Its only clear wins were on small instances and on some satisfiable ones. Adaptive splitting repeats only 2–6% of the search, so the loss is overhead from task creation and the central queue, not duplicated work. 3. A solver portfolio adds nothing when a certificate is required. Every partition piece was solved by all three backends. The DFS is about 3–4 orders of magnitude cheaper per piece than SAT or CP-SAT, so a learned selection rule always picks DFS. But a DFS or CP-SAT answer is not a checkable certificate. Once the SAT proof is required anyway, always choosing SAT matches the per-piece oracle at n = 13 (14,961 CPU s), and the adaptive selector is 0.03% above it. 4. Pruning matters more than parallel strategy. The midpoint reflection rule and the sub-ruler/unused-distance bound together cut serial work 53× at n = 15. That is more than any parallel decomposition gained. We also found that drat-trim's lrat-check (commit 2e3b2dc) accepts an invalid proof. A literature audit corrected the protocol's stated frontier to 586 ≤ OGR(29) ≤ 623. No new value of OGR(n) is claimed: every order solved here was settled decades ago.

Zenodo (CERN European Organization for Nuclear Research)
University of Manchester (GB)
Formal Methods in Verification
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon