search

sagemath / sage

Main repository of SageMath
https://www.sagemath.org
Other
1.37k stars 462 forks source link

Add rings for the center of the symmetric group algebras #10305

Open mguaypaq opened 13 years ago

mguaypaq commented 13 years ago

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:

Note that this depends on #7980 and #10304.

CC: @sagetrac-vferay

Component: combinatorics

Keywords: rings, symmetric functions

Author: Mathieu Guay-Paquet, Travis Scrimshaw

Branch/Commit: public/ticket/10305-farahat-higman @ fb33147

Reviewer: Travis Scrimshaw, Mathieu Guay-Paquet

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

mguaypaq commented 13 years ago

preliminary version

mguaypaq commented 13 years ago
comment:1

Attachment: trac_10305_farahat_higman-mgp.patch.gz

mguaypaq commented 12 years ago
comment:2

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.

tscrim commented 11 years ago
comment:3

Just wondering what the status of this patch is?

Thanks,

Travis

mguaypaq commented 11 years ago
comment:4

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

tscrim commented 11 years ago
comment:5

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

tscrim commented 11 years ago
comment:6

Hey Mathieu,

Just wondering if you've done any work on this patch?

Best,

Travis

mguaypaq commented 11 years ago
comment:7

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

tscrim commented 11 years ago
comment:8

I think the easiest thing would be for me to just take over the patch.

Best,

Travis

mguaypaq commented 11 years ago
comment:9

Alright, in that case you know where to find a reviewer :)

tscrim commented 11 years ago

Changed author from Mathieu Guay-Paquet to Mathieu Guay-Paquet, Travis Scrimshaw

tscrim commented 11 years ago
comment:11

Attachment: trac_10305-farahat_higman-ts.patch.gz

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:

(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​

tscrim commented 11 years ago

Reviewer: Travis Scrimshaw, Mathieu Guay-Paquet

tscrim commented 11 years ago

Description changed:

--- 
+++ 
@@ -10,3 +10,6 @@

 Note that this depends on #7980 and #10304.

+Apply:
+
+[attachment: trac_10305-farahat_higman-ts.patch​](https://github.com/sagemath/sage/files/ticket10305/4b7f5dfcedc14a513b2904d15122f326.gz)
mguaypaq commented 11 years ago
comment:12

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 allowing n to vary. Thus we would need to take the terms just corresponding to partitions n 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:

  1. Start from the Farahat-Higman algebra over R['t'] with parameter t, and specialize t to 4.

  2. 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

mguaypaq commented 11 years ago

Branch: u/mguaypaq/ticket/10305

mguaypaq commented 11 years ago

Commit: 25ff1fd

mguaypaq commented 11 years ago

Description changed:

--- 
+++ 
@@ -1,15 +1,10 @@
 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.

-Things that I plan to do:
-* Fill in all of the TODO doctests with actual doctests.
-* Figure out why some of the coercions aren't discovered by the coercion framework. (See the last few examples at the top of the file.)
-* `SymmetricGroupAlgebraCenter` does not actually have a multiplicative identity as currently implemented, so it should probably by in a category other than `GradedAlgebrasWithBasis`.
-* Reimplement `ConjugacyClassBasis` and `OrthogonalIdempotentBasis` for a fixed symmetric group over the integers. Then, the conversion table can be cached, the elements can be represented by lists of coefficients (possibly numpy arrays) instead of dictionaries, and faster linear algebra over the integers can be used. This results in massive (several orders of magnitude) speedups.
+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.
-* Add the relevant classes to `sage/combinat/all.py`.

 Note that this depends on #7980 and #10304.

-Apply:
-
-[attachment: trac_10305-farahat_higman-ts.patch​](https://github.com/sagemath/sage/files/ticket10305/4b7f5dfcedc14a513b2904d15122f326.gz)
mguaypaq commented 11 years ago
comment:14

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?

tscrim commented 11 years ago
comment:15

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:

.. [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.

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

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

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.
7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from 25ff1fd to 405178b

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

Changed commit from 405178b to fb33147

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 10 years ago

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

[changeset:fb33147]Merge branch 'master' into ticket/10305
mguaypaq commented 10 years ago

Changed branch from u/mguaypaq/ticket/10305 to public/ticket/10305-farahat-higman