KS Set Search Results
Computational search for small Kochen-Specker sets in 3D using coordinate alphabet generation and randomized greedy minimization.
Tools
ks_test.py— KS coloring tester (recursive backtracking with constraint propagation)ks_search.py— Real-valued search over coordinate alphabetsks_complex.py— Complex/Eisenstein extension with Hermitian inner productks_sat.py— SAT-solver approach (graph-first search with realizability optimization)ks_geometry.py— Geometry-first search (frame networks, mixed alphabets, perturbation analysis)ks_islands.py— Algebraic island classification (number field survey, closure analysis, icosahedral test)
Solver
The coloring test assigns GREEN (1) or RED (0) to each ray, enforcing:
- Orthogonal exclusion: if ray \(i\) is green and ray \(j\) is orthogonal to \(i\), then \(j\) must be red
- Triad completeness: in every orthogonal triad (three mutually orthogonal rays), exactly one must be green
- Contradiction detection: three reds in a triad, or two greens in a triad, or two orthogonal greens
A set is uncolorable (a KS set) if no consistent assignment exists.
Critical bug fix (2026-02-11): The original solver only enforced the orthogonal exclusion rule within triads. It missed contradictions where two orthogonal rays were both green but shared no common triad. This caused the Conway-Kochen 31-vector set to incorrectly test as colorable. After fixing, the integer alphabet correctly rediscovers CK-31.
Results: Real Coordinate Alphabets
Search method: generate all rays from alphabet, test full set for colorability, then run 200-1000 randomized greedy minimization trials.
| Alphabet | Rays | Pairs | Triads | Uncolorable? | Best Minimal |
|---|---|---|---|---|---|
| {0, +/-1} | 13 | 24 | 4 | No | -- |
| {0, +/-1, +/-sqrt(2)} (Peres) | 49 | 120 | 16 | Yes | 33 (72 pairs, 16 triads) |
| {0, +/-1, +/-2} (integer) | 49 | 138 | 26 | Yes | 31 (71 pairs, 17 triads) |
| {0, +/-1, +/-sqrt(3)} | 49 | 114 | 10 | No | -- |
| {0, +/-1, +/-phi} | 49 | 138 | 10 | No | -- |
| {0, +/-1, +/-sqrt(2), +/-2} | 109 | 330 | 38 | Yes | 31 (71 pairs, 17 triads) |
Key finding: Conway-Kochen 31 rediscovered
The integer alphabet {0, +/-1, +/-2} rediscovers the Conway-Kochen 31-vector KS set in ~19% of randomized trials (192 out of 1000). This is the smallest known KS set in real 3D.
Distribution (1000 trials on integer alphabet):
| Size | Count | Percent |
|---|---|---|
| 31 | 192 | 19% |
| 33 | 378 | 38% |
| 35 | 169 | 17% |
| 37 | 42 | 4% |
| 39 | 134 | 13% |
| 41+ | 85 | 9% |
No set smaller than 31 was found. The theoretical lower bound for 3D KS sets is 24 (Uijlen-Westerbaan 2016).
The 31-vector KS set (integer coordinates)
All coordinates from {0, +/-1, +/-2}. 71 orthogonal pairs, 17 triads.
1: (0, 0, 1) 12: (1, 1, 0) 23: (1, -2, 1)
2: (0, 1, 0) 13: (1, 1, 1) 24: (2, 0, 1)
3: (0, 1, 1) 14: (1, 1, -1) 25: (2, 0, -1)
4: (0, 1, -1) 15: (1, 1, 2) 26: (2, 1, 0)
5: (0, 1, 2) 16: (1, -1, 0) 27: (2, 1, 1)
6: (0, 2, -1) 17: (1, -1, 1) 28: (2, 1, -1)
7: (1, 0, 0) 18: (1, -1, -1) 29: (2, -1, 0)
8: (1, 0, 1) 19: (1, -1, -2) 30: (2, -1, 1)
9: (1, 0, -1) 20: (1, 2, 0) 31: (2, -1, -1)
10: (1, 0, 2) 21: (1, 2, -1)
11: (1, 0, -2) 22: (1, -2, 0)
Results: Complex Coordinate Alphabets (Hermitian inner product)
Orthogonality checked via the Hermitian inner product \(\langle v, w \rangle = \sum_k \overline{v_k} w_k\).
Roots of Unity Survey
Alphabet: {0} union {zeta^k : k = 0, ..., n-1} where zeta = e^(2pii/n).
Complete survey for n = 2 through 30:
| n | 6|n? | Rays | Pairs | Triads | Uncolorable? | Best Minimal |
|---|---|---|---|---|---|---|
| 2 | 13 | 24 | 4 | No | -- | |
| 3 | 21 | 21 | 4 | No | -- | |
| 4 | 31 | 69 | 7 | No | -- | |
| 5 | 43 | 18 | 1 | No | -- | |
| 6 | Y | 57 | 174 | 22 | Yes | 33 |
| 7 | 73 | 24 | 1 | No | -- | |
| 8 | 91 | 231 | 13 | No | -- | |
| 9 | 111 | 111 | 28 | No | -- | |
| 10 | 133 | 348 | 16 | No | -- | |
| 11 | 157 | 36 | 1 | No | -- | |
| 12 | Y | 183 | 633 | 67 | Yes | 33 |
| 13 | 211 | 42 | 1 | No | -- | |
| 14 | 241 | 654 | 22 | No | -- | |
| 15 | 273 | 273 | 76 | No | -- | |
| 16 | 307 | 843 | 25 | No | -- | |
| 17 | 343 | 54 | 1 | No | -- | |
| 18 | Y | 381 | 1380 | 136 | Yes | ≤76 (partial) |
| 19 | 421 | 60 | 1 | No | -- | |
| 20 | 463 | 1293 | 31 | No | -- | |
| 21 | 507 | 507 | 148 | No | -- | |
| 22 | 553 | 1554 | 34 | No | -- | |
| 23 | 601 | 72 | 1 | No | -- | |
| 24 | Y | 651 | 2415 | 229 | Yes | (not minimized) |
| 25 | 703 | 78 | 1 | No | -- | |
| 26 | 757 | 2148 | 40 | No | -- | |
| 27 | 813 | 813 | 244 | No | -- | |
| 28 | 871 | 2481 | 43 | No | -- | |
| 29 | 931 | 90 | 1 | No | -- | |
| 30 | Y | 993 | 3738 | 346 | Yes | (not minimized) |
Theorem (empirical): the n-th roots of unity produce an uncolorable set if and only if 6 divides n.
Tested for all n from 2 through 30. The pattern is exact: every multiple of 6 (6, 12, 18, 24, 30) is uncolorable; every non-multiple is colorable — regardless of triad count.
Notable counterexamples to "more triads = uncolorable":
- n = 27 (3|n, not 6|n): 244 triads, colorable
- n = 24 (6|n): 229 triads, uncolorable
- n = 15 (3|n, not 6|n): 76 triads, colorable
- n = 12 (6|n): 67 triads, uncolorable
The mechanism requires both the cube-root cancellation \(1 + \omega + \omega^2 = 0\) (from 3|n) and real-axis orthogonalities (from 2|n) working together. Divisibility by 3 alone creates triads but their constraint network is satisfiable; divisibility by 2 alone creates orthogonal pairs but too few triads. Only when both are present (6|n) does the interlocking become tight enough to force a KS contradiction.
Additional observations:
- Primes (5, 7, 11, 13, 17, 19, 23, 29) always produce exactly 1 triad — the three coordinate axes. Prime roots of unity generate no non-trivial orthogonalities.
- Even non-multiples of 3 (4, 8, 10, 14, 16, 20, 22, 26, 28) produce many orthogonal pairs but few triads (7-43). The real-axis structure alone doesn't create enough interlocking.
- Odd multiples of 3 (9, 15, 21, 27) produce many triads (28-244) through \(\omega\)-cancellation but no real-axis orthogonalities to lock them together.
Eisenstein Integer Search
Components are Eisenstein integers \(a + b\omega\) where \(\omega = e^{2\pi i/3}\), with \(|a|, |b| \leq\) max_coeff and squared norm \(|v|^2 \leq\) cutoff.
| Max coeff | Norm cutoff | Rays | Pairs | Triads | Uncolorable? | Best Minimal |
|---|---|---|---|---|---|---|
| 1 | 3 | 57 | 174 | 22 | Yes | 33 |
| 1 | 4 | 93 | 228 | 40 | Yes | 33 |
| 2 | 4 | 93 | 228 | 40 | Yes | 33 |
| 2 | 5 | 237 | 822 | 58 | Yes (subsumes core) | 33 |
| 2 | 6 | 345 | 1686 | 166 | Yes (subsumes core) | 33 |
The 33-vector complex KS set (Eisenstein notation)
Let \(\omega = e^{2\pi i/3}\). All coordinates from \(\{0, \pm 1, \pm\omega, \pm(1+\omega)\}\) = 6th roots of unity union {0}. 78 orthogonal pairs, 14 triads.
1: (1, 0, 0) 12: (1, 0, -omega) 23: (1, omega, 1)
2: (0, 1, 0) 13: (1, 0, -1) 24: (1, omega, -1)
3: (0, 0, 1) 14: (1, 0, -(1+omega)) 25: (1, -1, 0)
4: (0, 1, 1) 15: (1, 0, -omega) 26: (1, -1, (1+omega))
5: (0, 1, (1+omega)) 16: (1, 1, 0) 27: (1, -1, -(1+omega))
6: (0, 1, omega) 17: (1, 1, (1+omega)) 28: (1, -(1+omega), 0)
7: (0, 1, -1) 18: (1, 1, -(1+omega)) 29: (1, -(1+omega), 1)
8: (0, 1, -(1+omega)) 19: (1, (1+omega), 0) 30: (1, -(1+omega), -1)
9: (0, 1, -omega) 20: (1, (1+omega), 1) 31: (1, -omega, 0)
10: (1, 0, 1) 21: (1, (1+omega), -1) 32: (1, -omega, omega)
11: (1, 0, (1+omega)) 22: (1, omega, 0) 33: (1, -omega, -omega)
Systematic Alphabet Survey (Real)
What makes a cancellation work?
For the alphabet {0, +/-1, +/-x}, the dot product of two vectors can produce terms from {0, +/-1, +/-x, +/-x^2}. A nontrivial three-term orthogonality requires a sum of three such products to equal zero. There are exactly three algebraically special values of x:
| Identity | x | Triads | Best KS | Why |
|---|---|---|---|---|
| \(x^2 = 1 + 1\) | \(\sqrt{2}\) | 16 | 33 | Two 1s sum to one square |
| \(x^2 = x + 1\) | \(\varphi\) | 10 | colorable | Fibonacci recurrence |
| \(x = 1 + 1\) | 2 | 26 | 31 | Integer doubling |
The golden ratio satisfies the right kind of identity (\(\varphi^2 = \varphi + 1\)) but it involves three distinct magnitudes (\(\varphi^2\), \(\varphi\), 1), while the integer identity \(2 = 1 + 1\) involves only two (2 and 1). The simpler identity creates more symmetric orthogonalities, which close into triads far more often (26 vs 10).
Full alphabet results
| Alphabet | Rays | Pairs | Triads | Best KS | Hit rate (500 trials) |
|---|---|---|---|---|---|
| {0, +/-1} | 13 | 24 | 4 | colorable | -- |
| {0, +/-1, +/-sqrt(2)} | 49 | 120 | 16 | 33 | 100% |
| {0, +/-1, +/-1/sqrt(2)} | 49 | 120 | 16 | 33 | 100% |
| {0, +/-1, +/-sqrt(3)} | 49 | 114 | 10 | colorable | -- |
| {0, +/-1, +/-sqrt(5)} | 49 | 114 | 10 | colorable | -- |
| {0, +/-1, +/-sqrt(5)/2} | 49 | 114 | 10 | colorable | -- |
| {0, +/-1, +/-phi} | 49 | 138 | 10 | colorable | -- |
| {0, +/-1, +/-2} | 49 | 138 | 26 | 31 | 19% |
| {0, +/-1, +/-1/2} | 49 | 138 | 26 | 31 | 18% |
| {0, +/-1, +/-phi, +/-phi^2} | 109 | 396 | 24 | colorable | -- |
| {0, +/-1, +/-1/phi, +/-phi, +/-phi^2} | 193 | 798 | 30 | colorable | -- |
| {0, +/-1, +/-phi, +/-2} | 145 | 450 | 50 | 31 | 21% |
| {0, +/-1, +/-sqrt(2), +/-phi} | 145 | 396 | 28 | 33 | 100% |
| {0, +/-1, +/-sqrt(2), +/-2} | 109 | 330 | 38 | 31 | 12% |
| {0, +/-1, +/-2, +/-3} | 145 | 546 | 50 | 31 | 5% |
Key insight: the 2:1 ratio is what matters
Every alphabet that reaches 31 contains the integer ratio 2:1 — either as +/-2 or equivalently as +/-1/2. Adding other values (phi, sqrt(2), 3) to such an alphabet doesn't help or hurt: 31 remains the floor. And NO alphabet without a 2:1 ratio breaks below 33, no matter how rich.
The golden ratio alphabet {0, +/-1, +/-phi, +/-phi^2} with 193 rays and 30 triads is colorable — but the moment you add +/-2 ({0, +/-1, +/-phi, +/-2}, 50 triads), it becomes uncolorable and reaches 31.
Analysis
Why real integers beat complex roots
The integer alphabet {0, +/-1, +/-2} achieves 31 vectors while all complex alphabets bottom out at 33. The reason is triad density:
| Alphabet | Rays | Triads | Triads/Ray |
|---|---|---|---|
| Peres {0, +/-1, +/-sqrt(2)} | 49 | 16 | 0.33 |
| 6th roots of unity | 57 | 22 | 0.39 |
| Integer {0, +/-1, +/-2} | 49 | 26 | 0.53 |
The integer alphabet packs more interlocking triads per ray. The complex phase cancellation (\(1 + \omega + \omega^2 = 0\)) creates abundant orthogonal pairs but fewer tightly interlocked triads than the real integer cancellation (\(2 - 1 - 1 = 0\)).
Open questions
- Is 33 the minimum complex KS set in 3D (analogous to 31 for real)?
- Can systematic hypergraph enumeration + algebraic realizability close the 24-to-31 gap?
- Does every minimal 3D KS set with 31 vectors have the same orthogonality graph as Conway-Kochen?
- Is there a topological or cohomological obstruction that proves 31 is optimal?
SAT-Solver Approach: Graph-First Search
A fundamentally different construction method inverts the alphabet approach: instead of Coordinates -> Graph -> Check coloring, work Graph -> Check coloring (SAT) -> Find coordinates (optimization). This separates the combinatorial problem (find an uncolorable hypergraph) from the geometric problem (embed it in \(\mathbb{R}^3\)), allowing search over configurations whose coordinates need not come from any small alphabet.
Tool: ks_sat.py (requires python-sat, scipy, numpy).
Phase 1: SAT analysis of Conway-Kochen 31
Using the Glucose4 SAT solver, KS coloring is encoded as Boolean satisfiability: variable \(x_i\) = ray \(i\) is green; each triad gets an "exactly one green" constraint (4 clauses); each orthogonal pair gets an "at most one green" constraint (1 clause). UNSAT = no valid coloring = KS set.
CK-31 is maximally tight:
- All 31 rays are essential. Removing any single ray makes the remaining 30-ray set colorable.
- All 17 triads are in the UNSAT core. Every triad participates in the KS contradiction; none is redundant.
- SAT confirms uncolorability in < 1 ms (vs ~10 ms for backtracking).
Phase 2: Realizability via numerical optimization
Given an abstract orthogonality graph (vertices = rays, edges = orthogonal pairs), can we find unit vectors in \(\mathbb{R}^3\) satisfying all constraints? Each ray is parametrized by spherical coordinates \((\theta_i, \phi_i)\); the objective minimizes \(\sum_{(i,j) \in E} (v_i \cdot v_j)^2\) over all required orthogonal pairs. Multiple random restarts with L-BFGS-B optimization.
CK-31's abstract graph is realizable. The optimizer recovers coordinates with residual \(6.4 \times 10^{-10}\) and no unintended extra orthogonalities (the realized graph exactly matches the abstract graph).
Phase 3: Search for novel configurations
Strategy A: Random interlocked hypergraphs. Generate random 3-uniform hypergraphs with each triad sharing at least one ray with another (ensuring connectivity). Test KS-uncolorability via SAT, then check realizability.
| Rays | Triads | Tested | Uncolorable | Realizable |
|---|---|---|---|---|
| 26 | 15 | 200 | 73 (37%) | 0 |
| 26 | 17 | 200 | 125 (63%) | 0 |
| 26 | 19 | 200 | 158 (79%) | 0 |
| 28 | 15 | 200 | 60 (30%) | 0 |
| 28 | 17 | 200 | 97 (49%) | 0 |
| 28 | 19 | 200 | 144 (72%) | 0 |
| 30 | 15 | 200 | 46 (23%) | 0 |
| 30 | 17 | 200 | 73 (37%) | 0 |
| 30 | 19 | 200 | 106 (53%) | 0 |
| Total | 1800 | 882 (49%) | 0 |
Strategy B: Perturb CK-31's graph. Swap one ray in one triad for a different ray. Of 200 perturbations, zero preserved uncolorability.
Key insight: the geometry is the bottleneck
Nearly half of random abstract hypergraphs are KS-uncolorable — the combinatorial constraint is easy to satisfy. But none are realizable in \(\mathbb{R}^3\). Three mutually orthogonal unit vectors in 3D are so constrained that random interlocking patterns almost never have a consistent geometric embedding. Meanwhile, even tiny perturbations of CK-31's graph destroy the KS property entirely.
This explains why the gap between 24 (lower bound) and 31 (best construction) has persisted for decades. Breaking below 31 requires finding a KS-uncolorable graph that is also one of the extremely rare geometrically realizable configurations — and random or local search is unlikely to find one. Systematic enumeration combined with algebraic realizability testing (e.g., Groebner bases) would be needed to make progress.
Geometry-First Search (2026-02-12)
A new approach inverting the standard methodology: instead of starting from coordinates or abstract graphs, build KS configurations from actual R³ geometry, guaranteeing realizability by construction.
Tool: ks_geometry.py.
Mixed alphabet + cross-product completion
Combine two algebraically independent coordinate alphabets, then complete all orthogonal pairs via cross products. The cross products generate rays in neither original alphabet, exploring configurations invisible to any single alphabet search.
| Mix | Total rays | Pairs | Triads | Uncolorable? | Best minimal |
|---|---|---|---|---|---|
| {0,±1,±2} + {0,±1,±√2} | 205 | 498 | 158 | Yes | 31 |
| {0,±1,±2} + {0,±1,±√3} | 217 | 492 | 164 | Yes | 31 |
| {0,±1,±2} + {0,±1,±√5} | 217 | 492 | 164 | Yes | 31 |
| {0,±1,±2} + {0,±1,±φ} | 241 | 612 | 188 | Yes | 34 |
| {0,±1,±√2} + {0,±1,±√3} | 229 | 522 | 166 | Yes | 33 |
| {0,±1,±√2} + {0,±1,±φ} | 253 | 642 | 190 | Yes | 33 |
Key finding: Any mixed alphabet containing the 2:1 integer ratio reaches 31 — even when expanded with irrationals and completed via cross products. Cross-product completion adds 150+ rays beyond the original alphabets, but the minimum doesn't improve. The 31-vector barrier is not an artifact of the alphabet — it persists across all algebraically enriched constructions.
Coordinate perturbation sensitivity
Start from the integer alphabet {0, ±1, ±2} and add Gaussian noise of magnitude ε to each coordinate. Tests whether CK-31 exists in a "basin" of nearby KS configurations or at an isolated point.
| Perturbation ε | Uncolorable | Best minimal |
|---|---|---|
| 0.00 (exact) | 50/50 (100%) | 31 |
| 0.01 | 0/50 (0%) | — |
| 0.05 | 0/50 (0%) | — |
| 0.10 | 0/50 (0%) | — |
| 0.20 | 0/50 (0%) | — |
| 0.50 | 0/50 (0%) | — |
This is the most striking result of the entire search program. A 1% perturbation to CK-31's coordinates destroys the KS property completely. The exact integer algebraic relationships are not approximately sufficient — they are exactly necessary. CK-31 exists at a knife-edge: it is an isolated point in coordinate space, not surrounded by any basin of nearby KS configurations.
This is independently consistent with the rigidity result of Trandafir & Cabello (2025), who proved CK-31 is unique up to unitary transformation.
Random seed completion
Start with 8–25 random unit vectors, complete all orthogonal pairs via cross products, iterate until stable. Tests whether generic (non-algebraic) configurations can produce KS sets.
Result: 0/200 uncolorable. Random rays produce very few orthogonal pairs, and the resulting configurations are always colorable. KS-uncolorability requires algebraic structure — it cannot arise from generic coordinates.
Frame rotation networks
Build trees of orthogonal frames by rotating around shared axes with random or structured angles. Tests whether geometric constructions beyond alphabets can produce KS sets.
Result: 0/400 uncolorable across all tree topologies (depth 2–3, branching 1–2, random and structured angles). The configurations have 81–87 rays but low ray reuse (most rays appear in only 1 triad), which is insufficient for KS-uncolorability.
Algebraic Island Map (2026-02-12)
A systematic classification of all number fields that support KS sets in 3D, discovered through cross-product closure analysis.
Tool: ks_islands.py.
The four known islands
For each candidate number field K, we: (1) generate all rays from the alphabet of K, (2) complete via cross products until stable, (3) test KS-uncolorability, (4) minimize.
| Island | Field K | Key identity | Rays (raw -> completed) | Triads | Min KS |
|---|---|---|---|---|---|
| Integer | \(\mathbb{Q}\) | \(1+1=2\) | 49 -> 109 | 86 | 31 |
| Peres | \(\mathbb{Q}(\sqrt{2})\) | \(1+1=(\sqrt{2})^2\) | 49 -> 145 | 112 | 33 |
| Eisenstein | \(\mathbb{Z}[\omega]\) | \(1+\omega+\omega^2=0\) | 57 (complex) | 22 | 33 |
| Golden | \(\mathbb{Q}(\varphi)\) | \(\varphi^2=\varphi+1\) | 49 -> 205 | 166 | 52 |
The golden ratio island is a new discovery. The raw alphabet \(\{0, \pm 1, \pm\varphi\}\) produces only 10 triads (colorable). But cross-product completion generates 156 additional rays — all staying within \(\mathbb{Q}(\varphi)\) with no integer leak — expanding to 205 rays with 166 triads. This completed pool IS KS-uncolorable, with minimum 52 vectors.
Closure properties
A viable algebraic island must be closed under cross products (or at least, completion stays within the number field) and must not leak to \(\mathbb{Z}\) (which would collapse it to the integer island).
| Field | Closed? | Leaks to Z? | KS? |
|---|---|---|---|
| \(\mathbb{Q}\) (integers) | Leaks (generates irrationals) | YES (trivially) | 31 |
| \(\mathbb{Q}(\sqrt{2})\) | +12 new values, stays in field | No | 33 |
| \(\mathbb{Q}(\sqrt{3})\) | +12 new values, stays in field | No | colorable |
| \(\mathbb{Q}(\sqrt{5})\) | +12 new values, stays in field | No | colorable |
| \(\mathbb{Q}(\varphi)\) | +21 new values, stays in field | No | 52 |
Dead ends: systematic scan
Tested \(\{0, \pm 1, \pm\sqrt{d}\}\) for all non-square \(d\) from 2 to 30. Only \(d=2\) produces a KS set. Every other quadratic field (49 rays, \(\sim\)10 triads) is colorable.
Icosahedral symmetry: a false lead
The icosahedron has 31 symmetry-axis directions (6 vertex + 15 edge + 10 face) — a tantalizing coincidence with CK-31. But:
- 75 orthogonal pairs, only 5 triads — colorable
- After cross-product completion: 91 rays, 65 triads — still colorable
- Reason: the icosahedral group has rotation orders 2, 3, 5 (angles 180°, 120°, 72°) but no 90° rotations. The octahedral group (CK-31's symmetry) is the largest finite subgroup of SO(3) containing 90° rotations.
The efficiency hierarchy
The minimum KS set size correlates with the "simplicity" of the cancellation identity:
| Rank | Identity | Structure | Min KS | Why |
|---|---|---|---|---|
| 1 | \(1+1=2\) | Two identical terms sum to one | 31 | Maximally symmetric; 26 triads from 49 rays |
| 2 | \((\sqrt{2})^2=1+1\) | Square of irrational = sum of units | 33 | Less symmetric; 16 triads from 49 rays |
| 2' | \(1+\omega+\omega^2=0\) | Three-term phase cancellation | 33 | Complex-valued; 22 triads from 57 rays |
| 3 | \(\varphi^2=\varphi+1\) | Three distinct magnitudes | 52 | Requires completion to become KS-uncolorable |
The integer identity \(1+1=2\) wins because it involves only two distinct magnitudes (1 and 2). This creates the most symmetric orthogonality structure, packing the maximum number of interlocking triads per ray. The golden ratio identity \(\varphi^2 = \varphi + 1\) involves three distinct magnitudes (\(1, \varphi, \varphi^2\)), producing a looser orthogonality network that requires many more rays to achieve KS-uncolorability.
Implications for the 24-to-31 gap
These results constrain where a sub-31 KS set could live:
- Not in any \(\mathbb{Q}(\sqrt{d})\) for \(d = 2, \ldots, 30\) — all either give \(\geq 31\) or are colorable
- Not in \(\mathbb{Q}(\varphi)\) — gives 52, far above 31
- Not in \(\mathbb{Z}[\omega]\) — gives 33
- Not in any field containing {0, ±1, ±2} — collapses to the integer island (31)
- Not from icosahedral symmetry — no 90° rotations
- Not from continuous deformation of CK-31 — 1% perturbation destroys KS property
A sub-31 KS set would require a number field we haven't tested — perhaps a cubic extension, a cyclotomic field of higher degree, or a field with no obvious "alphabet" representation. The exhaustive quadratic scan and the closure analysis suggest such a field would need qualitatively different algebraic properties from anything in the known landscape.
The KS Theorem as a Rounding Impossibility (2026-02-12)
The fractional valuation perspective
The KS coloring problem can be recast as a rounding problem. Quantum mechanics assigns each ray in a triad a Born-rule probability — generically \(1/3\) each, always summing to 1. The KS coloring demands rounding each \(1/3\) to either 0 or 1, preserving the sum: exactly one ray rounds up (\(1/3 \to 1\)), the other two round down (\(1/3 \to 0\)).
For a single triad, rounding is trivial: pick any ray as the winner. The impossibility arises because rays are shared between triads. A ray rounded to 1 in one triad must keep the value 1 in every triad it touches (non-contextuality). This propagates rounding constraints through the orthogonality graph. When the sharing structure is complex enough, the constraints form a cycle with no consistent solution.
This connects the KS theorem to the integrality gap in combinatorial optimization: the fractional relaxation (Born probabilities) is always feasible, but the integer version ({0,1} coloring) becomes infeasible at \(n \geq 31\) rays in 3D.
Hierarchy of cancellation identities
The progression from feasible to infeasible tracks a hierarchy of valuations:
| Identity | Valuation type | KS-blocked? | Physics |
|---|---|---|---|
| \(0 + 0 = 0\) | trivial (all 0) | No | Vacuous — violates sum rule |
| \(\frac{1}{2} + \frac{1}{2} = 1\) | fractional \([0,1]\) | No — always satisfiable | Probabilistic hidden variables |
| \(1 + 1 = 2 \to 1 + 1 - 2 = 0\) | sharp \(\{0,1\}\) | Yes — KS theorem | Deterministic hidden variables |
The KS theorem lives precisely in the gap between \(\frac{1}{2}+\frac{1}{2}=1\) (works) and \(1+1=2\) (broken). Fractional valuations always exist; the impossibility is specific to the demand for all-or-nothing certainty.
The cost of geometric realizability
The rounding framing clarifies the meaning of the 24-to-31 gap:
- The lower bound (24) is the minimum number of abstract rounding constraints that CAN form an impossible cycle. This is pure combinatorics — no geometry required.
- The upper bound (31) is the minimum number of constraints that can be BUILT from actual perpendicular directions in \(\mathbb{R}^3\).
The 7-ray gap measures the tax that geometric realizability imposes on the abstract rounding problem. Three features of \(\mathbb{R}^3\) geometry drive this tax:
- Forced completions: If \(u \perp v\), then \(u \times v\) is the unique third member of any triad containing both. You don't choose the third ray — geometry chooses for you.
- Transitive constraints: If \(u \perp v\) and \(u \perp w\), then \(v\) and \(w\) are locked to the plane perpendicular to \(u\) (a one-parameter family). You can't place them independently.
- Algebraic closure: Cross products of integer rays produce integer rays. The alphabet forces the graph to grow until it stabilizes — for \(\{0, \pm 1, \pm 2\}\), stabilization occurs at exactly 31 rays.
Our perturbation result (CK-31 destroyed by 1% coordinate noise) shows that this geometric construction is maximally tight. The constraint cycle barely closes at 31 rays. Going below 31 would require an even tighter arrangement, but geometry keeps adding rays that loosen it. This suggests the 7-ray gap may be structural and permanent: the irreducible cost of physical space.
Conclusion
This search explored the 24-to-31 gap in 3D KS sets from five directions:
1. Alphabet generation (coordinates first): Exhaustively tested real, complex, and Eisenstein alphabets. The minimum is:
- 31 vectors for any alphabet containing the 2:1 integer ratio (the Conway-Kochen set)
- 33 vectors for alphabets based on \(\sqrt{2}\), complex roots of unity, or Eisenstein integers
- Colorable (no KS set at all) for golden ratio, \(\sqrt{3}\), \(\sqrt{5}\), and prime roots of unity
The only algebraic cancellation that produces enough interlocking triads to reach 31 is \(1 + 1 = 2\).
2. SAT + realizability (graph first): Tested 1,800 random abstract hypergraphs. 882 were KS-uncolorable, but zero were realizable in \(\mathbb{R}^3\). CK-31 itself is maximally tight: all 31 rays and all 17 triads are essential, and single-ray perturbations destroy the KS property.
3. Mixed alphabet + completion (geometry first): Combined algebraically independent alphabets and completed via cross products, generating 200+ rays. Every configuration containing the 2:1 ratio minimizes to exactly 31 — no smaller. Cross-product closure does not reveal hidden KS structure below the alphabet search floor.
4. Perturbation analysis: CK-31 exists at an isolated point in coordinate space. A 1% perturbation destroys the KS property. No continuous deformation path leads to a smaller KS set.
5. Algebraic island classification: Systematic survey of all quadratic number fields \(\mathbb{Q}(\sqrt{d})\) for \(d = 2, \ldots, 30\), plus golden ratio, icosahedral symmetry, and cross-product closure analysis. Discovered four algebraic islands supporting KS sets: integers (min 31), \(\sqrt{2}\) (min 33), Eisenstein (min 33), and golden ratio (min 52, newly discovered). None produces fewer than 31 vectors. The hierarchy 31 < 33 < 52 correlates with the algebraic simplicity of the underlying cancellation identity.
All five approaches converge on the same conclusion: the Conway-Kochen 31-vector set sits at the global optimum of a sparse algebraic landscape. Only four number fields support KS sets in dimension 3, and the integer field produces the most efficient construction. This is consistent with the Trandafir–Cabello rigidity theorem and their conjecture that 31 is optimal.
The gap to the theoretical lower bound of 24 remains open. Closing it would require either:
- A proof of optimality — showing no 30-or-fewer-ray KS set exists in \(\mathbb{R}^3\) (or \(\mathbb{C}^3\)), perhaps by tightening the Uijlen-Westerbaan lower bound, or
- A fundamentally new algebraic structure — a number field qualitatively different from the four known islands, perhaps a cubic extension or higher cyclotomic field, that creates a cancellation identity simpler than \(1+1=2\). The exhaustive quadratic scan and closure analysis suggest no such field exists among standard extensions of \(\mathbb{Q}\).
References
- Peres, A. (1991). "Two simple proofs of the Kochen-Specker theorem." J. Phys. A 24, L175.
- Peres, A. (1993). Quantum Theory: Concepts and Methods. Kluwer. Ch. 7 and Appendix.
- Conway, J. & Kochen, S. (unpublished, c. 1990). 31-vector KS set reported in Peres (1993).
- Kernaghan, M. (1994). "Bell-Kochen-Specker theorem for 20 vectors." J. Phys. A 27, L829.
- Kernaghan, M. & Peres, A. (1995). "Kochen-Specker theorem for eight-dimensional space." Phys. Lett. A 198, 1.
- Uijlen, S. & Westerbaan, B. (2016). Lower bound of 24 for 3D KS sets.
- Trandafir, S. & Cabello, A. (2025). "Two fundamental solutions to the rigid Kochen-Specker set problem and the solution to the minimal Kochen-Specker set problem under one assumption." arXiv:2501.11640.