[sage-devel] Fwd: [sage-combinat-devel] permutation group perspectives

[Mike Hansen]

---------- Forwarded message ----------
From: Jason B Hill <Jason....@colorado.edu>
Date: Mon, May 17, 2010 at 3:05 PM
Subject: [sage-combinat-devel] permutation group perspectives
To: sage-comb...@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-comb...@googlegroups.com.
To unsubscribe from this group, send email to
sage-combinat-d...@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-...@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

[Robert Bradshaw]

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

[Jason B Hill]

On Tue, May 18, 2010 at 12:28 AM, Robert Bradshaw <robe...@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
 

[Dan Christensen]

Most of this discussion is about cases where sage thinks it is acting on
a bigger set than the user wants it to. I'll just point out bug 8963

http://trac.sagemath.org/sage_trac/ticket/8963

where sage has the reverse problem: it thinks that the set that is
being acted on is smaller. For example, it correctly computes that
the row stabilizer group of the tableau [[1,2],[3]] is a group with
two elements generated by the transposition (1,2), but it thinks that
this group is acting on the set {1, 2} rather than the set {1, 2, 3},
and this leads to difficulties.

That bug has a patch that fixes this particular problem, but enhancing
sage to know about the set that a permutation group acts on sounds like
a good idea.

Dan

[Rob Beezer]

There's a problem with centralizers of permutation groups that sounds
like either (a) it is related, or (b) might not have happened if there
had been more care about just waht the symbol set was for a
permutation group. I posted it separately so it would be easy to find
in the archives, and thinking it might need some discussion before
being fixed.

http://groups.google.com/group/sage-devel/browse_thread/thread/8ad38a7c295af481

Rob

[Dima Pasechnik]

Indeed, somehow people who wrote the permutation groups code in Sage
kept forgetting that
a permutation group is a pair (G,X), where G is a group and X is a
set, on which G acts.
Once you think that you can get away with permutations alone, you are
doomed...
(same would apply to any group actions, not only to permutation ones;
e.g. if you have a linear group, don't even try to forget which
vectorspace it operates on)

Sorry for sounding like a grumpy algebra professor :-)
Dima

> For more options, visit this group athttp://groups.google.com/group/sage-devel
> URL:http://www.sagemath.org

[William Stein]

Let's rewrite:

* abelian groups
* permutations groups
* piecewise functions
* Sage's riemann_roch_basis command (wrapping Brill-Noether)...

William

--
William Stein
Professor of Mathematics
University of Washington
http://wstein.org

[Rob Beezer]

Abelian groups is second on my list (right after graphs + latex), but
as I've been told, "many have failed here." So I'd get out of the way
(or help) if anybody else is interested.

And I have a vested interest in permutation groups......

Rob

> William Stein
> Professor of Mathematics

> University of Washingtonhttp://wstein.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

[kcrisman]

On May 20, 4:33 pm, Rob Beezer <goo...@beezer.cotse.net> wrote:
> Abelian groups is second on my list (right after graphs + latex), but
> as I've been told, "many have failed here."  So I'd get out of the way
> (or help) if anybody else is interested.
>
> And I have a vested interest in permutation groups......
>
> Rob
>
> On May 20, 1:18 pm, William Stein <wst...@gmail.com> wrote:
>
>
>
> > Let's rewrite:
>
> >   * abelian groups
> >   * permutations groups
> >   * piecewise functions

It would be really good to find a way to get some of the stakeholders
together on this last one (wdj, Burcin, others?) to put together a
framework on this so that grunts like me could fill in some of the
boring details afterward. Is there a Sage Days in the next six-twelve
months which could have this as one of the (funded) topics?

- kcrisman

[kcrisman]

On May 20, 5:13 pm, kcrisman <kcris...@gmail.com> wrote:
> On May 20, 4:33 pm, Rob Beezer <goo...@beezer.cotse.net> wrote:
>
>
>
> > Abelian groups is second on my list (right after graphs + latex), but
> > as I've been told, "many have failed here."  So I'd get out of the way
> > (or help) if anybody else is interested.
>
> > And I have a vested interest in permutation groups......
>
> > Rob
>
> > On May 20, 1:18 pm, William Stein <wst...@gmail.com> wrote:
>
> > > Let's rewrite:
>
> > >   * abelian groups
> > >   * permutations groups
> > >   * piecewise functions
>
> It would be really good to find a way to get some of the stakeholders
> together on this last one (wdj, Burcin, others?) to put together a
> framework on this so that grunts like me could fill in some of the
> boring details afterward.  Is there a Sage Days in the next six-twelve
> months which could have this as one of the (funded) topics?
>
> - kcrisman

