> < ^ Date: Thu, 02 Feb 1995 12:36:00 +0000
> < ^ From: Derek Holt <dfh@maths.warwick.ac.uk >
> < ^ Subject: Re: How to reduce words in FpGroups

Jan de Wit writes:
> 1. Given an FpGroup, ie FreeGroup(2)/[a^3,b^2,a*b*a^-1*b^-1] (cyclic group of
> order 6). You can get the elements of this group by using Elements, and now
> I want to compute (a^2*b) * (a). You get a^2*b*a, which is NOT in the list
> of elements. It seems to me that GAP has a way of reducing this expression
> to one which is in the list. How do you do this ?
> The reason I want to do this is to make a data structure containing the
> *entire* multiplication table for a (hopefully small) group, no matter
> what the exact elements are, and start working on that. Then it would be
> possible ,for instance, to check isomorphism between CyclicGroup(6) - a
> permutation group - and the FpGroup above. (Yes, this is brute force, and I
> should write a program in C for it, but I want to try it using GAP).
> Maybe there are other ways of doing this that I'm not aware of yet...

Even for small groups, comparing multiplication tables would be a very
inefficient way of testing for isomorphism. If the groups both had order
n, then (assuming you knew which element was the identity), you would
have to test all (n-1)! permutations of the rows and columns of one table
against the other. This would become impractical as soon as n was bigger than
about 12, I should think. I don't think you should consider using group
multiplication tables for any serious computation in group theory - they
are really only useful for display purposes!

A better approach to the problem you mention is as follows. Suppose you
are given a finitely presented group G and a permutation group P, say and
you know that they both have order n. Let G have generators x_1,..,x_r,
and relators r_1, ..., r_s.
Then try each map of the generators of G onto P (there are n^r such maps).
For each such map, check to see if the images of the relators in P
evaluate to the identity. If so, the map is a homomorphism. Then check to
see if these images generate the whole of P. If so, it is an isomorphism.

In many interesting examples, r will be two, so there will only be n^2 maps
to consider, which is a lot less than (n-1)!.
There are various tricks to speed things up - like, if you have a relator,
such as x_1^2, then you need only consider images of x_1 which have order
2 in P. So, in your particular example, there would be one possible image for
b and two for a, which cuts down the search from 6^2 to 2. Of course taking
advantage of such things in general is more tricky to program, but it is
perfectly possible. It is doubtful whether there is any essentially
better method of testing for isomorphism than this, at least for general
groups. Testing for isomorphism between two permutation groups is not
easy - I think the best method there is to find a suitable presentation
of one of them, and then use the method I have outlined.

Derek Holt.

> < [top]