💻 logic

Machine-Checked Certificates for the Geometric Half of the Minimum Kochen-Specker Bound

This paper closes a critical verification gap in the minimum Kochen–Specker bound by introducing exact rational case-tree certificates and two independent checkers (one in Python and one formally proved in Lean 4) to machine-verify the geometric non-embeddability of all 180 distinct graphs in the published blocking database, thereby replacing unverified Z3 decisions with kernel-checked theorems while simultaneously uncovering and resolving several hidden flaws and discrepancies in the original proof pipeline.

Original authors: Shayaan Siddique, Ibrahim Mian

Published 2026-07-29

📖 6 min read🧠 Deep dive

Original authors: Shayaan Siddique, Ibrahim Mian

✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to build a house out of invisible, magical blocks. In the world of quantum physics, these blocks are called "vectors," and they have a very strange rule: if two blocks are at a perfect right angle to each other, they can't both be "on" at the same time. This is the heart of the Kochen–Specker theorem, a famous idea that proves the universe isn't just a giant, predictable machine where every part has a pre-set secret switch. Instead, it suggests that the act of looking at a quantum system changes how it behaves.

For decades, physicists have been playing a high-stakes game of "how small can we make this?" They want to find the smallest possible set of these magical blocks that creates a contradiction—a situation where the rules of the game make it impossible to assign "on" or "off" states without breaking the laws of physics. The current record for the smallest known set is 31 blocks. But the big question is: what is the absolute minimum? Could it be done with 25? 24? Or even fewer?

To answer this, researchers use powerful computer programs to generate thousands of potential block arrangements and then try to prove that none of them can actually exist in our 3D world. It's like a detective trying to prove that a suspect couldn't have committed a crime by showing that their alibi is mathematically impossible. The problem is, for the hardest part of this proof, the previous detectives had to trust a "black box" computer solver. They asked the computer, "Is this arrangement possible?" and the computer said, "No." But the computer didn't show its work, leaving a tiny gap in the logic where a mistake could hide.

This paper is about closing that gap. The authors, Shayaan Siddique and Ibrahim Mian, decided to build a new kind of "receipt" for every single impossible arrangement. Instead of just trusting the computer's "No," they created a step-by-step, mathematically perfect certificate that anyone (or any other computer) can check to verify the result. They didn't just check one or two; they checked 291 specific cases (representing 180 unique shapes) that form the foundation of the current best lower bound: 24 vectors.

Here is how they did it and what they found:

The Magic Receipt
Imagine you are trying to prove that a specific shape made of blocks cannot exist. The old way was to ask a super-smart AI, which would crunch numbers and say, "Impossible." The new way, invented in this paper, is to ask the AI to write a story. This story is a "case-tree certificate." It starts with a few basic blocks and then branches out like a choose-your-own-adventure book. At every fork in the road, the story explains why a certain path leads to a contradiction.

The authors made these stories incredibly rigorous. They used "exact rational arithmetic," which means they didn't use approximations or guesses (like saying "this is about 3.14"). Instead, they used perfect fractions. If the story says a number is zero, it is exactly zero, not "close enough to zero." They built two independent "checkers"—one written in Python and one in a formal proof language called Lean 4—to read these stories. These checkers are like strict librarians who verify every single step of the story. If the story has a typo or a logical leap, the librarian rejects it.

The Surprises in the Library
When the authors started reading the old "black box" results with their new, strict checkers, they found some surprises that the original researchers had missed because they were trusting the computer too much.

