[Sage] #14885: Very nonstandard convention used in multiplying permutations
Sage
-----------------------------+----------------------------------------------
Reporter: darij | Owner: sage-combinat
Type: defect | Status: new
Priority: critical | Milestone: sage-5.12
Component: combinatorics | Keywords: permutation, permutation group, symmetric group, sage-combinat, groups
Work issues: | Report Upstream: N/A
Reviewers: | Authors:
Merged in: | Dependencies: #14772, #14808, #14881
Stopgaps: |
-----------------------------+----------------------------------------------
In most mathematical literature, the product {{{p * q}}} of two
permutations {{{p}}} and {{{q}}} is defined to be the permutation given by
first applying {{{q}}} and then applying {{{p}}}. This notation is so
standard that (unlike either of the ways to draw a Young tableau, or
considering 0 a natural number or not) authors don't even bother to say
anything about it when they are using it. I have seen the opposite
convention ("left-to-right", i. e., first apply {{{p}}}, then {{{q}}})
only in Herstein's "Topics in Algebra" (he no longer seemed to use it in
his newer "Abstract Algebra") and GAP. Not until today did I know that
Sage also belongs to this exclusive circle. I don't know how many
computations I have made unaware of this, and how many of them gave wrong
results. And I have a hunch that I might not be the only one. Both
Herstein and GAP accompany their nonstandard definition of a product by a
corresponding syntax for actions: permutations (and, in the case of
Herstein, most maps in general) act on items from the right in their
notation. This, at least, has the advantage of screaming "nonstandard
notations!" to the reader/user, who will then (hopefully) be foresightful
enough to check out how products are read. But this is not how it works in
Sage (and is probably not possible in Python). In Sage, permutations act
on numbers from the left but are multiplied right-to-left. If you ask me,
this is a bug and as serious as a bug can get due to its enormous
potential for misunderstanding between man and machine.
Actually, by setting a global variable one can make Sage work with the
usual convention as well. Well, that requires knowing that the issue
exists in the first place. This left aside, this might be a cure worse
than the disease. Global variables affect computations inside methods, and
at least some methods reliant on multiplication of permutations were not
written with these variables in mind. Here is an example: The
{{{characteristic_symmetric_function()}}} method on Dyck words breaks if
the permutation option {{{mult}}} is set to {{{'r2l'}}}:
{{{
sage: R = QQ['q','t'].fraction_field()
sage: (q,t) = R.gens()
sage: f = sum(t**D.area()*D.characteristic_symmetric_function() for D in
DyckWords(3)); f
(q^3+q^2*t+q*t^2+t^3+q*t)*s[1, 1, 1] + (q^2+q*t+t^2+q+t)*s[2, 1] + s[3]
sage: PermutationOptions(mult='r2l')
sage: f = sum(t**D.area()*D.characteristic_symmetric_function() for D in
DyckWords(3)); f
---------------------------------------------------------------------------
ValueError Traceback (most recent call
last)
...
ValueError: (q^2+q)*F[1, 2] + q*F[2, 1] is not a symmetric function
}}}
The same error is cast if I use the new syntax introduced by #14772 (no
offense to Travis, his patch is not about this). (Before #14772, you would
switch from one convention to the other using
{{{PermutationOptions(mult='r2l')}}} resp.
{{{PermutationOptions(mult='l2r')}}}; now, it is
{{{Permutations.global_options(mult='r2l')}}} resp.
{{{Permutations.global_options(mult='l2r')}}}.)
Probably the "right" way to work around this issue is by doing what
{{{sage/combinat/symmetric_group_algebra.py}}} does in its
{{{epsilon_ik()}}} method, and temporarily reset the permutation options
before starting the computation, then setting them back after the
computation is done. I guess I'm not the only one who is finding this ugly
and error-prone; moreover, it probably makes parallelization harder.
I have checked sage.combinat and not found any other visible errors of the
above type, but this seems to be owed to the fact that we rarely ever
multiply permutations! I have seen some permutations being coerced into
larger symmetric groups by multiplying them with the appropriate identity
permutations (#14483, #14484), and some doctests which don't really depend
on the order of multiplication. Other than that, permutations getting
multiplied inside methods seem rare and mostly contained in
{{{permutation.py}}} and {{{symmetric_group_algebra.py}}}. This issue *is*
fixable if we want to; the worst that will happen is backward
incompatibility, but I don't think that would be worse than what we have
now.
What are everyone's opinions on this?
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/14885>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica, and MATLAB
Sage
Type: defect | Status: new
Priority: critical | Milestone: sage-5.12
Report Upstream: N/A | Reviewers:
Authors: | Merged in:
Dependencies: #14772, #14808, #14881 | Stopgaps:
Description changed by darij:
Old description:
multiplied inside methods seem rare and mostly contained in
{{{permutation.py}}} and {{{symmetric_group_algebra.py}}}. This issue *is*
fixable if we want to; the worst that will happen is backward
incompatibility, but I don't think that would be worse than what we have
now.
What are everyone's opinions on this?
--
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/14885#comment:1>
Sage
Type: defect | Status: new
Priority: critical | Milestone: sage-5.12
Report Upstream: N/A | Reviewers:
Authors: | Merged in:
Dependencies: #14772, #14808, #14881 | Stopgaps:
Comment (by tscrim):
What is the action on one permutation on another? Does is swap by position
or swap by value? The point I'm trying to make is that this affects how
multiplication of permutations is done as well. I'd also have to check (by
hand) what happens with what I do by default, which is swap by position. I
think all we really need is for this to be well documented. Also, are
there any methods which break when you set the opposite convention?
No matter what, this should be a discussion on sage-devel.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/14885#comment:2>
Sage
Type: defect | Status: new
Priority: critical | Milestone: sage-5.12
Report Upstream: N/A | Reviewers:
Authors: | Merged in:
Dependencies: #14772, #14808, #14881 | Stopgaps:
Comment (by darij):
What do you mean by "the action on[of?] one permutation on another"? Sage
doesn't understand {{{Permutation([1,3,2])(Permutation([2,3,1]))}}}. Do
you mean action on an int? It's the usual left action:
{{{
sage: Permutation([2,3,1])(3)
1
}}}
I think sage-devel is a good idea. I'm not on the list though (only sage-
combinat-devel); will try to join now.
About methods breaking if we set the opposite convention, the
{{{characteristic_symmetric_function()}}} one is an example, but probably
various methods in {{{permutation.py}}} and
{{{symmetric_group_algebra.py}}} will also; on the other hand, I am fairly
sure that very few methods outside these two files will change. (I have
only run doctests on sage.groups and sage.combinat, though.)
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/14885#comment:3>
Sage
Type: defect | Status: new
Priority: critical | Milestone: sage-5.12
Report Upstream: N/A | Reviewers:
Authors: | Merged in:
Dependencies: #14772, #14808, #14881 | Stopgaps:
Comment (by ncohen):
I also think that this should be a thread on Sage devel, if only to let
everybody know what has been going on until now. That's really scary `O_o`
Personally, I would vote for a backward uncompatible change that would set
things how they should have been written since the beginning. Possibly
with a warning the first time the multiplication is called to say that
"there has been a change, and that the users should think for a couple of
minutes of their past OR future computations, as one of the two is not
returning what they think it should".
But this is definitely worth advertisement on sage-devel !
Nathann
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/14885#comment:4>
Sage
Type: defect | Status: new
Priority: critical | Milestone: sage-5.12
Report Upstream: N/A | Reviewers:
Authors: | Merged in:
Dependencies: #14772, #14808, #14881 | Stopgaps:
Comment (by darij):
I have just figured out why I can't join sage-devel: I'm on the group
already *facepalm*.
Posted: https://groups.google.com/forum/#!topic/sage-devel/tAAb42Edh9o .
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/14885#comment:5>