From: mareg@csv.warwick.ac.uk (Dr D F Holt)
Newsgroups: sci.math,comp.theory
Subject: Re: permutation groups
Date: 10 Oct 1995 09:58:33 +0100

In article <45beuu$d06@firewall.isscad.com>,
	glipton@abu.isscad.com (Gary Lipton) writes:
>Given the generators of a permutation group, is there an
>algorithm for determining if a given permutation is a member
>of the group?
>-- 
>Gary Lipton
>Integrated Silicon Systems, RTP, NC


Yes - there is quite a lot of literature on such algorithms. The basic
algorithm is known as the Schreier-Sims algorithm and dates from the
late 60's. It first calculates  what is known as a base and strong
generating set for the permutation group (which tells you the order of
the group) - this enables you to solve the membership problem easily.
It formed the basis of Sims' construction by computer of
some of the large sporadic simple groups. To learn about it, I would
suggest the book "Fundamental Algorithms for Permutation Groups", by
G. Butler, Springer Lecture Notes in Computer Science, Vol. 559.
It has complexity about O(n^5) (where n is the permutation degree) in
its straightforward form, which is fine for  n  up to a few hundred, but
can get painfully slow for larger  n.

There have been various improvements since, some of which are Monte-Carlo
algorithms (i.e. the answer has a small and precisely estimatable (?) 
probability of giving the wrong answer (which would mean saying the
element was not in the group when it really was)). I don't have a list
of references to hand - you could start by looking in some of the
papers in the Dimacs conference proceedings "Groups and Computation", ed.
by L. Finkelstein and W.M. Kantor (AMS).  

You can access good implementations of these algorithms via one of the
group theory packages GAP and MAGMA. GAP inlcudes the Monte-Carlo
algorithms which are most useful if you already know something about the
group - for example if you already know its order, then it becomes
deterministic. I believe MAGMA has the fastest deterministic algorithms,
which will usually  work in a reasonable time (i.e. a few hours perhaps)
for degrees in the millions.
There is some sort of verion of the Schreier-Sims available in
Maple (and possibly Mathematica too) but when I tried it a few years ago
I found it painfully slow.
I don't recommend trying to program it yourself.

Derek Holt.

==============================================================================

Newsgroups: comp.theory,sci.math
From: "Paul Purdom" <pwp@cs.indiana.edu>
Subject: Re: permutation groups
Date: Tue, 10 Oct 1995 20:54:25 -0500

glipton@abu.isscad.com (Gary Lipton) writes:

>Given the generators of a permutation group, is there an
>algorithm for determining if a given permutation is a member
>of the group?

Mark Jerrum has a paper on how to do this in time n^5. That time has been
improved in later papers.

The problem is very interesting, as shown by the popularity of Rubic's cube
(where the problem is to find the permutation to get you back to the starting
position).