Thirty-one directions nobody can label

No way to hand out true and false proved the Kochen–Specker theorem in four dimensions with eighteen directions. The directions fall into nine orthogonal bases, every direction in exactly two of them; a labelling would need exactly one true direction in each basis, nine in all counted with multiplicity, while every true direction is counted twice, an even number. The contradiction is a parity, and it needs no search.

The theorem was first proved in three dimensions, the setting of a spin-one particle, and there the parity trick is unavailable: a direction in three dimensions can lie in any number of orthogonal triads, and no arrangement found so far makes the counting come out odd. A proof in three dimensions has to be a genuine contradiction, found by following consequences, and the question of how few directions can carry one has driven sixty years of constructions and searches. That essay ended on it.

The rule a labelling must obey #

The yes-or-no question “is the spin along this axis zero?” has, in quantum mechanics, a peculiar property: for any three mutually perpendicular axes, exactly one of the three questions is answered yes. A labelling of a set of directions is an assignment of true or false to each one that respects this, for every orthogonal triad in the set, and also never makes two perpendicular directions both true — since two perpendicular directions always belong to some triad, even if the third member is not in the set. If the outcomes of measurements were fixed in advance, independently of which other measurements were made alongside, they would form a labelling of every direction at once.

The rule is not an arbitrary game; it is what a spin-one particle does. For such a particle the squares of the spin components along three perpendicular axes, $S_x^2$, $S_y^2$ and $S_z^2$, can all be measured together, since they commute, and they always add to 2, with each one equal to 0 or 1. So exactly one of the three is 0 — exactly one of the three questions “is the spin along this axis zero?” gets the answer yes. Kochen and Specker chose three dimensions because this is the smallest system in which the questions about one axis belong to several different triads, and so to several different joint measurements.

A Kochen–Specker set is a finite set of directions with no labelling. Its existence proves that the outcomes cannot all be fixed in advance in that way; what an outcome is depends on the context of the other measurements made with it. Simon Kochen and Ernst Specker’s original set of 1967 had 117 directions.

Peres’s thirty-three, checked exactly #

Asher Peres found in 1991 a set of thirty-three directions with a pleasing description: all the rearrangements and sign changes of $(0, 0, 1)$, $(0, 1, 1)$, $(0, 1, \sqrt 2)$ and $(1, 1, \sqrt 2)$, with a direction and its opposite counted once. There are 3, 6, 12 and 12 of each kind.

Checking it by computer needs one precaution. Two of its directions are perpendicular when their dot product vanishes, and with $\sqrt 2$ in the coordinates a floating-point dot product of $10^{-16}$ might be a nought or might not. So every coordinate is stored as a pair of whole numbers $(a, b)$ meaning $a + b\sqrt 2$, and a dot product is nought exactly when both parts are. The set then has 72 perpendicular pairs and 16 orthogonal triads, exactly as Peres described.

The proof that no labelling exists is a search, but a short one. Try a value for one direction and follow every consequence: a true direction makes all its perpendicular partners false; a triad with two false members makes its third true; a triad with no true member and none left to set, or with two true members, is a contradiction, and the search backs up. It is unit propagation, the step at the heart of every satisfiability solver, applied to a problem whose clauses are triads, and on Peres’s set it runs out of options after twenty-three choices in all. A failed search is a proof: the twenty-three choices, written out, are a certificate that anyone can check.

The same question as a formula #

The labelling problem is a satisfiability problem in disguise, and writing it that way shows what kind of contradiction the search is finding. Give each direction a letter, true for “this direction is the one”. A triad $\{a, b, c\}$ needs at least one true letter, the clause $a \lor b \lor c$, and at most one, the three clauses $\lnot a \lor \lnot b$, $\lnot a \lor \lnot c$ and $\lnot b \lor \lnot c$. Every perpendicular pair outside a triad adds one more clause of two letters. Peres’s set becomes 16 clauses of three letters and 72 of two.

