Wrong matrix of Permutation

[Paul Mercat]

Hi !

Sage doesn't compute correctly the matrix of a Permutation:

matrix(Permutation('(1,2,3,4)'))

return a wrong answer: it returns the inverse of the correct result.
The product of matrices of permutations must be equal to the matrix of the composition.

If we do:

PermutationGroup([(1,2,3,4)]).gens()[0].matrix()

then we get the correct result.

[Paul Mercat]

Another bug with PermutationGroup:

{{

g1,g2 = PermutationGroup([(1,2,3,4), (1,3,2,4)]).gens()
(g1*g2)(3), g1(g2(3))

}}

should gives two times the same result, but it is not the case...

The action of the group on {1,2,3,4} is not an action !

[Michael Orlitzky]

On 2020-06-15 10:58, 'Paul Mercat' via sage-devel wrote:
> Hi !
>
> Sage doesn't compute correctly the matrix of a Permutation:
>
> matrix(Permutation('(1,2,3,4)'))
>
> return a wrong answer: it returns the inverse of the correct result.
> The product of matrices of permutations must be equal to the matrix of
> the composition.
>

Since the inverse is the transpose in this case, this is probably just
the result of one person having left-application in mind and another
having right-application in mind. The documentation doesn't say which
one you'll get; that should be changed too.

[David Joyner]

On Mon, Jun 15, 2020 at 11:21 AM 'Paul Mercat' via sage-devel <sage-...@googlegroups.com> wrote:

Another bug with PermutationGroup:

{{

g1,g2 = PermutationGroup([(1,2,3,4), (1,3,2,4)]).gens()
(g1*g2)(3), g1(g2(3))

}}

should gives two times the same result, but it is not the case...

The action of the group on {1,2,3,4} is not an action !

Did you mean to say the action on {1,2,3,4} is not a left action?

Some prefer right actions....

 

Le lundi 15 juin 2020 16:58:18 UTC+2, Paul Mercat a écrit :

Hi !

Sage doesn't compute correctly the matrix of a Permutation:

matrix(Permutation('(1,2,3,4)'))

return a wrong answer: it returns the inverse of the correct result.
The product of matrices of permutations must be equal to the matrix of the composition.

If we do:

PermutationGroup([(1,2,3,4)]).gens()[0].matrix()

then we get the correct result.

--
You received this message because you are subscribed to the Google Groups "sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/e4095a01-08f8-4aa1-924d-2c4494aeddd3o%40googlegroups.com.

[Paul Mercat]

Thank you for your answers.

It's very confusing to write a right action to the left : we write g(i) and not (i)g.

By default it should be a left action.

And its very confusing that PermutationGroup and Permutation doesn't give the same matrix for the same permutation.
I think that Sage should be coherent with itself as much as possible, and that it should choose the most natural convention.

Best regards,

Paul

Le lundi 15 juin 2020 17:30:33 UTC+2, David Joyner a écrit :

On Mon, Jun 15, 2020 at 11:21 AM 'Paul Mercat' via sage-devel <sage-...@googlegroups.com> wrote:

Another bug with PermutationGroup:

{{

g1,g2 = PermutationGroup([(1,2,3,4), (1,3,2,4)]).gens()
(g1*g2)(3), g1(g2(3))

}}

should gives two times the same result, but it is not the case...

The action of the group on {1,2,3,4} is not an action !

Did you mean to say the action on {1,2,3,4} is not a left action?

Some prefer right actions....

 

Le lundi 15 juin 2020 16:58:18 UTC+2, Paul Mercat a écrit :

Hi !

Sage doesn't compute correctly the matrix of a Permutation:

matrix(Permutation('(1,2,3,4)'))

return a wrong answer: it returns the inverse of the correct result.
The product of matrices of permutations must be equal to the matrix of the composition.

If we do:

PermutationGroup([(1,2,3,4)]).gens()[0].matrix()

then we get the correct result.

--
You received this message because you are subscribed to the Google Groups "sage-devel" group.

To unsubscribe from this group and stop receiving emails from it, send an email to sage-...@googlegroups.com.

[Dima Pasechnik]

Group theory convention for composition is the same as in GAP and Magma. It would be crazy to change it for a variety of reasons...

Whereas Permutation comes from combinatorics, I don't know why they took a different default.

To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/fa42b74e-c614-426e-96c3-bd7fe48ad4d4o%40googlegroups.com.

[David Joyner]

On Mon, Jun 15, 2020 at 11:42 AM 'Paul Mercat' via sage-devel <sage-...@googlegroups.com> wrote:

Thank you for your answers.

It's very confusing to write a right action to the left : we write g(i) and not (i)g.

By default it should be a left action.

