Sage: Ticket #16925: Revert SymmetricGroup.algebra change from #16678
https://trac.sagemath.org/ticket/16925
<p>
<a class="closed ticket" href="https://trac.sagemath.org/ticket/16678" title="defect: Fix coercions for descent and symmetric group algebras (closed: fixed)">#16678</a> makes <code>SymmetricGroup(n).algebra(K)</code> return <code>SymmetricGroupAlgebra(K,n)</code>.
</p>
<p>
This is nice in principle since <code>SymmetricGroupAlgebra</code> makes use of the specific properties of the symmetric group to provide more features (better implementation of the center, Yucis-Murphy elements, ...). However <code>SymmetricGroupAlgebra</code> is not a drop-in replacement for the plain group algebra of the symmetric group. In particular it breaks several assumptions of <code>.algebra</code> like the fact that the basis of <code>G.algebra(K)</code> is indexed by elements of <code>G</code> (here the basis is indexed by plain <code>Permutation</code>'s); it is therefore likely to create bugs and confusion.
</p>
<p>
This ticket reverts <code>SymmetricGroup.algebra</code> to the default behavior. See <a class="closed ticket" href="https://trac.sagemath.org/ticket/16926" title="enhancement: Merge the features of SymmetricGroupAlgebra and SymmetricGroup.algebra (closed: fixed)">#16926</a> for a proper plan to endow it with the additional structure of <code>SymmetricGroupAlgebra</code>.
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/16925
Trac 1.1.6nthieryWed, 03 Sep 2014 11:41:54 GMTcc, description changed
https://trac.sagemath.org/ticket/16925#comment:1
https://trac.sagemath.org/ticket/16925#comment:1
<ul>
<li><strong>cc</strong>
<em>virmaux</em> added
</li>
<li><strong>description</strong>
modified (<a href="/ticket/16925?action=diff&version=1">diff</a>)
</li>
</ul>
TicketnthieryWed, 03 Sep 2014 11:55:52 GMTbranch set
https://trac.sagemath.org/ticket/16925#comment:2
https://trac.sagemath.org/ticket/16925#comment:2
<ul>
<li><strong>branch</strong>
set to <em>u/nthiery/revert_symmetricgroup_algebra_change_from__16678</em>
</li>
</ul>
TicketdarijWed, 03 Sep 2014 11:58:55 GMTcommit set
https://trac.sagemath.org/ticket/16925#comment:3
https://trac.sagemath.org/ticket/16925#comment:3
<ul>
<li><strong>commit</strong>
set to <em>479fddb4afe86e8dc5382f50e0d8d0d11913e23a</em>
</li>
</ul>
<p>
I have a request. Could you add the fact that <code>SymmetricGroup.algebra() != SymmetricGroupAlgebra</code> to the doc, along with an explanation of how to get the <code>SymmetricGroupAlgebra</code>? Thanks.
</p>
<hr />
<p>
New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=479fddb4afe86e8dc5382f50e0d8d0d11913e23a"><span class="icon"></span>479fddb</a></td><td><code>16925: revert SymmetricGroups(...).algebra(...) to just do the standard thing</code>
</td></tr></table>
TicketnthieryWed, 03 Sep 2014 12:21:19 GMT
https://trac.sagemath.org/ticket/16925#comment:4
https://trac.sagemath.org/ticket/16925#comment:4
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/16925#comment:3" title="Comment 3">darij</a>:
</p>
<blockquote class="citation">
<p>
I have a request. Could you add the fact that <code>SymmetricGroup.algebra() != SymmetricGroupAlgebra</code> to the doc, along with an explanation of how to get the <code>SymmetricGroupAlgebra</code>? Thanks.
</p>
</blockquote>
<p>
I considered this. It means leaving an algebra method in <a class="missing wiki">SymmetricGroup?</a> that does nothing but the standard thing, except for having an extra chunk of doc advertising <a class="missing wiki">SymmetricGroupAlgebra?</a> and the backward incompatibility issue. I can do that if you think that's helpful for the user.
</p>
<p>
Right now, I am running all tests after just stripping away the method.
</p>
TicketdarijWed, 03 Sep 2014 12:22:59 GMT
https://trac.sagemath.org/ticket/16925#comment:5
https://trac.sagemath.org/ticket/16925#comment:5
<p>
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.
</p>
TicketnthieryWed, 03 Sep 2014 12:27:34 GMT
https://trac.sagemath.org/ticket/16925#comment:6
https://trac.sagemath.org/ticket/16925#comment:6
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/16925#comment:5" title="Comment 5">darij</a>:
</p>
<blockquote class="citation">
<p>
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.
</p>
</blockquote>
<p>
I am still hesitant actually. It's still nice to the user to warn him about the backward incompatibility flip-flop.
</p>
TicketgitWed, 03 Sep 2014 12:38:17 GMTcommit changed
https://trac.sagemath.org/ticket/16925#comment:7
https://trac.sagemath.org/ticket/16925#comment:7
<ul>
<li><strong>commit</strong>
changed from <em>479fddb4afe86e8dc5382f50e0d8d0d11913e23a</em> to <em>ce71c7444f957da20f6f9bd1cda95fde8feda9b1</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="http://git.sagemath.org/sage.git/commit/?id=ce71c7444f957da20f6f9bd1cda95fde8feda9b1"><span class="icon"></span>ce71c74</a></td><td><code>16925: updated a few doctests according to the previous commit</code>
</td></tr></table>
TicketnthieryWed, 03 Sep 2014 12:51:16 GMTstatus changed
https://trac.sagemath.org/ticket/16925#comment:8
https://trac.sagemath.org/ticket/16925#comment:8
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
</ul>
<p>
With the last commit, all tests passed. Haven't run long tests pass. Let's see what the bot says.
</p>
TicketvirmauxWed, 03 Sep 2014 13:00:41 GMT
https://trac.sagemath.org/ticket/16925#comment:9
https://trac.sagemath.org/ticket/16925#comment:9
<p>
Looks good to me...
</p>
TicketnthieryWed, 03 Sep 2014 13:11:31 GMT
https://trac.sagemath.org/ticket/16925#comment:10
https://trac.sagemath.org/ticket/16925#comment:10
<p>
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 <code>SymmetricGroup</code> whereas in the <code>SymmetricGroupAlgebra</code> elements are supposed to be indexed by <code>Permutation</code>s. Any further operation on it would have lead to an explosion.
</p>
<p>
Granted: the overall infrastructure should have trapped the creation of such corrupt element; but that's a different discussion ...
</p>
TickettscrimWed, 03 Sep 2014 17:29:59 GMT
https://trac.sagemath.org/ticket/16925#comment:11
https://trac.sagemath.org/ticket/16925#comment:11
<p>
I'm not quite sure about the (unwritten as far I can tell) assumption that <code>G.algebra</code> has a basis indexed by the elements of the group.
</p>
<p>
Here are some timings of the two implementations:
</p>
<pre class="wiki">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
</pre><p>
So getting the basis is significantly slower using the generic code, but multiplying elements is faster using the group.
</p>
<p>
Also going from the permutation group elements to a permutation is fast:
</p>
<pre class="wiki">sage: lst = list(S)
sage: %timeit Permutation(lst[4])
10000 loops, best of 3: 69 µs per loop
</pre><p>
although there is a slight bug:
</p>
<pre class="wiki">sage: P3 = Permutations(3)
sage: P3(lst[4])
TypeError: object of type 'sage.groups.perm_gps.permgroup_element.PermutationGroupElement' has no len()
</pre><p>
Multiplying permutation group elements is <em>really</em> fast compared to Sage's permutations:
</p>
<pre class="wiki">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
</pre><p>
So my proposal would be to change the indexing set of <code>SymmetricGroupAlgebra</code> to be the <code>SymmetricGroup</code> and add conversions to Sage's permutations where necessary.
</p>
TickettscrimWed, 03 Sep 2014 19:27:57 GMT
https://trac.sagemath.org/ticket/16925#comment:12
https://trac.sagemath.org/ticket/16925#comment:12
<p>
Minor technical challenge (or perhaps question), we will have to deal with handling backwards compatibility with giving the basis an instance of our <code>Permutation</code> class.
</p>
TicketnthieryWed, 03 Sep 2014 19:51:25 GMT
https://trac.sagemath.org/ticket/16925#comment:13
https://trac.sagemath.org/ticket/16925#comment:13
<blockquote>
<p>
Hi Travis,
</p>
</blockquote>
<p>
Thanks for the timings!
</p>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/16925#comment:11" title="Comment 11">tscrim</a>:
</p>
<blockquote class="citation">
<p>
I'm not quite sure about the (unwritten as far I can tell) assumption that <code>G.algebra</code> has a basis indexed by the elements of the group.
</p>
</blockquote>
<pre class="wiki"> 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.
...
</pre><p>
So any subclass overriding <code>algebra</code> should satisfy those premises.
</p>
<blockquote class="citation">
<p>
Here are some timings of the two implementations:
...
So getting the basis is significantly slower using the generic code,
</p>
</blockquote>
<p>
To be precise: in both cases, the implementation of <code></code>basis<code></code> is the
same (provided by <a class="missing wiki">ModulesWithBasis?</a>). What we are seeing here is that
iterating through <code>SymmetricGroup(n)</code> is slower than iteration through
<code>Permutations(n)</code>. Actually ridiculously slower:
</p>
<pre class="wiki">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
</pre><p>
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 <code>Permutations</code>:
</p>
<pre class="wiki">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
</pre><p>
But we are deviating here. That's for a separate ticket.
</p>
<blockquote class="citation">
<p>
So my proposal would be to change the indexing set of <code>SymmetricGroupAlgebra</code> to be the <code>SymmetricGroup</code> and add conversions to Sage's permutations where necessary.
</p>
</blockquote>
<p>
This would be even more backward incompatible: people have been using
<code>SymmetricGroupAlgebra</code> 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 <a class="closed ticket" href="https://trac.sagemath.org/ticket/16926" title="enhancement: Merge the features of SymmetricGroupAlgebra and SymmetricGroup.algebra (closed: fixed)">#16926</a>.
</p>
<p>
Cheers,
</p>
<blockquote>
<p>
Nicolas
</p>
</blockquote>
TickettscrimThu, 04 Sep 2014 05:47:41 GMT
https://trac.sagemath.org/ticket/16925#comment:14
https://trac.sagemath.org/ticket/16925#comment:14
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/16925#comment:13" title="Comment 13">nthiery</a>:
</p>
<blockquote class="citation">
<pre class="wiki"> 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.
...
</pre><p>
So any subclass overriding <code>algebra</code> should satisfy those premises.
</p>
</blockquote>
<p>
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".
</p>
<blockquote class="citation">
<p>
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 <code>Permutations</code>:
</p>
<pre class="wiki">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
</pre><p>
But we are deviating here. That's for a separate ticket.
</p>
</blockquote>
<p>
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.
</p>
<blockquote class="citation">
<p>
This would be even more backward incompatible: people have been using
<code>SymmetricGroupAlgebra</code> 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 <a class="closed ticket" href="https://trac.sagemath.org/ticket/16926" title="enhancement: Merge the features of SymmetricGroupAlgebra and SymmetricGroup.algebra (closed: fixed)">#16926</a>.
</p>
</blockquote>
<p>
It's (relatively) easy to get Sage's <code>Permutation</code>s to compare equal to permutation group elements, as perm gp elts have a method called <code>_gap_list</code>, which returns the oneline notation and compares correctly to a <code>Permutation</code>. We would also need to change the hash for a (standard) <code>Permutation</code> 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 <code>Permutation</code> and return the correct element (plus IMO they really should compare properly anyways).
</p>
<p>
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.
</p>
TicketnthieryFri, 20 Mar 2015 05:45:32 GMTstatus changed
https://trac.sagemath.org/ticket/16925#comment:15
https://trac.sagemath.org/ticket/16925#comment:15
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
</ul>
<p>
This can be set to duplicate of <a class="closed ticket" href="https://trac.sagemath.org/ticket/16926" title="enhancement: Merge the features of SymmetricGroupAlgebra and SymmetricGroup.algebra (closed: fixed)">#16926</a> which is ready to go. We don't need anymore this intermediate step.
</p>
TicketvbraunFri, 20 Mar 2015 06:36:08 GMTstatus changed
https://trac.sagemath.org/ticket/16925#comment:16
https://trac.sagemath.org/ticket/16925#comment:16
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
reviewer name
</p>
TicketdarijFri, 20 Mar 2015 06:44:22 GMTcommit, branch deleted
https://trac.sagemath.org/ticket/16925#comment:17
https://trac.sagemath.org/ticket/16925#comment:17
<ul>
<li><strong>commit</strong>
<em>ce71c7444f957da20f6f9bd1cda95fde8feda9b1</em> deleted
</li>
<li><strong>branch</strong>
<em>u/nthiery/revert_symmetricgroup_algebra_change_from__16678</em> deleted
</li>
</ul>
TicketnthieryFri, 20 Mar 2015 06:54:18 GMTstatus changed; reviewer set; author deleted
https://trac.sagemath.org/ticket/16925#comment:18
https://trac.sagemath.org/ticket/16925#comment:18
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>positive_review</em>
</li>
<li><strong>reviewer</strong>
set to <em>Nicolas M. Thiéry</em>
</li>
<li><strong>author</strong>
<em>Nicolas M. Thiéry</em> deleted
</li>
</ul>
<p>
Thanks Volker for the notice.
</p>
TicketvbraunFri, 20 Mar 2015 18:39:00 GMTstatus changed
https://trac.sagemath.org/ticket/16925#comment:19
https://trac.sagemath.org/ticket/16925#comment:19
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
there is no branch, did you delete it accidentally?
</p>
TicketdarijFri, 20 Mar 2015 19:27:39 GMT
https://trac.sagemath.org/ticket/16925#comment:20
https://trac.sagemath.org/ticket/16925#comment:20
<p>
I deleted it because this branch is obsolete and a dead end. Or was this a wrong assumption?
</p>
TickettscrimFri, 20 Mar 2015 19:41:50 GMTstatus, milestone changed
https://trac.sagemath.org/ticket/16925#comment:21
https://trac.sagemath.org/ticket/16925#comment:21
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>positive_review</em>
</li>
<li><strong>milestone</strong>
changed from <em>sage-6.4</em> to <em>sage-duplicate/invalid/wontfix</em>
</li>
</ul>
<p>
The milestone wasn't changed to duplicate.
</p>
TicketvbraunFri, 20 Mar 2015 19:56:20 GMTstatus changed; resolution set
https://trac.sagemath.org/ticket/16925#comment:22
https://trac.sagemath.org/ticket/16925#comment:22
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>duplicate</em>
</li>
</ul>
Ticket