Every two-letter clause is an arrow between two letters: if $a$ is true, $b$ is false. A formula made only of those is solved instantly by following arrows, and so is any formula once enough letters are fixed — which is exactly what the propagating search exploits. The three-letter clauses are where the difficulty lives, and there are only sixteen of them. It is also why a contradiction, if there is one, can always be found among finitely many directions: an infinite set with no labelling contains a finite one, refutable in something small by the compactness of propositional logic, which is why the question of the smallest set makes sense at all. The refutation the search finds can be rewritten as a proof in one rule, resolution, that derives the empty clause from these 88 clauses, and its length is a measure of how tangled the triads are; eliminating letters one at a time, the way Davis and Putnam resolved them away, reaches the same empty clause by a different route.

Every direction is needed #

A Kochen–Specker set might contain redundant directions, ones whose removal leaves the contradiction intact. Peres’s does not. Remove any one of the thirty-three and the remaining thirty-two can be labelled: in sixteen ways if the removed direction is one of the thirty off the coordinate axes, in 152 ways if it is one of the three axes, each of which sits in more triads than any other direction and so carries more of the contradiction. A set with this property is called critical. It is a local minimum: nothing can be taken out of it, though a quite different set might still be smaller.

Searching for something smaller #

The thirty-three directions come from a small menu of coordinates, $\{0, \pm 1, \pm\sqrt 2\}$. Conway and Kochen found a set of thirty-one from a different menu, $\{0, \pm 1, \pm 2\}$, and the search can rediscover it.

There are 49 directions with coordinates from $-2$ to 2, up to sign and common factors, and they have no labelling. Shrink the set: go through the directions in a random order and drop each one unless dropping it would make a labelling possible. What is left at the end is critical, and different orders leave different critical sets. Three hundred random orders reached sets of sizes from 31 to 43 — 54 of them reached 31, more reached 33 and 35 — and none reached 30. The smallest has 17 orthogonal triads and 71 perpendicular pairs.

The thirty-one have a structure Peres’s set does not. Some of them lie in no triad at all and act only through perpendicular pairs, forbidding two of their partners from both being true. A few hub directions lie in three or more triads and carry most of the contradiction. The shrinking does not know any of this; it only knows which directions it cannot do without, and the structure emerges as what is left.

The menu matters. With coordinates from $\{0, \pm 1\}$ alone there are thirteen directions — the three axes, six face diagonals of a cube and four body diagonals — and only four orthogonal triads among them, since no body diagonal belongs to a triad; those thirteen can be labelled, by hand, in a few lines. Allowing $\pm 2$ brings the count to forty-nine directions and twenty-six triads, enough triads sharing enough directions for a contradiction to close. The value of a coordinate menu is not the number of directions it offers but the number of right angles among them, and integer coordinates make right angles scarce: two random directions are perpendicular with probability nought, and two directions with small integer coordinates only when a short sum of products happens to cancel.

Random shrinking finds local minima, not global ones. That it finds 31 often and 30 never is evidence, not proof, that 31 is the best this menu of coordinates can do, and nothing at all about other menus — a set of 30 might need coordinates like $\sqrt 3$ or $\tfrac12(1 + \sqrt 5)$ that the search never offers.

How rare a contradiction is #

A Kochen–Specker set is a carefully arranged object. Of four hundred sets of thirty-three directions drawn at random from the forty-nine, none has the property — every one can be labelled. Thirty-three directions are enough for a contradiction only when they are chosen to create many interlocking triads, and a random choice creates too few: most randomly chosen pairs of directions are not perpendicular at all, and the constraints that remain are easy to satisfy. The same is true of the hard instances of satisfiability, which are rare among random formulas until the number of clauses passes a threshold, and of the four-dimensional proof, where eighteen directions work only because each sits in exactly two bases.

Why three dimensions is harder #

The parity proof in four dimensions needs two things: every direction in an even number of the chosen bases, and an odd number of bases. Count the memberships two ways. Each basis has four directions, so there are $4B$ memberships for $B$ bases; each direction contributes an even number; so $4B$ is a sum of even numbers, which it always is, and nothing stops $B$ from being odd — nine, in the eighteen-direction proof.

In three dimensions the same count kills the method. Each triad has three directions, so there are $3B$ memberships, and if every direction lies in an even number of triads then $3B$ is even and $B$ is even too. No parity proof can exist in three dimensions, or in any odd dimension, because the number of bases is forced to be even by the very condition that makes each direction count twice. A proof there must be a genuine contradiction among overlapping triads, reached by following consequences, and its length depends on exactly how the triads interlock.

