Implement Verma modules

[tscrim]

This implements Verma modules for Lie algebras (currently only implemented for the Chevalley basis implementation) and their homomorphisms (as U(g)-representations). In order to make this code to be potentially useful for affine Lie algebras, this creates the category of Kac-Moody algebras and the subcategory of those with a basis that respects the triangular decomposition.

Depends on #23375

CC: @sagetrac-sage-combinat @bsalisbury1

Component: algebra

Keywords: lie algebras

Author: Travis Scrimshaw

Branch/Commit: 0376efd

Reviewer: Sebastian Oehms

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

[tscrim]

comment:1

The eventual goal is to be able to construct highest weight representations by quotienting each weight space by the corresponding weight space of the Verma submodules (of which, there are only a finite number that contribute). This code should also be extendable to the quantum group case once that PBW basis is implemented.

In order to have the action of the Lie algebra directly, you also need #23440. I originally wrote the doctests without #23440, so I did not include it as a dependency (nor updated/added any doctests).

---

New commits:

3271f6d	Fixing preimage for PBW bases.
750c712	Fixing ordering of indices vs _basis_key.
8864277	Merge branch 'public/lie_algebras/fix_stucture_coeffs-23373' of git://trac.sagemath.org/sage into public/lie_algebras/fix_pbw_preimage-23375
08bd36a	Initial implementation of Verma modules.
1e3a529	Moving _basis_key to the category.
890aa22	Finishing implementation and doctest coverage of Verma modules.
e5c1c35	Fixing doctests and some other little finishing touches.

[tscrim]

Branch: public/lie_algebras/verma_modules-23517

[tscrim]

Commit: e5c1c35

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

Changed commit from e5c1c35 to 21339b1

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

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

9046b90	Fixing doctest failure.
8baf26a	Merge branch 'public/lie_algebras/fix_stucture_coeffs-23373' into public/lie_algebras/fix_pbw_preimage-23375
21339b1	Merge branch 'public/lie_algebras/fix_pbw_preimage-23375' into public/lie_algebras/verma_modules-23517

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

Changed commit from 21339b1 to 62e11e6

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

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

bc4dbf5	Making doctest robust.
33cea7d	Fixing preimage for PBW bases.
09ca385	Initial implementation of Verma modules.
633d70c	Moving _basis_key to the category.
c19998f	Finishing implementation and doctest coverage of Verma modules.
d5291cc	Fixing doctests and some other little finishing touches.
62e11e6	Fixing doctest failure.

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

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

c3225c7	Merge branch 'public/lie_algebras/verma_modules-23517' of git://trac.sagemath.org/sage into public/lie_algebras/verma_modules-23517
24f7006	Make _basis_key always return a KeyError and fix bad merging.
3f9ec19	Exponentiation is more strict with input type.

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

Changed commit from 62e11e6 to 3f9ec19

[tscrim]

comment:5

3rr0rz b3 pwn3d. :P

[soehms]

Reviewer: Sebastian Oehms

[soehms]

comment:6

I've checked the functionality from the point of view of a non expert who is familiar with the involved basic concepts. In this context, I noticed the following Problems:

1) A performance problem which I observed when I tried to define the irreducible 12-dimensional representation of sl2 and which should certainly be fixed:

sage: Lsl2 = lie_algebras.sl(ZZ, 2)
sage: WL = Lsl2.cartan_type().root_system().weight_lattice()
sage: La = WL.fundamental_weights()
sage: M = Lsl2.verma_module( 11* La[1])
sage: E, F, H =Lsl2.gens()
sage: PBW = Lsl2.pbw_basis()
sage: e, f, h = PBW(E), PBW(F), PBW(H)
sage: v = M.highest_weight_vector()
sage: v1bas=(f*v).support()[0]
sage:
sage: timeit('E = matrix( 12, 12, lambda i,j: (e*f**i*v).coefficient(v1bas**j))')
5 loops, best of 3: 6 s per loop

For this statement more than 57000 calls of the method _triangular_key where needed. After inserting the "@cached_method" decorator to the "_acted_upon" -method the same query gave:

sage: timeit('E = matrix( 12, 12, lambda i,j: (e*f**i*v).coefficient(v1bas**j))')
5 loops, best of 3: 30.3 ms per loop

The "@cached_method" decorator to the "_acted_upon"-method does also improve the statement of your example in the "singular_vector"-method of the VermaModuleHomset-class which is marked as "long time".

