Research · Papers · Exact answers in open problems · MF-184
Non-existence of 18-vector Kochen-Specker sets in dimension 6
No KS set in C^6 has 18 vectors, hence m_6 >= 19 and m_6 in [19, 21]
Published 2026-09-06
For everyone
Plain summary
In quantum mechanics, you cannot assign fixed values to physical properties before measuring them. The Kochen-Specker theorem proves this mathematically with vector arrangements called Kochen-Specker sets. In these sets, you cannot assign a 0 or a 1 to every vector such that every measurement basis has exactly one 1 and no two orthogonal vectors are both 1.
Xu, Chen, and Gühne proved that any Kochen-Specker set in any dimension needs at least 18 vectors. Four-dimensional space achieves this minimum. This paper proves that no 18-vector Kochen-Specker set exists in six-dimensional complex space, so the universal lower bound of 18 is not tight in dimension 6. The true minimum in dimension 6 must be 19, 20, or 21 vectors. The result is verified with automated proof certificates, conditional on one computational lemma from prior literature.
Result
Let m_d denote the minimum number of vectors in a Kochen-Specker (KS) set in C^d under the strong non-contextuality rule: no assignment v: V -> {0, 1} satisfies both sum_(u in B) v(u) = 1 for every orthonormal basis B and v(u) + v(w) <= 1 for all orthogonal pairs u, w.
Theorem: No KS set in C^6 contains 18 vectors. Therefore, m_6 >= 19.
Combined with the upper bound m_6 <= 21 from Lisoněk et al. (2014), the minimal size is bounded by: m_6 in [19, 21].
Dimension d = 6 is the first dimension where the universal lower bound m_d >= 18 from Xu, Chen, and Gühne (2020) is known to be loose.
Setting and definitions
Let C^d be a complex Hilbert space. A KS set in C^d is a finite set of rays V admitting no valuation v: V -> {0, 1} such that:
- For every complete orthonormal basis B subset of V (|B| = d), sum_(u in B) v(u) = 1.
- For all u, w in V with u orthogonal to w, v(u) + v(w) <= 1.
Let n = |V|. In a minimal KS set, every vector belongs to at least one complete basis. The residue degree bound of Xu, Chen, and Gühne states that any vertex v lying in at least two complete bases C_1 and C_2 satisfies deg(v) <= n - 11. For n = 18 and d = 6, this forces deg(v) = 7, |C_1 ∩ C_2| = 4, and closed neighborhood N[v] = C_1 ∪ C_2.
Method
The proof combines an analytical reduction with SAT-based exhaustive verification.
The analytical reduction proceeds in five steps (lane REPORT.md Theorem 1):
- In a minimal 18-vector KS set in C^6, every vector belongs to at least one 6-vector basis.
- The residue degree bound deg(v) <= n - 11 = 7 for vertices in multiple bases forces |C_1 ∩ C_2| = 4 and N[v] = C_1 ∪ C_2.
- No basis can intersect two distinct bases, as orthogonality would force eight mutually orthogonal vectors in C^6.
- The intersection relation 4p + 3s = 9 forces the configuration to partition into three pairwise disjoint bases.
- In this disjoint-basis case, constraints S4 and S5 admit an explicit valid 0/1 colouring. This step does not require the residue degree bound; S4 alone leaves at least two non-orthogonal candidates in each disjoint basis.
The computational verification partitions the labelled n = 18 CNF encoding into a five-cube cover:
- Cubes A_1, A_2, A_3, A_4: encode two bases intersecting in k = 1, 2, 3, 4 vertices, with S_18 symmetry breaking.
- Cube B: encodes three pairwise disjoint bases.
CaDiCaL solved all five cubes to s UNSATISFIABLE, producing DRAT certificates verified with drat-trim in runtimes between 6 and 23 seconds. An independent smsg symmetry-broken search ran in 39.5 seconds (44.6 seconds on rerun) and returned zero satisfying graphs.
Discussion
The result establishes m_6 in [19, 21]. The derivation depends on the computational residue degree lemma deg(v) <= n - 11 from Xu, Chen, and Gühne (2020), which rests on an external check showing that GHZ-type contextuality requires at least 10 events across all 288,266 graphs on fewer than 10 vertices. That lemma is imported directly without re-verification.
Audit records and verification status:
- Verification clearance: An independent clean-room check confirmed the result using a distinct encoder on 2026-09-06.
- Certificate artifact: An attempt to generate an LRAT certificate via SMS failed
lrat-check. The formal claim rests on the five-cube DRAT cover verified by drat-trim and the independentsmsgsearch. - Novelty: The exclusion of 18-vector KS sets in dimension 6 is novel relative to Xu et al. (2020) and Lisoněk et al. (2014); specific label novelty remains unverified.
For everyone — the takeaway
What this means
Quantum contextuality means that measurement outcomes cannot be fixed in advance. In four dimensions, 18 vectors are enough to construct a Kochen-Specker proof of contextuality. This result shows that 18 vectors are not enough in six dimensions.
The universal lower bound of 18 is therefore not tight for every dimension. A six-dimensional Kochen-Specker proof requires at least 19 vectors, leaving the true minimum at 19, 20, or 21.
Attribution and prior art
Prior art: This result improves the universal lower bound m_d >= 18 from Xu-Chen-Guehne (2020) in dimension 6. Together with Lisonek et al. (2014), this narrows m_6 to [19, 21]. Sources: Xu, Chen, Guehne 2020 (PRL 124, 230401) · Lisonek, Badziag, Portillo, Cabello 2014 (PRA 89, 042101)
Register references
- Register entry: MF-184
- Lane report:
lanes/ks-d6/REPORT.md - Candidate register:
BANK-CANDIDATES.md(KS6-01) - Proof artifacts:
frontier/ks6/w2/cubes/(A1..A4, B: .cnf, .drat, .cadical.log, .drattrim.log, CUBES-PROGRESS.log) - Search artifacts:
frontier/ks6/ks6_open_d6_n18/ - Prior art:
- Xu, Chen, and Guehne, Physical Review Letters 124, 230401 (2020), arXiv:2001.07656
- Lisonek, Badziag, Portillo, and Cabello, Physical Review A 89, 042101 (2014), arXiv:1308.6012
Every artifact named above is bundled in, or hashed by, this paper's evidence pack below.
Evidence pack
Everything needed to check this entry against its receipts: the register text, a manifest with a SHA-256 hash for every named receipt, and 3 of 5 receipt files bundled (21 KB). Anything not bundled is still hashed in the manifest and lives in the compute-box working trees.
Changelog
Last reviewed 2026-09-06
- 2026-09-06Published on this site.
- 2026-09-06Both the manual proof and the machine cover soundly apply Xu-Chen-Guehne’s published lemmas, with the machine version verifying deg(v) <= n - 11 at every vertex across their published Appendix A and Appendix D scopes.