6
$\begingroup$

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.

  • 0
    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)2011-05-16

3 Answers 3

7

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.

  • 0
    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!2011-05-23
4

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

3

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