**Unformatted text preview:**

The Rotation Group of Rubik's CubeOliver KnillRoman E. MdderETH ZurichRevised by Robin S. Sanders and Julie D. SimonUniversity of Illinois, at Urbana-ChampaignABSTRACTIn this project, the group theory program "Cayley" is used to solve some problems associated with Rubik's Cube, including the original problem of restoring the initial state of thecube.Project-No.:003-021Title: Rubik's CubeSubject: AlgebraPrograms: CayleyReferences: 001-021 Die Drehgruppe des Rubikwurfelsfypesetting:mltroffVersion: 5/15/8733T h e M a t h e m a t i c a l L a b o r a t o r y R u b i k ' s C u b e1. IntroductionSeveral years have passed since the Rubik's Cube conquered the world. Almost everyone knows this cube andmany have solved it or have tried to do so for hours. Rarely has there been a puzzle which has caused such a stirand which has found its way not only into the world of games but also into that of mathematics and computers.Before you start your work on this project about Rubik's cube, we recommend that you reach for a cube and getfamiliar with it (again). Many concepts of group theory can be demonstrated with this cube, and abstract definitionscan become more intuitive.1.1. The CubeIf you already know it or are even a cube expert, you may skim this section which defines the structure of the cubeand also introduces some notation.The Rubik's cube consists of 3x3x3 = 27 smaller cubes arranged in one larger cube. The 54 visible faces arecolored such that in the initial state, the 6 faces of the large cube are each a different color. Each layer of 3x3 = 9cubes can be rotated by multiples of 90°. After a few rotations, the colors are in disorder and it is nearly impossible to rearrange them by accidental rotations. The exact number of states that the cube can assume will be one ofthe results of this project.1.2. NotationLower case letters denote the 6 faces of the large cube, as follows:f((rom), b (back), u (up), d (down), / (left), r (right)Clockwise 90° rotation of a lateral 3x3 layer is denoted by the corresponding upper case letters F, B% U, Z>, L and R.Rotations by 180° are denoted by F2, etc. and counter-clockwise 90° rotations by F~\ etc.As an example, the product LDLTlU~lDLD~lLUD~l is a cyclic permutation of three "edge cubes".2. The Group of the Cube as a Permutation GroupFor mathematically dealing with the cube, we also need a formal description of it. The adequate tool is permutation groups.We start by enumerating the visible faces of the smaller cubes, ignoring the ones in the center of each face of thelarger cube. (The latter can be considered as fixed points if we agree never to rotate a central 3x3 layer, which isnot a real constraint.)The rotations can now be written as permutations, where each permutation is represented by a product of cyclic permutations:U= (1, 3, 8, 6)(2, 5, 7, 4)(9, 48, 15, 12)(10, 47, 16, 13)(11, 46, 17, 14)L = (9, 11, 26, 24)(10, 19, 25, 18)(1, 12, 33, 41)(4, 20, 36, 44)(6, 27, 38, 46)F = (12, 14, 29, 27)(13, 21, 28, 20)(6, 15, 35, 26)(7, 22, 34, 19)(8, 30, 33, 11)R = (15, 17, 32, 30)(16, 23, 31, 22)(3, 43, 35, 14)(5, 45, 37, 21)(8, 48, 40, 29)D = (33, 35, 40, 38)(34, 37, 39, 36)(24, 27, 30, 43)(25, 28, 31, 42)(26, 29, 32, 41)B = (41, 43, 48, 46)(42, 45, 47, 44)(1, 24, 40, 17)(2, 18, 39, 23)(9, 38, 32, 3)The rotation group G3 of the cube is now the group generated by U, L, F, /?, D and B. We writeG3 = KUrLfJiJ)^. The degree of G3 is 48.The Mathematical LaboratoryRubik's Cube1 2 34 u 56 7 89 10 11 12 131415 161718 1 1920 f 21 22 r 2324 25 26 27 2829 30 31 3233 34 3536 d 3738 39 4041 42 4344b4546 47 48Fig. 2-13. Problems3.1. ''Subgroups"First, we want to familiarize ourselves with the Cayley program:Find the order of the following subgroups:a) The Rubik group G3 itselfb) The "square group" <R2, L2, F2, 52, £/2, D*>c) The "bridge group" <R, Uy L>d) The "corner group" <R> U, F>e) The "antislice group" <LR, UD, FB>f) The "slice group" <RL'\ UD"\ FB~l>A permutation is called central if it commutes with every other permutation. Verify by theoretic reasoning that theset of all central elements of a group is a subgroup, and even a normal divisor, called the center of the group. UseCayley to find the center of:a) the Rubik group G3b) The "edge group" <£/, R>c) The "slice group" <RL~\ UD~\ FB'l>and find an interpretation of the result on your Rubik's cube.You can easily verify with Cayley that each 5 of the 6 generators suffice to generate G3. Find, by experimenting, asystem of as few generators as possible. (There exists one with only two generators).Optional:The symmetric group of order n consists of all permutations of n elements. Find by theoretic reasoning all symmetric subgroups of G3.35T h e M a t h e m a t i c a l L a b o r a t o r y R u b i k ' s C u b eOptional:A cyclic group of order n is a group having a single generating element c, such that cn is the identity. Try to getan overview over all cyclic subgroups of G3.3.2. "Structure"Now, we want to investigate the structure of G3. Cayley can help us to accomplish this.Find the orbits of G3 and find also the groups that result if the group operations are restricted to these orbits. Findan interpretation for the orbits on your cube.For each one of these groups find now the minimal block system, i.e. those packets of points that always staytogether, and interpret them on your cube.Find out what groups deal only with the packets.Optional:Prove (by theoretical reasoning) that the following permutations are not in G3, i.e. that the described situations cannot be obtained from the initial state by rotations:a) Only one single "corner cube" or "edge cube" is twistedb) Only two "comer cubes" or "edge cubes" have changed places3.3. "Strong Generating Sets"When they first encountered the Rubik's cube, many people spent large amounts oftime finding a method to solveit. Then each time they discovered a similar puzzle, they found the new one a little easier to solve than the last.Some of these other puzzles are: Rubik versions of the other regular polyhedra, the 4x4x4 cube, the magic drumand the tower of Babylon.The fact that experience makes the solution easier indicates that there might be an algorithm for systematically solving all of these problems. Such an algorithm indeed exists and it is based on the so-called strong generating sets.Let G be some permutation group operating on the set M = (1, . . . ,n}. The