Implement cellular algebras

[tscrim]

Cellular algebras are a class of algebras that have a well-behaved representation theory generalizing that of the Hecke algebra:

• https://en.wikipedia.org/wiki/Cellular_algebra
• http://webusers.imj-prg.fr/~bernhard.keller/ictp2006/lecturenotes/xi.pdf

We give a basic category implementation of cellular algebras and add the symmetric group algebra into this category as an example implementation.

CC: @sagetrac-sage-combinat @darijgr @AndrewAtLarge

Component: categories

Keywords: cellular algebra

Author: Travis Scrimshaw

Branch/Commit: 332f8ed

Reviewer: Andrew Mathas

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

[tscrim]

comment:1

This is mostly just a marker of constructing the cell datum (to which I coined some names). Follow-ups will include the natural representations a cellular algebra has and putting more algebras into this category.

---

New commits:

fda2f46

Initial implementation of cellular algebras.

[tscrim]

Commit: fda2f46

[tscrim]

Branch: public/categories/cellular_algebras-19506

[tscrim]

comment:2

I also fixed a bug in StandardTableaux when n is passed as a keyword.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

cbdbc2b

Fixing implementation of SGA cellular basis and more general code.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from fda2f46 to cbdbc2b

[AndrewMathas]

comment:4

Hi Travis,

I am intrigued. Which cellular basis are you using for the symmetric group? I have a few implementations of cellular bases but the nuts and bolts are always non-trivial so I am wondering what your category code provides and how easy it is to massage the symmetric group example into your framework. Of course, I really should read your code but I haven't done this. The ticket description does not give much information.

Andrew

[tscrim]

comment:5

I was originally following the lecture notes by Xi above, where RSK was define the basis (see example 5). However my test suite actually told me this was incorrect. So instead I switched to the seminormal basis, which as far as I can tell, is the specialization of the Murphy basis of the Hecke algebra.

To implement an object in cellular algebras, one needs to implement the following:

• cell_poset which returns the poset parameterizing the cells.
• cell which takes an element la in the cell poset and returns the cell M(la).
• One of the following:
  • _to_cellular_element which takes a basis index i and return an element in cellular_basis.
  • _from_cellular_index which takes (la, s, t) and returns an element of the algebra.
  • cellular_basis which returns an algebra with a basis indexed by (la, s, t) and has coercions to and from the algebra.

The first two are simply data, but the non-trivial part is the third one. However my current framework in a way assumes a distinguished cellular basis, but that is not to say it limits the algebra to one cellular basis.

[Edit - I should actually think a little bit more and remember that I am testing this mechanism for the tensor product.]

The next step would be to implement the representations, bilinear form, decomposition matrix, and Cartan matrix.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

da4f731

Fixing doctests and multiplication convention problems for SGA.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from cbdbc2b to da4f731

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

75215b6

Adding a method for getting the original algebra.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from da4f731 to 75215b6

[AndrewMathas]

comment:8

Replying to @tscrim:

I was originally following the lecture notes by Xi above, where RSK was define the basis (see example 5). However my test suite actually told me this was incorrect.

Example 5 of Xi's notes says that the Kazhdan-Lustig basis, via RSK, defines a cellular basis: that is, the cellular basis element indexed by (P,Q) is C_w if w corresponds to (P,Q) under RSK. This was Graham's motoviating example (and it is certainly correct). From the way that Xi has written it, however, I think that this result is only clear if you have already seen it before. Rather than Xi's notes the original Graham-Lehrer paper or my book would be a better reference (of course I am biased!)

So instead I switched to the seminormal basis, which as far as I can tell, is the specialization of the Murphy basis of the Hecke algebra.

A seminormal basis is a Wedderburn basis for the semisimple symmetric group or algebra. Wedderburn bases are always cellular but they are not particularly interesting examples of cellular bases because once you have a Wedderburn basis all of the consequences of cellularity are already obvious. The Murphy basis is an integral basis of the group algebra of the symmetric group (there are generalisations of the Murphy basis to other algebras). The transition matrix between the Murphy basis and one particular seminormal basis is unitriangular -- the off- diagonal entries of this transition matrix are not at all understood. I have no idea which seminormal basis is implemented in sage but I would guess that it is not the one that is closely related to the Murphy basis.

