From mschoene@math.rwth-aachen.de Tue Jun 20 08:40:27 1995 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 AA21537; Tue, 20 Jun 95 08:40:27 EDT Received: from hobbes.math.rwth-aachen.de by samson.math.rwth-aachen.de with smtp (Smail3.1.28.1 #11) id m0sO2aR-000MP0C; Tue, 20 Jun 95 14:39 MET DST Received: by hobbes.math.rwth-aachen.de (Smail3.1.28.1 #19) id m0sO2aQ-00026zC; Tue, 20 Jun 95 14:39 WET DST Message-Id: Date: Tue, 20 Jun 95 14:39 WET DST From: "Martin Schoenert" To: Cube-Lovers@ai.mit.edu Cc: BRYAN@wvnvm.wvnet.edu In-Reply-To: "Jerry Bryan"'s message of Sun, 18 Jun 1995 15:55:22 -0400 (EDT) Subject: Re: Re: A Third Way to Calculate the Real Size of Cube Space? Jerry wrote in his message of 1995/06/17 We define the real size of cube space to be the number of M-conjugate classes {m'Ym} for m in M, set of 48 rotations and reflections of the cube, and for Y in G. Dan Hoey has calculated the real size of cube space using the Polya-Burnside theorem. Dan and I (mostly Dan) have also calculated the same result using exhaustive computer search. The computer search is much less elegant than the Polya-Burnside results, but the search does provide additional information, such as the number of positions associated with each symmetry group. The results from the computer search have not yet been posted to the list, but a draft paper is in progress. In the meantime, it occurs to me that perhaps -- but only perhaps -- there is a third way to calculate the real size of cube space. The third way would not require (much) computer searching, but would provide the same level of detail about number of positions per symmetry group as does the full blown search. ... detailed description of the method deleted ... And he continued in his message of 1995/06/18 I should have said "a fourth way", I think. Martin Schoernert performed the same calculation with GAP. Hence, we have three ways in hand: 1) Dan's Polya-Burnside method, 2) Martin's GAP calculations, and 3) brute force computer search. My new proposal would then be a fourth way. Well, I don't know about *four* ways. Dan used the Polya-Burnside theorem. That is, he computed the number of M-conjugacy classes as the average number of fixed points of the elements of M w.r.t. to their action on G. He computed the number of fixed points of an element m using clever arguments about the cycle structure of elements of G that m would fix. I simply observed that the number of fixed points of an element m is the size of the centralizer of in G, and then used GAP to compute those. So I don't think it is correct to call this a way of its own. The method you propose is indeed different from Dan's method that uses Polya-Burnside. I can't figure out how the brute force computer search works. So I can't tell whether it is really different from the other methods (and if indeed it is a method to compute the real size of the cube ;-). Jerry, could you say a little bit more about this computation? It appears to me that Dan and Jim Saxe must have realized all the important pieces for your new method when they wrote their seminal ``Symmetry and Local Maxima (long message)'' message of 1980/12/14. As Jerry points out, they did calculate the important values for 9 of the 33 conjugacy classes of subgroups of M (those whose sizes are a multiple of 12). It is neither clear from their message how they found those 9 classes (in fact they apparently found all 98 subgroups of M), nor how they computed the numbers of elements of G that have a specific subgroup of M as symmetry group. Perhaps Dan can say a little bit more about this? Jerry continued in his message of 1995/06/18 Here is a question for Martin: is there any way with GAP to calculate the number of M-conjugacy classes associated with each symmetry class? It is this additional information about the "real cube space" which *is* available via computer search, and for which I am proposing an alternative which does not involve computer search. Of course there is ;-). Given a subgroup H of M, the centralizer of H in G is the set of all those elements of G that commute with all elements of H. But this is of course simply the set of those elements of G that have either H or a larger group as their symmetry group. So we can compute the numbers of elements of G with symmetry group H by computing the size of the centralizer of H in G, and then subtracting the numbers of those elements that have a symmetry group that is a proper supergroup of H. This is easy if we compute those numbers for all subgroups of M, from the larger subgroups down to the smaller. Of course it is not neccessarry to do this for all 98 subgroups of M, but only for one subgroup for each of the 33 conjugacy classes. Then if we simply divide the number of elements with symmetry group H by the index of H in M, we obtain the number of M-conjugacy classes into which those elements fall. As a GAP program this looks as follows # compute the conjugacy classes of subgroups of M classes := ConjugacyClassesSubgroups( M ); numbers := []; # for all conjugacy classes of subgroups of M for i in [Length(classes),Length(classes)-1..1] do # select a representative for this conjugacy class rep := Representative( classes[i] ); # compute how many elements have at least this symmetry group number := Size( Centralizer( G, rep ) ); # subtract the number of elements that have a larger symmetry group for k in [Length(classes),Length(classes)-1..i+1] do for sub in Elements( classes[k] ) do if IsSubgroup( sub, rep ) then number := number - numbers[k]; fi; od; od; # store the number numbers[i] := number; # print the number of the class Print( i, ":\t" ); # the size of the subgroups in the class Print( Size(rep), "\t" ); # the number of subgroups in the class Print( Size(classes[i]), "\t" ); # the number of elements whose symmetry group lies in the class Print( Size(classes[i]), " * ", number, "\t" ); # and the number of M-conjugacy classes of those elements Print( Size(classes[i]), " * ", number, " / ", Index(M,rep), "\n" ); od; *Do not try this with GAP 3.4.2 (our latest release).* GAP 3.4.2 contains several naive functions for permutation groups, that cause this computation to take a very long time. But with GAP 3.5 (our current development version), this produces in about a minute the following table. CLASS SIZE LENGHT NUMBER REAL NAME 33: 48 1 1 * 4 1 * 4 / 1 (M) 32: 24 1 1 * 0 1 * 0 / 2 (C) 31: 24 1 1 * 0 1 * 0 / 2 (AM) 30: 24 1 1 * 20 1 * 20 / 2 (H) 29: 16 3 3 * 124 3 * 124 / 3 (X1,X2,X3) 28: 12 4 4 * 12 4 * 12 / 4 (T1,T2,T3) 27: 12 1 1 * 48 1 * 48 / 4 26: 8 3 3 * 384 3 * 384 / 6 25: 8 3 3 * 1408 3 * 1408 / 6 24: 8 3 3 * 2944 3 * 2944 / 6 23: 8 3 3 * 1920 3 * 1920 / 6 22: 8 3 3 * 384 3 * 384 / 6 21: 8 3 3 * 896 3 * 896 / 6 20: 8 1 1 * 11892 1 * 11892 / 6 19: 6 4 4 * 416 4 * 416 / 8 18: 6 4 4 * 32 4 * 32 / 8 17: 6 4 4 * 7740 4 * 7740 / 8 16: 4 6 6 * 96232 6 * 96232 / 12 15: 4 6 6 * 96256 6 * 96256 / 12 14: 4 3 3 * 92928 3 * 92928 / 12 13: 4 3 3 * 437504 3 * 437504 / 12 12: 4 3 3 * 574208 3 * 574208 / 12 11: 4 3 3 * 1163520 3 * 1163520 / 12 10: 4 3 3 * 144640 3 * 144640 / 12 9: 4 3 3 * 62208 3 * 62208 / 12 8: 4 1 1 * 280272 1 * 280272 / 12 7: 3 4 4 * 3770864 4 * 3770864 / 16 6: 2 6 6 * 424415168 6 * 424415168 / 24 5: 2 6 6 * 2547748032 6 * 2547748032 / 24 4: 2 3 3 * 15285460992 3 * 15285460992 / 24 3: 2 3 3 * 18342768640 3 * 18342768640 / 24 2: 2 1 1 * 45862360944 1 * 45862360944 / 24 1: 1 1 1 * 43252003109885814336 1 * 43252003109885814336 / 48 As expected the numbers in the fourth column add to the size of G. And the numbers in the fifth column add to 901083404981813616, the real size of the cube (|M\MG/M|). For those classes that I could identify I have added their names. If somebody could describe Dan's taxonomy, I will name the other classes as well. 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