From: "A. Caranti"
Subject: Re: Question on Symmetric Groups
Date: Sun, 30 May 1999 11:51:45 +0200
Newsgroups: sci.math
Keywords: computational group theory, strong generating sets, Schreier-Sims
Lin Ziwei inquired:
> (1) How do we compute the order of subgroup G of the permutation group
> S_n, given its generators? When n is large, we cannot possibly enumerate
> the elements of the group.
>
> (2) How we determine if a particular permutation s is in G?
>
> (3) If the answer to (2) is yes, how do we express s as a product of
> the generators of G?
Schreier gave a constructive method that, given a finitely generated
group G and a subgroup H of finite index, allowed one to construct (a
finite number of) generators for the subgroup H. The original
Schreier-Sims algorithm by Sims uses Schreier's method to construct what
is called a strong generatimg set for a permutation group G. Here H is
first taken as a one-point stabilizer: one gets a transversal of H
(which are put in the strong generating set), and generators of H, and
repeats. This gives a reasonable solution for (1). Strong generating
sets also give a solution to (2), via a so-called sifting process. If s
is indeed in G, the method will express s in terms of the strong
generators, and in turn you can express these in terms of the original
generators, so you also get (3).
This is of course only a very rough sketch. You mentioned GAP: you can
learn quite a bit from GAP's inline help and bibliography - you'll also
see that nowadays there are very smart improvements on this method. If
you like, I can dig up some references on Monday.
Andreas
==============================================================================
From: mareg@lily.csv.warwick.ac.uk (Dr D F Holt)
Subject: Re: Question on Symmetric Groups
Date: 30 May 1999 15:28:47 GMT
Newsgroups: sci.math
In article <7iopm0$ccl$1@nuscc.nus.edu.sg>,
sci60065@leonis.nus.edu.sg (Lin Ziwei) writes:
>Hi! I've some queries here :
>
>(1) How do we compute the order of subgroup G of the permutation group
>S_n, given its generators? When n is large, we cannot possibly enumerate
>the elements of the group.
>
>(2) How we determine if a particular permutation s is in G?
>
>(3) If the answer to (2) is yes, how do we express s as a product of
>the generators of G?
>
>I know that there're efficient methods for performing (1) & (2)
>(demonstrated by the software package GAP). But what about (3)?
The basic algorithm for (1) and (2) is called the Schreier-Sims
Algorithm. You could try
G. Butler, "Fundamental algortihms for permutation groups",
Lecture Notes in Computer Science 559, Springer 1991
for background etc. There are also various improvements around for
small base groups of large degree.
(3) is generally difficult. The algorithm for (1) and (2) extends the
original generating set. It is easy to express s as a word in the new
generators. You could then write the new generators in terms of the old,
thereby getting s as a word in the old generators, but typically this
would be an absurdly long word.
If the group is not too large (say up to a million), then you could build
the Cayley graph of the group, and then you can derive the shortest word
in the generators for s very quickly.
Derek Holt.