Without decorator:

sage: timeit('all(e * v == M.zero() for e in E)')
5 loops, best of 3: 5.98 s per loop

With decorator:

sage: timeit('all(e * v == M.zero() for e in E)')
5 loops, best of 3: 3.77 µs per loop

2) Another performance problem I noticed when calculating singular vectors. Partly, this seems to be caused by multiplication in the universal enveloping algebra:

sage: Lsp6 = lie_algebras.sp(QQ, 6)                
sage: La = Lsp6.cartan_type().root_system().weight_space().fundamental_weights()
sage: la =    La[1]           - La[3] 
sage: mu = -3*La[1] - 2*La[2] - La[3]
sage: Mla = Lsp6.verma_module(la)
sage: Mmu = Lsp6.verma_module(mu)
sage: MuLa = Hom(Mmu, Mla)
sage: timeit('MuLa.singular_vector()', number=1r, repeat=1r)
1 loops, best of 1: 81.9 s per loop

sage: pbw =Lsp6.pbw_basis()
sage: f = Lsp6.f()
sage: F = {i: pbw(f[i]) for i in f.keys()}
sage: elt = F[3]**3*F[2]**3*F[1]**2
sage: timeit('F[2]**3*elt')
5 loops, best of 3: 710 ms per loop

Adding a cached_method decorator to the product_on_basis method of the PoincareBirkhoffWittBasis-class improved the needed time:

sage: timeit('MuLa.singular_vector()', number=1r, repeat=1r)
1 loops, best of 1: 16.6 s per loop

sage: timeit('F[2]**3*elt', number=1r, repeat=1r)
1 loops, best of 1: 272 ms per loop

If you can find a more structural and more satisfactory way to fix these performance issues, I would prefer this instead of the decorator approach.

3) I recommend to improve several doc-strings missing an INPUT section. Without these descriptions it is really hard for a persons that is not familiar with all special constructions in the Lie Algebra setting to understand what these methods do. For example it would be much easier to understand the "_monoid_key" method, if there would be a description like this (missing in PoincareBirkhoffWittBasis as well):

INPUT::

- `x` -- a tuple (alpha, n) describing an item of the dictionary of a basis element. Since the basis is indexed by the 
                            free abelian monoid generated by the basis of L such an item consist of an element
                            alpha of the basis of L together with an integer n indicating the exponent of alpha

Also, a more explicit example would help to understand this, for example, inserting the following line after the definition of M:

EXAMPLES::

...................
sage: M = L.verma_module(La[1])
sage: [ M._monoid_key((bas_ele, 1)) for bas_ele in L.basis().keys() ]
      [0, 1, 2, 3, 4, 5, 6, 7]

similar issues hold for "_triangular_key" and "_monomial_key". An "INPUT" section should also be added to the methods "degree_on_basis" and "homogeneous_component_basis", since these are directly accessed by the user.

Instead of improving the doc-string in cases where performance doesn't matter you may think about argument checks. For example, in the case of "_repr_generator" (similar "_latex_generator") a check like

if m not in M.basis().keys():
     raise ValueError

would avoid confusions like this:

sage: L = lie_algebras.sp(QQ, 4)
sage: La = L.cartan_type().root_system().ambient_space().fundamental_weights()
sage: M = L.verma_module(-1/2*La[1] + 3/7*La[2])
sage: m_wrong = M.basis().keys().indices()[2]
sage: m_right = M.basis().keys()[2]
sage: M.basis()[m_wrong]
-2*alpha[1] - alpha[2]*v[(-1/14, 3/7)]
sage: M.basis()[m_right]
f[-alpha[1] - alpha[2]]*v[(-1/14, 3/7)]
sage: 

4) Is the following really intended?

sage: pbw_verma = M.pbw_basis()
sage: pbw_lie   = L.pbw_basis()
sage: 
sage: pbw_verma == pbw_lie
False
sage: pbw_verma(L.e(1)) == pbw_lie(L.e(1))
True
sage: pbw_lie(L.e(1)) in pbw_verma
False

