[GAP Forum] Conway Co2 group

[Alexander Hulpke]

Dear GAP Forum,

On Apr 6, 2006, at 9:29 , Rudolf Zlabinger wrote:

> I try to handle the Conway Co2 group in GAP. I formed a Fpgroup  
> with the relators as given in the ATLAS as follows:

As this question concerns two aspects that come up again and again,  
allow me a more general answer:

The first aspect is on how to get a particular simple (or close to  
simple) group in GAP.

The most ``universal'' source is -- as already mentioned by several  
contributors -- probably the ATLAS web pages maintained by Rob Wilson  
and collaborators which provides a plethora of representations for  
such groups. In particular, there is the AtlasRep package which  
provides a very nice interface.

By searching through the forum archive you will find several mails  
describing this package in more detail.

A second way to get these groups is by the fact that they often have  
a faithful primitive representation of small degree. (For Example Co2  
has a representation of degree 2300.)
Thus many of these groups can be found in the primitive groups  
library. Even if you don't know the degree, but the order you can  
search for it:

AllPrimitiveGroups(IsSimple,true Size,42305421312000);

(This will run a while as it has to read in the whole library to  
check. However you only need to do this once.)

The second aspect is working with finitely presented groups.

Often the first example of defining a group in an abstract algebra  
course is de facto as a finitely presented group. Unfortunately this  
belies a serious problem:

    There can not be an algorithm (i.e. there is a proof that no such  
algorithm can exist)
    which would be able to test for an arbitrary finitely presented  
group whether
    it is trivial. In particular just testing the equality of words  
in a finitely presented
    group cannot be solved in general.

There are heuristics which can work in certain cases, but in other  
situations these heuristics fail and end up using huge amounts of  
memory and runtime. With this in mind, the following rules of thumb  
are worth remembering:

- If you have a finite group for which you know the order or even the  
isomorphism type don't represent it as a finitely presented group or  
-- if you have no other possibility -- convert it into another  
representation (say a permutation group as soon as possible.

- If you run any ``generic'' command for finitely presented groups,  
GAP internally has to find a way to compare elements. This is either  
a faithful permutation representation or a confluent rewriting  
system. Both can be potentially very large.

- Even with such an element comparison in place almost all algorithms  
used will be very naive, for example enumerating elements. Even just  
testing whether the group is finite can be unsurmountable.

- GAP does NOT automatically translate all complicated commands to  
permutation groups, because such a permutation representation could  
potentially be large and doing so would interfere with some  
calculations for huge finitely presented groups. You have to form the  
permutation representation by hand.

- If you want to get results as words in generators, still work in a  
permutation group, but use the permutation representation to pull the  
end result back into a finitely presented (or a free) group.

- It can sometimes be worth to preprocess a finitely presented group  
using `SimplifiedFpGroup' or `IsomorphismSimplifiedFpGroup' to  
eliminate redundant generators.

- If you know a priori the order of a group (of whatever form) you  
can often help GAP by telling it the order:
SetSize(G,known_size);

So how could we go about finding a faithful permutation  
representation. The most naive way is `IsomorphismPermGroup' but this  
will by default for FP groups use via the representation on the  
cosets of a cyclic subgroup. (The reason for this is that in general  
such groups are not simple and we need to ensure that we get a  
faithful representation.)
This is out of the question for a group as large as Co2.

The next possibility is to use the permutation representation on the  
cosets of a subgroup (or a set of subgroups). Here we are in luck, as  
CO2 is simple and any nontrivial representation will be faithful. So  
we only need to find a subgroup.

To find subgroups one could use quotient algorithms and take  
preimages of subgroups of quotients, or one could use the low index  
algorithm to find subgroups of small (say 20-50 at most) index.

In our case alas the group is perfect and the smallest subgroup index  
is 2300. So neither method will succeed. Thus we are left with a  
slightly desperate attempt:

Construct subgroups from generators. (In fact, given the particular  
presentation used in the example this is not as desperate as it  
sounds. For these Coxeter-type presentations often subgroups  
generated by some generators are a good try.

Indeed for the group co2 you defined in your mail, the following  
yields a subgroup of reasonable finite index:

gap> s:=Subgroup(co2,GeneratorsOfGroup(co2){[1,2,3,4,5,6]});
Group([ a, b, c, d, e, f ])
gap> Index(co2,s);
47104

Now we can take the permutation action on the cosets to get a  
permutation representation:

gap> act:=FactorCosetAction(co2,s);;
gap> p:=Image(act);
<permutation group with 7 generators>
gap> IsPrimitive(p);
true

Alas this is primitive, so we don't have an easy way of reducing the  
degree of the permutation action via blocks. (In fact it is rather  
hard to construct the representation of degree 2300 from this, which  
makes the first approach much more promising.)

(As Dima Pasechnik wrote, there are other representations in which  
one can easily find generators for the subgroup of index 2300, which  
would give us the degree 2300 representation.)

Best wishes,

    Alexander Hulpke

-- Colorado State University, Department of Mathematics,
Weber Building, 1874 Campus Delivery, Fort Collins, CO 80523-1874, USA
email: hulpke at math.colostate.edu, Phone: ++1-970-4914288
http://www.math.colostate.edu/~hulpke