The "Distinctness" Trap: The original computer program assumed that every single block in the set had to be unique, even if they weren't touching. The authors found that for some of the shapes, the only reason they were "impossible" was because two blocks accidentally ended up being the same block. If you relaxed that rule, the shape might actually work! This meant the original proof relied on a hidden rule about "injectivity" (making sure things are distinct) that wasn't obvious.
Hidden Dead Ends: The computer solver sometimes skipped over "degenerate" cases—weird, edge-case scenarios where the math gets messy. The new certificates forced the authors to write out these messy cases explicitly, proving that even in the weirdest corners, the shapes still couldn't exist.
Counting Errors: The original paper claimed there were 41 final candidate shapes left to check. The new, rigorous replay of the data showed there were actually 43. It turns out the original count was off by two. While this doesn't change the big picture (the bound is still 24), it shows that without these perfect receipts, we might have been missing two important pieces of the puzzle.

The Result
The paper successfully certifies that 180 distinct geometric shapes (drawn from 291 lines of data) cannot be built in our 3D world. They did this by replacing the unverified "black box" answers with 291 verified, machine-checkable certificates.

They also proved that 42 of the 44 final candidates for the minimum number of vectors can be ruled out because they contain one of these certified impossible shapes inside them. This leaves only 2 candidates that are still unproven, but now we know exactly what they are, and the path to proving them is clear.

The authors didn't just say, "We think it's 24." They built a system where every single step is a closed, logical loop that can be checked by a computer in about half a second. They turned a "trust us" argument into a "show your work" argument. While the final proof that the absolute minimum is exactly 24 (and not 23) still needs a few more pieces to be fully assembled, this paper has laid the verified foundation for the geometric half of the puzzle. It proves that for the vast majority of the cases, the universe really does forbid these shapes, and we now have the receipts to prove it.

Technical Summary: Machine-Checked Certificates for the Geometric Half of the Minimum Kochen–Specker Bound

Problem Statement

The minimum Kochen–Specker (KS) problem seeks the smallest number $n$ of nonzero vectors in $\mathbb{R}^3$ , pairwise distinct as rays, such that their orthogonality graph admits no $\{0, 1\}$ -coloring where every orthogonal pair contains at most one $1$ and every orthogonal triad contains exactly one $1$. The best known lower bound is $n \ge 24$ , established computationally by Li et al. and Kirchweger et al.

This proof consists of two halves:

Combinatorial Half: An isomorph-free SAT enumeration of candidate graphs up to order 23. Unsatisfiability results are accompanied by DRAT proofs, which are independently checkable.
Geometric Half: A demonstration that every enumerated candidate graph is non-embeddable in $\mathbb{R}^3$ . This half relies on Z3's nonlinear real arithmetic (NRA) solver to determine that no assignment of nonzero, ray-distinct vectors satisfies the orthogonality constraints.

The critical gap identified in this work is that the geometric half produces no checkable proof objects. The trust chain terminates in Z3's decision procedure for an $\exists\mathbb{R}$ -hard theory, requiring the community to accept the non-embeddability verdicts on faith. Furthermore, the published pipeline relies on "blocking databases" of minimal non-embeddable subgraphs, which are also Z3-derived and unverified.

Methodology

The authors introduce a framework for generating and verifying exact rational case-tree certificates for real non-embeddability. The methodology replaces the opaque Z3 decision procedure with a transparent, algebraic verification process.

1. Certificate Structure
A certificate is a self-contained object comprising:

Anchor and Propagation: A normalization step (anchoring an orthogonal triad or edge) followed by a propagation schedule that expresses all vertex vectors in terms of a few parameters using cross-products and plane parametrizations.
Case Tree: A tree structure where internal nodes represent splits based on:
- Factorization: $p = \prod f_k$ , verified by expansion.
- Sum-of-Squares (SOS): $p = \sum c_k m_k^2$ with $c_k \in \mathbb{Q}_{>0}$ , verified by expansion.
Leaves: Branches are closed by one of four mechanisms:
- Injectivity Collision: Proving two distinct vertices map to parallel rays.
- Obligation Collapse: Showing a required non-zero polynomial is identically zero.
- Ideal Membership: Explicit cofactors proving a polynomial is in the ideal generated by constraints.
- Positivstellensatz-shaped Positivity: A generalized argument showing a sum of positive terms (injectivity polynomials) equals a sum of squares, leading to a contradiction at real points.

