Opened 5 years ago
Closed 4 years ago
#23517 closed enhancement (fixed)
Implement Verma modules
Reported by:  tscrim  Owned by:  

Priority:  major  Milestone:  sage8.3 
Component:  algebra  Keywords:  lie algebras 
Cc:  sagecombinat, bsalisbury1  Merged in:  
Authors:  Travis Scrimshaw  Reviewers:  Sebastian Oehms 
Report Upstream:  N/A  Work issues:  
Branch:  0376efd (Commits, GitHub, GitLab)  Commit:  0376efd68c8c569b06843446358a4c32d13b10e5 
Dependencies:  #23375  Stopgaps: 
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 KacMoody algebras and the subcategory of those with a basis that respects the triangular decomposition.
Change History (18)
comment:1 Changed 5 years ago by
 Branch set to public/lie_algebras/verma_modules23517
 Commit set to e5c1c354ea25e1a2423b8544c328ab773ab62ab8
 Status changed from new to needs_review
comment:2 Changed 5 years ago by
 Commit changed from e5c1c354ea25e1a2423b8544c328ab773ab62ab8 to 21339b1addd67780aedcaad6b6f22720ffdbba57
Branch pushed to git repo; I updated commit sha1. New commits:
9046b90  Fixing doctest failure.

8baf26a  Merge branch 'public/lie_algebras/fix_stucture_coeffs23373' into public/lie_algebras/fix_pbw_preimage23375

21339b1  Merge branch 'public/lie_algebras/fix_pbw_preimage23375' into public/lie_algebras/verma_modules23517

comment:3 Changed 5 years ago by
 Commit changed from 21339b1addd67780aedcaad6b6f22720ffdbba57 to 62e11e68e08da7bb6bec01580e535db7a530253f
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
 Commit changed from 62e11e68e08da7bb6bec01580e535db7a530253f to 3f9ec19ea500031ed468876854db64c1b2d4436d
Branch pushed to git repo; I updated commit sha1. New commits:
c3225c7  Merge branch 'public/lie_algebras/verma_modules23517' of git://trac.sagemath.org/sage into public/lie_algebras/verma_modules23517

24f7006  Make _basis_key always return a KeyError and fix bad merging.

3f9ec19  Exponentiation is more strict with input type.

comment:6 followup: ↓ 7 Changed 4 years ago by
 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 12dimensional 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 docstrings 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 docstring 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 ; followup: ↓ 8 Changed 4 years ago by
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 12dimensional 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 docstrings 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 oneline 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 docstring 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 garbageingarbageout. 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 ; followup: ↓ 9 Changed 4 years ago by
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 allk
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 docstrings 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 alphaI disagree. This just says what the code (because if you're looking at this, you must already be looking at the code) and the oneline 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 beFalse
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 genericParent.__contains__
, which should make the last one beTrue
.
Ah, now I remember! You explained this before in connection with the matrixmethod 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 ; followup: ↓ 14 Changed 4 years ago by
Replying to soehms:
Replying to tscrim:
Replying to soehms:
3) I recommend to improve several docstrings 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 alphaI disagree. This just says what the code (because if you're looking at this, you must already be looking at the code) and the oneline 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
 Commit changed from 3f9ec19ea500031ed468876854db64c1b2d4436d to 2fcc51d52d97b2bebca913d90313d182b401073d
comment:11 Changed 4 years ago by
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.
comment:12 Changed 4 years ago by
 Cc bsalisbury1 added; salisbury1 removed
comment:13 Changed 4 years ago by
 Milestone changed from sage8.2 to sage8.3
 Status changed from needs_work to needs_review
comment:14 in reply to: ↑ 9 Changed 4 years ago by
Replying to tscrim:
Replying to soehms:
Replying to tscrim:
Replying to soehms:
3) I recommend to improve several docstrings 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
Now everything looks fine to me, accept that I am still running into the pdfdocbuild 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
 Commit changed from 2fcc51d52d97b2bebca913d90313d182b401073d to 0376efd68c8c569b06843446358a4c32d13b10e5
comment:17 Changed 4 years ago by
 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
 Branch changed from public/lie_algebras/verma_modules23517 to 0376efd68c8c569b06843446358a4c32d13b10e5
 Resolution set to fixed
 Status changed from positive_review to closed
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:
Fixing preimage for PBW bases.
Fixing ordering of indices vs _basis_key.
Merge branch 'public/lie_algebras/fix_stucture_coeffs23373' of git://trac.sagemath.org/sage into public/lie_algebras/fix_pbw_preimage23375
Initial implementation of Verma modules.
Moving _basis_key to the category.
Finishing implementation and doctest coverage of Verma modules.
Fixing doctests and some other little finishing touches.