Opened 3 years ago
Closed 3 years ago
#15576 closed defect (fixed)
Semimonomial transformation groups code is sensitive to Permutations global options
Reported by:  darij  Owned by:  

Priority:  major  Milestone:  sage6.1 
Component:  group theory  Keywords:  permutation, semimonomial transformation, groups 
Cc:  tfeulner  Merged in:  
Authors:  Thomas Feulner  Reviewers:  Darij Grinberg 
Report Upstream:  N/A  Work issues:  
Branch:  public/ticket/15576 (Commits)  Commit:  cbb5110ab7080629764e9ebeee44e117ad380ca6 
Dependencies:  Stopgaps: 
Description
As detailed in #14885, it is not healthy for code to rely on the __mul__
operation on permutations, since this operation depends on the Permutations().global_options()['mul']
variable which can change at runtime. It is better to use the left_action_product
and right_action_product
methods introduced in #15174 (formerly known as _left_to_right_multiply_on_left
and _left_to_right_multiply_on_right
).
My tests show some dependence on the __mul__
method in sage/groups/semimonomial_transformations/semimonomial_transformation.pyx
and sage/groups/semimonomial_transformations/semimonomial_transformation_group.py
, although it might be that only one of these files depends on it and the other depends on the first file. Unfortunately I don't have time to study this in detail, as I'd first have to read up on the definitions.
Change History (17)
comment:1 Changed 3 years ago by
 Branch set to u/tfeulner/ticket/15576
 Created changed from 12/23/13 18:52:02 to 12/23/13 18:52:02
 Modified changed from 12/23/13 18:52:02 to 12/23/13 18:52:02
comment:2 in reply to: ↑ description Changed 3 years ago by
 Commit set to c297a9af188fe1cde3fe9e12abf266b0fbea6be5
comment:3 Changed 3 years ago by
Thanks for taking care of this. The dependency is gone indeed. Could you maybe also document the choice of multiplication order in the (module) documentation? And while at that:
A semimonomial transformation group over a ring `R` of length `n` is equal to the semidirect product of the monomial transformation group (also known as the complete monomial group) and the group of ring automorphisms.
either it should be "The semimonomial...", not "A semimonomial...", or it should be "a group of ring automorphisms", not "the group of ring automorphisms". In general, it should be impossible to compute the group of all automorphisms of a ring, so I suspect it's either "a group" or you are only considering finite fields?
comment:4 Changed 3 years ago by
 Commit changed from c297a9af188fe1cde3fe9e12abf266b0fbea6be5 to d8cd6e3c3a59c98b3b68f2de22e12b805ffbdc23
Branch pushed to git repo; I updated commit sha1. New commits:
d8cd6e3  Minor changes to the documentation.

comment:5 Changed 3 years ago by
Thanks for your comments. You are right, up to now it is only possible to construct the semimonomial group over a finite field. My plan for the future is to provide an optional package, which implements finite chain rings and semimonomial groups defined over them.
While we are at it, the Permutation.action
method also depends on the multiplication order. Personally, I do also prefer the multiplication of permutations from right to left. But since I am applying the permutation to a vector, there is no choice.
comment:6 followup: ↓ 8 Changed 3 years ago by
Where does Permutation.action
depend on the multiplication order? I agree, the function isn't very useful because it's easier to write it oneself than to figure out what exactly it does; but it seems to be selfcontained. (It also has significant space for optimization... whoever wrote it seems not to have realized that permutations can be iterated over. I'll fix this in a separate ticket.)
I prefer using R^{\times}
instead of R*
for the multiplicative group of units of R
(the latter notation could be a dual of R
and either way seems to be a typographic substitute), but this is probably a judgment call (particularly seeing that you use *
for multiplication).
In
`\psi^{\pi, \alpha} = (\alpha(\psi_{\pi(0)}), \ldots, \alpha(\psi_{\pi(n1)}))`
you are using 0based indexing of permutations; I'm not sure if this is what you want (it's doc, not code).
You speak of the semimonomial group over a ring R of either "length n" (in the definition) or "degree n" (in other parts of the doc). I think it would help to settle upon one notation (or define them both).
Other than this, the code looks fine. Thanks for the quick response, and set this to positive_review once the above issues are fixed!
comment:7 Changed 3 years ago by
 Commit changed from d8cd6e3c3a59c98b3b68f2de22e12b805ffbdc23 to 6155cf9ce606b77b6c70c84a106430e9068e15c2
Branch pushed to git repo; I updated commit sha1. New commits:
6155cf9  Improved documentation

comment:8 in reply to: ↑ 6 Changed 3 years ago by
Replying to darij:
Where does
Permutation.action
depend on the multiplication order? I agree, the function isn't very useful because it's easier to write it oneself than to figure out what exactly it does; but it seems to be selfcontained. (It also has significant space for optimization... whoever wrote it seems not to have realized that permutations can be iterated over. I'll fix this in a separate ticket.)
Well, what I wanted to say is, that we need two functions to implement the action of the permutation group on list/vectors of length n
, depending on the multiplication rule used for the definition of the symmetric group.
The current implementation of Permutation.action
corresponds to the action from the left and the multiplication defined by right_action_product
.
Using left_action_product
for the multiplication in the group and still acting from the left would force us to define the action method in the following way:
pi * (v_1, ..., v_n) := (v_{pi^{1}(1)}, ... , v_{pi^{1}(n)})
But this should become the topic of a separate ticket.
Thanks for your careful reading, I think I have fixed them all.
comment:9 Changed 3 years ago by
Attention: branch change!
I'm a bit surprised that you changed the definite articles back to the indefinites, so I'm suggesting to change them back in my commit. (Also, "the group of degree n over a ring R" sounds better than "the group over a ring R of degree n" to my ears.)
If my edits are OK to you, please set this to positive_review. Thanks for your work!
EDIT: I see what you mean by adding new action
methods, but frankly I don't see much of a point in those methods anyway. At least I can rewrite that functionality faster than I could read through the docstring to tell which of the many possible actions it implements.
comment:10 Changed 3 years ago by
Trac is preventing me from changing the branch to public/ticket/15576, so maybe you can just merge this into your branch or write a big fat warning message on the ticket.
comment:11 Changed 3 years ago by
 Branch changed from u/tfeulner/ticket/15576 to public/ticket/15576
 Commit changed from 6155cf9ce606b77b6c70c84a106430e9068e15c2 to cbb5110ab7080629764e9ebeee44e117ad380ca6
comment:12 Changed 3 years ago by
 Status changed from new to needs_review
comment:13 Changed 3 years ago by
 Status changed from needs_review to positive_review
comment:14 Changed 3 years ago by
Thanks for your help, Darij. All your changes look good to me.
Of course, an experienced programmer could write these action methods very quickly. But, by allowing the user to freely decide on the multiplication rule, you also have to think about these dependencies and modifiy the existing code.
comment:15 Changed 3 years ago by
Please fill in the author/reviewer fields
comment:16 Changed 3 years ago by
 Reviewers set to Darij Grinberg
comment:17 Changed 3 years ago by
 Resolution set to fixed
 Status changed from positive_review to closed
I think there should be only this single occurrence of the
__mul__
method in the file. Maybe you can check this with your tests?New commits:
Make semimonomial transformations independent on the global variable governing product order of multiplications.