Opened 9 years ago

Closed 8 years ago

Last modified 8 years ago

#4326 closed enhancement (fixed)

Root systems improvements

Reported by: nthiery Owned by: nthiery
Priority: major Milestone: sage-4.3
Component: combinatorics Keywords: root systems
Cc: sage-combinat Merged in: sage-4.3.alpha0
Authors: Nicolas M. Thiéry, Anne Schilling, Daniel Bump, Nicolas Borie, Qiang Wang, Steve Pon Reviewers: Daniel Bump, Mike Hansen
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by nthiery)

Patch taken from Sage-Combinat: http://combinat.sagemath.org/patches/file/tip/root_systems-4326-nt.patch

Depends on: #6136 #6253 #6250 #5891


Documention:

  • quickref + links in sage.combinat.root_system
  • Long introduction in CartanTypes?
  • ...

Cartan Types:

  • Object oriented clean up: each cartan type has its own class (in .type_....py) which contains all its specific data (dynkin diagram, ascii art, ...). All the dispatch logic is now concentrated in the CartanType? factory.
  • fixed the definition of rank for affine types (Anne Schilling)
  • systematic implementation of the classical type underlying an affine type (Anne Schilling)
  • New methods: is_untwisted_affine, special_node, a, acheck, translation_factors, symmetrizer, row_annihilator col_annihilator (partly Nicolas Borie)
  • Relabelled Cartan types (with composition, classical, special_node, dual)
  • Use A~... B~* BC~ convention for affine types; Kac' convention implemented by renaming them (see CartanType??)
  • F3 is nonexistent so use F4 in one test (Dan Bump)
  • ascii art for reducible (Dan Bump), relabelled, and dual Cartan types

Root systems:

  • Preliminary plots (Nicolas Borie)
  • New methods for affine root systems (mostly Nicolas Borie): null_(co)root, level
  • RootSystem?(["A",3,1]) returns None rather than the ambient space for type A_3 (which was wrong!)
  • positive and negative roots for all (finite) root lattice realizations

Coxeter groups:

  • New categories: (Finite) CoxeterGroups?, (Finite, Affine) WeylGroups? standardized methods: first_descent, has_descent, descents, reduced_word, length, from_reduced_word, with systematic associated test (test_has_descent, ...) simple_reflections, simple_projections, coset_representatives, binary_factorisations, ... (many of them were extracted and generalized from WeylGroup?)
  • lower and upper cover for Bruhat order (Steve Pon)
  • affine stanley symmetric functions for types A, A affine
  • Documentation (with help from Qiang Wang, Nicolas Borie)

The following are not yet addressed, and will be bumped to a subsequent patch:

DynkinDiagram?:

  • allow for slicing notation for column/row extraction: c[i,:]

AmbientSpace?:

  • fundamental coweights by appropriate scaling of the fundamental weights
  • embedding coweight lattice

WeightLatticeRealization?

  • scalar product with coweight lattice in finite dimension

Classical case:

  • reverse map to coroot space and coroot lattice by scalar product with the fundamental weights
  • associated coroot in the root and weight space
  • s_\alpha on the (co)root and (co)weight lattice for any root \alpha
  • highest_coroot returning self.coroot_lattice().highest_root()

Affine case:

  • affine ambient space
  • Fix:
      sage: R = RootSystem(["A",2,1]).weight_lattice()
      sage: R.rho_classical()
      ...
      TypeError: unsupported operand parent(s) for '*': 'Rational Field' and 'Weight lattice of the Root system of type ['A', 2, 1]'
    

Categorification of RootLatticeRealization? / ... New category CoxeterGroupModules? Support for non crystalographic root systems

Attachments (3)

