From cube-lovers-errors@oolong.camellia.org Tue Jul 8 00:16:07 1997 Return-Path: cube-lovers-errors@oolong.camellia.org Received: from oolong.camellia.org (localhost [127.0.0.1]) by oolong.camellia.org (8.6.12/8.6.12) with SMTP id AAA07853; Tue, 8 Jul 1997 00:16:06 -0400 Precedence: bulk Errors-To: cube-lovers-errors@oolong.camellia.org Message-Id: <199707080413.AAA00423@life.ai.mit.edu> Date: Tue, 8 Jul 1997 00:18:18 -0400 From: michael reid To: cube-lovers@ai.mit.edu Subject: superfliptwist requires 20 face turns i can now show that the pattern "superfliptwist" is exactly 20 face turns from start. this position was proposed as a likely antipode of start by cubologist christoph bandelow. in the german edition of his book "einfuerung in die cubologie" he offered a prize for the shortest maneuver for this pattern. the prize was collected by rainer aus dem spring, who found a maneuver in 22 face turns. much later, a maneuver of length 20f was found by herbert kociemba: D F2 U' B2 R2 B2 R2 L B' D' F D2 F B2 U F' L R U2 F' (20f) as one of the first applications of his ingenious searching algorithm. i'll try not to be so verbose with my symmetry reductions this time. first note that "superfliptwist" does not describe a unique position of the cube; there are two possible orientations. in this context, i use the term "position" to refer to one of the 43252003274489856000 possible configurations, and the term "pattern" to refer to an equivalence class of positions under symmetries of the cube. (this concept has been discussed by dan hoey and jerry bryan as the "real size of cube space" i.e. the number of patterns.) the following two facts are easily verified: * superfliptwist commutes with the square of each face turn. * it does not commute with 90 degree slices (e.g. U D') or 90 degree antislices (e.g. U D), however, if A is a 90 degree slice or antislice, then A superfliptwist A^(-1) is also superfliptwist, but in the other orientation. these facts lead to the importance of the following proposition. superfliptwist is not in the subgroup generated by slices and antislices. (note that this group contains all squares of face turns.) proof. we may ignore the corners and just show that all edges cannot be flipped in this subgroup. to do this, we choose dominant facelets on the 12 edges as follows: choose the U or D facelet of the edges in the R-L slice, the R or L facelet of the edges in the F-B slice and the F or B facelet of the edges in the U-D slice. now we may define the flip of an edge that is not in its correct location. all edges start in the correct orientation. a 90 degree slice or antislice along the U-D axis changes the orientation of all eight edges in the F-B slices and R-L slices. similarly, a 90 degree slice or antislice along the F-B or R-L axis flips all edges in two different slices. within this subgroup, either all edges in a given slice are flipped, or none are flipped, and furthermore, the number of the three slices with flipped edges is even, i.e. 0 or 2. however, superfliptwist has all three slices with flipped edges, so it is not in this subgroup. qed. now consider the first syllable of a minimal maneuver for superfliptwist. ("syllable" was defined in my previous message.) if this is a single 180 degree turn, then we may cyclically shift this to the end of the maneuver. similarly, a slice squared may also be shifted to the end of the maneuver. furthermore, 90 degree slices and or antislices may also be shifted to the end of the maneuver, with only the mild effect of changing which orientation of superfliptwist we're doing. from the proposition, we eventually find a syllable which is not of these types, and is therefore of type U or D2 U. in the case of D2 U , we may shift the D2 to the back of the maneuver, so we may suppose that the first face turn is U . furthermore, by conjugating by the cube rotation C_U, if necessary, we may suppose that our maneuver solves our preferred orientation of superflip. the second face turn is in a different syllable, so it is an adjacent face. conjugating by C_U2, if necessary, brings this face to either R or F. therefore we may suppose that the first two face turns are one of the six sequences U R , U R2 , U R', U F , U F2 or U F' . to show that superfliptwist is not within 19f of start, i tested the six patterns obtained by applying these sequences to it. it took my program 7.5 hours to exhaustively search all of these through 17f. (these positions ran a bit faster than most of the others i've tested. this is partly because superfliptwist is 15 face turns from my "target" subgroup, so larger parts of the search tree are pruned.) no solutions were found, so superfliptwist requires 20 face turns. i also let the first situation run partially through depth 18f. in about 4 and a half hours, it found a solution which yields U R F' B U' D' F U' D F L F' L' U R D F U R L (20f, 20q) this is automatically minimal in the quarter turn metric! mike