# Full text of "Equations, States, and Lattices of Infinite-Dimensional Hilbert Spaces"

## See other formats

International Journal of Theoretical Physics, 39, 2337-2379 (2000). 2 ; Equations and State and Lattice Properties That Hold ^ ; in Infinite Dimensional Hilbert Space x By a (N en ; Norman D. Megill"']^ and Mladen Pavicic^Q 00 g ; ^Boston Information Group, 30 Church St., Belmont MA 02478, U. S. A. Q>^ ' ^Dept. of Physics, University of Maryland, Baltimore County, Baltimore, MD 21250, U. S. A. O ■ and University of Zagreb, Gradjevinski Fakultet, Kaciceva 26, HR-10000 Zagreb, Croatia. O :^ -4— > ' P3 ■ Abstract. We provide several new results on quantum state space, on lattice of subspaces of an 2 ' infinite dimensional Hilbert space, and on infinite dimensional Hilbert space equations as well as Q^i on connections between them. In particular we obtain an n-variable generalized orthoarguesian equation which holds in any infinite dimensional Hilbert space. Then we strengthen Godowski's result by showing that in an ortholattice on which strong states are defined Godowski's equations ;J] ■ as well as the orthomodularity hold. We also prove that all 6- and 4-variable orthoarguesian equations presented in the literature can be reduced to new 4- and 3- variable ones, respectively and that Mayet's examples follow from Godowski's equations. To make a breakthrough in testing these massive equations we designed several novel algorithms for generating Greechie diagrams with an arbitrary number of blocks and atoms (currently testing with up to 50) and for automated checking of equations on them. A way of obtaining complex infinite dimensional Hilbert space from the Hilbert lattice equipped with several additional conditions and without invoking the notion of state is presented. Possible repercussions of the results to quantum computing problems are discussed. PACS numbers: 03.65, 02.10, 05.50 Keywords: Hilbert space, Hilbert lattice, orthoarguesian property, strong state, quantum logic, quantum computation, Godowski equations, orthomodular lattice ^E-mail: nni@aluni.niit.edu; Web page: http://www.shore.net/~ndni/java/nini.htnil ^E-mail: mpavicic@faust.irb.hr; Web page: http://m3k.grad.hr/pavicic Megill and Pavicic (2000) 1 Introduction Recent theoretical and experimental developments in the field of quantum computing opened the possibility of using quantum mechanical states, their superpositions, and operators de- fined on them — i.e., the Hilbert space formalism — to exponentially speed up computation of various systems, on the one hand, and to simulate quantum systems, on the other. Quantum computers can be looked upon as parallel computing machines. Looking at the speed of com- putation, the difference between classical and quantum parallel machines is that in a classical one we increase its speed by increasing its physical space (occupied by electronic components: processors, etc.) while in a quantum one we achieve this by exponentially increasing its state space by means of linearly increased physical space (a register of n quantum bits — quhits — prepares a superposition of 2^ states). To make a quantum parallel machine compute a particular problem is tricky and requires a great deal of ingenuity but a computed system itself need not be quantum and need not be simulated. Actually, all algorithms designed so far are of such a kind. For example, Shor's algorithm [|I| factors n-digit numbers, Grover's algorithm searches huge databases, and Boghosian- Taylor's algorithm computes the Schrodinger equation. As opposed to this, a quantum simulator would simulate a quantum system (e.g., an atom, a molecule,. . . ) and give its final state directly: a quantum computer working as a quantum simulator would not solve the Scrodinger equation but would simulate it and the outputs would be its solutions — by typing in a Hamiltonian at a console we would simulate the system. Quantum simulation of quantum systems describable in the Hilbert space formalism (by the Scrodinger equation) would however only then be possible if we found an algebra underlying Hilbert space in the same way in which the Boolean algebra underlies classical state space. Such an algebra for quantum computers has recently been named quantum logic in some analogy to classical logic for classical computer. |^ However, this name is misleading for both types of computers because proper logics, both classical and quantum, have at least two models each. [Q Classical logic has not only a Boolean algebra but also a non-orthomodular algebra as its model and quantum logic not only an orthomodular algebra (Hilbert space) but also another non-orthomodular algebra: a weakly orthomodular lattice. What resolves this ambiguity is that as soon as we require either a numerical or a probabilistic evaluation of the propositions of classical logic we are left only with the Boolean algebra [Q and that as soon as we impose probabilistic evaluation (states) on quantum logic we are left only with Hilbert space. Therefore quantum logic itself does not to play a role in the current description of quantum systems. Its standard model — Hilbert space — does. One can make Hilbert space operational on a quantum computer by imposing lattice Megill and Pavicic (2000) 3 equations that hold in any Hilbert space on the computer states using quantum gates. Unfortunately not very much is known about the equations — explorations of Hilbert space have so far been concentrated on the operator theory leaving the theory of the subspaces of a Hilbert space (wherefrom we obtain these equations) virtually unexplored. So, in this paper we investigate how one can arrive at such equations starting from both algebraic and probabilistic structures of Hilbert space of quantum measurement and computation. We obtain several new results on these structures, give a number of new Hilbert space equations, and systematize, significantly simplify, and mutually reduce already known equations. In Section ^ we give several new characterizations of orthomodularity which we make use of later on. In Section ^ we consider ways in which states can be defined on an ortholattice underlying Hilbert space and make it orthomodular — when quantum, and distributive — when classical. We also analyze several kinds of equations characteristic of strong states in Hilbert space (Godowski's and Mayet's). On the other hand we present a way of obtaining complex Hilbert space from the Hilbert lattice equipped with several additional conditions but without invoking the notion of state. In Section ^ we give a new way of presenting orthoarguesian equations and their consequences which must hold in any Hilbert space and for which it is not known whether they are characteristic of the states or not. We reduce the number of variables used in the orthoarguesian-like equations in the literature (from 6 to 4 for the standard orthoarguesian equation and to 3 for all its consequences), we show that all consequences that appear in the literature reduce to a single 3-variable equation, and find a new one which does not. In Section ^we present generalizations of orthoarguesian equations that must hold in any Hilbert space. This previously unknown and unconjectured result is our most important contribution to the theory of infinite dimensional Hilbert spaces in this paper. In Section |^ we show several distributive properties that must hold in any Hilbert space. 2 Orthomodular Lattice Underlying Hilbert Space Closed subspaces of Hilbert space form an algebra called a Hilbert lattice. A Hilbert lat- tice is a kind of orthomodular lattice which we, in this section, introduce starting with an ortholattice which is a still simpler structure. In any Hilbert lattice the operation meet, a Ob, corresponds to set intersection. Ha f] '^b, of subspaces Ha, Ht of Hilbert space H, the ordering relation a < b corresponds to Ha C Hb, the operation join, aU b, corresponds to the smallest closed subspace of H containing Ha [jHb, and a' corresponds to H-^, the set of vectors orthogonal to all vectors in Ha- Within Hilbert space there is also an operation which has no a parallel in the Hilbert lattice: the sum of two subspaces Ha + Ht which is defined as the set of sums of vectors from Ha and Hb- We also have Ha+H^ = H- One can define all the lattice operations on Hilbert space itself following the above definitions {Ha^Hb = Ha fl ^b; etc.). Thus we have HaV^Hb = Ha + Hb = (Ha + Hb)^^ = (^f n^^)^>i> P- 175] where Wc is a closure of He, and therefore Ha + Hb ^ Ha U Hb- When H is finite dimensional or when the closed subspaces Ha and Hb are orthogonal to each other then Ha + Hb = Ha U Hb- [0, pp. 21-29], i, pp. 66,67], § pp. 8-16] Megill and Pavicic (2000) 4 The projection associated with Ha is given by Pa{x) = y for vector x from H that has a unique decomposition x = y + z ior y from Ha and z from H^- The closed subspace belonging to P is Hp = {x E H\P{x) = x}. Let Pa fl P;, denote a projection on Ti^ fl Hb, PaU Pb a projection on Ha U TYb, P^ + P;, a projection on Ha + Hb if Ha -L Tib, and let Pa < Pb mean Ha C Hfe. Thus a fl 6 corresponds to P^ n F,, = lim„^oo(PaPfe)",[|, P- 20] a' to /-P„ aUfeto P.UPfe = / -lim„^oo[(/- Pa) (/-Pfe)]M, p. 21] and a < 6 to P, < P^. a < fe also corresponds to either Pa = PaPb or to Pa = PbPa or to Pa — Pb = Pant'- Two projectors commute iff their associated closed subspaces commute. This means that (see Definition 2.5 ) a n (a' U 6) < b corresponds to PaPb = PbPa- In the latter case we have: P^ fl P;, = PaPb and PaUPb = Pa + Pb- PaPb- a ± b, i.e., Pa ± Pb is characterized by PaPb = 0. [|, pp. 173-176], i, pp. 66,67], i pp. 18-21], H pp. 47-50], In this section we give several definitions of an orthomodular lattice, two of which (given by Theorem p.8[) are new. In Section ^ we then show that the orthomodularity of an ortho- lattice is a consequence of defining strong states on the ortholattice and in Sections ^ and § we show that it also a consequence of other more restrictive lattice conditions: Godowski equations and orthoarguesian equations. Definition 2.1. An ortholattice (^OLj is an algebra {Cq,' , fl, U) such that the following con- ditions are satisfied for any a, b, c, d, e, f,g,hE Cq: (6n(cna))Ua = a (2.1) ((a n (6 n (/ U c))) U d) U e = ((((^ n g') u (c' n /')') n (a n b)) U e) u {{h ud)nd) (2.2) Lemma 2.2. The following conditions hold in any OL.- aUb = bUa, (aU6)Uc = aU(6Uc), a" = a, aU [af] b) = a, aHb = (a' U b')' . Also an algebra in which these conditions hold is an OL. Proof. As given in Ref. Illl. D Definition 2.3. An orthomodular lattice ('OMLj is an ortholattice in which any one of the following hold a =i b = 1 =^ a = b, i = l,...,5 (2.3) holds, where a =i b = {a — >,; b) fl (6 ^o Ci)i "^ = l)---)5, where a ^q b = a' U b, a ^i b = a' U (a n b), a ^2 b = b' ^1 a', a ^3 b = {a' n b) U {a' n b') U (a ^1 b), a ^4 b = b' ^3 a', and a -.5 b = (a n 6) U (a' nb)U {a' H b'). The equivalence of this definition to the other definitions in the literature follows from Lemma 2.1 and Theorem 2.2 of and the fact that Eq. (|2.3| ) fails in lattice 06 (Fig. |l]a), meaning it implies the orthomodular law by Theorem 2 of ||^, p. 22]. Definition 2.4. a = b= ianb)U (a' n b') (2.4) Megill and Pavicic (2000) We note that a = b = a =5 b holds in all OMLs, so these two identities may be viewed as alternate definitions for the same operation in OMLs. The equality also holds in lattice 06, so they may be used interchangeably in any orthomodular law equivalent added to ortholattices; in particular = may be substituted for =5 in the i = 5 case of Eq. (|2.3|) . However a = b = a =5 b does not hold in all ortholattices as shown in 0, so the two identities should be considered to be different operations from an ortholattice point of view. Definition 2.5. We say that a and b commute in OML and write aCb when either of the following equations hold: /jlj, [7^/ a= {{anb)U {anb')) an{a' Ub) <b (2.5) (2.6) Lemma 2.6. An OL in which Equations ( \2.^ and (\2.(^ follow from each other is an OML Yet other forms of the orthomodularity condition are the following ones. Lemma 2.7. An OL in which any one of the following conditions hold is an OML and vice versa. ■,.b ^ a < b, 1,...,5 (2.7) Proof. The proof of Eq. (|2.7| ) is given in [Q and [|15[. We stress that any OL. direction holds in D Figure 1: (a) Lattice 06; (b) Lattice M02. Later on we shall make use of a definition based on the following "transitivity" theorem which does not work for =j, z = 1, . . . , 4. Note that in any OML a = b = (a fl 6) U (a' fl 6') = (a — >-j b) n (6 — i>i a) for i = 1, . . . ,5 and that instead of the above Definition p.3| one can use one with a =1 b = {a -^i b) fl {b -^^ a), etc. Theorem 2.8. An ortholattice in which {a = b)n{b = c) < a c {a = b)n{b = c) = {a = b)n{a = c) hold is an orthomodular lattice and vice versa. (2.8) (2.9) The same statement holds for (a —>-i b) fl {b a = b. a 1, . . . , 5 being substituted for Megill and Pavicic (2000) Proof. Equations ( |2.8| ) and ( p.9| ) fail in lattice 06, so they imply the orthomodular law. For the converse with Eq. ( [27^ ) we start with {{a (lb) Li {a' fl 6')) fl {b' U (6 fl c)). It is easy to show that (a' n b')C{b' U (6 n c)) and (a' n b')C{a Ub). By applying the Foulis-HoUand theorem (which we shall subsequently refer to as F-H) ||l2| to our starting expression we obtain: ((a n fe) H (6' U (6 H c))) U ((a' n b') n (6' U (fe H c))). The first conjunction is by orthomodularity equal to a fl 6 fl c. The disjunction is thus equal or less than a' U (a fl c) and we arrive at (a = 6) fl (6 — >i c) < (a — >i c). By multiplying both sides by (c — >i b) we get (a = 6) n (6 = c) < (c — »i 6) fl (a — i>i c) < (a — i>i c). By symmetry we also have (a = fe) n (6 = c) < (c — i>i a). A combination of the latter two equations proves the theorem. We draw the reader's attention to the fact that (a — >i 6) fl (6 = c) < (a ^i c) does not hold in all OMLs (it is violated by M02). For the converse with Eq. ( ^.91 ) we start with Eq. ( p.8| ) and obtain (a = 5) fl (6 = c) < (a = 5) fl (a = c). On the other hand, starting with (a = b) n {a = c) < {b = c) we obtain (a = 6) fl (6 = c) < (a = 6) fl (a = c). Therefore the conclusion. As for the statements with (a — >j b) fl (6 -^j a), i = 1, . . . , 5 substituted for a = 6 they fail in 06, so they imply the orthomodular law. For the converse it is sufficient to note that in any OML the following holds: (a — s>j b) fl (6 — >j a)=a = b, i = l,...,5 O We conclude this section with an intriguing open problem whose partial solutions we find with the help of states defined on OML in the next section. Theorem 2.9. In any OML the following conditions follow from each other. {a = b)r]{{b = c)U{a = c)) < (a = c) (2.10) (a = b)^oi{a = c) = ib = c)) = 1 (2.11) {a = b)r]{{b = c)U{a = c)) = {{a = b)n{b = c))U{{a = b)n{a = c)) (2.12) Eq. I ^KWi ) fails in 06. Eqs. I ^ll\ ) and ( ^1^ ) fail m lattices m which weakly OML (WOMLj fail / fig/ but do not fail in 06. Proof. To obtain Eq. (|2Tl| ) from Eq. (|2:T0| ) we apply Lemma ^(z = 1): 1 = (a = 6)'U((6 = c)' n (a = c)') U (((a = c) n (a = 6)) n ((6 = c) U (a = c))) = [Eq. (pj)] = {a = b)' U ((a = c) n (6 = c)) U ((a = c)' n (6 = c)'). Reversing the steps yields ( p^ from (g]Tl|). To get Eq. ( |2.12| ) we first note that one can easily derive (a = 6) fl ((6 = c) U (a = c)) [a = c) n (a = 6) from Eq. ( pAO| ). Then one gets ( p32D by applying Eq. (^. To arrive at Eq. ( |2.1(]| ) starting from Eq. ( |2.12| ) we apply Eq. ( p.9| ) and reduce the right hand side of Eq. (^l2D to (a = 6) n (a = c) what yields Eq. (^lOl) . D An open problem is whether conditions ( p.llD and ( |2.12| ) hold in any WOML and whether these conditions together with condition (|2.1CI|) hold in any OML. Note that Eq. (|2.10|) fails in 06 only because Eqs. ( |2.9| ) and (|2.8| ), which we used to infere it from Eq. ( p. 121) , fail in Megill and Pavicic (2000) 7 06. We scanned all available orthoniodular Greechie lattices^ with up to 14 blocks (without legs and with 3 atoms in a block; this makes 271930 legless lattices), over 400000 lattices with up to 17 blocks, and selected lattices with up to 38 blocks, but there was no violation of any of them by the Eq. (|2.10|) , so, there is a strong indication that these conditions might hold in any OML, but we were not able to either prove or disprove this. We think it is an intriguing problem because repeated attempts to prove these conditions either in WOML, or in OML, or in Hilbert space always brought us into a kind of a vicious circle and also because we were unable to prove that an even weaker condition holds in any OML. We have, however, proved that the latter condition holds in Hilbert space and we give the proof in the next section (Equation |3.30| ). 3 States and Their Equations In the standard approach of reconstructing Hilbert space one starts from an orthomodular lattice, OML, then defines a state on OML, and imposes additional conditions on the state as well on OML to eventually arrive at the Hilbert space representation of such a mixed lattice-state structure. [To get an insight into the latter structure, below we first define a state on a lattice and pinpoint a difference between classical and quantum strong states (Definitions ^]1] and |3.1| and Theorems |3.3| , |3.8| , and p.lO| ).] Alternatively one can reconstruct Hilbert space solely by means of the lattice theory. We start with an ortholattice, OL, build the Hilbert lattice (Definition |3.4| and Theorem |3.5|) and with the help of three additional axioms arrive at its complex Hilbert space representation (Theorem |3.6|) without invoking the notion of state at all. The states needed for obtaining mean values of measured observables follow from Gleason's theorem. Going back to the traditional approach we explore how far one can go in reconstructing the Hilbert space starting with a strong state defined on OL without invoking any further either lattice or state condition. We show that strong quantum states imposed on OL turn the latter into an OML in which the so-called Godowski equations hold and obtain several new traits of the equations and much simpler than original Greechie lattices that characterize them (Theorems and Lemmas |3.10| - |3rT9| and |3.21| - ^r2^ . In the end we derive Mayet's equations from Godowski's (Theorem 3.20| ). Definition 3.1. A state on a lattice L is a function m : L — > [0, 1] (for real interval [0, 1]) such that m{l) = 1 and a ± 6 ^ m{a U b) = m{a) + m{b), where a ± 6 means a < h' . This implies m{a) + m{a') = 1 and a < b ^ m{a) < m{b). ■^We obtain the Greechie lattices with practically arbitrary number of atoms and blocks by us- ing the technique of isomorph-free exhaustive generation^lq. The reader can retrieve many lattices with up to 38 atoms and blocks at ftp : //cs . anu . edu . au/pub/people/bdm/nauty/greechie . html and ftp://m3k.grad.hr/pavicic/greechie/diagrams (legless), and a program for making an y desired set of lattices written in C by B. D. McKay at ftp : //m3k . grad . hr/pavicic/greechie/progranj Megill and Pavicic (2000) 8 Definition 3.2. A nonempty set S of states on L is called a strong set o/ classical states if (3mG 5)(Va,6GL)((m(a) = 1 ^ m(6) = 1) ^ a < b) (3.1) and a strong set o/ quantum states if {\/a,bEL){3me S){{m{a) = l =^ m(6) = 1) ^ a < b) . (3.2) We assume that L contains more than one element and that an empty set of states is not strong. Whenever we omit the word "quantum" we mean condition l\3.2j. The first part of Definition ^7^ we have not seen in the literature but consider it worth defining it because of the following theorem. Theorem 3.3. Any ortholattice that admits a strong set of classical states is distributive. Proof. Eq. ( p.2|) follows from Eq. (|3.1| ) and by Theorem 3.1C an ortholattice that admits a strong set of classical states is orthomodular. Let now a and b be any two lattice elements. Assume, for state m, that m{b) = 1. Since the lattice admits a strong set of classical states, this implies 6 = 1, so m{a (1 b) = m{a fl 1) = m{a). But m{a') + m{a) = 1 for any state, so m{a ^1 b) = m{a') + m{a fl 6) = 1. Hence we have m{b) = 1 ^ m{a — ^i b) = 1, which means (since the ortholattice admits a strong set of classical states) that b < a ^i b. This is another way of saying aCb. |]13[ By F-H, an orthomodular lattice in which any two elements commute is distributive. D We see that that a description of any classical measurement by a classical logic (more precisely by its lattice model, a Boolean algebra) and by a classical probability theory coin- cide, because we can always find a single state (probability measure) for all lattice elements. As opposed to this, a description of any quantum measurement consists of two inseparable parts: a quantum logic (i.e., its lattice model, an orthomodular lattice) and a quantum probability theory, because we must obtain different states for different lattice elements. In order to enable an isomorphism between an orthocomplemented orthomodular lattice and the corresponding Hilbert space we have to add further conditions to the lattice. These conditions correspond to the essential properties of any quantum system such as superposi- tion and make the so-called Hilbert lattice as follows. fl2 Definition 3.4. An OML which satisfies the following conditions is a Hilbert lattice, HL. 1. Completeness: The meet and join of any subset of an HL always exist. 2. Atomic: Every non-zero element in an HL is greater than or equal to an atom. (An atom a is a non-zero lattice element with < b < a only if b = a.) 3. Superposition Principle: (The atom c is a superposition of the atoms a and b if c ^ a, c j^ b, and c < aU b.) Megill and Pavicic (2000) 9 (a) Given two different atoms a and b, there is at least one other atom c, c ^ a and c ^ b, that is a superposition of a and b. (b) If the atom c is a superposition of distinct atoms a and b, then atom a is a superposition of atoms b and c. 4- Minimal length: The lattice contains at least three elements a,b,c satisfying: < a < b < c< 1. Note that atoms correspond to pure states when defined on the lattice. We recall that the irreducibility and the covering property follow from the superposition principle. ^9 pp. 166,167] We also recall that any Hilbert lattice must contain a countably infinite number of atoms. |jl8| The above conditions suffice to establish isomorphism between HL and the closed subspaces of any Hilbert space, C(7i), through the following well-known theorem. pO , §§33,34] Theorem 3.5. For every Hilbert lattice HL there exists a field K, and a Hilbert space Ti over K,, such that C{7i) is ortho-isomorphic to HL. Conversely, let Ti be an infinite- dimensional Hilbert space over a field K, and let an) = {X (l'H\ X^^ = X} (3.3) be the set of all biorthogonal closed subspaces ofH. Then C{7i) is a Hilbert lattice relative to: anb = XaDXb and aUb = (Xa + Xb)^^. (3.4) In order to determine the field over which Hilbert space in Theorem |3.5| is defined we make use of the following theorem. Theorem 3.6. [Soler-Mayet-Holland] Hilbert space Ti from Theorem \3.d^ is an infinite- dimensional one defined over a complex field C if the following conditions are met: 5. Infinite orthogonality: Any HL contains a countably infinite sequence of orthogonal elements. /^7]/ 6. Unitary orthoautomorphism: For any two orthogonal atoms a and b there is an automorphism U such thatU{a) = b, which satisfies U {a') =U{a)', i.e., it is an orthoauto- morphism, and whose mapping into Ti is a unitary operator U and therefore we also call it unitary. / |7^/ 7. C characterization: There are pairwise orthogonal elements a,b,c G L such that (3d,e E L){0 < d < a Sz < e < b) and there is an automorphism V in L such that (V(c) < c), (V/ G L : / < a)(V(/) = f), {^g e L : g < b)iV{g) = g) and (3/i G L)(0 <h< aUbL V{V{h)) ^h). M Megill and Pavicic (2000) 10 Proof. [|T2| By Theorem ^^, to any two orthogonal atoms a and b there correspond or- thogonal one-dimensional subspaces (vectors) e and / from H such that a = fCe and h = /C/. The unitary orthoautomorphism U maps into the unitary operator U so as to give U{e) = af for some a G /C. From this and from the unitarity of U we get: (e, e) = {U{e),U{e)) = {af,af) = a{f,f)a*. Hence, there is an infinite orthogonal se- quence {ci : i = 1,2,...}, such that {ei,ei) = {fj,fj), for all i,j. Then Soler's [^ and Mayet's p2| theorems prove the claim. D We have seen that the definition of the "unitarity" of the unitary automorphism in the previous theorem is not given directly in HL but through the inner product of the corre- sponding Hilbert space (whose existence is guaranteed by Theorem |3.5|). A pure lattice version of the definition of the unitary automorphism formulated by S. S. Holland, JR., |12 is not known, but it is known that it can be replaced by Morash's purely lattice theoretic angle bisecting condition in HL. |21 From the previous two theorems we see that to arrive at the basic Hilbert space structure we do not need the notion of state, i.e., of the probability of geting a value of a measured observable. This probability and state follow uniquely from Hilbert space by Gleason's theorem and we can use them to make probabilistic (the only available ones in the quantum theory) predictions of an observable A: Prob{A) = tr{pA), there tr is the trace and p is a density matrix. |^, p. 178] Alternatively we can start with the pure states that correspond to one dimensional subspaces of Hilbert space, i.e., to vectors of Hilbert space and to atoms in the Hilbert lattice. Definition 3.7. A state m is called pure if, for all states mi,m2 and all reals < A < 1, the equality m = Ami + (1 ^ A)m2 implies m = mi = m2 According to Gleason's theorem |2^, for every vector ^m ^ 'H, \\^m\\ = 1 and for every Pa, where Pa is a projector on the subspace Ha, there exists a unique inner product {Pa'^m, ^m) which is a pure state m{a) on C(TC). By the spectral theorem to each subspace there corresponds a self-adjoint operator A and we write Pa = Pa- The mean value of A in the state m is {A) = Expm(^) = / at/(P4,|„|^^, ^^) = (^^^,^^). [||] So, conditions 1-4 of Definition ^^ and 5-7 from Definition |3.6| enable a one-to-one corre- spondence between the lattice elements and the closed subspaces of the infinite-dimensional Hilbert space of a quantum system and Gleason's theorem enables a one-to-one correspon- dence between states and mean values of the operators measured on the system provided the above strong states (probability measures) are defined on them. The usage of strong states here is somewhat unusual because most authors use full states instead. [|12|, ^ |^ To prove that the correspondence (isomorphism) holds for the strong states as well, we only have to prove that Hilbert space admits strong states because the other direction follows from the fact that any strong set of states is full. The result is not new (it appears, e.g., in ||19| , p. 144]) but we give here a proof communicated to us by Rene Mayet, for the sake of completeness. Theorem 3.8. Any Hilbert lattice admits a strong set of states. Megill and Pavicic (2000) 11 Proof. We need only to use pure states defined by unit vectors: If a and b are closed subspaces of Hilbert space, Ti such that a is not contained in b, there is a unit vector u oiTi belonging to a — b. If for each c in the lattice of all closed subspaces of 7i, C(H), we define m^c) as the square of the norm of the projection of u onto c, then m is a state on Ti such that m{a) = 1 and m(6) < 1. This proves that C{TC) admits a strong set of states, and this proof works in each of the 3 cases where the underlying field is the field of real numbers, of complex numbers, or of quaternions. We can formalize the proof as follows: {\/a,be L){{r^ a<b) ^ (3m G 5)(m(a) = 1 & ~ m{b) ^ (Wa,be L){3me S){{m{a) = l => m,{b) = 1) ^ a < b) 1)) D So, any Hilbert space admits strong states and we need them to predict outcomes of measurements. But there is more to it — states, when defined on an ortholattice, impose very strong conditions on it. In particular, they impose a class of orthomodular equations which hold in C(7i) and do not hold in all OMLs: Godowski's [|25[ and Mayet's |^ equations. In the rest of this section we shall first give some alternative formulations of Godowski's equations and present a new class of lattices in which the equations fail. Then we shall show that Mayet's Examples 2, 3, and 4 which were meant to illustrate a generalization of Godowski's equations are nothing but special cases of the latter equations. Definition 3.9. Let us call the following expression the Godowski identity.' ai=a„ = (ai ^i 02) n (a2 -*i 03) ■ ■ ■ n (a„_i ^1 a„) n (a„ ^1 ai), n = 3,4,5, .. . (3.5) 7 We define a„=ai in the same way with variables Oj and a„„j+i swapped; in general 7 ai=aj will be an expression with |j — 2| + 1 > 3 variables ai, . . . ,aj first appearing in that 7 dei, X , >i tti) = 1 and [ai order. For completeness and later use (Theorem |3.22| ) we define ai=ai aj=aj+i = (oj ^1 aj+i) fl (oj+i — >i «») = Oj = Cj+i, the last equality holding in any OML. We also define ai=a„, etc. with the substitution of Theorem 3.10. Godowski's equations [ p5[| 7 7 ai=a4 7 01=05 for ^1 in ai=a„, etc. 7 03=^1 7 a4=ai 7 a5=ai (3.6) (3.7) (3.8) hold in all ortholattices, OL 's with strong sets of states. An OL to which these equations are added is a variety smaller than OML. We shall call these equations n-Go f3-Go, 4-Go, etc.). We also denote by nGO f3G0, 4G0, etc.) the OL variety determined by n-Go (which we also call the nGO lawj. Megill and Pavicic (2000) 12 Proof. The proof is similar to that in [^. By Definition |3.1| we have m{ai ^i 02) = m{a[) + m(ai fl 02) etc., because a[ < {a[ U a'a), i.e., a[ ± (ai fl 02) in any ortholattice. Assuming m(ai=a„) = 1 we get m(ai — >i 02) = ■ ■ ■ = m(a„_i ^1 a„) = m(an -^1 ai) = 1. Hence, n = m(ai ^1 02) ■ ■ ■+m(a„_i ^1 an)+m{an — *i fli) = m{an — >i fln-i) ■ ■ ■+m{a2 ^1 ai) + m(ai — >i a„). Therefore, m(a„ — >i a„_i) = ■ ■ ■ = m(a2 — >i ai) = m(ai ^1 a„) = 1. 7 Thus, by Definition ^]2|for strong quantum states, we obtain: (ai=a„) < (a„ ^1 a„_i), . . . , (ai=a„) < (02 ^1 ai), and (ai=a„) < (ai — >i a„), wherefrom we get (ai=a„) < (a„=ai). By symmetry, we get (a„=ai) < (01=0^). Thus (01=0^) = (a„=ai). TT-GO is orthomodular because 3-Go fails in 06, and n-Go implies {n — l)-Go in any OL (Lemma p.l7|) . It is a variety smaller than OML because 3-Go fails in the Greechie lattice from Fig. |^a. D The following lemma provides a result we will need. Lemma 3.11. The following equation holds in all OMLs. (ai = 02) ■ • • n (a„_i = On) = (oi ■ ■ ■ n a„) U {a[- ■ ■ H a^), n >2 (3.9) Proof. We use induction on n. The basis is simply the definition of =. Suppose (ai = 02) ■ ■ ■ n (a„-2 = fln-i) = (fli • • ■ n an-i) U (a'l • • • n a^_i). Multiplying both sides by a„„i = an = (a„-i ^1 a„) fl (a„ ^2 a„_i), we have (ai = 02) • ■ ■ n (a„_i = a„) = [((ai ■ ■ ■ n a„_i) U (a'l ■ ■ • n a^_i)) H (a„_i ^1 a„)] H (a„ ^2 On-i) = [(ai ■ ■ ■ n a„) U (a'l ■ ■ • n a^_{)] n (a„ -»2 a„„i) = (ci ■ ■ ■ n On) U {a[- ■ ■ n a'^) . F-H was used in the last two steps, whose details we leave to the reader. D Theorem 3.12. An OL in which any of the following equations holds is an nGO and vice versa. s 5 ai=an = a„=ai (3.10) ai=a„ = (fli = 02) n (a2 = as) ■ ■ ■ n (a„_i = a„) (3.11) ai=an = (fli = 02) n (a2 = as) • ■ ■ n (a„_i = a„) (3.12) o-i=an < tti — >j a„, 2 = 1,2,3,5 (3.13) ai=an < ai ->i a„, 2 = 1,2,4,5 (3.14) (ai=a„) n (ai U a2 ■ • ■ U a„) = ai fl 02 ■ ■ ■ H a„ (3.15) (ai=a„) n {a[ U a'g ■ ■ • U a^) = a'^^ fl 03 ' ' ' ("I o^n (3.16) Megill and Pavicic (2000) 13 Proof. Lattice 06 violates all of the above equations as well as n-Go. Thus for the proof we can presuppose that any OL in which they hold is an OML. Equation ( |3.10|) follows from definitions, replacing variables with their orthocomplements in n-Go. Assuming (|3.11|) , we make use of a = b = {a ^i b) fl (6 ^i a) to obtain the equivalent 'V 'Y 'v 'Y 'Y equation ai=a„ = 0'i=o-n H 0^=01, so ai=a„ < 0^=01. By renaming variables, the other direction of the inequality also holds, establishing n-Go. Conversely, n-Go immediately implies ai=a„ = ai=a„ fl a„=ai. The proof for (|3.12|) is similar. For ( p.l3[ ) and ( p.l4[ ), we demonstrate only (|3.13| ), z = 3. From ( |3.13| ), by rearranging factors on the left-hand-side we have ai=a„ < 02 — ^3 oi, so ai=a„ < (02 — ^3 ai) fl (ai ^i 02) = oi = 02 (from Table 1 in ||^), etc.; this way we build up (|3.11| ). For the converse, ( CT ) and (gi§ obviously follow from ( PT| ) and ( PTT^ . For (p.l5|) , using ( p.9|) we can write ( p.ll| ) as ai=a„ = (ai ■ • • fl a„) U {a[- ■ ■ H a^). Multiplying both sides by ai ■ ■ ■ U a„ and using F-H we obtain ( ^.15| ). Conversely, disjoining both sides of ( p.l5| ) with a[- ■ -Ha'^ and using F-H and ( |3.9| ) we obtain ( p.ll| ). The proof for ( p.l6| ) is similar. D Theorem 3.13. In any nGO, n = 3, 4, 5, . . ., all of the following equations hold. 0<i<5, l<j<n, l<k<n <i<5, l<j<n, I <k<n 7 ai=a„ < ttj ^i Qk 5 ai=a„ < ttj ^i ttk ai=a„ = S ai=an (3.17) (3.18) (3.19) Proof. These obviously follow from ( |3.11 ) and ( p.l2| ) and (for i = 0) the fact that a — >,„ b < a —>o b, < m < 5. O Some of the equations of Theorem 3.13| (in addition to those mentioned in Theorem 3.12| ) also imply the nGO laws. In Theorem |3.15| below we show them for n = 3. First we prove the following preliminary results. Lemma 3.14. The following equations hold in all OMLs. (ai (a ^2 b) n (6 ^1 c) = (a' n b') U (& n c) 5 02) n (a2 ^5 as) n (ag ^5 Oi) = [oi = 02) n (02 = as) (3.20) (3.21) Proof. For ( lOOl) , (a ^2 &) H (6 ^1 c) = ((6U (a' n 6')) H (6' U (bn c)) = {{bU{a' f\b'))nb')U {{b u (a' n b')) n 6 n c) = (a' n V) u (6 n c). Megill and Pavicic (2000) 14 For ( |3.21| ), we have (ai ^5 02) n (a2 ^5 03) n (as ^5 ai) = [(fli = 02) u {a[ n 02)] n [(02 < ((ai = 02) U {a[ n as)) n ( ^2 ^1 03) n (02 -^2 «3)] n [(03 *2 CL's) n (03 ^1 fli) tti) n (a3 ->2 cti)] = "-2; '-' V"l ' ' "2;; I I V"'2 ^2 "-3; I I v^-a ^1 ": = ((ai = 02) U (a'l n 02)) n ((4 n 4) U (aa n ai)) = 02) n ((4 n 4) u (as n ai))) u ((% n 02) n ((02 n 4) u (a^ n ai))) = ((d = 02) n ((4 n 4) u (03 n ai))) u = ((«! = < ai = 02 In the third step we used ( p.20|) ; in the fourth ai = a2Ca[r\a2 and a[r\a2C{a2na'^)U{a3nai); in the fifth a'^ na2Ca2 flOg and a'j^ ("102 Caa flai. Rearranging the left-hand side, this proof also gives us (ai — >-5 02) fl (02 — >-5 03) fl (03 — i>5 ai) < 02 = 03 and thus < (ai = 02) fl (02 = 03). The other direction of the inequality follows from a = b < a -^5 b. D Theorem 3.15. When n = 3, an OML in which any of the following equations holds is a nGO and vice versa. (3.22) (3.23) (3.24) 7 < fln —^i Ol, i = 2,3,4,5 <5 < fln -^i Oi , i = 1,3,4,5 7 = .5 ai=a„ Proof. We have already proved the converses in Theorem p. 13 . From (|3.22|) , we have 01=03 < {a^ —>-i ai) fl (03 ^1 ai) = 03 ^5 ai since (a ^- b) fl (a ^^ b) = a — >5 fo when j ^ k for j, A; = 1, . . . , 5. By rearranging the left-hand side we also have '^1=03 < til ~^5 (^2 and < 02 -^5 %. Thus 01=03 < (oi — s>5 02) fl (02 — ^5 03) fl (03 — i>5 oi) < Oi = 02 < 02 —^1 oi, which is the 3G0 law by ( p.l3| ). In the penultimate step we used (|3.21|) . The proof for ( p.23 ) is similar, and from ( 3.24 ) we obtain ( p.22 D Whether Theorem 3.15 holds for n > 3 is not known. The equations obtained by substituting ^2 for one or more — *i's in Godowski's equations also hold in some riGO, although to show such an equation with j variables may require the use of an n-Go equation with n > j. Theorem 3.16. The following equation with i variables holds in some nGO with n > i, where each -^j^ {^ < k < i) is either ~^i or ^2 in any combination. (oi ^j, 02) n (02 -^j2 03) ■ ■ ■ n (ai_i ^j,_^ ai) n (a^ -^j^ fli) 1. fli^flj (3.25) Megill and Pavicic (2000) 15 Proof. We illustrate the proof by showing that the 3- variable equation (oi ^2 02) n (a2 ^1 as) n (as ^1 ai) holds in any 4G0. The essential identities we use are 7 ai=as [a (a >i (aUb)) n ((aU6) -^1 b) >2 (a n b)) n ((a n 6) ^2 &) a ^1 fo (3.26) (3.27) (3.28) which hold in any OML. Starting with ( 3.17 ), we have (ai ib)n{b ^1 a2) n (a2 ^1 as) n (as ^1 ai) < (ai ^1 as) n (as ^1 ai) n (as ^1 a2) H (a2 ^1 as) = (ai = as) n (as = a2) = (ai = 02) n (a2 = as) 7 = ai=as where in the penultimate step we used ( p.9|) [or more generally (|3.9|)] and in the last step ( p.llQ . Substituting ai U a2 for b and using (|3.27|) we obtain (ai ^2 0^2) n (a2 ->i as) n (as -^1 ai) < ai=as Using ( |3 . 1 7| ) for the other direction of the inequality, we obtain ( |3.26| ). The reader should be able to construct the general proof. D a = c (3.29) A consequence of (|3.25|) that holds in any 4G0 is (a -^1 b) n (b ^2 c) n (c ^1 a) < which, using ( p.20| ) and weakening the left-most factor, implies {a = b)n{{b'nc')U{anc)) < {a = c). (3.30) Equation (|3.30 ) is also a consequence of ( 2.101 ) as can be seen if we write ( 2.10 ) as follows: (a = 6) n ((6nc) u (6'nc') u (anc) U (a'nc')) < {a = c). As with ( p.lOl) , we were unable to prove that even the weaker-looking ( p.30| ) holds in all OMLs. It is also unknown if ( p.30| ) even holds in all 3GOs. Finally, we do not know if there is an n such that (|2.10| ) holds in all nGOs. The equations obtained by substituting -^j for ^1 in the Godowski equations do not in general result in equivalents for i = 3,4,5 nor even hold in an nGO. For example, for n = 3, the equations (ai ^s ^12) H (a2 ^s eta) H {(^3 ~^3 C'l) ^ (^^2 ^3 o-i) and (ai — >4 0^2) n (a2 ^4 as) n (as ^4 ai) < (a2 ^4 ai) fail in lattice M02 {Chinese lantern, Fig. ||b), and (ai — ^5 a2) fl (02 -^5 as) fl (as — ^5 ai) < (a2 — *-5 ai) holds in all OMLs by ( |3.21| ). Megill and Pavicic (2000) 16 Figure 2: (a) Greechie diagram for OML G3; (b) Greechie diagram for OML G4. Lemma 3.17. Any nGO is an (n — 1)G0, n 4,5,6,.... Proof. Substitute Oi for 02 in equation n-Go. D The converse of Lemma ( p.lTD does not hold. Indeed, the wagon wheel OMLs Gn, n = 3,4,5,..., are related to the n-Go equations in the sense that Gn violates n-Go but (for n > 4) not (n — l)-Go. In Fig. ^ we show examples G3 and G4; for larger n we construct Gn by adding more "spokes" in the obvious way (according to the general scheme described inp5i). For any particular n there may exist lattices smaller than Gn for which this property holds. These can be more efficient, computationally, for proving that an equation derived in nGO is weaker than n-Go or independent from (n — l)-Go. Based on a computer scan of all (legless) OMLs with 3-atom blocks (see footnote at the end of Section ^, up to and including a block count of 12 along with selected lattices with block counts up to 17, we obtained the following results. Lattice G3, with 34 nodes, is the smallest that violates 3-Go. (In OMLs with 3-atom blocks, the number of nodes is twice the number of atoms, plus 2.) The Peterson OML, with 32 nodes (vs. 44 nodes in G4), is the smallest that violates 4-Go but not 3-Go. (Fig. 0) Lattice G5s, with 42 nodes (vs. 54 nodes in G5), is the smallest that violates 5-Go but not 4-Go. (Also Fig. |^) Lattices G6sl and G6s2, each with 44 nodes (vs. 64 nodes in G6), are two of three smallest that violate 6-Go but not 5-Go. (Fig. 1) Of these three, G6sl is one of two with 14 blocks, whereas G6s2 has 15 blocks. Lattices G7sl and G7s2 (Fig. ^ are two of several smallest we obtained to violate 7-Go but not 6-Go. They both have 50 nodes and 16 and 17 blocks, respectively (vs. 74 nodes and 21 blocks in G7). We made use of a dynamic programming algorithm to obtain a program for checking on n-Go which is so fast that no reasonable n is a problem. For example, to find G7sl among 207767 Greechie diagrams with 24 atoms and 16 blocks took an 800 MHz PC less than two hours. The next lemma provides some technical results for subsequent use. Note that a _L 6 _L c means a -L b and 6 _L c (but not necessarily a _L c). Lemma 3.18. In any OML we have: a ±b ±c => (a U 6) n (a ->2 c) < 6 U c (3.3i; Megill and Pavicic (2000) 17 Figure 3: (a) Peterson OML; (b) Greechie diagram for OML G5s. Figure 4: (a) Greechie diagram for OML G6sl; (b) Greechie diagram for OML G6s2. Figure 5: (a) Greechie diagram for OML G7sl; (b) Greechie diagram for OML G7s2. Megill and Pavicic (2000) 18 a±b±c => aUb<c-^2a (3.32) a±b±c & {c^2a)nd<a-^2C => {aUb)nd<bUc (3.33) Proof. For (|3.31| ): (aU6)n(a — >2 c) = (aU6)n(cU(a'nc')). From hypotheses, 6 commutes with aandcU(a'nc'). Using F-H twice, (aU6)n(cU(a'nc')) = (fon(cU(a'nc')))U(anc)U(ana'nc') < bUc. For (g): From hypotheses, aUb < aU {c' H a') = c ^2 a. For ( p:33|) : From ( |332|) , (a U 6) n (i < (c — >2 a) n (i <[from hypothesis] a — >2 c. Thus {aUb) Hd < (a U 6) fl (a — >-2 c), which by (|33l| ) is < 6 U c. D The n-Go equations can be equivalently expressed as inferences involving 2n variables, as the following theorem shows. In this form they can be useful for certain kinds of proofs, as we illustrate in Theorem |3.2CI| . Theorem 3.19. Any OML in which Oi _L 61 _L a2 -L 62 -L . . . ctn -L 6„ -L «! =^ (ai U 61) n (02 U 62) n ■ ■ ■ (a„ U bn) <biUa2 (3.34) holds is an nGO and vice versa. Proof. Substituting ci for ai,. . . , c„ for a„, c[ fl C2 for 61, . . . , c^_]^ fl c'„ for fe„_i, and c'„ fl c^ for 6„, we satisfy the hypotheses of (|3.34| ) and obtain (|3.14|) . Conversely, suppose the hypotheses of ( p.34| ) hold. From the hypotheses and ( p.32| ), we obtain (a2U62) ■ ■ ■n(a„„iU6„_i)n(a„U6„) < {a^ — >2 ^2) ■ ■ ■n(a„ — >2 a„_i)n(ai — >2 a™). Thus (a2 ^2 oi) n [(02 U 62) ■ ■ ■ n (a„_i U bn-i) H (a„ U 6„)] < (02 ^2 ai) n [(03 ^2 ^2) ■ ■ • n (a„ -^2 a„_i) n (ai ^2 an)] = (^2 ->2 ^i) n (ai ^2 a„) n (a„ ->2 fln-i) • • ■ H (03 ^2 02)- Applying ( ^.14| ) to the right-hand side, we obtain (02 —^2 '^i)n [(a2U62) ■ ■ ■n(an_iU6„_i)n(a„U6n)] < ai —^2 ^2- Then ( p.33|) gives us (|3.34|) . D Mayet ||2^ presents a method for obtaining equations that hold in all lattices with a strong or full set of states. However, it turns out that the examples of those equations he shows are implied by the n-Go equations and thus do not provide us with additional information about lattices with strong states or CiH) in particular. To the authors' knowledge, there is no known example of such an equation that cannot be derived from the n-Go equations. It apparently remains an open problem whether Mayet's method gives equations that hold in all OMLs with a strong set of states but that cannot be derived from equations n-Go. Theorem 3.20. The following equations (derived as Examples 2, 3, and 4 in f^B^) hold in 3G0, 6G0, and 4G0 respectively. (a^i 6) n(6^i c)n(c^i a) < 6^1 a (3.35) a ± b ± c ± rf ± e ± / ± a ^ (a U 6) n (d U e)' n ((((a U b) ^1 {d U e)') ^1 ((e U /) ^1 (6 U c)')')' ^1 (c U d)) Megill and Pavicic (2000) 19 < feUcU (eU/)' a_L&_Lc_L(i_Le_L/_L(7_L/i_La =^ {aU b) n {cU d) n {eU f) n {g U h) n ((a U h) (due)') (3.36) (3.37) Proof. For (|3.35|) : This is the same as ( p.l3|) for n = 3. For (|3.36| ): Using ( |3.34| ) we express the 6G0 law as Oi _L 6i _L a2 -L ^2 -L ^3 _L 63 ± 04 _L 64 _L as _L 65 _L ae -L ^6 -L Oi =^ (ai U 61) n (aa U 62) H (03 U 63) H (04 U 64) H (as U h) n (ag U h) < fei U as . (3.38) We define p= ((aU6) ^1 (rfUe)')', g= ((eU/) ^1 (feUc)')', and r = (p' ->i g)'n(cUd). In ( p.38| ) we substitute a for ai, 6 for 61, c for as, (cUrf)' for 62, ?" for as, p' ^1 q for 63, (p' — i>i g)' for a4, p' n g for 64, g' for as, q for 6s, (e U /)' for ae, and / for b^. With this substitution, all hypotheses of ( p.38| ) are satisfied by the hypotheses of ( p.36| ). The conclusion becomes (a U 6) n (c U (c U d)') n (r U (p' ^1 q)) n((p -^1 q)' Uip'nq))n (q' U g) n ((e U /)' U /) < 6 U c . (3.39) We simplify ( |3.39| ) using cU (cUd)' = [since c and d commute by hypothesis] (cUc') fl {cUd') = 1 n (c U d') = [since c < d'] d'; (e U /)' U / = e' similarly; (p' ^1 g)' U (p' H g) = p'; and g' U g = 1. This gives us {aUb)nd' n{rU{p' -^iq))np' ne < bUc. (3.40) Now, in any OML we have p' = {a U b) ^1 {d U e)' = (a U 6)' U ((a U 6) n ((i U e)') > (aU6)n(rfUe)' > (aU6)n(rfUe)'n((p' ^1 g)Ur). Thus the left-hand side of (|O0| ) absorbs p', so (aU6) nd'n (rU (p ^1 g)) ne' < 6Uc < &UcU(eU/)' which after rearranging is exactly ( |3.36| ). For (|3.37|) : Using (|3.34|) we obtain from the 4G0 law (3.41) a_L6_Lc_Lrf±e_L/_L5f_L/i_La ^ (a U 6) n (c U rf) n (e U /) n (5- U /i) < (a U /i) n (d U e) . Therefore a_L6_Lc±d±e_L/_L5f_L/i_La ^ (a U 6) n (c U d) n (e U /) n (fif U /i) n ((a ^ h) ^1 (d U e)') < (a U /i) n (rf U e) n ((a U /i) ^1 {d U e)') . In any OML we have x fl y fl (x -^i y') = 0; applying this to the right-hand side we obtain Megill and Pavicic (2000) 20 To the authors' knowledge all 3- variable equations published so far that hold in all OMLs with a strong set of states are derivable in 3G0. Below we show an equation with 3 variables that is derivable in 6G0 but is independent from the 3G0 law. It shows that it is possible to express with only 3 variables a property that holds only in nGOs smaller than 3G0. Theorem 3.21. The 3-variable equation ((a ->2 b) n (a ^2 c)') n ((((a ^2 b) ^1 (a ^2 c)') ^1 {{b ^2 c) ^1 (b ^2 a)')')' ^1 (c ^2 a)) <b^2a (3.42) holds in a 6G0 but cannot be derived (in an OMLj from the 3G0 law nor vice versa. Proof. To show this equation holds in 6G0, we start with ( |3.41| ) that occurs in the proof of Mayet's Example 3, rewriting it as: d±e± f ± g ±h±j ±d => idUe)n{gU h)' n ((((rf U e) ^1 {g U h)') ^, {{h U j) ^1 (e U /)')')' ^1 (/ U g)) <eU/ (3.43) We substitute b for d, a' fl b' for e, a for /, a' fl c' for g, c for /i, and c' fl 6' for j. With these substitutions, the hypotheses of ( p.43| ) are satisfied. This results in ( |3.42| ), showing that i ^A^ holds in 6G0. We show independence as follows. On the one hand, (|3.42|) fails in the Peterson OML (Fig. |a) but holds in OML G3 (Fig. |a). On the other hand, the 3G0 law (^ holds in the Peterson OML but fails in G3. D It is not known whether ( |3.42|) holds in 4G0 or 5G0 Using our results so far we can show that ai=aj = 1 is similar to a relation of equivalence (although strictly speaking it is not one, since ai=aj involves not 2 but |j — i| + 1 variables). Reflexivity ai=ai = 1 follows by definition, symmetry ai=aj = 1 ^ aj=ai = 1 from the Godowski equations, and transitivity ai=aj = 1 & aj=ak = 1 ^ 0'i=(ik = 1 from the following theorem. Analogous results can be stated for =. An open problem is whether 7 5 there exists an equation corresponding to ai=aj = 1 and ai=aj = 1 as in Equations Ll, (OD, and (WM. Theorem 3.22. The following equation holds in nGO, where i,j > 1 and n = max(i, j, 3). [ai=ai) n {ai=aj) < ai=aj (3.44) Proof. If = has 3 or more variables, we replace it with a chained identity per ( |3.11|) , otherwise we replace it with the extended definition we mention after Definition p.9| . The proof is then obvious. (In many cases the equation may also hold for smaller n or even in OML or OL, e.g. when j = 1.) D Megill and Pavicic (2000) 21 The next lemma shows an interesting "variable-swapping" property of the Godowski identity that we shall use in a later proof [of Theorem |0 Lemma 3.23. In any OML we have (ai=a„) n a[ = a[n a2- ■ ■ n a'^ , i = 1, . . . ,n . (3.45) In particular, (ai=a„) n a^ = (ai=a„) f^ a'j , z = 1, . . . , n , j = 1, . . . , n . (3.46) Proof. We illustrate the case i = 1. In any OML we have a' fl {b ^i a) = a' Ci b'. Thus (ai ^1 02) ■ ■ ■ n (a„_2 ^1 a„_i) n (a„_i ->i a„) n (a„ ^1 Oi) n a[ = (ai -^1 02) ■ ■ ■ n (a„_2 -^1 a„_i) n (a„_i — >i a„) fl a^ fl a'^^ = ■ ■ ■ = a'^^ D 03 ■ ■ ■ fl a^_i fl a^ D a'^ D 4 Orthoarguesian Equations In this section we show that all orthoarguesian-based equalities (which must hold in any Hilbert lattice) that have appeared in the literature as equations with 4 and 6 variables can be reduced to just two equations with 3 and 4 variables. The latter two equations we call the 30A and 40A laws, respectively, and introduce them by Definition [4.4|. Their equivalence to the afore mentioned 4- and 6- variables equations is shown in Theorems |4.8| and ^]9| and in Theorem [4.7| , respectively. A new 3-variable consequence of the 40A law which is not equivalent to the 30A law is given by Theorem |4.11] . Possibly equivalent inference forms of the 30A law and the 40A law are given by Theorems ^^, [4.3| , and 4.1CI| . Definition 4.1. c , def a=ib = {{a ^i c) n {b ^i c)) U ((a' - ^i c) n {b' - -. c)). i = 1,3, (4.1) c , def a=ib = {{c ^^ a) n (c ^i b)) U {{c - ^i a) n (c - -^ b')), 2 = 2,4, (4.2) c4 dof a=ib = (a4&)U((a4c)n(64c)), z = l,.. ,4. (4.3) We call a=ib a 3-variable orthoarguesian identity and a^ib a ^-variable orthoarguesian iden- tity and denote them as 3-oa and 4-oa respectively. Theorem 4.2. An ortholattice to which any of a=ib = 1 -x^ a^iC = b^iC, i = 1,3 (4.4) a^ib = 1 ^ c ^i a = c ^i b, z = 2, 4 (4.5) are added is a variety smaller than OML that fails in lattice L28 (Fig. ^a). The corresponding expressions for i = 5 do not hold in a Hilbert lattice (right to left implications fail in M02). Megill and Pavicic (2000) 22 -^ C) -e- Figure 6: (a) Greechie diagram for OML L28; (b) Greechie diagram for OML L36. Theorem 4.3. An ortholattice to which any of c,d a=ib = 1 -v^ a^id = h^id, z = l,3 (4.6) is added is a variety smaller than OML that fails in lattice L36 (Fig. ^) for i = 1,3. The new identities =i and =i being equal to one are relations of equivalence. It is obvious that they are reflexive (a=ia = 1, a=ia = 1), and symmetric {a=ib = 1 ^ b=ia = 1, c,d c^d I I a=ib = 1 ^ b=ia = 1), and the transitivity follows from Theorem [4.10| below. They are, C C however, not relations of congruence because a =i b = 1 =^ {a U d) =i {b U d) = 1 does not hold: it fails in the Chinese lantern M02 (Fig. |l]b). Conditions and (U) must hold in any Hilbert space (and therefore by any quantum simulator) for z = 1 as we show below. Expressions corresponding to Eq. ( |4.6| ) for i = 2,4,5 do not hold in a Hilbert lattice and it is an open problem whether there exist equivalent relations of equivalence for i = 2,4,5. In what follows we keep to i = 1 (and not i = 3) because i = 1 enables us to switch to the Sasaki projection ipab = {a — >i b')' of 6 on a later on. The Sasaki projection plays an important role in the definition of the covering property which is a consequence of the superposition principle. ||T9(| Definition 4.4. Let a=b = a=ib and a=b = a=ib. A 30A is an OL in which the following additional condition is satisfied: (a — *i c) n {a=b) < b -^i c . A 40A is an OL in which the following additional condition is satisfied: c d (a ^1 d) n {a=b) <b^id. (4.7) (4. Note that the 30A and 40A laws ([4.7|) and (|4.^ ) have 3 and 4 variables respectively. Both 30A and 40A laws fail in 06, so, they are OMLs, but there exist OMLs that are Megill and Pavicic (2000) 23 neither 30As nor 40As: equations ( ^.7| ) and ( [4.8| ) both fail in the orthomodular lattice L28 (Fig.|a). Theorem 4.5. Every 40A is a 30A, but there exist 30As that are not 40As. c,d Proof. In (a ^i d) fl {a=b) < [h ^i d), set c = b. On the other hand, lattice L36 (Fig. ^) is a 30A because it is an OML in which (|4.7| ) holds, but it is not a 40A because it violates D The next lemma provides some technical results for use in subsequent proofs. Lemma 4.6. In any OML we have: {a^ib)na = anb (4.9) (a -^1 b) n (a' ^1 b) = {a-^ib)nb= {anb)U (a' H b) (4.10) (a' ^1 b)' <a' <a^ib (4.11) (a^i 6) ^1 6 = a'^i 6 (4.12) (a^i 6)'^i 6 = a^i 6 (4.13) (a ->i 6) U (a ^j b) = a ^0 ^ i,i = 0, . . . ,4, z ^ j (4.14) a'<6 ^ b<a-^ib (4.15) an ((a^i c) U6) < c <^ 6 < a ^i c (4.16) Proof. For (|4.9|) - (|4?T5|) : We omit the easy proofs. For ( ^A6|) : If a H ((a ^i c) U 6) < c then a H ((a ^i c) U 6) < a n c = (a ^i c) H a using dJ), so 6 < 1 n ((a ->i c) U b) = ((a ^i c) U a) n ((a ^i c) U ((a -*i c) U 6)) = (via F-H) (a — i>i c) U (a n ((a — i>i c) U 6)) < (a — >i c) U ((a — >i c) fl a) = a — >i c. Conversely, if b < a ^1 c, then using ( |4.9| ), a fl ((a -^i c) U 6) = a fl (a — >i c) = a fl c < c. D In the next theorem we show that the 40A law ( [4.8[ ) is equivalent to the orthoarguesian law (|]T7D discovered by A. Day (cf. [i?], H), which holds in C{n). Thus the 40A law also holds in C{n). Theorem 4.7. An OML in which a±b & c±d & e±f => {a U b) n {cU d) n {e U f) < 6 U (a n (c U (((a U c) n (6 U d)) H (((a U e) H (6 U /)) U ((c U e) H (c? U /)))))) (4.17) (where a-Lb = a<b') holds is a 40A and vice versa. Megill and Pavicic (2000) 24 Proof. We will work with the dual of ( |4.17| ) a <b k c <d & e'</ => 6 n (a u (c n (((a n c) u (6 n d)) u (((a n e) u (6 n /)) n ((c n e) u (rf n /)))))) < (anb)u(cnd)u(en/). (4.I8) First we show that the 40A law implies (f4.18|) . In any OL we have b<g^ik & d<h^ik k f < j ^1 k =^ bnigu{hni{ignh)uibnd))u{i{gnj)uibnf))ni{hnj)u{dnf))m< (g ^1 k)nigUihn {{{g n h) U {{g ^i A;) n (h ^i A:))) U {{{g n j) u {{g ^1 A:) n U ^, k))) n {{h n j) u {{h ^1 fc) n (j ^1 k))))))) . (4.19) Substituting a' — >i A; for gf, c' — >i A; for /z, and e' ^i A; for j; simplifying with (|4.12|); and applying (|4.11| ) to the left-hand side of the conclusion we obtain b < a -^1 k k d < c — >i k k / < e ^i k =^ 6 n (a u (c n (((a n c) u (6 n d)) u (((a n e) u (6 n /)) n ((c n e) u (rf n /)))))) < e,fc (a -^1 A;) n (((a' ^i A;) U ((c' ^i A;) n (c=a)))) . (4.20) We convert the 40A law (c' ^i k)r\{c' = m') < [m' -^i k) to (c' ^i A;)n(c=m) < (m' ^i A;) to m' n ((m' ^1 A;) U ((c' ^i k) fl (c=m))) < k using (|4.16| ). We substitute (a ^i A;)' for m and simplify with [W^ and (|]T|) to obtain (a ^i A;)n((a' ^i A;)U((c' ^i A;)n(c=a))) < k. Combining with ( [4.20[ ) yields b < a ^1 k k d < c ^i k k / < e ^i k =^ 6 n (a u (c n (((a n c) u (6 n rf)) u (((a n e) u (6 n /)) n ((c n e) u (c? n /)))))) < k . Letting A; = (a n 6) U (c n d) U (e n /) we have a' <b => b <a~ -^^k c' <d => d<c- ^,k e<f => /<e- ^ik (4.21) (4.22) (4.23) (4.24) [e.g. for ( [4.221) , using (|4.15|) we have b < a ^i b = a' U {an (aHb)) < a' U (aHk) = a ^i k] from which we obtain ( |4.18| ). Conversely, assume (|4.18| ) holds. Let a = g -^i k, b = g' -^i k, c = h — >i k, d = h' — i>i k, e = j — >-i k, f = j' — >i k. The hypotheses of ( |4.18| ) are satisfied using ( [4.11| ). Noticing [with the help of ( [4.10I )] that the right-hand side of the resulting inequality is < k, we have {g' ^1 k)n{{g ->i k)U{{h ^1 k)n{h'ig))) < k, so gr\{{g ^i k)U{{h ^, k)n{h'ig))) < k. Applying (|4.16|) , we have the 40A law {h -^i k) n {h'=g) < g ^i k. D Megill and Pavicic (2000) 25 Thus we have demonstrated that the orthoarguesian law ( |4.17| ) can be expressed by an equation with only 4 variables instead of 6. This is in contrast to the stronger Arguesian law that has been shown by Haiman to necessarily involve at least 6 variables. [29 The 30A law (|4.7|) expresses an orthoarguesian property that does not hold in all OMLs, but as demonstrated by the fact that it holds in OML L36, it is strictly weaker than the l?ro|?er orthoarguesian law expressed by (|4.8| ) or ([4.17|) . The 30A law is equivalent to the following 3-variable equation [^, Equation III] obtained by Godowski and Greechie and thus to the other 3-variable variants of that equation mentioned in [^. Godowski and Greechie were apparently the first to observe that ( [4.25| ) fails in OML L28 and also in OML L of Fig. ||a below. Theorem 4.8. An OML in which (fb'O. U a{a, b, c) = tpc'd U a{a, b, c) (4.25) [where f is the Sasaki projection and a{a, b, c) = (6 U c) fl {ipb'O' U fc'Ct-)] holds is a 30A and vice versa. Proof. Using the definitions, ([4.25|) can be written in the dual form (a — >i c)n((an6)U((a — >i c) n (b ^1 c))) = (6 ^1 c) n ((a nb)U ((a ^i c) H {b ^i c))). We substitute a' -^i c for a and b' ^i c for b throughout; simplifying with ( |4.12|) we obtain (a ^i c) fl (a=6) = (6 ^i c) n (a=6). This is easily shown to be equivalent to ( |4.7|) . D Equation ([4.25|) was derived by Godowski and Greechie from Eq. (|4.26| ) below, which is a 4- variable substitution instance of ( ^.17| ). Godowski and Greechie state that ( ^.25| ) is "more restrictive" than (|4.26| ). While it is not clear to us what is meant by this remark, it turns out that the two equations are equivalent in an OML. This equivalence also means that the 40A law cannot be derived from (^4.26|) [which can also be verified independently by noticing that ( ^^261) does not fail in OML L36]. Theorem 4.9. An OML in which a±b & c±d => (aU6) n (cUrf) < 6U (an (cU ((aUc) n (6Urf)))) (4.26) holds is a 30A and vice versa. Proof. The proof is analogous to that for Theorem |4.7| . D With the help of the following theorem we show that the relation of equivalence intro- duced in Theorems 14. 21 and K^ is transitive. Megill and Pavicic (2000) 26 Theorem 4.10. (a) In any 30A we have: a=b =1 -v^ a — s>i c = b — i>i c (b) In any 40A we have: c.d. a=b =1 <^ a -^1 d = b — >i d (4.27) (4.28) Proof. For ( [4.27| ), assuming a=6 = 1 we have (a ^i c) fl (a=6) = (a ^i c) fl 1 < (6 — >i c) by (|4.?| ). Conversely, from ( [4.1 1|) (a ^i c)' < a' — >i c and {b —>-i c)' < b' —>-i c and from the hypothesis (a ^i c) = {b ^i c) = 1, so 1 = ((a ^i c) fl (b ^i c)) U ((a ^i c)' fl {b ^i c)') < ((a ^1 c) n (6 -^1 c)) U ((a' ^i c) n {b' ^i c)) = a=6. For ( ^1281) , the proof is similar, c,d. noticing for its converse that a=b < a=b. D The inference rules ( [4.27|) and ( [4.28|) fail in lattices L28 and L36 respectively, suggesting the possibility that they imply (in an OML) the 30A and 40A laws. However, we were unable to find a proof. The transitive laws that are a consequence of ([4.27|) and ( |4.28|) a=b = 1 d,e a=b = 1 & & b=c= 1 6=c = 1 a=c = i d,e a=c = 1 (4.29) (4.30) are weaker than the 30A and 40A laws, since both hold in lattice L of Fig. ^a (which violates both laws). However, they have a weak orthoarguesian property: both fail in lattice L38m0 Figure 7: (a) Greechie diagram for OML L38m; (b) Greechie diagram for OML L42. (Fig. I^a) and thus cannot be derived in an OML. ''OML L38m is neither a 30A nor a 3G0, and in addition violates all equations we have tested that are known not to hold in all OMLs. It has been useful as a counterexample for disproving equations conjectured to hold in aU OMLs. OML L42 is a 40A, a 50A (Section |), and an nGO (for n < 9, the upper limit we have tested) but violates all equations we have tested that are known to hold in neither 50A nor 9G0. It has been useful for disproving equations conjectured to hold in at least one of these varieties. Megill and Pavicic (2000) 27 The 30A law and its equivalents have been so far (to the authors' knowledge) the only published 3-variable equations derived from the 40A law that do not hold in all OMLs. Below we show another 3-variable consequence of the 40A law that is independent from the 30A law. Theorem 4.11. In any OML, the 3-variable equation c,d {a -^1 d) n {a=a') < a' ^i d . holds in a 40A but cannot be derived from the 30A law nor vice versa. (4.31) Proof. This equation is obviously a substitution instance of the 40A law ( |4.8| ). On the one hand, it fails in lattice L36 but holds in lattice L (Fig. ^) . On the other hand, the 30A law ( [4.7|) holds in lattice L36 but fails in lattice L. D Figure 8: (a) Greechie diagram for L from [^, Fig. II; (b) Greechie diagram for L38. An interesting OML is L38 (Fig. ^d), which violates the 40A law but does not violate any 3-variable consequence of the 40A law known to the authors. One possibility that came to mind was that perhaps L38 "characterizes" 40A in an essential way, in the sense that a failure in L38 of an equation derived in a 40A implies its equivalence to the 40A law (analogous to the fact that a failure in 06 of an equation derived in an OML implies its equivalence to the orthomodular law). This turns out not to be the case — there is a 4- variable consequence of 40A that is strictly weaker than 40A but fails in L38. Whether there exists a 3-variable consequence of 40A that fails in L38 remains an open problem. Theorem 4.12. A failure of a 40A equation in lattice L38 does not imply its equivalence to the 40A law. c,d Proof. Writing the 40A law as (a' ^i d) fl [a'=h') < h' ^i d, we weaken the left-hand side of the inequality with a < (a' ^i d), etc. to obtain a n ((a n fe) U (((a n c) U (a' n (c ^1 d))) n ((6 n c) U ((6 ^1 d) n c')))) <b' ^id. (4.32) Megill and Pavicic (2000) 28 This equation fails in OML L38 but holds in L28. D L38 has a peculiar history. We found it "by hand" before we had our present program for generating Greechie diagrams. [|17| Later we found out that G. Beuttenmiiller's program P, pp. 319-328] for generating Greechie diagrams does not give L38 (and a number of other lattices). Looking for a correct algorithm we came across McKay's isomorph-free generation of graphs. Applied to Greechie diagrams it gave not only a correct algorithm for their generation but also enabled writing a program which is several orders of magnitude faster than G. Beuttenmiiller's program transcribed into the C language (originally it was written in Algol). 5 Generalized Orthoarguesian Equations That Hold in C{7{) Using the 30A law as a starting point, we can construct an infinite sequence of equations El, E2, ■ ■ . that are valid in all Hilbert lattices C{T-C). The second member E2 of this sequence is the 40A law and the remaining members are equations with more variables that imply the 40A law. (n) Definition 5.1. We define an operation = on n variables ai, . . . ,an (n > 3) as follows^ ai = a2 = ai=a2 = ((ai ^1 as) fl (02 -^1 03)) U ((a'l ^1 03) fl (4 ^1 03)) (5.1) (1) def a4^, (3) (3) (3) ai = a2 = ai = a2 = (01 = 02) U ((01 = 04) fl (02 = 04)) (5.2) ai = 02 = (01 = 02) U ((01 = 05) n (02 = 05)) (5.3) ai = 02 = (oi = 02) U ((oi = a„) n (02 = o„)) , n>A. (5.4) Then we have the tt-OA laws (n) (ai ^1 03) n (ai = 02) < 02 — >i 03 . (5.5) Each nOA law can be shown to be equivalent, in an OML, to equation -En-2 of Theo- rem B^ below by a proof analogous to that for Theorem [4.7|. Thus they all hold in CiTi) and for n > A imply (in an OML) the 40A law. Also, as we shall show, 50A is strictly smaller than 40A, providing us with a new equational variety valid in C{7i) that apparently has not been previously known. It remains an open problem whether in general, nOA is strictly smaller than (n — 1)0A. To obtain = we substitute in each = subexpression only the two exphcit variables, leaving the other (4) . . .ir^ . (3) , , , ,, (3) , ^ , (3) variables the same. For example, (02 = as) in (5.3) means (a2 = ar-,) U ((a2 = a4) n (05 = 04)) which means (((02 ^1 03)0(05 ^1 03))U((o2 ^1 03)0(05 ^1 a3)))U((((a2 ->i 03)0(04 ^1 a3))U((a^ -^1 03)0(04 as))) n (((05 ^1 03) O (04 ^1 03)) U ((o[; ^1 03) O (o^ ^1 03)))). Megill and Pavicic (2000) 29 For the following theorem we will refer to the 30A and 40A laws in their 4- and 6- variable forms (|4.26|) and ( [4.17|) . Starting with the 30A law, we construct a sequence of equations as follows. Theorem 5.2. Let Ei, E2, . . . be the sequence of equations constructed as follows. The first equation Ei is the 30A law expressed as qq -L bo & ai -L bi =^ (ao U bo) n (ai U 61) < 60 U (ao fl (ai U ((oo U ai) fl (60 U 61)))) . (5.6) Given an equation En-i, oq -L &o <^ «! -L 61 ... & a„„i ± 6„_i => (ao U bo) n (ai U 61) • • ■ n (a„_i U 6„_i) < 60 U (ao n (ai U (• ■ ■ {ai U a^-) n {h U 6^) ■ ■ •))) (5.7) we add new variables an and bn to the hypotheses and left-hand side of the conclusion. For each subexpression appearing in the right-hand side of the conclusion that is of the form {ai U Qj) n {bi U bj), i,j < n, we replace it with {ai U aj) fl {bi U bj) fl {{{ai U a^) fl {bi U bn)) U {{ttj U a„) n {bj U bn))) to result in equation En: -'n ao -L &o & ai ± 61 ... & a„ ± 6„ (ao U 60) n (ai U bi) • ■ ■ n {an U 6„) < 60 U (ao n (ai U (■ ■ ■ {tti U a^) H (6^ U 6^)) n(((ai U an) n (6i U bn)) U ((a, U a„) H (6,- U 6„,))) ■ ■ ■))) • (5.8) Then E2 is the 40A law, and En {n > 3) is an equation that implies the 40A law, that holds in C{7i), and that cannot be inferred from 40A. Proof. It is obvious by definition that E2 is the 40A law (|4.17| ). It is also obvious En {n > 3) implies En-i and thus the 40A law: each subexpression of En-i is greater than or equal to the subexpression of En that replaces it. m To show that En holds in C{7i), we closely follow the proof of the orthoarguesian equation . We recall that in lattice C{H), the meet corresponds to set intersection and < to C. We replace the join with subspace sum + throughout: the orthogonality hypotheses permit us to do this on the left-hand side of the conclusion P, Lemma 3 on p. 67], and on the right-hand side we use a-\-b C a U 6. Suppose X is a vector belonging to the left-hand side of (|5.7|). Then there exist vectors xo e ao, Vo^bo, . . . , Xn-i G a„_i, Hn-i G bn-i such that x = Xq + yo = ■ ■ ■ = x„_i + yn-i- Hence Xk — xi=yi — ykioTO<k,l<n~l. In ( ^.71) we assume, for our induction hypothesis, that the components of vector x = xo + yo can be distributed over the leftmost terms on the Megill and Pavicic (2000) 30 right-hand side of the conclusion as follows: • • ■ C bo +( ao n ( ai +((ao+ai) n (bo+bi) Vo xo xi x^ _ x^ _y^ _^y_^^ ^^ n ^ Xi ^0 ^ n ^ Xi Xq Xi Xq — Xi Xl + (xo - Xi) Xo yo + xo = X In particular if we eliminate the right-hand ellipses we obtain a C(7i) proof of the starting equation Ei, which is the 30A law; this is the basis for our induction. Let us first extend ( |5.7| ) by adding variables a„ and bn to the hypothesis and left-hand side of the conclusion. The extended ( ^7|) so obtained obviously continues to hold in C(H). Suppose X is a vector belonging to the left-hand side of this extended ( p.7|) . Then there exist vectors Xq G ao, yo E bo, . . . , x^ G a^, y„ G 6„ such that x = Xq + Vo = ■ ■ ■ = Xn + Vn- Hence Xk — xi = yi — yk for < k,l < n. On the right-hand side of the extended ( |5.7| ), for any arbitrary subexpression of the form (a^ U a^) fl (6j U 6^), where i,j<n, the vector components will be distributed (possibly with signs reversed) as Xi — Xj G ai+aj and x, — Xj = —yi + yj G bi+bj. If we replace (aj U aj) fl (foj U bj) with (oj U aj) fl (6j U bj) fl (((flj U a„) fl {bi U 6„)) U ((oj U a„) n (&j U bn))), components Xj and Xj can be distributed as (tti+aj) n (bi+bj) n (( (ai+a„) n {bi+b tAj If tXj /l -yi + %• a^i Xn -?/* + ?/. n (&,+b„))) Xi Xr, \ \ Xj ~r Xfij Jb j lAj rj so that Xi — Xj remains an element of the replacement subexpression. We continue to replace all subexpressions of the form (oj U Uj) fl (6j U bj), where i,j < n, as above until they are exhausted, obtaining Figure 9: (a) Greechie diagram for L46-7; (b) Greechie diagram for L46-9. That En {n > 3) cannot be inferred from the 40A law follows from the fact that the 40A (5) law holds in L46-7 (Fig. |^) while (ai — ^i 03) fl (01=02) < 02 —^1 03 fails in it. L46-9, Fig. ^ Megill and Pavicic (2000) 31 is the only other lattice with this property among all Greechie 3-atoms-in-a-block lattices with 22 atoms and 13 blocks. L46-7 and L46-9 are most probably the smallest Greechie 3-atoms-in-a-block lattices with that property: we scanned some 80% of smaller lattices and did not find any other. D Theorem 5.3. In any nOA we have: (n) This also means that 01 = 02 being equal to one is a relation of equivalence. Proof. The proof is analogous to the proof of the Theorem [4.1U|. D As with the Theorem [4.10| there is an open problem whether (oi — >i 03) fl (01 = 02) < 02 ^1 03 follow from Eq. ( |5.9|) . The fact that Eq. (|5.9| ) fails in L46-7 and L46-9 for n=5 indicates that they might. 6 Distributive Properties That Hold in C{H) The distributive law does not hold in either orthomodular or Hilbert lattices, as it would make them become Boolean algebras; indeed the failure of this law is the essential difference between these lattices and Boolean algebras. But by using the Godowski and orthoarguesian equations that extend the orthomodular ones, we can also extend the distributive properties of OMLs such as those provided by F-H. These can give us additional insight into the nature of the distributive properties of Hilbert lattices, as well as provide us with additional methods for further study of these lattices. In this section we show several distributive properties that imply the Godowski and orthoarguesian equations they are derived from, meaning that they are the strongest possible in their particular form. Definition 6.1. Let us call the following expression a chained identity.' ai^an = (oi = 02) ■ ■ ■ n (a„_i = a„), n = 2,3,4,... (6.1) Lemma 6.2. In any OML, the chained identity ai=a„ commutes with every term (polyno- mial) constructed from variables ai, . . . , a^ "n- Proof. In any OML, from ( p.8| ) we have (a = 6) fl (6 = c) = (a = 6) fl (a = c). Using this, we rewrite ai=a„ as (ai = 02) ■ ■ ■ fl (ai = a„). In any OML we also have aCa = b. Repeatedly applying the commutation law aCb & aCc =^ aCb fl c, we prove aiCai=a„. Similarly, for any 1 < i < n we have aiCai=an- Repeatedly applying the commutation laws aCc & bCc =^ a U bCc and aCb =^ a'Cb, we can build up tCai=an for any expression t constructed from variables ai, . . . , a„. As an exercise, the reader is invited to show an alternate proof using (|3.9|). D Megill and Pavicic (2000) 32 Theorem 6.3. In any OML in which the Godowski equation n-Go holds, the Godowski 7 identity ai=a„ commutes with any term constructed from variables Oi, . . . , a„. Proof. Lemma |6.2| and ( p.llj ) . D We can use this commutation relationship in conjunction with F-H to obtain immediately simple distributive laws that hold for any nGO, such as (ai=a„) fl (s U t) = ((ai=a„) fl s) U ((ai=a„) n t), where s and t are any terms constructed from variables Oi, . . . , a„. More general laws are also possible, as Theorem ^^ below shows. Lemma 6.4. In any OML the following inferences hold. aCd & hCd & bnd<c<d => an {bU c) = (aHb) U {an c) (6.2) aCd & bCd & bnd<c<d => bn {aU c) = {bn a) U {bn c) (6.3) aCd & c<d<b' => c n (a U 6) = (c n a) U (c n 6) (6.4) Proof For (|]2]): a H (6 U c) = a H (fe U (c H d)) =[using 6C(/, cCrf] a H ((fe U c) n (6 U (i)) = (6 U c) n (a n (6 U d)) =[using aCd, bCd] (6 U c) n ((a n b) U {a n d)) =[using b U cCa fl 6, an^Caflci] ((6Uc) fl (afl 6)) U ((6U c) fl (a n rf)) = (anb) U {an {dn {bU c))) =[usmg dCb, dCc] {anb)U {an{{dnb)U (dnc)) =[smcednb= bncandc< d] (aflfo) U(an((&nc) Uc)) = {anb)U (ana). For (|63): fen(aUc) < {bn{aUd) =[usmgbCd, aCd] {bna)U{bnd) =[usmgbnd = bnc] (6 n a) U (6 n c). The other direction of the inequality is obvious. For (^): en (aUb) = c n d n {a U b) =[using dCa, dCb] c n {{d n a) U {d n b)) = c n ((d n a) u 0) = (c n a) u = (c n a) u (c n &). n In passing we note that ( |6.2| )-( [6^ ) are examples of OML distributive properties that cannot be obtained directly from F-H because a does not necessarily commute with either 6 or c (lattice M02 would violate these conclusions). Also, the conclusion of ( |6.4| ) does not hold under the weaker hypotheses of ( |6.2|) since the inference would fail in OML L42 (Fig. |^). We also mention that (|6.2|)-(|H^) all fail in lattice 06 and thus are equivalent to the orthomodular law. The next theorem shows examples of more general distributive laws equivalent to n-Go, where the variables a, b, and c are not necessarily equal to any other specific term and may be different from variables oi, . . . , an- The hypotheses of ( |6.6[ ) and ( |6.7| ) can also be replaced by those of (|6.8|) to obtain simpler though somewhat less general laws. Definition 6.5. Let us call the following expression a chained implication.- dcf ai^a„ = (ai ^1 a2)---n(a„_i ^1 a„), n = 2,3,4, ... (6.5) Megill and Pavicic (2000) 33 Theorem 6.6. Let t he any term constructed from variables ai, . . . , a„. Then in any nGO (n > 3), we have the following distributive laws for any variables a, b, c not necessarily in the list ai, . . . , a„; ai=a„ < a < ai^a„ & bCt & bnt<c<t & 6 U c < a„ — >i ai =^ a n (6 U c) = (a n 6) U (a n c) (6.6) 0'i=cin ^ CL ^ CLi-^CLn & bCt & bCit < c < t & 6Uc<a„ — >i ai =^ bn{aUc) = {bna)U{bnc) (6.7) 0-1=0-71 < o < Oi'-^Un & c < t < b' & 6Uc<a„ — i>i ai ^ en (a U 6) = (en a) U (en 6) (6.8) /n particular, when t is aid a„ //or ( |g. 6| j and ( jgT^j / or a[j //"or ( |g.<^j /, an OML m which any one of these inferences holds is an nGO and vice versa. Proof. For (|6.6|) : Let s abbreviate a n (a„ ^i ai). By (|3.11|) we have (ai^a,„) n (a„ ^i ai) = ai=an = ai=an. Hence from the first hypothesis ai=a„ = (ai=a„) n (a„ — ^i ai) < a n (a„ — i>i tti) < (ai^a„) n (a„ ^i ai) = ai=an, so s = a n (a„ — i>i ai) = ai=a„ and by Lemma |6.2| sCt. Using ( |6.2D , we obtain ai=a„ < a < ai^a„ & bCt & 6nt<e<t ^ s n (6 U e) = (s n 6) U (s n e) . Since 6 U e < a„ ^i ai , it follows that sn(6Ue) =an(foUe), sn6 = an6, and s n e = a n e. In a similar way we obtain ( |6.7| ) and ( |6.8| ) from ( |6.3| ) and (O) respectively. To obtain the nGO law from ( p.6|) , we substitute ai=a„ for a, ai n a„ for t and e, and a^ for h. The hypotheses of (|6.6| ) are satisfied in any OML, and the conclusion becomes (ai=a„) n (a„ ^i ai) = ((ai=a„) n a'J U ((ai=a„) n (oi n a„)) =[using (|3.46|) ] ((ai=a„) n a'l) U ((ai=a„) n (ai n a„)) < a'l U (ai n a„), which is (|3.13| ). To obtain the nGO law from (|6.7| ), we make the same substitutions as above. The 1 1 conclusion becomes a^ n ((ai=art) U (a„ n ai)) = (a^ n (ai=a„)) U (a^ n a„ n ai) = a^ n 7 7 N^,rT„ r / „ N, ,//,„// 7 ai=a„) =[using (|3.46|) ] a'^n(ai=a„) < a[. Therefore (aina„)U((a^n((ai=a„)U(a„nai))) < 1 (fli n a„) U a[ = ai — s> a„. The left-hand side evaluates as (ai n a„) U ((a^ n ((ai=a„) U (a„ n ai))) = ((oi n an) U a^) n ((ai=a„) U (a„ n ai)) > ((oi n a„) U a^) n (ai=a„) = ai=a„, establishing ( |3.13| ). 7 To obtain the nGO law from ( |6.8|) , we substitute ai=an for a, a'^ for t and e, and ai n a^ for 6. After that the proof is the same as for ( |6.7| ). D In a 30A or 40A we can also derive distributive properties that are stronger than those that hold in OML. In fact the laws we show in Theorems ^^ and |6.9| below are strong enough to determine a 30A or 40A. First we prove a technical lemma. Megill and Pavicic (2000) 34 Lemma 6.7. In any OML we have: (a ^1 c) n ((a ^1 c) n (6 ^i c))' n (a' ^i c) n (6' ^1 c) = (6.9) (a ^1 c) n (((a ^1 c) n (6 -^1 c))' -^i ((a' ^i c) n (6' -^i c))) < 6 ^i c, z = 1, 2 (6.10) Proo/. For (j^: By F-H we have d H eH cH {{d ^i c)' U (e ->i c)') = (d H e H c H (d ^i c)') U (d n e n c n (e ^1 c)') = U = 0. From {^ we have d n e n (rf ^i c) = c? n e n c. Combining these we have dflefl {d ^i c) fl (((i ^i c)'U (e ^i c)') = 0. Substituting (a' -^ c) for d and (6' — >■ c) for e and simphfying with ( |4. 12| ) gives the result. For (|6.10|) , z = 1: Expanding the definition of — >j (i = 1) and applying F-H, we have (a ^1 c) n (((a ^1 c) n {b ^1 c))' ^, {{a' ^i c) n (fe' ^i c))) = ((a ^i c) n ((a ^i c) n (6 ^1 c))) U ((a ->i c) n ((a ^i c) n (6 ^1 c))' n (o' ^1 c) n {b' ^1 c)) = [using (|OD ] ((a -^1 c) n (6 ^1 c)) U < (6 ^1 c). For (|6.10|) , z = 2: Expanding the definition of ^2 and applying F-H, we have {d — >-i c)n(((rf^i c)n(e^i c))' ^2 (rfne)) = ((rf-^1 c)nc^ne)u((d^i c)n(e->i c)n(rfne)') = [using (U)] (d n e n c) U ((d -^1 c) n (e -^1 c) fl (d n e)') < (e' U (e n c)) U (e -^^ c) = e ^1 c. Substituting (a' — > c) for d and (6' — > c) for e and simplifying with ( |4.12| ) gives the result. D Theorem 6.8. An OML in which d<a-^ic k dr]{b^i c) <e & e U / < a=6 => (in(eU/) = (dne)U(dn/) (6.11) /io/(i5 is a 30A and wee versa. Proof. Assume that (|6.11|) holds. Substitute a — s>i c for d, {{a — >i c) fl {b — >i c))' — >i ((a' — >i c) n (6' — i>i c)) for e, and ((a — i>i c) fl (6 -^1 c))' — »2 ((a' -^1 c) fl (6' — i>i c)) for /. It is easy to see the hypotheses of ( |6.11| ) are satisfied [use ( [4.14| ) to establish the third hypothesis]. Using ( [4.14| ), the left-hand side of the conclusion evaluates to (a ^1 c) fl (a=6). The right-hand side is ((a ^1 c) n (((a ^1 c) fl (6 ^1 c))' ^1 ((a' ^1 c) n (6' ->i c)))) U ((a ^1 c) n (((a ^1 c)n{b ^1 c))' ^2 ((a' ^1 c)n(6' ^1 c)))), which by ( pJUD is < (6 ^1 c)U(6 -^1 c) = 6 ^1 c, establishing the 30A law Conversely, we show the 30A law implies ( p. 111) . In any OML we have from the third hypothesis d fl (e U /) < d n {a=b). From the first hypothesis and the 30A law (^l7| ) we obtain d fl a=b < dn {b ^i c). From the second hypothesis we have dn {b ^i c) < d fl e < (d n e) U (d n /). Thus d n (e U /) < (d n e) U (d n /). Since d n (e U /) > (d n e) U (d n /) holds in any ortholattice, we conclude d fl (e U /) = (d fl e) U (d fl /). D The proof of the 40A version of this theorem shows an application of the 30A distributive law ( |6.11|) , where we use it to construct the inner terms of the 40A equation. Megill and Pavicic (2000) 35 Theorem 6.9. An OML in which e<a^id & en{b-^id) < f & f ^ g < a=b => en{fUg) = {enf)U{eng) (6.12) holds is a 40A and vice versa. Proof. Assume that ( |6.12 ) holds. Since a=b < a=b, we also have that (|6.11 ) holds. So by Theorem 6.S we have {a^id)n{a=b) <b^id. (6.13) By Theorem ^]8| we also have (a ^i d) fl {a=c) < c — >i d, so (a ^i d) fl {a=c) fl (fee) < (c — >i d) n (6=c); applying Theorem ^]B| again to the right-hand side we obtain (a ^1 d) n (a^c) n (6=c) < fe ^i d . (6.14) In ( |6.12|) we substitute a ^i d for e, a=b for /, and (a=c) fl (fee) for (7. It is easy to see the hypotheses of ( |6.12|) are satisfied, and the conclusion gives us (a ^1 d) n {a=b) = ((a ^1 d) n {a=b)) U ((a ^1 d) n {a=c) n (fee)) . (6.15) From (|6.13| ), (|6.14]) , and ( |6.15|) we conclude the 40A law For the converse, the proof that the 40A law implies (|6.12|) is essentially identical to that for Theorem 6.8. D 7 Conclusion Our investigation in the field of Hilbert lattices and therefore in the field of Hilbert space and its subspaces in previous sections resulted in several novel results and many decisive simpli- fications and unifications of the previously known results mostly due to our new algorithms for generation of Greechie lattices and automated checking of Hilbert space equations and lattice equations in general. So, the results have their own merit in the theory of Hilbert space, quantum measurements, and the general lattice theory, but as we stressed in the In- troduction, we were prompted to attack the problem of generating Hilbert lattice equations and their possible connections with the quantum states (probability measures) by recent de- velopment in the field of quantum computing. In particular, we are interested in the problem of making a quantum computer work as a quantum simulator. In order to enable this, we were looking for a way to feed a quantum computer with an algebra underlying a Hilbert space description of quantum systems. Boolean algebra underlies any classical theory or model computed on a classical computer and it imposes conditions (equations) on classical bits {0,1} with the help of classical logic gates. For quantum theory such an algebra is still Megill and Pavicic (2000) 36 not known. Quantum computation at its present stage manipulates quantum bits {|0), |1)} by means of quantum logic gates (unitary operators) following algorithms for computing par- ticular problems. A general quantum algebra underlying Hilbert space does exist, though. It is the Hilbert lattice we elaborated in Section §. However, its present axiomatic definition by means of universal and existential quantifiers and infinite dimensionality does not allow us to feed a quantum computer with it. What we would need is an equational formulation of the Hilbert lattice. This would again contribute in turn to the theory of Hilbert space subspaces which is poorly developed. It is significant that there are two ways of reconstructing Hilbert space starting from an ortholattice. One is a pure lattice one and it is presented in Section ^. The other one is a pure state one. [0 The equational approach unites them. There were only two classes of such equations known so far: Godowski's and Mayet's equations determined by the states defined on a lattice and 4- and 6-variable orthoarguesian equations determined by the projective geometry defined on it. To these ones, we add our newly discovered — in Theorem ^.2| — generalized orthoarguesian equations with n variables. In order to interconnect and simplify the already known results on the former equations and to obtain new results we analyze the interconnections between an ortholattice and states defined on it and obtain the following results. By Theorem 3.101 and Theorem 3^ the difference between classical and quantum states is that there is a single classical state for all lattice elements while quantum states for different lattice elements are different; By Theorem |3.3| a classical state defined on an ortholattice turns it into the Boolean algebra; By Theorem 3.10 a strong state defined on an ortholattice turns it into a variety smaller than OML in which Godowski's equations hold. On the other hand, '■) • by Theorem |3.6| there is a way of obtaining complex infinite dimensional Hilbert space from the Hilbert lattice equipped with several additional conditions and without invoking the notion of state at all. States then follow by Gleason's theorem. As for Godowski's and Mayet's equations we obtain the following results: Theorems |3.12| , |3.13| , |3.15| , and |3.16| present several new results on and simplifications of Godowski's equations based on the operation of identity given by the Definition ^]4| which is also used to give a new formulation of orthomodularity by Theorem |2] New Greechie diagrams in which Godowski's equations with up to seven variables fail are presented in Figures |^, ^, and ^. They were obtained by a new algorithm for generating Greechie diagrams and a new algorithm for automated checking of passage of lattice equations through them |T^ (see footnote at the end of Section and the Megill and Pavicic (2000) 37 comment at the end of Section ^ and they are by several atoms and blocks smaller than the previously known ones. This makes preliminary checking of any conjecture related to Godowski's equations a lot faster; In Theorem p.20| Mayet's examples which were apparently supposed to differ from Godowski's equations are derived from Godowski's equations. As for the orthoarguesian equations, their consequences, and generalizations, the clue for their unification were 3- and 4-variable orthoarguesian identities (3-oa and 4-oa, defined in Definition |4.1j ) which served us to obtain the following results: A 4-variable Eq. (|4.8| ), the 40A law, is equivalent to the original 6- variable orthoar- guesian equation as given by A. Day as we show in Theorem |4.7|; All lower than 6- variable consequences of the original orthoarguesian equation that one can find in the literature can be reduced to the 3- variable Eq. (|4.71), the 30A law, as illustrated by Theorems 4.8 and 4.9; There is a 3-variable consequence of the 40A law which is not equivalent to the 30A law as proved in Theorem [4.11|; There is an n-variable generalization of the orthoarguesian equations, the nOA law which holds in any Hilbert lattice, as proved in Theorem p.2|, and which cannot be derived from the 40A law, as proved in Theorem |5.3| ; The nOA law added to an ortholattice turns it into a variety smaller than OML as shown by Theorems 4.10, 4.2, and ff^ Each ?7,0A determines a relation of equivalence as proved by Theorem 5.3 In the end, different distributive properties that hold in the lattice of closed subspaces of any Hilbert space are given in Section |^ and several intriguing open problems are formulated following Theorems |2]^, p.l5| , |3.16| , p.21| , ^l3| , [4.10| , [4.11| , and p3| , as well as preceding The- orems |3.2CI| and |3.22| . Open problems are also to attach a geometric interpretation to nOA and to rigorously prove that infinite dimensional Hilbert space contains an infinite sequence of relations of equivalence. The latter claim would immediately follow from condition 5 of Theorem p.6| , if we could prove that for no n can the tt-OA law can be inferred from the (n — 1)0A law starting with the n = 5 case proved in Theorem |5.2| . [p^ , p. 379] References [1] p. W. Shor, Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer, SIAM J. Comp. 26, 1484-1509 (1997), http://xxx.lanl.gov/abs/quant-ph/9508027 . Megill and Pavicic (2000) 38 [2' L. K. Grover, Quantum Computers Can Search Arbitrarily Large Databases by a Single Query, Pliys. Rev. Lett. 79, 4709-4712 (1997), |http://xxx.lanl.gov/abs/quant-| ph/9706005| . [3] B. M. Boghosian and W. Taylor, Simulating Quantum Mechanics on a Quantum Com- puter, Physica D 120, 30-42 (1998), |littp://xxx.lanl.gov/abs/quant-ph/9701016| . [4] V. Vedral and M. B. Plenio, Basic Quantum Computation, Prog. Quant. Electron. 22, 1-40 (1998), Ihttp: / /xxx.lanl.gov/abs/quant-ph/9802065| . [5] M. Pavicic and N. D. Megill, Non-Orthomodular Models for Both Standard Quantum Logic and Standard Classical Logic: Repercussions for Quantum Computers, Helv. Phys. Acta 72, 189-210 (1999), |littp://xxx.lanl.gov/abs/quant-ph/9906T0Tl . [6] C. J. Isham, Lectures of Quantum Theory, Imperial College Press, London, 1995. [7] P. R. Halmos, Introduction to Hilbert Space and the Spectral Theory of Spectral Multi- plicity, Chelsea, New York, 1957. [8] G. Kalmbach, Orthomodular Lattices, Academic Press, London, 1983. [9] P. Mittelstaedt, Quantum Logic, Synthese Library; Vol. 18, Reidel, London, 1978. [10] S. S. Holland, JR., The Current Interest in Orthomodular Lattices, in Trends in Lattice Theory, edited by J. C. Abbot, pages 41-126, Van Nostrand Reinhold, New York, 1970. [11] B. Sobocihski, Equational Two Axiom Bases for Boolean Algebras and Some Other Lattice Theories, Notre Dame J. Formal Logic 20, 865-875 (1979). [12] S. S. Holland, JR., Orthomodularity in Infinite Dimensions; a Theorem of M. Soler, Bull. Am. Math. Soc. 32, 205-234 (1995). [13] J. J. Zeman, Quantum Logic with Implications, Notre Dame J. Formal Logic 20, 723-728 (1979). [14] M. Pavicic, Minimal Quantum Logic with Merged Implications, Int. J. Theor. Phys. 26, 845-852 (1987). [15] M. Pavicic, Unified Quantum Logic, Found. Phys. 19, 999-1016 (1989). [16] M. Pavicic and N. D. Megill, Binary Orthologic with Modus Ponens Is either Ortho- modular or Distributive, Helv. Phys. Acta 71, 610-628 (1998). [17] B. D. McKay, N. D. Megill, and M. Pavicic, Isomorph-Free Exhaustive Generation of Greechie Diagrams and Automated Checking of Their Passage by Orthomodular Lattice Equations, Int. J. Theor. Phys., 39, No. 10 (2000). [18] P.-A. Ivert and T. Sjodin, On the Impossibility of a Finite Propositional Lattice for Quantum Mechanics, Helv. Phys. Acta 51, 635-636 (1978). Megill and Pavicic (2000) 39 [19 [20 [21 [22 [23 [24 [25; [26; [27; [28 E. G. Beltrametti and G. Cassinelli, The Logic of Quantum Mechanics, Addison- Wesley, 1981. F. Maeda and S. Maeda, Theory of Symmetric Lattices, Springer- Verlag, New York, 1970. M. P. Soler, Characterization of Hilbert Spaces by Orthomodular Spaces, Comm. Alg. 23, 219-243 (1995). R. Mayet, Some Characterizations of Underlying Division Ring of a Hilbert Lattice of Authomorphisms, Int. J. Theor. Phys. 37, 109-114 (1998). A. M. Gleason, Measures on the closed subspaces of a Hilbert space, J. Math. Mechanics 6, 885-893 (1957). M. J. M§czyhski, Hilbert Space Formalism of Quantum Mechanics without the Hilbert Space Axiom, Rep. Math. Phys. 3, 209-219 (1972). R. Godowski, Varieties of Orthomodular Lattices with a Strongly Full Set of States, Demonstratio Math. 14, 725-733 (1981). R. Mayet, Equational Bases for Some Varieties of Orthomodular Lattices Relatied to States, Algebra Universalis 23, 167-195 (1986). R. Godowski and R. Greechie, Some Equations Related to the States on Orthomodular Lattices, Demonstratio Math. 17, 241-250 (1984). R. J. Greechie, A Non-Standard Quantum Logic with a Strong Set of States, in Current issues in quantum logic, (Proceedings of the Workshop on Quantum Logic held in Erice, Sicily, December 2-9, 1979, at Ettore Majorana Centre for Scientific Culture), edited by E. G. Beltrametti and B. C. van Fraassen, pages 375-380, Plenum Press, New York, 1981. M. Haiman, Two Notes on the Arguesian Identity, Algebra Universalis 21, 167-171 (1985).