I am astonished about the first "False". The curiosity about the "True" seems to be inherited from CombinatorialFreeModule (which in my point of view is a bug, but I don't know if already reported):

sage: S3 = SymmetricGroup(3)
sage: S4 = SymmetricGroup(4)
sage: GA3 = S3.algebra(QQ)
sage: GA4 = S4.algebra(QQ)
sage: GA3.zero() == GA4.zero()
True
sage: GA3.zero() in GA4
False

[tscrim]

comment:7

Replying to @soehms:

I've checked the functionality from the point of view of a non expert who is familiar with the involved basic concepts. In this context, I noticed the following Problems:

Thank you for taking a look at this and the detailed review.

1) A performance problem which I observed when I tried to define the irreducible 12-dimensional representation of sl2 and which should certainly be fixed:

[snip]

For this statement more than 57000 calls of the method _triangular_key where needed. After inserting the "@cached_method" decorator to the "_acted_upon" -method the same query gave:

It is a very bad idea to cache _acted_upon_ because that means (k*e) * v, is cached for all k in the ground field. That is very likely to explode the cache, and as such, is something that should not be done.

2) Another performance problem I noticed when calculating singular vectors. Partly, this seems to be caused by multiplication in the universal enveloping algebra:

[snip]

Adding a cached_method decorator to the product_on_basis method of the PoincareBirkhoffWittBasis-class improved the needed time:

This one is much more reasonable to do. Unfortunately I do not see a way out of the recursive construction of the PBW multiplication. There might be a way to reduce some of the intermediate objects and helper function calls, but that would require a fair bit of work.

I was not expecting so much of a difference in timings because I figured most calls would need to be done irregardless and the lower order computations would not be a significant factor. So I opted for the lower memory usage approach. I will change this to use @cached_method.

3) I recommend to improve several doc-strings missing an INPUT section. Without these descriptions it is really hard for a persons that is not familiar with all special constructions in the Lie Algebra setting to understand what these methods do. For example it would be much easier to understand the "_monoid_key" method, if there would be a description like this (missing in PoincareBirkhoffWittBasis as well):

INPUT::

- `x` -- a tuple (alpha, n) describing an item of the dictionary of a basis element. Since the basis is indexed by the 
                            free abelian monoid generated by the basis of L such an item consist of an element
                            alpha of the basis of L together with an integer n indicating the exponent of alpha

I disagree. This just says what the code (because if you're looking at this, you must already be looking at the code) and the one-line description already does. I can add this if you insist, but I think it does not have any value because the code does the talking. (In fact, it is effectively a more documented/tested lambda function.)

Also, a more explicit example would help to understand this, for example, inserting the following line after the definition of M:

EXAMPLES::

...................
sage: M = L.verma_module(La[1])
sage: [ M._monoid_key((bas_ele, 1)) for bas_ele in L.basis().keys() ]
      [0, 1, 2, 3, 4, 5, 6, 7]

I can add it, but I do not think it helps at all. IMO, the sorted showing how the more macro behavior changes is more useful to understand how to use the function.

similar issues hold for "_triangular_key" and "_monomial_key". An "INPUT" section should also be added to the methods "degree_on_basis" and "homogeneous_component_basis", since these are directly accessed by the user.

Yes, but IMO, they are an implementation detail and should be hidden (and never called by a user). So I am treating them as such, and do not think they need to be as extensively documented.

Instead of improving the doc-string in cases where performance doesn't matter you may think about argument checks. For example, in the case of "_repr_generator" (similar "_latex_generator") a check like

[snip]

No, it would not. The fundamental problem is Family, the object returned by basis(), plays it safe (in the sense that containment checking might be impossible or prohibitively expensive) and fast by not checking something is in the keys. This is an known complaint, but I sort of see it as garbage-in-garbage-out. There are a few subtle speed issues because of possibly changing the behavior of Family. In addition, such a proposed check would just result in a message saying the repr was bad; it wouldn't prevent you from creating and manipulating the elements.

4) Is the following really intended?

[snip]

I am astonished about the first "False". The curiosity about the "True" seems to be inherited from CombinatorialFreeModule (which in my point of view is a bug, but I don't know if already reported):

[snip]

It is not a bug but a feature. For equality, coercion is used (e.g., do you want 2/2 == 1 to be False because they are different parents?). So if there is a common parent, then it coerces to said parent and performs the computation in there. __contains__ is under no such obligation. With that being said, there is #22707 to default to the generic Parent.__contains__, which should make the last one be True.

[soehms]

comment:8

Replying to @tscrim:

Replying to @soehms:

[snip]

For this statement more than 57000 calls of the method _triangular_key where needed. After inserting the "@cached_method" decorator to the "_acted_upon" -method the same query gave:

It is a very bad idea to cache _acted_upon_ because that means (k*e) * v, is cached for all k in the ground field. That is very likely to explode the cache, and as such, is something that should not be done.

I didn't mean that this should be the solution. So, take this experiment as a hint which shows that there is a potential to improve the performance by a factor of 200. If you find another way to reach a part of this potential, it would be fine, as well. But please decide by yourself if effort stands in relation to the result and don't mind if there is no practical way.

[snip]

3) I recommend to improve several doc-strings missing an INPUT section. Without these descriptions it is really hard for a persons that is not familiar with all special constructions in the Lie Algebra setting to understand what these methods do. For example it would be much easier to understand the "_monoid_key" method, if there would be a description like this (missing in PoincareBirkhoffWittBasis as well):

