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