Research · Papers · Exact answers in open problems · MF-185
Two necessary conditions on Kochen-Specker orthogonality graphs
For basis K in C^d: deg_K(v) ≤ d-2 for v ∉ K; and v ∦ w (v, w ∉ K) implies ∃u ∈ K with u ∦ v and u ∦ w.
Published 2026-09-06
For everyone
Plain summary
Kochen-Specker systems are sets of geometric directions, or rays, proving that quantum measurements cannot merely reveal preexisting values. When search algorithms look for these systems, they represent rays as graph nodes connected by edges whenever two directions are perpendicular. A complete set of mutually perpendicular directions forms a basis clique.
Any valid ray system in d dimensions obeys two strict geometric rules:
- A ray outside a complete basis can be perpendicular to at most d - 2 rays inside that basis.
- If two rays outside a basis are not perpendicular to each other, at least one ray in the basis must be perpendicular to neither of them.
These conditions serve as static pruning clauses for automated search software. While both hold in any dimension d, standard three-dimensional literature instead relies on different closure properties, leaving general novelty unverified.
Result
Let G be the orthogonality graph of a set of distinct rays in C^d, and let K be a d-clique corresponding to an orthogonal basis. The graph G satisfies two necessary conditions:
- Condition S4: For any vertex v outside K, deg_K(v) ≤ d - 2. That is, v is adjacent to at most d - 2 vertices of K.
- Condition S5: For any vertices v, w outside K, if v and w are non-adjacent (v ∦ w), there exists a vertex u ∈ K such that u is adjacent to neither v nor w (u ∦ v and u ∦ w).
Setting and definitions
Let C^d denote the d-dimensional complex vector space. A ray is a one-dimensional subspace in C^d. The orthogonality graph G = (V, E) of a set of distinct rays has vertex set V corresponding to the rays, with an edge (v, w) ∈ E if and only if the rays v and w are orthogonal (v ⊥ w).
A basis clique K ⊆ V is a clique of size d representing a complete mutually orthogonal basis of C^d. For a vertex v ∉ K, deg_K(v) denotes the number of neighbors of v in K. Non-adjacency in G is denoted by ∦, indicating non-orthogonal rays.
Method
Both conditions follow from elementary linear algebra:
- For S4: if a distinct ray v ∉ K were orthogonal to d - 1 elements of K, the one-dimensional orthogonal complement of those d - 1 basis elements would force v to coincide with the remaining d-th basis ray in K, contradicting v ∉ K.
- For S5: if no such u ∈ K exists, every basis vector in K is orthogonal to v, to w, or to both. Partitioning K into basis subsets orthogonal to v and w places v and w in orthogonal subspaces spanned by complementary subsets of K, forcing v ⊥ w and contradicting v ∦ w. S5 formulates XCG's colourability argument as a local graph rule.
Both conditions were verified via exact sympy replay on known Kochen-Specker configurations, including the Cabello 18-vector system in d = 4 and the LBPC 21-vector system in d = 6. The constraints are implemented as static clauses in lanes/ks-d6/receipts/tools-w2/ks_cnf.py and utilized in MF-184.
Discussion
Conditions S4 and S5 provide necessary graph-theoretic pruning clauses for SAT encodings of Kochen-Specker vector systems and orthogonality graphs in dimension d.
The conditions are necessary but not sufficient for embeddability in C^d. They do not appear in the d = 3 SAT literature, which relies on C4-free and cross-product closure properties; novelty in general dimension remains unverified.
For everyone — the takeaway
What this means
Automated solvers searching for quantum ray configurations face combinatorial spaces of candidate graphs. Translating geometric constraints into graph-level rules allows SAT solvers to discard branches that cannot embed in d dimensions without running expensive algebraic checks.
Attribution and prior art
Prior art: This result was not found in the existing d = 3 SAT literature, which typically relies on C4-free or cross-product closure methods; its novelty remains unverified. Sources: Xu, Chen, Guehne 2020
Register references
- Entry: MF-185
- Related entry: MF-184
- Receipts:
lanes/ks-d6/receipts/tools-w2/ks_cnf.py,receipts/replay/ - Prior art: d = 3 SAT literature (C4-free / cross-product closure; novelty unverified)
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 1 of 1 receipt files bundled (3 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-06Results S4 and S5 were independently re-proved from scratch, showing 0 violations across 13,737 numeric and graph tests. S5 corresponds to the Lemma proof in XCG's Appendix D, though the novelty of the graph-rule packaging remains unverified.