Add rings for the center of the symmetric group algebras

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

[mguaypaq]

preliminary version

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

[tscrim]

Just wondering what the status of this patch is?

Thanks,
Travis

[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

[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

[tscrim]

Hey Mathieu,

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

Best,
Travis

[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

[tscrim]

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

Best,
Travis

[mguaypaq]

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

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

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

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]

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]

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

[git]

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.

[git]

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

[changeset:fb33147]

Merge branch 'master' into ticket/10305