From news@nntp-server.caltech.edu Fri Dec 9 20:34:59 1994 Return-Path: Received: from piccolo.cco.caltech.edu by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA10781; Fri, 9 Dec 94 20:34:59 EST Received: from gap.cco.caltech.edu by piccolo.cco.caltech.edu with ESMTP (8.6.7/DEI:4.41) id RAA03400; Fri, 9 Dec 1994 17:34:54 -0800 Received: by gap.cco.caltech.edu (8.6.7/DEI:4.41) id RAA10180; Fri, 9 Dec 1994 17:34:42 -0800 To: mlist-cube-lovers@nntp-server.caltech.edu Path: whuang From: whuang@cco.caltech.edu (Wei-Hwa Huang) Newsgroups: mlist.cube-lovers Subject: Newbie Date: 10 Dec 1994 01:34:37 GMT Organization: California Institute of Technology, Pasadena Lines: 4 Message-Id: <3cb0jd$9tq@gap.cco.caltech.edu> Nntp-Posting-Host: accord.cco.caltech.edu X-Newsreader: NN version 6.5.0 #12 (NOV) Subscribe me to this list, please. -- Wei-Hwa From BRYAN@wvnvm.wvnet.edu Fri Dec 9 22:20:45 1994 Return-Path: Received: from WVNVM.WVNET.EDU by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA14904; Fri, 9 Dec 94 22:20:45 EST Message-Id: <9412100320.AA14904@life.ai.mit.edu> Received: from WVNVM.WVNET.EDU by WVNVM.WVNET.EDU (IBM VM SMTP V2R2) with BSMTP id 4266; Fri, 09 Dec 94 22:20:47 EST Received: from WVNVM.WVNET.EDU (NJE origin BRYAN@WVNVM) by WVNVM.WVNET.EDU (LMail V1.2a/1.8a) with BSMTP id 5379; Fri, 9 Dec 1994 22:20:47 -0500 X-Acknowledge-To: Date: Fri, 9 Dec 1994 22:20:42 -0500 (EST) From: "Jerry Bryan" To: "Cube Lovers List" Subject: Normal Subgroup Question On 12/07/94 at 20:45:00 Martin Schoenert said: >Unfortunately C is *not* a normal subgroup of CG, and therefore CG/C is >*not* a group. If we want to apply group theory, we need a better model. >I argue that G is indeed a good model for the 3x3x3 cube. I responded at great length, showed a group for CG/C, and concluded as follows. >I guess this must mean that C[C], C[E], and C[C,E] are all normal >subgroups of their respective CG's, but that C[C,F], C[E,F], and >C[C,E,F] are not. That should not be surprising. Having the >Face-centers there only as a frame of reference and never moving >is not the same as having them there and really moving (as when you >rotate the entire cube). This just *has* to be wrong. I just don't see any way that any of the flavors of C are a normal subgroup of their respective flavors of CG. The presence or absence of the Face-centers can't have anything to do with it. I was jumping to the conclusion that since I found a group for some of the flavors of CG/C, that therefore the respective C's must be normal. I have reread my note, and it still looks to me like I found groups for all the CG/C's I discussed. I would invite instruction and correction from any of you group theory experts out there, but here is the way it looks to me. Using G and H generically for a group and subgroup (not necessarily cubes at all), G/H is a group if H is a normal subgroup of G, under the "natural" operation {Xh} * {Yh} = {(XY)h} (where {Xh} etc. denotes all h in H.) Coset notation would be (xH)(yH)=(xy)H. Under these circumstances, G/H is the factor group of H in G. My group operation on the cosets not the "natural" operation. It gets around the fact that C is not normal by picking specific rather than arbitrary elements of the cosets in order to perform the group operation, namely a picking specific element which fixes the same cubie for all cosets. I guess this means that CG/C is not the factor group of C in CG (such a thing being impossible), but by golly it still looks like a group to me under the "unnatural" operation ?? = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = Robert G. Bryan (Jerry Bryan) (304) 293-5192 Associate Director, WVNET (304) 293-5540 fax 837 Chestnut Ridge Road BRYAN@WVNVM Morgantown, WV 26505 BRYAN@WVNVM.WVNET.EDU From mschoene@math.rwth-aachen.de Sat Dec 10 09:15:04 1994 Return-Path: Received: from samson.math.rwth-aachen.de by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA08876; Sat, 10 Dec 94 09:15:04 EST Received: from hobbes.math.rwth-aachen.de by samson.math.rwth-aachen.de with smtp (Smail3.1.28.1 #11) id m0rGSXF-000MPHC; Sat, 10 Dec 94 15:12 MET Received: by hobbes.math.rwth-aachen.de (Smail3.1.28.1 #19) id m0rGSXE-0000PvC; Sat, 10 Dec 94 15:12 PST Message-Id: Date: Sat, 10 Dec 94 15:12 PST From: "Martin Schoenert" To: cube-lovers@life.ai.mit.edu In-Reply-To: "Jerry Bryan"'s message of Thu, 8 Dec 1994 15:42:36 -0500 (EST) <9412082301.AA24053@life.ai.mit.edu> Subject: Re: Re: Models for the Cube Jerry Bryan wrote in his e-mail message of 1994/12/08 On 12/07/94 at 20:45:00 Martin Schoenert said: >Unfortunately C is *not* a normal subgroup of CG, and therefore CG/C is >*not* a group. If we want to apply group theory, we need a better model. >I argue that G is indeed a good model for the 3x3x3 cube. Well, with great fear and trepidation, let's see if we can't interpret CG/C in such a way that it is a group. I agree that your statement above is correct, but I believe we are interpreting C, G, and CG somewhat differently. I have discussed this subject before, but armed with some better notation suggested via Dan Hoey, I think I can do it again both more accurately and more succinctly. I think that we agree much more than we actually realize, and that it is mostly a matter of language. So your clarification was most welcome, and I hope mine is too. Jerry continued Dan's suggestion is to carefully distinguish which of the various types of cubies we are talking about. I have done a lot of work with (for example) corners-only-cubes-without-centers, corners-only- cubes-with-centers, etc. When we talk about the set C of rotations, Dan suggests specifying such things as C[C] (Corners-only), C[E] (Edges-only), C[C,F] (Corners-plus-Face-centers), etc. The C[C] thing looks funny, using C in two such different ways, but there are only so many letters. I want to reserve lower case c for elements of C, so I will live with C[C]. I would suggest extending the notation to G and Q, so that (for example) the corners-only with Face-centers group we have called GC could instead be called G[C,F] = , and the 2x2x2 cube could be called G[C]= because there are no Face-centers. Let's see whether I understand this correct. Let CG again be the complete cube group generated by the face turns and the rotations, let G be its subgroup of index 24 generated by the face turns, and C the subgroup of size 24 generated by the rotations. CG can be represented as a permutation group on 54 points. On this set it makes three orbits, called C(orners), E(dges), and F(ace-centers), of sizes 24, 24, and 6. [A sidenote. Old e-mails in Cube-Lovers often talk about the 12 ``orbits'' of the cube group G in the group that you get when you are allowed to take the cube apart. This group has structure (S(8) 3) (S(12) 2). Strictly speaking, these are not ``orbits'' but ``cosets'' instead.] We can now look at the operation of CG (and C and G) on the 8 sets [], [C], [E], [C,E], [F], [C,F], [E,F], and [C,E,F] (where [X,Y] here means the (disjoint) union of the orbits X and Y). This gives us 8 groups to look at, together with their respective subgroups induced by C and G. Clearly CG[] is trivial, and CG[C,E,F] = CG. Such a group, e.g., CG[C], is a model for what we get when we remove the color tabs from the other orbits, e.g., for CG[C] we would remove the color tabs from the edges and the faces. A little bit of group theory. Each of those 8 groups CG[] is a homorphic image of CG. That means there is a homomorphism from CG to CG[]. This homomorphism is actually very easy to describe: you get the image of an element by simply forgetting what that element does on the other orbits. The kernel of this homomorphism is the subgroup of elements of CG that do nothing on and only permute the points in the other orbits. What this means is that each CG[] is a factor group of CG. Jerry continued The "standard Singmaster model" (my terminology) would be written as G[C,E,F] = . (Well, I think Singmaster would write it as G[C,E,F] = , since I think he prefers to accept H turns as single moves.) However, I tend to work with G[C,E] = instead. I consider G[C,E] to be equivalent to G[C,E,F] for most purposes because G fixes the Face-centers, as does M-conjugation. I have described this equivalence before as the Face-centers simply providing a frame of reference that can be provided in other ways. However, when you step outside the friendly confines of G=, it does start to matter whether the Face-centers are there or not. As an example important to this discussion, if you consider CG=, then it makes a considerable difference whether you are talking about CG[C,E] or CG[C,E,F]. Correct. Since G fixes the faces, G[C,E,F] and G[C,E] are isomorphic. But CG[C,E,F] and CG[C,E] are not isomorphic, and neither are C[C,E,F] and C[C,E]. Jerry continued For example, G[C,E] = can be simulated on a real cube by removing the color tabs from the Face-centers, by restricting yourself to Q moves only (no whole cube rotations or slices), and by declaring the cube solved only when the Up color is up and the Front color is Front. Notice that with the Face centers absent, you can make the cube look solved even when it isn't. It will be rotated instead, but it won't be solved. This model may seem a little simple-minded. Why are no rotations allowed, and why don't you count it as solved when it looks solved? But computers are simple-minded. My programs only consider things equal when they are literally equal, and equivalence is something I have to program in. As an example I have used before, consider G[C]=, modeled in the real world by a 2x2x2 pocket cube or by removing both the edge and Face-center color tabs from a 3x3x3 cube. Take a solved cube in G[C] and perform RL'. The cube will still look solved, but it will be rotated. The memory cells in my program will not be the same for I as for RL', but I want to treat them as equivalent, as would nearly everybody with a real world 2x2x2 cube in their hands. Maybe a little convention would help. We could say that a cube is *completely solved* if all the up-color tabs are on the up-face, all the right-color tabs are on the right-face, etc. And a cube is *solved up to rotations* if all the tabs on each face have the same color, i.e., if it can be completely solved with a rotation of the entire cube. Talking about the groups, only the identity is completely solved, but all elements in C[] are solved up to rotations. In this language CG[C] is a model for the complete solution of the 2x2x2 cube, and a supplement for C[C] in CG[C] is a model for the solution up to rotations of the 2x2x2 cube. And of course, most of the time we are interested in solutions up to rotations. Jerry continued This is where I have claimed before that a model that treats RL' the same as I is G[C]/C[C]. The idea is that G[C]/C[C] is a group with the identity being C[C] itself (i.e., rotating the cube is "doing nothing".) The proof is fairly simple. From each element (coset) of G[C]/C[C], pick the unique permutation that fixes a particular corner, say UFR, and form a new set G[C]* containing the one element chosen from each coset. The elements of G[C]/C[C] are sets (namely cosets), but the elements of G[C]* are permutations which are also in G[C]. In particular, G[C]* = . Hence, G[C]* is a group. Note that the generators of G[C]* are the twists of those faces which are diagonally opposed to the corner fixed by the selection function from G[C]/C[C] to G[C]*. Hence, the generators fix the same corner as the selection function, showing that is really the same set as G[C]*, namely the set of all cubes in G[C] for which the UFR corner is fixed. Finally, there is an obvious isomorphism between G[C]/C[C] and . Namely, to multiply two cosets, map each to via the selection function, perform the multiplication there using standard cube multiplication, and map the product back to a coset. Hence, G[C]/C[C] is a group. I agree mostly but not completely. First I claim that we are interested not in the cosets of C[C] in G[C], but rather in the cosets of C[C] in CG[C]. Now since G[C] = CG[C] this doesn't seem to make any difference. But for a different set of orbits, G[] may be different from CG[], and C[] will then not be a subgroup of G[]. So in those cases it doesn't make sense to speak of the cosets of C[] in G[]. Second your usage of G/H. Many group theory textbooks restrict this notation to the case when H is a normal subgroup of G. Others use G/H in general for the set of cosets of H in G. But whenever they write ``the group G/H'' or ``G/H is a group'', they always mean that H is normal in G, and that G/H is the factor group. I would be happy if you wrote about ``the set G[C]/C[C] with the multiplication defined by ... is a group'' instead of ``G[C]/C[C] is a group''. The reason why I think it is important to be carefull is that many properties carry over from G to a proper factor group G/H, but do not carry over from G to ``the set G/C with the multiplication defined by ...''. I shall return to this point below. I agree that G[C]* is indeed a group. You do exactely the same thing that I did in my message. You pick a set of represtatives that forms a subgroup, which I called a supplement for C[C]. Then you define the multiplication using those representatives. I think that it is easier to work with the supplement instead of the structure G[C]/C[C] with the induced multiplication, but that is clearly a matter of taste. Jerry continued A similar argument applies to G[E]/C[E] except that we have to fix an edge cubie instead of a corner cubie. Almost. But there is a tricky problem here. Again G[E] = CG[E], so it doesn't matter whether we talk about G[E]/C[E] (as you prefer) or about CG[E]/C[E] (as I prefer). Again we can find a supplement for C[E] in CG[E], namely the subgroup of all elements of CG[E] that leave a particular edge cubie fixed. Assume that we fix the upper-right edge cubie, then this supplement is . But this does *not* respect costs. That is take an element e of CG[E]. Let r be its representative in , i.e., c e = r, where c is a rotation of the entire cube. The the costs of the two elements, viewed as elements of CG[E] is clearly the same (remember, rotations cost nothing). But the cost of r, viewed as an element of *with this generating system*, may be higher. For example take R[E] * r[E]' (where r is the rotation of the entire cube). In CG[E] this element has cost 1. And this element lies in , since it fixes the upper-right edge cubie. But the cost of this element *with respect to the generating system L[E],D[E],F[E],B[E]* is not 1. We can repair this by choosing a different generating system for , for example the system L[E],D[E],F[E],B[E],R[E]*r[E]',U[E]*u[E]'. So in general a model for the solution up to rotations for a certain set , is a supplement of C[] in CG[], with a generating system that respects costs. Jerry continued A similar argument applies to G[C,E]/C[C,E] except we have to fix an edge cubie and restrict C to even permutations. Dan calls the set of even rotations E, so let's call it G[C,E]/E[C,E]. (Still wish we had letters whose use did not conflict so blatantly.) But when we started, we were talking about CG/C, not about G/C. However, notice that when our model does not include Face-centers, we have = , = , and = . (I mean that the groups are equal, not that the Cayley graphs are the same.) Hence, speaking generically of the first two cases, we have C is in G, CG=G, and both CG/C and G/C are groups. In the last case, we have to say E is in G, EG=G, and EG/E is a group. But we can go one step further. Since there are no Face-centers, we can admit Slice moves or C as generators (it doesn't matter which), and we no longer have to restrict ourselves to even rotations. We can say G+[C,E]= and we will have C is in G+, CG+=G+, and CG+/C is a group which is the same size as EG/E. (G+ is twice as big as G, of course.) This is the reason why I think that it is better to talk about CG[C,E]/C[C,E]. As you say G[C,E] <> CG[C,E] (it has index 2), and C[C,E] is not a subgroup of G[C,E]. That your model works depends on the fact that their is a bijection between the set CG[C,E]/C[C,E] and G[C,E]/E[C,E]. This follows by a standard argument from the fact that E[C,E] = Intersection( G[C,E], C[C,E] ). Jerry continued I guess this must mean that C[C], C[E], and C[C,E] are all normal subgroups of their respective CG's, but that C[C,F], C[E,F], and C[C,E,F] are not. That should not be surprising. Having the Face-centers there only as a frame of reference and never moving is not the same as having them there and really moving (as when you rotate the entire cube). It would be most surprising. In fact C[C], C[E], and C[C,E] are *not* normal in their respective CG's. I don't see what face centers should have to do with it. Jerry continued After joining Cube-Lovers, I discovered that others had solved God's algorithm for the 2x2x2 long before me. I was expecting my solution to be 24*48 times smaller than theirs because I was using cosets of C and M-conjugates. But my solution was only 48 times smaller than theirs. By taking both cosets and M-conjugates I really had reduced by 24*48 times. However, everybody else who worked on the problem had modeled it as something like , fixing a corner. (Any other corner would do as well. There are eight conjugate groups, any of which would do as well as any other.) is 24 times smaller than in the first place, and as I said earlier, is equivalent to for most purposes anyway because of the fixed Face-centers. Hence, everybody else had a 24 times head start on me. (At the time, Dan suggested that I was increasing the size of the problem by 24 and then reducing it by 24*48 for a net reduction of 48. But that would only be true if the model were . Since the model was , there really was a reduction of 24*48. But does not really model the 2x2x2 cube, and is 24 times larger than it needs to be in the first place if you are trying to model the 2x2x2.) Allow me to translate this to a more group theoretic language. You are interested in finding God's algorithm for CG[C]. If e is any element of this group, then clearly it has the same costs as (c * e), where c is any element of C[C]. Thus you need only compute the cost for one representative of each right coset (C[C] * e). All those cosets have size 24, so using cosets reduces the problem by a factor 24. However, (c' * e * c) also has the same cost, so you only need one representative of each conjugacy class (e ^ C[C]). Taking those two approaches together means, that you need only look at one representative of the set { c1 * (c2' * e * c2) | c1, c2 in C[C] }. But we can also write this set as { c1 * e * c2 | c1, c2 in C[C] }. Such a set if usually called a *double coset* and written as (C[C]*e*C[C]). Most of those double cosets have size 576 = 24*24, but some are smaller (but of course all sizes are always multiples of 24, since each double coset is the union of single cosets). Thus using double cosets reduces the problem by a factor almost 576. Finally e has the same cost as (x' e x), where x is the reflection. Thus you only need one representative from each set { y' * c1 * e * c2 * y | c1, c2 in C[C], y in M[C] }. This reduces the problem by an total factor almost 1152. Jerry continued Modeling cubes without centers such as the 2x2x2 is trickier than it looks because of the requirement that rotations be treated as equivalent. I did it by using cosets of rotations; everybody else did it by fixing a corner. But before I realized all this, I went on a Quixotic chase for a model which would simultaneously be a true model for a 2x2x2 cube and would retain the cubic symmetry of the problem (whatever that means). There are articles in the archives concerning this subject, with the conclusion that no such model is possible because any true model would be isomorphic to , which does not have "cubic symmetry". I guess the "cubic symmetry of the problem" means that you should use M-conjugate classes. Lets first take a look at the 3x3x3 cube, i.e., CG[C,E,F] = CG. In this case you can use G as a supplement for C, i.e., as a system of representatives for the cosets (C * e). Now G is normal in CG, thus you can conjugate the elemenents of G with elements of C and stay in G. So there is a bijection between the representatives of the conjugacy classes of G under the conjugation by C and the representatives for the double cosets (C * e * C). In fact G is normal in MG, and there is a bijection between the representatives of the conjugacy classes of G under the conjugation by M and the representatives for the sets ((C * e * C)^M). This is the basis for applying the ``Lemma that is not Burnside's'' to count the number of such sets, as the real size of the cube. But in the case of the 2x2x2 cube without centers, i.e., CG[C], this is not possible. Finding such a model would mean finding a supplement of C[C] that is normal in CG[G], i.e., is fixed under conjugation by C[C]. And no such supplement exists. Jerry continued Recall that when I solved I used what Dan calls W-conjugate classes because W is the symmetry group for , and W-conjugate classes reduced the size of the problem by four times. This leads me to a question. The way I modeled the 2x2x2, I used M-conjugate classes of cosets and reduced the size of the problem by 48 times. If I were going to model , I would be very inclined not to use M-conjugate classes, but rather to use a subgroup of M which was the symmetry group of . The subgroup would have less than 48 elements, and I would get less than a 48 times reduction in the size of the problem. But a fixed corner model such as is isomorphic to a coset model such as /C[C], and M-conjugates are appropriate to the coset model. Therefore, my analysis of the situation is obviously very flawed. Can anybody see what is wrong? Yes I can ;-). The problem is in the statement ``and M-conjugates are appropriate to the coset model''. I think this problem comes from your unusual usage of the notation G[C]/C[C]. If C[C] was a normal subgroup of G[C] and G[C]/C[C] was the proper factor group, then the operation of M-conjugation would carry over from G[C] to the factor group (any such operation carries over to a factor group, provided that the normal subgroup is fixed, which is certainly the case here). But G[C]/C[C] is not the proper factor group, so there is no reason why the M-conjugation should carry over, and in fact it does not. Finally allow to correct a non-standard language again. In group theory one usually does not speak of the symmetry group of another group, but of the *automorphism group* of another group. Moreover you don't want to know the ``subgroup of M which was *the* automorphism group of '', but the ``subgroup of M which was *also a subgroup of* the automorphism group of '', because the automorphism group of is in fact much larger. In other word, you want to know the subgroup of M that fixes . This is a cyclic group of size 3, namely the rotation along the diagonal axis of the cube that goes through your fixed center and cyclically permutes D[C], B[C], and L[C]. Have a nice day. Martin. -- .- .-. - .. -. .-.. --- ...- . ... .- -. -. .. -.- .- Martin Sch"onert, Martin.Schoenert@Math.RWTH-Aachen.DE, +49 241 804551 Lehrstuhl D f"ur Mathematik, Templergraben 64, RWTH, 52056 Aachen, Germany From mschoene@math.rwth-aachen.de Sat Dec 10 09:21:41 1994 Return-Path: Received: from samson.math.rwth-aachen.de by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA09060; Sat, 10 Dec 94 09:21:41 EST Received: from hobbes.math.rwth-aachen.de by samson.math.rwth-aachen.de with smtp (Smail3.1.28.1 #11) id m0rGSde-000MPHC; Sat, 10 Dec 94 15:19 MET Received: by hobbes.math.rwth-aachen.de (Smail3.1.28.1 #19) id m0rGSdd-0000PvC; Sat, 10 Dec 94 15:19 PST Message-Id: Date: Sat, 10 Dec 94 15:19 PST From: "Martin Schoenert" To: cube-lovers@life.ai.mit.edu In-Reply-To: "Jerry Bryan"'s message of Thu, 8 Dec 1994 15:02:33 -0500 (EST) <9412082002.AA14755@life.ai.mit.edu> Subject: Re: Re: Models for the Cube I wrote in my e-mail message of 1994/12/07 But C is not the largest such group. The largest such group is M, i.e., the full group of symmetries of the entire cube. This is the reason why I prefer to view G as a subgroup of MG, which is the semidirekt product of M and G, even though I realize that MG is not physically realizable. Jerry Bryan answered in his e-mail message of 1994/12/07 But can't you speak of conjugates such as m'gm without regard to G being a subgroup of MG? I agree that MG seems like a very useful group, and it is a very nice model of what is going on. But doesn't g in G imply m'gm in G whether I ever heard of MG or not? Yes I certainly could. I think it is only a matter of taste. You seem to favor the physical model. There the reflection has no real realization, and it makes sense to distinguish between the rotations and the reflection. I look at the problem more from the computational aspect. I view the whole thing as a permutation group, and then there is no real reason to distinguish between the rotations and the reflection (both being ordinary permutations on 54 points). And when working with those groups in GAP, it is certainly a lot more convenient to work in MG and treat all of M uniformly, then to work in CG and to handle the reflection specially. Have a nice day. Martin. -- .- .-. - .. -. .-.. --- ...- . ... .- -. -. .. -.- .- Martin Sch"onert, Martin.Schoenert@Math.RWTH-Aachen.DE, +49 241 804551 Lehrstuhl D f"ur Mathematik, Templergraben 64, RWTH, 52056 Aachen, Germany From BRYAN@wvnvm.wvnet.edu Sat Dec 10 10:13:39 1994 Return-Path: Received: from WVNVM.WVNET.EDU by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA10971; Sat, 10 Dec 94 10:13:39 EST Message-Id: <9412101513.AA10971@life.ai.mit.edu> Received: from WVNVM.WVNET.EDU by WVNVM.WVNET.EDU (IBM VM SMTP V2R2) with BSMTP id 5452; Sat, 10 Dec 94 10:13:41 EST Received: from WVNVM.WVNET.EDU (NJE origin BRYAN@WVNVM) by WVNVM.WVNET.EDU (LMail V1.2a/1.8a) with BSMTP id 1045; Sat, 10 Dec 1994 10:13:42 -0500 X-Acknowledge-To: Date: Sat, 10 Dec 1994 10:13:33 -0500 (EST) From: "Jerry Bryan" To: "Cube Lovers List" Subject: Cubic Symmetry of the 2x2x2 (Again) The argument has been made that the 2x2x2 cube (or really any 2Nx2Nx2N) cube cannot have the "symmetry of the cube". In order for a real 2x2x2 cube to have the "symmetry of the cube", you would have to adopt unreasonable rules, such as no rotations (or if you use rotations they have a cost of at least 2) and the cube is only solved when the colors are oriented properly. But a 2x2x2 cube certainly feels like a real cube when you hold it in your hands. I offer the following interpretation that "sort of" gives the 2x2x2 cube the symmetry of the cube. Since I will only be talking about the 2x2x2, I will simplify the notation by talking about C, G, Q, etc. rather than C[C], G[C], Q[C], etc. As I have discussed several times before, my favorite model for the 2x2x2 is G/C (or CG/C, if you prefer; G=CG for the 2x2x2). The group operation is (xC)(yC)=(uv)C, where u and v are the elements of xC and yC, respectively, which fix a particular corner. (xC)(yC)=(xy)C doesn't work because C is not normal. There is an obvious isomorphism between G/C and , where the three q-turns are those which fix the same corner as the selection function for u and v. There are eight corners, and hence there are eight conjugate selection functions and eight conjugate subgroups G_m of the form which fix a particular corner. If you think of mapping G/C simultaneously and in parallel to the all the elements in the set {G_1, G_2, G_3, G_4, G_5, G_6, G_7, G_8}, then in a loose sense you have preserved the cubic nature of the problem. That is, none of the individual G_m's have the same symmetry as the cube, but in a loose sense the entire collection {G_m} does. = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = Robert G. Bryan (Jerry Bryan) (304) 293-5192 Associate Director, WVNET (304) 293-5540 fax 837 Chestnut Ridge Road BRYAN@WVNVM Morgantown, WV 26505 BRYAN@WVNVM.WVNET.EDU From BRYAN@wvnvm.wvnet.edu Sat Dec 10 10:21:06 1994 Return-Path: Received: from WVNVM.WVNET.EDU by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AB11211; Sat, 10 Dec 94 10:21:06 EST Message-Id: <9412101521.AB11211@life.ai.mit.edu> Received: from WVNVM.WVNET.EDU by WVNVM.WVNET.EDU (IBM VM SMTP V2R2) with BSMTP id 5482; Sat, 10 Dec 94 10:21:08 EST Received: from WVNVM.WVNET.EDU (NJE origin BRYAN@WVNVM) by WVNVM.WVNET.EDU (LMail V1.2a/1.8a) with BSMTP id 1260; Sat, 10 Dec 1994 10:21:08 -0500 X-Acknowledge-To: Date: Sat, 10 Dec 1994 10:21:02 -0500 (EST) From: "Jerry Bryan" To: Subject: Re: Re: Models for the Cube In-Reply-To: Message of 12/10/94 at 15:19:00 from , Martin.Schoenert@math.rwth-aachen.de On 12/10/94 at 15:19:00 Martin Schoenert said: >You seem to favor the physical model. There the reflection has no >real realization, and it makes sense to distinguish between the >rotations and the reflection. That is probably an accurate assessment. However, it should be pointed out that the edges can be reflected on a physical model, even though the corners and Face-centers cannot. Mathematically, this means that generates reflections, but and do not. = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = Robert G. Bryan (Jerry Bryan) (304) 293-5192 Associate Director, WVNET (304) 293-5540 fax 837 Chestnut Ridge Road BRYAN@WVNVM Morgantown, WV 26505 BRYAN@WVNVM.WVNET.EDU From @mail.uunet.ca:mark.longridge@canrem.com Fri Dec 16 04:19:31 1994 Return-Path: <@mail.uunet.ca:mark.longridge@canrem.com> Received: from seraph.uunet.ca (uunet.ca) by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA29461; Fri, 16 Dec 94 04:19:31 EST Received: from portnoy.canrem.com ([198.133.42.17]) by mail.uunet.ca with SMTP id <87818-4>; Fri, 16 Dec 1994 04:20:19 -0500 Received: from canrem.com by portnoy.canrem.com (4.1/SMI-4.1) id AA00403; Fri, 16 Dec 94 04:16:34 EST Received: by canrem.com (PCB-UUCP 1.1f) id 1C4371; Fri, 16 Dec 94 01:51:35 -0500 To: cube-lovers@life.ai.mit.edu Reply-To: CRSO.Cube@canrem.com Sender: CRSO.Cube@canrem.com Subject: Cyclic Decomposition From: mark.longridge@canrem.com (Mark Longridge) Message-Id: <60.897.5834.0C1C4371@canrem.com> Date: Fri, 16 Dec 1994 01:32:00 -0500 Organization: CRS Online (Toronto, Ontario) I've been working on a new algorithm to find move sequences to reach certain positions on the 3x3x3 cube. The basic idea is to find a sequence such that: (S1 S2 S3... SX) ^N = Goal State where X is the number of moves in the fragment and N is the number of times the fragment is repeated. I call such a process to be "Cyclicly Decomposable". Certain states, such as the 12-flip, require quite a few moves, in fact more moves than possible to search using brute force even when using high-order computers. The best results using the Kociemba algorithm need 28 q turns or 20 q+h turns for the 12-flip. While the cyclic decomposition algorithm (henceforth the CD algorithm for short) usually requires more moves than the Kociemba algorithm it does have an mnemonic advantage. The following is the best result using the CD algorithm to date: p192 2 Flip in face (F1 B1 L1 T1 D1)^6 (30 q) p195 12 Flip (T1 B3 T1 L1 F3 R3)^6 (36 q) Note that both of these processes use 5 of the 6 generators. Some cube positions are extremely resistant to CD but flip and twist patterns are no problem. In particular, the 6 X order 3 pattern does not yield to CD with values of X up to 7. Naturally with N = 1 we can always find one of the optimal paths but I am more interested in cases where N > 1. One may note that with N > 1 using CD processes we are still free to use any number of q turns except a prime number, for which N must be 1, but this should not be too constraining. By relaxing the conditions somewhat we can conceive of sequences which are near-CD, that is CD with a small suffix or prefix: p169 4 Y's Rot + 2 X (F2 B2 D1 L2 R2) ^2 + T1 (11 q+h) By looking at the best sequence the Kociemba algorithm can find for a position, we can count the number of q turns and use this as a starting point for an attempt with CD... p1 6 X order 3 R2 L3 D1 F2 R3 D3 F1 B3 U1 D3 F1 L1 D2 F3 R1 L2 (20 q) Looking at p1 we can infer that possibly X=5 and N=4 may lead to finding a CD process or X=4, N=5 X=10, N=2 X=20, N=2 etc. At the very least we can discount X * N = odd number. -> Mark <- Email: mark.longridge@canrem.com From Wechsler@world.std.com Fri Dec 16 10:23:44 1994 Return-Path: Received: from europe.std.com by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA10847; Fri, 16 Dec 94 10:23:44 EST Received: from world.std.com by europe.std.com (8.6.8.1/Spike-8-1.0) id KAA03983; Fri, 16 Dec 1994 10:23:37 -0500 Received: by world.std.com (5.65c/Spike-2.0) id AA13703; Fri, 16 Dec 1994 10:23:47 -0500 Date: Fri, 16 Dec 1994 10:23:47 -0500 From: Wechsler@world.std.com (Allan C Wechsler) Message-Id: <199412161523.AA13703@world.std.com> To: CRSO.Cube@canrem.com Cc: cube-lovers@life.ai.mit.edu In-Reply-To: Mark Longridge's message of Fri, 16 Dec 1994 01:32:00 -0500 <60.897.5834.0C1C4371@canrem.com> Subject: Cyclic Decomposition In the corner group, (RFU)^5 exchanges corners fur and bur. I only mention this because of all the tools I use, it is the only one that involves a lot of repetition. It's a fossil from my earliest cube solution, c. 1980, which used _only_ repetitive processes. (RFU)^5 is only useful to me because I solve corners first. One-face-first solvers will find this incomprehensible. From ccw@eql12.caltech.edu Fri Dec 16 13:55:58 1994 Return-Path: Received: from EQL12.Caltech.Edu by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA22563; Fri, 16 Dec 94 13:55:58 EST Date: Fri, 16 Dec 94 10:54:10 PST From: ccw@eql12.caltech.edu Message-Id: <941216105410.25001944@EQL12.Caltech.Edu> Subject: A comment on Cyclic Decomposition To: cube-lovers@life.ai.mit.edu, mark.longridge@canrem.com X-St-Vmsmail-To: ST%"cube-lovers@life.ai.mit.edu" Mark Longridge proposes looking for processes that can be expressed in the form (S1 S2 S3... SX) ^N = Goal State He calls such a processes "Cyclicly Decomposable". I think that the results would be far richer if there was also allowed to be one cube rotation in the subprocess. I know of 2 examples. I will use a * after a move to represent a full cube move. I am a little rusty on this one, and I don't have a cube here to verify it, but (L' R F*) ^ 6 (12q) is (or should be, if I remember it correctly) the Pons Asinorum. We also know that this pattern takes at best 12q, so it is actually optimum. The existance of this process has always made me wonder how many different ways there are to do the Pons, especially with different face effects in the Supergroup. The other one is my favorite process. (L D L' R' F'*)^4 (16q) This twists 3 corners on one face. I suspect this one is also optimum as I have never heard of a process that twists 3 corners in less than 16q. It has one very interesting feature, L' R' F'* can be done as 1 combined two-hand motion. A casual observer may think you are only turning the cube and not see the face turns involved. This makes the process look magic, achieving a state in far fewer apparant moves then people think is possible. This process is so fast and easy to remember that it is what I use while solving. From news@nntp-server.caltech.edu Fri Dec 16 15:36:21 1994 Return-Path: Received: from piccolo.cco.caltech.edu by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA29220; Fri, 16 Dec 94 15:36:21 EST Received: from gap.cco.caltech.edu by piccolo.cco.caltech.edu with ESMTP (8.6.7/DEI:4.41) id MAA19196; Fri, 16 Dec 1994 12:36:15 -0800 Received: by gap.cco.caltech.edu (8.6.7/DEI:4.41) id MAA02485; Fri, 16 Dec 1994 12:36:07 -0800 To: mlist-cube-lovers@nntp-server.caltech.edu Path: txr From: txr@alumni.caltech.edu (Tim Rentsch) Newsgroups: mlist.cube-lovers Subject: Re: Cyclic Decomposition Date: 16 Dec 1994 20:36:05 GMT Organization: California Institute of Technology, Pasadena Lines: 23 Message-Id: <3cstnl$2dj@gap.cco.caltech.edu> References: <60.897.5834.0C1C4371@canrem.com> Nntp-Posting-Host: alumni.caltech.edu X-Newsreader: NN version 6.5.0 #4 (NOV) mark.longridge@canrem.com (Mark Longridge) writes: > Certain states, such as the 12-flip, require quite a few moves, in >fact more moves than possible to search using brute force even when >using high-order computers. The best results using the Kociemba >algorithm need 28 q turns or 20 q+h turns for the 12-flip. I found Mark's post generally interesting and thought provoking. Without detracting from his ideas I would like to comment on the paragraph above. If a certain state (such as the 12 flip) is known to be reachable in no more than 20 moves, then isn't that state within reach of a brute force search? Start one brute force at the initial state, one at the final state, expand the position trees one move at a time until the trees touch. A state 20 moves from start will require a tree (well, two trees) 10 moves deep, which is about 10 billion states. That seems achievable in a reasonable time on fast computers of today. Doesn't it? regards, Tim Rentsch From mreid@ptc.com Fri Dec 16 17:24:16 1994 Return-Path: Received: from ptc.com (poster.ptc.com) by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA07150; Fri, 16 Dec 94 17:24:16 EST Received: from ducie.ptc.com by ptc.com (5.0/SMI-SVR4-NN) id AA08915; Fri, 16 Dec 94 17:22:51 EST Received: by ducie.ptc.com (1.38.193.4/sendmail.28-May-87) id AA27627; Fri, 16 Dec 1994 17:33:48 -0500 Date: Fri, 16 Dec 1994 17:33:48 -0500 From: mreid@ptc.com (michael reid) Message-Id: <9412162233.AA27627@ducie.ptc.com> To: cube-lovers%life.ai.mit.edu@ptc.com Subject: Re: Cyclic Decomposition Content-Length: 2380 tim writes > If a certain state (such as the 12 flip) is known to be reachable > in no more than 20 moves, then isn't that state within reach of > a brute force search? Start one brute force at the initial state, > one at the final state, expand the position trees one move at a time > until the trees touch. A state 20 moves from start will require a > tree (well, two trees) 10 moves deep, which is about 10 billion states. unfortunately, this estimate is too optimistic. the number of positions within 10 face turns of start is more like 2.6 x 10^11. [ keep in mind that while "billion" means 10^9 in the u.s., it may mean 10^12 elsewhere. ] > That seems achievable in a reasonable time on fast computers of today. > Doesn't it? i don't know, but it would be nice if it were possible. i recall that dik winter was doing some work on this front, although i think he was working on "superfliptwist". also, he was using kociemba's algorithm (first stage only). my impression was that this would take too long. (any results here, dik?) however, there's a method similar to the one tim mentions that hasn't received much attention here. i don't have all the details handy, but here's a sketch: the idea is to start with a list of permutations L and to generate (on the fly!) all products p1 p2 (with p1, p2 in the list L) in (lexicographically) increasing order. this means that while the list itself is stored in memory, the list of products (denoted L L) need not be. also, the technique for doing this (which i don't remember offhand) is easily adapted to generate all products q p1 p2 where q is a fixed permutation and p1 p2 are in the list L (q L L), again in (lexicographically) increasing order, and again, on the fly. now let L be the list of all configurations within 5 face turns of start, and let q be "superflip" or "superfliptwist". now simultaneously generate the products L L and q L L in increasing order, and look for common configurations. a common configuration gives p1 p2 = q p3 p4 ==> q = p1 p2 p4^-1 p3^-1 which gives a manuever of (at most) 20 face turns for q. of course, this technique can be used for quarter turns as well. i don't know much about the practicality of implementing this algorithm, but i'd be happy to hear from anyone who's done it, or even thought about it. mike From ccw@eql12.caltech.edu Fri Dec 16 20:47:12 1994 Return-Path: Received: from EQL12.Caltech.Edu by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA18801; Fri, 16 Dec 94 20:47:12 EST Date: Fri, 16 Dec 94 17:47:01 PST From: ccw@eql12.caltech.edu (Chris Worrell) Message-Id: <941216174701.25001b45@EQL12.Caltech.Edu> Subject: correction on my previous message. To: cube-lovers@life.ai.mit.edu My memory is indeed faulty. I was incorrct about the repeated process which yields the Pons Asinorum. The process I was actually thinking of does not need a cube rotation to make it have a repeated structure. (L' R U' D)^3 There is however an interpretation of the standard Process for the Poms, which can be decomposed into a repeated process by a cube rotation. Denote by "A", turning by 120 degrees around any diagonal, it doesn't matter which one, nor in which direction. (L^2 R^2 A)^3 yields the Pons. From news@nntp-server.caltech.edu Fri Dec 16 23:24:15 1994 Return-Path: Received: from piccolo.cco.caltech.edu by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA01947; Fri, 16 Dec 94 23:24:15 EST Received: from gap.cco.caltech.edu by piccolo.cco.caltech.edu with ESMTP (8.6.7/DEI:4.41) id UAA19585; Fri, 16 Dec 1994 20:24:06 -0800 Received: by gap.cco.caltech.edu (8.6.7/DEI:4.41) id RAA16788; Fri, 16 Dec 1994 17:06:30 -0800 To: mlist-cube-lovers@nntp-server.caltech.edu Path: txr From: txr@alumni.caltech.edu (Tim Rentsch) Newsgroups: mlist.cube-lovers Subject: Re: Cyclic Decomposition Date: 17 Dec 1994 01:06:24 GMT Organization: California Institute of Technology, Pasadena Lines: 29 Message-Id: <3ctdig$gci@gap.cco.caltech.edu> References: <9412162233.AA27627@ducie.ptc.com> Nntp-Posting-Host: alumni.caltech.edu X-Newsreader: NN version 6.5.0 #4 (NOV) mreid@ptc.com (michael reid) writes: >unfortunately, this estimate is too optimistic. the number of positions >within 10 face turns of start is more like 2.6 x 10^11. An upper bound for number of positions reachable after 10 turns is 18 * 12**9 which is 92,876,046,336. Admittedly this number is closer to 2.6e11 than 1e10, but the number is an upper bound. It seems to me I remember reading that the limiting branching factor (for q+h turns) is about 9.5 and is reached rather quickly. The value of 18 * 12 * 12 * 12 * 9.5**6 is 22,864,298,166.0 (according to 'bc'), which should be within reach of brute force algorithms. Unfortunately this approach requires several hundred gigabytes of disk space but that could be spread out over lots of physical machines (parallelizing could also result in speeding up the computation). Anyone know where we could find 1000 machines with a few hundred megabytes free each? Well, maybe not just yet. But soon. regards, Tim Rentsch From BRYAN@wvnvm.wvnet.edu Sat Dec 17 11:10:56 1994 Return-Path: Received: from WVNVM.WVNET.EDU by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA17733; Sat, 17 Dec 94 11:10:56 EST Message-Id: <9412171610.AA17733@life.ai.mit.edu> Received: from WVNVM.WVNET.EDU by WVNVM.WVNET.EDU (IBM VM SMTP V2R2) with BSMTP id 5988; Sat, 17 Dec 94 11:10:53 EST Received: from WVNVM.WVNET.EDU (NJE origin BRYAN@WVNVM) by WVNVM.WVNET.EDU (LMail V1.2a/1.8a) with BSMTP id 3919; Sat, 17 Dec 1994 11:10:54 -0500 X-Acknowledge-To: Date: Sat, 17 Dec 1994 11:10:52 EST From: "Jerry Bryan" To: "Cube Lovers List" Subject: How Big is Big? Some of the notes in the last day or two about whether or not ten levels deep is too large to search reminded me of a note I have been meaning to send for a long time. Just how big is 4.3*10^19, and can we ever hope to search it all? First of all, 4.3*10^19 is really about 10^18. That is, we could safely confine ourselves to searching M-conjugate classes, and there are about 0.9*10^18 classes, which we might as well call about 10^18. But how big is that? Suppose were trying to buy enough disk space. I claim that you could store each position in a byte with clever indexing. Actually, you could store each position in 5 bits, or 5/8 of a byte, but leave it as a byte per position. Let's say that you can purchase a gigabyte for about 1,000 U.S. Dollars (10^12 bytes for about 10^3 USD). (We are buying good quality used disks for mainframes for about 1,000 USD per gigabyte; new prices are closer to 4,000 or 5,000 USD per gigabyte. Both SCSI and IDE disks for the desktop, PC or UNIX, are just now down to around 500 USD per gigabyte, and I have seen firesale type prices closer to 300 USD per gigabyte). At 10^3 USD per 10^12 bytes, the cost would be 10^9 USD per 10^18 bytes. Well, 10^9 USD is a lot of money, but it is a lot less than the cost of going to the moon, or the cost of an aircraft carrier. In fact, Bill Gates could afford it if he so chose. There are other ways to think about the problem. The size of chess is about 10^75 states, and Go is about 10^120 states. The standard 3x3x3 Rubik's cube is vastly smaller than either of these. In fact, Go (and maybe chess, I can't remember for sure) is usually described as being bigger than the universe. A handy number in these types of comparisons and in determining "how big is the universe" is Avogadro's number, which is about 6*10^23. Avogadro's number is the number of molecules (or atoms, for substances which occur atomically) in the gram molecular weight of a substance. For example, molecular hydrogen has a molecular weight of 2, so 2 grams of hydrogen contain 6*10^23 molecules. Iron is atomic with an atomic weight of 56, so 56 grams of iron contain about 6*10^23 atoms. If you had 56 grams of iron, and if you could store magnetically each cube position in no more than 6*10^5 iron atoms, then you could store the whole Rubik's cube. By comparison to the size of the universe, the mass of the sun is about 10^30 grams, consisting mostly of atomic hydrogen, so there are about (10^30)*(10^23)=10*53 hydrogen atoms in the sun. I can't remember for sure, but I think there are about 10^11 stars in the Milky Way. If the sun is typical star, that would leave about 10^64 hydrogen atoms in the Milky Way. I don't know how many galaxies there are, but we are clearly getting close to the size of Chess at 10^75 being about the same as the size of the universe, and of Go at 10^120 being much larger than the size of the universe. Rubik's cube is small potatoes. A couple of more items: the human genome is being mapped. I cannot remember the exact size of the problem, but I do remember when I read about it that it was a larger problem than Rubik's cube. Finally, the Chronicle of Higher Education had an article in the last few weeks about particle physicists and the Internet. Traditionally, these people send hundreds or thousands of magnetic tapes to each other via standard mail (snail mail to E-mail folks -- but mailing magnetic tapes can yield tremendous data transfer rates if you actually calculate bytes per second). According to the article, the physicists are already sending gigabytes over the Internet. They are planning soon to start sending petabytes (10^15) over the Internet. 10^15 is getting interesting close to the size of Rubik's cube (never mind that I thought that the proper term for 10^15 bytes was terabytes.) = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = Robert G. Bryan (Jerry Bryan) (304) 293-5192 Associate Director, WVNET (304) 293-5540 fax 837 Chestnut Ridge Road BRYAN@WVNVM Morgantown, WV 26505 BRYAN@WVNVM.WVNET.EDU From mreid@ptc.com Sat Dec 17 14:53:48 1994 Return-Path: Received: from ptc.com (poster.ptc.com) by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AB28037; Sat, 17 Dec 94 14:53:48 EST Received: from ducie.ptc.com by ptc.com (5.0/SMI-SVR4-NN) id AA09900; Sat, 17 Dec 94 14:52:32 EST Received: by ducie.ptc.com (1.38.193.4/sendmail.28-May-87) id AA27879; Sat, 17 Dec 1994 15:03:32 -0500 Date: Sat, 17 Dec 1994 15:03:32 -0500 From: mreid@ptc.com (michael reid) Message-Id: <9412172003.AA27879@ducie.ptc.com> To: cube-lovers%life.ai.mit.edu@ptc.com Subject: planning in permutation groups Content-Length: 866 here is some more info on the algorithm i briefly described yesterday. the paper i have is "planning and learning in permutation groups", by fiat, moses, shamir, shimshoni and tardos. it appeared in the 30th annual symposium on foundations of computer science, pp 274-9. the paper mentions that they have calculated all identities of length 16 (they count face turns). this means that the algorithm was successfully implemented for the list L of all configurations within 4 face turns of start! also, alan gives a much more detailed description of this algorithm in the archives. see his message of may 27, 1987 "shamir's talk really was about how to solve the cube!" (cube-mail-6) i encourage people to look up the paper and/or alan's message. this is an exciting development, and the lack of attention this idea has received is a shame. regards, mike From BRYAN@wvnvm.wvnet.edu Sat Dec 17 23:44:44 1994 Return-Path: Received: from WVNVM.WVNET.EDU by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA17750; Sat, 17 Dec 94 23:44:44 EST Message-Id: <9412180444.AA17750@life.ai.mit.edu> Received: from WVNVM.WVNET.EDU by WVNVM.WVNET.EDU (IBM VM SMTP V2R2) with BSMTP id 7248; Sat, 17 Dec 94 23:44:42 EST Received: from WVNVM.WVNET.EDU (NJE origin BRYAN@WVNVM) by WVNVM.WVNET.EDU (LMail V1.2a/1.8a) with BSMTP id 9464; Sat, 17 Dec 1994 23:44:42 -0500 X-Acknowledge-To: Date: Sat, 17 Dec 1994 23:44:36 EST From: "Jerry Bryan" To: "Cube Lovers List" Subject: Re: How Big is Big? In-Reply-To: Message of 12/17/94 at 12:55:35 from dlitwin@geoworks.com On 12/17/94 at 12:55:35 dlitwin@geoworks.com said: >"Jerry Bryan" writes: >> I claim that you could store each position in a byte with clever >> indexing. Actually, you could store each position in 5 bits, or 5/8 of a >> byte... > Could you explain what you mean by this? You can't mean each >possible cube position because you only get 256 from a byte. Are you >talking about each type of operation you can perform on a cube? I'd buy >that, but I'd think you could store that in 4 bits (12 possible moves). >I'm clearly missing something here. I have talked about this before, but let's have a go at it again. Previously, I have talked about it in terms of corners only or edges only. This time, let's talk about it in terms of whole cubes. In terminology we have used recently, we will talk about representing G[C,E]=. That is, we will only represent corners and edges. There is no need for the purposes of this paper to include Face centers because |G[C,E]| = |G[C,E,F]|. For each cube position, we only need to store the depth, assuming we have some way to index to the proper cell in a data structure containing the depth for each cube position. As long as the depth does not exceed 31, then 5 bits will suffice for each cell. Start with G[C] and G[E] separately (corners only, and edges only). Partition G[C] into equivalence classes of the form {m'(Xc)m} for each m in M (the set of 48 rotations and reflections), for each c in C (the set of 24 rotations), and for each X in G[C]. Partition G[E] into equivalence classes of the form {m'(Yc)m} for each m in M, for each c in C, and for each Y in G[E]. These tasks have already been accomplished via computer search. For each {m'(Xc)m} choose a representative element V, and for each {m'(Yc)m} choose a representative element W. It is not strictly necessary, but it will prove convenient if each representative element is even, and such a choice is always possible. Denote the sets of representative elements as G*[C] and G*[E]. These sets have already been created via computer search. We have |G*[C]|=77802 and |G*[E]|=851625008. The sets G*[Cl and G*[E] will be used as indices, and will have to be stored. But storing them is between 10^12 and 10^13 bytes, which is a drop in the bucket compared to storing 10^18 depths. We can think of a cube in G[C,E] as XY with X in G[C] and Y in G[E]. That is, X is the corners and Y is the edges. Both X and Y are even, or both X and Y are odd, and the choice of odd or even can be thought of as an index which doesn't have to be stored. V=Repr{m'(Xc)m} can be thought of as an index for XY. V has to be stored, but it only has to be stored once for the whole data structure, not once very every position XY for which V=Repr{m'(Xc)m}. Similarly, W=Repr{m'(Yc)m} can be thought of as an index for XY, and W only has to be stored once for the entire data structure. Given V, we can write X=n'(Vd)n for some fixed n in M and for some fixed d in C. Notice that since V is even, the parity of d is the same as the parity of X, and hence there are 12 rather than 24 choices for d. Notice also that while both n and d will always exist, neither is necessarily unique, depending on how "symmetrical" is V. Hence, a selection procedure is necessary to assure that both n and d are unique. d can be thought of as an index for XY, and d does not need to be stored. As for n being an index, see two paragraphs below. Given W, we can write Y=o'(We)o for some fixed o in M and for some fixed e in C. Notice that since W is even, the parity of e is the same as the parity of Y, and hence there are 12 rather than 24 choices for e. Notice also that while both o and e will always exist, neither is necessarily unique, depending on how "symmetrical" is W. Hence, a selection procedure is necessary to assure that both o and e are unique. e can be thought of as an index for XY, and e does not need to be stored. As for o being an index, see the next paragraph. We could think of n and o as both being indices for XY, with both of them having 48 different values. The indices would not have to be stored. However, we can write XY as (n'(Vd)n)(o'(We)o). Any M-conjugate of XY has the same length as XY. If we conjugate by nn' we have n(n'(Vd)n)(o'(We)o)n'=n(n'(Vd)n)n')(n(o'(We)o)n')=(Vd)(p'(We)p), where p=on', p'=no', and p is in M. Hence, there is only one index into M with 48 different values, not two. Putting this all together, we need a table with 2*77802*851625008*12*12*48 cells, and each cell could be 5 bits. The total number of cells is about .916*10^18. The actual number of M-conjugate classes is about .901*10^18. (I am using a slightly unusual decimal point placement in deference to the total size of the table being "about 10^18".) The reason that the table size is a bit larger than the number of M-conjugate classes is that the table will contain some empty cells due to the non-uniqueness of some of the indexing by C and M. The number of cells that will be non-empty *will* in fact be exactly the same as the number of M-conjugate classes. I have talked about indices that would have to be stored, and indices that would not have to be stored. As an example of indices that would have to be stored, consider a table of names and ages. E.g., Name Age Doe, John 25 Evans, Bill 42 Jones, Jane 33 Smith, Sarah 21 You can think of the names as indices into the ages, and the names do have to be stored. On the other hand, think of storing N floating point numbers in an array X, with I as an index for I in 1..N. You would write this in a program as something like X[I]. The index I would have to be stored once, I suppose, but it would not have to be stored with each X. Similarly, in the proposed structure for storing all of God's Algorithm, the indices V and W would have to be stored, but the parity index 1..2 would not have to be stored, the rotation index 1..12 for V would not have to be stored, the rotation index 1..12 for W would not have to be stored, and the M conjugation index 1..48 for V or W (but not both) would not have to be stored. But even though the indices V and W would have to be stored, they would only have to be stored once for the whole program, not for each cube position. = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = Robert G. Bryan (Jerry Bryan) (304) 293-5192 Associate Director, WVNET (304) 293-5540 fax 837 Chestnut Ridge Road BRYAN@WVNVM Morgantown, WV 26505 BRYAN@WVNVM.WVNET.EDU From BRYAN@wvnvm.wvnet.edu Sun Dec 18 10:23:35 1994 Return-Path: Received: from WVNVM.WVNET.EDU by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA01444; Sun, 18 Dec 94 10:23:35 EST Message-Id: <9412181523.AA01444@life.ai.mit.edu> Received: from WVNVM.WVNET.EDU by WVNVM.WVNET.EDU (IBM VM SMTP V2R2) with BSMTP id 8075; Sun, 18 Dec 94 10:23:33 EST Received: from WVNVM.WVNET.EDU (NJE origin BRYAN@WVNVM) by WVNVM.WVNET.EDU (LMail V1.2a/1.8a) with BSMTP id 2308; Sun, 18 Dec 1994 10:23:33 -0500 X-Acknowledge-To: Date: Sun, 18 Dec 1994 10:23:32 EST From: "Jerry Bryan" To: "Cube Lovers List" Subject: Re: How Big is Big? In-Reply-To: Message of 12/17/94 at 22:46:08 from txr@alumni.caltech.edu On 12/17/94 at 22:46:08 txr@alumni.caltech.edu said: >In mlist.cube-lovers you write: >>For each cube position, we only need to store the depth, assuming >>we have some way to index to the proper cell in a data structure >>containing the depth for each cube position. As long as the depth >>does not exceed 31, then 5 bits will suffice for each cell. >I think depth modulo 3 is enough, since depth of adjacent positions >will differ by at most one -- just move in the direction of depth >getting less. So we could get by with 2 bits per cell. >regards, >Tim Rentsch You are certainly correct. And as Dan Hoey pointed out to me via private E-mail once upon a time, for Q turns you can get it down to only one bit by storing (depth modulo 4)/2 because you can infer the state of the low order bit from the parity of cube position. (Parity of the cube position equals the parity of the depth for Q turns, but not for Q+H turns.) But I tend to think that certain kinds of interesting analyses of a data base for the entire God's Algorithm would be greatly assisted by storing the entire depth. = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = Robert G. Bryan (Jerry Bryan) (304) 293-5192 Associate Director, WVNET (304) 293-5540 fax 837 Chestnut Ridge Road BRYAN@WVNVM Morgantown, WV 26505 BRYAN@WVNVM.WVNET.EDU From mouse@collatz.mcrcim.mcgill.edu Sun Dec 18 16:02:19 1994 Return-Path: Received: from Collatz.McRCIM.McGill.EDU by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA14014; Sun, 18 Dec 94 16:02:19 EST Received: (root@localhost) by 13839 on Collatz.McRCIM.McGill.EDU (8.6.8.1 Mouse 1.0) id PAA13839 for cube-lovers@ai.mit.edu; Sun, 18 Dec 1994 15:56:10 -0500 Date: Sun, 18 Dec 1994 15:56:10 -0500 From: der Mouse Message-Id: <199412182056.PAA13839@Collatz.McRCIM.McGill.EDU> To: cube-lovers@ai.mit.edu Subject: Re: How Big is Big? > [Physicists] are planning soon to start sending petabytes (10^15) > over the Internet. 10^15 is getting interesting close to the size of > Rubik's cube (never mind that I thought that the proper term for > 10^15 bytes was terabytes.) I thought it was kilo 10^3 mega 10^6 giga 10^9 tera 10^12 peta 10^15 exa 10^18 except, of course, that as applied to quantities that tend to come in powers of two, like bytes, they normally refer to 2^10, 2^20, 2^30, 2^40, 2^50, and 2^60 instead. (This is a common problem when buying disks: manufacturers like to quote capacities in terms of powers of ten, because it makes their disks seem larger than they really are. A "2.1G" disk, for example, typically has a capacity of about 2.1e9 bytes...which is really only about 1.956Gb. The error can be roughly estimated as 2.5% per power of 10^3: 2.5% for K, 5% for M, 7.5% for G, etc. Semiconductor memory manufacturers generally get this right, probably because doing other than powers of two would be hard for them.) It also means that a certain well-known manufacturer of data drives for 8mm videotape is being extremely arrogant with their choice of name. :-) As for the 10^18 bytes of storage estimated (probably only about half that, if we consider that we really need only 5*.9e18 bits, less if we resort to some of the clever coding tricks recently mentioned)...that's about a gig of storage each across a million machines. The net's not quite to the point where it can be done distributed. Yet. :-) Incidentally, someone mentioned that you need only store two bits, or even only one if you don't use H turns, per position, because you don't need to know more than how to get closer to Start...and then said that it would be nice to have the full depth available nevertheless. If you have this enormous database of .9e18 positions available in the compact form, all that's needed to get the full depth for a position is to take the short walk through the tree back to Start. Also note that the Cube database storage size requires the highest prefix we have. Time to get SI to think up some more, I guess :-) der Mouse mouse@collatz.mcrcim.mcgill.edu From dik@cwi.nl Sun Dec 18 16:43:21 1994 Return-Path: Received: from charon.cwi.nl by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA15510; Sun, 18 Dec 94 16:43:21 EST Received: from boring.cwi.nl by charon.cwi.nl with SMTP id ; Sun, 18 Dec 1994 22:43:19 +0100 Received: by boring.cwi.nl id ; Sun, 18 Dec 1994 22:43:19 +0100 Date: Sun, 18 Dec 1994 22:43:19 +0100 From: Dik.Winter@cwi.nl Message-Id: <9412182143.AA04820=dik@boring.cwi.nl> To: cube-lovers@ai.mit.edu Subject: Re: How Big is Big? > Also note that the Cube database storage size requires the highest > prefix we have. Time to get SI to think up some more, I guess :-) They did: 10^-24 y yocto 10^-21 z zepto 10^+21 Z zetta 10^+24 Y yotta so now you can talk about yotta bytes. dik From BRYAN@wvnvm.wvnet.edu Sun Dec 18 17:32:44 1994 Return-Path: Received: from WVNVM.WVNET.EDU by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA17736; Sun, 18 Dec 94 17:32:44 EST Message-Id: <9412182232.AA17736@life.ai.mit.edu> Received: from WVNVM.WVNET.EDU by WVNVM.WVNET.EDU (IBM VM SMTP V2R2) with BSMTP id 8903; Sun, 18 Dec 94 17:32:41 EST Received: from WVNVM.WVNET.EDU (NJE origin BRYAN@WVNVM) by WVNVM.WVNET.EDU (LMail V1.2a/1.8a) with BSMTP id 5951; Sun, 18 Dec 1994 17:32:41 -0500 X-Acknowledge-To: Date: Sun, 18 Dec 1994 17:32:40 EST From: "Jerry Bryan" To: "Cube Lovers List" Subject: Re: How Big is Big? In-Reply-To: Message of 12/18/94 at 15:56:10 from , mouse@collatz.mcrcim.mcgill.edu On 12/18/94 at 15:56:10 der Mouse said: >> [Physicists] are planning soon to start sending petabytes (10^15) >> over the Internet. 10^15 is getting interesting close to the size of >> Rubik's cube (never mind that I thought that the proper term for >> 10^15 bytes was terabytes.) >I thought it was > kilo 10^3 > mega 10^6 > giga 10^9 > tera 10^12 > peta 10^15 > exa 10^18 You are correct, of course. In retrospect, the aspect of the article in the Chronicle that waylaid me (and which I still find puzzling) is the absence of any mention of "tera". It is a giant jump from "giga" to "peta", skipping "tera" on the way. But "giga" and "peta" were juxtaposed in the article. I have known how big "tera" is for years -- can't believe I screwed it up. It makes me wonder if the article had it right. It is reasonable to jump from gigabytes to petabytes in one fell swoop? = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = Robert G. Bryan (Jerry Bryan) (304) 293-5192 Associate Director, WVNET (304) 293-5540 fax 837 Chestnut Ridge Road BRYAN@WVNVM Morgantown, WV 26505 BRYAN@WVNVM.WVNET.EDU From mouse@collatz.mcrcim.mcgill.edu Mon Dec 19 03:55:27 1994 Return-Path: Received: from Collatz.McRCIM.McGill.EDU by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA07255; Mon, 19 Dec 94 03:55:27 EST Received: (root@localhost) by 15068 on Collatz.McRCIM.McGill.EDU (8.6.8.1 Mouse 1.0) id DAA15068 for cube-lovers@ai.mit.edu; Mon, 19 Dec 1994 03:49:19 -0500 Date: Mon, 19 Dec 1994 03:49:19 -0500 From: der Mouse Message-Id: <199412190849.DAA15068@Collatz.McRCIM.McGill.EDU> To: cube-lovers@ai.mit.edu Subject: Re: How Big is Big? > In retrospect, the aspect of the article in the Chronicle that > waylaid me (and which I still find puzzling) is the absence of any > mention of "tera". It is a giant jump from "giga" to "peta", > skipping "tera" on the way. But "giga" and "peta" were juxtaposed in > the article. [...] It makes me wonder if the article had it right. > It is reasonable to jump from gigabytes to petabytes in one fell > swoop? IMO it is not. Without seeing it, I can't be sure, but it seems likely that it's Just Another Dumb Reporter. Perhaps someone took notes and wrote down 10^15 instead of 10^12, and then looked up the name for 10^15 and didn't notice the basic inconsistency of jumping from Gb to Pb without stopping at Tb. Hmmm, this is drifting off-topic for cube-lovers.... der Mouse mouse@collatz.mcrcim.mcgill.edu From BRYAN@wvnvm.wvnet.edu Mon Dec 19 08:48:32 1994 Return-Path: Received: from WVNVM.WVNET.EDU by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA14147; Mon, 19 Dec 94 08:48:32 EST Message-Id: <9412191348.AA14147@life.ai.mit.edu> Received: from WVNVM.WVNET.EDU by WVNVM.WVNET.EDU (IBM VM SMTP V2R2) with BSMTP id 0349; Mon, 19 Dec 94 08:48:28 EST Received: from WVNVM.WVNET.EDU (NJE origin BRYAN@WVNVM) by WVNVM.WVNET.EDU (LMail V1.2a/1.8a) with BSMTP id 2224; Mon, 19 Dec 1994 08:48:29 -0500 X-Acknowledge-To: Date: Mon, 19 Dec 1994 08:48:28 EST From: "Jerry Bryan" To: "Cube Lovers List" Subject: Re: How Big is Big? In-Reply-To: Message of 12/17/94 at 11:10:52 from BRYAN@wvnvm.wvnet.edu One more correction to this giga, tera, peta, nonsense. Since 10^9 bytes of disk space cost about 10^3 USD, then 10^18 bytes would cost about 10^12 USD. This is more than Bill Gates could afford, more than going to the moon, more than an aircraft carrier, and indeed is of the same order of magnitude as the entire United States federal budget. Disk prices need to come down several orders of magnitude before we can think about storing God's Algorithm. = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = Robert G. Bryan (Jerry Bryan) (304) 293-5192 Associate Director, WVNET (304) 293-5540 fax 837 Chestnut Ridge Road BRYAN@WVNVM Morgantown, WV 26505 BRYAN@WVNVM.WVNET.EDU From Wechsler@world.std.com Mon Dec 19 09:59:54 1994 Return-Path: Received: from europe.std.com by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA17311; Mon, 19 Dec 94 09:59:54 EST Received: from world.std.com by europe.std.com (8.6.8.1/Spike-8-1.0) id JAA02475; Mon, 19 Dec 1994 09:59:52 -0500 Received: by world.std.com (5.65c/Spike-2.0) id AA05068; Mon, 19 Dec 1994 10:00:04 -0500 Date: Mon, 19 Dec 1994 10:00:04 -0500 From: Wechsler@world.std.com (Allan C Wechsler) Message-Id: <199412191500.AA05068@world.std.com> To: mouse@collatz.mcrcim.mcgill.edu Cc: cube-lovers@ai.mit.edu In-Reply-To: der Mouse's message of Sun, 18 Dec 1994 15:56:10 -0500 <199412182056.PAA13839@Collatz.McRCIM.McGill.EDU> Subject: How Big is Big? Date: Sun, 18 Dec 1994 15:56:10 -0500 From: der Mouse > [Physicists] are planning soon to start sending petabytes (10^15) > over the Internet. 10^15 is getting interesting close to the size of > Rubik's cube (never mind that I thought that the proper term for > 10^15 bytes was terabytes.) I thought it was kilo 10^3 mega 10^6 giga 10^9 tera 10^12 peta 10^15 exa 10^18 [...] Also note that the Cube database storage size requires the highest prefix we have. Time to get SI to think up some more, I guess :-) (Warning to Cube-Lovers: this is off the topic, but it's a digression I can never resist. Alan is going to come over to my house and soap my windows for this, I just know it.) They _have_ thought up some more -- this was in Science News about 18 months ago. But the ones they thought up are absolutely awful, and I want to take this opportunity to advertise my own suggestions. First note the following relationships, which I believe are entirely the result of coincidence: te(t)ra 1000^4 pe(n)ta 1000^5 (h)exa 1000^6 In each case, the prefix for 1000^n looks like the neo-greek prefix for n, with the second-to-last consonant deleted. I merely propose that we continue this scheme: he(p)ta 1000^7 o(c)to 1000^8 (en)nea 1000^9 I admit to a fudge with n=9, but I like neabytes better than eneabytes, and the prefix E was already taken by n=6. I wanted to keep up the unique sequence of prefixes: K, M, G, T, P, E, H, O, N. For those who care, megameters are good for measuring small planets, gigameters for big planets and stars, and terameters for solar systems. A petameter is about a tenth of a light year, and so it's good for measuring near interstellar distances; exameters are good for the 100-ly range, galaxies should be measured with hetameters, and intergalactic distances with otometers. Current theory says the universe is considerably smaller than one neameter. From @mitvma.mit.edu:will4086@UDCVAX.BITNET Wed Dec 21 18:48:20 1994 Return-Path: <@mitvma.mit.edu:will4086@UDCVAX.BITNET> Received: from mitvma.mit.edu by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA05936; Wed, 21 Dec 94 18:48:20 EST Received: from MITVMA.MIT.EDU by mitvma.mit.edu (IBM VM SMTP V2R2) with BSMTP id 2190; Wed, 21 Dec 94 18:48:14 EST Received: from UDCVAX.BITNET (NJE origin MXMAILER@UDCVAX) by MITVMA.MIT.EDU (LMail V1.2a/1.8a) with BSMTP id 3314; Wed, 21 Dec 1994 18:48:15 -0500 Received: by UDCVAX.BITNET (MX V3.3 VAX) id 3192; Wed, 21 Dec 1994 18:50:19 EST Sender: will4086%UDCVAX.BITNET@mitvma.mit.edu Date: Wed, 21 Dec 1994 18:50:19 EST From: will4086%UDCVAX.BITNET@mitvma.mit.edu To: CUBE-LOVERS@life.ai.mit.edu Message-Id: <0098948C.2AA66560.3192@UDCVAX.BITNET> Subject: MAILING LIST I WOULD LIKE TO BE PLACED ON THE MAILING LIST FOR THE SUBJECTS YOUR GROUPS DISCUSS.THIS IS THE FIRST E-MAIL MESSAGE THAT I HAVE SENT,SO PLEASE DON'T LAUGH AT THIS PARAGRAPH. From dik@cwi.nl Wed Dec 21 20:16:25 1994 Return-Path: Received: from charon.cwi.nl by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA09542; Wed, 21 Dec 94 20:16:25 EST Received: from boring.cwi.nl by charon.cwi.nl with SMTP id ; Thu, 22 Dec 1994 02:16:04 +0100 Received: by boring.cwi.nl id ; Thu, 22 Dec 1994 02:16:03 +0100 Date: Thu, 22 Dec 1994 02:16:03 +0100 From: Dik.Winter@cwi.nl Message-Id: <9412220116.AA03233=dik@boring.cwi.nl> To: cube-lovers@life.ai.mit.edu Subject: CFF 35 CFF #35 came out, the editors expected it in December and it came out in December! Good for them. Summary of contents. Vic Stok: Paving stones. A new twist to polyominos. Squares are linked in a brick-wall fashion. Lee Sallows: Alphamagic squares. About the construction of magic squares where, if you replace each entry with the value of the word length, the result is magic again. The most surprising for me was one square that was alphamagic in both Welsh and Norwegian. Torsten Sillke and Bernhard Wiezorke: Stacking Identical Polyspheres. Part 1: Tetrahedra. Discusses many possible and impossible tetrahedra that can be packed by polyspheres. Jan de Ruiter: Braiding. An article about a contest problem issued on the Dutch 1992 Cube Day. It involves (amongst others) the number of ways a braid can be made from a varying number of bundles of hair. Joop van der Vaart: IPP 1994 Impressions. Impressions from the 1994 International Puzzle Party in Seattle. Leo Links: Cube Day Impressions. Impressions of the 1994 Dutch Cube Day in Stavoren. Result of contest 24 (CFF 33, Cross Pattern Piling). Anneke Treep: Anti-slide... a winner! A short note about the Hikimi Wooden Puzzle Competition. Wil Strijbos from the Netherlands came second with his puzzle. Start with 15 1x2x2 square pieces and a 4x4x4 box. Pack the pieces in the box so that no piece can slide. Do the same with 14, 13, 12, 11 (actually the article has a typo here). Columns: Mark Peters: Books and Magazines (reviews) Edward Hordern: What's Up? (details some new puzzles and other news) ------ CFF (Cubism For Fun) is the newsletter published by the Nederlands Kubus Club NKC (Dutch Cubists Club). Information can be obtained from one of the editors: Rik van Grol . Membership fee is NLG 25 individual, NLG 80 institutional. (USD 1 ~ NLG 1.70). Applications for membership to the treasurer: Lucien Matthijsse Loenapad 12 3402 PE IJsselstein The Netherlands If you write, please add an international reply coupon (can be obtained at your post office). -- dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924098 home: bovenover 215, 1025 jn amsterdam, nederland; e-mail: dik@cwi.nl From jkato@tmastb.eec.toshiba.co.jp Wed Dec 21 20:43:59 1994 Received: from inet-tsb.toshiba.co.jp by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA11701; Wed, 21 Dec 94 20:43:59 EST Received: from tis2.tis.toshiba.co.jp (tis2) by inet-tsb.toshiba.co.jp (5.67+1.6W/2.8Wb) id AA22586; Thu, 22 Dec 94 10:43:45 JST Received: from tis10.tis.toshiba.co.jp (tis10) by tis2.tis.toshiba.co.jp (5.67+1.6W/6.4J.6-R05) id AA24598; Thu, 22 Dec 94 10:44:15 JST Received: from eecisa.eec.toshiba.co.jp (eecisa) by tis10.tis.toshiba.co.jp (5.67+1.6W/6.4J.6-MHS-CNTML-R1) id AA10538; Thu, 22 Dec 94 10:44:29 JST Received: from tmastb.eec.toshiba.co.jp by eecisa.eec.toshiba.co.jp (4.1/6.4J.6-R1) id AA15739; Thu, 22 Dec 94 10:35:37 JST Received: by tmastb.eec.toshiba.co.jp (4.0/6.4J.6-R1) id AA02582; Thu, 22 Dec 94 10:42:11 JST Date: Thu, 22 Dec 94 10:42:11 JST From: jkato@tmastb.eec.toshiba.co.jp (Toshi Kato) Return-Path: Message-Id: <9412220142.AA02582@tmastb.eec.toshiba.co.jp> To: cube-lovers@life.ai.mit.edu Subject: IPP #15 To: International Puzzle Collectors Dear Sirs, 15th International Puzzle collectors' Party(15th IPP) will be taken place on April 15-16,1995 in Tokyo,Japan and optional HAKONE tour on April 17. Have you received an invitation letter of 15th IPP from Nob Yoshigahara? And then, you have done to reply to Nob, haven't you? So, thanks. If you did not yet, please answer by express snail mail or fax or e-mail, as soon as possible. We are looking forward you come to Japan. Thank you, Toshi(Junk) Kato --------------------------------------JUNK: jkato@tmastb.eec.toshiba.co.jp (Notice)If you interest in Puzzle KONWAKAI(Academy of recreatinal mathe- matics,Japan), you may attend the meeting on April 22,1995 for a guest. From mmoss@panix.com Thu Dec 22 10:45:49 1994 Return-Path: Received: from panix2.panix.com by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA14655; Thu, 22 Dec 94 10:45:49 EST Received: by panix2.panix.com id AA13543 (5.67b/IDA-1.5 for cube-lovers@life.ai.mit.edu); Thu, 22 Dec 1994 10:45:48 -0500 From: Matthew Moss Message-Id: <199412221545.AA13543@panix2.panix.com> Subject: UNSUBSCRIBE To: cube-lovers@life.ai.mit.edu (Cube Mailing List) Date: Thu, 22 Dec 1994 10:45:48 -0500 (EST) X-Mailer: ELM [version 2.4 PL23] Mime-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit Content-Length: 40 Please unsubscribe me. mmoss@panix.com From magnum@cyberstore.ca Thu Dec 22 13:23:33 1994 Return-Path: Received: from yvr.cyberstore.ca by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA22499; Thu, 22 Dec 94 13:23:33 EST Received: from [198.70.153.8] (ylw-ppp-8.cyberstore.ca [198.70.153.8]) by yvr.cyberstore.ca (8.6.9/8.6.9) with SMTP id KAA23820 for ; Thu, 22 Dec 1994 10:23:24 -0800 X-Sender: ylwm0169@cyberstore.ca Message-Id: Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Date: Thu, 22 Dec 1994 10:23:58 -0800 To: cube-lovers@life.ai.mit.edu (Cube Mailing List) From: magnum@cyberstore.ca (Darryl EJ Ruff) unsubscribe Darryl EJ Ruff, Dir. Magnum Results Corp. PO Box 692, Stn A Kelowna, BC Canada V1Y 7P4 Ring: 604/769-6169 Fax: 604/769-6158 Internet: magnum@cyberstore.ca "..If We Fail To Achieve Superior Results, We Won't Accept Your Money.." From epaytl@epa.ericsson.se Thu Dec 22 16:34:29 1994 Return-Path: Received: from mailgate.ericsson.se by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA02346; Thu, 22 Dec 94 16:34:29 EST Received: from epa.epa.ericsson.se (epa.epa.ericsson.se [146.11.8.1]) by mailgate.ericsson.se (8.6.9/1.0) with SMTP id WAA05712 for ; Thu, 22 Dec 1994 22:34:26 +0100 Received: from brsw006.epa.ericsson.se.epa.ericsson.se by epa.epa.ericsson.se (4.1/SMI-4.1-EPA1.6) id AA14797; Fri, 23 Dec 94 08:34:21 DST Date: Fri, 23 Dec 94 08:34:21 DST From: epaytl@epa.ericsson.se (Y T - T/ZA) Message-Id: <9412222134.AA14797@epa.epa.ericsson.se> To: cube-lovers@life.ai.mit.edu Subject: UNSUBSCRIBE Please unsubscribe me. epaytl@epa.ericsson.se From alan@curry.epilogue.com Thu Dec 22 23:38:49 1994 Return-Path: Received: from curry.epilogue.com by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA29296; Thu, 22 Dec 94 23:38:49 EST Received: (from alan@localhost) by curry.epilogue.com (8.6.8/8.6.6) id XAA07218; Thu, 22 Dec 1994 23:41:33 -0500 Date: Thu, 22 Dec 1994 23:41:33 -0500 Message-Id: <22Dec1994.232120.Alan@LCS.MIT.EDU> From: Alan Bawden Sender: Cube-Lovers-Request@ai.mit.edu To: mmoss@panix.com, epaytl@epa.ericsson.se, magnum@cyberstore.ca Cc: Cube-Lovers@ai.mit.edu In-Reply-To: Matthew Moss's message of Thu, 22 Dec 1994 10:45:48 -0500 (EST) <199412221545.AA13543@panix2.panix.com> Subject: UNSUBSCRIBE From: Matthew Moss Date: Thu, 22 Dec 1994 10:45:48 -0500 (EST) Please unsubscribe me. mmoss@panix.com Date: Thu, 22 Dec 1994 10:23:58 -0800 From: Darryl EJ Ruff unsubscribe Darryl EJ Ruff, Dir. Magnum Results Corp. PO Box 692, Stn A Kelowna, BC Canada V1Y 7P4 Ring: 604/769-6169 Fax: 604/769-6158 Internet: magnum@cyberstore.ca "..If We Fail To Achieve Superior Results, We Won't Accept Your Money.." Date: Fri, 23 Dec 94 08:34:21 DST From: Y T - T/ZA Please unsubscribe me. epaytl@epa.ericsson.se I have removed all three of you from the Cube-Lovers mailing list. Note, please, that all three of you sent your requests to be removed to Cube-Lovers as a whole. You should have sent them to me, Cube-Lovers-Request@AI.MIT.EDU, instead of bothering the entire list. This was all clearly explained in the introductory note I sent you when you first subscribed (earlier this month for two of you). This is, in fact, a wide-spread Internet convention. If you can remember it, you can often avoid looking like an idiot in front of hundreds of people. I'm sorry to bother everybody else on Cube-Lovers by CC'ing this note to you all, but this way I can perhaps prevent more copy-cat repetitions of the same annoying mistake. REMEMBER: SEND SUBMISSIONS TO: Cube-Lovers@AI.MIT.EDU SEND ADMINISTRATIVE CORRESPONDENCE TO: Cube-Lovers-Request@AI.MIT.EDU GOT IT? From ba05133@bingsuns.cc.binghamton.edu Fri Dec 23 10:24:30 1994 Return-Path: Received: from bingsuns.cc.binghamton.edu (bingnfs1.cc.binghamton.edu) by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA19786; Fri, 23 Dec 94 10:24:30 EST Received: from podsun7 by bingsuns.cc.binghamton.edu (5.0/SMI-4.0) id AA02035; Fri, 23 Dec 1994 10:20:35 -0500 From: ba05133@bingsuns.cc.binghamton.edu Received: by podsun7 (5.0/BING1.0) id AA01392; Fri, 23 Dec 1994 10:21:46 -0500 Message-Id: <9412231521.AA01392@podsun7> Subject: "unsubscribe" To: cube-lovers@life.ai.mit.edu Date: Fri, 23 Dec 1994 10:21:44 -0500 (EST) X-Mailer: ELM [version 2.4 PL24] Mime-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit Content-Length: 25 Please unsubscribe me. From BRYAN@wvnvm.wvnet.edu Fri Dec 23 18:26:02 1994 Return-Path: Received: from WVNVM.WVNET.EDU by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA10284; Fri, 23 Dec 94 18:26:02 EST Message-Id: <9412232326.AA10284@life.ai.mit.edu> Received: from WVNVM.WVNET.EDU by WVNVM.WVNET.EDU (IBM VM SMTP V2R2) with BSMTP id 0778; Fri, 23 Dec 94 18:25:59 EST Received: from WVNVM.WVNET.EDU (NJE origin BRYAN@WVNVM) by WVNVM.WVNET.EDU (LMail V1.2a/1.8a) with BSMTP id 5031; Fri, 23 Dec 1994 18:25:58 -0500 X-Acknowledge-To: Date: Fri, 23 Dec 1994 18:25:57 EST From: "Jerry Bryan" To: "Cube Lovers List" Subject: Antipodal Processes With the help of a suggestion from Dan Hoey, I can now provide processes for the 27 antipodal positions of that are unique up to W-conjugancy. (It is the positions that are unique up to W-conjugancy, not necessarily the processes.) Without further ado, here are processes which generate each of the 27 positions. 1 R U U R R U' R U' R U' R U R' U R U R' U' R R U' R' U R U 2 R' U R' U R' U R R U' R' U' R' U' R U' R' R' U' R R U' R' U R U 3 R R U R' U R U' R' U R' R' U R R U' U' R R U R R U R R U' 4 U' R U R' U R U' R' U' R' R' U R' U' R U U R' U R' U' R' U R U' 5 R' R' U U R U R U' R U' U' R' U R R U' R R U' R' U R' U R' U' 6 U' R R U R' U R' R' U' R' U U R U' R' U R R U R R U R' U' R 7 U R' U R' U R U U R' U' R R U R' U' R' U R R U R' U R U' R 8 R' U R' U' U' R U' R U' U' R' U R' U R' R' U' R U R U R U' R U 9 U R U' R U R R U' R U' R' U R U' R' R' U U R' R' U' R U' R R 10 U' R R U R U U R' U' R' U R U' R' R' U' U' R' U' R' U' R' U R U' 11 R' U R U R' U' R U R' U' U' R' U' R R U U R' U R U R U' R' R' 12 R U U R' U U R' U R U' R' U R' U' R U' R' U' R' U R U' R R U 13 R R U R R U' R U' U' R U' R R U' R' R' U' R R U' R U' R R U 14 U' R' U' R' U' R' U R R U' R U' R U' R U' R' U R U' U' R U U R 15 R R U' R' R' U' R U U R' U U R' R' U' R' U' U' R' R' U' R U' U' R 16 U R' U R' R' U' R U' R U U R R U' R U R' U' R U' R' U' R R U' 17 U' R U' U' R' R' U' R U' R U' R U' R R U R' R' U' R' R' U' R' R' U' 18 R U U R U R U' R' U R' U R U' R R U' R' U' R U U R U' U' R' 19 R' U R' U' U' R U' R U' R' R' U U R U' R' U R U' R U R U U R' 20 U R R U' R R U' R' U' R' U U R' U R' U R U U R' U R U' R R 21 R' U R' U' R' U R U U R' U R' U R' U' R U' R' U R U R' U R R 22 U R U U R U' R U R' U' R U U R U' R U' R' R' U R R U R U 23 R' U U R U R' U R' U R U R' U' R R U' R U' U' R' U R R U R 24 R' U R' U' R R U U R' U R U' R' R' U U R' U R' U' U' R U U R 25 U R' R' U U R U R U' U' R U' R U U R' U R' U' U' R' U R R U 26 U' R' U R U' R' U U R R U R' U R' U R' U' U' R R U' R' U' R' R' 27 R U' R' U' U' R R U' R' U' R U' R U' U' R' U' R' R' U' R U' R R U' The 27 processes are in the same order as the 27 positions I posted on 11 November this year. However, I want to repost the 27 positions anyway. I found a formatting inconsistency in that posting. Generally speaking, when you unfold the cube for printing with the Back above, you can choose to print the Back face right-side-up or up-side-down, and up-side-down makes more sense to me. All my screen displays work that way, and it makes the cubies move smoothly under repeated applications of the R or L operators. However, I discovered that the print program I used for the 11 November posting printed the edge facelets of the Back face right-side- up. That wouldn't have been so bad, I suppose, but at the same time I printed the corner facelets correctly as up-side-down. So herewith I reprint the 27 antipodal positions with all the Back faces correctly up-side-down. BBL BBL BBU BBU BBU BBF LRF RRF LRR UDR FDU UBD BUU BUU DUU FUB FUR UUF FRD RFR DRU URD RFB URL FRB LFD RLB LLL FFF RRB LLL FFF RRB LLL FFU RRR LLL FFB RLU LLL FFD RLU LLL FFF UBR DDU DDB DDR DDU DDU DDU DDB DDB DDB --------------------------------------------------------------- BBU BBR BBU BBF BBU BBF DRR BRB FBD FDU RDL LUB UUB FUB UUU BUR RUL LUF RBR DFB URF URU FFF URU ULU BFD RRR LLL FFU LRR LLL FFU LRR LLL FFB RRR LLL FFL BRL LLL FFR BBF LLL FFU RRR DDU DDD DDF DDU DDU DDD DDF DDD DDB ---------------------------------------------------------------- BBR BBU BBB BBU BBU BBU LRD RLF FRF UDB DUR UFD UUF FUD DUU UUR BUU UUR FRB LFF DRR FRR DFR BRU RRL FLB URR LLL FFB RRB LLL FFB RRR LLL FFU FRB LLL FFU RLB LLL FFU LBL LLL FFB URR DDF DDB DDL DDU DDU DDB DDU DDF DDD ---------------------------------------------------------------- BBR BBR BBL BBF BBU BBU FFR URU DRF LUB FFF FFR UUU DUU DUU RBR BBB DBR ULD BRU FRU LRL URU RRR RRB RRB URU LLL FFU BRR LLL FFU BRF LLL FFU BRF LLL FFB URF LLL FFR BLF LLL FFU LLF DDL DDD DDB DDD DDU DDU DDD DDD DDU ------------------------------------------------------------------ BBR BBF BBF BBU BBU BBU URU FRF FRF FFF RDR RDR UUU FUU FUU BBB DBR BBR LRL URU RLR DRB RRB URU DRR DRB URU LLL FFU BRF LLL FFU BRL LLL FFU BRL LLL FFR BRF LLL FFU LFU LLL FFL BFU DDD DDB DDU DDD DDU DDU DDD DDL DDL -------------------------------------------------------------- BBF BBR BBR BBU BBU BBU DRL URR FRD RFU FFB RDB UUD DUU FUU RBR RBF UBL BRF DRB URB LRD BRR UBU DRB LRF URR LLL FFU BRL LLL FFU RRL LLL FFU FRB LLL FFU RFU LLL FFB UFF LLL FFR ULU DDF DDL DDB DDU DDU DDU DDL DDD DDF -------------------------------------------------------------- BBB BBU BBU BBU BBU BBU FRL RRF BRR RDF BFR UUU FUU DUU DUF UBB FBU UBD DRF RRL URU DRD RRL FLU LRL FRR FRF LLL FFU FRB LLL FFU FRB LLL FFU FRB LLL FFD RLU LLL FFB URR LLL FFD RLR DDB DDL DDB DDU DDU DDU DDR DDB DDB --------------------------------------------------------------- BBB BBB BBD BBU BBF BBU URU UFD LRF BUF RUR UBR DUF DUU DUU UBU UBR UFR RRB LRL FRR FRL FRB URF FRB LRB URU LLL FFU FRB LLL FFU LRR LLL FFU FRB LLL FFF RLR LLL FFB UBR LLL FFD RLR DDD DDL DDB DDU DDU DDU DDD DDD DDF ---------------------------------------------------------------- BBD BBF BBR BBF BBF BBF BFB UFF LFR RUL FUR UUD UUU UUU UUU RUL BUR UUD URU FBF ULU LRL UBB ULU FRB LBR FLB LLL FFB RRR LLL FFB RRR LLL FFB RRR LLL FFD RRR LLL FFB DRD LLL FFR FRB DDB DDR DDU DDD DDD DDD DDF DDR DDU ------------------------------------------------------------ = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = Robert G. Bryan (Jerry Bryan) (304) 293-5192 Associate Director, WVNET (304) 293-5540 fax 837 Chestnut Ridge Road BRYAN@WVNVM Morgantown, WV 26505 BRYAN@WVNVM.WVNET.EDU From BRYAN@wvnvm.wvnet.edu Fri Dec 23 20:55:24 1994 Return-Path: Received: from WVNVM.WVNET.EDU by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA15546; Fri, 23 Dec 94 20:55:24 EST Message-Id: <9412240155.AA15546@life.ai.mit.edu> Received: from WVNVM.WVNET.EDU by WVNVM.WVNET.EDU (IBM VM SMTP V2R2) with BSMTP id 0980; Fri, 23 Dec 94 20:55:21 EST Received: from WVNVM.WVNET.EDU (NJE origin BRYAN@WVNVM) by WVNVM.WVNET.EDU (LMail V1.2a/1.8a) with BSMTP id 5731; Fri, 23 Dec 1994 20:55:21 -0500 X-Acknowledge-To: Date: Fri, 23 Dec 1994 20:55:19 EST From: "Jerry Bryan" To: "Cube Lovers List" Subject: Antipodal Processes Here are the 16 antipodal processes for . Also, as in the case of , I am including replacement position diagrams that include a correction for the Back face so that both the corners and edges are up-side-down. Q+H turners will like these processes because of the way turns of the U face alternate with turns of the R face. I have performed a few of the processes on a real cube (as opposed to on a computer screen), and I find the alternating faces to be quite pleasant somehow or other. 1 R' U R2 U R U2 R U R U2 R' U2 R U2 R' U2 R2 U R2 U 2 U' R U' R2 U' R2 U' R U' R2 U2 R U R U' R U R U2 R2 3 U R U2 R U' R U2 R2 U2 R2 U R U R2 U2 R U' R U R2 4 R' U2 R' U R U' R2 U' R2 U' R' U R' U' R' U' R U' R' U2 5 R' U2 R2 U' R U2 R' U' R U R' U2 R' U2 R' U' R' U2 R U 6 R U R U' R U R2 U R2 U R' U' R U2 R U2 R U R' U 7 R2 U' R U2 R U2 R U' R' U' R U2 R U R2 U R' U R U2 8 U' R' U R' U R' U R2 U' R' U' R' U R' U R' U R2 U' R' 9 R U2 R' U R' U R U' R U R' U2 R' U2 R U' R U' R' U2 10 U' R' U2 R2 U2 R' U R' U2 R' U' R U R' U R U' R' U R2 11 U' R' U' R' U2 R2 U2 R2 U R2 U R2 U' R2 U2 R' U' R U2 R' 12 R2 U' R2 U2 R' U' R2 U' R U R2 U2 R2 U R U2 R U' R' U 13 R U2 R' U' R U' R' U' R2 U' R U2 R U R2 U R' U2 R U 14 U2 R' U R2 U' R' U' R2 U' R U R' U2 R' U2 R2 U R' U2 R' 15 U' R U2 R' U2 R U' R U' R U2 R' U' R U2 R2 U R U R2 16 U' R2 U2 R' U R' U2 R U' R2 U2 R' U2 R U R2 U' R2 U2 R2 BBR BBB BBL BBB BBB BBB FBU LBD RBU RUR BUB BUR UUU UUU UUU RUU RUU DUF DLU FFL FRB ULU FFL FRR DLR FFR URB LLL FFF RRR LLL FFF RRR LLL FFF RRR LLL FFU LRD LLL FFD FRU LLL FFL URU DDB DDR DDF DDD DDD DDD DDB DDR DDB ------------------------------------------------------------- BBD BBU BBR BBB BBB BBB LBR LBR RBB UUF UUB UUL UUU UUU UUU BUR BUR LUR FLL UFU FRD FLL UFD BRU BLF UFF DRU LLL FFF RRR LLL FFF RRR LLL FFF RRR LLL FFR URB LLL FFR DRF LLL FFU RRD DDB DDF DDF DDD DDD DDD DDR DDR DDB ----------------------------------------------------------- BBL BBR BBU BBB BBB BBB RBR LBU FBB BUU BUR RUR UUU UUU UUU LUB LUF FUR DLF UFU RRF ULF UFR URB DLU LFU FRD LLL FFF RRR LLL FFF RRR LLL FFF RRR LLL FFD FRU LLL FFD FRD LLL FFL BRR DDR DDR DDU DDD DDD DDD DDB DDB DDB ----------------------------------------------------------- BBF BBU BBB BBF BBD BBU FBR LFR BRR LUU UUD UFB UUU UUB DUU UUR LUF UBF ULB LFB URF FBU BLD RRB LRL FRR ULU LLL FFB RRR LLL FFU RRR LLL FFU BRF LLL FFR BRD LLL FFR FRR LLL FFF RRR DDD DDU DDD DDD DDF DDU DDR DDB DDD -------------------------------------------------------------- BBL BBB BBB BBU BBU BBU DRF FRF FFD FFR RDR RUB DUU FUU UUF DBR UBB FDU RRB RRB URU DRL FRL URU DLU LRF RRR LLL FFU BRF LLL FFU FRB LLL FFB RRR LLL FFU LLF LLL FFR ULR LLL FFU LBU DDB DDB DDB DDU DDU DDU DDU DDD DDR ----------------------------------------------------------- BBF BBU UFB LUU UUF BDR BLR DRF DRR LLL FFB RRR LLL FFU RBU DDF DDU DDL = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = Robert G. Bryan (Jerry Bryan) (304) 293-5192 Associate Director, WVNET (304) 293-5540 fax 837 Chestnut Ridge Road BRYAN@WVNVM Morgantown, WV 26505 BRYAN@WVNVM.WVNET.EDU From kotani@cc.tuat.ac.jp Mon Dec 26 05:33:46 1994 Received: from mail01.cc.tuat.ac.jp (mail01.tuat.ac.jp) by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA20405; Mon, 26 Dec 94 05:33:46 EST From: kotani@cc.tuat.ac.jp Received: by mail01.cc.tuat.ac.jp (4.1/6.4JAIN-930819) id AA00817; Mon, 26 Dec 94 13:11:23 JST Date: Mon, 26 Dec 94 13:11:23 JST Return-Path: Message-Id: <9412260411.AA00817@mail01.cc.tuat.ac.jp> To: cube-lovers@life.ai.mit.edu Cc: kotani@cc.tuat.ac.jp In-Reply-To: ba05133@bingsuns.cc.binghamton.edu's message of Fri, 23 Dec 1994 10:21:44 -0500 (EST) <9412231521.AA01392@podsun7> Subject: "unsubscribe" Please unsubscribe me. From jkato@tmastb.eec.toshiba.co.jp Mon Dec 26 22:45:54 1994 Received: from inet-tsb.toshiba.co.jp by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA21328; Mon, 26 Dec 94 22:45:54 EST Received: from tis2.tis.toshiba.co.jp (tis2) by inet-tsb.toshiba.co.jp (5.67+1.6W/2.8Wb) id AA03648; Tue, 27 Dec 94 12:45:37 JST Received: from tis10.tis.toshiba.co.jp (tis10) by tis2.tis.toshiba.co.jp (5.67+1.6W/6.4J.6-R05) id AA10356; Tue, 27 Dec 94 12:46:08 JST Received: from eecisa.eec.toshiba.co.jp (eecisa) by tis10.tis.toshiba.co.jp (5.67+1.6W/6.4J.6-MHS-CNTML-R1) id AA27988; Tue, 27 Dec 94 12:46:23 JST Received: from tmastb.eec.toshiba.co.jp by eecisa.eec.toshiba.co.jp (4.1/6.4J.6-R1) id AA14678; Tue, 27 Dec 94 12:36:57 JST Received: by tmastb.eec.toshiba.co.jp (4.0/6.4J.6-R1) id AA00285; Tue, 27 Dec 94 12:44:00 JST Date: Tue, 27 Dec 94 12:44:00 JST From: jkato@tmastb.eec.toshiba.co.jp (Toshi Kato) Return-Path: Message-Id: <9412270344.AA00285@tmastb.eec.toshiba.co.jp> To: cube-lovers@life.ai.mit.edu Subject: GreyhoundBus Puzzle This is a sliding block puzzle that I thought. +---+---+---+---+---+ |[N]|[U]|[S]|[H]|[U]| ［Problem］ +---+---+---+---+---+ Left figure is starting condition.　 |[O]|###| |###|[G]| Make a sequence,"GREYHOUNDBUS",with minimum step. +---+---+---+---+---+　　 |[B]|[Y]|[R]|[D]|[E]| Note: Vacant room is only one.　 +---+---+---+---+---+ ### are not moved. If you can get answer, please write it to me or on Cube-Lovers ML. Toshi(Junk) Kato, Japan --------------------------------------JUNK: jkato@tmastb.eec.toshiba.co.jp From BRYAN@wvnvm.wvnet.edu Tue Dec 27 16:55:19 1994 Return-Path: Received: from WVNVM.WVNET.EDU by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA00248; Tue, 27 Dec 94 16:55:19 EST Message-Id: <9412272155.AA00248@life.ai.mit.edu> Received: from WVNVM.WVNET.EDU by WVNVM.WVNET.EDU (IBM VM SMTP V2R2) with BSMTP id 1728; Tue, 27 Dec 94 11:23:07 EST Received: from WVNVM.WVNET.EDU (NJE origin BRYAN@WVNVM) by WVNVM.WVNET.EDU (LMail V1.2a/1.8a) with BSMTP id 7330; Tue, 27 Dec 1994 11:23:07 -0500 X-Acknowledge-To: Date: Tue, 27 Dec 1994 11:23:06 EST From: "Jerry Bryan" To: "Cube Lovers List" Subject: Normal Subgroups of G Recently, there was some discussion of whether the set C of twenty-four rotations is a normal subgroup of the cube group G=. It isn't, but I decided to write up some information about normal subgroups as it relates to the cube. Most of the following is from Frey and Singmaster. Any good stuff is theirs. Any crud that sneaks in is mine. If H is any subgroup of G, a right coset of H in G is a set {hX} for some fixed X in G and for all h in H. Similarly, a left coset of H in G is a set {Xh}. Right cosets may be denoted as Hx, and left cosets by xH. In general, a right coset Hx is not equal to a left coset xH. But if we have Hx=xH for all x in G, then H is a normal subgroup of G. An alternative definition is H is normal if x'Hx=H for every x in G. The definitions are equivalent, and Frey and Singmaster give as a theorem Hx=xH for every x in G if and only if x'Hx=H for every x in G. It should be noted that H normal does not imply that the elements h of H commute with the elements x of G. That is, just because Hx=xH we do not necessarily have hx=xh for every h in H (or even for any h in H other than the identity). However, I think it is fair to characterize a normal subgroup as commuting "globally" with G, even if it does not commute "locally". On the other hand, if a subgroup H does commute "locally" (i.e., if hx=xh for all h in H and all x in G), then H is certainly normal. Normal groups serve a function with respect to finite groups analogous to the function served by prime numbers with respect to natural numbers. First of all, any finite group always has at least two trivial normal subgroups, namely the group itself and the group containing only the identity. Second, a finite group containing normal subgroups may be "factored" in a fashion analogous to prime numbers factoring composite numbers. A finite group containing no normal subgroups is called simple, analogous to numbers with no factors being called prime. The cube group G does not have very many normal subgroups, but it does have a few. The first place to look for normal subgroups is to look for subgroups with index 2. That is, look for subgroups that are half as big a G. Such a subgroup is the subgroup A of even permutations. ("A" stands for "Alternating", I think.) It is easy to see that A is normal. If x is even, then Ax=xA=A. if x is odd, then Ax=xA=Abar, where Abar is the set (not group!) of odd permutations. Similarly, any subgroup H with index 2 is normal. If the index of H in G is 2, then H partitions G into two equal size sets H and Hbar. If x is in H, then Hx=xH=H. If x is in Hbar, then Hx=xH=Hbar. If we may digress briefly to the set M of 48 rotations and reflections, then there are three subgroups of M with index 2. In Dan Hoey's taxonomy, they are called C, A, and H. We may categorize the elements of M as even or odd, and as rotations or reflections. There are 12 even rotations, 12 odd rotations, 12 even reflections, and 12 odd reflections. If we take 12 even rotations and 12 odd rotations, we have C. So C is a normal subgroup of M, even if it is not a normal subgroup of G. If we take 12 even rotations and 12 even reflections, we have A. This A (a subgroup of M) is not to be confused with the A we have already talked about which is a subgroup of G. But I think the name derives from the same source ("Alternating") in either case. If we take 12 even rotations and 12 odd reflections, we have H. Returning to G, the next two normal subgroups are Ac which leaves the set of edges fixed, and Ae which leaves the set of corners fixed. Ac is even on the corners, and Ae is even on the edges, in order to conserve parity. Note that both Ac and Ae are normal subgroups of A as well as of G. I suppose that what is going on with Ac and Ae is obvious enough, but I want to talk about it for a minute anyway. I most typically think of an equation such as X=RLUD'R as meaning something to the effect that "X" is a shorthand *name* for the collection of five processes (in order) R, L, U, D', and R. But I still tend to think of the processes as distinct. However, from the point of view of group theory, X is a single operation which exists in its own right just as do the quarter turns. With a physical cube, you cannot perform an operation in Ac or Ae without making a fairly long sequence of quarter turns. For example, something so simple as performing FF on the corners while leaving the edges fixed is non-trivial. But from the point of view of group theory, we can easily find a single permutation X[C,E] such that X[C]=FF[C] while X[E]=I[E]. Indeed, from the point of view of group theory, you are never more than one move from Start. That is, if you are at X, the one move which will always solve the cube is X'. It is only if you are asked to decompose X' into generators such as quarter-turns that the question of how far from Start you are makes any sense. If a subgroup H of G is normal, the left cosets form a group under the operation (xH)(yH)=(xy)H. This group is called the factor group of H in G or the quotient group of G by H, and is denoted as G/H. Martin Schoenert recently clarified that while there may be more than one way to define an operation on cosets such that they form a group, the notation G/H is usually reserved for the case where the operation is (xH)(yH)=(xy)H. The factor group G/A contains two elements, and is isomorphic to any group containing only two elements. We may write it as ={A,Abar}, where A is the identity of the group. The factor group G/Ac is isomorphic to the set of all permutations on the edges (which we have written as G[E] in the recent past). The factor group G/Ae is isomorphic to the set of all permutations on the corners (which we have written as G[C] in the recent past). Since Ac and Ae are normal subgroups of A, we may write A/Ac and A/Ae which are isomorphic to Ae and Ac, respectively. We can find normal subgroups of Ac and Ae. The set At of all permutations in Ac which leave all corner locations fixed except for twisting some of them is a normal subgroup of Ac. The set Af of all permutations in Ae which leave all edge locations fixed except for flipping some of them is a normal subgroup of Ae. (This twists and flips have to follow the normal rules of conservation of twist and flip, of course.) This completes the list of normal subgroups. I will now give Frey and Singmaster's proof that we are done, while interposing some questions of my own for the cube theory experts out there. My first question is that Frey and Singmaster do not state that At and Af are normal subgroups of G. It seems obvious that they are. However, is the formal argument that (for example) At is a normal subgroup of Ac and Ac is a normal subgroup of G; hence, At is a normal subgroup of G? How analogous is the factoring of groups by normal subgroups to the factoring of composite numbers by prime numbers? Continuing with Frey and Singmaster, we may write Ac/At and Ae/Af, where Ac/At is isomorphic to the group Asc which leaves the corners sane and Ae/Af is isomorphic to the group Ase which leaves the edges sane. "Sane" is a term used by Frey and Singmaster in their proof of conservation of twist and flip. In general, it is easy to see if a cubie is twisted or flipped when it is home, but it is not so easy to see if it is twisted or flipped when it is not home. Their proof (and the others I have seen) define a frame of reference so that you can tell if a cube is twisted or flipped when it is not home. A cubie which is not twisted or flipped in this frame of reference is sane. Asc and Ase are not normal subgroups of Ac and Ae, respectively. (I tend to think that the reason they are not normal is related to the fact that the frame of reference required to define sane positions is not unique.) However, Asc and Ase are isomorphic to well known groups. The group Sn of all permutations of n objects is the n-element symmetric group. The subgroup An of all even permutations of n objects is the n-element alternating group (there is that word "alternating" again!). Asc is isomorphic to A8 (there being eight corner cubies) and Ase is isomorphic to A12 (there being twelve edge cubies). A famous result from Abel and Galois is that An does not have any non-trivial normal subgroups for n >= 5. Hence, we have reduced G to normal subgroups which have no more normal subgroups, and we are done. I guess my questions are as follows: 1) why must we restrict ourselves to alternating groups? 2) For example, just as we found three subgroups of M with index 2, might we not find other subgroups of G with index 2 than the one we found? 3) Might we not find a normal subgroup of G with some index other than 2, e.g., with index 3? = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = Robert G. Bryan (Jerry Bryan) (304) 293-5192 Associate Director, WVNET (304) 293-5540 fax 837 Chestnut Ridge Road BRYAN@WVNVM Morgantown, WV 26505 BRYAN@WVNVM.WVNET.EDU From mreid@ptc.com Tue Dec 27 19:49:45 1994 Return-Path: Received: from ptc.com (poster.ptc.com) by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA06219; Tue, 27 Dec 94 19:49:45 EST Received: from ducie.ptc.com by ptc.com (5.0/SMI-SVR4-NN) id AA18097; Tue, 27 Dec 94 19:48:22 EST Received: by ducie.ptc.com (1.38.193.4/sendmail.28-May-87) id AA16989; Tue, 27 Dec 1994 20:00:04 -0500 Date: Tue, 27 Dec 1994 20:00:04 -0500 From: mreid@ptc.com (michael reid) Message-Id: <9412280100.AA16989@ducie.ptc.com> To: Cube-Lovers%ai.mit.edu@ptc.com Subject: Normal Subgroups of G Content-Length: 3023 jerry writes [ ... ] > My > first question is that Frey and Singmaster do not state that At and > Af are normal subgroups of G. It seems obvious that they are. indeed. > However, is the formal argument that (for example) At is a normal > subgroup of Ac and Ac is a normal subgroup of G; hence, At is a > normal subgroup of G? but this argument is not valid. your question might be rephrased: if H is a normal subgroup of G and K is a normal subgroup of H, does it follow that K is a normal subgroup of G ?? the answer is no. here's an easy counterexample: let G be the alternating group A_4, H the subgroup of order 4 {e, (1 2)(3 4), (1 3)(2 4), (1 4)(2 3)}, and K the subgroup {e, (1 2)(3 4)}. it is easy to see that H is normal in G and K is normal in H. however, if x is any three cycle (for example), xK != Kx. [ ... ] > "Sane" is a term used by Frey and Singmaster > in their proof of conservation of twist and flip. In general, it > is easy to see if a cubie is twisted or flipped when it is home, > but it is not so easy to see if it is twisted or flipped when it > is not home. Their proof (and the others I have seen) define a > frame of reference so that you can tell if a cube is twisted or > flipped when it is not home. A cubie which is not twisted or > flipped in this frame of reference is sane. here's a completely different proof of "conservation" which doesn't use any frame of reference. instead of thinking of permutations of edge cubies, think of permutations of the facelets of the edges. any quarter turn induces two four cycles of these edge facelets, which is an even permutation. thus, any legal position has an even permutation of the edge facelets. however, a single flipped edge is just a two cycle of edge facelets, an odd permutation, and therefore is not a legal position. my proof for conservation of twist is slightly more sophisticated, but i think it's worthwhile. the group of legal corner states may be viewed as a subgroup of the wreath product S_8 wr C_3. we have a natural homomorphism S_8 wr C_3 ---> C_3 (*) defined by (s, c_1, ... , c_8) |--> c_1 + ... + c_8 (the cyclic group C_3 is written additively). it is easy to see that this is a homomorphism, but it uses the fact that C_3 is abelian. (in general, we have a natural homomorphism G wr H ---> H^ab ( = H / [H, H] ) defined in the same way.) conservation of corner twist is equivalent to saying that all legal corner states are in the kernel of the map given in (*). however, any quarter turn has order 4, so its image in C_3 must be the identity. thus all quarter turns lie in the kernel, and therefore the same is true of all legal positions. (actually, i've cheated slightly here. we actually need a frame of reference in order to view the group of corner states as a subgroup of S_8 wr C_3.) mike From BRYAN@wvnvm.wvnet.edu Tue Dec 27 22:46:45 1994 Return-Path: Received: from WVNVM.WVNET.EDU by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA13741; Tue, 27 Dec 94 22:46:45 EST Message-Id: <9412280346.AA13741@life.ai.mit.edu> Received: from WVNVM.WVNET.EDU by WVNVM.WVNET.EDU (IBM VM SMTP V2R2) with BSMTP id 2172; Tue, 27 Dec 94 14:26:46 EST Received: from WVNVM.WVNET.EDU (NJE origin BRYAN@WVNVM) by WVNVM.WVNET.EDU (LMail V1.2a/1.8a) with BSMTP id 9642; Tue, 27 Dec 1994 14:26:46 -0500 X-Acknowledge-To: Date: Tue, 27 Dec 1994 14:26:45 EST From: "Jerry Bryan" To: "Cube Lovers List" Subject: Squares Group On 9 Aug 1994, Mark Longridge posted God's Algorithm results for the squares group consisting entirely of 180 degree turns. Mark invited corroboration. The following will serve to verify Mark's results, and will also provide the same information for the M-conjugacy classes of . Notice that the ratio of cube positions to M-conjugacy classes never gets very close to 48. Hence, there are a significant number of positions in at each level of the search tree that are at least somewhat "symmetrical". M Branching Cube Branching Ratio of Level Conjugate Factor Positions Factor Cubes to Classes M Classes 0 1 1 1 1 1 1 6 6 6 2 2 2 27 4.5 13.5 3 5 2.5 120 4.4444 24 4 18 3.6 519 4.3250 28.8333 5 56 3.1111 1932 3.7225 34.5000 6 162 2.8929 6484 3.3561 40.0247 7 482 2.9753 20310 3.1323 42.1369 8 1258 2.6100 55034 2.7097 43.7472 9 2627 2.0882 113892 2.0695 43.3544 10 4094 1.5584 178495 1.5672 43.5992 11 4137 1.0105 179196 1.0039 43.3154 12 2231 0.5393 89728 0.5007 40.2187 13 548 0.2456 16176 0.1803 29.5182 14 114 0.2080 1488 0.0920 13.0526 15 16 0.1404 144 0.0968 9 Total 15752 663552 42.1249 = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = Robert G. Bryan (Jerry Bryan) (304) 293-5192 Associate Director, WVNET (304) 293-5540 fax 837 Chestnut Ridge Road BRYAN@WVNVM Morgantown, WV 26505 BRYAN@WVNVM.WVNET.EDU From mschoene@math.rwth-aachen.de Fri Dec 30 09:20:21 1994 Return-Path: Received: from samson.math.rwth-aachen.de by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA05461; Fri, 30 Dec 94 09:20:21 EST Received: from hobbes.math.rwth-aachen.de by samson.math.rwth-aachen.de with smtp (Smail3.1.28.1 #11) id m0rNi90-000MPDC; Fri, 30 Dec 94 15:17 MET Received: by hobbes.math.rwth-aachen.de (Smail3.1.28.1 #19) id m0rNi8z-00025fC; Fri, 30 Dec 94 15:17 WET Message-Id: Date: Fri, 30 Dec 94 15:17 WET From: "Martin Schoenert" To: Cube-Lovers@ai.mit.edu In-Reply-To: "Jerry Bryan"'s message of Tue, 27 Dec 1994 11:23:06 EST <9412272155.AA00248@life.ai.mit.edu> Subject: Re: Normal Subgroups of G Jerry Bryan wrote in his e-mail message of 1994/12/27 Recently, there was some discussion of whether the set C of twenty-four rotations is a normal subgroup of the cube group G=. It isn't, but I decided to write up some information about normal subgroups as it relates to the cube. Most of the following is from Frey and Singmaster. Any good stuff is theirs. Any crud that sneaks in is mine. Very good. The lattice of normal subgroups of G is not too complicated and relates nicely to the structure of this group. Allow me to throw in my $0.02. Nitpicking alert! C is not even a subgroup of G=. It is a subgroup of CG. But not a normal one. Jerry continued It should be noted that H normal does not imply that the elements h of H commute with the elements x of G. That is, just because Hx=xH we do not necessarily have hx=xh for every h in H (or even for any h in H other than the identity). However, I think it is fair to characterize a normal subgroup as commuting "globally" with G, even if it does not commute "locally". On the other hand, if a subgroup H does commute "locally" (i.e., if hx=xh for all h in H and all x in G), then H is certainly normal. In group theory there this distinction is made by using the terms *normal* and *central* (even though globally and locally are perhaps more descriptive names). If xH = Hx, then x is said to *normalize* H. The set of all elements that normalize H is called the *normalizer* of H, usually written N_G(H). It is easy to see that N_G(H) is a subgroup of G containing H. If every x of G normalizes H, then H is said to be *normal* in G. Of course H is normal in G, if and only if N_G(H) = G. If xh = hx for every h in H, then x is said to *centralize* H. The set of all elements that centralize H is called the *centralizer* of H, usually written C_G(H). It is easy to see that C_G(H) is again a subgroup of G, but it need not contain H (it contains H if and only if H is abelian). If every x of G centralizes H, then H is said to be *central* in G. Of course H is central in G, if and only if C_G(H) = G. Furthermore it is easy to see that H is central, if and only if H is a subgroup of C_G(G), which is the set of those elements in G that commute with all elements in G. C_G(G) is called the *center* of G. And as you say, a central subgroup is also normal, but a normal subgroup need not be central. If N1 and N2 are two normal subgroups of G, then it is easy to see that the intersection of N1 and N2 and the closure of N1 and N2 are both normal subgroups too. Thus the set of normal subgroups of G is closed w.r.t. intersection and closure. In other words, the set of normal subgroups forms a lattice. I shall draw the lattice of normal subgroups of G below. Jerry continued Normal groups serve a function with respect to finite groups analogous to the function served by prime numbers with respect to natural numbers. First of all, any finite group always has at least two trivial normal subgroups, namely the group itself and the group containing only the identity. Second, a finite group containing normal subgroups may be "factored" in a fashion analogous to prime numbers factoring composite numbers. A finite group containing no normal subgroups is called simple, analogous to numbers with no factors being called prime. This is correct. Allow me a few more remarks. Groups are composed from simple groups, which correspond to primes. The simple groups have been classified. There are several families (the alternating groups A_n are one such family), and 26 sporadic simple groups. This classification is one of the outstanding mathematical achievements. It is estimated that the complete proof is about 10000 pages long (distributed over several papers, books, Ph.D. thesis, etc.). And then there are the ways in which those simple groups can be composed. In the case of natural numbers, this is very simple. The fundamental theorem tells us, that there is, up to the order, just one way in which any natural number is composed from primes. In the case of groups it is much more difficult. There is still a theorem which tells us that the composition factors of a group are determined up to order. But not any order will do. For example the symmetric group S_3 of size 6, has a factor group C_2 over a normal subgroup C_3, but it cannot be decomposed with a factor group C_3 over a normal subgroup C_2. Furthermore given a certain set of composition factors and a certain order, there may be several groups that decompose in this way. For example the cyclic group C_6 can also be decomposed with a factor group C_2 over a normal subgroup C_3. Even in the simplest case, groups of prime power size, which decompose as a sequence of cyclic groups C_p, is so difficult that they have not been classified (and maybe never will). Jerry continued The cube group G does not have very many normal subgroups, but it does have a few. The first place to look for normal subgroups is to look for subgroups with index 2. That is, look for subgroups that are half as big a G. Such a subgroup is the subgroup A of even permutations. ("A" stands for "Alternating", I think.) It is easy to see that A is normal. If x is even, then Ax=xA=A. if x is odd, then Ax=xA=Abar, where Abar is the set (not group!) of odd permutations. Similarly, any subgroup H with index 2 is normal. If the index of H in G is 2, then H partitions G into two equal size sets H and Hbar. If x is in H, then Hx=xH=H. If x is in Hbar, then Hx=xH=Hbar. ... and later on ... The factor group G/A contains two elements, and is isomorphic to any group containing only two elements. We may write it as ={A,Abar}, where A is the identity of the group. This is correct. There is another way to obtain A, which is also very instructive. Let G be any group. Let g1 and g2 be two elements of G. Then the element g1^-1 * g2^-1 * g1 * g2 is called the commutator of g1 and g2, and is usually written as [g1,g2]. Now let g be any element of G. Then g^-1 [g1,g2] g = g^-1 g1^-1 g2^-2 g1 g2 g = (g^-1 g1^-1 g) (g^-1 g2^-1 g) (g^-1 g1 g) (g^-1 g2 g) = (g^-1 g1 g)^-1 (g^-1 g2 g)^-1 (g^-1 g1 g) (g^-1 g2 g) = [ (g^-1 g1 g), (g^-1 g2 g) ]. Thus the conjugate of a commutator is again a commutator. It follows that the subgroup generated by all commutators of all pairs of elements of G is a normal subgroup. This subgroup is called the *commutator subgroup* or *derived subgroup* of G, and is usually written G'. It is the minimal normal subgroup of G, such that the factor group G/G' is an abelian group. Minimal means that for each normal subgroup N of G such that G/N is an abelian group, G' is a subgroup of N. In the case of the cube group G' is A. I shall use G' instead of A. Jerry continued If we may digress briefly to the set M of 48 rotations and reflections, then there are three subgroups of M with index 2. In Dan Hoey's taxonomy, they are called C, A, and H. We may categorize the elements of M as even or odd, and as rotations or reflections. There are 12 even rotations, 12 odd rotations, 12 even reflections, and 12 odd reflections. If we take 12 even rotations and 12 odd rotations, we have C. So C is a normal subgroup of M, even if it is not a normal subgroup of G. If we take 12 even rotations and 12 even reflections, we have