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: [EMAIL PROTECTED], Phone: ++1-970-4914288
http://www.math.colostate.edu/~hulpke
_______________________________________________
Forum mailing list
[email protected]
http://mail.gap-system.org/mailman/listinfo/forum
