Opened 11 years ago
Last modified 8 years ago
#6588 closed enhancement
Categories for root systems and many misc improvements — at Version 20
Reported by: | nthiery | Owned by: | mhansen |
---|---|---|---|
Priority: | major | Milestone: | sage-5.0 |
Component: | combinatorics | Keywords: | root systems, categories |
Cc: | sage-combinat, mshimo@… | Merged in: | |
Authors: | Nicolas M. Thiéry | Reviewers: | Anne Schilling, Mark Shimozono, PatchBot |
Report Upstream: | N/A | Work issues: | |
Branch: | Commit: | ||
Dependencies: | #10817 | Stopgaps: |
Description (last modified by )
New Features:
- Extended weight lattice/space for affine types - coxeter_matrix and coxeter_diagram (for crystallographic types) - Embeddings of the root lattice/space in root lattice realizations - Embeddings of the weight lattice/space in weight lattice realizations - Partial conversion from the root space to the root lattice - Iterator for any Coxeter group, and weak order ideals thereof - Facade option for weak_poset's and bruhat_poset's of finite coxeter groups - weak_poset's of finite coxeter groups are lattices; added link weak_lattice -> weak_poset (courtesy of Christian Stump) - Enumerated set for grassmannian elements, and is_grasmmannian test - Added method register_as_conversion to morphisms
Refactoring:
- RootLatticeRealization and WeightLatticeRealization are now categories - Use abstract_methods where appropriate - Cleanup of an_element - to_coroot_lattice_morphism: renamed to to_coroot_lattice_space, and moved from RootLatticeRealization to RootSpace (it does not make sense for, e.g., the weight lattice). - Moved the implementation of associated_coroot in root_lattice_realization to root_space where it belongs
Tests and bug fixes:
- 100% doctests on sage.combinat.root_system, except for weyl_group and weyl_characters - 100% doctests on CoxeterGroups - Add minimal documentation to AffineWeylGroups - Added systematic tests for associated_coroot - Fixed further missing features revealed by this test: - reducible Cartan types were not seen as finite/simply laced/crystallographic as appropriate - symmetrizer needed to be generalized to reducible cartan types (including D2) - the relabelling for reducible cartan types was broken for affine types - More tests for scalar products - Added systematic consistency check between the simple_root and simple_roots methods - same thing for fundamental_weight and fundamental_weights - Fixed a SL vs GL glitch when obtaining simple roots for reducible cartan types revealed by the above - Fixed imports (extraneous ones, and a missing one reported by M. Shimozono and others)
Change History (21)
comment:1 Changed 8 years ago by
- Cc mshimo@… added
- Dependencies set to #10963, #10817
- Description modified (diff)
- Report Upstream set to N/A
comment:2 Changed 8 years ago by
- Description modified (diff)
- Summary changed from Root systems: categorification to Categories for root systems
comment:3 Changed 8 years ago by
- Description modified (diff)
comment:4 follow-up: ↓ 6 Changed 8 years ago by
- Status changed from new to needs_review
comment:5 Changed 8 years ago by
Beside, I commuted it up the Sage-Combinat queue. In principle, there should not be other dependencies than the listed ones.
comment:6 in reply to: ↑ 4 Changed 8 years ago by
Replying to nthiery:
The updated patch adds many missing doctests, and improves coxeter diagrams. It's probably close to completion, up to fixing some potentially failing doctests.
There are indeed a couple minor ones:
http://sage.math.washington.edu/home/nthiery/trac_6588-categories-root_systems-nt.patch-testlog
Note: that's with the following patches applied on 5.0.beta5:
trac_12476-lattice_join_matrix_speedup-fh.patch trac_9469-category-membership_without_arguments-nt.patch trac_10603-union_enumset_elconstr_fix-fh.patch trac_12528_free_module-optimize-nt.patch trac_10817-generalized_associahedra-cs.patch trac_10817-generalized_associahedra-review-nt.patch trac_12078-see_also-fh.patch trac_9128-intersphinx_python_database-fh.patch trac_9128-sphinx_links_all-fh.patch trac_12527-fraction_field-is_exact_optimization-nt.patch trac_12510-nonzero_equal_consistency-fh.patch trac_12536-linear_extensions-as.patch trac_12518-enumerated_set_from_iterator-vd.patch trac_11880.patch trac_11880-graph_classes-review-nt.patch trac_7980-multiple-realizations-nt.patch trac_7980-multiple-realizations-review-nt.patch trac_6588-categories-root_systems-nt.patch
Off for skiing :-)
comment:7 Changed 8 years ago by
I fixed the doctests failures due to this patch. Most of them where due to the fact that affine weyl groups are iterable now, which gives a nicer an_element on any free module thereupon.
The other doctests failures showing up in the log are related to #12518 (or to the ISGCI patch, but that's because I did not upload the appropriate database on my test server).
The review can start!
comment:8 Changed 8 years ago by
- Dependencies changed from #10963, #10817 to #10817
- Description modified (diff)
Patch updated after a bug report by Mark; see end of patch description
comment:9 Changed 8 years ago by
Upon popular demand, extended weight lattice/spaces are now implemented.
comment:10 follow-up: ↓ 11 Changed 8 years ago by
- Reviewers set to Anne Schilling, Mark Shimozono
Hi Nicolas,
Impressive patch! Thanks for working on this. Here are some first comments:
- In /sage/categories/affine_weyl_groups.py there is a new import
from sage.categories.infinite_enumerated_sets import InfiniteEnumeratedSets? which is not used. Please either remove this line or add InfiniteEnumeratedSets? in the class (which is probably preferable).
- In /sage/categories/affine_weyl_groups.py please add a
TestSuite(s).run()
doctest.
- I am not sure this is related to the patch, but there are some
strange methods in /sage/categories/coxeter_groups.py without doctests:
@abstract_method(optional = True) def has_right_descent(self, i):
""" Returns whether i is a right descent of self.
# EXAMPLES:: # # sage:
"""
def has_left_descent(self, i):
""" Returns whether
i
is a left descent of self.
This default implementation uses that a left descent of
w
is a right descent ofw^{-1}
. """ return (~self).has_right_descent(i)
Should has_left_descent also be an abstract_method? Or is that implicit through has_right_descent?
- Why is the cateogry RootLatticeRealization? in
/sage/combinat/root_system/root_lattice_realization.py here and not in categories (if it is a category as specified in the docstring)?
The same question holds for WeightLatticeRealizations?(Category_over_base_ring) in /sage/combinat/root_system/weight_lattice_realization.py.
- When using the extended weight lattice, the list of fundamental weights
does not include \delta
. On the other hand it is possible to input
\delta
into the method fundamental_weight. This seems a little inconsistent.
sage: Q = RootSystem(['A', 3, 1]).weight_lattice(extended = True); Q Extended weight lattice of the Root system of type ['A', 3, 1] sage: Q.fundamental_weights() Finite family {0: Lambda[0], 1: Lambda[1], 2: Lambda[2], 3: Lambda[3]} sage: Q.fundamental_weight('delta') delta
Also, I posted a first reviewer's patch on sage-combinat with mostly just trivial changes. Please fold it if you are satisfied.
Thanks!
Anne
comment:11 in reply to: ↑ 10 ; follow-up: ↓ 12 Changed 8 years ago by
Thanks much Anne for your detailed review!
Replying to aschilling:
- In /sage/categories/affine_weyl_groups.py there is a new import
from sage.categories.infinite_enumerated_sets import InfiniteEnumeratedSets? which is not used. Please either remove this line or add InfiniteEnumeratedSets? in the class (which is probably preferable).
Good point. Done!
- In /sage/categories/affine_weyl_groups.py please add a
TestSuite(s).run()
doctest.
Done.
- I am not sure this is related to the patch, but there are some
strange methods in /sage/categories/coxeter_groups.py without doctests:
CoxeterGroups? is now 100% doctested.
Should has_left_descent also be an abstract_method? Or is that implicit through has_right_descent?
There is a default implementation for this method, so it's not abstract. Indeed, it would be nice to track such dependencies in the documentation; but we don't have the infrastructure for that.
- Why is the cateogry RootLatticeRealization? in
/sage/combinat/root_system/root_lattice_realization.py here and not in categories (if it is a category as specified in the docstring)?
The same question holds for WeightLatticeRealizations?(Category_over_base_ring) in /sage/combinat/root_system/weight_lattice_realization.py.
- When using the extended weight lattice, the list of fundamental weights
does not include
\delta
. On the other hand it is possible to input\delta
into the method fundamental_weight. This seems a little inconsistent.sage: Q = RootSystem(['A', 3, 1]).weight_lattice(extended = True); Q Extended weight lattice of the Root system of type ['A', 3, 1] sage: Q.fundamental_weights() Finite family {0: Lambda[0], 1: Lambda[1], 2: Lambda[2], 3: Lambda[3]} sage: Q.fundamental_weight('delta') delta
More on those after lunch!
Also, I posted a first reviewer's patch on sage-combinat with mostly just trivial changes. Please fold it if you are satisfied.
Folded in! There is a new reviewer's patch on the patch server.
Cheers,
Nicolas
comment:12 in reply to: ↑ 11 ; follow-up: ↓ 16 Changed 8 years ago by
- Why is the cateogry RootLatticeRealization? in
/sage/combinat/root_system/root_lattice_realization.py here and not in categories (if it is a category as specified in the docstring)?
The same question holds for WeightLatticeRealizations?(Category_over_base_ring) in /sage/combinat/root_system/weight_lattice_realization.py.
Yeah, we had a similar discussion for the crystal categories and the categories for Symmetric Functions and friends. And there is a non trivial borderline to set.
On one hand, we have general categories (like Groups, Algebras, ...) which are likely to get used in several Sage modules. Also, they name a well-known area of mathematics; so it's natural to import them by default in the interpreter, if not just as an entry point.
On the other hand we have categories that are rather specific to a Sage module, if not just implementation details. So it's good to keep them in this module, in particular to be as close as close as possible from the other sources of that module.
CoxeterGroups? clearly fits the first case (most mathematicians have heard of them; this category is used by WeylGroup? (in sage.combinat.root_system) and by SymmetricGroup? (in sage.groups).
The categories for symmetric functions are basically implementation details and fits in the second case. Anyway, SymmetricFunctions? is already a good entry point.
Crystals are only implemented in sage.combinat.crystals (so far). But this names an area of mathematics. So this fits a bit more the first case.
RootLatticeRealizations? and WeightLatticeRealizations? seem rather specific. So this fits a bit more the second case.
- When using the extended weight lattice, the list of fundamental weights
does not include
\delta
. On the other hand it is possible to input\delta
into the method fundamental_weight. This seems a little inconsistent.
Yeah, this abuse is documented in "fundamental_weight". Basically, we need a function that describes the embedding of the basis elements of the (extended) weight lattice. That's almost what fundamental_weight does, and I did not have a good alternative name. So I abused fundamental_weight to do just a bit more that its natural job. Anyway, we currently only have a single implementation of WeightLatticeRealizations? in the affine case, so it's very localized, and easy to change in the future if we come up with a good name (unless you have one!).
Let me know if you are ok with the above and with my reviewer's patch. If yes, I'll fold the patches, reindent properly root_lattice_realization.py and weight_lattice_realization.py, and add a 's' at the end of those files (I haven't done those yet to keep the diff meaningful). Then, the patch will be good to go.
For the record, all tests pass on Sage 5.0 beta6, with the following patches applied:
trac_10817-generalized_associahedra-cs.patch trac_12645-fix_rst_markup-sk.patch trac_9128-intersphinx_python_database-fh.patch trac_9128-sphinx_links_all-fh.patch trac_9128-MANIFEST-fh.patch trac_12527-fraction_field-is_exact_optimization-nt.patch trac_12510-nonzero_equal_consistency-fh.patch trac_12536-linear_extensions-as.patch element_compare_consistency-fh.patch trac_11880-isgci-all_in_one-nc.patch trac_11880-isgci-more-review-nt.patch trac_7980-multiple-realizations-nt.patch trac_7980-multiple-realizations-review-nt.patch trac_6588-categories-root_systems-nt.patch trac_6588-categories-root_systems-review-nt.patch
Cheers,
Nicolas
comment:13 follow-up: ↓ 14 Changed 8 years ago by
- Reviewers changed from Anne Schilling, Mark Shimozono to Anne Schilling, Mark Shimozono, PatchBot
- Status changed from needs_review to needs_work
Fails doctests on Sage 5.0.beta7:
sage -t -long devel/sage-main/sage/combinat/root_system/weight_space.py ********************************************************************** File "/storage/masiao/sage-5.0.beta7/devel/sage-main/sage/combinat/root_system/weight_space.py", line 126: sage: Q.null_root(0)[index] Exception raised: Traceback (most recent call last): File "/storage/masiao/sage-5.0.beta7/local/bin/ncadoctest.py", line 1231, in run_one_test self.run_one_example(test, example, filename, compileflags) File "/storage/masiao/sage-5.0.beta7/local/bin/sagedoctest.py", line 38, in run_one_example OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags) File "/storage/masiao/sage-5.0.beta7/local/bin/ncadoctest.py", line 1172, in run_one_example compileflags, 1) in test.globs File "<doctest __main__.example_1[17]>", line 1, in <module> Q.null_root(Integer(0))[index]###line 126: sage: Q.null_root(0)[index] TypeError: __call__() takes exactly 0 positional arguments (1 given) **********************************************************************
(The patchbot found this, but I also reproduced it by hand)
comment:14 in reply to: ↑ 13 Changed 8 years ago by
- Status changed from needs_work to needs_review
Replying to davidloeffler:
Fails doctests on Sage 5.0.beta7:
sage -t -long devel/sage-main/sage/combinat/root_system/weight_space.py ********************************************************************** File "/storage/masiao/sage-5.0.beta7/devel/sage-main/sage/combinat/root_system/weight_space.py", line 126: sage: Q.null_root(0)[index] Exception raised: Traceback (most recent call last): File "/storage/masiao/sage-5.0.beta7/local/bin/ncadoctest.py", line 1231, in run_one_test self.run_one_example(test, example, filename, compileflags) File "/storage/masiao/sage-5.0.beta7/local/bin/sagedoctest.py", line 38, in run_one_example OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags) File "/storage/masiao/sage-5.0.beta7/local/bin/ncadoctest.py", line 1172, in run_one_example compileflags, 1) in test.globs File "<doctest __main__.example_1[17]>", line 1, in <module> Q.null_root(Integer(0))[index]###line 126: sage: Q.null_root(0)[index] TypeError: __call__() takes exactly 0 positional arguments (1 given) **********************************************************************(The patchbot found this, but I also reproduced it by hand)
Sorry, already fixed on the Sage-Combinat queue where the review is occuring. I'll delete the patch here for the moment so that others don't waste time reviewing an outdated version.
Thanks though for the report!
comment:15 Changed 8 years ago by
- Description modified (diff)
comment:16 in reply to: ↑ 12 ; follow-up: ↓ 17 Changed 8 years ago by
Replying to nthiery:
Thanks much Anne for your detailed review!
You are welcome. I hope you will return the favor for trac_12536-linear_extensions-as.patch!
- Why is the cateogry RootLatticeRealization? in
/sage/combinat/root_system/root_lattice_realization.py here and not in categories (if it is a category as specified in the docstring)?
The same question holds for WeightLatticeRealizations?(Category_over_base_ring) in /sage/combinat/root_system/weight_lattice_realization.py.
Yeah, we had a similar discussion for the crystal categories and the categories for Symmetric Functions and friends. And there is a non trivial borderline to set.
On one hand, we have general categories (like Groups, Algebras, ...) which are likely to get used in several Sage modules. Also, they name a well-known area of mathematics; so it's natural to import them by default in the interpreter, if not just as an entry point.
On the other hand we have categories that are rather specific to a Sage module, if not just implementation details. So it's good to keep them in this module, in particular to be as close as close as possible from the other sources of that module.
CoxeterGroups? clearly fits the first case (most mathematicians have heard of them; this category is used by WeylGroup? (in sage.combinat.root_system) and by SymmetricGroup? (in sage.groups).
The categories for symmetric functions are basically implementation details and fits in the second case. Anyway, SymmetricFunctions? is already a good entry point.
Crystals are only implemented in sage.combinat.crystals (so far). But this names an area of mathematics. So this fits a bit more the first case.
No, there is a lot of crystal code in /sage/categories: crystals, finite_crystals, highest_weight_crystals, ....
- When using the extended weight lattice, the list of fundamental weights
does not include
\delta
. On the other hand it is possible to input\delta
into the method fundamental_weight. This seems a little inconsistent.Yeah, this abuse is documented in "fundamental_weight". Basically, we need a function that describes the embedding of the basis elements of the (extended) weight lattice. That's almost what fundamental_weight does, and I did not have a good alternative name. So I abused fundamental_weight to do just a bit more that its natural job. Anyway, we currently only have a single implementation of WeightLatticeRealizations? in the affine case, so it's very localized, and easy to change in the future if we come up with a good name (unless you have one!).
Why can't fundamental_weights when "extended" is set also include delta
? This would at least fit with the notational abuse of fundamental_weight.
Let me know if you are ok with the above and with my reviewer's patch. If yes, I'll fold the patches, reindent properly root_lattice_realization.py and weight_lattice_realization.py, and add a 's' at the end of those files (I haven't done those yet to keep the diff meaningful). Then, the patch will be good to go.
I also wrote another very small reviewer's patch that you can fold in.
For the record, all tests pass on Sage 5.0 beta6, with the following patches applied:
trac_10817-generalized_associahedra-cs.patch trac_12645-fix_rst_markup-sk.patch trac_9128-intersphinx_python_database-fh.patch trac_9128-sphinx_links_all-fh.patch trac_9128-MANIFEST-fh.patch trac_12527-fraction_field-is_exact_optimization-nt.patch trac_12510-nonzero_equal_consistency-fh.patch trac_12536-linear_extensions-as.patch element_compare_consistency-fh.patch trac_11880-isgci-all_in_one-nc.patch trac_11880-isgci-more-review-nt.patch trac_7980-multiple-realizations-nt.patch trac_7980-multiple-realizations-review-nt.patch trac_6588-categories-root_systems-nt.patch trac_6588-categories-root_systems-review-nt.patch
That's good!
Cheers,
Anne
comment:17 in reply to: ↑ 16 ; follow-up: ↓ 18 Changed 8 years ago by
Replying to aschilling:
You are welcome. I hope you will return the favor for trac_12536-linear_extensions-as.patch!
I sure will, soon!
Crystals are only implemented in sage.combinat.crystals (so far). But this names an area of mathematics. So this fits a bit more the first case.
No, there is a lot of crystal code in /sage/categories: crystals, finite_crystals, highest_weight_crystals, ....
I meant: the crystals themselves (CrystalOfLetter?, KR, ...) are all in implemented in sage.combinat.crystals.
Why can't fundamental_weights when "extended" is set also include
delta
? This would at least fit with the notational abuse of fundamental_weight.
Because we want to do things like:
sage: x in self.fundamental_weights()
sage: all(L.some_property() for L in self.fundamental_weights())
So adding delta would change the semantic of fundamental_weights. Whereas the current abuse of fundamental_weight can't break any code.
I also wrote another very small reviewer's patch that you can fold in.
I don't see it on the queue; did you push?
Thanks!
Nicolas
comment:18 in reply to: ↑ 17 Changed 8 years ago by
Replying to nthiery:
Replying to aschilling:
You are welcome. I hope you will return the favor for trac_12536-linear_extensions-as.patch!
I sure will, soon!
Thanks.
Crystals are only implemented in sage.combinat.crystals (so far). But this names an area of mathematics. So this fits a bit more the first case.
No, there is a lot of crystal code in /sage/categories: crystals, finite_crystals, highest_weight_crystals, ....
I meant: the crystals themselves (CrystalOfLetter?, KR, ...) are all in implemented in sage.combinat.crystals.
But these are not categories, they are classes. In your case, a cateogory is in /sage/combinat/root_systems/
Why can't fundamental_weights when "extended" is set also include
delta
? This would at least fit with the notational abuse of fundamental_weight.Because we want to do things like:
sage: x in self.fundamental_weights()
sage: all(L.some_property() for L in self.fundamental_weights())
So adding delta would change the semantic of fundamental_weights. Whereas the current abuse of fundamental_weight can't break any code.
How about self.fundamental_weights(extended = True) with default extended = False?
I also wrote another very small reviewer's patch that you can fold in.
I don't see it on the queue; did you push?
Sorry, I forgot to push. It should be there now.
Best,
Anne
comment:19 Changed 8 years ago by
- Description modified (diff)
comment:20 Changed 8 years ago by
- Description modified (diff)
- Summary changed from Categories for root systems to Categories for root systems and many misc improvements
The updated patch adds many missing doctests, and improves coxeter diagrams. It's probably close to completion, up to fixing some potentially failing doctests.