Opened 8 years ago

Last modified 2 months ago

#14885 new defect

Very nonstandard convention used in multiplying permutations

Reported by: darij Owned by: sage-combinat
Priority: major Milestone: sage-9.5
Component: combinatorics Keywords: permutation, permutation group, symmetric group, sage-combinat, groups
Cc: tscrim, sage-combinat, mhansen, nthiery, ncohen, jakobkroeker, mafra, slelievre Merged in:
Authors: Reviewers:
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #14772, #14808, #14881 Stopgaps: #15174

Status badges

Description (last modified by darij)

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?

Change History (17)

comment:1 Changed 8 years ago by darij

  • Description modified (diff)

comment:2 Changed 8 years ago 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.

comment:3 Changed 8 years ago 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. 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!

Last edited 8 years ago by darij (previous) (diff)

comment:4 Changed 8 years ago 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

comment:5 Changed 8 years ago 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 .

comment:6 Changed 8 years ago by darij

  • Stopgaps set to #15174

comment:7 Changed 8 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:8 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:9 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:10 Changed 7 years ago by jakobkroeker

  • Cc jakobkroeker added

comment:11 Changed 3 years ago by mafra

  • Cc mafra added

comment:12 Changed 12 months ago by slelievre

  • Cc slelievre added
  • Priority changed from critical to major

Demoting from 'critical' to 'major'.

comment:13 Changed 12 months ago by mantepse

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

comment:14 Changed 12 months ago by slelievre

  • Milestone changed from sage-6.4 to sage-9.3
  • Priority changed from major to critical

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

comment:15 Changed 12 months ago by tscrim

  • Priority changed from critical to major

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.

comment:16 Changed 8 months ago by mkoeppe

  • Milestone changed from sage-9.3 to sage-9.4

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

comment:17 Changed 2 months ago by mkoeppe

  • Milestone changed from sage-9.4 to sage-9.5
Note: See TracTickets for help on using tickets.