# What are good ways of understandng a permutation group from a set of generators?

I'm trying to understand the structure of a Rubik's Cube-style puzzle I'm playing with; I have an expression of the solutions as the permutation group generated by four elements of $S_{16}$, each a simple cycle. My first inclination is to check all words of a given length (I think I can check all 8-element words easily, and maybe all 9- or 10-element words with a little effort) to see which ones move as few pieces as possible and then try and use that to understand more of the structure (for instance, I already know that there are elements of odd sign, so it's not a subgroup of $A_{16}$); above and beyond that, though, what tricks and techniques should I be aware of? In particular, are there any good ways of finding useful/meaningful expressions of my group as some sort of wreath product, or of understanding its quotient in $S_{16}$ (assuming it's even normal!)? I'm presuming that understanding $S_{16}/G$ will provide a sense of the constraints that any valid position has to satisfy...

EDIT: For anyone who's curious enough and has better tools to play with it than I do, the four generators are the cycles: $\alpha = (1\quad 2\quad 3\quad 7\quad 11\quad 10\quad 9\quad 5)$ , $\beta = (2\quad 3\quad 4\quad 8\quad 12\quad 11\quad 10\quad 6)$, $\gamma = (5\quad 6\quad 7\quad 11\quad 15\quad 14\quad 13\quad 9)$, and $\delta = (6\quad 7\quad 8\quad 12\quad 16\quad 13\quad 14\quad 10)$. I wouldn't be surprised to learn it's all of $S_{16}$, but that still leaves a lot of obviously-open questions from a puzzle perspective (minimal-length words to swap two elements and the like), and any good suggestions on ways of finding particular elements of the group (where to look for interesting commutators and conjugates, etc.) would be welcome; I have a little background from doing some basic Rubik's-Cube stuff (for instance, my first look was at the element $(\alpha^2\beta^2)^2$ ), but not much.

-
From your description it seems likely that your group is the whole of S16. You might check that. Programs like GAP gap-system.org make it easy to investigate permutation groups. Feel free to post the generators and I can be more specific. As it is now, the problem is too general for me to say much (every finite group and every finite permutation group could be described more or less as you have done, so it is hard to say anything about them). –  Jack Schmidt May 16 '11 at 17:54
Good point; my apologies. I've added the generators now - and yeah, GAP was the first real tool I was going to apply to it, but it wasn't clear to me how to present my group to GAP... –  Steven Stadnicki May 16 '11 at 18:23
A way to find memorable moves to solve the puzzle is to investigate pretty conjugates of single moves, for example: $(abcabc)d(abcabc)^{-1}$. (and check it for short cycle length) –  Phira May 16 '11 at 18:31

GAP is reasonably well suited to such problems. Here is a sample session for your problem:

gap> g:=Group( (1,2,3,7,11,10,9,5), (2,3,4,8,12,11,10,6),
> (5,6,7,11,15,14,13,9), (6,7,8,12,16,13,14,10) );;
gap> StructureDescription(g);
"S16"


To find short move sequences that leave lots of points stable, you could use your idea of just checking short sequences:

gap> f := FreeGroup("a","b","c","d");;
gap> for w in f do
> p := MappedWord(w,GeneratorsOfGroup(f),GeneratorsOfGroup(g));
> if p <> () and NrMovedPoints(p) < 5 then Print(p," ",w,"\n"); fi;
> od;
( 5,10)( 7,12) d^-2*a^-2*d^2*a^2


Which means that you un-apply δ twice, then un-apply α twice, then δ twice, then α twice. In other words, the commutator of α and δ is a "nice" move.

For smaller puzzles, GAP supplies a function Factorization which you could normally use to answer these questions quickly. For whatever reason it was not working well in this particular example. Normally one would just ask:

 gap> Factorization( g, (1,2) );


and it would give you (a short) move sequence that switched the first and second tiles.

-
Another fairly short one is (11,12,13) a^-1*b*a*b^-1*a^2*c*a^-1*c^-1*a^-1. Modulo some inverses, this is the commutator of (a,b) followed by the a-conjugate of the commutator of (a,c), so maybe is memorable, but check your signs. :-) Let me know if you want a list of moves. I'm just letting the computer spin for a bit on it, as I've never thought about this kind of thing before. –  Jack Schmidt May 16 '11 at 19:21
It turned out that I had the wrong group (I wasn't paying close attention; my generators were actually $\alpha^2, \beta^2, \gamma^2, \delta^2$, so products of 4-cycles, and the group turns out to be $S_8\times S_8/Z_2$), but this was great advice for finding interesting moves (although apparently the combination of EpimorphismFromFreeGroup and PreImagesRepresentative turns out to be more efficient than Factorization). Still, this was the overall most informative answer for me; thank you! –  Steven Stadnicki May 23 '11 at 22:34

Using Maple's group package:

with(group):
a:= [[1,2,3,7,11,10,9,5]]:
b:= [[2,3,4,8,12,11,10,6]]:
c:= [[5,6,7,11,15,14,13,9]]:
d:= [[6,7,8,12,16,13,14,10]]:
G:= permgroup(16, {a,b,c,d}):
grouporder(G);

20922789888000


Since this is 16!, the four cycles do generate all of $S_{16}$.

-

Yes, the group generated by the permutations is all of $S_{16}$.

Here's my GAP:

gap> g:= (1,2,3,7,11,10,9,5);

(1,2,3,7,11,10,9,5)

gap> h:= (2,3,4,8,12,11,10,6);

(2,3,4,8,12,11,10,6)

gap> k:=(5,6,7,11,15,14,13,9);

(5,6,7,11,15,14,13,9)

gap> m:=(6,7,8,12,16,13,14,10);

(6,7,8,12,16,13,14,10)

gap> G:=Group( g,h,k,m);

Group([ (1,2,3,7,11,10,9,5), (2,3,4,8,12,11,10,6), (5,6,7,11,15,14,13,9), >(6,7,8,12,16,13,14,10) ])

gap> Size(G);

20922789888000

gap> Size(SymmetricGroup(16));

20922789888000

-