2. Verification Architecture
The system employs two independent checkers that share no code with the certificate generator:

Pure-Python Replay: Executes the certificate logic using exact rational arithmetic.
Lean 4 Total Checker: A reflective function Cert.check implemented in the Lean 4 proof assistant.
- Kernel-Reducibility: To ensure the verdict is a closed kernel theorem, the authors implemented a gcd-free rational arithmetic layer (KRat) and fuel-structural recursion. This allows the entire computation to be reduced by the Lean kernel without native reduction or custom axioms.
- Axiom Closure: The soundness theorem relies only on {propext, Classical.choice, Quot.sound}, avoiding unverified native reductions.

3. Soundness Theorem
The core theorem, check_sound, states that if check c = true, then no realization of the graph exists. A realization is defined as a map to $\mathbb{R}^3$ satisfying non-zero vectors, orthogonality on edges, and pairwise ray-distinctness (injectivity) for all vertex pairs.

Key Contributions

Exact Rational Certificates: The introduction of a certificate format that replaces numerical approximations and opaque solvers with exact rational arithmetic, polynomial factorizations, and SOS decompositions.
Complete Coverage of Blocking Database: Certification of all 291 source lines (representing 180 distinct graphs) from the published PhysicsCheck blocking lists (orders 10–13), replacing every Z3 verdict with a machine-checked theorem.
Dual Independent Replay: Validation by two distinct checkers (Python and Lean) that reject 115 adversarial mutations (e.g., tampered coefficients, dropped branches) while accepting genuine certificates.
Formalization-Driven Findings: The rigorous formalization revealed specific issues in the original pipeline:
- Injectivity is Load-Bearing: The original Z3 encoding enforced pairwise ray-distinctness for all pairs, not just adjacent ones. Several graphs in the database are non-embeddable solely due to this injectivity constraint, a nuance invisible to standard geometric solvers.
- Hidden WLOG Cases: The orthoplane parametrization used in the original pipeline concealed degenerate cases (parallel vectors) that must be explicitly discharged by injectivity arguments.
- Empirical Optimization: A "non-colorability" optimization in the original pipeline was found to be empirical rather than a load-bearing lemma.
- Reproducible Counts: The published count of final order-23 candidates (41) was found to be irreproducible from the artifacts; the correct count is 43, with 42 discharged by the new order-13 certificates.

Results

Verification Coverage: All 180 distinct graphs in the blocking database now have closed kernel theorems proving their non-embeddability.
Performance: Kernel evaluation costs approximately 0.5 seconds for order-10/11/12 graphs and 1.8 seconds for order-13 graphs on a standard laptop. The entire verification suite runs in minutes.
Impact on the Bound: The seven new order-13 certificates discharge 42 of the 44 final candidates in the order-22/23 enumeration via verified subgraph monotonicity. The remaining two candidates are tracked as explicit, machine-readable obligations.
Adversarial Robustness: Both checkers successfully rejected all 115 mutated certificates in continuous integration, demonstrating that the verification logic is not merely a replay of the generator's output but a genuine independent check.

Significance

The paper claims to close the trust gap for the geometric half of the minimum KS bound regarding the blocking database. By converting unverified Z3 verdicts into closed kernel theorems, the work ensures that the non-embeddability of the critical subgraphs is no longer a matter of faith in a black-box solver.

The authors emphasize that the formalization process itself was a primary source of value, surfacing hidden assumptions (injectivity), hidden case obligations, and data discrepancies that were invisible to the original workflow. While the paper does not yet compose a fully verified end-to-end theorem for $n \ge 24$ (due to the scale of the SAT enumeration and canonicity proofs), it establishes the verified geometric foundation and provides a scalable path forward. The work demonstrates that complex geometric reasoning in quantum foundations can be made fully machine-checkable with exact arithmetic and minimal axioms.