Metraipolis › archive › dc_c03fa62364bd
Toward a Formally Verified Optimality Certificate for OGR(29): A SAT-Encoding Methods Note with Small-Case Demos — arXiv:2609.05421
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.05421
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-16T13:07:03.349Z
- SHA-256 of the archived text
43f181755436c8d3e6eb62a40819ea3ba9cac933bcb6d30731375a62693742a5- Stable URL of this page
https://metraipolis.com/documento/dc_c03fa62364bd
How to cite
Toward a Formally Verified Optimality Certificate for OGR(29): A SAT-Encoding Methods Note with Small-Case Demos — arXiv:2609.05421 — arXiv (en), https://arxiv.org/abs/2609.05421 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_c03fa62364bd (Metraipolis archive dc_c03fa62364bd, sha256 43f181755436c8d3e6eb62a40819ea3ba9cac933bcb6d30731375a62693742a5)
BibTeX
@misc{dcc03fa62364bd,
title = {Toward a Formally Verified Optimality Certificate for OGR(29): A SAT-Encoding Methods Note with Small-Case Demos — arXiv:2609.05421},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.05421},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_c03fa62364bd; sha256 43f181755436c8d3e6eb62a40819ea3ba9cac933bcb6d30731375a62693742a5},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.05421. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
A Golomb ruler of order~$n$ is an integer set $\{a_0<a_1<\cdots<a_{n-1}\}$ whose $\binom{n}{2}$ pairwise differences $a_j-a_i$ ($i<j$) are all distinct. The optimal Golomb ruler problem asks for $\mathrm{OGR}(n)=\min\{a_{n-1}-a_0\}$ and is a classical combinatorial benchmark. The values $\mathrm{OGR}(2),\dots,\mathrm{OGR}(28)$ are settled through distributed volunteer search (the this http URL OGR project); $\mathrm{OGR}(29)$ is in active computation, with verification expected in late 2026 or early 2027. The recent upper bound $\mathrm{OGR}(29)\le 757$ of Lee, Park, and Kim ( arXiv:2510.0122 , October~2025) tightens the search window. This note describes a compact CNF encoding of the decision problem $\mathrm{GR}(n,L)$ (``is there a Golomb ruler of order~$n$ with length exactly~$L$?'') with $O(n^2 L)$ clauses, together with a small-case verification sweep that emits machine-checkable LRAT certificates of optimality for $\mathrm{OGR}(n)$ at $n\le 12$. We then give closed-form encoding-size estimates for $\mathrm{OGR}(29, L=757)$ and propose a cube-and-conquer decomposition aimed at a Mallob-style parallel run on commodity multi-core hardware. The certificate pipeline (CaDiCaL with --lrat=true, a structural sanity-check, then formal validation by drat-trim or cake\_lpr) is end-to-end. A formally verified optimality proof for any single $\mathrm{OGR}(n)$ value beyond the trivial $n\le 5$ would be a first in the field.
Tema degli esploratori: calcolo e infrastrutture (retro-catalogo arXiv: annunci del 2026-09-09 in cs.DC).
Categorie arXiv: Distributed, Parallel, and Cluster Computing (cs.DC) ; Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2609.05421 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-16T13:02:21.534Z dalla pagina https://arxiv.org/catchup/cs.DC/2026-09-09?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).