On Tue, May 18, 2010 at 12:28 AM, Robert Bradshaw < rober...@math.washington.edu> wrote:
> I full heartedly agree with the idea that permutation groups should be able > to act on more than just the set 1..n, using a dictionary to do the mapping > transparently to the user under the hood (and this is technically totally > feasible). I'm not as convinced that we should throw out the notion of fixed > points. For example, given Sn, n>2, I would not say all Z/2Z subgroups are > "transitive" but it sounds like you want it to. > > Good question. Your point aims at the notion that transitivity is not inherently an invariant of a group, but is a property of a specific representation. Yes, something such as a group generated by (100,101) should be considered transitive... while a group generated by (98,99)(100,101) as a single generator is clearly not transitive. They are both of course representations of Z/2Z. At present, Sage considers neither of these to be transitive. I also agree that we should not throw away the notion of fixed points. But, my argument is that fixed points of a permutation representation should be made explicit when defining the representation. So, a group generated by (2)(100,101) is not transitive while a group generated by (100,101) is. > Would it be sufficient to provide a method that, given a group, returns a > representation that keeps the permuted set names the same, but restricts the > domain to non-fixed points? > I do think this would be sufficient, yes. Keep in mind though that this should be easily restricted to subgroups and subrepresentations. Jason B Hill > > - Robert > > > On May 17, 2010, at 3:06 PM, Mike Hansen wrote: > > ---------- Forwarded message ---------- >> From: Jason B Hill <jason.b.h...@colorado.edu> >> Date: Mon, May 17, 2010 at 3:05 PM >> Subject: [sage-combinat-devel] permutation group perspectives >> To: sage-combinat-de...@googlegroups.com >> >> >> >> 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<sage-combinat-devel%2bunsubscr...@googlegroups.com> >> . >> For more options, visit this group at >> http://groups.google.com/group/sage-combinat-devel?hl=en. >> >> -- >> To post to this group, send an email to sage-devel@googlegroups.com >> To unsubscribe from this group, send an email to >> sage-devel+unsubscr...@googlegroups.com<sage-devel%2bunsubscr...@googlegroups.com> >> For more options, visit this group at >> http://groups.google.com/group/sage-devel >> URL: http://www.sagemath.org >> > > -- To post to this group, send an email to sage-devel@googlegroups.com To unsubscribe from this group, send an email to sage-devel+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-devel URL: http://www.sagemath.org