And its very confusing that PermutationGroup and Permutation doesn't give the same matrix for the same permutation.
I think that Sage should be coherent with itself as much as possible, and that it should choose the most natural convention.

This is turning into a political discussion:-)  I'm not taking sides! 

You can say something similar about left-kernels vs right-kernels of 

matrices, about left-eigenvectors vs right-eigenvectors. Different

linear algebra textbooks are different. Likewise, for permutations

acting on the left vs the right. Different group theory textbooks are

different. 

Personally, I find it easier to get used to what is coded up than to rewrite code:-)

To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/fa42b74e-c614-426e-96c3-bd7fe48ad4d4o%40googlegroups.com.

[Nils Bruin]

On Monday, June 15, 2020 at 9:11:08 AM UTC-7, David Joyner wrote:

This is turning into a political discussion:-)  I'm not taking sides! 

You can say something similar about left-kernels vs right-kernels of 

matrices, about left-eigenvectors vs right-eigenvectors. Different

linear algebra textbooks are different. Likewise, for permutations

acting on the left vs the right. Different group theory textbooks are

different. 

Personally, I find it easier to get used to what is coded up than to rewrite code:-)

There's obviously the choice for letting permutations/matrices on the left/right, but I think there's a definite preferred choice for how to convert to a permutation matrix: the one that makes it a homomorphism. And for that, "Permutation" fails presently:

sage: matrix(Permutation('(1,2,3)')*Permutation('(1,3)')) == matrix(Permutation('(1,2,3)'))*matrix(Permutation('(1,3)'))
False

Permutation groups (via gap) obviously get this right:

sage: S3=SymmetricGroup(3)

sage: (S3((1,2,3))*S3((1,3))).matrix() == S3((1,2,3)).matrix()*S3((1,3)).matrix()
True

I can't find explicit documentation that matrix(Permutation(...)) is a recommended way of converting a permutation to a permutation matrix. The code path through "matrix" is rather convoluted, because that's a routine that tries so many things to make sense of its arguments. It may well be that this works only accidentally, in which a solution would be to explicitly block it.

I do think the current behaviour can be considered a bug, though. Given a choice between a homomorphism and an anti-homomorphism between a permutation group and a matrix group, there is a clear preference. Possible fixes are clear

 1) Change the multiplication convention on Permutation

 2) Change the way matrix produces a matrix from a Permutation (transpose)

 3) Block matrix from doing this at all (and perhaps provide a method on Permutation?)

[4) Change the convention for matrix multiplication]

[Nils Bruin]

On Monday, June 15, 2020 at 10:43:51 AM UTC-7, Nils Bruin wrote:

There's obviously the choice for letting permutations/matrices on the left/right, but I think there's a definite preferred choice for how to convert to a permutation matrix: the one that makes it a homomorphism. And for that, "Permutation" fails presently:

sage: matrix(Permutation('(1,2,3)')*Permutation('(1,3)')) == matrix(Permutation('(1,2,3)'))*matrix(Permutation('(1,3)'))
False

To make things worse, there is actually an option to fix this:

sage: sage.combinat.permutation.Permutations.options(mult="r2l")

sage: matrix(Permutation('(1,2,3)')*Permutation('(1,3)')) == matrix(Permutation('(1,2,3)'))*matrix(Permutatio

....: n('(1,3)'))

