Opened 5 years ago

Closed 4 years ago

# Implement Verma modules

Reported by: Owned by: tscrim major sage-8.3 algebra lie algebras sage-combinat, bsalisbury1 Travis Scrimshaw Sebastian Oehms N/A 0376efd 0376efd68c8c569b06843446358a4c32d13b10e5 #23375

### Description

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.

### comment:1 Changed 5 years ago by tscrim

• Branch set to public/lie_algebras/verma_modules-23517
• Commit set to e5c1c354ea25e1a2423b8544c328ab773ab62ab8
• Status changed from new to needs_review

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.

### comment:2 Changed 5 years ago by git

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

### comment:3 Changed 5 years ago by git

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.

### comment:4 Changed 4 years ago by git

• Commit changed from 62e11e68e08da7bb6bec01580e535db7a530253f to 3f9ec19ea500031ed468876854db64c1b2d4436d

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.

### comment:5 Changed 4 years ago by tscrim

• Milestone changed from sage-8.1 to sage-8.2

3rr0rz b3 pwn3d. :P

### comment:6 follow-up: ↓ 7 Changed 4 years ago by soehms

• Reviewers set to Sebastian Oehms
• Status changed from needs_review to needs_work

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


### comment:7 in reply to: ↑ 6 ; follow-up: ↓ 8 Changed 4 years ago by tscrim

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.

### comment:8 in reply to: ↑ 7 ; follow-up: ↓ 9 Changed 4 years ago by 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)!

### comment:9 in reply to: ↑ 8 ; follow-up: ↓ 14 Changed 4 years ago by tscrim

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.

### comment:10 Changed 4 years ago by git

• Commit changed from 3f9ec19ea500031ed468876854db64c1b2d4436d to 2fcc51d52d97b2bebca913d90313d182b401073d

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.

### comment:11 Changed 4 years ago by tscrim

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.

Last edited 4 years ago by tscrim (previous) (diff)

### comment:12 Changed 4 years ago by bsalisbury1

• Cc bsalisbury1 added; salisbury1 removed

### comment:13 Changed 4 years ago by tscrim

• Milestone changed from sage-8.2 to sage-8.3
• Status changed from needs_work to needs_review

### comment:14 in reply to: ↑ 9 Changed 4 years ago by 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)!

### comment:15 Changed 4 years ago by soehms

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!

### comment:16 Changed 4 years ago by git

• Commit changed from 2fcc51d52d97b2bebca913d90313d182b401073d to 0376efd68c8c569b06843446358a4c32d13b10e5

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

### comment:17 Changed 4 years ago by tscrim

• Status changed from needs_review to positive_review

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!

### comment:18 Changed 4 years ago by vbraun

• Branch changed from public/lie_algebras/verma_modules-23517 to 0376efd68c8c569b06843446358a4c32d13b10e5
• Resolution set to fixed
• Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.