Sorry for the OT post, by the way.

[Jason B Hill]

On Thu, May 20, 2010 at 2:33 PM, Rob Beezer <goo...@beezer.cotse.net> wrote:

Abelian groups is second on my list (right after graphs + latex), but
as I've been told, "many have failed here."  So I'd get out of the way
(or help) if anybody else is interested.

And I have a vested interest in permutation groups......

Rob

Can we get a list together of all of those who may be interested in contributing to the rewrite of permutation groups on some level? We can move to an in-depth discussion and inventory. I don't want to flood the sage-devel list with too much, unless there are those who think the discussion should remain here.

I'm currently on vacation, until just after Memorial Day, and so I have limited time to respond until then. Otherwise, I'd personally like to coordinate and work on this during the summer months, as when courses start in the fall my time for this won't be as great. (I'm guessing that is true for others, depending on your locations.) Let me know if you think that schedule, i.e., late August, is too ambitious. If you think it is too far down the line, then you may care to remember Hofstadter's Law:

http://en.wikipedia.org/wiki/Hofstadter's_law

We could also save the work for a Sage Days and do this in person if there is insistence on that.

Rob: I think your experience using the permgroup methods in your teaching can be used a lot for building usability in that area. I know some others in your situation who are not on the sage-devel list and I will see if they are interested in helping from the non-developer perspective. Myself... I'm most interested in building a concrete permutation group structure that allows for more advanced computations and research. From what I've heard in the centralizer, subgroup and tableaux discussions, I think our fundamental needs are relatively the same.


Jason B. Hill

[Rob Beezer]

Hi Jason,

That all sounds great, I am available for a summertime push on
permutation groups as it will fit nicely with some other plans I have.

Over on the centralizer thread, I think David Joyner volunteered me as
"leader." I don't think I want to go that far, in particular because
I don't know GAP that well. ;-) But I would like to contribute and
especially from my viewpoint as a consumer in the classroom.

Yes, we can avoid flooding sage-devel, though we should post updates
as discussions consolidate and tickets appear. And we could move over
to sage-algebra and breathe some life into that group before it gets
killed as part of a Google-Group-non-proliferation treaty.

Besides the usual suspects (who I hope are interested as well, you
know who you are!), Mike O'Sullivan and his students at San Diego
State might also be interested.

Rob

[Dima Pasechnik]

please keep me in the loop.
Thanks,
Dima

> For more options, visit this group athttp://groups.google.com/group/sage-devel
> URL:http://www.sagemath.org

[Mike OS]

>
> Besides the usual suspects (who I hope are interested as well, you
> know who you are!), Mike O'Sullivan and his students at San Diego
> State might also be interested.
>
> Rob

Yes, indeed, we are very interested. Our primary interest is
classroom use, rather
than research. Some of the of the things I would like to do:
have various types of groups be integrated better e.g.
unit groups of rings, matrix groups, permutation groups, abelian
groups;
be able to construct homomorphisms between them;
construct direct products, construct a group via generators and
relations
compute cosets and conjugacy classes.

Well, I am still a novice, so I'm not sure what can be done in Sage,
what needs directly calling
gap, and what all is involved in fulfilling this wish list.

Mike

[Mike Hansen]

On Fri, May 21, 2010 at 5:58 PM, Jason B Hill <Jason....@colorado.edu> wrote:
> Can we get a list together of all of those who may be interested in
> contributing to the rewrite of permutation groups on some level? We can move
> to an in-depth discussion and inventory. I don't want to flood the
> sage-devel list with too much, unless there are those who think the
> discussion should remain here.

I've been working on this over the next few days, cleaning up the
code, and making permutation groups act over an "arbitrary" domain.
I'll be posting these in the next few days.

--Mike

[Jason B Hill]

Sweet!