Quoting from the documentation:

     It is best  for code not to rely on this setting being set to a particular
     standard, but rather use the methods "left_action_product()" and
     "right_action_product()" for multiplying permutations (these
     methods don't depend on the setting). See
     https://trac.sagemath.org/14885 for more details.

so, "Permutation" objects aren't really meant to be a group: they are just objects on which two different groups can be overlaid (the opposites). So that means "matrix" can't possibly get it right in all cases. There should be a left_action_permutation_matrix and right_action_permutation_matrix on Permutation objects.

[Travis Scrimshaw]

We also recently had a ticket about correcting the permutation action on a matrix, so we also need that to also be consistent.

Best,

Travis

[kcrisman]

so, "Permutation" objects aren't really meant to be a group:

I think this is the salient point.   Is there any documentation that already has matrix(Permutation(...)) ? 

For several more points of view (some articulated by people on the current thread), see also the (long) discussion that the ticket you mention led to on this forum, seven years ago: https://groups.google.com/forum/#!topic/sage-devel/tAAb42Edh9o

[Nils Bruin]

On Tuesday, June 16, 2020 at 4:40:45 AM UTC-7, kcrisman wrote:

For several more points of view (some articulated by people on the current thread), see also the (long) discussion that the ticket you mention led to on this forum, seven years ago: https://groups.google.com/forum/#!topic/sage-devel/tAAb42Edh9o

That's quite a thread. One thing I'd like to highlight from there that didn't seem to get so much traction is a point Marco Streng made about possible notations for right actions:

If G is a group acting on the right on a ring R, and a,b in R and s in G then denoting right-action by right-multiplication has a problem:

(a*b)*s would suggest it's equal to a*(b*s), which it is generally not. Exponential notation (a*b)^s does not suffer from this problem. That disqualifies right-multiplication as a general notation for right-actions to me.

[Dima Pasechnik]

It becomes more evident if one has to compose not necessarily
invertible linear maps.

E.g. if one wants to represent linear maps A:F^n -> F^m by matrices,
so that A(v), for v in F^n, be given by the matrix/vector multiplication Av,
then A should be mxn matrix. Then, if B:F^m->F^k (and so B is kxm) the
composition B(A(v)) is matrix product BAv.

And one needs to explain why to form the composition F^n-A->F^m-B->F^k
one has to do BA:F^n->F_k.

So in order to retain the convenience of A(v) being Av, one has to
accept that the order of composition is swapped.
Or write A(v) as vA, then A is nxm, and B(A(v)) is vAB.

Dima

>
>
> --
> You received this message because you are subscribed to the Google Groups "sage-devel" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+...@googlegroups.com.

> To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/fadeb1c0-73ea-427f-9337-5b627bf7b224o%40googlegroups.com.

[Markus Wageringel]

Am Dienstag, 16. Juni 2020 13:40:45 UTC+2 schrieb kcrisman:

so, "Permutation" objects aren't really meant to be a group:

I think this is the salient point.   Is there any documentation that already has matrix(Permutation(...)) ? 

 

The documentation of Permutation.to_matrix states this:

    Notice that matrix multiplication corresponds to permutation multiplication only when the permutation option mult=’r2l’

I am not sure why exactly it was implemented like this, but I imagine this makes it generally more predictable, as the conversion to matrices does not depend on a global option of Permutations.

 

[Markus Wageringel]

Am Dienstag, 16. Juni 2020 19:03:40 UTC+2 schrieb Nils Bruin:

That's quite a thread. One thing I'd like to highlight from there that didn't seem to get so much traction is a point Marco Streng made about possible notations for right actions:

If G is a group acting on the right on a ring R, and a,b in R and s in G then denoting right-action by right-multiplication has a problem:

(a*b)*s would suggest it's equal to a*(b*s), which it is generally not. Exponential notation (a*b)^s does not suffer from this problem. That disqualifies right-multiplication as a general notation for right-actions to me.

I would also be in favor of using a different notation for actions. My suggestion would be to use the shift operator << to denote right actions and, similarly, the right shift operator >> for left actions. This makes it explicit what kind operation is intended; for example, `a*b << s*t` and `a*b << s << t` would do exactly what one expects.

This notation can be thought of as a generalization of the bitwise << operation if one interprets it as a monoid action of (ℕ,+). The notation can be used for both multiplicative and additive groups.

As the shift operators are not common mathematical operators, it is less likely to confuse them with actual mathematical operations like exponentiation or multiplication. This could also resolve otherwise ambiguous cases, such as the Weyl algebra acting on the polynomial ring, where multiplication already has a different meaning.

If one wants, one could even define the action of permutations on permutations themselves and, thus, distinguish between left-to-right and right-to-left multiplication via << and >>.

[kcrisman]

On Wednesday, June 17, 2020 at 6:01:31 PM UTC-4, Markus Wageringel wrote:

Am Dienstag, 16. Juni 2020 19:03:40 UTC+2 schrieb Nils Bruin:

That's quite a thread. One thing I'd like to highlight from there that didn't seem to get so much traction is a point Marco Streng made about possible notations for right actions:

If G is a group acting on the right on a ring R, and a,b in R and s in G then denoting right-action by right-multiplication has a problem:

(a*b)*s would suggest it's equal to a*(b*s), which it is generally not. Exponential notation (a*b)^s does not suffer from this problem. That disqualifies right-multiplication as a general notation for right-actions to me.

I would also be in favor of using a different notation for actions. My suggestion would be to use the shift operator << to denote right actions and, similarly, the right shift operator >> for left actions. This makes it explicit what kind operation is intended; for example, `a*b << s*t` and `a*b << s << t` would do exactly what one expects.

I assume that would need a pretty major change in the preparser?  Does other mathematical software use this as a convention?  (Just asking, no presuppositions here.) 

[Nils Bruin]

On Thursday, June 18, 2020 at 5:00:00 AM UTC-7, kcrisman wrote:

I assume that would need a pretty major change in the preparser?  Does other mathematical software use this as a convention?  (Just asking, no presuppositions here.) 

No, not the preparser. It would affect the coercion framework quite a bit, though. It would mean that __lshift__ and __rshift__ need to be hooked into left actions and right actions. Using ">>" and "<<" for actions has the large advantage that the methods are for the most part available. The coercion framework can already discover left and right multiplicative actions (used for scalar multiplication and matrix actions on modules), so I'd expect it can be made to discover "shift" actions by specifying the relevant operator. The operator precedence in python look way off, though: 1 + 3<<2 == 16.

I think it has the large drawback that it doesn't look like math notation at all, whereas function application and exponentiation does. I'd be uncomfortable using it.

To compare: magma has function-application-on-the right in the notation x@f and map composition f*g (for right action). So with

QQ:=Rationals();

f:=map<QQ->QQ|x:->x+1>;

g:=map<QQ->QQ|x:->x^2>;

1@(f*g) == 1@f@g == 4

Magma also has left application as a notational help, but then

(f*g)(1) == 1@(f*g) == 4 so function composition really doesn't work well with that notation.

Permutations just act on the right, with exponentiation as notation. So if

S3:=SymmetricGroup(3);
a:=S3!(1,2,3);
b:=S3!(1,2);

then this hold: 1^(a*b) == (1^a)^b

[Markus Wageringel]

Am 18.06.2020 um 19:47 schrieb Nils Bruin <nbr...@sfu.ca>:
>
> On Thursday, June 18, 2020 at 5:00:00 AM UTC-7, kcrisman wrote:
>
> I assume that would need a pretty major change in the preparser? Does other mathematical software use this as a convention? (Just asking, no presuppositions here.)
>
> No, not the preparser. It would affect the coercion framework quite a bit, though. It would mean that __lshift__ and __rshift__ need to be hooked into left actions and right actions. Using ">>" and "<<" for actions has the large advantage that the methods are for the most part available. The coercion framework can already discover left and right multiplicative actions (used for scalar multiplication and matrix actions on modules), so I'd expect it can be made to discover "shift" actions by specifying the relevant operator.

Indeed, this would not require changes to the preparser, as these are standard Python operators. I assume that we could implement the shift methods on SageObject (possibly with some special care for Integers that implement the bitwise shifts), which would then redirect to the appropriate discovery of the correct action that is already implemented. Cython actually helps us here because, instead of calling x.__lshift__(y), it automatically calls something like type(y).__lshift__(x, y) if __lshift__ is not implemented on x. This is useful if x is not a Sage type, but a Python type such as list or int, on which a permutation might act from the right.


As for other mathematical software, I do not know any that uses >> and << for group actions. However, I think it is rather common to use operators that are the same but flipped for operations that have a right- and left-minded variant. In Python, only the shift operators can be used for that, unless we extend the preparser.

The best example I can think of is that of the Monad bind operation >>= and Kleisli composition >=> in Haskell, which has also been adopted by several libraries in other languages. For a monad element m and Kleisli functions f and g, the following are the same

(m >>= f) >>= g
m >>= (f >=> g)

so this can be thought of as a right action. Similarly, the flipped operators exist:

f =<< (g =<< m)
(f <=< g) =<< m

Another common example of same-but-flipped operators is <<< and >>> for composition of arrows in a category/semigroupoid.

Other examples include Matlab's / and \ operators for matrix division, and the / and \ operator in Macaulay2 for mapping a function over a list. For example, the following are the same in Macaulay2

(1,2,3) / sqrt / sin
sin \ sqrt \ (1,2,3)
sin @@ sqrt \ (1,2,3)

so this is a left action. If one views permutations as bijective functions of {1,..,n}, the left action of permutations is a special case of this.

Admittedly, these operators do not look like mathematical notation, but they can still be useful for programming. In all the associativity laws above, mathematically one does not care about the execution order, but for programming it is still often relevant. I do not expect Sage/Python to embrace unicode operators the way, for example, Agda does [1], so this limits the options quite a bit.


[1] https://github.com/agda/agda-stdlib/blob/49fa0985b2e7ed8896174f4d7ecca92d4e8c847d/src/Algebra/Module/Bundles.agda#L145-L151

[Michael Orlitzky]

On 2020-06-18 13:47, Nils Bruin wrote:
>
> To compare: magma has function-application-on-the right in the notation x@f
> and map composition f*g (for right action). So with

Off-topic:

For some programming-language design trivia, the explicit syntax for
function application on the right has a lot going for it. Using
parentheses has well-known problems, particularly to anyone who has
taught the chain rule. They also make it awkward to curry functions of
multiple arguments. If I want to write the function that adds three to
its argument on a chalkboard, I have to make up some junk like
plus(3,--) with a dash or dot in the hole where the argument goes. In
python, I have to use e.g. lambda x: plus(3,x).

Many functional languages solve that problem by using spaces for
function application, and by treating all functions as functions of one
argument (that return other functions). So you would write

plus

for the function that takes an argument and returns (a function that
takes another argument and adds the first argument to it). Thus

plus 3

is the function that adds three to its argument, and

plus 3 4 = (plus 3) 4

is probably 7. Of course, that has problems too, not the least of which
is having the most important operation in the language be invisible and
generally unparseable. If I want to make a higher level function, how do
I apply some other function to a space? Is your language going to parse
" " as function application applied to function application? Nah. An
explicit visible application syntax solves those problems and others. To
keep the same example,

3@plus

would be what we want, and

4@3@plus = 4@(3@plus) = 7

Finally, working left-to-right eliminates all of the annoying problems
that arise when you do something to (f `compose` g) and everything
flips. It's also just nicer to read, because when you see

((x@foo)@bar)@baz

you can start reading, "I take x, and give it to foo; then I take the
result and feed it to bar..." Whereas with baz(bar(foo(x))) you have to
get all the way to the end before you can reverse engineer what's about
to happen. There is also usually shortcut for function composition
mentioned, so that the parentheses above can be avoided above, like

x@foo;bar;baz

The paper "A useful lambda-notation" by Fairouz Kamareddine and Rob
Nederpelt was once recommended to me on this same topic. Curiously
(after I spent 2 months figuring out how to read it), the "item
notation" they devise for the lambda calculus is basically "@".

But @ is matrix multiplication in python, so we're screwed there =)

[John Cremona]

I would like to vote for exponentiation for a right group action.  This is standard mathematical notation (as has already been said), at least in several fields that I know of.  Using the shift operators looks too much like a computer-sciency solution to me.  Sage has always tried to keep its notation close to what a mathematician (including students) would expect -- for example (almost the only one), re-purposing ^ to mean exponentiation rather than the python default.

All students learning permutations get confused about the order of multiplcation and just need to learn that there are two conventions and you *have to* know which is being used when you read something since otherwise half of what you read will not make sense.

When I was a student I had two tutors who I handed work in to each week.  One was (is) a group theorist (https://en.wikipedia.org/wiki/Peter_M._Neumann) for whom we had to write xf for the result of applying function f to object x, so fg meant "do f then g".  The other was/is an analyst who only allowed f(x) and the other convention.  I had to keep both happy (and get the right answers) so I leant fast.

John

[Dima Pasechnik]

On Fri, 19 Jun 2020, 09:05 John Cremona, <john.c...@gmail.com> wrote:

I would like to vote for exponentiation for a right group action.  This is standard mathematical notation (as has already been said), at least in several fields that I know of.  Using the shift operators looks too much like a computer-sciency solution to me.  Sage has always tried to keep its notation close to what a mathematician (including students) would expect -- for example (almost the only one), re-purposing ^ to mean exponentiation rather than the python default.

I don't know how to reconcile this with group theory use of exponentiation for the conjugation action(s).

All students learning permutations get confused about the order of multiplcation and just need to learn that there are two conventions and you *have to* know which is being used when you read something since otherwise half of what you read will not make sense.

When I was a student I had two tutors who I handed work in to each week.  One was (is) a group theorist (https://en.wikipedia.org/wiki/Peter_M._Neumann) for whom we had to write xf for the result of applying function f to object x, so fg meant "do f then g".  The other was/is an analyst who only allowed f(x) and the other convention.  I had to keep both happy (and get the right answers) so I leant fast.

John

--

You received this message because you are subscribed to the Google Groups "sage-devel" group.
To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/a0d38f53-cbf0-4667-9ba1-ab6a3b0c48dbo%40googlegroups.com.

[John Cremona]

On Fri, 19 Jun 2020 at 09:39, Dima Pasechnik <dim...@gmail.com> wrote:
>
>
>
> On Fri, 19 Jun 2020, 09:05 John Cremona, <john.c...@gmail.com> wrote:
>>
>> I would like to vote for exponentiation for a right group action. This is standard mathematical notation (as has already been said), at least in several fields that I know of. Using the shift operators looks too much like a computer-sciency solution to me. Sage has always tried to keep its notation close to what a mathematician (including students) would expect -- for example (almost the only one), re-purposing ^ to mean exponentiation rather than the python default.
>
>
> I don't know how to reconcile this with group theory use of exponentiation for the conjugation action(s).

I had not thought of that. But if you want to write h^g for the
conjugate of h by g and you want this to be a right action, so that
g^(h1*h2) = (g^h1)^h2, then that is fine provided that "the conjugate
of h by g" means g^(-1)*h*g.

It's really the same issue. If instead you think of "the conjugate of
h by g" as meaning g*h*g^(-1) the you have a left action and so the
notation h^g is *not* appropriate! I would write that instead using
left exponentiation, i.e. ${}^gh = ghg^{-1}$ in tex notation.

Are you now reconciled, Dima?

John

>
>>
>> All students learning permutations get confused about the order of multiplcation and just need to learn that there are two conventions and you *have to* know which is being used when you read something since otherwise half of what you read will not make sense.
>>
>> When I was a student I had two tutors who I handed work in to each week. One was (is) a group theorist (https://en.wikipedia.org/wiki/Peter_M._Neumann) for whom we had to write xf for the result of applying function f to object x, so fg meant "do f then g". The other was/is an analyst who only allowed f(x) and the other convention. I had to keep both happy (and get the right answers) so I leant fast.
>>
>> John
>>
>> --
>> You received this message because you are subscribed to the Google Groups "sage-devel" group.
>> To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+...@googlegroups.com.
>> To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/a0d38f53-cbf0-4667-9ba1-ab6a3b0c48dbo%40googlegroups.com.
>
> --

> You received this message because you are subscribed to a topic in the Google Groups "sage-devel" group.
> To unsubscribe from this topic, visit https://groups.google.com/d/topic/sage-devel/f-wvE2S2LrA/unsubscribe.
> To unsubscribe from this group and all its topics, send an email to sage-devel+...@googlegroups.com.
> To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/CAAWYfq2pFjZs8HxRSGGveH5Z%3D_AtkbCEstUG91Si0De5s%3D7f%2Bg%40mail.gmail.com.

[Dima Pasechnik]

On Fri, Jun 19, 2020 at 10:14 AM John Cremona <john.c...@gmail.com> wrote:
>
> On Fri, 19 Jun 2020 at 09:39, Dima Pasechnik <dim...@gmail.com> wrote:
> >
> >
> >
> > On Fri, 19 Jun 2020, 09:05 John Cremona, <john.c...@gmail.com> wrote:
> >>
> >> I would like to vote for exponentiation for a right group action. This is standard mathematical notation (as has already been said), at least in several fields that I know of. Using the shift operators looks too much like a computer-sciency solution to me. Sage has always tried to keep its notation close to what a mathematician (including students) would expect -- for example (almost the only one), re-purposing ^ to mean exponentiation rather than the python default.
> >
> >
> > I don't know how to reconcile this with group theory use of exponentiation for the conjugation action(s).
>
> I had not thought of that. But if you want to write h^g for the
> conjugate of h by g and you want this to be a right action, so that
> g^(h1*h2) = (g^h1)^h2, then that is fine provided that "the conjugate
> of h by g" means g^(-1)*h*g.
>
> It's really the same issue. If instead you think of "the conjugate of
> h by g" as meaning g*h*g^(-1) the you have a left action and so the
> notation h^g is *not* appropriate! I would write that instead using
> left exponentiation, i.e. ${}^gh = ghg^{-1}$ in tex notation.

My problem is that if a group acts on itself, conjugation actions (be
it h|->ghg^-1 or h|->g^-1 hg)
are vastly different from regular actions (left or right).

How are you going to use '^' for both?

>
> Are you now reconciled, Dima?
>
> John
>
> >
> >>
> >> All students learning permutations get confused about the order of multiplcation and just need to learn that there are two conventions and you *have to* know which is being used when you read something since otherwise half of what you read will not make sense.
> >>
> >> When I was a student I had two tutors who I handed work in to each week. One was (is) a group theorist (https://en.wikipedia.org/wiki/Peter_M._Neumann) for whom we had to write xf for the result of applying function f to object x, so fg meant "do f then g". The other was/is an analyst who only allowed f(x) and the other convention. I had to keep both happy (and get the right answers) so I leant fast.
> >>
> >> John
> >>
> >> --
> >> You received this message because you are subscribed to the Google Groups "sage-devel" group.
> >> To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+...@googlegroups.com.
> >> To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/a0d38f53-cbf0-4667-9ba1-ab6a3b0c48dbo%40googlegroups.com.
> >
> > --
> > You received this message because you are subscribed to a topic in the Google Groups "sage-devel" group.
> > To unsubscribe from this topic, visit https://groups.google.com/d/topic/sage-devel/f-wvE2S2LrA/unsubscribe.
> > To unsubscribe from this group and all its topics, send an email to sage-devel+...@googlegroups.com.
> > To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/CAAWYfq2pFjZs8HxRSGGveH5Z%3D_AtkbCEstUG91Si0De5s%3D7f%2Bg%40mail.gmail.com.
>
> --
> You received this message because you are subscribed to the Google Groups "sage-devel" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+...@googlegroups.com.

> To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/CAD0p0K7wp5kaJ6KjFj7Tr5qNZuVkon3DM%2BSL%2B7c%3DDMo7tthP1w%40mail.gmail.com.

[John Cremona]

On Fri, 19 Jun 2020 at 10:24, Dima Pasechnik <dim...@gmail.com> wrote:
>
> On Fri, Jun 19, 2020 at 10:14 AM John Cremona <john.c...@gmail.com> wrote:
> >
> > On Fri, 19 Jun 2020 at 09:39, Dima Pasechnik <dim...@gmail.com> wrote:
> > >
> > >
> > >
> > > On Fri, 19 Jun 2020, 09:05 John Cremona, <john.c...@gmail.com> wrote:
> > >>
> > >> I would like to vote for exponentiation for a right group action. This is standard mathematical notation (as has already been said), at least in several fields that I know of. Using the shift operators looks too much like a computer-sciency solution to me. Sage has always tried to keep its notation close to what a mathematician (including students) would expect -- for example (almost the only one), re-purposing ^ to mean exponentiation rather than the python default.
> > >
> > >
> > > I don't know how to reconcile this with group theory use of exponentiation for the conjugation action(s).
> >
> > I had not thought of that. But if you want to write h^g for the
> > conjugate of h by g and you want this to be a right action, so that
> > g^(h1*h2) = (g^h1)^h2, then that is fine provided that "the conjugate
> > of h by g" means g^(-1)*h*g.
> >
> > It's really the same issue. If instead you think of "the conjugate of
> > h by g" as meaning g*h*g^(-1) the you have a left action and so the
> > notation h^g is *not* appropriate! I would write that instead using
> > left exponentiation, i.e. ${}^gh = ghg^{-1}$ in tex notation.
>
> My problem is that if a group acts on itself, conjugation actions (be
> it h|->ghg^-1 or h|->g^-1 hg)
> are vastly different from regular actions (left or right).
>
> How are you going to use '^' for both?

I was not: in fact I said "I would like to vote for exponentiation for
a right group action". Only for right actions! For left actions
we can use * (with the group element which is acting on the left of
the *), though that could be confusing if the group was acting on
itself on the left not by the left regular action (e.g. by
conjugation). Let's face it, a group can have many different left or
right actions on the same set so whatever symbol we choose, somewhere
we'll have to specify which action we mean. In a mathematical text
you just give the definition and that's it. Here too then the action
intended must be defined somewhere, deducible from the types/parents
of the objects concerned. In the context of the original post we have
a finite set {1,2,...,n} and the symmetric group acting on it. And
also some vector space and matrices acting: either on the left, on
column vectors, or on the right, on row vectors. For these, Sage uses
* for both and (as you know of course) does not distinguish between
row and column vectors except by context:

sage: v2 = vector([1,2])
sage: v2
(1, 2)
sage: v3 = vector([1,2,3])
sage: v3
(1, 2, 3)
sage: m23 = matrix([[11,12,13],[21,22,23]])
sage: m23
[11 12 13]
[21 22 23]
sage: v2*m23
(53, 56, 59)
sage: m23*v3
(74, 134)

(while of course v3*m23 and m23*v2 raise errors). This is all good.
If we were to allow ^ for right action of a matrix on a (row) vector
that would probably be OK but we certainly should not take away the
ability to use * as well for the same thing (as in m23*v3) or many
loud objections would be raised.

By the way, I think it may be true that the preparser changes every ^
into ** so if we did introduce ^ for a right group action for use
from the command line it would have to be implemented as **; for .py
files I hope we could actually implement ^ to be used as itself.

>
>
> >
> > Are you now reconciled, Dima?
> >
> > John
> >
> > >
> > >>
> > >> All students learning permutations get confused about the order of multiplcation and just need to learn that there are two conventions and you *have to* know which is being used when you read something since otherwise half of what you read will not make sense.
> > >>
> > >> When I was a student I had two tutors who I handed work in to each week. One was (is) a group theorist (https://en.wikipedia.org/wiki/Peter_M._Neumann) for whom we had to write xf for the result of applying function f to object x, so fg meant "do f then g". The other was/is an analyst who only allowed f(x) and the other convention. I had to keep both happy (and get the right answers) so I leant fast.
> > >>
> > >> John
> > >>
> > >> --
> > >> You received this message because you are subscribed to the Google Groups "sage-devel" group.
> > >> To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+...@googlegroups.com.
> > >> To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/a0d38f53-cbf0-4667-9ba1-ab6a3b0c48dbo%40googlegroups.com.
> > >
> > > --
> > > You received this message because you are subscribed to a topic in the Google Groups "sage-devel" group.
> > > To unsubscribe from this topic, visit https://groups.google.com/d/topic/sage-devel/f-wvE2S2LrA/unsubscribe.
> > > To unsubscribe from this group and all its topics, send an email to sage-devel+...@googlegroups.com.
> > > To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/CAAWYfq2pFjZs8HxRSGGveH5Z%3D_AtkbCEstUG91Si0De5s%3D7f%2Bg%40mail.gmail.com.
> >
> > --
> > You received this message because you are subscribed to the Google Groups "sage-devel" group.
> > To unsubscribe from this group and stop receiving emails from it, send an email to sage-devel+...@googlegroups.com.
> > To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/CAD0p0K7wp5kaJ6KjFj7Tr5qNZuVkon3DM%2BSL%2B7c%3DDMo7tthP1w%40mail.gmail.com.
>
> --
> You received this message because you are subscribed to a topic in the Google Groups "sage-devel" group.
> To unsubscribe from this topic, visit https://groups.google.com/d/topic/sage-devel/f-wvE2S2LrA/unsubscribe.
> To unsubscribe from this group and all its topics, send an email to sage-devel+...@googlegroups.com.

> To view this discussion on the web visit https://groups.google.com/d/msgid/sage-devel/CAAWYfq1jUGEMB8GQLBDmxPTi9S0--bOzXO%3DpnBag-s1xdSNctw%40mail.gmail.com.

[Nils Bruin]

On Friday, June 19, 2020 at 2:24:55 AM UTC-7, Dima Pasechnik wrote:

My problem is that if a group acts on itself, conjugation actions (be
it h|->ghg^-1 or h|->g^-1 hg)
are vastly different from regular actions (left or right).

How are you going to use '^' for both?

I think in mathematics this problem does not usually arise: Groups have a left- and right- coset action on their underlying sets, but that's not an action that respects the group structure. They also have a left- and right-conjugation action on themselves which does respect the group operation. So you can tell from the category which action is being considered.

We already have left- and right-multiplication to denote the coset actions (because that's where the action comes from!)

Hence, the choice in mathematics to use exponentiation for (right) conjugation a^s=s^(-1)*a*s. Left conjugation is a little harder to denote, because we don't have a convenient way of writing "presuperscripts", but that's an area where also in math notation you need to get careful. The obvious way would be to define left: G->Aut(G) and write left(s)(a) [or in math probably left_s(a)] 

I don't think the discussion here is to abolish all multiplicatively written actions. I'm pretty sure people don't want to start writing scalar multiplication as exponentiation. I read it more are an exploration of what tools are/should be available for denoting actions that aren't conveniently denoted multiplicatively. It looks to me like there is a significant consensus (and prior art) that function application (for left action) and exponentiation (for right action) are reasonable options, and that it's slightly unfortunate that there's no convenient notation in python for applying functions from the right, but that any "fix" of that is worse than the problem.

If we were to use method notation, then there's a ridiculous asymmetry: for right actions, acted-upon elements would need to know about the action:

a.right_action(s)

and for left-actions, the group elements would have to know how to act:

s.left_action(a)

All this disappears once we are happy using functions with two parameters as "action operation":

left = G.acting_on_the_left_on(M) # or left = M.left_action_by(G)

left(g,m)

left = G.acting_on_the_right_on(M) # or left = M.right_action_by(G)

right(m,g)

in cases where we're running out of action notations, I'd far prefer seeing this explicitly labelled notation.

[Markus Wageringel]

Am Freitag, 19. Juni 2020 18:40:34 UTC+2 schrieb Nils Bruin:

All this disappears once we are happy using functions with two parameters as "action operation":

left = G.acting_on_the_left_on(M) # or left = M.left_action_by(G)

left(g,m)

left = G.acting_on_the_right_on(M) # or left = M.right_action_by(G)

right(m,g)

This functionality is already available for actions that are actually implemented via Action:

sage: G = SymmetricGroup(3)
sage: M = MatrixSpace(QQ, 3)
sage: right = coercion_model.get_action(M, G)
sage: right(M.diagonal_matrix([1,2,3]), G('(2,3)'))  # with #29808
⎛1 0 0⎞
⎜0 0 2⎟
⎝0 3 0⎠

For cases where this is not implemented, it is possible to construct and register custom actions (a factory function for this might be useful). For example, the right action of the symmetric group on the integers via exponentiation:

sage: class CallAction(sage.categories.action.Action):
....:     def _act_(self, g, a):
....:         return g(a)
sage: G = SymmetricGroup(3); g, h = G('(1,2,3)'), G('(2,3)')
sage: right = CallAction(G, ZZ, is_left=False, op=operator.pow)
sage: right(right(1, g), h)
3
sage: ZZ._unset_coercions_used()
sage: ZZ.register_action(right)
sage: (1 ^ g) ^ h
3
sage: 1 ^ (g * h)
3

It is not currently possible to use shift operators for this, as they are not implemented in sage.structure.element. Also, it might not be easily possible to support the operator syntax for actions on non-Sage types such as Python lists.