This question involves Group Theory and GAP (http://www.gap-system.org/)

We know that the equation - phi * pi * inverse of g = identity

And now, we wish to find the pi, which is the permutation for achieving the target?

If we apply GAP to a pack of cards,
for example we have 5 cards

Our input is 1,2,3,4,5
Target is 2,4,3,5,1

For example provided that we have 
Permutation A, B, C

By using GAP (http://www.gap-system.org/)
(1)Can we achieve the target by A, B, C?
(2)And...how to achieve the target by A, B, C? (E.g. maybe (pi_A)(pi_B)?? )
(3)How to achieve and how many times will the pack of cards back to "identity"?

Thanks a lot.
I am new to GAP and hope somebody can explain to me by some examples
to solve my problem.

---

Request for Question Clarification by mathtalk-ga on 01 Dec 2004 10:08 PST

Hi, rndgroup-ga:

I'm somewhat familiar with GAP, but I can't follow what you are
asking.  Please explain what phi, pi, and g (a group homomorphism?)
refer to.  This notation should perhaps be connected to the example
that you ask about, e.g. what do you mean by input, target, and
permutations A,B,C?  Are you looking for a recipe to solve a
particular kind of problem with GAP, or are you looking for more
general tutorial materials on GAP?

regards, mathtalk-ga

---

Clarification of Question by rndgroup-ga on 02 Dec 2004 10:30 PST

Suppose we fix a symmetric group, say S_{n}.
Take some fixed elements in S_{n}, say pi_{1}, pi_{2} and pi_{3}.
Given any element in S_{n}, call it phi.

We wish to use GAP to determine the following:

(1). Can I express phi as a product of pi_{1}, pi_{2} and pi_{3}?
      In other words, is phi in the subgroup generated by pi_{1},
pi_{2} and pi_{3}?

(2). If yes, how can I write phi as a product of pi_{1}, pi_{2} and pi_{3}?

(3). Except GAP, is Maple/Mathematica a better choice to handle this issue?

Many thanks mathtalk. Please, please help asap.

---

Clarification of Question by rndgroup-ga on 06 Dec 2004 18:31 PST

Mathtalk are you happy with my classification?
Thanks

---

Request for Question Clarification by mathtalk-ga on 06 Dec 2004 19:42 PST

Hi, rndgroup-ga:

Your clarification is very helpful.  I believe it would be fair to
call this a "word" problem in the sense of abstract group theory, and
I believe GAP is a promising tool to tackle it.  However I don't yet
have an Answer to give you!

I'll be happy to keep you updated on my progress through Comments.

regards, mathtalk-ga

---

Request for Question Clarification by mathtalk-ga on 08 Dec 2004 18:18 PST

Hi, rndgroup-ga:

I think I've worked out an Answer for you.  For the sake of
illustration, would you care to pose a specific problem?  It could
involve a deck of cards, I suppose, but perhaps a somewhat smaller
number of objects (eg. one suit of the deck, or anything involving
maybe 10 to 20 items) would be more satisfactory from the standpoint
of reading the details.

regards, mathtalk-ga

---

Clarification of Question by rndgroup-ga on 10 Dec 2004 02:52 PST

Suppose we are in S30

A = (1 2 4 15 20)(3 9 8 7 22)
B = (2 4 3)(7 9 8)(30 29 28)

pi= (7 4 25 6 8 9 16 20 1 5 29 30 17 2 3)

Write pi in terms of A and B

I would be greatly appreciated if you are able to find the minimal
"length" in terms of the generators

---

Request for Question Clarification by mathtalk-ga on 10 Dec 2004 03:28 PST

According to the online interface I posted below to a GAP4 based
calculator, your permutation pi, a cycle of length 15, is not
generated by A,B.

Was there a reason you expected it could be so generated?

With regard to finding the minimal length representation, this would
definitely increase the difficulty of the Question.

regards, mathtalk-ga

---

Request for Question Clarification by mathtalk-ga on 10 Dec 2004 13:00 PST

I should add that the special case of two generators (which your
example illustrates) is easier to address with respect to finding a
minimal length representation than the general case (of N generators).

regards, mathtalk-ga

---

Clarification of Question by rndgroup-ga on 16 Dec 2004 01:29 PST

Dear Mathtalk,

The answer is impressive, this is just an "example" by my rough random
guessing :). If you have better examples please feel free to post
here.

Please tell me the method not just the answer, step-by-step with
explainations, how to achieve cycle length 15?

Looking forward for your investigation especially in finding min
length. I understand the the difficulty and I am sure your effort will
not be forgotten.

Many thanks indeed.

---

Request for Question Clarification by mathtalk-ga on 20 Dec 2004 16:29 PST

Hi, rndgroup-ga:

I'll be running GAP under Windows XP in preparing an Answer for you. 
Is this the same platform you are using?  Because the command line
interface is fairly consistent, I don't think this would be a major
source of confusion, but if it would be helpful I can interpolate some
stuff about differing setups.

regards, mathtalk-ga

---

Clarification of Question by rndgroup-ga on 21 Dec 2004 06:36 PST

Yes I am running Windows XP, thanks!

Hi, rndgroup-ga:

I've illustrated the GAP commands below with a "standard" Windows XP
installation into C:\GAP4R4, and I'm simply running it from a standard
console window.  In the "bin" subdirectory, I run gap.bat.

Defining a permutation group
============================

GAP allows us to construct a group generated by permutations in an easy way.

The generators are just permutations, which we can write using "cycle"
notation.  For example, to use the generators you prescribed above:

A = (1 2 4 15 20)(3 9 8 7 22)
B = (2 4 3)(7 9 8)(30 29 28)

we want to write them in almost the same way, but adding commas to
separate the elements:

gap> pgrp := Group(
> (1, 2, 4, 15, 20)(3, 9, 8, 7, 22),
> (2, 4, 3)(7, 9, 8)(30, 29, 28) );

Note that assignment is done by the ":=" operator, that commas also
separate the generators, and that the command's completion is marked
with a semicolon.  The GAP system then prints the message:

Group([ (1,2,4,15,20)(3,9,8,7,22), (2,4,3)(7,9,8)(28,30,29) ])

that represents the evaluation of this command.

A quick test to see that GAP understands this new object as a group is
to ask for its size:

gap> Size( pgrp );
5443200

This is much smaller than 30! (the size of S_30), and it's easy to ask
GAP to factor it out for us:

gap> Collected( Factors( last ) );
[ [ 2, 7 ], [ 3, 5 ], [ 5, 2 ], [ 7, 1 ] ]

That is 5443200 = 2^7 * 3^5 * 5^2 * 7.  Of course that doesn't tell us
which group has been generated.  GAP4 has a command IdGroup that can
give more information about small groups (say up to order 2000), but
this group is too large for that.  Just out of curiousity, we can ask
if the group is abelian:

gap> IsAbelian( pgrp );
false

Attributes like IsAbelian that are boolean-valued (unlike Size, for
instance) are called Properties in GAP.  Here are a couple more:

gap> IsPermGroup( pgrp );
true
gap> IsSolvableGroup( pgrp );
false


Determine members of a group
============================

One way to test whether a permutation is in the group is to throw in
the additional generator and see if you get a strictly larger group or
not:

gap> qgrp := Group(
> (1, 2, 4, 15, 20)(3, 9, 8, 7, 22),
> (2, 4, 3)(7, 9, 8)(30, 29, 28),
> (7, 4, 25, 6, 8, 9, 16, 20, 1, 5, 29, 30, 17, 2, 3) );
Group([ (1,2,4,15,20)(3,9,8,7,22), (2,4,3)(7,9,8)(28,30,29),
  (1,5,29,30,17,2,3,7,4,25,6,8,9,16,20) ])
gap> Size( qgrp );
3201186852864000

As you can see, we've answered your "target" example in the negative
by showing that the cycle of length 15 that you picked would increase
the size of the generated group if we add it.

Representing a permutation with generators
==========================================

For the purpose of illustrating the task of representing a permutation
in terms of generators, let's let GAP pick a random group member for
us:

gap> r := Random( pgrp );
(1,9,4,3)(2,7,15)(20,22)

To obtain a representation of this permutation in terms of the
generators you gave, we first set up a homomorphism from the free
group on two generators to the permutation group pgrp we've been
working with, based on the assigned mapping of generators to
generators:

gap> f := FreeGroup("x","y");
<free group on the generators [ x, y ]>
gap> hom := GroupHomomorphismByImagesNC(f,prgp,GeneratorsOfGroup(f),
> GeneratorsOfGroup(prgp));
[ x, y ] -> [ (1,2,4,15,20)(3,9,8,7,22), (2,4,3)(7,9,8)(28,30,29) ]

Now hom is a group homomorphism that sends x to the first generator of
pgrp and y to the second generator.  We can then ask for a
representative of the preimage of group element r under the inverse
mapping:

gap> PreImagesRepresentative(hom,r);
x*y*x^-2*y^-1*x^-1*y^-1*x*y*x^-1*y^-1*x^-1*y^-1*x^-1*y*x^-1*y*x^-1*y*x^2*y*x^
-1*y*x^2*y*x^-2*y^-1*x^-1*y*x^-1*y^-1*x^-1*y^-1*x^2*y^-1*x^-1*y^-1*x^-2*y^
-1*x*y^-1*x^-1*y^-1*x*y^-1*x*y^-1*x*y^-1*x*y^-1*x*y^-1*x*y^-1*x

This last command took several seconds to complete, by far the longest
of the several we've issued in this session.

For further discussion...
=========================

As we kicked around the Question earlier, you raised many other
interesting points to pursue.  How can we get a minimal length
representation?  If the given cycle of length 15 is not generated by
the two given permutations, is there some other cycle of length 15
which is?  Or do we need different generators?

We can continue to discuss these issues, but I'm going ahead with
posting the Answer to at least those items you raised in the initial
post.

regards, mathtalk-ga

Part (1) of the Question can be done in GAP in a straightforward way.

I believe the trickiest part of the Question is (2) to find an
expression for the target element in terms of the given generators.

To find an expression that is of minimal "length" in terms of the
generators can be a very difficult problem.

regards, mathtalk-ga

Interested readers who don't wish to install the full GAP4 package may
find the following online calculator for permutation groups a partial
replacement:

[PermGroup -- Xiao Gang, based on GAP4]
http://wims.unice.fr/wims/en_tool~algebra~permgroup.en.phtml

It can determine if a specific set of permutations (generators) will
allow one to represent another permutation (target).  Enter the
generators using the last option on the first page (you may have to
hit the enter button twice, once to generate a session ID for the
calculator and once to do the calculation).  Then on the second page
enter the target permutation to "Examine".

For example, I entered as generators:

(1,2)
(1,2,3,4,5)

and the resulting permutation group is all of S_5, the symmetric group
on five points.  I then "examined" (3,5) and was told this is in the
subgroup generated (of course), but this calculator doesn't provide an
explicit representation, as far as I can tell.

regards, mathtalk-ga

List Price is changed, hope I can get the answer as soon as possible.
Thanks Mathstalk!

Hi, rndgroup-ga:

Sorry, I had not noticed this Comment about the urgency of an Answer!

I was posting to give a link which discusses a particular case of
finding a minimal length representation of permutations, when the
generators are a certain minimal subset of transpositions:

http://mail.gap-system.org/pipermail/forum/2004/000351.html

As that forum message notes, in general there is no better way than
"brute force", but even brute force can be intelligently applied.  If
the generated group is small enough to be exhaustively enumerated, say
of order no more than a few thousand, one can take a "dynamic
programming" approach.  Especially with the permutation groups
considered here, one can easily check when two "words" in the
generators agree (by comparing the results as permutations). 
Therefore one can start with the word of length 0 (group identity) and
recursively determine all group elements that can be expressed by
words of length 1, 2, etc. until the specific target permutation is
found.

Since your need for a quick Answer seems to outweigh having a thorough
exploration of the difficulties of minimal length representations
(which is indeed a hard problem in general; the number of possible
card deck shufflings at 52! is far too big for an exhaustive
enumeration), I'll set out for you the GAP4 commands that address your
original Question.  We can then discuss what further refinements are
important to you.

regards, mathtalk-ga

Thanks mathtalk.

Looking forward for your answer of commands, nevermind of shortest
path or not at this stage.

Remind-->Expires: 27 Dec 2004 06:16 PST
PS: Is it possible to extend it?