[GAP Forum] Applying Burnside's Lemma to the 2x2x2 Rubik's Cube?

[Brandon Enright]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Hi GAP Forum,

I'm a relatively new user of GAP and this is my first Forum post.  I'm
having a great time exploring various permutation puzzle groups so
thank you very much to all of the developers that have helped to
make such great software!

A common problem that comes up on certain permutation puzzles has to do
with "extra" symmetry of certain positions when the whole puzzle is
reoriented in space.  When this happens simple combinatoric counting
arguments only produce an approximate number of distinct states.  This
doesn't happen for the 3x3x3 Rubik's Cube because the 6 face centers
always provide a reference.

My trouble is when you don't have a reference and certain positions
have extra symmetry so they look identical from more than one
orientation of the puzzle.  If you'd like to see an image of a puzzle
where this happens, I've asked about this problem (with images) at
http://math.stackexchange.com/q/1822752/132892

So let me be specific.  I have a 2x2x2 Rubik's Cube defined by the
following 3 generators:

# Turn U face
TU := (1, 2, 3, 4)(5, 7, 9, 11)(6, 8, 10, 12);
# Rotate whole puzzle around U face
RU := (1, 2, 3, 4)(5, 7, 9, 11)(6, 8, 10, 12)
      (13, 15, 17, 19)(14, 16, 18, 20)(21, 22, 23, 24);
# Rotate whole puzzle around L face
RL := (5, 6, 14, 13)(1, 7, 22, 20)(2, 15, 21, 12)
      (4, 8, 23, 19)(3, 16, 24, 11)(10, 9, 17, 18);


I can make a group using these generators and also a group using just
the two orientation generators:

# The whole 2x2x2 cube group
custom222 := Group([TU, RU, RL]);

# The 24 orientations of a 2x2x2
custom222o := Group([RU, RL]);

gap> Size(custom222o);
24

gap> Size(custom222) / 24;
3674160


The 3674160 number is the correct number of positions for a normal
2x2x2 Rubik's cube.  I had to divide the number by 24 because the cube
has 24 orientations and positions that are equivalent under orientation
are counted as the same position.

Trouble arises when I want to look at variations of this 2x2x2 where
some stickers look identical.  I have defined which stickers are
identical this way:

samecolors := [[1, 5, 12, 16, 17, 23],[3, 7, 10, 14, 19, 21],
               [2, 4, 6, 8, 9, 11, 13, 15, 18, 20, 22, 24]];

Now I'd like to know how many identical positions there are using this
set of stickers.  I can do that with a stabilizer using OnTuplesSets
which will count how many configurations of the 2x2x2 permute stickers
within each set of identical stickers.  If I divide the size of the
whole group by the size of the identical solutions group I should get
the number of distinct positions:

gap> (Size(custom222) / Size(Stabilizer(custom222, samecolors,
      OnTuplesSets))) / 24;
1701/2

Unfortunately 1701/2 isn't the right answer.  It's not even a whole
number.  The problem is that some positions look identical in more than
one orientation so Burnside's Lemma needs to be applied.  I have
already done this application of Burnside's Lemma by hand to get the
correct answer of 893.  The answer GAP gave of 850.5 wasn't that far
away.

One thing I need to know for Burnside's Lemma is all the symmetries of
the cube.  I can enumerate this by hand but GAP can also tell me it
using the custom222o group:

gap> List(ConjugacyClasses(custom222o), Size);
[ 1, 6, 3, 8, 6 ]


1 is the identity so the cube isn't rotated at all
6 is the six 90-degree rotations about a cube face
3 is the three 180-degree rotations about a cube face
8 is the eight 120-degree rotations about a cube corner
6 is the six 180-degree rotations about a cube edge

By hand I can calculate how many positions of the custom222 group fall
into each of these conjugacy classes, sum them up, and divide by 24 to
get the correct results of 983.  I have also written a program to use
iterative-deepening BFS to enumerate all positions and it confirms that
893 is indeed correct.

But how do I get GAP to give me this number?  I feel like I have all
the pieces but I don't know how to put them together.  If I can get it
working for this simple case, that will allow me to tackle much more
complicated puzzles for which a manual by-hand calculation just isn't
possible.

Thanks in advance for any guidance or pointers for how to handle this!

Best regards,

Brandon

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2

iEYEARECAAYFAld69doACgkQqaGPzAsl94KQ+QCeMHWG5rHLUwaKXO8jvCoV5nt2
fE0AoKqEvsi9hdB87DU5IBtMruzmBfVM
=KoEP
-----END PGP SIGNATURE-----