Opened 8 months ago

Closed 8 months ago

#15576 closed defect (fixed)

Semimonomial transformation groups code is sensitive to Permutations global options

Reported by: darij Owned by:
Priority: major Milestone: sage-6.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 8 months ago by tfeulner

  • Branch set to u/tfeulner/ticket/15576
  • Created changed from 12/23/13 10:52:02 to 12/23/13 10:52:02
  • Modified changed from 12/23/13 10:52:02 to 12/23/13 10:52:02

comment:2 in reply to: ↑ description Changed 8 months ago by tfeulner

  • Commit set to c297a9af188fe1cde3fe9e12abf266b0fbea6be5

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:

c297a9aMake semimonomial transformations independent on the global variable governing product order of multiplications.

comment:3 Changed 8 months ago by darij

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?

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

comment:4 Changed 8 months ago by git

  • Commit changed from c297a9af188fe1cde3fe9e12abf266b0fbea6be5 to d8cd6e3c3a59c98b3b68f2de22e12b805ffbdc23

Branch pushed to git repo; I updated commit sha1. New commits:

d8cd6e3Minor changes to the documentation.

comment:5 Changed 8 months ago by tfeulner

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 follow-up: Changed 8 months ago by 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 self-contained. (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(n-1)}))` 

you are using 0-based 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 8 months ago by git

  • Commit changed from d8cd6e3c3a59c98b3b68f2de22e12b805ffbdc23 to 6155cf9ce606b77b6c70c84a106430e9068e15c2

Branch pushed to git repo; I updated commit sha1. New commits:

6155cf9Improved documentation

comment:8 in reply to: ↑ 6 Changed 8 months ago by tfeulner

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 self-contained. (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 8 months ago by darij

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.

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

comment:10 Changed 8 months ago by darij

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 8 months ago by tfeulner

  • Branch changed from u/tfeulner/ticket/15576 to public/ticket/15576
  • Commit changed from 6155cf9ce606b77b6c70c84a106430e9068e15c2 to cbb5110ab7080629764e9ebeee44e117ad380ca6

New commits:

adac1c9Merge branch 'u/tfeulner/ticket/15576' of trac.sagemath.org:sage into 15576
cbb5110some more doc fixes

comment:12 Changed 8 months ago by tfeulner

  • Status changed from new to needs_review

comment:13 Changed 8 months ago by tfeulner

  • Status changed from needs_review to positive_review

comment:14 Changed 8 months ago by tfeulner

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 8 months ago by vbraun

Please fill in the author/reviewer fields

comment:16 Changed 8 months ago by darij

  • Authors set to Thomas Feulner
  • Reviewers set to Darij Grinberg

comment:17 Changed 8 months ago by vbraun

  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.