#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 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 this, 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.
--
Ticket URL: <http://trac.sagemath.org/ticket/19506#comment:8>
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.