I'm assuming you're using a dictionary map? I think this could kill two birds with one stone. If we want to make Sage act more like GAP and consider the domain of a permutation group to be the collection of non-fixed points (I think we should consider subgroups separately), then even in the case when the generators contain integers, those integers could be dictionaried (I think that's a word) into a compacted list of integers. In that situation, 99% of the existing methods could be used.

I have some things to add to the subgroup discussion from farther up, and I'll be back from vacation on Wednesday. Unfortunately, this will be my last computer access until then. :-(

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-comb...@googlegroups.com.
To unsubscribe from this group, send email to sage-combinat-d...@googlegroups.com.
For more options, visit this group at http://groups.google.com/group/sage-combinat-devel?hl=en.

[Rob Beezer]

On May 30, 2:46 pm, Mike Hansen <mhan...@gmail.com> wrote:
> I've been working on this over the next few days, cleaning up the
> code, and making permutation groups act over an "arbitrary" domain.
> I'll be posting these in the next few days.

Mike H - thanks for your work on this!

Mike O'S - that's a great wish list. I'd like to see lots of that
happen. Another item on my wish list is to build a quotient group and
have its elements (optionally) actually be cosets. Right now for
permutation groups you get back a new permutation group:

sage: D=DihedralGroup(7)
sage: H=D.subgroup([D((1,2,3,4,5,6,7))])
sage: Q=D.quotient(H)
sage: Q.list()
[(), (1,2)]

Maybe with a new "coset" class and Mike's arbitrary domains this would
be easy to implement?

I've brought this one up before. How do folks feel about having the
named permutation groups available like graphs are? In other words,
rather than each family of permutation groups being a new class, there
is a single system-wide object ("groups", or "perm_groups") whose
methods produce instances of permutation groups (or more generally,
just groups). So for example,

D=groups.DihedralGroup(7)

would replace the above syntax. Advantages - namespace is less
cluttered, and tab-completion (groups.<tab>) gives precise one-stop
shopping for examples of specific groups.

Rob

[Robert Bradshaw]

On May 30, 2010, at 3:33 PM, Jason B Hill wrote:

>
> Sweet!
>
> I'm assuming you're using a dictionary map? I think this could kill
> two birds with one stone. If we want to make Sage act more like GAP
> and consider the domain of a permutation group to be the collection
> of non-fixed points

To clarify, are you talking just about the case where a group it
constructed from a set of generators, or are you considering having
every construction figure out the set of fixed points and throw them
away? The former sounds fine, but I don't like the latter.

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

[Robert Bradshaw]

I'm +1 to a group object like this, but removing things from the top
level namespace is backwards incompatable and could break a lot of
code out there. As for classes vs. methods, one advantage of classes
is that sometimes certain methods can be simplified/optimized if you
know what specific group you have.

- Robert

[William Laffin]

>> I've brought this one up before.  How do folks feel about having the
>> named permutation groups available like graphs are?  In other words,
>> rather than each family of permutation groups being a new class, there
>> is a single system-wide object ("groups", or "perm_groups") whose
>> methods produce instances of permutation groups (or more generally,
>> just groups).  So for example,
>>
>> D=groups.DihedralGroup(7)
>>
>> would replace the above syntax.  Advantages - namespace is less
>> cluttered, and tab-completion (groups.<tab>) gives precise one-stop
>> shopping for examples of specific groups.
>
> I'm +1 to a group object like this, but removing things from the top level
> namespace is backwards incompatable and could break a lot of code out there.

What is wrong with using sage.misc.misc.deprecation?

> As for classes vs. methods, one advantage of classes is that sometimes
> certain methods can be simplified/optimized if you know what specific group
> you have.

I might be off on what you are trying to say, and I'm not fully pro
with gap but I believe depending class inheritance with group theory
is inherently too weak. Applicable methods installed into operations
that are dynamically chosen at runtime based on some fitness criteria
(what gap has) seems smarter than dynamic classes (operations chosen
by class hierarchy only). This applies specifically to group theory,
where there are many different ways to deal with groups, and some
properties are more important than others when dealing with different
functions.

http://www.gap-system.org/Manuals/doc/htm/tut/CHAP008.htm#SECT002

I might be a gap fan boy here, but having many attributes in a small
number of classes with many private functions that are called from
public ones seems more robust than an extremely large class hierarchy.

-bill

[Robert Bradshaw]

On May 31, 2010, at 3:06 PM, William Laffin wrote:

>>> I've brought this one up before. How do folks feel about having the
>>> named permutation groups available like graphs are? In other words,
>>> rather than each family of permutation groups being a new class,
>>> there
>>> is a single system-wide object ("groups", or "perm_groups") whose
>>> methods produce instances of permutation groups (or more generally,
>>> just groups). So for example,
>>>
>>> D=groups.DihedralGroup(7)
>>>
>>> would replace the above syntax. Advantages - namespace is less
>>> cluttered, and tab-completion (groups.<tab>) gives precise one-stop
>>> shopping for examples of specific groups.
>>
>> I'm +1 to a group object like this, but removing things from the
>> top level
>> namespace is backwards incompatable and could break a lot of code
>> out there.
>
> What is wrong with using sage.misc.misc.deprecation?

That doesn't prevent breaking people's code, just warns them about it.
Preserving backwards compatibility is hard enough as it is (especially
for people of upgrade infrequently, or if there are publications using
the old syntax) so I'm +1 to not adding new names to the global
namespace, but think there should be really good reasons before we go
an remove stuff.

>> As for classes vs. methods, one advantage of classes is that
>> sometimes
>> certain methods can be simplified/optimized if you know what
>> specific group
>> you have.
>
> I might be off on what you are trying to say, and I'm not fully pro
> with gap but I believe depending class inheritance with group theory
> is inherently too weak. Applicable methods installed into operations
> that are dynamically chosen at runtime based on some fitness criteria
> (what gap has) seems smarter than dynamic classes (operations chosen
> by class hierarchy only). This applies specifically to group theory,
> where there are many different ways to deal with groups, and some
> properties are more important than others when dealing with different
> functions.
>
> http://www.gap-system.org/Manuals/doc/htm/tut/CHAP008.htm#SECT002
>
> I might be a gap fan boy here, but having many attributes in a small
> number of classes with many private functions that are called from
> public ones seems more robust than an extremely large class hierarchy.

I'm not advocating an extremely large class hierarchy, just saying
that it may make sense in some cases to have actual classes (if only
to provide extremely quick fitness criteria tests, though some of that
could be done with attributes as well). I'll leave it to the experts,
like you, to actually design the system.

- Robert

[Jason B Hill]

Sorry, I was in the mountains for a bit and missed some conversation.

Mike H: Do you want any assistance in your current task?

Robert B: In response to your question after my last e-mail, assuming I understand it correctly, I am under the assumption that only points declared explicitly in the generators are considered. (And perhaps fixed points should be declared with 1-cycle generators?) I realize this may not be backwards compatible, and so I'm wondering what the best course of action here is.

Someone asked me a great question a couple of days ago that made me realize that something should be emphasized here, even if it is a bit basic. A permutation group as defined in Sage (and GAP) is three objects: a set, an action/representation, and an underlying group. Unfortunately, the best way to define a permutation group is usually to instead define the corresponding action/representation. Of course, this gives a group and it also brings along more structure (transitivity, primitivity, etc.). But, technically, it is not "a group" and is more appropriately "an action." GAP blurs this difference, but always maintains the action as the primary structure (as Rob's recent example illustrates), even if its primary purpose is to examine the underlying group and even if it calls the structure "a group". Traditionally, the set on which the action acts is a formal object (formal in the mathematical sense, it has no underlying structure). This is true in GAP, although the domain of an action is limited to natural numbers (although there is no underlying structure or order that is assumed). In Sage, this isn't true, and the underlying set is assumed to be well-ordered (the natural numbers as a set plus the structure of order). At least, this is true in Sage currently before an arbitrary action set is implemented.

Rob: In response to your question about a coset class.. We have discussed briefly the idea of a PermutationSubgroup class which would inherit certain information from a parent group/action, and I think the idea of a method for a complete list of coset reps, or transversal reps, etc., fits well into such a class.

Jason

[Mike Hansen]

On Thu, Jun 3, 2010 at 1:11 PM, Jason B Hill <Jason....@colorado.edu> wrote:
>
> Sorry, I was in the mountains for a bit and missed some conversation.
>
> Mike H: Do you want any assistance in your current task?

I have two patches up on the combinat patch server which add domains
to permutation groups.

The first is http://combinat.sagemath.org/hgwebdir.cgi/patches/file/290251ce8ef7/permgroup_cleanup-mh.patch#l1
which is just some general cleanup stuff. This is independent of the
domains code.

The real patch is at
http://combinat.sagemath.org/hgwebdir.cgi/patches/file/290251ce8ef7/permgroup-domain.patch
. I still need to do a little more work in terms of the documentation
and testing things outside of groups/, combinat/, and graphs/, but it
should be pretty close to done. It also does somethings like make
lots of things actual subgroups so that they know about their domain.
Finally, all of the functionality from #8929 was added.

If people could try it out and see how the interface works for them,
that'd be great.

--Mike