Semimonomial transformation groups code is sensitive to Permutations global options

[darijgr]

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.

CC: @sagetrac-tfeulner

Component: group theory

Keywords: permutation, semimonomial transformation

Author: Thomas Feulner

Branch/Commit: public/ticket/15576 @ cbb5110

Reviewer: Darij Grinberg

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

[sagetrac-tfeulner]

Branch: u/tfeulner/ticket/15576

[sagetrac-tfeulner]

Commit: c297a9a

[sagetrac-tfeulner]

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:

c297a9a

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

[darijgr]

comment:3

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?

[sagetrac-git]

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

d8cd6e3

Minor changes to the documentation.

[sagetrac-git]

Changed commit from c297a9a to d8cd6e3

[sagetrac-tfeulner]

comment:5

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.

[darijgr]

comment:6

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!

[sagetrac-git]

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

6155cf9

Improved documentation

[sagetrac-git]

Changed commit from d8cd6e3 to 6155cf9

[sagetrac-tfeulner]

comment:8

Replying to @darijgr:

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.

[darijgr]

comment:9

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.

[darijgr]

comment:10

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.

[sagetrac-tfeulner]

Changed branch from u/tfeulner/ticket/15576 to public/ticket/15576

[sagetrac-tfeulner]

Changed commit from 6155cf9 to cbb5110

[sagetrac-tfeulner]

New commits:

adac1c9	Merge branch 'u/tfeulner/ticket/15576' of trac.sagemath.org:sage into 15576
cbb5110	some more doc fixes

[sagetrac-tfeulner]

comment:14

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.

[vbraun]

comment:15

Please fill in the author/reviewer fields

[darijgr]

Author: Thomas Feulner

[darijgr]

Reviewer: Darij Grinberg