Root systems improvements

[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

CC: @sagetrac-sage-combinat

Component: combinatorics

Keywords: root systems

Author: Nicolas M. Thiéry, Anne Schilling, Daniel Bump, Nicolas Borie, Qiang Wang, Steve Pon

Reviewer: Daniel Bump, Mike Hansen

Merged: sage-4.3.alpha0

Issue created by migration from https://trac.sagemath.org/ticket/4326

[anneschilling]

Description changed:

--- 
+++ 
@@ -13,6 +13,8 @@
 
 Generic:
 - (signed) reduced word for a chamber/alcove
+- fix rank(): for the affine cases it currently returns the same
+  as n.
 
 Classical case:
 - reverse map to coroot space and coroot lattice by scalar product with the fundamental weights

[nthiery]

Description changed:

--- 
+++ 
@@ -1,3 +1,5 @@
+Current patch: http://combinat.sagemath.org/patches/file/tip/root_systems-4326-nt.patch
+
 Doc:
 - Use $F_4$ instead of F4 
 

[nthiery]

Attachment: root_systems-4326-nt.patch.gz

[nthiery]

Changed keywords from none to root systems

[nthiery]

Description changed:

--- 
+++ 
@@ -1,7 +1,45 @@
-Current patch: http://combinat.sagemath.org/patches/file/tip/root_systems-4326-nt.patch
+Patch from Sage-Combinat: http://combinat.sagemath.org/patches/file/tip/root_systems-4326-nt.patch
 
-Doc:
-- Use $F_4$ instead of F4 
+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,:]
@@ -13,17 +51,14 @@
 WeightLatticeRealization
 - scalar product with coweight lattice in finite dimension
 
-Generic:
-- (signed) reduced word for a chamber/alcove
-- fix rank(): for the affine cases it currently returns the same
-  as n.
-
 Classical case:
 - reverse map to coroot space and coroot lattice by scalar product with the fundamental weights
-- => associated coroot
+- associated coroot in the root and weight space
 - s_\alpha on the (co)root and (co)weight lattice for any root \alpha
 
 Affine case:
-- analogues whenever well defined 
-- reduced words for translations elements.
+- affine ambient space
 
+Categorification of RootLatticeRealization / ...
+New category CoxeterGroupModules
+Support for non crystalographic root systems

[nthiery]

Reviewer: bump

[nthiery]

Author: nthiery with help from schilling, bump, Nicolas Borie, Qiang Wang, Steve Pon

[nthiery]

Description changed:

--- 
+++ 
@@ -1,4 +1,8 @@
-Patch from Sage-Combinat: http://combinat.sagemath.org/patches/file/tip/root_systems-4326-nt.patch
+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

[dwbump]

comment:7

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.