From cube-lovers-errors@mc.lcs.mit.edu Sun May 23 20:46:27 1999 Return-Path: Received: from sun28.aic.nrl.navy.mil ([132.250.84.38]) by mc.lcs.mit.edu (8.9.1a/8.9.1-mod) with SMTP id UAA18154 for ; Sun, 23 May 1999 20:46:26 -0400 (EDT) Precedence: bulk Errors-To: cube-lovers-errors@mc.lcs.mit.edu Date: Sun, 23 May 99 20:37:41 EDT Message-Id: <9905240037.AA26143@sun28.aic.nrl.navy.mil> From: Dan Hoey To: whuang@ugcs.caltech.edu (Wei-Hwa Huang) Cc: gej@spamalot.mfg.sgi.com, Cube-lovers@ai.mit.edu Subject: Re: Algorithm for the Antislice Group Gene Johannsen wrote: > I am having problems with this step. My cube is in a > configuration that this maneuver does not solve: And whuang@ugcs.caltech.edu (Wei-Hwa Huang) replied > As I e-mailed Gene, I do not believe his configuration is part of the > anti-slice group -- would any members care to give a quick heuristic to > determine if a cube is in the anti-slice group? Gene Johannsen sent in a reply agreeing that he had probably made a twisto in scrambling the cube. The moderator did not forward that reply to the group, hoping instead to determine a sure answer to the question. I'm sorry if the delay has cast doubt on Wei-Hwa Huang's antislice algorithm (which I have not examined in detail). The problem is actually fairly difficult if we want a definitive answer for any antislice-group position--Singmaster (p. 54) despairs of presenting Morwen B. Thistlethwaite's analysis of the antislice group, settling instead for an outline. I must admit that I have not yet found a complete answer that can be carried out by hand. However, I have a method that will recognize positions in a group four times the size of the antislice group, and that is good enough to weed out almost all of the near misses. In fact, a simpler method that will detect positions in a group 972 times the size of the antislice group is sufficient for the case in question. As in Singmaster we consider a corner-based representation. That is to say, we keep the BLD corner from moving, and perform an antislice as a half-turn of the F, T, or R face together with a quarter-turn of the adjacent center-slice. [ For newcomers, I'll mention that my use of "T" for "Top" instead of "U" for "Up" is an intentional preference; see 22 Feb 90 and 28 Oct 94 in the archives for an explanation. ] In this representation the face centers form a movable part of the cube. We could represent their position as a permutation of the six face centers, but it is more convenient to represent them as a permutation of the four major diagonals of the enclosing cube, as Jim Saxe and I did for the Tartan cube (16 February 1981). We may label the faces and diagonal-endpoints as follows: Z---X | B | Z---W---Y---X---Z | L | T | R | D | Y---X---Z---W---Y | F | Y---W The T antislice acts on the face centers as (F,L,B,R) and on the diagonals as (W,Y,Z,X). Similarly, the R antislice induces the face permutation (T,B,D,F) and the diagonal permutation (W,Z,Y,X). The F antislice induces the permutations (L,T,R,D) and (W,Y,X,Z). In the following, I will use note the diagonal permutations. In addition to the face centers, there are three orbits of edge cubies and two orbits of corner cubies (ignoring BLD). The corner orientation never changes, and reorientation of edges is applied to an entire orbit at a time. I label the edges and corners as follows: [Z]--Z3--Xp | | Z2 B Y2 | | [Z]--Z2--Wp--Y3--Y---Y2--Xp--Z3-[Z] | | | | | Z1 L X1 T Y1 R W1 D Z1 | | | | | Yp--X2--X---X3--Zp--W2--W---W3--Yp | | X2 F W2 | | Yp--W3--W The diagonals W-Wp, X-Xp, Y-Yp, and Z-Zp are labeled Wc, Xc, Yc, and Zc, respectively, for the purpose of recording the face center position. In addition I label the orientation of the edge orbits as P1, P2, and P3, where P1^2 = P2^2 = P3^2 = I. (These could be represented as permutations of 2-sets, but that seems unnecessary). So the three antislices are: Fa = (W,X)(Yp,Zp) (W1,Z1,X1,Y1) (W2,X2) (W3,X3) P1 (Wc,Yc,Xc,Zc), Ta = (X,Y)(Wp,Zp) (X1,Y1) (W2,X2,Z2,Y2) (X3,Y3) P2 (Wc,Yc,Zc,Xc), Ra = (W,Y)(Xp,Zp) (W1,Y1) (W2,Y2) (W3,X3,Y3,Z3) P3 (Wc,Zc,Yc,Xc). corner perm edge perm ori center perm It is immediately apparent that each antislice is an odd permutation of each orbit of corners, of each orbit of edges, and of the center diagonals. In addition, the number of Pi orientations is changed by one on each antislice. Thus we expect to see each of these seven parities agree in any position of the antislice group. Gene Johannsen's position (after replacing color letters with position letters) is BBB BBF <- Back face FFF LLR TDT LLR DTD LLL DTD RRR TDT <- Down face LRR TDT LRR DTD BBB BFF <- Front face FFF which is represented as (X,Y) (Wp,Zp) (W1,Y1)(X1,Z1) (X2,Y2) (W3,Y3,Z3,X3) in the corner-based representation. Here the permutations on the corner orbits and two of the edge orbits is odd. But the {W1,X1,Y1,Z1} orbit has an even permutation and the orientation and center positions are the identity, of even parity. So the position cannot be in the antislice group. I noticed that the difference could conceivably be caused by a single error, say an F-slice move: Fs = (W1,Z1,X1,Y1) (Wc,Yc,Xc,Zc) P1, and with a short program in GAP I was able to find the following single-error process for Gene's position: Fa Ta Fs Fa Ta' Fa Ra^2. Now I'll apologize to anyone whose head is reeling, and invite anyone who's game to join in a little bit of slightly tougher group theory. This will show you how far I've been able to analyze the antislice group, and the part that remains mysterious. Note that the parity constraints above allow: 6 permutations of {W,X,Y}, 24 permutations of {Wp,Xp,Yp,Zp}, 24 permutations each of {W1,X1,Y1,Z1}, {W2,X2,Y2,Z2}, and {W2,X2,Y2,Z2}, 8 subsets of {P1,P2,P3}, and 24 permutations of {Wc,Xc,Yc,Zc}, with a parity constraint on the seven components that reduces the number by 2^6, for 6 * 8 * 24^5 / 64 = 5971968 possible positions. Singmaster notes that the actual size of the antislice group is 6144 = 5971968 / 972 positions. Clearly there are more constraints at work than permutation parity. Most of them are due to life in a certain quotient group. The group S4 of permutations on four letters contains a normal subgroup consisting of the identity plus the three pairs of two-cycles: H = { (), (W,X)(Y,Z), (W,Y)(X,Z), (W,Z)(X,Y) }. The quotient S4/H then has six elements, and is isomorphic to S3. We can see this explicitly by writing down the blocks of S4/H: Block 0 Block 1 Block 2 Block 3 Block 4 Block 5 () (W,X,Y) (W,Y,X) (W,X) (W,Y) (X,Y) (W,X)(Y,Z) (W,Y,Z) (W,Z,Y) (Y,Z) (X,Z) (W,Z) (W,Y)(X,Z) (W,Z,X) (W,X,Z) (W,Y,X,Z) (W,X,Y,Z) (W,X,Z,Y) (W,Z)(X,Y) (X,Z,Y) (X,Y,Z) (W,Z,X,Y) (W,X,Y,X) (W,Y,Z,X) The top line of each block shows the element of S3=S({W,X,Y}) corresponding to the block. Note how easy it is to recognize the blocks 3, 4, and 5: If you have a four-cycles, use one two-cycle from its square; If you have a two-cycle containing Z, use the disjoint two-cycle. This procedure will yield the S3 representative from these blocks. Now remember the antislices? Fa = (W,X)(Yp,Zp) (W1,Z1,X1,Y1) (W2,X2) (W3,X3) P1 (Wc,Yc,Xc,Zc), Ta = (X,Y)(Wp,Zp) (X1,Y1) (W2,X2,Z2,Y2) (X3,Y3) P2 (Wc,Yc,Zc,Xc), Ra = (W,Y)(Xp,Zp) (W1,Y1) (W2,Y2) (W3,X3,Y3,Z3) P3 (Wc,Zc,Yc,Xc). Ignoring the orientation component, we see that the action of every component of Fa is from block 3, every component of Ta from block 4, and every component of Ra from block 5. So for every position in < Fa, Ta, Ra >, each permutation orbit will be in the same block, and the orientation component must still agree in parity. So instead dividing by 2^6, we divide by 6^5 2 = 15552, for 6 * 8 * 24^5 / 15552 = 24576 positions, which is only four times the size of the actual antislice group. The factor of four arises if we fix all but the {Wp,Xp,Yp,Zp} and {Wc,Xc,Yc,Zc} orbits. There are only four possibilities for the last two orbits, rather than the sixteen that my analysis provides. (As Singmaster notes, when the other components are the identity, the four possibilities consist of SOLVED and the four Zigzag/Laughter patterns). Unfortunately, I have not found any way to describe the correspondence between these components in general, to make the analysis exact. Dan Hoey@AIC.NRL.Navy.Mi