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.