Machine-Checked Certificates for the Geometric Half of the Minimum Kochen-Specker Bound
Shayaan Siddique, Ibrahim Mian
cs.LO
Jul 29, 2026 · v1
quant-ph
TL;DR
A checker for real non-embeddability certificates of Kochen-Specker candidate graphs is implemented and proved sound in Lean 4, with per-graph results as kernel theorems.
Abstract
The best known lower bound for the minimum Kochen-Specker vector system in $\mathbb{R}^3$ – 24 vectors – rests on a computational proof whose combinatorial half emits DRAT proofs but whose geometric half does not: the non-embeddability of thousands of candidate graphs is established by Z3's nonlinear real arithmetic, which produces no checkable proof objects. We close this gap for the proof's blocking database. We introduce exact rational case-tree certificates of real non-embeddability, whose splits are polynomial factorizations and rational sum-of-squares decompositions and whose leaves are discharged by injectivity, ideal-membership, or Positivstellensatz-shaped positivity arguments, and we certify all 291 source lines (180 distinct graphs) of the published pipeline's order-10 to order-13 blocking lists. Certificates are replayed by two independent checkers that share no code with the generator: a pure-Python replay over exact fractions, and a total checker implemented and proved sound in Lean 4. The soundness theorem – acceptance implies that no injective-on-rays, orthogonality-respecting assignment of nonzero real vectors realizes the graph – is kernel-checked with axiom closure {propext, Classical.choice, Quot.sound}, and a gcd-free rational arithmetic layer makes the entire verdict computation kernel-reducible, so each per-graph non-embeddability result is a closed kernel theorem proved by decide. The formalization surfaced findings about the published pipeline, including a load-bearing injectivity side condition in its embeddability notion, hidden WLOG case obligations invisible to Z3-based workflows, and an unreproducible candidate count that we resolve against the published artifacts. All certificates, checkers, and proofs are available and replayable from a single build.
Problem
The best known lower bound (24 vectors) for the minimum Kochen-Specker vector system in R^3 relies on a computational proof whose geometric half uses Z3's nonlinear real arithmetic, which produces no checkable proof objects. This leaves half the flagship result unverified.
Approach
Exact rational case-tree certificates of real non-embeddability are introduced, with splits given by polynomial factorizations and rational sum-of-squares decompositions, and leaves discharged by injectivity, ideal membership, or Positivstellensatz-shaped positivity arguments. A total checker is implemented and proved sound in Lean 4 (toolchain v4.32.0, pinned Mathlib) against a semantic embedding notion, with a gcd-free rational arithmetic layer making verdict computation kernel-reducible via decide. Certificates are also replayed by an independent pure-Python checker over exact fractions.
Results
All 291 source lines (180 distinct graphs) of the published pipeline's order-10 to order-13 blocking lists are certified, each carrying a closed kernel theorem with axiom closure {propext, Classical.choice, Quot.sound}. Seven order-13 certificates discharge 42 of 44 final candidates; formalization also surfaced a load-bearing injectivity condition, hidden WLOG obligations, and an unreproducible candidate count.
| order | source lines | distinct | certified | kernel thms |
|---|
| 10 | 2 | 2 | 2/2 | 2/2 |
| 11 | 16 | 16 | 16/16 | 16/16 |
| 12 | 266 | 155 | 266/266 | 155/155 |
| 13 | 7 | 7 | 7/7 | 7/7 |
| total | 291 | 180 | 291/291 | 180/180 |
Certification coverage of the blocking database and order-13 minimal graphs