INPUT::

- `x` -- a tuple (alpha, n) describing an item of the dictionary of a basis element. Since the basis is indexed by the 
                            free abelian monoid generated by the basis of L such an item consist of an element
                            alpha of the basis of L together with an integer n indicating the exponent of alpha

I disagree. This just says what the code (because if you're looking at this, you must already be looking at the code) and the one-line description already does. I can add this if you insist, but I think it does not have any value because the code does the talking. (In fact, it is effectively a more documented/tested lambda function.)

Certainly this can be seen from the code. But if you start from zero and must figure out where _basis_key comes from (...) it isn't that easy as it seems to you who knows all these constructions. Now, you may say, one has to figure out these things, anyway. But such hints in the documentation would accelerate this process a lot. And surely I will not be the last person, that starts from zero finding out how this code works. So, you will save more human resources as you put in. I will not insist on this issue. But please think about improvements (which must not necessarily follow my suggestions) from this point of view, again.

[snip]

similar issues hold for "_triangular_key" and "_monomial_key". An "INPUT" section should also be added to the methods "degree_on_basis" and "homogeneous_component_basis", since these are directly accessed by the user.

Yes, but IMO, they are an implementation detail and should be hidden (and never called by a user). So I am treating them as such, and do not think they need to be as extensively documented.

But why did you use names without leading "_", than?

[snip]

I am astonished about the first "False". The curiosity about the "True" seems to be inherited from CombinatorialFreeModule (which in my point of view is a bug, but I don't know if already reported):

[snip]

It is not a bug but a feature. For equality, coercion is used (e.g., do you want 2/2 == 1 to be False because they are different parents?). So if there is a common parent, then it coerces to said parent and performs the computation in there. __contains__ is under no such obligation. With that being said, there is #22707 to default to the generic Parent.__contains__, which should make the last one be True.

Ah, now I remember! You explained this before in connection with the matrix-method for the classical Lie algebras. I agree with that (under the restrictions pointed out by Nicolas Thiery in the Ticket you mentioned). I hope I will not ask this again! By the way: what I was really asking here was a stupid question which I have answered by myself: The pbw_basis are different because of the different _basis_key!

Please note, that I will not respond until the 4. of June (because of vacation)!

[tscrim]

comment:9

Replying to @soehms:

Replying to @tscrim:

Replying to @soehms:

3) I recommend to improve several doc-strings missing an INPUT section. Without these descriptions it is really hard for a persons that is not familiar with all special constructions in the Lie Algebra setting to understand what these methods do. For example it would be much easier to understand the "_monoid_key" method, if there would be a description like this (missing in PoincareBirkhoffWittBasis as well):

INPUT::

- `x` -- a tuple (alpha, n) describing an item of the dictionary of a basis element. Since the basis is indexed by the 
                            free abelian monoid generated by the basis of L such an item consist of an element
                            alpha of the basis of L together with an integer n indicating the exponent of alpha

I disagree. This just says what the code (because if you're looking at this, you must already be looking at the code) and the one-line description already does. I can add this if you insist, but I think it does not have any value because the code does the talking. (In fact, it is effectively a more documented/tested lambda function.)

Certainly this can be seen from the code. But if you start from zero and must figure out where _basis_key comes from (...) it isn't that easy as it seems to you who knows all these constructions. Now, you may say, one has to figure out these things, anyway. But such hints in the documentation would accelerate this process a lot. And surely I will not be the last person, that starts from zero finding out how this code works. So, you will save more human resources as you put in. I will not insist on this issue. But please think about improvements (which must not necessarily follow my suggestions) from this point of view, again.

I have, and I cannot think of a way to explain it that is more clear than just reading the code (and is not sensitive to internal changes in the monoid's data structure). Plus most of them have doctests that gives you sample in/output. Some of it is the natural resistance of the language (lack of good ways to give API specifications unlike, say, header files in C++).

similar issues hold for "_triangular_key" and "_monomial_key". An "INPUT" section should also be added to the methods "degree_on_basis" and "homogeneous_component_basis", since these are directly accessed by the user.

Yes, but IMO, they are an implementation detail and should be hidden (and never called by a user). So I am treating them as such, and do not think they need to be as extensively documented.

But why did you use names without leading "_", than?

That is how they are defined in the category and is what is looked for by the general framework. So they currently have to be this way and would require changes likely to a good portion of Sage's codebase.

Please note, that I will not respond until the 4. of June (because of vacation)!

I hope you are enjoying your vacation.

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

Changed commit from 3f9ec19 to 2fcc51d

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

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

39498c2	Merge branch 'public/lie_algebras/verma_modules-23517' of trac.sagemath.org:sage into public/lie_algebras/verma_modules-23517
2fcc51d	Caching products and Q in classical Lie algebras.

[tscrim]

comment:11

I cached the product and also the root lattice for the classical Lie algebras as this object was repeatedly being recreated. I added an example to _monoid_key, but it really is just retesting things that are in FreeAbelianIndexedMonoid (and in the # indirect doctest). I do not think it contribute anything to understanding how the function is used, which is all essentially internal via the __init__ and the corresponding basis indexing class.

[soehms]

comment:14

Replying to @tscrim:

Replying to @soehms:

Replying to @tscrim:

Replying to @soehms:

3) I recommend to improve several doc-strings missing an INPUT section. Without these ...

[snip]

.... I will not insist on this issue. But please think about improvements (which must not necessarily follow my suggestions) from this point of view, again.

I have, and I cannot think of a way to explain it that is more clear than just reading the code (and is not sensitive to internal changes in the monoid's data structure). Plus most of them have doctests that gives you sample in/output. Some of it is the natural resistance of the language (lack of good ways to give API specifications unlike, say, header files in C++).

I completely understand that you like to avoid redundancies. A way out would be to describe the structure in a comment, for example concerning input/output see the doctests of ... (including your sign and the current date). My colleague, sharing my office room, educated me to write much more comments as I did 20 years ago. Today, I am still far behind her (in amount of comments) but I must confess that she was right to do that. Even to understand your own code after a couple of years and even if the comment has run out of date this helps a lot. But this is a topic which we better should discuss by word of mouth in Zaragoza.

similar issues hold for "_triangular_key" and "_monomial_key". An "INPUT" section should also be added to the methods "degree_on_basis" and "homogeneous_component_basis", since these are directly accessed by the user.

Yes, but IMO, they are an implementation detail and should be hidden (and never called by a user). So I am treating them as such, and do not think they need to be as extensively documented.

But why did you use names without leading "_", than?

That is how they are defined in the category and is what is looked for by the general framework. So they currently have to be this way and would require changes likely to a good portion of Sage's codebase.

I see!

Please note, that I will not respond until the 4. of June (because of vacation)!

I hope you are enjoying your vacation.

Thanks! Yes, we did (after we needed one extra day to get there, because the french air traffic control was on strike)!

[soehms]

comment:15

Now everything looks fine to me, accept that I am still running into the pdf-docbuild failure:

? ! Undefined control sequence.
<argument> \split@tag \begin {split}\dim (\Hom
                                               (M_{w \cdot \lambda }, M_{w' ...
l.38677 ... M_{w' \cdot \lambda'})) = 1\end{split}

?
LaTeX Warning: Hyper reference `sage/algebras/lie_algebras/verma_module:sage.al

Further, by your improvements you may now erase the # long time mark in the singular_vector method. On my machine this command now takes 103 ms (it had been nearly 6 seconds before your changes).

If these things are done you may switch to positive review!

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

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

fd6fd79	Merge branch 'public/lie_algebras/verma_modules-23517' of git://trac.sagemath.org/sage into public/lie_algebras/verma_modules-23517
0376efd	Some doc fixes and removing a "# long time".

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

Changed commit from 2fcc51d to 0376efd

[tscrim]

comment:17

Fixed (\Hom -> \hom). Thank you very much.

I am happy to talk about ways we can try to improve things in Zaragoza. I look forward to meeting you there!

[vbraun]

Changed branch from public/lie_algebras/verma_modules-23517 to 0376efd