Finite Witnesses for the Kochen–Specker Theorem

The Kochen–Specker theorem excludes a single zero-one assignment to all rank-one projectors that selects exactly one outcome in every orthonormal basis, in dimension at least three. Its usual formulation mentions infinitely many projectors. Compactness shows that some finite collection of basis constraints already witnesses the contradiction. This page proves that reduction; the linked article explains the theorem, dimensional exceptions, and explicit Peres–Mermin proof.

Required background. Projection-Valued Measures identifies a sharp context with orthogonal alternatives summing to the identity; Kochen–Specker Theorem supplies the global impossibility statement used below.

Projector valuations as a compact constraint problem

Fix a real or complex Hilbert space of finite dimension $d\ge3$. Let $R$ be its rank-one orthogonal projectors, and put

$$\Omega=\{0,1\}^{R}.$$

A point of $\Omega$ assigns a bit to every projector. Give each factor the discrete topology and $\Omega$ the product topology. Tychonoff’s theorem makes $\Omega$ compact; this argument uses the usual classical compactness principle, not an effective algorithm for finding a configuration.

For each orthonormal basis context $C=\{P_1,\ldots,P_d\}$, define

$$F_C=\left\{v\in\Omega: \sum_{P\in C}v(P)=1\right\}.$$

Membership depends on only $d$ coordinates, so $F_C$ is both closed and open. A global Kochen–Specker valuation is exactly a point of $\bigcap_C F_C$. The theorem says this intersection is empty.

If every finite collection of the $F_C$ had nonempty intersection, compactness would force their full intersection to be nonempty. Therefore there are finitely many contexts $C_1,\ldots,C_m$ with

$$F_{C_1}\cap\cdots\cap F_{C_m}=\varnothing.$$

Only the finitely many projectors in their union matter. This proves existence of a finite uncolorable configuration from the global theorem. Conversely, a finite uncolorable subset immediately obstructs a valuation on all projectors, since any global valuation would restrict to one on that subset. The two forms agree at the level of existence.

What a finite certificate contains

Let $R_0=\{P_1,\ldots,P_n\}$ be the chosen projectors and define the incidence matrix $M$ by $M_{aj}=1$ if $P_j\in C_a$ and zero otherwise. The finite logical problem is

$$Mv=\mathbf1,\qquad v\in\{0,1\}^n.$$

It has two distinct inputs. The incidence matrix specifies which events are identified between contexts. A Hilbert-space realization supplies normalized vectors, their rank-one projectors, and exact orthogonality and completeness relations for every context. Proving that an arbitrary incidence matrix is uncolorable does not prove that it describes quantum measurements in a specified dimension.

There is always a fractional solution $v_j=1/d$ for a configuration whose contexts all contain $d$ vertices. Thus ordinary linear feasibility is not the zero-one problem. Fractional assignments are appropriate probabilities; the impossibility concerns deterministic noncontextual values. This is why the theorem does not contradict the Born rule.

One may verify a small certificate by exhaustive enumeration of its $2^n$ assignments. Larger certificates can use a Boolean satisfiability proof or an analytic invariant. The verification should retain the projector identifications and the exact coordinate data, not just a plot of nearly orthogonal vectors.

A parity certificate and its boundary

Suppose a finite configuration has an odd number $m$ of complete contexts, and each projector occurs in an even number $r_j$ of them. Summing every context equation would give

$$\sum_{j=1}^n r_jv_j=m.$$

The left side is even, while the right side is odd. Hence no zero-one valuation exists. This parity lemma is a sufficient combinatorial certificate, not a characterization of all Kochen–Specker sets.

The 18-ray, nine-context construction of Cabello, Estebaranz, and García-Alcaine realizes this pattern in dimension four, with each ray appearing twice. Its exact vectors establish quantum realizability, which the parity calculation alone does not guarantee. The canonical theorem page develops a different compact observable-parity witness, the Peres–Mermin square.

Exact orthogonality enters the logical theorem. Replacing its vectors by nearby laboratory settings does not automatically preserve an exact identification of events or a deterministic constraint. A noise-tolerant experimental inequality needs its own operational assumptions and error analysis. Compactness establishes a finite exact witness, not an experimental tolerance bound.

Exercise: why odd-dimensional parity needs more care

Show that the parity pattern above cannot consist solely of complete rank-one contexts in odd dimension with an odd number of contexts and every ray occurring an even number of times. Does this restore a valuation in dimension three?

Solution

Counting incidences gives $md=\sum_jr_j$. If $m$ and $d$ are odd, the left side is odd and the right side is even, so such incidence data cannot exist at all. This excludes that particular parity construction, not other uncolorability arguments. The Kochen–Specker obstruction in dimension three remains; compactness still guarantees a finite witness, but this simple even-incidence pattern cannot provide it.

References

• Cabello, Adán, José M. Estebaranz, and Guillermo García-Alcaine, “Bell–Kochen–Specker theorem: A proof with 18 vectors,” Physics Letters A 212, 183–187 (1996), doi:10.1016/0375-9601(96)00134-X — an exact finite parity configuration.
• Kochen, Simon, and Ernst P. Specker, “The Problem of Hidden Variables in Quantum Mechanics,” Journal of Mathematics and Mechanics 17, 59–87 (1967), doi:10.1512/iumj.1968.17.17004 — the global valuation obstruction and finite geometric construction; the DOI uses the journal volume-year convention.
• Munkres, James R., Topology, 2nd edition, Prentice Hall, 2000 — product compactness and the finite-intersection property used in the reduction.