

Subject:
Using GAP for Computational Group Theory
Category: Science > Math Asked by: rndgroupga List Price: $35.00 
Posted:
27 Nov 2004 06:16 PST
Expires: 27 Dec 2004 06:16 PST Question ID: 434708 
This question involves Group Theory and GAP (http://www.gapsystem.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.gapsystem.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.  
 
 
 
 
 
 
 
 
 
 


Subject:
Re: Using GAP for Computational Group Theory
Answered By: mathtalkga on 27 Dec 2004 05:55 PST 
Hi, rndgroupga: 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 booleanvalued (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, mathtalkga 

Subject:
Re: Using GAP for Computational Group Theory
From: mathtalkga on 06 Dec 2004 21:08 PST 
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, mathtalkga 
Subject:
Re: Using GAP for Computational Group Theory
From: mathtalkga on 08 Dec 2004 06:05 PST 
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, mathtalkga 
Subject:
Re: Using GAP for Computational Group Theory
From: rndgroupga on 16 Dec 2004 01:31 PST 
List Price is changed, hope I can get the answer as soon as possible. Thanks Mathstalk! 
Subject:
Re: Using GAP for Computational Group Theory
From: mathtalkga on 21 Dec 2004 10:41 PST 
Hi, rndgroupga: 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.gapsystem.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, mathtalkga 
Subject:
Re: Using GAP for Computational Group Theory
From: rndgroupga on 23 Dec 2004 08:04 PST 
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? 
If you feel that you have found inappropriate content, please let us know by emailing us at answerssupport@google.com with the question ID listed above. Thank you. 
Search Google Answers for 
Google Home  Answers FAQ  Terms of Service  Privacy Policy 