View Question
Q: Using GAP for Computational Group Theory ( Answered,   5 Comments )
 Question
 Subject: Using GAP for Computational Group Theory Category: Science > Math Asked by: rndgroup-ga 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.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!`
 Subject: Re: Using GAP for Computational Group Theory Answered By: mathtalk-ga on 27 Dec 2004 05:55 PST
 ```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"); 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```
 Subject: Re: Using GAP for Computational Group Theory From: mathtalk-ga 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, mathtalk-ga```
 Subject: Re: Using GAP for Computational Group Theory From: mathtalk-ga 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, mathtalk-ga```
 Subject: Re: Using GAP for Computational Group Theory From: rndgroup-ga 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: mathtalk-ga on 21 Dec 2004 10:41 PST
 ```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```
 Subject: Re: Using GAP for Computational Group Theory From: rndgroup-ga 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?```