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" 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).