From mschoene@math.rwth-aachen.de Mon Nov 7 19:20:36 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 AA13091; Mon, 7 Nov 94 19:20:36 EST Received: from hobbes.math.rwth-aachen.de by samson.math.rwth-aachen.de with smtp (Smail3.1.28.1 #11) id m0r4eGO-000MP6C; Tue, 8 Nov 94 01:18 MET Received: by hobbes.math.rwth-aachen.de (Smail3.1.28.1 #19) id m0r4eGN-0000R9C; Tue, 8 Nov 94 01:18 PST Message-Id: Date: Tue, 8 Nov 94 01:18 PST From: Martin.Schoenert@math.rwth-aachen.de To: Cube-Lovers@life.ai.mit.edu Cc: hoey@aic.nrl.navy.mil In-Reply-To: hoey@aic.nrl.navy.mil's message of Fri, 4 Nov 94 11:46:50 EST <9411041646.AA21659@sun13.aic.nrl.navy.mil> Subject: Re: The real size of cube space Dan Hoey writes in his e-mail message of 1994/11/04 In January of this year, Jerry Bryan and I wrote of counting the number of M-conjugacy classes of Rubik's cube. In the sense that (for instance) there is really only one position 1 QT from start, even though that QT may be applied in twelve different ways, this task amounts to counting the true number of positions of the cube. The earlier discussion centered on calculations involving computer analysis of large numbers of positions. However, a look in Paul B. Yale's book _Geometry and Symmetry_ gave me a clue: the Polya-Burnside theorem is a tool that allows us to perform this calculation by hand. ...a very nice application of the Polya-Burnside theorem, to compute the number of M-conjugacy classes in G... Yes, a little bit of group theory can answer many questions arising from the cube. In fact I have noticed that quite a few of well known results in group theory have been rediscovered in this forum. Note that I don't think this is a bad thing. At least for me results that I ``knew'' are now, that they have been demonstrated for the cube, much easier to grasp than they were before (grasp is certainly an appropriate term in connection with the cube). Dan continues For our purpose, we take the group J to be M, the 48-element group of symmetries of the cube. X will be the set of all cube positions, which we usually call Gx (for GE, GC, or G, depending on whether we consider edges, corners, or both; we are considering the positions relative to fixed face centers in all three cases). And the repre- sentation R is the operation of M-conjugation: (R(m))(g) = m' g m. Verifying that R is a homomorphism is an exercise in associativity that Jim Saxe and I carried out in the Symmetry and Local Maxima paper, in the archives [cube-mail-1, 14 December 1980]. The way I view this is as follows. The entire cube group C is a permutation group group on 6*9 points, generated by the six face turns U, D, L, R, F, B; the three middle slice turns M_U, M_L, M_F; and the reflection S. This group has a subgroup M of symmetries of the cube (of order 48), generated by U M_U D', L M_L R', F M_F B', and S. Another subgroup is G, generated by the six face turns, which has index 48 in G. G is a normal divisor of C, G is the semidirect product of M and G. The same is true for GE and GC. Obviously M operates by conjugation on G, and this implies that the mapping R is a homomorphisms. Another way to say this is that M is a subgroup of the outer autmorphism group of G (which in this case can be easily represented as a supplement of G). Note that the elements of M are also a autmorphisms of the Cayley graph. That means that elements of M respects the length of operations. That is if g_1 and g_2 are elements of G that are in one conjugacy class under M, then the lenght of the shortest process effecting them is equal. This follows from the fact that M fixes the set of the generators of G and their inverses. M is fact the largest subgroup of the outer autmorphism group with this property, which makes it rather important. Dan continues R has been so chosen because we wish to calculate the number of M-conjugacy classes of Gx, |Gx\Conj(M)|, which is be the number of orbits of R(M). To apply the Polya-Burnside theorem for this, we need to calculate, for each element of m of M, the number of fixed points of R(m). That is the number of elements g of Gx for which m' g m = g. Multiplying by m, this becomes g m = m g: the fixed points we wish to count are just those elements g of Gx that commute with m. This set is called the *centralizer* of m in Gx. Usually the centralizer in a group X is only defined for elements in X, but it is obvious how to extend this definition. Dan continues The fundamental principle we use in finding whether g commutes with m can be found by examining the cycles of m. Suppose m permutes a cycle (c1,c2,...,ck), so that c2=m(c1), c3=m(c2),...,ck=m(c[k-1]),c1=m(ck). ...nice discussion of what must happen to cycles if two permutations commute... This can be used directly to compute the centralizer of an element in the full symmetric group. Since G's structure is very similar to a symmetric group (or more accurately the direct product of two symmetric groups), it allows to describe the centralizer of an element in G. The more a group differs from a symmetric group the less this analysis helps (for those that know what I'm talking about: the more a group differs from the symmetric group, the worse a backtrack computation using cycle structure analysis is). Dan continues Counting M-conjugacy classes of the entire Rubik's cube M class Edge Corner Corner times edge (class size) F.P. F.P. / (96*class size) =============== ========== ========= ======================= Minor typo. You don't mean ``Corner times edge / (96 * class size)'' but ``Corner times edge / 96 * class size'', which is in fact what you computed for the following table. Dan continues | G\Conj(M) | = 901,083,404,981,813,616 Here is how you compute this value in GAP (excuse me the plug). gap-3.4 -b -g 4m gap> Sum( ConjugacyClasses( M ), > c -> Size( Centralizer(G,Representative(c)) ) / 48 * Size(c) ); 901083404981813616 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