At the heart of the Conway-Kochen Free Will theorem and Kochen and Specker's argument against non-contextual hidden variable theories is the existence of a Kochen-Specker (KS) system: a set of points on the sphere that has no 0,1-coloring such that at most one of two orthogonal points are colored 1 and of three pairwise orthogonal points exactly one is colored 1. In public lectures, Conway encouraged the search for small KS systems. At the time of writing, the smallest known KS system has 31 vectors. Arends, Ouaknine and Wampler have shown that a KS system has at least 18 vectors, by reducing the problem to the existence of graphs with a topological embeddability and non-colorability property. The bottleneck in their search proved to be the sheer number of graphs on more than 17 vertices and deciding embeddability. Continuing their effort, we prove a restriction on the class of graphs we need to consider and develop a more practical decision procedure for embeddability to improve the lower bound to 22.
At the heart of the Conway-Kochen Free Will theorem and Kochen and Specker's argument against non-contextual hidden variable theories is the existence of a Kochen-Specker (KS) system: a set of points on the sphere that has no 0,1-coloring such that at most one of two orthogonal points are colored 1 and of three pairwise orthogonal points exactly one is colored 1. In public lectures, Conway encouraged the search for small KS systems. At the time of writing, the smallest known KS system has 31 vectors. Arends, Ouaknine and Wampler have shown that a KS system has at least 18 vectors, by reducing the problem to the existence of graphs with a topological embeddability and non-colorability property. The bottleneck in their search proved to be the sheer number of graphs on more than 17 vertices and deciding embeddability. Continuing their effort, we prove a restriction on the class of graphs we need to consider and develop a more practical decision procedure for embeddability to improve the lower bound to 22.
Kochen-Specker (KS) vector systems are sets of vectors in R^3 with the property that it is impossible to assign 0s and 1s to the vectors in such a way that no two orthogonal vectors are assigned 0 and no three mutually orthogonal vectors are assigned 1. The existence of such sets forms the basis of the Kochen-Specker and Free Will theorems. Currently, the smallest known KS vector system contains 31 vectors. In this paper, we establish a lower bound of 18 on the size of any KS vector system. This requires us to consider a mix of graph-theoretic and topological embedding problems, which we investigate both from theoretical and practical angles. We propose several algorithms to tackle these problems and report on extensive experiments. At the time of writing, a large gap remains between the best lower and upper bounds for the minimum size of KS vector systems.
We look at generalisations of sets of vectors proving the Kochen-Specker theorem in 3 and 4 dimensions. It has been shown that two such sets, although unitarily inequivalent, are part of a larger 3-parameter family of vectors that share the same orthogonality graph. We find that these sets are unusual, in that the vectors in all other Kochen-Specker sets investigated here are fully determined by orthog-onality conditions and thus admit no free parameters. The Kochen-Specker (KS) theorem [1] is a statement about the fundamen-tal nature of quantum mechanics: no non-contextual hidden variable theory can reliably reproduce quantum mechanical predictions. The KS theorem states that in a Hilbert space with dimension n ≥ 3 it is impossible to assign definite values v ∈ {0, 1} to m projection operators Pm so that for every commuting set of projection operators satisfying Pm = I, the correspond-ing definite values obey v (Pm) = 1. The KS theorem is often visualised by means of a set of "uncolourable" vectors, where projection operators are represented by their constituent rays in Hilbert space and rays can be simplified to vectors as only directions are relevant here. The vectors are coloured according to their pre-assigned val-ues and the summation conditions above translate into colouring rules. This allows us to construct orthogonality graphs that, when uncolourable, pro-vide a contradiction within non-contextual hidden variable models and thus a proof of the KS theorem. Sets of vectors exemplifying the KS theorem have been discovered by nu-merous authors, with an aim to reduce the number of vectors required to reach a contradiction. Most notably, in a 3-dimensional Hilbert space, the original KS proof of 117 vectors has been replicated with sets using between 31 and 33 vectors [2, 3, 4, 5] and in a 4-dimensional Hilbert space, sets of between 24 and the lower limit of 18 vectors have been realised [2, 6, 7]. Additionally, an extensive computer search has recently revealed over one thousand of such KS sets in R4 [8]. In a publication by E. Gould and P. K. Aravind [10], two of these sets in 3 dimensions have been shown to share the same orthogonality graph. Specifically, the sets of 33 vectors found by Penrose [3] and Peres [2] have
The challenge of determining bounds for the minimal number of vectors in a three-dimensional Kochen-Specker (KS) set has captivated the quantum foundations community for decades. This paper establishes a weak lower bound of 10 vectors, which does not surpass the current best-known bound of 24 vectors. By exploring the complementary concept of large non-KS sets and employing a probability argument independent of the graph structure of KS sets, we introduce a technique that could be applied in the future to derive tighter bounds. Additionally, we highlight an intriguing connection to a generalization of the moving sofa problem in navigating a right-angled hallway on the surface of a two-dimensional sphere.
Abstract We show that there is no non-constant assignment of zeros and ones to points of a unit sphere in R3 R 3 such that for every three pairwisely orthogonal vectors, an odd number of them is assigned 1. This is a new strengthening of the Bell–Kochen–Specker theorem, which proves the non-existence of hidden variables in quantum theories.
In Phys. Rev. Lett. 135, 190203 (2025) a discovery of the simplest 3D contextual set with 33 vertices, 50 bases, and 14 complete bases is claimed. In this paper, we show that it was previously generated in Quantum 7, 953 (2023) and analyze the meaning, origin, and significance of the simplest contextual sets in any dimension. In particular, we prove that there is no ground to consider the aforementioned set as fundamental since there are many 3D contextual sets with a smaller number of complete bases. We also show that automatic generation of contextual sets from basic vector components automatically yields all known minimal contextual sets of any kind in any dimension and therefore also the aforementioned set in no CPU-time. In the end, we discuss varieties of contextual sets, in particular Kochen-Specker (KS), extended KS, and non-KS sets as well as ambiguities in their definitions.
One of the fundamental results in quantum foundations is the Kochen–Specker (KS) theorem, which states that any theory whose predictions agree with quantum mechanics must be contextual, i.e., a quantum observation cannot be understood as revealing a pre-existing value. The theorem hinges on the existence of a mathematical object called a KS vector system. While many KS vector systems are known, the problem of finding the minimum KS vector system in three dimensions (3D) has remained stubbornly open for over 55 years. To address the minimum KS problem, we present a new verifiable proof-producing method based on a combination of a Boolean satisfiability (SAT) solver and a computer algebra system (CAS) that uses an isomorph-free orderly generation technique that is very effective in pruning away large parts of the search space. Our method shows that a KS system in 3D must contain at least 24 vectors. We show that our sequential and parallel Cube-and-Conquer (CnC) SAT+CAS methods are significantly faster than SAT-only, CAS-only, and a prior CAS-based method of Uijlen and Westerbaan. Further, while our parallel pipeline is somewhat slower than the parallel CnC version of the recently introduced Satisfiability Modulo Theories (SMS) method, this is in part due to the overhead of proof generation. Finally, we provide the first computer-verifiable proof certificate of a lower bound to the KS problem with a size of 40.3 TiB in order 23.