# Coset Enumeration with GAP

I have downloaded GAP version 4.7.8. for windows, and installed everything (all packages, including"ACE") with the installer. Now I want to do a simple task, enumerating the cosets. To create a group and a subgroup I execute:

gap> G := SymmetricGroup( 8 );
Sym( [ 1 .. 8 ] )
gap> U := Subgroup( G, [ (1,2), (3,4), (3,4,5) ] );
Group([ (1,2), (3,4), (3,4,5) ])


which works fine. Now for coset enumeration I found in the GAP Manual for Version 4.7.8 the function CosetTable, but when I trying to execute in analogy with the example given there I get:

gap> tab := CosetTable(G, U);
Error, no method found! For debugging hints type ?Recovery from NoMethodFound
Error, no 1st choice method found for CosetTable' on 2 arguments called from
<function "HANDLE_METHOD_NOT_FOUND">( <arguments> )
called from read-eval loop at line 3 of *stdin*
you can 'quit;' to quit to outer loop, or
you can 'return;' to continue


which leaves me with a big question sign? Using "? Coset Table" directly in GAP just gives me also the above section in the manual. Now looking further through the manual I found the function "CosetTableBySubgroup", executing gives me

gap> CosetTableBySubgroup(G,U);
[ [ 2, 4, 1, 6, 8, 3, 5, 10, 7, 9 ], [ 3, 1, 6, 2, 7, 4, 9, 5, 10, 8 ],
[ 1, 5, 7, 4, 2, 6, 3, 9, 8, 10 ], [ 1, 5, 7, 4, 2, 6, 3, 9, 8, 10 ] ]


So luckily something that works, but what would be preferable would be a list of cosets, something like this GAP Code which unluckily does not work (maybe because it refers to an old version), because it gives:

gap> LeftCosets(G, U);
Error, Variable: 'LeftCosets' must have a value not in any function at line 6 of *stdin*


While searching through the web I found this document, stating that you have to define the function "CosetTable" first, but when I try to execute the code there I get:

gap> CosetTable:=function(g,n)
> local x,y,tmp;
> tmp:=Flat(List(LeftCosets(g,n),x->Elements(x)));
Syntax error: warning: unbound global variable
tmp:=Flat(List(LeftCosets(g,n),x->Elements(x)));
^


So does not help. Then I found the package "ACE", and tried to use it, but this package, despite being installed, does not load on my system:

gap> LoadPackage("ace");
#I  Package ACE'': The program ace' is not compiled
fail


How should I compile, I have no compiler on my Windows 8.1 system, and I used the installer, which should have all packages pre-installed on it?

So how can I enumerate the cosets in GAP?????

• Binaries for ACE package are not included in the Windows version, but you should be able to do this without ACE: see Manual Section on Cosets Oct 4 '15 at 13:58
• Thanks for your answer! But I am curious, why was "CosetTable" not working, despite being listed in the manual? Oct 4 '15 at 14:16
• The basic problemis that coset enumeration is an algorithm for groups defined by finite presentations, and not for permutation groups. But a coset table is not a list of cosets, it is a list of the images of the group generators in the action of the group by multiplication on the right cosets. There is a function $\mathsf{RightCosets}$ that will list the cosets,, or $\mathsf{RightTransversal}$ if you just want a list of transversal elements. Oct 4 '15 at 14:24
• If a package is missing on windows, you may try to use Cygwin and build GAP and packages there. Another alternative would be a Docker container for GAP and packages - I'd be interested in some feedback if you'd try that. As for the Windows installer, it splits packages into several groups, and IIRC the ACE package is in the group which makes clear that it doesn't work on Windows - but it is included since users still will be able to search in its manual using the GAP help system, inspect the code, etc. Oct 4 '15 at 15:53
• Not necessarily - GRAPE package includes Windows binary produced with Cygwin, for example (it's stand-alone so it does not matter whether with the same Cygwin version that was used to build GAP or not). But different packages may have different ways of interacting with GAP, so YMMV. You may start GAP in Cygwin shell and in this case use it like in a UNIX environment. VirtualBox should work fine for you. Docker is just another virtualisation solution, comes with as many packages and external dependencies satisfied as we can :) Oct 4 '15 at 16:11

Forget about the external binaries (or the ACE package, or in fact any packages at all) at the moment -- they can give runtime improvements, but that is not what you need here. Also the web pages you link are not the best references. Go to http://www.gap-system.org.

CosetTable or "coset enumeration" refers to a technical concept (a particular way to write down a permutation representation for finitely presented groups. Again this is most likely not what you are after. (The CosetTableBySubgroup gives such a table -- each coset is represented by a number.)

If you want a list of the cosets (GAP uses right cosets, not left cosets and there is basically no functionality for left cosets), you can use the command RightCosets:

gap> g:=SymmetricGroup(5);
Sym( [ 1 .. 5 ] )
gap> s:=Subgroup(g,[(1,2,3),(2,3,4)]);
Group([ (1,2,3), (2,3,4) ])
gap> SetName(s,"mysubgroup");
gap> cosets:=RightCosets(g,s);
[ RightCoset(mysubgroup,()), RightCoset(mysubgroup,(3,4)),
RightCoset(mysubgroup,(1,5)), RightCoset(mysubgroup,(1,5)(3,4)),
RightCoset(mysubgroup,(1,5,2)), RightCoset(mysubgroup,(1,5,2)(3,4)),
RightCoset(mysubgroup,(1,5,3)), RightCoset(mysubgroup,(1,5,3,4)),
RightCoset(mysubgroup,(1,5,4)), RightCoset(mysubgroup,(1,5,4,3)) ]


You can then determine the action on the cosets by multiplication

gap> act:=Action(g,cosets,OnRight);
Group([ (1,4,5,7,9)(2,3,6,8,10), (1,2)(3,5)(4,6)(7,8)(9,10) ])


or ActionHomomorphism (which will not return the image group, but a homomorphism.

• @Stefan: a trick which could perhaps save your time greatly and avoid hitting manuals for GAP 3 still lying around in Internet is to use GAP online help: enter ??Coset in GAP and follow the instructions. Oct 4 '15 at 18:03
• Very Welcome here @ahulpke. :-) Nov 21 '15 at 9:05