Checking whether a list of Permutations form a Group

Question

I am new to Group Theory and GAP as well. I am given a list of Permutations say

gap> a:=[(1,2), ()]

How can i check whether these permutations form a Group themselves. Apart from the obvious method of, checking equality of Group list generated by a and list a

gap> AsList(Group(a))=a ?

Answer 1

Maybe you could try

G:=Group([(1,2),()]);

G is the group generated by the permutations (1,2) and ().

Answer 2

So the question is how to check that a list of permutations forms a group under the standard multiplication of permutations. We don't have to check associativity, but we have to check whether the identity permutation is there, and whether it is closed with respect of multiplication and taking inverses.

This is a nice question, which leads to interesting programming exercises and exposes some misconceptions.

First of all, even the approach suggested in the question does not work:

gap> a:=[(1,2), ()];
[ (1,2), () ]
gap> AsList(Group(a))=a;
false

This happens because GAP compares two unsorted lists, and they contain same elements but in different order:

gap> AsList(Group(a));a;
[ (), (1,2) ]
[ (1,2), () ]

If you want to check that they are equal as sets, use IsEqualSet instead:

gap> IsEqualSet(AsList(Group(a)),a);
true

This however will be very inefficient for larger examples, since it will create a list of all elements of potentially much larger group. It may help to turn a into a sorted list (e.g. using Set ). After that one could even use Group(a)=a:

gap> a:=[(1,2), ()];
[ (1,2), () ]
gap> a:=Set(a);
[ (), (1,2) ]
gap> Group(a)=a;
true

For larger groups, this would work fast in the list does not form a group, but may be still slower in the case when it is actually a list of all elements of a group. Two ideas that one could explore and compare are:

1. Instead of comparing sets, compare their orders with

Size(Group(a))=Length(a)

2. Write own code which takes a sorted list, first checks whether the identity permutation is there, whether it is closed with respect of taking inverses and with respect to multiplication. Because the list is sorted, lookup in the list will be fast.

However, both of them may be impractical for very large groups.