Opened 11 years ago
Last modified 8 years ago
#10305 needs_work enhancement
Add rings for the center of the symmetric group algebras
Reported by: | mguaypaq | Owned by: | mguaypaq |
---|---|---|---|
Priority: | minor | Milestone: | sage-6.4 |
Component: | combinatorics | Keywords: | combinatorics, rings, symmetric functions |
Cc: | vferay | Merged in: | |
Authors: | Mathieu Guay-Paquet, Travis Scrimshaw | Reviewers: | Travis Scrimshaw, Mathieu Guay-Paquet |
Report Upstream: | N/A | Work issues: | |
Branch: | public/ticket/10305-farahat-higman (Commits, GitHub, GitLab) | Commit: | fb331475d3c1865b55f3cac024039001de9f28ad |
Dependencies: | Stopgaps: |
Description (last modified by )
Here is some preliminary code to implement the center of the symmetric group algebras, various bases for this and related rings, and coercions between these and to/from the ring of symmetric functions.
Work issues:
- Re-architecting in progress
- Fix the performance of conversion from SymmetricGroupAlgebraCenter to SymmetricGroupAlgebra
- Add the new files (and possibly some old ones?) to the reference manual
- Possibly add the option of saving some of the conversion tables to disk, as they can be large and expensive to compute.
Attachments (2)
Change History (23)
Changed 11 years ago by
comment:1 Changed 11 years ago by
- Status changed from new to needs_work
comment:2 Changed 10 years ago by
This code is very old and we now know much better ways of doing this. If you want to help, please contact me and I'll get you up to speed.
comment:3 Changed 9 years ago by
Just wondering what the status of this patch is?
Thanks,
Travis
comment:4 follow-up: ↓ 5 Changed 9 years ago by
It's been a while, but my recollection is that the code works most of the time, but several doctests are missing before it's acceptable. Also the performance is not great.
To fix the problems with the code (mostly some coercions and performance issues), I think a better architecture would be needed. In particular, not using CombinatorialFreeModule
would probably be better. We also have a better understanding of the mathematics behind the various changes of basis between symmetric functions and the Farahat-Higman algebra now, and this could be used for the code. I tried doing this a few times, but never got to the end.
Do you have a need for this functionality? If so, I'd be happy to collaborate or let you take over. Otherwise, I think this ticket can be safely ignored and/or closed for now.
Cheers,
Mathieu
comment:5 in reply to: ↑ 4 Changed 9 years ago by
Hey Mathieu,
Replying to mguaypaq:
It's been a while, but my recollection is that the code works most of the time, but several doctests are missing before it's acceptable. Also the performance is not great.
I'd be happy to write a review patch and add in the documentation.
To fix the problems with the code (mostly some coercions and performance issues), I think a better architecture would be needed. In particular, not using
CombinatorialFreeModule
would probably be better. We also have a better understanding of the mathematics behind the various changes of basis between symmetric functions and the Farahat-Higman algebra now, and this could be used for the code. I tried doing this a few times, but never got to the end.
There has also be a very substantial rewrite of the symmetric functions and we would likely be able to lift some code (or at least the implementation concepts) from there.
Do you have a need for this functionality? If so, I'd be happy to collaborate or let you take over. Otherwise, I think this ticket can be safely ignored and/or closed for now.
It would be nice for a colleague of mine to have a working version of this in sage. Right now he's looking into Schur rings in Z(CC[S_n]) as they come up in supercharacter theory and this patch would be useful. I'm happy to help where I can to get this working.
Best,
Travis
comment:6 Changed 9 years ago by
Hey Mathieu,
Just wondering if you've done any work on this patch?
Best,
Travis
comment:7 Changed 9 years ago by
Hey Travis,
Not yet, sorry. Feel free to take over the patch, or to poke me mercilessly until I get it done, since I'm now back home and getting back to work. Would it be helpful to set up a chat over IRC or something with this colleague of yours?
Cheers, Mathieu
comment:8 Changed 9 years ago by
I think the easiest thing would be for me to just take over the patch.
Best,
Travis
comment:9 Changed 9 years ago by
Alright, in that case you know where to find a reviewer :)
comment:10 Changed 9 years ago by
- Milestone changed from sage-5.11 to sage-5.12
Changed 9 years ago by
comment:11 follow-up: ↓ 12 Changed 9 years ago by
- Description modified (diff)
- Reviewers set to Travis Scrimshaw, Mathieu Guay-Paquet
Hey Matthieu,
Here's everything that I could do with the patch. I've reworked it to use the same framework as the symmetric functions, allowed the SGA center for a fixed n, and added in coercions to the SGA when appropriate. However there's three more things I'll need from you:
- Could you put in some references for the Farahat-Higman/partial class algebras?
- From what I could find, it seems like the Farahat-Higman algebra is actually just the parts for a fixed
n
, not allowingn
to vary. Thus we would need to take the terms just corresponding to partitionsn
in the larger product. Is this correct? - On line 426 of
farahat_higman.py
, you had originally left that sentence as incomplete and I couldn't figure out how to finish it. Could you finish writing that paragraph?
(Due to the amount of changes by just reorganizing code, I felt it was better to post a new version of the patch than a review patch.)
For reviewing this patch, we'll do a cross-review where I review your changes and you review mine. Sound good?
Thanks,
Travis
For patchbot:
Apply: trac_10305-farahat_higman-ts.patch
comment:12 in reply to: ↑ 11 Changed 9 years ago by
Hi Travis,
Replying to tscrim:
Hey Matthieu,
Here's everything that I could do with the patch. I've reworked it to use the same framework as the symmetric functions, allowed the SGA center for a fixed n, and added in coercions to the SGA when appropriate.
Great! I'll have a look as you suggest.
- Could you put in some references for the Farahat-Higman/partial class algebras?
Sure. In the meantime, here's the bibtex from mathscinet for the original paper by Farahat and Higman:
@article {MR0103935, AUTHOR = {Farahat, H. K. and Higman, G.}, TITLE = {The centres of symmetric group rings}, JOURNAL = {Proc. Roy. Soc. London Ser. A}, FJOURNAL = {Proceedings of the Royal Society. London. Series A. Mathematical, Physical and Engineering Sciences}, VOLUME = {250}, YEAR = {1959}, PAGES = {212--221}, ISSN = {0962-8444}, MRCLASS = {20.00}, MRNUMBER = {0103935 (21 \#2697)}, MRREVIEWER = {T. Nakayama}, }
The partial class algebra is used and described in a recent paper by Féray, but originally defined by Ivanov and Kerov. Both articles are available in English on arXiv, and the mathscinet bibtex is:
@article {MR2854640, AUTHOR = {F{\'e}ray, Valentin}, TITLE = {Partial {J}ucys-{M}urphy elements and star factorizations}, JOURNAL = {European J. Combin.}, FJOURNAL = {European Journal of Combinatorics}, VOLUME = {33}, YEAR = {2012}, NUMBER = {2}, PAGES = {189--198}, ISSN = {0195-6698}, MRCLASS = {05A05 (05A15)}, MRNUMBER = {2854640 (2012k:05013)}, DOI = {10.1016/j.ejc.2011.09.035}, URL = {http://dx.doi.org/10.1016/j.ejc.2011.09.035}, } @article {MR1708561, AUTHOR = {Ivanov, V. and Kerov, S.}, TITLE = {The algebra of conjugacy classes in symmetric groups, and partial permutations}, JOURNAL = {Zap. Nauchn. Sem. S.-Peterburg. Otdel. Mat. Inst. Steklov. (POMI)}, FJOURNAL = {Rossi\u\i skaya Akademiya Nauk. Sankt-Peterburgskoe Otdelenie. Matematicheski\u\i\ Institut im. V. A. Steklova. Zapiski Nauchnykh Seminarov (POMI)}, VOLUME = {256}, YEAR = {1999}, NUMBER = {Teor. Predst. Din. Sist. Komb. i Algoritm. Metody. 3}, PAGES = {95--120, 265}, ISSN = {0373-2703}, MRCLASS = {20B30 (05A05)}, MRNUMBER = {1708561 (2000g:20010)}, DOI = {10.1023/A:1012473607966}, URL = {http://dx.doi.org/10.1023/A:1012473607966}, }
- From what I could find, it seems like the Farahat-Higman algebra is actually just the parts for a fixed
n
, not allowingn
to vary. Thus we would need to take the terms just corresponding to partitionsn
in the larger product. Is this correct?
In the current version, the ground field R
given to the constructor FarahatHigmanAlgebra
is first transformed into a polynomial ring of the form R['t']
, and then the n
is the variable t
from this new polynomial ring. A better design would be to pass the ring R['t']
directly to the constructor, and let the parameter be chosen arbitrarily from this ring (not just the generator t
). This is one of the points that made me think a better design is in order, because it creates some problems down the line.
Regarding the bound on partitions based on n
: strictly speaking, in the FH algebra, the basis includes *all* partitions, not just those where size + length <= n
. If you want to get the center of the symmetric group algebra for a fixed integer n
, say n = 4
, then you need to do two things:
- Start from the Farahat-Higman algebra over
R['t']
with parametert
, and specializet
to4
.
- Map every basis element where the partition has
size + length > 4
to zero.
The second step is where the bound on partitions comes up, but at that point it's no longer the Farahat-Higman algebra itself, but rather a homomorphic image. Does that make sense?
- On line 426 of
farahat_higman.py
, you had originally left that sentence as incomplete and I couldn't figure out how to finish it. Could you finish writing that paragraph?
Hah, what I just wrote above is what I meant to write in the documentation. I think it's a very muddled and unclear explanation, though, so I should improve it. Let me know if it makes no/some/complete sense.
(Due to the amount of changes by just reorganizing code, I felt it was better to post a new version of the patch than a review patch.)
Good call.
For reviewing this patch, we'll do a cross-review where I review your changes and you review mine. Sound good?
That works.
Cheers, Mathieu
comment:13 Changed 9 years ago by
- Branch set to u/mguaypaq/ticket/10305
- Modified changed from 09/09/13 19:39:07 to 09/09/13 19:39:07
comment:14 Changed 9 years ago by
- Commit set to 25ff1fd7f9ad2539fb7e95134d96b882bfd40187
- Description modified (diff)
Sorry for the very long delay. The code is still a work in progress, but now using the new git workflow! I've been tinkering with the code a lot, but hopefully this first commit makes some sense. It's mostly about splitting off the SymmetricGroupAlgebraCenter code into its own file, but there's a pretty long-winded commit message to explain the code changes.
I now have a much clearer picture of what rings should be created, in what order, under what conditions, which coercions should be registered, and what should be cached where. I'll start chipping away at this for now, and if anyone wants to validate the design, I bet a conversation on IRC (or some other real-time communication medium) would be best.
For reviewing, my hope would be that each commit makes sense individually, and could be reviewed individually to check that it does what it claims to do in the commit message. Travis, would this be acceptable?
comment:15 Changed 9 years ago by
Hey Mathieu,
I think it would be best to just look at the final version, but the commit messages are helpful. A few quick comments from looking over the branch:
- The
SymmetricGroupAlgebraCenterBases
should be in the other file. - The references should be formatted like:
.. [Name2013] Blah. *I prefer titles in italics when there's no math formatting needed*. Other stuff.
Then you can reference them as[Name2013]_
in any place in any file, i.e. they are global to all of the Sage documentation. - It should be
.. RUBRIC::
with 2 colons and.. SEEALSO::
as one word.
I'll make some changes if you don't beat me to them first as I start to work with the new workflow.
Best,
Travis
comment:16 Changed 9 years ago by
- Commit changed from 25ff1fd7f9ad2539fb7e95134d96b882bfd40187 to 405178b1ec1776ecc0e40ce8e328ab7e3f7141b4
Branch pushed to git repo; I updated commit sha1. New commits:
[changeset:405178b] | Remove extra chunk from farahat_higman.py and fix related formatting issues. |
comment:17 Changed 9 years ago by
- Commit changed from 405178b1ec1776ecc0e40ce8e328ab7e3f7141b4 to fb331475d3c1865b55f3cac024039001de9f28ad
Branch pushed to git repo; I updated commit sha1. New commits:
[changeset:fb33147] | Merge branch 'master' into ticket/10305 |
comment:18 Changed 9 years ago by
- Branch changed from u/mguaypaq/ticket/10305 to public/ticket/10305-farahat-higman
comment:19 Changed 8 years ago by
- Milestone changed from sage-6.1 to sage-6.2
comment:20 Changed 8 years ago by
- Milestone changed from sage-6.2 to sage-6.3
comment:21 Changed 8 years ago by
- Milestone changed from sage-6.3 to sage-6.4
preliminary version