To implement an object in cellular algebras, one needs to implement the following:

• cell_poset which returns the poset parameterizing the cells.
• cell which takes an element la in the cell poset and returns the cell M(la).

• One of the following:

  • _to_cellular_element which takes a basis index i and return an element in cellular_basis.
  • _from_cellular_index which takes (la, s, t) and returns an element of the algebra.
  • cellular_basis which returns an algebra with a basis indexed by (la, s, t) and has coercions to and from the algebra.

  The first two are simply data, but the non-trivial part is the third one. However my current framework in a way assumes a distinguished cellular basis, but that is not to say it limits the algebra to one cellular basis.

  [Edit - I should actually think a little bit more and remember that I am testing this mechanism for the tensor product.]

  The next step would be to implement the representations, bilinear form, decomposition matrix, and Cartan matrix.

I have had a quick look at your code. I don't think that it makes much sense to have a CellularBasis class without first developing a non-trivial example because without a proper example you will not see what is likely to be needed in general.

I think that the idea is to provide extra functionality/structure on top of an AlgebraWithBasis. The non-trivial work in implementing a real example is in writing the coercion/conversion code going from a standard basis (for example, the permutation basis of the group algebra of the symmetric group) to a cellular basis (for example, the Murphy or Kazhdan-Lusztig bases of the group algebra of the symmetric group). Typically it is easy to write the cellular basis elements in terms of standard bases elements but the inverse operation is often tricky.

If C were a cellular basis class then I would expect C(s,t) to return the cellular basis element indexed by s and t. Strictly speaking, this should be C(mu,s,t) but in all of the interesting examples the "shape" mu (=element of the indexing poset) is implicitly encoded in s and t so there is no need to specify it. The methods _to_cellular_element and _from_cellular_index should be hidden, as you have them. I would expect them to be called implicitly via commands like A(C(s,t)) and C(A(w)).

There probably should be a cell_poset method, as you have, but the cell method seems slightly strange to me, I might call this cell_module_indices. The most important method should be a cell_module method that returns the (left or right) cell module: C.cell_module(mu) or perhaps C.left_cell_module(m) and C.right_cell_module(mu). These should be something like a CombinatorialFreeModules and they should come with actions of the algebra. The bilinear form on the cell module would of course be defined on this module. I would expect things the like following to work:

sage: M=SymmetricGroupAlgebra(ZZ,4).Murphy_basis()
sage: Smu=M.cell_module(3,1)
sage: Smu.basis()   
{ S([[1,2,3],[4]]), S([[1,2,4],[3]]), S([[1,3,4],[2]]) ]
sage: M([[1,2,4],[3]], [[1,2,3],[4]]) * S([[1,2,3],[4]])
6*S([[1,2,4],[3]])   
sage: Smu.inner_product([[1,2,3],[4]], [[1,2,3],[4]])
6

Note that indexing set for the basis of the cell modules is your .cell method and that the action of the cellular basis on the cell module gives the inner product.

There are no (good) algorithms for computing the decomposition matrices and Cartan matrices -- except for special cases like the Iwahori-Hecke algebras of types A and B using Kazhdan-Lustzig polynomial combinatorics.

[tscrim]

comment:9

Thank you for your detailed response.

Replying to @AndrewAtLarge:

Replying to @tscrim:

I was originally following the lecture notes by Xi above, where RSK was define the basis (see example 5). However my test suite actually told me this was incorrect.

Example 5 of Xi's notes says that the Kazhdan-Lustig basis, via RSK, defines a cellular basis: that is, the cellular basis element indexed by (P,Q) is C_w if w corresponds to (P,Q) under RSK. This was Graham's motoviating example (and it is certainly correct). From the way that Xi has written it, however, I think that this result is only clear if you have already seen it before. Rather than Xi's notes the original Graham-Lehrer paper or my book would be a better reference (of course I am biased!)

Ah, I see. I had a suspicion that it was going to be the KL basis. I misinterpreted the w \in \Sigma_n as an element of the natural basis since RSK of w vs w^-1 switches the two tableaux. At least that tells me a way to implement the cellular basis for the Iwahori-Hecke algebra (for type A).

Math question, do you know if the other type analogues of RSK extend to give a cellular basis for the Iwahori-Hecke algebras of other types, such as Lecouvey's insertion for type C?

