Coloring the rational quantum sphere and the Kochen-Specker theorem

Hans Havlicek
Institut für Geometrie, Technische Universität Wien
Wiedner Hauptstraß e 8-10/1133, A-1040 Vienna, Austria
Günther Krenn and Johann Summhammer
Atominstitut der österreichischen Universitäten,
Stadionallee 2
A-1020 Vienna, Austria,
Karl Svozil
Institut für Theoretische Physik, Technische Universität Wien
Wiedner Hauptstraß e 8-10/136, A-1040 Vienna, Austria
(to whom correspondence should be directed)[    \tilde] svozil/publ/2000-co.{htm,ps,tex}


We review and extend recent findings of Godsil and Zaks [1], who published a constructive coloring of the rational unit sphere with the property that for any orthogonal tripod formed by rays extending from the origin of the points of the sphere, exactly one ray is red, white and black. They also showed that any consistent coloring of the real sphere requires an additional color. We discuss some of the consequences for the Kochen-Specker theorem [2].

1  Colorings

In what follows we shall consider ``rational rays.'' A ``rational ray'' is the linear span of a non-zero vector of Qn Rn.

Let p be a prime number. A coloring of the rational rays of Rn, n 1, using pn-1+pn-2++1 colors can be constructed in a straightforward manner. We refer to [3,4,5] for the theoretical background of the following construction.

Each rational ray is the linear span of a vector (x1,x2,,xn) Zn, where x1,x2,...,xn are coprime. Such a vector is unique up to a factor 1.

Next, let Zp be the field of residue classes modulo p. The vector space Zpn has pn -1 non-zero vectors; each ray through the origin of Zpn has p-1 non-zero vectors. So there are exactly (pn -1)/(p-1) = pn-1+pn-2++1 distinct rays through the origin which can be colored with pn-1+pn-2++1 distinct colors.

Finally, assign to the ray Sp(x1,x2,,xn) (``Sp'' denotes linear span) the color of the ray of Zpn which is obtained by taking the modulus of the coprime integers x1,x2,,xn modulo p. Observe that x1,x2,,xn cannot vanish simultaneously modulo p and that (x1,x2,,xn) yield the same color. Obviously, all pn-1+pn-2++1 colors are actually used.

In what follows, we consider the case p = 2, n = 3. Here all rational rays Sp(x,y,z) (with x,y,z Z coprime) are colored according to the property which ones of the components x,y,z are even (E) and odd (O). There are exactly 7 of such triples OEE, EOE, EEO, OOE, EOO, OEO, OOO which are associated with one of seven different colors #1,#2,#3,#4,#5,#6,#7. Only the EEE triple is excluded. Those seven colors can be identified with the seven points of the projective plane over Z2; cf. Fig. 1.

Picture Omitted

Figure 1: The projective plane over Z2. and the reduced coloring scheme discussed.

Next, we restrict our attention to those rays which meet the rational unit sphere S2Q3. The following statements on a triple (x,y,z) Z3 \{(0,0,0)} (not necessarily coprime) are equivalent:

(i) The ray Sp(x,y,z) intersects the unit sphere at two rational points; i.e., it contains the rational points ( x,y,z)/[(x2+y2+z2)] S2Q3.
(ii) The Pythagorean property holds, i.e., x2+y2+z2 = n2,  n N.

This equivalence can be demonstrated as follows. All points on the rational unit sphere can be written as r = ([a/(a)],[b/(b)],[c/(c)] ) with a,b,c Z, a,b,c Z\{0}, and ([a/(a)])2+([b/(b)])2+([c/(c)])2 = 1. Multiplication of r with a2b2c2 results in a vector of Z3 satisfying (ii). Conversely, from x2+y2+z2 = n2,  n N, we obtain the rational unit vector (x/n,y/n,z/n) S2Q3.

Notice that this Pythagorean property is rather restrictive. Not all rational rays intersect the rational unit sphere. For a proof, consider Sp(1,1,0) which intersects the unit sphere at (1/2)(1,1,0) S2Q3. Although both the set of rational rays as well as S2Q3 are dense, there are ``many'' rational rays which do not have the Pythagorean property.

If x,y,z are chosen coprime then a necessary condition for x2+y2+z2 being a non-zero square is that precisely one of x, y, and z is odd. This is a direct consequence of the observation that any square is congruent to 0 or 1, modulo 4, and from the fact that at least one of x, y, and z is odd. Hence our coloring of the rational rays induces the following coloring of the rational unit sphere with those three colors that are represented by the standard basis of Z23:

