Nonexistence of 20-vector Kochen-Specker sets in C^6 and minimality of m_6 = 21

Result

No Kochen-Specker vector system exists in C^6 with n = 20 vectors. The minimum size m_6 of a Kochen-Specker set in dimension d = 6 is m_6 = 21, matching the upper bound achieved by the symmetric construction of Lisonek, Badziag, Portillo, and Cabello (2014).

This proof is conditional on the Xu-Chen-Gühne (XCG) parity lemma (every Greenberger-Horne-Zeilinger-type parity proof contains at least 10 events), which enforces the universal vertex degree bound:

deg(v) <= n - 11 = 9

for every vertex v in an n = 20 hypergraph.

Setting and definitions

A Kochen-Specker (KS) set in C^d is a finite set of rays V in C^d with no valuation f: V -> {0, 1} satisfying:

1. For every orthonormal basis B ⊆ V of C^d, ∑_{v ∈ B} f(v) = 1.
2. For any two orthogonal vectors u, v ∈ V, f(u) + f(v) <= 1.

The hypergraph of the KS set has vertex set V (|V| = n), with hyperedges corresponding to complete orthonormal bases of size d = 6.

Let m_d denote the minimum cardinality |V| of a KS set in dimension d. For all d >= 3, 18 <= m_d. In d = 6, Lisonek, Badziag, Portillo, and Cabello (LBPC 2014) constructed a symmetric 21-vector parity proof, establishing m_6 <= 21 and bounding m_6 in [18, 21].

Method

Nonexistence was proved by refuting a preregistered 143-cube cover over Boolean encodings of hypergraph orthogonality and valuation constraints.

The cover decomposition was preregistered in lanes/ks-d6/verify-invent/tests/ks6-n20-cover/PREREG.md:

1. Level 1 splits on intersection size k = |C1 ∩ C2| for two distinct orthonormal bases C1, C2:

• k = 0 is impossible because two disjoint 6-element bases would partition 20 vertices into multiples of 6.
• k = 1, 2, 3, 4 are admissible.
• k = 5 violates S4 orthogonality for distinct complete bases.
• k = 6 gives identical bases.

1. Level 2 partitions the vertex set in branch A_k into four disjoint blocks:

• Shared vertices: SH = C1 ∩ C2, with |SH| = k.
• Private basis 1 vertices: P1 = C1 \ SH, with |P1| = 6 - k.
• Private basis 2 vertices: P2 = C2 \ SH, with |P2| = 6 - k.
• Outer vertices: OU = V \ (C1 ∪ C2), with |OU| = 20 - (12 - k) = 8 + k >= 9.

Every outer vertex in OU belongs to at least one basis, requiring a third basis C3. The level 2 branch decomposes over:

(a, b, c, e) = (|C3 ∩ SH|, |C3 ∩ P1|, |C3 ∩ P2|, |C3 ∩ OU|)

subject to:

• a + b + c + e = 6
• e >= 1
• a + b <= 4 (since |C3 ∩ C1| <= 4)
• a + c <= 4 (since |C3 ∩ C2| <= 4)

The block-wise symmetry group S_SH x S_P1 x S_P2 x S_OU acts transitively on tuples with identical intersection counts, permitting canonical index assignment for C3 without loss of generality.

Branch counts across k = 1..4:

• k = 1: 32 cubes (19 tuples with a = 0, 13 with a = 1)
• k = 2: 40 cubes
• k = 3: 40 cubes
• k = 4: 31 cubes
• Total: 143 cubes.

Execution and certification:

• A calibration run at n = 19 (31 cubes) yielded 31/31 unsatisfiable.
• The 143 cubes at n = 20 were generated with clean-room encoder vks.py, validated against exact model enumeration on 6 vertices (differing from ks_cnf.py by 200 variables and 270 clauses at n = 18).
• Each cube was solved by CaDiCaL and certified with drat-trim.
• All 143 cubes returned s UNSATISFIABLE with s VERIFIED, 0 SAT instances, and 0 timeouts (exit code 124), averaging ~20 seconds per cube.
• The entire 143-cube cover was replayed and verified 143/143 by an independent second encoder.

Discussion

This result establishes m_6 = 21, closing the gap above the lower bound of 18 (and intermediate nonexistence results in MF-184 and MF-195). Dimension d = 6 is the first dimension where the universal bound m_d >= 18 is strictly loose.

Scope and conditions:

• The proof is conditional on the Xu-Chen-Gühne lemma (XCG 2020), which requires at least 10 events in any GHZ-type parity proof, yielding deg(v) <= n - 11 = 9. Clean-room verification confirmed the scope of XCG Appendix A ("the choice of |psi_i> is arbitrary"), including three unstated side conditions.
• LBPC (PRA 89, 2014) introduced their 21-vector system as a symmetric parity proof without claiming minimality; this result establishes that it is minimal.
• Novelty status is unverified regarding whether another team has independently excluded 19 or 20 vectors in d = 6, though literature search across four seats found no prior claims.

Attribution and prior art

Prior art: While prior work established 18 <= m_d for all d (XCG 2020) and m_6 <= 21 (LBPC 2014, "simplest KS set admitting a symmetric parity proof"), m_6 remained in [18, 21]. Entries MF-184, MF-195, and this work close m_6 to 21, proving d = 6 is the first dimension where the bound 18 is not attained. Sources: Xu, Chen, Guehne 2020 (PRL 124, 230401) · Lisonek, Badziag, Portillo, Cabello 2014 (PRA 89, 042101)

Register references

• Entry: MF-199 (incorporating MF-184, MF-195)
• Prior art:
• Xu, Chen, and Gühne (XCG 2020), universal lower bound 18 <= m_d and GHZ-type parity lemma
• Lisonek, Badziag, Portillo, and Cabello (LBPC 2014, PRA 89, 042101), 21-vector symmetric parity proof
• Receipts and verification artifacts:
• lanes/ks-d6/verify-invent/tests/ks6-n20-cover/PREREG.md
• frontier/ks6vet/n20/ (PROGRESS.box.log, status_20_1..4.json, status_19_4.json)
• lanes/ks-d6/verify-invent/tools/
• tests/ks6-n20-cover/
• Encoder: vks.py (and comparison encoder ks_cnf.py)

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 4 of 6 receipt files bundled (9 KB). Anything not bundled is still hashed in the manifest and lives in the compute-box working trees.

Download evidence.zip

Related in this programme

• MF-195
  Nonexistence of 19-vector Kochen-Specker sets in C^6 and the lower bound m_6 ≥ 20
• MF-190
  Exact B2 circuit size and machine-checkable certificate for 5-input MOD3,1
• MF-189
  Exact sizes of small single-output median networks
• MF-184
  Non-existence of 18-vector Kochen-Specker sets in dimension 6