This comes after a discussion I had with several at Sage days 20.5 in Toronto relating to the underlying structure of permutation representations in Sage. Sorry for the length, but it does completely express the situation.
I'll start by saying that I'm relatively new to Sage development (I'm from the lands of GAP and C), but I do have some time and desire to contribute in this area, depending on what results from this discussion. I've also posted a ticket (#8929) on trac.sagemath.org that adds some minimal functionality along these lines to the permutation group methods in permgroup.py. Here's my basic issue: Sage constructs permutation groups in a very intuitive, but arguably less robust and less mathematically consistent way when compared to GAP. I want to explain these differences, to explain why Sage's current perspective makes conducting my research in Sage very challenging, and also to explain how the two perspectives may potentially be brought together to add more functionality to permutation group methods in Sage than currently exist in either Sage or GAP. Here's an example of the same permutation group (really, a permutation representation or action) in Sage and in GAP: sage: G=PermutationGroup([[(2,3,4,5,6,7,8)]]) gap> G:=Group([(2,3,4,5,6,7,8)]); To illustrate the differences between Sage and GAP, we can consider transitivity: sage: G.is_transitive() False gap> IsTransitive(G); true This difference is caused by GAP understanding G to be a permutation representation acting on [2 ... 8], while Sage understands the action to be on the set [1 ... 8], where 1 is in the domain of the action and is simultaneously never moved by this specific representation. Sage determines the degree of a permutation group to be the largest integer moved by any of the generators. GAP considers the degree of a permutation group to be the number of non-fixed points of the representation. Hence, any notion of transitivity, regularity, primitivity, etc. will be considerably different between GAP and Sage. In fact, Sage currently has no is_primitive method, and I don't think it is possible to implement such a method consistently given Sage's current implementation of G.degree(). In our above example, GAP does rightly think that G is primitive. However, in Sage, not only do we have a block system / equivalence relation on the domain (composed on blocks having different sizes, that's bad), but the representation of G is not even transitive. Note about the ticket mentioned above: I have rewritten is_transitive() and allowed for optional arguments in the form of integers (in which case [1 .. input] is the domain) or lists of integers (in which case the list is the domain). In the patch is also a method for determining fixed and non-fixed points as a list, which may then be used for transitivity, regularity and primitivity calculations. Sage's approach is very intuitive. If I input a single generator [(100,101)], then my permutation group is isomorphic to Z_2 and acts on [1 ... 101]. Unfortunately, I think this approach has more pitfalls than bonuses. While it does mimic a human's permutation group intuition, it removes a naive algorithmic understanding that makes more in-depth calculations (those beyond a normal person's intuition) run cleanly. Here's a simple example that is easy for intuition to handle: sage: H=PermutationGroup([[(1,2,3,4)],[(5,6,7)]]) sage: S=H.stabilizer(2) sage: S.degree() 7 Here's one that isn't so intuitive: Randomly number the edges and vertices of the unit cube. Define the rotational group of this cube in terms of permutation generators. Rotational actions are clearly not transitive on this collection of objects (it is a degree 20 representation of S_4), so pick the smallest orbit and define a homomorphism (actually, an isomorphism) from your original group to an action on this single orbit (vertices only). This new action is transitive, but not primitive. So, do the same thing and create a homomorphism (again, isomorphism) to an action on a block system. Now, tell me the degree of this new action (it should be 4), the socle of the corresponding group (it is affine, this calculation is easy if you can compute a point stabilizer complement in the final action), and then compute the EARNS of my original group as a lift back through my isomorphisms from this socle. Once you abstract a permutation group beyond an intuitive level, Sage loses its ability to calculate these properties and invariants. In GAP, this calculation is relatively painless. My goal here is to spark a conversation about what can be done in this situation. I would love to have Sage more in-line with GAP's understanding of the underlying structure of permutation actions. And, I'm not sure that much has to be done to make this happen. I'm not an expert in python, but I'm wondering if a dictionary could be used to translate the non-fixed points of Sage's permutation group generators to a compacted list of integers [1 ... degree] on which the current methods could be run. This may have the added benefit of being able to define permutation actions in Sage on more than integers. (I.e., one could define a permutation action on arbitrary strings such as 'jane' and 'red'.) That would be a huge bonus over current implementations in Sage or GAP. Once the methods are run, then the dictionary could translate back and output results in the original generator language. If singleton/trivial placeholders are desired as generators in permutation actions, then entering them as [(2)] or [(joe)] should be acceptable as input as a generator. For now, I would appreciate input on this and also the patch I submitted to introduce some of these capabilities in Sage's current implementation of permutation groups. Brevity is a virtue I do not have. Sorry about that. Jason B. Hill -- You received this message because you are subscribed to the Google Groups "sage-combinat-devel" group. To post to this group, send email to sage-combinat-de...@googlegroups.com. To unsubscribe from this group, send email to sage-combinat-devel+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/sage-combinat-devel?hl=en.
