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

Question

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.

Answer 1

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.

Answer 2

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

Answer 3

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}$.