Opened 11 years ago

# Categories for root systems and many misc improvements — at Version 20

Reported by: Owned by: nthiery mhansen major sage-5.0 combinatorics root systems, categories sage-combinat, mshimo@… Nicolas M. Thiéry Anne Schilling, Mark Shimozono, PatchBot N/A #10817

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)


### comment:1 Changed 8 years ago by nthiery

• Authors set to Nicolas M. Thiéry
• Dependencies set to #10963, #10817
• Description modified (diff)
• Report Upstream set to N/A

### comment:2 Changed 8 years ago by nthiery

• Description modified (diff)
• Summary changed from Root systems: categorification to Categories for root systems

### comment:3 Changed 8 years ago by nthiery

• Description modified (diff)

### comment:4 follow-up: ↓ 6 Changed 8 years ago by nthiery

• Status changed from new to needs_review

The updated patch adds many missing doctests, and improves coxeter diagrams. It's probably close to completion, up to fixing some potentially failing doctests.

### comment:5 Changed 8 years ago by nthiery

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 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:

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_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 nthiery

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 nthiery

• 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 nthiery

Upon popular demand, extended weight lattice/spaces are now implemented.

### comment:10 follow-up: ↓ 11 Changed 8 years ago by aschilling

• 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 of w^{-1}. """ return (~self).has_right_descent(i)

Should has_left_descent also be an abstract_method? Or is that implicit through has_right_descent?

/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 nthiery

Thanks much Anne for your detailed review!

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

/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 nthiery

/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-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 davidloeffler

• 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 nthiery

• Status changed from needs_work to needs_review

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 nthiery

• Description modified (diff)

### comment:16 in reply to: ↑ 12 ; follow-up: ↓ 17 Changed 8 years ago by aschilling

Thanks much Anne for your detailed review!

You are welcome. I hope you will return the favor for trac_12536-linear_extensions-as.patch!

/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-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 nthiery

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

### Changed 8 years ago by nthiery

This contains the user-readable diff. Do not apply!

### comment:19 Changed 8 years ago by nthiery

• Description modified (diff)

### comment:20 Changed 8 years ago by nthiery

• Description modified (diff)
• Summary changed from Categories for root systems to Categories for root systems and many misc improvements
Note: See TracTickets for help on using tickets.