color #1 if x is odd, y and z are even,
color #2 if y is odd, z and x are even,
color #3 if z is odd, x and y are even.

All three colors occur, since the vectors of the standard basis of R3 are colored differently.

Suppose that two points of S2Q3 are on rays Sp(x,y,z) and Sp(x,y,z), each with coprime entries. The inner product xx+yy+zz is even if and only if the inner product of the corresponding basis vectors of Z23 is zero or, in other words, the points are colored differently. In particular, three points of S2Q3 with mutually orthogonal position vectors are colored differently.

From our considerations above, three colors are sufficient to obtain a coloring of the rational unit sphere S2Q3 such that points with orthogonal position vectors are colored differently, but clearly this cannot be accomplished with two colors. So the ``chromatic number'' for the rational unit sphere is three. This result is due to Godsil and Zaks [1]; they also showed that the chromatic number of the real unit sphere is four. However, they obtained their result in a slightly different way. Following [4] all rational rays are associated with three colors by making the following identification:
#2 = #4,
#3 = #5 = #6 = #7.
This 3-coloring has the property that coplanar rays are always colored by using only two colors; cf. Fig. 1. According to our approach this intermediate 3-coloring is not necessary, since rays in colors #4, #5, #6, #7 do not meet the rational unit sphere.

1.1  Reduced two-coloring

As a corollary, the rational unit sphere can be colored by two colors such that, for any arbitrary orthogonal tripod spanned by rays through its origin, one vector is colored by color #1 and the other rays are colored by color #2. This can be easily verified by identifying colors #2 & #3 from the above scheme. (Two equivalent two-coloring schemes result from a reduced chromatic three-coloring scheme by requiring that color #1 is associated with x or y being odd, respectively.)

Kent [6] has shown that there also exist dense sets in higher dimensions which permit a reduced two-coloring. Unpublished results by P. Ovchinnikov, O.G.Okunev and D. Mushtari [7] state that the rational d-dimensional unit sphere is d-colorable if and only if it admits a reduced two-coloring if and only if d < 6.

1.2  Denseness of single colors

It can also be shown that each color class in the above coloring schemes is dense in the sphere. To prove this, Godsil and Zaks consider a such that sina = 3/5 and thus cosa = 4/5. a is not a rational multiple of p; hence sin(na) and cos(na) are non-zero for all integers n. Let F be the rotation matrix about the z-axis through an angle a; i.e.,
F =


Then the image I, under the powers of F, of the point (1,0,0) is a dense subset of the equator.

Now suppose that the point u = ( a/c,b/c,0) is on the rational unit sphere and that a,c are odd and thus b is even. In the coloring scheme introduced above, u has the same color as (1,0,0) (identify a = c = 1 and b = 0); and so does Fu. This proves that I (the image of all powers of F of the points u) is dense. We shall come back to the physical consequences of this property later.

In the reduced two-color setting, if the two "poles" (0,0,1) acquire color #1, then the entire equator acquires color #2. Thus, for example, for the two tripods spanned by {(1,0,0),(0,1,0),(0,0,1)} and {(3,4,0),(-4,3,0),(0,0,1)}, the first two legs have color #2, while (0,0,1) has color #1.

1.3  The chromatic number of the real unit sphere in three dimensions is four

A proof that four colors suffice for the coloring of points of the unit sphere in three dimensions is constructive and rather elementary. Consider first the intersection points of the sphere with the the x-, the y- and the z-axis, colored by green, blue and red, respectively. There are exactly three great circles which pass through two of these three pairs of points. The great circles can be colored with the two colors used on the four points they pass through. The three great circles divide the sphere into eight open octants of equal area. Four octants, say, in the half space z > 0, are colored by the four colors red, white, green and blue. The remaining octants obtain their color from their antipodal octant.

Although Godsil and Zaks' [1] paper is not entirely specific, it is easy to write down an explicit coloring scheme according to the above prescription. Consider spherical coordinates: let q be the angle between the z-axis and the line connecting the origin and the point, and j be the angle between the x-axis and the projection of the line connecting the origin and the point onto the x-y-plane. In terms of these coordinates, an arbitrary point on the unit sphere is given by (q, j, r = 1) (q,j).

The fact that three colors are not sufficient is not so obvious. Here we shall not review Godsil and Zaks' proof based on a paper by A. W. Hales and E. G. Straus [4], but refer to a result of S. Kochen and E. Specker [2], which is of great importance in the present debate on hidden parameters in quantum mechanics. They have proven that there does not exist a reduced two-coloring, also termed valuation, on the one dimensional subspaces of real Hilbert space in three dimensions.

