#14881: Some symmetric group algebra modifications
-------------------------------------------------+-------------------------
Reporter: darij | Owner: sage-
Type: defect | combinat
Priority: major | Status:
Component: combinatorics | needs_review
Keywords: permutations, symmetric group | Milestone:
algebra, combinat, | sage-5.12
Authors: Darij Grinberg | Resolution:
Report Upstream: N/A | Merged in:
Branch: | Reviewers: Travis
Stopgaps: | Scrimshaw
| Work issues:
| Dependencies: #14772,
| #14101
-------------------------------------------------+-------------------------
Old description:
> **UPDATED and ready for review.** The patch does the following:
>
> 1) Allows `k = 1` in the construction of the k-th Jucys-Murphy element in
> both the symmetric group algebra and the Hecke algebra. There is no
> theoretical reason not to. They're not very interesting elements, but
> algorithms shouldn't mysteriously fail in corner cases. (Note: I'm
> treating `k = 1` as a separate case in the Hecke algebra because I want
> it to return the 1 of the Hecke algebra, not the int 1.)
>
> 2) The `algebra_generators()` method on a symmetric group algebra with n
> being 0 or 1 doesn't throw an error anymore.
>
> 3) The `cpi` method should now be a lot faster (checked on S,,6,, and
> `[3,2,1]`, where the speedup factor was more than 2).
>
> 4) New methods `a` and `b` in `symmetric_group_algebra.py` allow
> computing the sum of the row-preserving permutations and the alternating
> sum of the column-preserving permutation of a Young tableau, not just
> their product. These methods are not exported by default so as not to
> pollute the namespace.
>
> 5) A fix in `tableau.py` ensures that `Tableau([]).row_stabilizer()`
> behaves as it should. My speed tests are inconclusive, but I don't think
> this fix has any noticeable impact on overall speed of tableau
> computations. The assumption I added to the documentation was already
> needed beforehand; it just wasn't documented.
>
> Issues I'd like the reviewer to look at closely:
>
> A) I removed a "#################### SEGFAULTS ################" comment
> after a doctests since that doctest doesn't even run close to segfaulting
> (on my machine, that is). If it had a reason to be there, please insert
> it back.
>
> B) I don't know what the `star` keyword in my methods is for -- I copied
> it over from the `e` method (which should be similar to `a` and `b` in
> various regards), where it was undocumented. Apparently it is used
> internally in other methods. If you think I should remove it from my
> methods, I will.
>
> C) There are two TODOs which might deserve tickets of their own.
>
> {{{
> 627 # This all should be over ZZ, not over QQ, but
> symmetric group
> 628 # algebras don't seem to preserve coercion (the one
> over ZZ
> 629 # doesn't coerce into the one over QQ even for the
> same n),
> 630 # and the QQ version of this method is more
> important, so let
> 631 # me stay with QQ.
> 632 # TODO: Fix this.
> }}}
>
> and
>
> {{{
> 637 # Ugly hack for the case of an empty tableau, due to
> the
> 638 # annoyance of
> Permutation(Tableau([]).row_stabilizer()[0])
> 639 # being [1] rather than [] (which seems to have its
> origins in
> 640 # permutation group code).
> }}}
>
> If you agree, I'll open these tickets.
>
> * Apply: [attachment:trac_14881-symmetric_group_algebra_rebased-dg.patch]
>
> ====================================================================
>
> The following rant is being kept for reference; it now has a ticket of
> its own (#14885) and a sage-devel discussion (
> https://groups.google.com/forum/#!topic/sage-devel/tAAb42Edh9o ). The
> present ticket changes nothing about it.
>
> Writing this patch made me notice that **Sage is using Herstein's idiotic
> left-to-right convention for the product of permutations as default**! I
> think the only reason why I have missed this so far is that I haven't
> been multiplying permutations very often in the first place. That said,
> I'm not sure about this, and I feel sorry for the conjectures I have been
> discarding because I thought I was able to produce counterexamples with
> Sage. Can we do anything about this or at least document it in such a way
> that it can't be missed? I will open another ticket for this issue once
> I've done a quick search to see where these multiplications are being
> used; I wouldn't be surprised if there are bugs lurking in the code just
> because people expected that Sage would use the same conventions as
> everyone else in mathematics. I know about GAP, but part of the reason
> I've been using Sage is to not have to put up with crappy syntax.
>
> When I grep for `PermutationOptions` and `permutation_options`, I only
> get hits from `permutation.py` and `symmetric_group_algebra.py`, which
> suggests that all other files are either oblivious to the semantics of a
> product of permutations depending on a global variable, or they just work
> around this product method. I'm hoping it's the latter...
New description:
**UPDATED and ready for review.** The patch does the following:
1) Allows `k = 1` in the construction of the k-th Jucys-Murphy element in
both the symmetric group algebra and the Hecke algebra. There is no
theoretical reason not to. They're not very interesting elements, but
algorithms shouldn't mysteriously fail in corner cases. (Note: I'm
treating `k = 1` as a separate case in the Hecke algebra because I want it
to return the 1 of the Hecke algebra, not the int 1.)
2) The `algebra_generators()` method on a symmetric group algebra with n
being 0 or 1 doesn't throw an error anymore.
3) The `cpi` method should now be a lot faster (checked on S,,6,, and
`[3,2,1]`, where the speedup factor was more than 2).
4) New methods `a` and `b` in `symmetric_group_algebra.py` allow computing
the sum of the row-preserving permutations and the alternating sum of the
column-preserving permutation of a Young tableau, not just their product.
These methods are not exported by default so as not to pollute the
namespace.
5) A fix in `tableau.py` ensures that `Tableau([]).row_stabilizer()`
behaves as it should. My speed tests are inconclusive, but I don't think
this fix has any noticeable impact on overall speed of tableau
computations. The assumption I added to the documentation was already
needed beforehand; it just wasn't documented.
Issues I'd like the reviewer to look at closely:
A) I removed a "#################### SEGFAULTS ################" comment
after a doctests since that doctest doesn't even run close to segfaulting
(on my machine, that is). If it had a reason to be there, please insert it
back.
B) I don't know what the `star` keyword in my methods is for -- I copied
it over from the `e` method (which should be similar to `a` and `b` in
various regards), where it was undocumented. Apparently it is used
internally in other methods. If you think I should remove it from my
methods, I will.
C) There are two TODOs which might deserve tickets of their own.
{{{
627 # This all should be over ZZ, not over QQ, but
symmetric group
628 # algebras don't seem to preserve coercion (the one
over ZZ
629 # doesn't coerce into the one over QQ even for the
same n),
630 # and the QQ version of this method is more important,
so let
631 # me stay with QQ.
632 # TODO: Fix this.
}}}
and
{{{
637 # Ugly hack for the case of an empty tableau, due to
the
638 # annoyance of
Permutation(Tableau([]).row_stabilizer()[0])
639 # being [1] rather than [] (which seems to have its
origins in
640 # permutation group code).
}}}
If you agree, I'll open these tickets.
Apply:
* [attachment:trac_14881-symmetric_group_algebra_rebased-dg.patch]
* [attachment:trac_14881-review-ts.patch]
====================================================================
The following rant is being kept for reference; it now has a ticket of its
own (#14885) and a sage-devel discussion (
https://groups.google.com/forum/#!topic/sage-devel/tAAb42Edh9o ). The
present ticket changes nothing about it.
Writing this patch made me notice that **Sage is using Herstein's idiotic
left-to-right convention for the product of permutations as default**! I
think the only reason why I have missed this so far is that I haven't been
multiplying permutations very often in the first place. That said, I'm not
sure about this, and I feel sorry for the conjectures I have been
discarding because I thought I was able to produce counterexamples with
Sage. Can we do anything about this or at least document it in such a way
that it can't be missed? I will open another ticket for this issue once
I've done a quick search to see where these multiplications are being
used; I wouldn't be surprised if there are bugs lurking in the code just
because people expected that Sage would use the same conventions as
everyone else in mathematics. I know about GAP, but part of the reason
I've been using Sage is to not have to put up with crappy syntax.
When I grep for `PermutationOptions` and `permutation_options`, I only get
hits from `permutation.py` and `symmetric_group_algebra.py`, which
suggests that all other files are either oblivious to the semantics of a
product of permutations depending on a global variable, or they just work
around this product method. I'm hoping it's the latter...
--
Comment (by tscrim):
Hey Darij,
Here's a small review patch which makes some minor tweaks to the doc and
removes two asserts used for input checking. If you're happy with my
changes, you can go ahead and set this to positive review.
Best,[[BR]]
Travis
For patchbot:
Apply: trac_14881-symmetric_group_algebra_rebased-dg.patch trac_14881
-review-ts.patch
--
Ticket URL: <http://trac.sagemath.org/ticket/14881#comment:16>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/groups/opt_out.
