Revert SymmetricGroup.algebra change from #16678

[nthiery]

#16678 makes SymmetricGroup(n).algebra(K) return SymmetricGroupAlgebra(K,n).

This is nice in principle since SymmetricGroupAlgebra makes use of the specific properties of the symmetric group to provide more features (better implementation of the center, Yucis-Murphy elements, ...). However SymmetricGroupAlgebra is not a drop-in replacement for the plain group algebra of the symmetric group. In particular it breaks several assumptions of .algebra like the fact that the basis of G.algebra(K) is indexed by elements of G (here the basis is indexed by plain Permutation's); it is therefore likely to create bugs and confusion.

This ticket reverts SymmetricGroup.algebra to the default behavior. See #16926 for a proper plan to endow it with the additional structure of SymmetricGroupAlgebra.

CC: @sagetrac-sage-combinat @tscrim @darijgr @avirmaux

Component: combinatorics

Reviewer: Nicolas M. Thiéry

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

[nthiery]

Branch: u/nthiery/revert_symmetricgroup_algebra_change_from__16678

[darijgr]

comment:3

I have a request. Could you add the fact that SymmetricGroup.algebra() != SymmetricGroupAlgebra to the doc, along with an explanation of how to get the SymmetricGroupAlgebra? Thanks.

---

New commits:

479fddb

16925: revert SymmetricGroups(...).algebra(...) to just do the standard thing

[darijgr]

Commit: 479fddb

[nthiery]

comment:4

Replying to @darijgr:

I have a request. Could you add the fact that SymmetricGroup.algebra() != SymmetricGroupAlgebra to the doc, along with an explanation of how to get the SymmetricGroupAlgebra? Thanks.

I considered this. It means leaving an algebra method in SymmetricGroup that does nothing but the standard thing, except for having an extra chunk of doc advertising SymmetricGroupAlgebra and the backward incompatibility issue. I can do that if you think that's helpful for the user.

Right now, I am running all tests after just stripping away the method.

[darijgr]

comment:5

Oops, I meant adding a mention of this to the class-wide doc. Overshadowing the method solely for this sake is too much of a hassle, sorry.

[nthiery]

comment:6

Replying to @darijgr:

Oops, I meant adding a mention of this to the class-wide doc. Overshadowing the method solely for this sake is too much of a hassle, sorry.

I am still hesitant actually. It's still nice to the user to warn him about the backward incompatibility flip-flop.

[sagetrac-git]

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

ce71c74

16925: updated a few doctests according to the previous commit

[sagetrac-git]

Changed commit from 479fddb to ce71c74

[nthiery]

comment:8

With the last commit, all tests passed. Haven't run long tests pass. Let's see what the bot says.

[avirmaux]

comment:9

Looks good to me...

[nthiery]

comment:10

For the record: it's actually a piece of luck that e.g. hecke_algebra_representations only needed a doctest update. The data structure of the element that was created behind the scene was actually corrupted since a term was internaly indexed by an element of SymmetricGroup whereas in the SymmetricGroupAlgebra elements are supposed to be indexed by Permutations. Any further operation on it would have lead to an explosion.

Granted: the overall infrastructure should have trapped the creation of such corrupt element; but that's a different discussion ...

[tscrim]

comment:11

I'm not quite sure about the (unwritten as far I can tell) assumption that G.algebra has a basis indexed by the elements of the group.

Here are some timings of the two implementations:

sage: S = SymmetricGroup(3)
sage: SGA = SymmetricGroupAlgebra(QQ, 3)
sage: GA = GroupAlgebra(S, QQ)
sage: %timeit L = list(GA.basis())
10 loops, best of 3: 23.3 ms per loop
sage: %timeit SL = list(SGA.basis())
1000 loops, best of 3: 775 µs per loop

sage: L = list(GA.basis())
sage: SL = list(SGA.basis())
sage: %timeit sum(L)
1000 loops, best of 3: 357 µs per loop
sage: %timeit sum(SL)
1000 loops, best of 3: 336 µs per loop
sage: %timeit prod(L)
1000 loops, best of 3: 466 µs per loop
sage: %timeit prod(SL)
1000 loops, best of 3: 1.28 ms per loop
sage: %timeit sum(L)^2
100 loops, best of 3: 2.26 ms per loop
sage: %timeit sum(SL)^2
100 loops, best of 3: 7.68 ms per loop

So getting the basis is significantly slower using the generic code, but multiplying elements is faster using the group.

Also going from the permutation group elements to a permutation is fast:

sage: lst = list(S)
sage: %timeit Permutation(lst[4])
10000 loops, best of 3: 69 µs per loop

although there is a slight bug:

sage: P3 = Permutations(3)
sage: P3(lst[4])
TypeError: object of type 'sage.groups.perm_gps.permgroup_element.PermutationGroupElement' has no len()

Multiplying permutation group elements is really fast compared to Sage's permutations:

sage: %timeit prod(lst)
100000 loops, best of 3: 2.27 µs per loop
sage: P3L = list(Permutations(3))
sage: %timeit prod(P3L)
1000 loops, best of 3: 446 µs per loop

So my proposal would be to change the indexing set of SymmetricGroupAlgebra to be the SymmetricGroup and add conversions to Sage's permutations where necessary.

[tscrim]

comment:12

Minor technical challenge (or perhaps question), we will have to deal with handling backwards compatibility with giving the basis an instance of our Permutation class.

[nthiery]

comment:13

Hi Travis,

Thanks for the timings!

Replying to @tscrim:

I'm not quite sure about the (unwritten as far I can tell) assumption that G.algebra has a basis indexed by the elements of the group.

    sage: S = DihedralGroup(3)
    sage: S.algebra?
    ... provided by Sets.ParentMethods.algebra ...
    This returns the K-free module with basis indexed by S, endowed
    with whatever structure can be induced from that of S.
    ...

So any subclass overriding algebra should satisfy those premises.

Here are some timings of the two implementations:
...
So getting the basis is significantly slower using the generic code,

To be precise: in both cases, the implementation of basis is the
same (provided by ModulesWithBasis). What we are seeing here is that
iterating through SymmetricGroup(n) is slower than iteration through
Permutations(n). Actually ridiculously slower:

sage: S = SymmetricGroup(6)
sage: %time l = list(S)
CPU times: user 1.05 s, sys: 29.2 ms, total: 1.08 s
Wall time: 1.19 s
sage: S = Permutations(6)
sage: %time l = list(S)
CPU times: user 27.6 ms, sys: 13.4 ms, total: 41 ms
Wall time: 34.2 ms

In principle the complexity should be fairly similar, even for a
generic permutation group implementation; there really must be a
glitch in the GAP/Sage communication given that GAP itself is about as
fast as Permutations:

sage: S = gap("SymmetricGroup(6)")
sage: %time l = S.List()
CPU times: user 21.7 ms, sys: 0 ns, total: 21.7 ms
Wall time: 33.9 ms

But we are deviating here. That's for a separate ticket.

So my proposal would be to change the indexing set of SymmetricGroupAlgebra to be the SymmetricGroup and add conversions to Sage's permutations where necessary.

This would be even more backward incompatible: people have been using
SymmetricGroupAlgebra for a long while, and some may have a specific
need for having it indexed by plain permutations. I prefer the
approach outlined here and in #16926.

Cheers,
Nicolas

[tscrim]

comment:14

Replying to @nthiery:

    sage: S = DihedralGroup(3)
    sage: S.algebra?
    ... provided by Sets.ParentMethods.algebra ...
    This returns the K-free module with basis indexed by S, endowed
    with whatever structure can be induced from that of S.
    ...

So any subclass overriding algebra should satisfy those premises.

I didn't interpret that as a contract, but just instead a statement about what the generic method returns. I think some more terse language is needed, such as adding "All classes overriding this method must return a K-module with basis indexed by S".

In principle the complexity should be fairly similar, even for a
generic permutation group implementation; there really must be a
glitch in the GAP/Sage communication given that GAP itself is about as
fast as Permutations:

sage: S = gap("SymmetricGroup(6)")
sage: %time l = S.List()
CPU times: user 21.7 ms, sys: 0 ns, total: 21.7 ms
Wall time: 33.9 ms

But we are deviating here. That's for a separate ticket.

It's possible that GAP is also slow, and I get similar behavior when using the Weyl group. However this is definitely something for a separate ticket.

This would be even more backward incompatible: people have been using
SymmetricGroupAlgebra for a long while, and some may have a specific
need for having it indexed by plain permutations. I prefer the
approach outlined here and in #16926.

It's (relatively) easy to get Sage's Permutations to compare equal to permutation group elements, as perm gp elts have a method called _gap_list, which returns the oneline notation and compares correctly to a Permutation. We would also need to change the hash for a (standard) Permutation to return a hash of the tuple of self (and we could do this generically by doing this first and if we need a fallback, use the hash of the string representation). This should allow the basis to take a Permutation and return the correct element (plus IMO they really should compare properly anyways).

At the end of the day, the biggest thing I don't like is having a generic implementation when there is a specialized implementation (which we agree on I believe). Reverting the change and having more classes (even with a good ABC) seems like a much harder maintenance task in the long run.

[nthiery]

comment:15

This can be set to duplicate of #16926 which is ready to go. We don't need anymore this intermediate step.

[vbraun]

comment:16

reviewer name

[darijgr]

Changed commit from ce71c74 to none

[darijgr]

Changed branch from u/nthiery/revert_symmetricgroup_algebra_change_from__16678 to none

[nthiery]

comment:18

Thanks Volker for the notice.

[nthiery]

Changed author from Nicolas M. Thiéry to none

[nthiery]

Reviewer: Nicolas M. Thiéry

[vbraun]

comment:19

there is no branch, did you delete it accidentally?

[darijgr]

comment:20

I deleted it because this branch is obsolete and a dead end. Or was this a wrong assumption?

[tscrim]

comment:21

The milestone wasn't changed to duplicate.