Products of permutations use nonstandard order of operation

[darijgrinberg]

Hello!

While trying to do computations in symmetric group algebras today, I was shocked by the fact that Sage uses the convention that a product \pi \psi of two permutations \pi and \psi is the permutation that applies \pi first and \psi later. In my opinion, this convention is highly nonstandard (I only saw it in GAP and in Herstein's older books; nowadays most mathematicians use the opposite convention without even mentioning it, and even Herstein stopped pushing the other way) and does not match the fact that permutations, like any functions, are applied to elements from the left in Sage (as opposed to GAP, which at least is consequent in that permutations act from the right).

This *can* be defended as a convention, but I see every reason to call it a bug. I spent a year or more using Sage, multiplying permutations among other things, and never noticed that the results I was getting did not mean what I supposed them to mean. (Working with the wrong operation order only becomes visible in S_3 and higher, and many properties of the symmetric group algebra are independent of the order -- like any group algebra, it is isomorphic to its opposite --, so one only gets bitten if one works with specific elements, like the Young symmetrizers; but for this reason it's particularly hard to notice that something is going wrong!)

There is a further issue lurking in the background here. It *is* possible to make Sage use the standard convention (first \psi, then \pi), namely by setting a global variable (see http://trac.sagemath.org/sage_trac/ticket/14885 for details). Unfortunately, this requires knowing of the existence of this variable; apparently, some of the coders did not, and so a method in dyck_word.py seemingly completely unrelated to permutations (it only uses permutations in its implementation) breaks when this global variable is set. With no offense, I believe the only reason why this doesn't happen more often is that permutations are multiplied surprisingly rarely in Sage code (maybe for this reason?). In order to use products of permutations reliably in a method, one has to distinguish cases depending on this global variable! I've even seen the variable set to the standard value at the beginning of a method, and then reset back to what it was at the end. I thought we had Python to avoid having to hack like that.

The main reason I'm posting this here is to sound out how many people see this as a problem like I do, and what solutions would be favored. I am not exactly a seasoned developer, so the way I see to solve the problems might be somewhat crude:

1) Switch the convention to the standard one, and remove the global variable. For those who want to use the GAP convention, add an OppositeAlgebra constructor/factory/class/whatever (I have to admit I don't understand Categories well enough to do that part, but if we can define dual bases we surely can define opposite algebras).

2) Fix the methods that rely on the convention being nonstandard. My experiments (breaking the __mul__ function on Permutations, and subsequently running doctests) show that the number of methods using products of permutations is rather modest (I made #14883 and #14884 to reduce it even further); however, it can be argued that I am counting doctests rather than methods...

3) Splatter warnings all over permutations, permutation groups, and symmetric group algebra code in the hope of waking up the users. Unfortunately, it doesn't seem like deprecation warnings can be used here, so there will be some rude awakenings. Nathann Cohen suggests a warning that is spat out the first time a product of permutations is being called; I hope this can be done in a way that does not break doctests. Any other ideas how to make things noticed?

Is this too barbarous a solution? Is the problem not much of a problem?

  Best regards,
  Darij

[Rob Beezer]

On Friday, July 12, 2013 4:43:09 PM UTC-7, darijgrinberg wrote:

Is this too barbarous a solution? Is the problem not much of a problem?

Thanks for bringing this off Trac and to the wider audience.  Some thoughts.

While less than ideal, I would not go so far as to call it a bug.  But then I studied out of an older version of Herstein.  ;-)   I *always* check  which ordering is employed when I pick up a new text or software system.  I have had little trouble telling my students that their text (Judson) and Sage use different conventions.  We follow Sage in all their work.

Breaking doctests is one thing, breaking user code is another.   I've written some rather extensive materials to incorporate in Judson's book, on Sage and elementary group theory (using permutation groups), following the Sage convention.  All of the low-level elementwise stuff there would break with a change.  I am not arguing against a change, we should just be aware that the pain goes beyond fixing up doctests.

It is unfortunate that historical accidents like this (I assume Sage was following GAP's lead) are so hard to correct.  I've had my own personal crusade on the row-vector and column-vector dichotomy, so I sympathize.

I agree that setting the convention with a global variable is evil, and your example with Dyck words could be a good lesson on why.

I hope somebody here can see a graceful way to improve the situation without too much pain or splattering.

Rob

[Volker Braun]

I would be in favor of having the "sensible" notation, that is, change what is currently in Sage.

With Sage-6.0 coming up there would be a natural transition point. It is easy to have a warning shown the first time that you multiply two permutations and not show it in DOCTEST_MODE. We would then keep the (ill-advised) global variable around, flip the default value, and deprecate it. The warning would tell you that you can use use it for a limited time to switch back to the old behavior. In >1 year we then get rid of that crutch.

[David Joyner]

On Fri, Jul 12, 2013 at 11:21 PM, Rob Beezer <goo...@beezer.cotse.net> wrote:
>
> On Friday, July 12, 2013 4:43:09 PM UTC-7, darijgrinberg wrote:
>>
>> Is this too barbarous a solution? Is the problem not much of a problem?
>
>
> Thanks for bringing this off Trac and to the wider audience. Some thoughts.
>
> While less than ideal, I would not go so far as to call it a bug. But then

I would not call this a bug either.
It boils down to defining a permutation group via a left action or
a right action. Some people favor left-actions, some right-actions.
IMHO, it has the correct default behavior, but if someone wants to
add methods to allow for an alternative definition, great!

>
> Rob
>
> --
> You received this message because you are subscribed to the Google Groups
> "sage-devel" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to sage-devel+...@googlegroups.com.
> To post to this group, send email to sage-...@googlegroups.com.
> Visit this group at http://groups.google.com/group/sage-devel.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>

[Travis Scrimshaw]

I would not call this a bug either.
It boils down to defining a permutation group via a left action or
a right action. Some people favor left-actions, some right-actions.
IMHO, it has the correct default behavior, but if someone wants to
add methods to allow for an alternative definition, great!

Because of that, I would not be in favor of deprecating the global variable, but instead make sure that the convention might be different than you expect for your methods. I don't have a real preference on which is the default, just so long as whatever convention a user would want to employ is available.

Best,

Travis

[Volker Braun]

On Friday, July 12, 2013 11:58:13 PM UTC-4, David Joyner wrote:

It boils down to defining a permutation group via a left action or
a right action. Some people favor left-actions, some right-actions.

 

But the question is, how is this right action that you speak of implemented in Sage?

sage: p = Permutation([2,3,1])

sage: p(1)      # looks like a left action to me

2

sage: (1)p

  File "<ipython-input-7-23ee1ba2540f>", line 1

    (Integer(1))p

                ^

SyntaxError: invalid syntax

sage: 1 * p

---------------------------------------------------------------------------

TypeError                                 Traceback (most recent call last)

<ipython-input-8-6438d08d9819> in <module>()

----> 1 Integer(1) * p

/home/vbraun/opt/sage-5.11.beta3/local/lib/python2.7/site-packages/sage/structure/element.so in sage.structure.element.RingElement.__mul__ (sage/structure/element.c:14531)()

/home/vbraun/opt/sage-5.11.beta3/local/lib/python2.7/site-packages/sage/structure/coerce.so in sage.structure.coerce.CoercionModel_cache_maps.bin_op (sage/structure/coerce.c:8114)()

/home/vbraun/opt/sage-5.11.beta3/local/lib/python2.7/site-packages/sage/combinat/permutation.pyc in __rmul__(self, lp)

   1162         global permutation_options

   1163         if permutation_options['mult'] == 'l2r':

-> 1164             return self._left_to_right_multiply_on_left(lp)

   1165         else:

   1166             return self._left_to_right_multiply_on_right(lp)

/home/vbraun/opt/sage-5.11.beta3/local/lib/python2.7/site-packages/sage/combinat/permutation.pyc in _left_to_right_multiply_on_left(self, lp)

   1179         #Pad the permutations if they are of

   1180         #different sizes

-> 1181         new_lp = lp[:] + [i+1 for i in range(len(lp), len(self))]

   1182         new_p1 = self[:] + [i+1 for i in range(len(self), len(lp))]

   1183         return Permutation([ new_p1[i-1] for i in new_lp ])

TypeError: 'sage.rings.integer.Integer' object has no attribute '__getitem__'

[Nils Bruin]

On Saturday, July 13, 2013 1:43:09 AM UTC+2, darijgrinberg wrote:

There is a further issue lurking in the background here. It *is* possible to make Sage use the standard convention (first \psi, then \pi), namely by setting a global variable (see http://trac.sagemath.org/sage_trac/ticket/14885 for details). Unfortunately, this requires knowing of the existence of this variable; apparently, some of the coders did not, and so a method in dyck_word.py seemingly completely unrelated to permutations (it only uses permutations in its implementation) breaks when this global variable is set.

This sounds like the most serious issue to me. Having such a global variable will be an eternal pitfall . If you always have to check *at runtime* in which order a permutation composition has to be done, you're far worse off than testing it *at developing time* (since you'll have to check how to interpret the value of the global variable at runtime anyway). Never mind that a separate thread could change the value of the global variable half way through your computation!

I don't particularly care which convention is followed, since half of the time, it will be the less convenient one anyway, but it should be consistent. Since a permutation group is an abstract group *given by its action*, the appropriate place to offer a choice would be at construction of the group, e.g.

SymmetricGroup(<finite set>,action="left"/"right")

but I'd prefer there's only one.

Incidentally, note:

sage: S3=SymmetricGroup(3)
sage: s=S3((1,2,3))
sage: s.matrix()
[0 1 0]
[0 0 1]
[1 0 0]

which suggests to me that the natural action of s as permutation matrix is on row vectors, i.e., on the right. The global variable doesn't change that.

[Darij Grinberg]

Hello again,

thanks for the reactions! Good to see that I'm not the only one who is having headaches with the current system.

On Saturday, 13 July 2013 05:21:58 UTC+2, Rob Beezer wrote:

>    Breaking doctests is one thing, breaking user code is another.   

>    I've written some rather extensive materials to incorporate in

>    Judson's book, on Sage and elementary group theory (using

>    permutation groups), following the Sage convention.  All of

>    the low-level elementwise stuff there would break with a

>    change.  I am not arguing against a change, we should just

>    be aware that the pain goes beyond fixing up doctests.

Yes, I never said that doctests will be the only thing that breaks; I said they are the only thing we can prevent from breaking. It's not a very responsible attitude, but imho it's still better than doing nothing.

But if Judson's book uses right-to-left and Sage uses left-to-right, shouldn't your materials actually become easier to use once the dust has settled?


On Saturday, 13 July 2013 05:47:15 UTC+2, Volker Braun wrote

>    With Sage-6.0 coming up there would be a natural transition

>    point. It is easy to have a warning shown the first time that

>    you multiply two permutations and not show it in

>    DOCTEST_MODE. We would then keep the (ill-advised)

>    global variable around, flip the default value, and deprecate

>    it.

Good idea, although I'd rather have this done before 6.0 as I imagine the 6.0 update creating a cluster of other complications (git, and who knows, maybe even Python 3).

  Best regards,
  Darij

[John Cremona]

I think this point (Volker's) is a very good one: if the action is
to be a right action then it should be implemented as such, just as
many group theorists write "i\sigma" for the image of i under \sigma
with a right action. Persumably such right actions can be implemented
in Sage so one would write i*sigma for this instead of sigma(i) or
sigma*i for the left action.

The permutations and permutations groups would have the direction of
the action set on creation (with some default of course) and run-time
errors would arise if you tried sigma*i with right action or i*sigma
with a left action or sigma*tau if they came with different actions.

John

[Dima Pasechnik]

On 2013-07-12, darijgrinberg <darijg...@gmail.com> wrote:
> ------=_Part_13473_7743396.1373672589533
> Content-Type: text/plain; charset=ISO-8859-1

>
> Hello!
>
> While trying to do computations in symmetric group algebras today, I was
> shocked by the fact that Sage uses the convention that a product \pi \psi
> of two permutations \pi and \psi is the permutation that applies \pi first
> and \psi later. In my opinion, this convention is highly nonstandard (I
> only saw it in GAP and in Herstein's older books; nowadays most
> mathematicians use the opposite convention without even mentioning it, and
> even Herstein stopped pushing the other way) and does not match the fact
> that permutations, like any functions, are applied to elements from the
> left in Sage (as opposed to GAP, which at least is consequent in that
> permutations act from the right).

IMHO it's a not as obsolete convention as you seem to imply; isn't e.g. Magma
using the same convention as GAP?
Not mentioning a lot of group theory literature...

[Darij Grinberg]

Hi Dima,

On Sat, Jul 13, 2013 at 1:26 PM, Dima Pasechnik <dim...@gmail.com> wrote:
> IMHO it's a not as obsolete convention as you seem to imply; isn't e.g. Magma
> using the same convention as GAP?
> Not mentioning a lot of group theory literature...

I don't know anything about Magma, but what group theory literature
uses this convention?

Best regards,
Darij

[Darij Grinberg]

TypeError: unsupported operand parent(s) for '-': 'Symmetric group
algebra of order 5 over Rational Field' and 'Symmetric group algebra
of order 5 over Integer Ring'

I am disappoint...

[Nicolas M. Thiery]

Hi all,

Thanks Darij for bringing up the issue, and everyone for your
feedback! Here is my (strong for once) opinion on this issue. Sorry I
am taking off right now for vacations, so it's stated in a rush.

- I for myself usually prefer left composition for permutations (like
most combinatorialist) but do prefer right actions in many other
related situations. In short, I want both :-)

- GAP (and to a lesser extent Magma) is *the* reference when it comes
to computational group theory. I find it very natural that Sage
chose to follow GAP's lead.

- A global option for this is bad. In general, global options should
not affect the semantic.

- +1 on a parent option:

sage: PermutationGroup(..., action='left')

Note that this is consistent with what we do for finite set maps:

sage: M = FiniteSetMaps([1, 2, 3], action = 'right')

Maybe PermutationGroupElement will need to take an option too, and a
decision will need to be taken for mixed products.

- -1 on changing the default value. There is way too much risk to
break user code out there and in a way to subtle way.

Cheers,
Nicolas
--
Nicolas M. Thi�ry "Isil" <nth...@users.sf.net>
http://Nicolas.Thiery.name/

[William Stein]

On Sat, Jul 13, 2013 at 5:50 AM, Nicolas M. Thiery
<Nicolas...@u-psud.fr> wrote:
> Hi all,
>
> Thanks Darij for bringing up the issue, and everyone for your
> feedback! Here is my (strong for once) opinion on this issue.

+1 to everything in your strong opinion.

> Sorry I
> am taking off right now for vacations, so it's stated in a rush.
>
> - I for myself usually prefer left composition for permutations (like
> most combinatorialist) but do prefer right actions in many other
> related situations. In short, I want both :-)
>
> - GAP (and to a lesser extent Magma) is *the* reference when it comes
> to computational group theory. I find it very natural that Sage
> chose to follow GAP's lead.
>
> - A global option for this is bad. In general, global options should
> not affect the semantic.
>
> - +1 on a parent option:
>
> sage: PermutationGroup(..., action='left')
>
> Note that this is consistent with what we do for finite set maps:
>
> sage: M = FiniteSetMaps([1, 2, 3], action = 'right')
>
> Maybe PermutationGroupElement will need to take an option too, and a
> decision will need to be taken for mixed products.
>
> - -1 on changing the default value. There is way too much risk to
> break user code out there and in a way to subtle way.
>
> Cheers,
> Nicolas
> --

