From hoey@aic.nrl.navy.mil Fri Aug 13 19:19:41 1993 Received: from Sun0.AIC.NRL.Navy.Mil by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA04412; Fri, 13 Aug 93 19:19:41 EDT Received: from sun13.aic.nrl.navy.mil by Sun0.AIC.NRL.Navy.Mil (4.1/SMI-4.0) id AA05894; Fri, 13 Aug 93 18:26:10 EDT Return-Path: Received: by sun13.aic.nrl.navy.mil; Fri, 13 Aug 93 18:26:09 EDT Date: Fri, 13 Aug 93 18:26:09 EDT From: hoey@aic.nrl.navy.mil Message-Id: <9308132226.AA28300@sun13.aic.nrl.navy.mil> To: Mark Longridge , cube-lovers@life.ai.mit.edu Subject: Re: Squares group In-Reply-To: <60.251051.104.0C180C07@canrem.com> Mark Longridge has some interesting things to say about the antipodes of the group generated by half-turns: > If we define "symmetry level" as the number of distinct patterns > generated by rotating the cube through it's 24 different > orientations in space then most known antipodes are symmetry level > 6. Thus the lower the number the higher the level of symmetry. The > least symmetric positions have level 24, and this is very common. This approach is somewhat unfortunate in two ways. First, it would be better to use the full 48-element symmetry group M of the cube, because some patterns are not recognized as transformed images of each other if you only use the 24-element group C of rotations. For instance, the positions reached by processes F2R2T2 and F2T2R2 cannot be related with C, so you would see four classes of positions at distance three rather than three. But the antipodes you give are all mirror-symmetric, so there is no new coalescence there. Relating processes that are conjugates by a reflection is usually somewhat tricky, since the moves of the process must be changed in direction (replacing clockwise by counterclockwise) but in the squares group this is a nonproblem. The second deficiency of your approach is that you lose information by specifying only the index of the symmetry subgroup (the ``number of distinct patterns generated ...''). It makes sense to find out exactly which subgroup of M is the symmetry group of your positions. I've done that, below. Each of these symmetry groups comes in three conjugates, so I've transformed some of the processes (marked x) so they all use the same particular symmetry group(s). The group elements are given as cycles of the cube faces, so (TD)(FRBL) means to reflect T<->D and rotate F->R->B->L->F. > Cases with symmetry level 6: These are cases where the symmetry group has order 8. > p66x Double 4 corner sw L2 D2 R2 T2 L2 T2 F2 R2 (F2 B2 T2 F2) T2 L2 B2 > p80 2 DOT, Invert T's R2 B2 D2 R2 B2 L2 B2 L2 (T2 D2 F2 T2) F2 L2 T2 > p99 2 DOT, 4 ARM R2 B2 D2 L2 B2 L2 F2 L2 (T2 D2 F2 T2) F2 L2 T2 > p100 2 Cross, 4 ARCH 1 R2 B2 T2 R2 F2 L2 F2 L2 (T2 D2 F2 T2) F2 L2 T2 p66x, p80, p99, and p100 have symmetry group P=<(TD)(FRBL),(FB),(LR)>. > p67x Antipode 2 R2 D2 B2 T2 B2 T2 F2 L2 (F2 B2 T2 F2) L2 F2 D2 > p130 2 Cross, 4 ARCH 2 L2 B2 D2 B2 L2 D2 F2 L2 (T2 D2 F2 L2) F2 L2 T2 p67x and p130 have symmetry group Q=<(TD),(FRBL)>. > p135x 2 X, 4 T D2 B2 L2 F2 R2 F2 R2 D2 (R2 L2 F2 R2) D2 L2 F2 > p137 2 X, 4 ARM L2 F2 T2 B2 T2 F2 T2 L2 (T2 D2 F2 T2) L2 D2 F2 p135x and p137 have symmetry group S=<(TD),(FB)(LR),(FR)(BL)>. > Cases with symmetry level 12: These have 4-element symmetry groups. > p108 2 DOT, 2 T, 2 ARM L2 F2 T2 R2 B2 L2 F2 L2 (T2 D2 F2 T2) F2 L2 T2 > p128x 2 H, 2 T, 2 CRN L2 D2 R2 T2 L2 T2 F2 R2 (F2 B2 T2 F2) T2 L2 F2 > p129x 2 H, 2 T, 2 ARCH R2 T2 L2 T2 L2 T2 F2 R2 (F2 B2 T2 F2) T2 L2 F2 > p131x 2 H, 2 ARM, 2 ARCH L2 T2 R2 B2 D2 L2 B2 L2 (F2 B2 T2 F2) T2 L2 T2 > p132 2 Cross,2 ARCH,2CRN L2 F2 D2 R2 F2 L2 B2 L2 (T2 D2 F2 T2) F2 L2 D2 > p136x 2 H, 2 ARM, 2 CRN R2 T2 L2 F2 D2 L2 F2 L2 (F2 D2 T2 F2) T2 L2 D2 p108, p128x, p129x, p131x, p132, and p136x have symmetry group HP=<(FB),(LR)>. > p133x 2 Cross, 2 T, 2 ARM L2 T2 B2 T2 B2 T2 F2 L2 (F2 B2 T2 F2) L2 F2 D2 > p134x 2 CRN, 2 X, 2 ARCH L2 T2 B2 D2 F2 T2 F2 L2 (F2 B2 T2 F2) L2 F2 D2 p133x and p134x have symmetry group HS=<(TD),(FB)(LR)>. In case you have trouble forming the closure of these groups: P = {I, (FB)(LR), (TD)(FRBL), (TD)(FLBR), (FB), (LR), (TD)(FR)(BL), (TD)(FL)(BR)} Q = {I, (FB)(LR), (TD), (TD)(FB)(LR), (TD)(FRBL), (TD)(FLBR), (FLBR), (FRBL)} S = {I, (FB)(LR), (TD), (TD)(FB)(LR), (TD)(FR)(BL), (TD)(FL)(BR), (FR)(BL), (FL)(BR)} HP = {I, (FB)(LR), (FB), (LR)} HS = {I, (FB)(LR), (TD), (TD)(FB)(LR)}. I should note that the subgroup names M, C, P, Q, S, HP, and HS are part of a general classification of subgroups of M that I worked out some time ago. I have a chart of them I can send; just ask by email. > A few observations... > - It is not possible to swap just 1 pair of edges and corners Certainly, all the generators are even permutations on the edges and on the corners. > - It is only possible to have 4, 6 or 8 corners out of place That is a nice, concise way of putting it. To elaborate, if you permute one of the corner orbits in a 3-cycle, the other will also be permuted in a 3-cycle; otherwise, any pair of cycle structures of the same parity is possible. > - In reaching an antipode one may start with any of the 6 turns > (since antipodes are global maxima, any turn will get you one move > closer) Careful! This also relies on the fact you call a conjecture, below. Otherwise you could have two neighboring global maxima, and their inverses would be antipodes that do not have this property. For instance, consider the corner group as generated by the 24 pairs of neighboring squares (F2R2, etc). This is a 48-element group with diameter 2, trivial enough to be analyzed by hand. Antipodes (L2B2)(D2R2) and (D2R2)(T2F2) are neighbors, because (L2B2)(D2R2)(F2T2)=(D2R2)(T2F2). So there is no length-2 process equivalent to (F2T2)(R2D2) that starts with T2F2. > - If the corners are fixed, the position is NOT an antipode > - All known (probably all!) antipodes have symmetry level 6 or 12 I presume these comments are left over from before you found them all. > - Longest order appears to be 12 Appears? The orbits are all of size 4 (two orbits of corners, three orbits of edges), so 12=LCM(2,3,4) is an easy upper bound. Finding one is easy given the processes Singmaster lists. > - Although only conjectural, it is now believed that one turn of a > face MUST lead to a new state which is either 1 move closer or 1 > move farther from START Conjectural? It's immediate from the fact that each generator is an odd permutation of the corner orbit {FTR,FDL,BTL,BDR}. > Question: Are there any irreducible square's group sequences that > are longer then 10 moves? Are these truly irreducible or only > irreducible under Dik Winter's Kociemba inspired program? Well, that could be searched for; a matter of checking 600K positions for each of the 15K or so pattern representatives. I hope I can find the time to hack it up. Dan Hoey Hoey@AIC.NRL.Navy.Mil