> < ^ From:

> < ^ Subject:

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]