So instead I switched to the seminormal basis, which as far as I can tell, is the specialization of the Murphy basis of the Hecke algebra.

A seminormal basis is a Wedderburn basis for the semisimple symmetric group or algebra. Wedderburn bases are always cellular but they are not particularly interesting examples of cellular bases because once you have a Wedderburn basis all of the consequences of cellularity are already obvious. The Murphy basis is an integral basis of the group algebra of the symmetric group (there are generalisations of the Murphy basis to other algebras). The transition matrix between the Murphy basis and one particular seminormal basis is unitriangular -- the off- diagonal entries of this transition matrix are not at all understood. I have no idea which seminormal basis is implemented in sage but I would guess that it is not the one that is closely related to the Murphy basis.

Hmm...interesting and good to know. I will have to change some of my documentation.

We definitely have to implement each of these bases as actual instances and some point in the near future I will (finally) convert the symmetric group algebra into the WithRealizations framework. (Yes, I know I have said this a few times in the past.)

To implement an object in cellular algebras, one needs to implement the following:

• cell_poset which returns the poset parameterizing the cells.
• cell which takes an element la in the cell poset and returns the cell M(la).

• One of the following:

  • _to_cellular_element which takes a basis index i and return an element in cellular_basis.
  • _from_cellular_index which takes (la, s, t) and returns an element of the algebra.
  • cellular_basis which returns an algebra with a basis indexed by (la, s, t) and has coercions to and from the algebra.

  The first two are simply data, but the non-trivial part is the third one. However my current framework in a way assumes a distinguished cellular basis, but that is not to say it limits the algebra to one cellular basis.

  The next step would be to implement the representations, bilinear form, decomposition matrix, and Cartan matrix.

I have had a quick look at your code. I don't think that it makes much sense to have a CellularBasis class without first developing a non-trivial example because without a proper example you will not see what is likely to be needed in general.

I think that the idea is to provide extra functionality/structure on top of an AlgebraWithBasis. The non-trivial work in implementing a real example is in writing the coercion/conversion code going from a standard basis (for example, the permutation basis of the group algebra of the symmetric group) to a cellular basis (for example, the Murphy or Kazhdan-Lusztig bases of the group algebra of the symmetric group). Typically it is easy to write the cellular basis elements in terms of standard bases elements but the inverse operation is often tricky.

The nice thing about the way I've done it using module_morphism is that it computes the inverse transition for free (at least when working over a field). So it is sufficient to define the transition from the cellular basis to the standard basis.

If C were a cellular basis class then I would expect C(s,t) to return the cellular basis element indexed by s and t. Strictly speaking, this should be C(mu,s,t) but in all of the interesting examples the "shape" mu (=element of the indexing poset) is implicitly encoded in s and t so there is no need to specify it.

I agree that there should be a mechanism for shortening the input. I think I can add something to the category so that this can be done.

The methods _to_cellular_element and _from_cellular_index should be hidden, as you have them. I would expect them to be called implicitly via commands like A(C(s,t)) and C(A(w)).

You are correct; that is what currently occurs by passing them to module_morphism.

There probably should be a cell_poset method, as you have, but the cell method seems slightly strange to me, I might call this cell_module_indices.

I wasn't too happy with the name cell either. Will change.

The most important method should be a cell_module method that returns the (left or right) cell module: C.cell_module(mu) or perhaps C.left_cell_module(m) and C.right_cell_module(mu). These should be something like a CombinatorialFreeModules and they should come with actions of the algebra.

This is what I am currently working on.

The bilinear form on the cell module would of course be defined on this module. I would expect things the like following to work:

sage: M=SymmetricGroupAlgebra(ZZ,4).Murphy_basis()
sage: Smu=M.cell_module(3,1)
sage: Smu.basis()   
{ S([[1,2,3],[4]]), S([[1,2,4],[3]]), S([[1,3,4],[2]]) ]
sage: M([[1,2,4],[3]], [[1,2,3],[4]]) * S([[1,2,3],[4]])
6*S([[1,2,4],[3]])   
sage: Smu.inner_product([[1,2,3],[4]], [[1,2,3],[4]])
6

Note that indexing set for the basis of the cell modules is your .cell method and that the action of the cellular basis on the cell module gives the inner product.

