#19506: Implement cellular algebras
-------------------------------------+-------------------------------------
Reporter: tscrim | Owner: sage-combinat
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-6.10
Component: categories | Resolution:
Keywords: cellular algebra | Merged in:
Authors: Travis Scrimshaw | Reviewers:
Report Upstream: N/A | Work issues:
Branch: | Commit:
public/categories/cellular_algebras-19506|
75215b6d63159e95b21e9d95d2f6e8f9a2cfc1aa
Dependencies: | Stopgaps:
-------------------------------------+-------------------------------------
Comment (by tscrim):
Thank you for your detailed response.
Replying to [comment:8 andrew.mathas]:
> Replying to [comment:5 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.
--
Ticket URL: <http://trac.sagemath.org/ticket/19506#comment:9>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/sage-trac.
For more options, visit https://groups.google.com/d/optout.
