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.
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?
- 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.
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
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