Andrew Gleason’s theorem of 1957 implies the Kochen–Specker theorem in three dimensions without exhibiting any set at all: every way of assigning probabilities to directions that respects orthogonal triads is given by a quantum state, and no quantum state gives only probabilities nought and one. It is a proof by continuity over all directions at once, and it says nothing about how few a finite witness needs. In four dimensions and above small parity proofs are known — eighteen directions in four dimensions has been shown by exhaustive search to be the fewest possible — and three dimensions is the one case where the best sets come from cleverness or search and the best lower bounds from searching all possible arrangements.

What a quantum state does instead #

Quantum mechanics has no trouble with these thirty-three directions, because it never labels them. A state assigns each direction a probability — the squared length of the state’s shadow on that direction — and for every orthogonal triad the three probabilities add to one, since the three shadows are the state’s coordinates in that triad. For the state along the axis $(0, 0, 1)$, the axis itself gets probability one, the directions perpendicular to it get nought, and $(1, 1, \sqrt 2)$, at an angle whose cosine is $\sqrt 2/2$, gets exactly a half. Every triad is satisfied, and no direction except the axis is certain.

That is the logic no table of truth values could capture: propositions that are neither true nor false but carry a weight, combined by rules that respect orthogonality and nothing more. A labelling is the special case where every weight is nought or one, and the Kochen–Specker sets are exactly the places where that special case is impossible. The finite set turns Gleason’s continuous theorem into a contradiction that can be written on a page.

Where the bounds stand #

The upper bound has stood at thirty-one since Conway and Kochen’s set appeared in Peres’s book of 1993. The lower bounds are a different kind of statement: that no arrangement of fewer directions in three-dimensional space has the property. Proving one means listing every possible pattern of orthogonalities among $n$ directions that could carry a contradiction — every graph in which triads are triangles and no two triangles share an edge, among other constraints — and showing each is either unlabellable only in principle and not realisable by real directions, or labellable. Felix Arends, Joël Ouaknine and Charles Wampler pushed the bound to 18 in 2011, Sander Uijlen and Bas Westerbaan to 22 in 2016, and Zhengyu Li, Curtis Bright and Vijay Ganesh to 24 in 2023, by combining satisfiability solvers with computer algebra that decides which orthogonality patterns can be drawn in space.

What the computations show and assume #

Every orthogonality in the figures is decided exactly, by whole-number arithmetic in $\mathbb{Z}[\sqrt 2]$ or $\mathbb{Z}$, and every claim that a set has no labelling comes with a complete search that anyone can rerun. What the computations do not show is minimality. The random shrinking finds the thirty-one by luck within a fixed menu of coordinates, and its failure to reach thirty says nothing about menus it does not search. The lower bound of twenty-four is a theorem from a different and much larger computation, cited rather than repeated.

Nor do the figures show what the theorem means physically, which is a matter of interpretation rather than mathematics. What they show is that the impossibility can be exhibited with thirty-one concrete directions, each a measurement that could be made on a spin-one particle, and that the obstruction is a finite combinatorial fact about those directions and their right angles.

Still open: the true minimum #

What is the smallest Kochen–Specker set in three dimensions? It has between 24 and 31 directions. Closing the gap from below means extending the exhaustive search past 24, where the number of candidate orthogonality patterns grows explosively and each must be tested for realisability in real three-dimensional space, which is a question about the solvability of polynomial equations. Closing it from above means finding a set of 30 or fewer, which no construction and no search over small coordinate menus has done. There is also a dual question with a different flavour: the set with the fewest triads, or the one whose contradiction is shortest to verify, need not be the set with the fewest directions, and for those measures the answers are less studied still.

A contradiction made of right angles #

In three dimensions no parity argument is available, and a Kochen–Specker proof is a genuine contradiction that a search must find. Peres’s thirty-three directions, built exactly from $\{0, \pm1, \pm\sqrt2\}$, have 16 triads and 72 perpendicular pairs, no labelling, and no redundant member; shrinking the forty-nine directions with coordinates from $-2$ to 2 in random orders reaches thirty-one, the size of Conway and Kochen’s set and still the smallest known. Exhaustive searches have shown that no set of 24 or fewer works, and between 24 and 31 the answer is not known.