> Nicolas M. Thiéry "Isil" <nth...@users.sf.net>
> http://Nicolas.Thiery.name/

>
> --
> You received this message because you are subscribed to the Google Groups "sage-devel" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+...@googlegroups.com.
> To post to this group, send email to sage-...@googlegroups.com.
> Visit this group at http://groups.google.com/group/sage-devel.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>

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

[Darij Grinberg]

Hi Nicolas, and hi all,

> - +1 on a parent option:
>
> sage: PermutationGroup(..., action='left')
>
> Note that this is consistent with what we do for finite set maps:
>
> sage: M = FiniteSetMaps([1, 2, 3], action = 'right')
>
> Maybe PermutationGroupElement will need to take an option too, and a
> decision will need to be taken for mixed products.

I like this idea a lot, provided we can pull this off.

One way to do it, of course, is by making the symmetric group algebra
an AlgebraWithRealizations (like most combinatorial Hopf algebras),
and implement the two different conventions as two different
realizations of it, with the antipode map (g |-> g^{-1} for g in the
group) serving as the coercion in both directions. This will lead to
things working exactly as they should, *but* the coercion map involves
inverting permutations and that might slow things down. Ideally, I'd
want two distinct PermutationGroup classes differing only in their
__mul__'s, without having the need to duplicate code or split into
cases depending on left/rightness. Something like: if I put a method
in the left version of the PermutationGroup class, then it
automatically also works for the right version, but if the method
internally depends on __mul__, I want it to be using the same __mul__
in both classes, so when I call the method from the right class, it
first converts into the left version, then applies the method written
there, and then converts back into the right version. But, of course,
I only want this for methods which *internally* depend on
multiplication rather than for methods like "product" which *should*
work differently on both sides. Do we have the right framework to
formalize this and make this work? Or is what I'm describing misguided
or self-contradictory?

