Opened 6 years ago

Last modified 3 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) Commit: fb331475d3c1865b55f3cac024039001de9f28ad
Dependencies: Stopgaps:

Description (last modified by mguaypaq)

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.

Note that this depends on #7980 and #10304.

Attachments (2)

trac_10305_farahat_higman-mgp.patch (35.1 KB) - added by mguaypaq 6 years ago.
preliminary version
trac_10305-farahat_higman-ts.patch (46.3 KB) - added by tscrim 4 years ago.

Download all attachments as: .zip

Change History (23)

Changed 6 years ago by mguaypaq

preliminary version

comment:1 Changed 6 years ago by mguaypaq

  • Status changed from new to needs_work

comment:2 Changed 5 years ago by mguaypaq

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 4 years ago by tscrim

Just wondering what the status of this patch is?

Thanks,
Travis

comment:4 follow-up: Changed 4 years ago by 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.

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 4 years ago by tscrim

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 4 years ago by tscrim

Hey Mathieu,

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

Best,
Travis

comment:7 Changed 4 years ago by mguaypaq

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 4 years ago by tscrim

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

Best,
Travis

comment:9 Changed 4 years ago by mguaypaq

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

comment:10 Changed 4 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

Changed 4 years ago by tscrim

comment:11 follow-up: Changed 4 years ago by tscrim

  • Authors changed from Mathieu Guay-Paquet to Mathieu Guay-Paquet, Travis Scrimshaw
  • 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 allowing n to vary. Thus we would need to take the terms just corresponding to partitions n 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 4 years ago by mguaypaq

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.
  1. 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 3 years ago by mguaypaq

  • 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 3 years ago by mguaypaq

  • 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 3 years ago by tscrim

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

Last edited 3 years ago by tscrim (previous) (diff)

comment:16 Changed 3 years ago by git

  • 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 3 years ago by git

  • 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 3 years ago by mguaypaq

  • Branch changed from u/mguaypaq/ticket/10305 to public/ticket/10305-farahat-higman

comment:19 Changed 3 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:20 Changed 3 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:21 Changed 3 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4
Note: See TracTickets for help on using tickets.