Recall that a reduced two-coloring of the one dimensional linear subspaces with two colors could immediately be obtained from any possible appropriate coloring of the sphere with three colors by just identifying two of the three colors. Thus, the impossibility of a reduced two-coloring implies that three colors are not sufficient for an appropriate coloring of the threedimensional real unit sphere. (``Appropriate'' here means: ``points at spherical distance p/2 get different colors.'')

In the same article [2], Kochen and Specker gave an explicit example (their G3) of a finite point set of the sphere with weaker properties which suffice just as well for this purpose: the structure still allows for a reduced two-coloring, yet it cannot be colored by three colors. (The authors did not mention nor discuss this particular feature [9].)

The impossibility of a reduced two-coloring also rules out another attempt to ``nullify'' the Kochen-Specker theorem by identifying pairs of colors of an appropriate four-coloring of the real unit sphere. Any such identification would result in tripods colored by #1-#2-#2, as well as for instance #1-#1-#2, which is not allowed for reduced coloring schemes, which requires colorings of the type #1-#2-#2.

2  Physical aspects

2.1  Physical truth values

Based on Godsil and Zaks [1] results, Meyer [10] suggested that the physical impact of the Kochen-Specker theorem [2] is ``nullified,'' since for all practical purposes it is impossible to operationalize the difference between any dense set of rays and the continuum of Hilbert space rays. (See also the subsequent papers by Kent [6] and Clifton and Kent [11].) However, for the reasons given below, the physical applicability of these constructions remain questionable.

Let us re-state the physical interpretation of the coloring schemes discussed above. Any linear subspace Sp r of a vector r can be identified with the associated projection operator Er and with the quantum mechanical proposition ``the physical system is in a pure state Er'' [12]. The coloring of the associated point on the unit sphere (if it exists) is equivalent with a valuation or two-valued probability measure
Pr:Er {0,1}
where 0 ~ #2 and 1 ~ #1. That is, the two colors #1, #2 can be identified with the classical truth values: ``It is true that the physical system is in a pure state Er'' and ``It is false that the physical system is in a pure state Er,'' respectively.

Since, as has been argued before, the rational unit sphere has chromatic number three, two colors suffice for a reduced coloring generated under the assumption that the colors of two rays in any orthogonal tripod are identical. This effectively generates consistent valuations associated with the dense subset of physical properties corresponding to the rational unit sphere [10].

Kent [6] has shown that there also exist dense sets in higher dimensions which permit a reduced two-coloring. Unpublished results by P. Ovchinnikov, O.G.Okunev and D. Mushtari [7] state that the rational unit sphere of the d-dimensional real Hilbert space is d-colorable if and only if it admits a reduced two-coloring if and only if d < 6.

2.2  Sufficiency

The Kochen-Specker theorem deals with the nonembedability of certain partial algebras-in particular the ones arising in the context of quantum mechanics-into total Boolean algebras. 0-1 colorings serve as an important method of realizing such embeddings: e.g., if there are a sufficient number of them to separate any two elements of the partial algebra, then embedability follows [2,13,14]. Kochen and Specker's original paper [2] contains a much stronger result-the nonexistence of 0-1 colorings-than would be needed for nonembedability. However, the mere existence of some homomorphisms is a necessary but no sufficient criterion for embedability. The Godsil and Zaks construction merely provides three homomorphisms which are not sufficient to guarantee embedability. This has already be pointed out by Clifton and Kent [11].

2.3  Continuity

The regress to unsharp measurements is rather questionable and would allow total arbitrariness in the choice of approximation. That is, due to the density of the coloring, depending on which approximation is chosen, one predicts different results. The probabilities resulting from these truth assignments are noncontinuous and arbitrary. This is even more problematic if one realizes that the each color of the 0-1 coloring of the rational unit sphere is dense.

2.4  Closedness

The rational unit sphere is not closed under certain geometrical operations such as taking an orthogonal ray of the subspace spanned by two non-collinear rays (the cross product of the associated vectors). This can be easily demonstrated by considering the two vectors

, 4


0, 4
, 3

The cross product thereof is

, -9
, 12


Indeed, if instead of S2Q3 one would start with three non-orthogonal, non-collinear rational rays and generate new ones by the cross product, one would end up with all rational rays [15].

In the Birkhoff-von Neumann approach to quantum logics [16], this non-closedness under elementary operations such as the nor-operation might be considered a serious deficiency which rules out the above model as an alternative candidate for Hilbert space quantum mechanics. (However, his argument does not apply to the Kochen-Specker partial algebra approach to quantum logic, since there operations among propositions are only allowed if the propositions are comeasurable.)