root_systems-4326-nt.patch (407.8 KB) - added by nthiery 8 years ago.
trac_4326-root_systems-nt.patch (386.9 KB) - added by nthiery 8 years ago.
Latest version of the patch from the Sage-Combinat patch server (no change since Dan's review)
trac_4326-root_systems-fix-nt.patch (9.3 KB) - added by nthiery 8 years ago.
Fix ClassicalWeylSubgroup? and remove unneeded long time, as spotted by Mike

Download all attachments as: .zip

Change History (22)

comment:1 Changed 9 years ago by nthiery

  • Cc sage-combinat added

comment:2 Changed 9 years ago by aschilling

  • Description modified (diff)

comment:3 Changed 8 years ago by nthiery

  • Status changed from new to assigned

comment:4 Changed 8 years ago by nthiery

  • Description modified (diff)

Changed 8 years ago by nthiery

comment:5 Changed 8 years ago by nthiery

  • Authors set to nthiery with help from schilling, bump, Nicolas Borie, Qiang Wang, Steve Pon
  • Description modified (diff)
  • Keywords root systems added
  • Reviewers set to bump
  • Summary changed from Root systems improvements to [with patch, needs review] Root systems improvements

comment:6 Changed 8 years ago by nthiery

  • Description modified (diff)

comment:7 Changed 8 years ago by bump

  • Summary changed from [with patch, needs review] Root systems improvements to [with patch, positive review] Root systems improvements

Normally I would have waited for the category patches to be merged before reviewing this patch. However I recieved an email from Tom Boothby urging me to do the review now, so here it is.

This review is based on the version of the patches in the combinat queue. This is because it depends on patches that have not been merged yet.

After qpushing the combinat queue up to this patch but not beyond, all tests pass. This is with Sage 4.1 and the last changeset is this one:

changeset:   1520:188022ff52b9
tag:         tip
user:        Nicolas M. Thiery <nthiery@users.sf.net>
date:        Tue Jul 21 01:13:42 2009 +0200
summary:     Update

The patch adds quite a bit of new functionality for working with Coxeter groups and affine Weyl groups. The following new files are added. There are new categories added for CoxeterGroups? and WeylGroups?. There is an extensive ChangeLog? in the comments at the beginning of the patch.

Since the patch is over 11,000 lines of code, there could very well be bugs in it. However it probably does not introduce significant new bugs in the portion of the code that deals with classical root systems, since I used it extensively during the spring of 2009 in connection with #5794. Every classical Cartan type and many reducible types have been created and worked with. What problems I found then were fixed. Moreover the portion of the code that deals with affine root systems was similarly very tested by Anne Schilling in connection with affine crystals.

Therefore the most uncertainty in my is with the new functionality for Coxeter groups. I will mention one "wish" in this direction, which is that in addition to implementing the Bruhat covers, the Bruhat order be properly implemented. This could be done efficiently using Proposition 1.1 in Stembridge, A Short Derivation of the Möbius Function for the Bruhat Order, Journal of Algebraic Combinatorics 25, (2007).

This wish is not a reason to hold up merging the patch. Rather the patch should be merged as soon as possible and such changes can be made later.

comment:8 follow-up: Changed 8 years ago by mvngu

Let me get this straight. Tickets #6136, #6253, #6250, and #5891 must first be merged before merging this ticket?

comment:9 in reply to: ↑ 8 ; follow-up: Changed 8 years ago by nthiery

Replying to mvngu:

Let me get this straight. Tickets #6136, #6253, #6250, and #5891 must first be merged before merging this ticket?

Indeed. Should we use a specific subject for patches that have a positive review, but have dependencies on not yet merged tickets? Something like:

[with patch, positive review, depends on #6136, #6253, #6250, #5891] ...

comment:10 in reply to: ↑ 9 Changed 8 years ago by mvngu

Replying to nthiery:

Indeed. Should we use a specific subject for patches that have a positive review, but have dependencies on not yet merged tickets? Something like:

[with patch, positive review, depends on #6136, #6253, #6250, #5891] ...

No, not really. I just want to double check since the patch is rather huge and I was concerned about it getting bit rotten. Anyway, people who uses the merge script would not be able to easily tell whether a positive-reviewed ticket has other dependencies.

Changed 8 years ago by nthiery

Latest version of the patch from the Sage-Combinat patch server (no change since Dan's review)

comment:11 Changed 8 years ago by nthiery

  • Description modified (diff)

comment:12 Changed 8 years ago by nthiery

  • Description modified (diff)

Changed 8 years ago by nthiery

Fix ClassicalWeylSubgroup? and remove unneeded long time, as spotted by Mike

comment:13 Changed 8 years ago by nthiery

  • Status changed from positive_review to needs_work

comment:14 Changed 8 years ago by nthiery

  • Authors changed from nthiery with help from schilling, bump, Nicolas Borie, Qiang Wang, Steve Pon to Nicolas M. Thiéry, with help from Anne Schilling, Daniel Bump, Nicolas Borie, Qiang Wang, Steve Pon
  • Reviewers changed from bump to Daniel Bump
  • Status changed from needs_work to needs_review

comment:15 Changed 8 years ago by mhansen

  • Reviewers changed from Daniel Bump to Daniel Bump, Mike Hansen
  • Status changed from needs_review to positive_review

The new patch looks okay to me.

comment:16 Changed 8 years ago by mhansen

  • Merged in set to sage-4.3.alpha0
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:17 Changed 8 years ago by mvngu

  • Milestone changed from sage-combinat to sage-4.3

comment:18 Changed 8 years ago by mvngu

  • Report Upstream set to N/A
  • Summary changed from [with patch, positive review] Root systems improvements to Root systems improvements

comment:19 Changed 8 years ago by mvngu

  • Authors changed from Nicolas M. Thiéry, with help from Anne Schilling, Daniel Bump, Nicolas Borie, Qiang Wang, Steve Pon to Nicolas M. Thiéry, Anne Schilling, Daniel Bump, Nicolas Borie, Qiang Wang, Steve Pon
Note: See TracTickets for help on using tickets.