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