[sage-devel] Centralizer for permutation groups gets wrong degree

[Rob Beezer]

Consider the following discovered in the course of debugging an IRC
query:

sage: G=SymmetricGroup(4)
sage: g=G("(1,2)")
sage: g in G.centralizer(g)
True

sage: G=SymmetricGroup(3)
sage: g=G("(1,2)")
sage: g in G.centralizer(g)
False

Explanation:
In the first case, (3,4) is in the centralizer and so
G.centralizer(g).degree() == 4.

In the second case, the centralizer is just {(), (1,2)} and so
G.centralizer(g).degree() == 2.

A workaround is g in G.centralizer(g).list() which seems to be
immune to this.

It looks like G.centralizer(g) gets generators from GAP and uses
those to build a new permutation group, independent of any notion of
where g came from (ie degree of its parent).

I imagine I can fix this one, but I'm posting here since I wonder if
this is a concrete example that ties into the current discussion about
symbols, fixed/unfixed elements, transitivity, etc for permutation
groups?
http://groups.google.com/group/sage-devel/browse_thread/thread/330ddca4c6ea06ca

Rob

--
To post to this group, send an email to sage-...@googlegroups.com
To unsubscribe from this group, send an email to sage-devel+...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/sage-devel
URL: http://www.sagemath.org

[Jason B Hill]

This is definitely an example of where Sage and GAP differ in their approaches, but this is more about subgroups/subactions... and there hasn't been much discussion on this topic yet.

GAP evaluates subgroups/subactions without regard for the degree of the original action. Thus, if you take your typical degree 4, primitive representation of S_4 on 4 integers, then any subgroup defined as a single point stabilizer of one of those integers will be a degree 3 group. (In Sage currently: If you start with the S_4 action on [1..4] then three of the point stabilizers are degree 4 and one of them is degree 3.)

GAP's approach at forgetting the degree of the original action feels counter-intuitive and it feels like the actions should sustain a notion of degree from the original group. I think this could be argued either way. The reason GAP does this is purely algorithmic, as many invariants of a particular permutation action (such as composition series, stabilizer chains, etc.) are formed by recursively reducing the degree of the action (through point stabilizers, homomorphisms into groups of smaller degree, etc.). It is also the only consistent way for GAP to determine if subactions are transitive, or primitive, or etc... and essentially GAP is only performing those determinations on a collection of non-fixed-points for the subactions.

Your example is confusing for other reasons though. Notice the following rewrite:

sage: G=SymmetricGroup(4)
sage: g=G("(1,2)")
sage: g in G.centralizer(g)
True

sage: H=SymmetricGroup(3)
sage: g in H.centralizer(g)
False

It is arguable that this last argument returns false for the wrong reason. The question then becomes how g=G("(1,2)") is in any way different than declaring g to be "the" transposition (1,2). Anyway... this is a different issue.

I think the design question here is in how Sage should treat the domain of subactions/subgroups. This is different than the original question of the domain of actions themselves, but obviously highly related and should probably be answered at the same time. Essentially, what I am saying is that I think Sage should be compatible with GAP as much as possible in terms of the notion of the degree of a permutation group. But, when it comes to subgroups, GAP fails to recognize that the structure in question is indeed a subgroup (It applies methods consistently and naively). If there is enough demand to have this notion of subgroup as an extra structural component for permutation groups in Sage, we would need to discuss how to implement such a thing.

Jason

[Rob Beezer]

Hi Jason,

Thanks for your comments. I was mulling some commentary on your
previous post about permutation groups, but my comments are just
applicable in this case, so here goes.

My main interest in Sage is its use in my teaching. GAP is a perfect
example. I've always felt that the syntax and learning curve for GAP
would require about 7 or 8 weeks to get my undergraduate students to a
productive state (though I never ran that experiment in a careful
way). In contrast, Sage takes about 3 weeks or less to get through
all the logistical, syntactical and other gotchas before I can
concentrate totally on having the students explore new ideas (I've run
this experiment twice). And of course, then in subsequent courses the
startup time is nearly zero (in contrast, to say, learning Singular or
PARI from scratch).

A real strength of the Sage community is that there is little tension
between supporting clean intuitive syntax for beginners and providing
powerful routines for experts. So my point-of-view is that Sage
should harness the power (speed, maturity, breadth) of GAP in a way
that is easy for beginners and experts alike. And if it fails the
experts, there is always the direct interface to GAP itself to fall
back on.

In the specific case of the centralizer, I've looked briefly at the
code, and I would suggest the following adjustment. Instead of
returning a brand-new PermutationGroup object (current behavior), I
would return a subgroup of the original group. My argument: if a
textbook has the following definition for a centralizer

C(g)={h\in G | .....}

then it would be best if Sage would return a subgroup of G, carrying
that much more information. I haven't checked, but I would think it
would be easy to convert the centralizer to a group of its own
(discard the subgroup information) and even slim down its degree. But
I'd rather have that information preserved for the beginner, than have
it obscured, or hard to resurrect.

In terms of the broader discussion, it would be great if the symbol
set for a permutation group could be anything (hashable), with
dictionary translation between GAP's integers of 1..n. I belive this
was Dima's short reaction. As one example where this would be a huge
improvement, default vertex labeling for graphs begins at 0, so a
computed automorphism group has the 0-vertex translated to the n-
integer in the permutations. Very confusing, even when you expect it
and understand why.

[Dima Pasechnik]

GAP subgroups know its parent, which in the case of permutation groups
amount to knowing the domain of action.
Sage ought to follow the suit, IMHO

> >http://groups.google.com/group/sage-devel/browse_thread/thread/330ddc...

>
> > Rob
>
> > --
> > To post to this group, send an email to sage-...@googlegroups.com
> > To unsubscribe from this group, send an email to

> > sage-devel+...@googlegroups.com<sage-devel%2Bunsubscribe@googlegrou ps.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-...@googlegroups.com
> To unsubscribe from this group, send an email to sage-devel+...@googlegroups.com

> For more options, visit this group athttp://groups.google.com/group/sage-devel