I'm glad to know that we are on the same page for this.

There are no (good) algorithms for computing the decomposition matrices and Cartan matrices -- except for special cases like the Iwahori-Hecke algebras of types A and B using Kazhdan-Lustzig polynomial combinatorics.

We have the capacity to compute the radical and the quotient in Sage. I guess the trouble is determining the exact decompositions in the quotient. I wasn't so hopeful on this.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

b22a007

Added support for cell modules, but not full doctest coverage yet.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 75215b6 to b22a007

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from b22a007 to c615650

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

c615650

Fixing issues with the action.

[tscrim]

comment:12

Here is a basic implementation for the cell modules. I haven't fully tested it yet, but it should work. I will do more testing tomorrow and get it to full doctest coverage.

Question, what should I rename the method cells to? It doesn't quite fit now that cell -> cell_module_indices.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from c615650 to 98bc475

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

98bc475

Fixing bugs and adding full support and doctests for cell modules.

[tscrim]

comment:14

Okay, so I've tried working on reducing the input for the cellular algebra down to 2 indices at the level of the category and I was running into trouble. I think what I will have to do to implement this is do a subclass of CellularBasis which overrides the category methods.

I'm not sure if I want to put the Iwahori-Hecke algebra into the cellular algebras category unless there is a way we can do it for all (finite) Coxeter groups. This would also work as a good followup ticket too IMO.

The other big thing I want to do is get the action extended to the base algebra and working on the simple modules.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

9b8ad72

Better support for actions by allowing coercions.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 98bc475 to 9b8ad72

[tscrim]

comment:16

With my current framework, I don't think it is really possible to have the cell basis elements only indexed by s,t. This would cause too many inconsistencies and to shift away from this would restrict the generality of the cell module indices and force them to be unique. So I think it is something we are best just living with.

I've done everything that I wanted to do for this ticket. I am open to suggestions as well.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

45741e3	Merge branch 'public/categories/cellular_algebras-19506' into 7.0.rc1
a8822d0	trac #19506 correct Cartesian spelling

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 9b8ad72 to a8822d0

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

879567b

Merge branch 'public/categories/cellular_algebras-19506' in 7.5.b2

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from a8822d0 to 879567b

[fchapoton]

comment:19

2 failing doctests (missing import)

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

9e25877

Added missing import statement.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 879567b to 9e25877

[tscrim]

comment:21

Fixed.

[cheuberg]

comment:22

failing doctest (deprecation warning, cf. patchbot)

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

acc5eea	Merge branch 'public/categories/cellular_algebras-19506' of git://trac.sagemath.org/sage into public/categories/cellular_algebras-19506
276d529	Fix due to move of dic BLAS.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 9e25877 to 276d529

[fchapoton]

comment:25

does not apply

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 276d529 to a69a7f5

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

a69a7f5

Merge branch 'public/categories/cellular_algebras-19506' of git://trac.sagemath.org/sage into public/categories/cellular_algebras-19506

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

f3960e1

Expanding documentation and fixing some issues

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from a69a7f5 to f3960e1

[AndrewMathas]

comment:29

Hi Travis, this looks good. I wonder about the wisdom of having the code scatter between sage.categories and sage.algebras but I suspect that this is forced on you because you want to allow this code to be used axiomatically. Some of the documentation was not displaying properly so I have fixed this and expanded the documentation in places. Please have a look and tell what you think. If you are happy with my changes then I a happy to give this a positive review. I tried to add a few seealso, which would benefit from being looked at.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

1bac49b

A few additional doc tweaks.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from f3960e1 to 1bac49b

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

a1a2ae2

Fixing doc references.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 1bac49b to a1a2ae2

[tscrim]

comment:32

I made a few other cosmetic changes, fixed a few typos, moved/added stuff in the doc reference listing, and removed the cellular basis from the catalog documentation because it is not accessible via the catalog. I understand why you put the cellular_basis in the finite-dimensional algebras portion, but I decided to move that out of there because it was not connected with that specific implementation. (Also, in principle, it could eventually contain a basis for related generalizations like affine cellular algebras.) If my changes are good, then you can set a positive review.

[AndrewMathas]

Reviewer: Andrew Mathas

[AndrewMathas]

comment:33

All good.

[vbraun]

comment:34

PDF docs don't build