At 12:22 PM 12/26/03, chiachichang1123@yahoo.com.tw wrote:

generators: s1=(57)(68) s2=(56)(78) s3=(34) s4=(37)(48) s5=(26)(48) s6=(24)(68) s7=(78) s8=(68) s9=(48) S={si : i=1~9}

<S> means a permutation group generate by S

give a=(2345678)

(1) is a in <S>???

Yes; in fact, <S> is the full symmetric group on {2,3,4,5,6,7,8}.

(2) a=??

a = s9*s2*s1*s6*s3. I found the answers to these questions using GAP, available from http://www.gap-system.org/ , which describes it as "a free system for computational discrete algebra". GAP stands for "Groups, Algorithms and Programming". Here's a transcript of the GAP session, with commentary added. First, enter the generators: gap> s1 := (5,7)(6,8); # GAP has a built-in syntax for permutations (5,7)(6,8) gap> s2 := (5,6)(7,8);; # the double semicolon suppresses the response gap> s3 := (3,4);; gap> s4 := (3,7)(4,8);; gap> s5 := (2,6)(4,8);; gap> s6 := (2,4)(6,8);; gap> s7 := (7,8);; gap> s8 := (6,8);; gap> s9 := (4,8);; Create the group they generate: gap> g := Group(s1,s2,s3,s4,s5,s6,s7,s8,s9); Group([ (5,7)(6,8), (5,6)(7,8), (3,4), (3,7)(4,8), (2,6)(4,8), (2,4)(6,8), (7,8), (6,8), (4,8) ]) The order of g is 7!, so it is the full symmetric group on 2,3,...,8. gap> Order(g); 5040 Use the technique of section 37.5 of the reference manual to express a given permutation in terms of the generators. First, create a free group with the same number of generators (and give them the same names): gap> f := FreeGroup("s1","s2","s3","s4","s5","s6","s7","s8","s9"); <free group on the generators [ s1, s2, s3, s4, s5, s6, s7, s8, s9 ]> Create the homomorphism that maps f's generators onto g's ("NC" means "no check"; it promises that this will be possible so GAP needn't check): gap> hom := GroupHomomorphismByImagesNC(f,g,GeneratorsOfGroup(f),GeneratorsOfGroup(g)); [ s1, s2, s3, s4, s5, s6, s7, s8, s9 ] -> [ (5,7)(6,8), (5,6)(7,8), (3,4), (3,7)(4,8), (2,6)(4,8), (2,4)(6,8), (7,8), (6,8), (4,8) ] Find the answer we want: gap> PreImagesRepresentative(hom, (2,3,4,5,6,7,8)); s9^-1*s2^-1*s1^-1*s6^-1*s3^-1 A quirk in the algorithm has expressed the result in terms of inverses of the generators, even though they all have order two. Check the answer, skipping the inverses: gap> s9*s2*s1*s6*s3; (2,3,4,5,6,7,8) Note that GAP composes permutations from left to right; if you prefer right-to-left, your answer would be s3*s6*s1*s2*s9. The GAP reference manual includes an extensive bibliography. -- Fred W. Helenius <fredh@ix.netcom.com>

At 01:22 AM 12/27/03 +0800, =?big5?q?=B1i=AEa=BB=F4?= wrote:

Is there an algorithm to distinguish whether p in <S>??

Yes, there is. I forget its name, but I learned it back when Rubik's Cube was first popular. The algorithm works by filling up a triangular table with sequences of generators ("words") whose products have desired properties. In the first row, the first word will carry 1 to 2 (and we don't care what it does to any of the other elements). The next word carries 1 to 3, the next 1 to 4, and so on. So the first row of the table tells you how to move 1 to any desired place. The second row of the table tells you how to move 2 to any desired place, while leaving 1 in place. The first word has the property 1->1, 2->3. The next word: 1->1, 2->4. And so on. The third row tells how to move 3 while fixing 1 and 2. The fourth row tells how to move 4 while fixing 1, 2, and 3. And so on, until the last row tells how to fix 1, 2, ..., and exchange (n-1) and n. Now, when we begin, we do not know how to do any of these things: the table is empty. We consider the first generator, S1. Now, it MUST belong in one of the places of the table. If it moves 1, it belongs in the first row, and we put it in the correct place depending on where it moves 1 to. If it doesn't move 1, it might move 2, in which case it belongs in the second row. And so on. So we put S1 in its proper place. Similarly, we place each generator in the correct place in the table, and also all the inverse generators. While we are doing this, we might encounter a situation where the correct place in the table is filled already. For example, two of the generators might move 1 to 4. When this happens, multiply the word that is already in the table by the inverse of the one we are trying to place; this will produce a word that keeps 1 fixed. Find the right place in the table for this new word. Every time we try to put a word B in a position already occupied by A, give up on B and place AB' instead. Eventually, you will either find a place for the accumulated word, or you will discover a new relation. After all the generators and their inverses have been placed, begin working on words made of two generators, and so on. Eventually you will reach a stage where every attempt to add an new word to the table produces a known relation (you will be able to prove this). Then all the empty places in the table are empty because no sequence of generators has the desired property. The table is a recipe for achieving any achievable permutation. You can use the inverses of words in the first row to position 1; then the second row lets you bring things to position 2 without disturbing 1; and so on. -A