Informally speaking, the relative (with respect to other sets such as the rational rays) ``thinness'' guarantees colorability. In such a case, the formation of finite cycles such as the ones introduced by Kochen and Specker [2] are impossible.

To put it differently: given any nonzero measurement uncertainty e and any non-colorable Kochen-Specker graph G(0) [2,17], there exists another graph (in fact, a denumerable infinity thereof) G(d) which lies inside the range of measurement uncertainty d e [and thus cannot be discriminated from the non-colorable G(0)] which can be colored. Such a graph, however, might not be connected in the sense that the associated subspaces can be cyclically rotated into itself by local transformation along single axes. The set G(d) might thus correspond to a collection of tripods such that none of the axes coincides with any other, although all of those non-identical single axes are located within d apart from each other. Indeed, this appears to be precisely how the Clifton-Kent construction works [11].

The reason why a Kochen-Specker type contradiction does not occur in such a scenario is the impossibility to ``close'' the argument; to complete the cycle: the necessary propositions are simply not available in the rational sphere model. For the same reason, an equilateral triangle does not exist in Q2 [9]. Yet, while these findings seem to contradict the conclusions of Clifton and Kent [11], we would like to emphasize that this does not relate to their formal arguments but rather is a matter of interpretation and a question of how much should be sacrificed for value definiteness.

Thus, although the colorings of rational spheres offer a rather unexpected possibility to define consistent classical models, a closer examination shows that any such colorings should be excluded for physical reasons.


The authors would like to acknowledge stimulating discussions with Ernst Specker.


C. D. Godsil and J. Zaks. Coloring the sphere. University of Waterloo research report CORR 88-12, 1988.

Simon Kochen and Ernst P. Specker. The problem of hidden variables in quantum mechanics. Journal of Mathematics and Mechanics, 17(1):59-87, 1967. Reprinted in [18].

Wilhelm Klingenberg. Projektive Geometrien mit Homomorphismus. Math. Ann., 132:180-200, 1956.

A.W. Hales and E.G. Straus. Projective colorings. Pac. J. Math., 99:31-43, 1982.

David S. Carter and Andrew Vogt. Collinearity-preserving functions between Desarguesian planes. Mem. Am. Math. Soc., 235:98, 1980.

Adrian Kent. Non-contextual hidden variables and physical measurements. Physical Review Letters, 83(19):3755-3757, 1999. arXiv:quant-ph/9906006.

Peter Ovchinnikov. private e-mail communication in May 2000.

Ernst Specker. Die Logik nicht gleichzeitig entscheidbarer Aussagen. Dialectica, 14:175-182, 1960. Reprinted in [18]; English translation: The logic of propositions which are not simultaneously decidable, reprinted in [19].

Ernst Specker. private communication, 1999.

David A. Meyer. Finite precision measurement nullifies the Kochen-Specker theorem. Physical Review Letters, 83(19):3751-3754, 1999. arXiv:quant-ph/9905080.

Rob Clifton and Adrian Kent. Simulating quantum mechanics by non-contextual hidden variables. Proc. R. Soc. Lond., A 456:2101-2114, 2000. arXiv:quant-ph/9908031 v4.

John von Neumann. Mathematische Grundlagen der Quantenmechanik. Springer, Berlin, 1932. English translation: Mathematical Foundations of Quantum Mechanics, Princeton University Press, Princeton, 1955.

Pavel Pták and Sylvia Pulmannová. Orthomodular Structures as Quantum Logics. Kluwer Academic Publishers, Dordrecht, 1991.

Karl Svozil and Josef Tkadlec. Greechie diagrams, nonexistence of measures in quantum logics and Kochen-Specker type constructions. Journal of Mathematical Physics, 37(11):5380-5401, November 1996.

Hans Havlicek and Karl Svozil. Density conditions for quantum propositions. Journal of Mathematical Physics, 37(11):5337-5341, November 1996.

Garrett Birkhoff and John von Neumann. The logic of quantum mechanics. Annals of Mathematics, 37(4):823-843, 1936.

K. Svozil. Quantum Logic. Springer, Singapore, 1998.

Ernst Specker. Selecta. Birkhäuser Verlag, Basel, 1990.

Clifford Alan Hooker. The logico-algebraic approach to quantum mechanics. D. Reidel Pub. Co., Dordrecht; Boston, [1975]-1979.

File translated from TEX by TTH, version 2.69.
On 20 Feb 2001, 12:36.