Best regards,
Darij

[Travis Scrimshaw]

Hey everyone who's following #14772,

   I don't want to change the patch, which has the multiplication in a GlobalOptions class, since it's just lifts the previous options up (a standard dict). Thus any change should depend on #14772 IMO. I'm not attached to having multiplication be a global option anyways and would be happy with two separate parents and/or element classes.

Hey Darij,

   I think you're hoping for too much. If you have an algorithm which strongly depends on permutation multiplication done a certain way, we will need 2 separate element classes, one which does the algorithm, and another which converts and calls the algorithm (or hacked around using some optional arguments which I'd be against).

Best,

Travis

[Rob Beezer]

On Saturday, July 13, 2013 2:22:41 AM UTC-7, Darij Grinberg wrote:

But if Judson's book uses right-to-left and Sage uses left-to-right, shouldn't your materials actually become easier to use once the dust has settled?

Yes, of course.  It is me who will have trouble adjusting to the new convention.  And I don't like dusting.  ;-)

Rob

[Dima Pasechnik]

IMHO, most of what is written by the UK (and even the British Commonwealth)
mathematicians, e.g. the Altas of Finite Groups by J.Conway et al.

Dima

[vdelecroix]

Here is a Sage argument in favor of right action: vectors are row vectors in Sage (on which matrices act on right). There has been a choice to silently ignore transposition and we can write vA or Av in Sage... but still the natural way to do it is through right action (if we do it the other way, there is a lot of time lost in transpositions).

