GAP Lesson on Coset Enumeration

gap> LogTo("GAPCosetLesson");

Coset Enumeration

References:
?Coset Table
D.L. Johnson, Presentations of Groups, Cambridge U.P.
?Creating Presentations

Let's get going by defining three groups in GAP:

eight:= <x,y | yxyx^-1, xyxy^-1 >
neweight:= <x,y | y^-3xyx^-1, x^-3yxy^-1 >
one:= < x,y | xy^2x^-1y^-3, yx^2y^-1x^-3 >
two:= < x,y | x^100y^101, x^101y^102 >

You can do this by doing the following, which we learned in an earlier lesson.

gap> e:=FreeGroup(2,"e");
gap> eight:=e/[e.2*e.1*e.2*e.1^-1,e.1*e.2*e.1*e.2^-1];
gap> neweight:=e/[e.2^-3*e.1*e.2*e.1^-1,e.1^-3*e.2*e.1*e.2^-1];
gap> o:=FreeGroup(2,"o");
gap> one:=o/[o.1*o.2^2*o.1^-1*o.2^-3,o.2*o.1^2*o.2^-1*o.1^-3];
gap> t:=FreeGroup(2,"t");
gap> two:=t/[t.1^100*t.2^101,t.1^101*t.2^102];


We have already seen how to get permutation groups isomorphic to the above:

gap> IsomorphismPermGroup(eight);

Exercise: Identify the group eight.

gap> CosetTable(eight, Subgroup(eight,[]));
gap> List(last,PermList);
gap> CosetTable(eight, Subgroup(eight,[eight.1]));
gap> List(last,PermList);
gap> CosetTable(neweight, Subgroup(neweight,[]));

What can you guess so far about the output of CosetTable? Why are there four entries in the list it produces.

The Todd-Coxeter algorithm will now be explained. See the chapter in D.L. Johnson, Presentations of Groups, Cambridge U.P.

We will now investigate how GAP produces coset tables.

gap> CosetTableDefaultMaxLimit:=5;

gap> CosetTable(eight,Subgroup(eight,[]));
brk> table;

Exercise: Find out (as closely as you can in a reasonable time) how many cosets GAP had to create to get the coset table for the group neweight. Do this by changing CosetTableDefaultMaxLimit and/or responding appropriately when you enter the break environment after doing CosetTable.

Do the same thing for the group eight, this time exactly.

Determine the order in which definitions of cosets are made for eight. Compare this with the order in which the first 5 or so definitions are made for the group one. Can you reach any conclusions about the order in which GAP is choosing cosets?

Now determine how many cosets GAP uses before it finishes enumerating the cosets of one.

Investigate similarly the group two.

At this point it will be explained that presentations of the kind given in group two take arbitrarily many cosets.

Examine what happens if you do the following:
gap> Print(CosetTableFromGensAndRels);
gap> ?CosetTableFromGensAndRels