Very nonstandard convention used in multiplying permutations

[darijgr]

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 (#14883, #14884), 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?

Depends on #14772
Depends on #14808
Depends on #14881

CC: @tscrim @sagetrac-sage-combinat @mwhansen @nthiery @nathanncohen @sagetrac-jakobkroeker @sagetrac-mafra @slel

Component: combinatorics

Keywords: permutation, permutation group, symmetric group, sage-combinat

Stopgaps: #15174

Issue created by migration from https://trac.sagemath.org/ticket/14885

[tscrim]

comment:2

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.

[darijgr]

comment:3

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. EDIT: got no idea how :(

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

EDIT: And I'm not sure that "all we really need is for this to be well documented". I am in favor of removing left-to-right completely and only leaving right-to-left as the only option. For those who want to use left-to-right, I propose making an "opposite algebra" constructor (which could come quite useful in other situations, too). Do you think this is a viable option (disregarding backward compatibility for a moment)? My problems with global variables are, 1) there is no way to ensure that future coders will know about them and cater to them (see the example I gave), and 2) they feel like a total hack and could easily lead to spooky action at a distance. I have nothing against using globals for output options, I am talking about globals that determine the structure constants of an algebra!

[nathanncohen]

comment:4

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

[darijgr]

comment:5

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 .

[darijgr]

Stopgaps: #15174

[slel]

comment:12

Demoting from 'critical' to 'major'.

[mantepse]

comment:13

I must admit that I think that this one should stay critical.

[slel]

comment:14

Can someone summarise the sage-devel discussion
and propose a path forward?

[tscrim]

comment:15

I do not think it is critical. There is a problem with things not being well documented and things relying on a particular multiplication convention. However, the convention choice within Sage itself is not a critical issue.

[mkoeppe]

comment:16

Setting new milestone based on a cursory review of ticket status, priority, and last modification date.

[goncharovdk]

Got here being somewhat confused about the permutation multiplication behavior. Surprised to see this issue open for more than 10 years. To clarify, below is a quote from (Joyner, 2008). Prof. Joyner is a SAGE contributor and the referenced book uses SAGE extensively.

A Notational Warning! We shall follow standard convention and write our compositions of permutations left-to-right. (This contrasts to the right-to-left composition of functions you may have seen in calculus.) When a possible ambiguity may arise, we call this type of composition ‘composition as permutations’ and call ‘right-to-left composition’ the ‘composition as functions’.

(Bold text is exactly as in the book.)

Joyner, D. (2008). Adventures in group theory: Rubik’s cube, Merlin’s machine, and other mathematical toys (2nd ed.). Johns Hopkins University Press.