As Volker Braun mentioned, the main problem is that it is possible to write p(i) in Sage! I suggest that we remove the __call__ attribute of permutations (it does not exists in GAP but I do not know for other softwares). If we consider permutations as a function on a finite set, then it should definitely be a left action (this is because of Python). One caveheat of this removal is that we may want to access to p as a list and for list we have the notation l[i] which is as bad as a left action. Perhaps we should also remove the __getitem__ attribute.

Vincent

[Darij Grinberg]

Hi all,

On Sun, Jul 14, 2013 at 5:54 AM, Travis Scrimshaw <tsc...@ucdavis.edu> wrote:
> Hey everyone who's following #14772,
> I don't want to change the patch, which has the multiplication in a
> GlobalOptions class, since it's just lifts the previous options up (a
> standard dict). Thus any change should depend on #14772 IMO. I'm not
> attached to having multiplication be a global option anyways and would be
> happy with two separate parents and/or element classes.

I wasn't asking you to do this in #14772, or anything that would make
that patch even larger (though it feels like much of its size is due
to suboptimal diff encoding).

> I think you're hoping for too much. If you have an algorithm which
> strongly depends on permutation multiplication done a certain way, we will
> need 2 separate element classes, one which does the algorithm, and another
> which converts and calls the algorithm (or hacked around using some optional
> arguments which I'd be against).

Hmm. Then we should keep the currently existing
_left_to_right_multiply_on_right and _left_to_right_multiply_on_left
methods (which don't depend on the global variable) and encourage
coders to always use them instead of *, and to never use things like
product([...]).

On Sun, Jul 14, 2013 at 10:49 AM, vdelecroix <20100.d...@gmail.com> wrote:
> Here is a Sage argument in favor of right action: vectors are row vectors in
> Sage (on which matrices act on right). There has been a choice to silently
> ignore transposition and we can write vA or Av in Sage... but still the
> natural way to do it is through right action (if we do it the other way,
> there is a lot of time lost in transpositions).

Well, when I type A * v in Sage, it multiplies the matrix A from the
left with the columnized vector v. No big surprises here, just what
one would expect when one assumes that Sage prints column vectors as
rows to save space. It's a pity that things like v * A * v make sense
in Sage, but this is a different story. What is certainly not
happening is that the product A * v means v * A.

I don't think the side from which matrices act must be unified with
the side from which permutations act. The conversion from permutations
to permutation matrices isn't *that* important. In Schur-Weyl duality,
permutations and matrices traditionally act on tensors from two
different sides, and regarding permutations as matrices is a great way
to get confused about it (unless one really wants to see how these
permutation matrices act in Schur-Weyl duality).

> As Volker Braun mentioned, the main problem is that it is possible to write
> p(i) in Sage! I suggest that we remove the __call__ attribute of
> permutations (it does not exists in GAP but I do not know for other
> softwares). If we consider permutations as a function on a finite set, then
> it should definitely be a left action (this is because of Python). One
> caveheat of this removal is that we may want to access to p as a list and
> for list we have the notation l[i] which is as bad as a left action. Perhaps
> we should also remove the __getitem__ attribute.

I don't like this idea at all, and I think people will just switch to
list(p)[i-1]. I still think that the definitive standard, OK, outside
group theory, is to have permutations be maps, and for maps to act
from the left.

On Sun, Jul 14, 2013 at 10:07 AM, Dima Pasechnik <dim...@gmail.com> wrote:
> IMHO, most of what is written by the UK (and even the British Commonwealth)
> mathematicians, e.g. the Altas of Finite Groups by J.Conway et al.

There might be a representation-theory vs. group-theory divide here.
James/Kerber certainly uses my convention. This convinces me that both
should be implemented.

Best regards,
Darij

[Volker Braun]

On Sunday, July 14, 2013 4:49:36 AM UTC-4, vdelecroix wrote:

As Volker Braun mentioned, the main problem is that it is possible to write p(i) in Sage! I suggest that we remove the __call__ attribute of permutations (it does not exists in GAP but I do not know for other softwares). If we consider permutations as a function on a finite set, then it should definitely be a left action (this is because of Python). One caveheat of this removal is that we may want to access to p as a list and for list we have the notation l[i] which is as bad as a left action. Perhaps we should also remove the __getitem__ attribute.

But the call syntax is just very handy. How about we show a warning the first time the call syntax is used with a right-action-permutation but not with the yet-to-be-written left-action-permutation.

Proper right actions could be implemented in a multiplicative notation via __rmul__. The warning could be avoided with a special right_action() method or with an optional keyword argument p(i, right=True).

 

[Nicolas M. Thiery]

Hi Darij,

On Sat, Jul 13, 2013 at 08:39:02PM +0200, Darij Grinberg wrote:
> One way to do it, of course, is by making the symmetric group algebra
> an AlgebraWithRealizations (like most combinatorial Hopf algebras),
> and implement the two different conventions as two different
> realizations of it, with the antipode map (g |-> g^{-1} for g in the
> group) serving as the coercion in both directions. This will lead to
> things working exactly as they should, *but* the coercion map involves
> inverting permutations and that might slow things down. Ideally, I'd
> want two distinct PermutationGroup classes differing only in their
> __mul__'s, without having the need to duplicate code or split into
> cases depending on left/rightness. Something like: if I put a method
> in the left version of the PermutationGroup class, then it
> automatically also works for the right version, but if the method
> internally depends on __mul__, I want it to be using the same __mul__
> in both classes, so when I call the method from the right class, it
> first converts into the left version, then applies the method written
> there, and then converts back into the right version. But, of course,
> I only want this for methods which *internally* depend on
> multiplication rather than for methods like "product" which *should*
> work differently on both sides. Do we have the right framework to
> formalize this and make this work? Or is what I'm describing misguided
> or self-contradictory?

Unless you have a specific need for working simultaneously with the
two group algebras of a group of permutation (one for it acting on the
left, and one for it acting on the right), this feels like overkill at
this point to have the symmetric group algebra as an algebra with
several realizations just for this.

Btw: don't worry too much about SymmetricGroupAlgebra. It needs to be
rewritten anyway at some point to use the generic code about group
algebras, and there will be very little specific code left -- if any a
this point -- after this.

[Marco Streng]

2013/7/13 Volker Braun <vbrau...@gmail.com>:

> But the question is, how is this right action that you speak of implemented
> in Sage?

+1 to this comment of Volker. And the notation should be "^" (hat)

I had Darij's problem as well, and many others probably did as well.
In a right action, I would prefer p(1) to give a warning. In a right
action, I would want some notation where p is on the right, preferably
1^p (1 hat p).
The notation "*" has the wrong distributive laws in case of actions on
rings or groups. Of course this is irrelevant for permutations acting
on sets, but since Galois groups can be interpreted as permutation
groups too and they act on rings, the hat is much better.

+1 also to a parent option for all groups with natural actions (Galois
groups, permutation groups, ...?) saying "left" or "right". I don't
care too much what the default value is in each case, as long as there
are warnings.

[Peter Bruin]

Hi Marco and all,

I had Darij's problem as well, and many others probably did as well.
In a right action, I would prefer p(1) to give a warning. In a right
action, I would want some notation where p is on the right, preferably
1^p (1 hat p). 

That would make sense (except that I don't really see why "^" is better than "*", see below).  In principle one can even allow completely symmetric notation:

- left action of g on x: g(x) or g^x; think of [left exponent g]x in two-dimensional notation

- right action of g on x: (x)g or x^g

Of course g^x and (x)g look a bit funny and maybe too confusing, but this is just because we are used to thinking that g^x means that x is in the exponent (as opposed to g, on the left), and we are not used to (x)g at all.  I guess existing parsers could be enhanced to accept all these notations if somebody is crazy enough to want them. 8-)

The notation "*" has the wrong distributive laws in case of actions on 
rings or groups. Of course this is irrelevant for permutations acting 
on sets, but since Galois groups can be interpreted as permutation 
groups too and they act on rings, the hat is much better. 

For both left and right actions, whether multiplicative ("*", similar binary symbols or the empty notation) or exponential notation ("^", left or right exponents) looks more natural depends on whether you are looking at the behaviour of the group action with respect to addition or with respect to multiplication.  The following (and their equivalents for right actions) look OK:

g*(x + y) = g*x + g*y

[left exponent g](x*y) = [left exponent g]x * [left exponent g]y

g^(x*y) = (g^x)*(g^y)  (as long as you think of g as the exponent, not x and y)

But the following look somewhat less appropriate:

g*(x*y) = (g*x)*(g*y)

[left exponent g](x + y) = [left exponent g]x + [left exponent g]y  (especially strange for right actions)

g^(x + y) = g^x + g^y

Peter

[William Stein]

On Mon, Jul 15, 2013 at 10:34 AM, Peter Bruin <pjb...@gmail.com> wrote:
> Hi Marco and all,
>
>> I had Darij's problem as well, and many others probably did as well.
>> In a right action, I would prefer p(1) to give a warning. In a right
>> action, I would want some notation where p is on the right, preferably
>> 1^p (1 hat p).
>
>
> That would make sense (except that I don't really see why "^" is better than
> "*", see below). In principle one can even allow completely symmetric
> notation:
>
> - left action of g on x: g(x) or g^x; think of [left exponent g]x in
> two-dimensional notation

Trivial remark: I don't think anybody is suggesting that we use
exponentiation to denote a *left* action. Above, he wrote " In a
right action, I would want ...".

> --
> You received this message because you are subscribed to the Google Groups
> "sage-devel" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to sage-devel+...@googlegroups.com.
> To post to this group, send email to sage-...@googlegroups.com.
> Visit this group at http://groups.google.com/group/sage-devel.
> For more options, visit https://groups.google.com/groups/opt_out.
>
>

[Marco Streng]

2013/7/15 Peter Bruin <pjb...@gmail.com>:

> Hi Marco and all,
>
>> I had Darij's problem as well, and many others probably did as well.
>> In a right action, I would prefer p(1) to give a warning. In a right
>> action, I would want some notation where p is on the right, preferably
>> 1^p (1 hat p).
>
>
> That would make sense (except that I don't really see why "^" is better than

Hi Peter,

I was just saying that I prefer "^" personally (reasons below if you
really want to know), but never for left actions, and actually not
even for all right actions. This must be true for more people. So why
not allow multiple notations:
g(x) (but give a warning if it is a right action)
g*x (but give a warning if it is a right action)
x*g (but give a warning if it is a left action)
x^g (but give a warning if it is a right action)
We can even have three types of actions: left, right, and commutative
(for commutative groups acting, where one could let g(x), g*x, x*g,
x^g all give the same result with no warnings).

> "*", see below). In principle one can even allow completely symmetric
> notation:

Yes, but I would discourage writing left actions as right actions or
vice versa. The associative laws become a great source of confusion
and mistakes. For example, x^(g*h) = (x^g)^h makes sense where the
current notation suggests the (in current Sage incorrect) (g*h)(x) =
g(h(x)).

>
> - left action of g on x: g(x) or g^x; think of [left exponent g]x in
> two-dimensional notation
> - right action of g on x: (x)g or x^g
>
> Of course g^x and (x)g look a bit funny and maybe too confusing, but this is
> just because we are used to thinking that g^x means that x is in the

To people who use hats for exponentiation and/or latex superscripts,
"g^x" can only mean that x is in the exponent. The only notation I can
think of where g is in the superscript is the ugly ${}^g x$ (which is
sometimes really used in the literature), but I don't see how to do
that in Python and I don't expect to be very popular in Sage.

> For both left and right actions, whether multiplicative ("*", similar binary
> symbols or the empty notation) or exponential notation ("^", left or right
> exponents) looks more natural depends on whether you are looking at the
> behaviour of the group action with respect to addition or with respect to
> multiplication.

True, but.... (and this debate about * versus ^ is not really
important, so this is the place to stop reading this post if you still
are, it also is not really about permutation groups acting on sets of
integers.)

I'll take Peter's examples, but only for right actions of course,
there is no discussion about notations for left actions.

For actions on rings and additive groups:
(x+y)^g = x^g + y^g violates no rules of arithmetic in itself,
just looks funny
(x+y)*g = x*g + y*g is a very nice distributive law
For actions on commutative rings and multiplicative groups:
(x*y)^g = (x^g) * (y^g) is a very nice distributive law
(x*y)*g violates the associative rule for multiplication, since
(x*y)*g = x*(y*g) is only true if g acts trivially on x.
So in some situations "*" is very bad, while in all situations "^" is ok.

Also, I sometimes choose a right action *because* I want to use
exponential notation, as in e.g. x^(1-g) = x / (x^g).

[David Kohel]

Hi,

I also strongly support both left and right actions, with the syntax

Left action:
s1(s2(x)) == (s1*s2)(x)  

Right action:
(x^s1)^s2 == x^(s1*s2)

Currently the left (functional) notation is implemented in Sage with
the right order of application: s1(s2(x)) == (s2*s1)(x) is True.
This needs to be either accepted or deprecated in preference to
a new right operator.

Magma implements only the right action with ^ notation, and GAP
also (only?) implements the same. 

Attention: Unless I'm mistaken, Magma does something bad with
operator precedence in order to have x^s1^s2 evaluate to (x^s1)^s2
rather than x^(s1^s2) -- the latter is defined but not equal.

The significant change is that a left acting symmetric group
will have its multiplication reversed.

Implementing the right action involves some thought, since it
must be a method on the domain class.  Either the domain
must be a designated class of G-sets, which knows about its
acting group G, or for each object with a "natural" permutation
action, one needs to implement or overload ^ on a case-by-case
basis (e.g. integers, free modules, polynomial rings and other
free objects [action on the generators], etc.).  Please correct
me if there is another way to drop through and pick up an
action operation on the right-hand argument.

Defining the (left or right) action by * would probably be a
nightmare with the coercion model, since it is handled as
a symmetric operator.

Some thought needs to be given to the extension from a
group action to a group algebra action.  The ZZ-module
structure of an abelian group with left G-action would give
an argument to admitting * as a possible (left) notation
for this operation, despite the obvious headaches.
The ^ notation would give a compatible extension of
the natural ZZ-module structure acting on the right on
a multiplicatively represented abelian group. 

As an example, in number theory, when G is a Galois
group Gal(L/K), it is typical to left K[G] act on the left
on L by *, and ZZ[G] act on the right on multiplicative
group L^*.  Although G is not a permutation group in
this example, we want to set up the framework for
G-sets to admit these natural actions.  The left action
is problematic, since the coercion model is susceptible
to building L[G] and carry out * with the trivial G-action
on L.  To avoid this, L needs to be identified as an
object in the category of K-modules (with G-action)
rather than a K-algebra.  Until someone comes up
with a well-developed and coherent model for treating
the operator * in general G-actions, I would avoid any
implementations using this operator with permutation
actions.

--David

[Simon King]

Hi David,

On 2013-07-16, David Kohel <drk...@gmail.com> wrote:
> Defining the (left or right) action by * would probably be a
> nightmare with the coercion model, since it is handled as
> a symmetric operator.

Is this really so?

There is stuff in sage.structure.coerce, for example methods R.get_action(S,operator.mul),
which can be overloaded using R._get_action_, where you can also decide on the
side from which S acts.

Hence, if you want to let S act on R from the left by multiplication, you could
simply let S._get_action_(R, operator.mul, True) return an action, and
if you want to let S act on R from the right by multiplication, you
could let S._get_action_(R, operator.mul, False) return an action.

Here, "action" means something like the stuff in
sage.structure.coerce_acitons.

Let's try an example:
sage: from sage.structure.coerce_actions import GenericAction
sage: class MyAction(GenericAction):
....: def _call_(self, x, y):
....: if self.is_left():
....: return x.left_action(y)
....: return y.right_action(x)
....:
sage: from sage.structure.element import Element
sage: class MyElement(Element):
....: def __init__(self, s, parent=None):
....: self.s = s
....: Element.__init__(self, parent)
....: def left_action(self, n):
....: return self.__class__(self.s+repr(n), self.parent())
....: def right_action(self, n):
....: return self.__class__(self.s*n, self.parent())
....:
sage: class MyParent(Parent):
....: Element = MyElement
....: def _get_action_(self, S, op, self_is_left):
....: if op is operator.mul:
....: return MyAction(self, S, self_is_left, check=False)
....: def _element_constructor_(self, s):
....: return self.element_class(s, self)
....:
sage: P = MyParent(category=Objects())
sage: a = P('hi')
sage: a.s
'hi'
sage: b = a*5
sage: b.s
'hi5'
sage: c = 3*a
sage: c.s
'hihihi'

So, this should show how to implement left and right actions.

Of course, the mathematical property of being an action must be ensured
by a correct implementation of the action.

In particular, note that technically I have implemented an action of
MyParent on ZZ, but in fact I did so in order to get two different
actions of ZZ on MyParent.

Best regards,
Simon

[David Roe]

On Tue, Jul 16, 2013 at 2:07 PM, Simon King <simon...@uni-jena.de> wrote:

Hi David,

On 2013-07-16, David Kohel <drk...@gmail.com> wrote:
> Defining the (left or right) action by * would probably be a
> nightmare with the coercion model, since it is handled as
> a symmetric operator.

Is this really so?

There is stuff in sage.structure.coerce, for example methods R.get_action(S,operator.mul),
which can be overloaded using R._get_action_, where you can also decide on the
side from which S acts.

Hence, if you want to let S act on R from the left by multiplication, you could
simply let S._get_action_(R, operator.mul, True) return an action, and
if you want to let S act on R from the right by multiplication, you
could let S._get_action_(R, operator.mul, False) return an action.

Agreed: defining actions through * should be no problem.  In fact, it will be easier than with ^, since many elements implement __pow__ directly rather than going through the coercion system.
David

[Nicolas M. Thiery]

On Thu, Jul 18, 2013 at 03:16:28PM -0600, David Roe wrote:
> Agreed: defining actions through * should be no problem. In fact, it will
> be easier than with ^, since many elements implement __pow__ directly
> rather than going through the coercion system.

Yup, I agree that * can be a convenient notation for actions.

That being said, * is already very overloaded, which can lead to
confusions. It's no accident that, when writing mathematics, people
often use a different operator (like . or ^) to denote actions and
only resort to * (or nothing) when there is no ambiguity in the given
context. I believe we want the same:

(1) Use by default explicit non ambiguous notations like g.act(x), or
even:

sage: action = ....
sage: action(g,x)

(2) Provide an easy way for the user to register g*x as shorthand for
the above when he thinks it's ok in his/her context.

[Simon King]

On 2013-08-13, Nicolas M. Thiery <Nicolas...@u-psud.fr> wrote:
> (2) Provide an easy way for the user to register g*x as shorthand for
> the above when he thinks it's ok in his/her context.

I think quite often one is in a situation that one has two different
sets (rings, groups, ...) S1, S2, such that there is only one action of
S1 on S2 from the left, and thus if one has s1 from S1 and s2 from S2,
then s1*s2 is not ambiguous.

Concerning "registering an action", we have
sage.structure.parent.Parent.register_action. Does this do what you
suggest?

Best regards,
Simon

[Marc Mezzarobba]

Simon King wrote:
> I think quite often one is in a situation that one has two different
> sets (rings, groups, ...) S1, S2, such that there is only one action
of
> S1 on S2 from the left, and thus if one has s1 from S1 and s2 from S2,
> then s1*s2 is not ambiguous.

I guess it depends what exactly you mean by "only one action of S1 on
S2": think of S1 = K[x][d/dx] and S2 = K[x]. Differential operators act
on polynomials (e.g., d/dx(x) = 1), but there is also an embedding of
K[x] into K[x][d/dx] under which d/dx*x = x*d/dx+1. The internal
multiplication of K[x][d/dx] applied in this context is not a left
action of K[x][d/dx] _on K[x]_, but I would definitely expect (d/dx)*x
to coerce x to K[x][d/dx] and multiply there.

--
Marc

[Simon King]

Hi Marc,

On 2013-08-14, Marc Mezzarobba <ma...@mezzarobba.net> wrote:
> Simon King wrote:
>> I think quite often one is in a situation that one has two different
>> sets (rings, groups, ...) S1, S2, such that there is only one action
> of
>> S1 on S2 from the left, and thus if one has s1 from S1 and s2 from S2,
>> then s1*s2 is not ambiguous.
>
> I guess it depends what exactly you mean by "only one action of S1 on
> S2":

I wrote: "quite often one is in a situation that...". Of course,
sometimes there are two or more different actions to be considered at
the same time. But I would expect that far more often one has just one
action.

>think of S1 = K[x][d/dx] and S2 = K[x]. Differential operators act
> on polynomials (e.g., d/dx(x) = 1), but there is also an embedding of
> K[x] into K[x][d/dx] under which d/dx*x = x*d/dx+1.

Do you see what you just did? You use "call notation" for one action,
i.e., d/dx(x), but use multiplicative notation for the other action,
i.w., d/dx*x.

You can do exactly the same with Sage/Python. I guess if you call a
differential operator, then it means to apply the operator. And if you
define a (multiplicative) action, then "*" will use this action.

> The internal
> multiplication of K[x][d/dx] applied in this context is not a left
> action of K[x][d/dx] _on K[x]_, but I would definitely expect (d/dx)*x
> to coerce x to K[x][d/dx] and multiply there.

No, I'd rather expect to coerce x into a *non-commutative* version of the
polynomial ring K[x][d/dx]. This ring, by the way, is implemented in Sage.
And actually I would expect that the parent of d/dx *is* this ring. So,
instead of using register_action, it would be enough to tell this
non-commutative ring that there is a coercion from K[x].

Best regards,
Simon

[Marc Mezzarobba]

Hi,

Simon King wrote:
>>> I think quite often one is in a situation that one has two different
>>> sets (rings, groups, ...) S1, S2, such that there is only one action
>>> of S1 on S2 from the left, and thus if one has s1 from S1 and s2
>>> from S2, then s1*s2 is not ambiguous.
>>
>> I guess it depends what exactly you mean by "only one action of S1 on
>> S2":
>
> I wrote: "quite often one is in a situation that...".

Sorry, apparently I misinterpreted your "thus...".

>>think of S1 = K[x][d/dx] and S2 = K[x]. Differential operators act
>> on polynomials (e.g., d/dx(x) = 1), but there is also an embedding of
>> K[x] into K[x][d/dx] under which d/dx*x = x*d/dx+1.
>
> Do you see what you just did? You use "call notation" for one action,
> i.e., d/dx(x), but use multiplicative notation for the other action,
> i.w., d/dx*x.

Yes, except that the second one is not an action of S1 on S2 from the
left, but an action of S2 on S1 from the right, isn't it? That's all I
wanted to point out: when trying to decide whether there is a single
action that makes sense, one has to be careful to take into account
actions from both sides and/or actions on larger sets to which the
elements coerce. Apologies if I'm stating the obvious :-)

>> The internal
>> multiplication of K[x][d/dx] applied in this context is not a left
>> action of K[x][d/dx] _on K[x]_, but I would definitely expect
>> (d/dx)*x to coerce x to K[x][d/dx] and multiply there.
>
> No, I'd rather expect to coerce x into a *non-commutative* version of
> the polynomial ring K[x][d/dx].

Yes, what I denoted K[x][d/dx] was the ring of differential operators
with polynomial coefficients. Or do you have something else in mind?

Best wishes,

--
Marc

[Simon King]

Hi Marc,

On 2013-08-14, Marc Mezzarobba <ma...@mezzarobba.net> wrote:

>> Do you see what you just did? You use "call notation" for one action,
>> i.e., d/dx(x), but use multiplicative notation for the other action,
>> i.w., d/dx*x.
>
> Yes, except that the second one is not an action of S1 on S2 from the
> left, but an action of S2 on S1 from the right, isn't it?

Sage has both left and right actions. I would need to look up the
details, but it is no problem to implement a right action of S2 on S1
rather than a left action of S1 on S2. Since the mathematical property
of "being an action" is not relevant in the implementation, you could
actually still tell Sage that there is a left action of S1 on S2, even
though mathematically it is the other way around.

>> No, I'd rather expect to coerce x into a *non-commutative* version of
>> the polynomial ring K[x][d/dx].
>
> Yes, what I denoted K[x][d/dx] was the ring of differential operators
> with polynomial coefficients. Or do you have something else in mind?

Well, I thought you use the usual notation in Sage. And there, square
brackets denote (commutative) polynomial rings. I would do
sage: F.<X,d> = FreeAlgebra(QQ)
sage: D.<x,dx> = F.g_algebra({d*X:X*d+1})
sage: dx*x
x*dx + 1

to create the ring in question. But this is because I am algebraist,
and I guess "proper" differential operators are implemented somewhere
else in Sage (dunno where/how/why), and do *not* live in this ring.

Best regards,
Simon

[Marc Mezzarobba]

Simon King a écrit :

> Sage has both left and right actions. I would need to look up the
> details, but it is no problem to implement a right action of S2 on S1
> rather than a left action of S1 on S2. Since the mathematical property
> of "being an action" is not relevant in the implementation, you could
> actually still tell Sage that there is a left action of S1 on S2, even
> though mathematically it is the other way around.

Okay, so you were speaking of actions in the sense of the coercion
model, and I thought you meant actions in the mathematical sense. Sorry
again for the misunderstanding.

>>> No, I'd rather expect to coerce x into a *non-commutative* version
>>> of the polynomial ring K[x][d/dx].
>>
>> Yes, what I denoted K[x][d/dx] was the ring of differential operators
>> with polynomial coefficients. Or do you have something else in mind?
>
> Well, I thought you use the usual notation in Sage. And there, square
> brackets denote (commutative) polynomial rings.

(On a side note, ticket #13215 proposes to change that in some cases.)

> I would do
> sage: F.<X,d> = FreeAlgebra(QQ)
> sage: D.<x,dx> = F.g_algebra({d*X:X*d+1})
> sage: dx*x
> x*dx + 1
>
> to create the ring in question. But this is because I am algebraist,
> and I guess "proper" differential operators are implemented somewhere
> else in Sage (dunno where/how/why), and do *not* live in this ring.

As far as I know, rings of differential operators are not yet
implemented in the Sage library, and currently the best way to define a
differential operator is the one you mention. (I think that's also more
or less what you told me in Orsay a few weeks ago.) The external package
ore_algebra[1] that Fredrik Johansson announced a few weeks ago[2]
provides "proper" differential operators, though.

[1]
http://www.risc.jku.at/research/combinat/software/ore_algebra/

[2]
<CAJdUXTLq78H2Mcz2-WH-LNbJ=yPax9La-oMic...@mail.gmail.com>
https://groups.google.com/forum/#!topic/sage-devel/S7Wv67C6DvE


Best wishes,

--
Marc

[Darij Grinberg]

Hi everyone,

Two updates on the topic of the multiplication order for permutations:

1) In trac #15174, I have implemented global-option-independent multiplication methods for elements of symmetric group algebras. (Such methods already existed for permutations -- I have now exposed them and added documentation --, but symmetric group algebra elements would only multiply in an option-dependent way.) This should at least improve the situation for coders who want a reliable multiplication method. (However it will sometimes still be better to avoid these methods in favor of manual multiplication a la "Permutation([p(i) for i in q])", because they involve a bit of overhead to ensure that both permutations have the same size -- something which is often already satisfied.)

2) About standardizing (or not) the product of permutations; here is a weird suggestion. What if we deprecate the __mul__ method of the Permutations class, and instead make two new classes called LeftPermutations and RightPermutations, which both inherit from Permutations and additionally have this method defined each differently? Conversely the Permutations class should coerce into both of these new classes (or does this create a coercion cycle?), so that a product of the form Permutation([3,1,2]) * LeftPermutation([1,3,2]) will be well-defined, but one of the form RightPermutation([3,1,2]) * LeftPermutation([1,3,2]) will not, and one of the form Permutation([3,1,2]) * Permutation([1,3,2]) will throw a deprecation warning. We could then proceed to implement different syntaxes for actions of these permutations (left permutations act by p(i); right ones act by i^p, if we ever get this to work). Does this overcomplicate things?

  Best regards,
  Darij

[Johannes Huisman]

Hi there,

I'm new to sage-devel. So I apologize in advance if I say things that make no sense. 

The order of the product of two permutations in sage struck me as well, as many others, no doubt. As has been said, it does not really matter which order has been chosen, as soon as the other order is available as well. 

It appears to me that the opposite of a group, or more generally of a magma, is currently not implemented in sage. Wouldn't that be a nice feauture and a solution to the problem? SymmetricGroup(n).opposite() would then give the symmetric group in which (1,2) * (1,3) equals (1,3,2), whereas (1,2) * (1,3) = (1,2,3) in SymmetricGroup(n).

Johan