sagemath / sage

Main repository of SageMath
https://www.sagemath.org
Other
1.31k stars 451 forks source link

Refactor Coxeter groups as matrix groups and non crystallographic root systems #15703

Open nthiery opened 10 years ago

nthiery commented 10 years ago

This is a follow up to #9290.

Tests:

  sage: C = CoxeterDiagram(...)           # good name? or CartanDatum(coxeter_matrix=...) [1] ? or?
  sage: L = RootSystem(C).root_space()
  sage: W = L.reflection_group()
  sage: W = CoxeterGroup(['H',3])
  sage: W.domain()

Sage Days 57 in Cernay will be a good occasion to work on this.

Follow ups: #16087

[1]: Generally speaking, it's planned to rename CartanType to CartanDatum.

Depends on #16120 Depends on #16126 Depends on #16130 Depends on #17798 Depends on #18152

CC: @sagetrac-sage-combinat @tscrim @jplab @sagetrac-vripoll @mathzeta

Component: combinatorics

Keywords: coxeter groups, days57

Author: Jean-Philippe Labbé, Vivien Ripoll

Branch/Commit: u/jipilab/refactor_coxeter_groups_as_matrix_groups_and_non_crystallographic_root_systems @ 09a1ff9

Reviewer: Nicolas M. Thiéry

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

fchapoton commented 10 years ago

Changed keywords from none to coxeter

nthiery commented 10 years ago

Description changed:

--- 
+++ 
@@ -11,4 +11,4 @@

 As a prerequisite, implement root spaces and weight spaces for non-crystallographic Coxeter groups.

-Sage Days 47 in Cernay will be a good occasion to work on this.
+Sage Days 57 in Cernay will be a good occasion to work on this.
nthiery commented 10 years ago

Changed keywords from coxeter to coxeter groups, days57

nthiery commented 10 years ago

Description changed:

--- 
+++ 
@@ -1,14 +1,42 @@
 This is a follow up to: #9290.

-Refactor CoxeterMatrixGroup and WeylGroup to make the later a subclass of the former, and lift as many features as possible from WeylGroup to CoxeterMatrixGroup. This includes:
-- Building the matrices from a root lattice realization
-- Implementing the following methods:
+- Create a class CoxeterDiagram (similar to DynkinDiagram)
+  Edge labels: m_{i,j}, possibly with number <-1 for oo

-  ```
+  Starter: just use a plain digraph.
+
+- Implement the method dynkin_diagram() which builds the cartan matrix
+  for the geometric representation
+
+  Starter: just make this a function
+
+- Feed this to RootSystem, and check that the root space and weight
+  space are built properly. Rename the weyl_group method to
+  reflection_group, with an alias from weyl_group.
+
+- Long run: stuff specific to the crystallographic case, starting with
+  this weyl_group method, should go in
+  RootLatticeRealizations.Crystallographic. That's for a follow up
+  ticket on using axioms for root systems; but let's not depend on
+  #10963 right now.
+
+- Refactor CoxeterMatrixGroup and WeylGroup to make the later a
+  subclass of the former, and lift as many features as possible from
+  WeylGroup to CoxeterMatrixGroup.
+
+Tests:
+
+```
+  sage: C = CoxeterDiagram(...)           # good name? or CartanDatum(coxeter_matrix=...) [1] ? or?
+  sage: L = RootSystem(C).root_space()
+  sage: W = L.reflection_group()
   sage: W = CoxeterGroup(['H',3])
   sage: W.domain()
-  ```
-
-As a prerequisite, implement root spaces and weight spaces for non-crystallographic Coxeter groups.
+```

 Sage Days 57 in Cernay will be a good occasion to work on this.
+
+Follow ups: #16087
+
+[1]: Generally speaking, it's planned to rename CartanType to CartanDatum.
+
jplab commented 10 years ago

Description changed:

--- 
+++ 
@@ -1,28 +1,18 @@
 This is a follow up to: #9290.

-- Create a class CoxeterDiagram (similar to DynkinDiagram)
-  Edge labels: m_{i,j}, possibly with number <-1 for oo
+* Create a class CoxeterGraph (similar to DynkinDiagram) Edge labels: m_{i,j}, possibly with number <-1 for oo

-  Starter: just use a plain digraph.
+  Starter: a edge-labeled graph.

-- Implement the method dynkin_diagram() which builds the cartan matrix
-  for the geometric representation
+* Implement the method dynkin_diagram() which builds the cartan matrix for the geometric representation

   Starter: just make this a function

-- Feed this to RootSystem, and check that the root space and weight
-  space are built properly. Rename the weyl_group method to
-  reflection_group, with an alias from weyl_group.
+* Feed this to RootSystem, and check that the root space and weight space are built properly. Rename the weyl_group method to reflection_group, with an alias from weyl_group.

-- Long run: stuff specific to the crystallographic case, starting with
-  this weyl_group method, should go in
-  RootLatticeRealizations.Crystallographic. That's for a follow up
-  ticket on using axioms for root systems; but let's not depend on
-  #10963 right now.
+* Long run: stuff specific to the crystallographic case, starting with this weyl_group method, should go in RootLatticeRealizations.Crystallographic. That's for a follow up ticket on using axioms for root systems; but let's not depend on #10963 right now.

-- Refactor CoxeterMatrixGroup and WeylGroup to make the later a
-  subclass of the former, and lift as many features as possible from
-  WeylGroup to CoxeterMatrixGroup.
+* Refactor CoxeterMatrixGroup and WeylGroup to make the latter a subclass of the former, and lift as many features as possible from WeylGroup to CoxeterMatrixGroup.

 Tests:

@@ -33,10 +23,8 @@
   sage: W = CoxeterGroup(['H',3])
   sage: W.domain()

- Sage Days 57 in Cernay will be a good occasion to work on this.

Follow ups: #16087

[1]: Generally speaking, it's planned to rename CartanType to CartanDatum.

nthiery commented 10 years ago

Description changed:

--- 
+++ 
@@ -1,18 +1,101 @@
-This is a follow up to: #9290.
+This is a follow up to #9290.

-* Create a class CoxeterGraph (similar to DynkinDiagram) Edge labels: m_{i,j}, possibly with number <-1 for oo
+* Experiment with the infrastructure scales and benchmark

-  Starter: a edge-labeled graph.
+  - Build by hand an interesting dynkin diagram.
+  - Shoot straight at producing a nice plot with a bunch of limit roots.
+  - Post the picture here.
+  - Benchmark the calculation.
+  - Every hack along the way is fair.
+  - Update the TODO list below with what would need to be done for a
+    proper implementation.
+  - Discard the experiment.

-* Implement the method dynkin_diagram() which builds the cartan matrix for the geometric representation
+* CoxegerGraph

-  Starter: just make this a function
+  - Create a class similar to DynkinDiagram
+    Starter: an edge-labeled graph.
+  - Edge labels: m_{i,j}, possibly with number <-1 for oo
+  - method dynkin_diagram() which builds the cartan matrix for the geometric representation
+    Starter: just make this a function

-* Feed this to RootSystem, and check that the root space and weight space are built properly. Rename the weyl_group method to reflection_group, with an alias from weyl_group.
+* Update DynkinDiagram to support non crystallographic case:

-* Long run: stuff specific to the crystallographic case, starting with this weyl_group method, should go in RootLatticeRealizations.Crystallographic. That's for a follow up ticket on using axioms for root systems; but let's not depend on #10963 right now.
+  - Add an argument base_ring to the constructor
+  - Add a method base_ring
+  - Make add_edge honor this method when automatically adding edges
+  - Update cartan_matrix() to use the base_ring
+  - Add a method _test_base_ring that checks that all edge labels are
+    indeed in this base ring
+  - Implement is_crystallographic testing if the base ring is ZZ
+  - Add an argument symmetric=False to the constructor, and make
+    add_edge and symmetrizer use it.
+  - Add a method _test_dynkin_diagram that tests that the Dynkin
+    diagram indeed defines a proper root system. See in particular
+    cartan_matrix.is_generalized_cartan_matrix.

-* Refactor CoxeterMatrixGroup and WeylGroup to make the latter a subclass of the former, and lift as many features as possible from WeylGroup to CoxeterMatrixGroup.
+  * Update CartanMatrix
+  - Add a base ring argument to the constructor
+  - Update is_crystallographic
+  - Decide on the semantic of crystallographic (symmetrizable or
+    not?), and if possibly add an is_... method to decide whether the
+    entries are integral or not.
+  - Update is_affine
+  - Update is_finite
+  - Update is_generalized_cartan_matrix
+
+* CartanType
+  - Possibly update to accept appropriate data to build a
+    CoxeterDiagram
+
+* RootSystem
+
+  - Decide on the meaning of root_lattice: either disable it in the
+    non integral case, or have it be the span of the roots over the
+    smallest available ring.
+
+* RootLatticeRealizations:
+
+  - Feed this to RootSystem, and check that the root space and weight
+    space are built properly.
+  - Rename the weyl_group method to reflection_group, with an alias
+    from weyl_group; update the setting of the category.
+  - Long run: stuff specific to the crystallographic case, starting
+    with this weyl_group method, should go in
+    RootLatticeRealizations.Crystallographic. That's for a follow up
+    ticket on using axioms for root systems; but let's not depend on
+    #10963 right now.
+
+* RootSpace (for this ticket or some follow up):
+
+  - Define the inner product
+  - Signature of the bilinear form
+
+* CoxeterMatrixGroup and WeylGroup:
+
+  - Refactor WeylGroup to make it a subclass of CoxeterMatrixGroup,
+    and lift as many features as possible from WeylGroup to
+    CoxeterMatrixGroup.
+  - Check that, with a proper Dynkin diagram, the conversion to GAP
+    issue does not appear
+  - Now or later: we probably want the Weyl group elements to be
+    represented by Sage matrices, but keep a handle to the
+    corresponding Gap group. Currently one has to make a choice
+    between MatrixGroup_generic and MatrixGroup_gap.
+
+* Update WeylGroups:
+
+  - inversions: use the "root_lattice" by default?
+
+* Cartan types
+
+  - provide a dynkin_diagram method that builds the Dynkin diagram
+    from the Coxeter diagram when available?
+  - Test: H_3 and friends should have a working dynkin_diagram method
+
+* Prerequisites:
+
+  - Add a `_float_` method to UCF

 Tests:

@@ -28,3 +111,4 @@
 Follow ups: #16087

 [1]: Generally speaking, it's planned to rename CartanType to CartanDatum.
+
nthiery commented 10 years ago

Author: Jean-Philippe Labbé, Vivien Ripoll

nthiery commented 10 years ago

Description changed:

--- 
+++ 
@@ -1,7 +1,6 @@
 This is a follow up to #9290.

 * Experiment with the infrastructure scales and benchmark
-
   - Build by hand an interesting dynkin diagram.
   - Shoot straight at producing a nice plot with a bunch of limit roots.
   - Post the picture here.
@@ -12,7 +11,6 @@
   - Discard the experiment.

 * CoxegerGraph
-
   - Create a class similar to DynkinDiagram
     Starter: an edge-labeled graph.
   - Edge labels: m_{i,j}, possibly with number <-1 for oo
@@ -20,7 +18,6 @@
     Starter: just make this a function

 * Update DynkinDiagram to support non crystallographic case:
-
   - Add an argument base_ring to the constructor
   - Add a method base_ring
   - Make add_edge honor this method when automatically adding edges
@@ -37,25 +34,26 @@
   * Update CartanMatrix
   - Add a base ring argument to the constructor
   - Update is_crystallographic
-  - Decide on the semantic of crystallographic (symmetrizable or
-    not?), and if possibly add an is_... method to decide whether the
-    entries are integral or not.
   - Update is_affine
   - Update is_finite
   - Update is_generalized_cartan_matrix

 * CartanType
-  - Possibly update to accept appropriate data to build a
-    CoxeterDiagram
+  - Possibly update to accept appropriate data to build a CoxeterDiagram (e.g. a matrix)
+  - Add a base_ring method?
+  - Decide on the semantic of is_crystallographic (symmetrizable or
+    not?), and if possibly add an is_... method to decide whether the
+    entries are integral or not.
+  - Provide a dynkin_diagram method that builds the Dynkin diagram
+    from the Coxeter diagram when available
+  - Test: H_3 and friends should have a working dynkin_diagram method

 * RootSystem
-
   - Decide on the meaning of root_lattice: either disable it in the
     non integral case, or have it be the span of the roots over the
     smallest available ring.

 * RootLatticeRealizations:
-
   - Feed this to RootSystem, and check that the root space and weight
     space are built properly.
   - Rename the weyl_group method to reflection_group, with an alias
@@ -67,12 +65,10 @@
     #10963 right now.

 * RootSpace (for this ticket or some follow up):
-
   - Define the inner product
   - Signature of the bilinear form

 * CoxeterMatrixGroup and WeylGroup:
-
   - Refactor WeylGroup to make it a subclass of CoxeterMatrixGroup,
     and lift as many features as possible from WeylGroup to
     CoxeterMatrixGroup.
@@ -84,17 +80,9 @@
     between MatrixGroup_generic and MatrixGroup_gap.

 * Update WeylGroups:
-
   - inversions: use the "root_lattice" by default?

-* Cartan types
-
-  - provide a dynkin_diagram method that builds the Dynkin diagram
-    from the Coxeter diagram when available?
-  - Test: H_3 and friends should have a working dynkin_diagram method
-
 * Prerequisites:
-
   - Add a `_float_` method to UCF

 Tests:
nthiery commented 10 years ago

Reviewer: Nicolas M. Thiéry

tscrim commented 10 years ago
comment:11

I believe I'm taking care of the inner product on the root space in #15384 (which I called symmetric_form()). Also for a followup ticket, we should implement/refactor things for symmetrizable and the non-symmetrizable types (for when we get the hyperbolic types done).

jplab commented 10 years ago
comment:12

Very good!

Just a small suggestion: I would call the function "bilinear_form". Although it is true that we deal with symmetric forms so far...

jplab commented 10 years ago

Attachment: benchmark.png

jplab commented 10 years ago

Description changed:

--- 
+++ 
@@ -1,7 +1,9 @@
 This is a follow up to #9290.

-* Experiment with the infrastructure scales and benchmark
-  - Build by hand an interesting dynkin diagram.
+* Experiment with the infrastructure scales and benchmark 
+
+  Here is a goal picture (benchmark.png) given by the Coxeter matrix [[1,oo,2,5],[oo,1,6,2],[2,6,1,-1.1],[5,2,-1.1,1]]. It represents the limit roots of the elements of infinite order of length 3 and 4, and their orbits under the actions of elements of length smaller or equal to 5. There are 12212 drawn limits. (Not showing 66 limit roots that created approximation errors coming from a "to be looked at" usage of solve in my code). With a homemade implementation, it took 42 seconds to do the computations of everything from scratch and also the computation of the tetrahedron and the light cone.
+
   - Shoot straight at producing a nice plot with a bunch of limit roots.
   - Post the picture here.
   - Benchmark the calculation.
@@ -83,7 +85,7 @@
   - inversions: use the "root_lattice" by default?

 * Prerequisites:
-  - Add a `_float_` method to UCF
+  - Add a `__float__` method to UCF, see #16120

 Tests:
jplab commented 10 years ago

Dependencies: 16120

jplab commented 10 years ago

Changed dependencies from 16120 to #16120

ccca2971-5672-4685-956c-1deb9dcd67bf commented 10 years ago

Branch: u/vripoll/refactor_coxeter_groups_as_matrix_groups_and_non_crystallographic_root_systems

jplab commented 10 years ago

Changed dependencies from #16120 to #16120, #16126

jplab commented 10 years ago

Description changed:

--- 
+++ 
@@ -12,7 +12,7 @@
     proper implementation.
   - Discard the experiment.

-* CoxegerGraph
+* CoxegerGraph, see #16126
   - Create a class similar to DynkinDiagram
     Starter: an edge-labeled graph.
   - Edge labels: m_{i,j}, possibly with number <-1 for oo
jplab commented 10 years ago

New commits:

a2fdd20First draft with some hacks to make root systems visualization work
d025f0fAdded a `__float__` method to the class Universal Cyclotomic Field
2846f67Merge branch 'ticket16120' into t/15703/refactor_coxeter_groups_as_matrix_groups_and_non_crystallographic_root_systems
jplab commented 10 years ago

Commit: 2846f67

jplab commented 10 years ago

Changed dependencies from #16120, #16126 to #16120, #16126, #16130

jplab commented 10 years ago

Description changed:

--- 
+++ 
@@ -4,13 +4,7 @@

   Here is a goal picture (benchmark.png) given by the Coxeter matrix [[1,oo,2,5],[oo,1,6,2],[2,6,1,-1.1],[5,2,-1.1,1]]. It represents the limit roots of the elements of infinite order of length 3 and 4, and their orbits under the actions of elements of length smaller or equal to 5. There are 12212 drawn limits. (Not showing 66 limit roots that created approximation errors coming from a "to be looked at" usage of solve in my code). With a homemade implementation, it took 42 seconds to do the computations of everything from scratch and also the computation of the tetrahedron and the light cone.

-  - Shoot straight at producing a nice plot with a bunch of limit roots.
-  - Post the picture here.
-  - Benchmark the calculation.
-  - Every hack along the way is fair.
-  - Update the TODO list below with what would need to be done for a
-    proper implementation.
-  - Discard the experiment.
+  The picture named benchmark2.png shows an image produced with sage with hacks and tweaks. It took around 10 minutes to compute. There are 2347 roots shown. (There was a problem in the production of the roots located at (0,0,0)) These roots is formed as the union of the inversion sets of the elements of length at most 8 obtained via the weak order poset.

 * CoxegerGraph, see #16126
   - Create a class similar to DynkinDiagram
jplab commented 10 years ago

Attachment: benchmark2.png

jplab commented 10 years ago

Description changed:

--- 
+++ 
@@ -26,6 +26,7 @@
   - Add a method _test_dynkin_diagram that tests that the Dynkin
     diagram indeed defines a proper root system. See in particular
     cartan_matrix.is_generalized_cartan_matrix.
+  - adapt column() and row() method to give the labels in the base ring

   * Update CartanMatrix
   - Add a base ring argument to the constructor
@@ -54,6 +55,7 @@
     space are built properly.
   - Rename the weyl_group method to reflection_group, with an alias
     from weyl_group; update the setting of the category.
+  - Define a new projection "transversal" to visualise root systems (and find a right name for it)
   - Long run: stuff specific to the crystallographic case, starting
     with this weyl_group method, should go in
     RootLatticeRealizations.Crystallographic. That's for a follow up
@@ -62,6 +64,7 @@

 * RootSpace (for this ticket or some follow up):
   - Define the inner product
+  - adapt the is_positive_root to make it work for any base ring
   - Signature of the bilinear form

 * CoxeterMatrixGroup and WeylGroup:
@@ -74,6 +77,9 @@
     represented by Sage matrices, but keep a handle to the
     corresponding Gap group. Currently one has to make a choice
     between MatrixGroup_generic and MatrixGroup_gap.
+
+* Plotting:
+  - add a family_of_points method in the projections to be used by the "transversal projection"

 * Update WeylGroups:
   - inversions: use the "root_lattice" by default?
jplab commented 10 years ago

Changed branch from u/vripoll/refactor_coxeter_groups_as_matrix_groups_and_non_crystallographic_root_systems to u/jipilab/refactor_coxeter_groups_as_matrix_groups_and_non_crystallographic_root_systems

jplab commented 10 years ago

Changed commit from 2846f67 to 09a1ff9

jplab commented 10 years ago
comment:21

I adapted the TODO list in relation with the latest changes I just pushed. The script joined allows you to create the pictures and do some tests...

Now we have to work!!


New commits:

09a1ff9First dirty version to get a TODO list for the ticket 15703
856887fc-c4a0-4392-a207-e1239ccef741 commented 10 years ago
comment:22

Attachment: test_rootsystems.sage.gz

jplab commented 9 years ago

Description changed:

--- 
+++ 
@@ -1,10 +1,6 @@
 This is a follow up to #9290.

 * Experiment with the infrastructure scales and benchmark 
-
-  Here is a goal picture (benchmark.png) given by the Coxeter matrix [[1,oo,2,5],[oo,1,6,2],[2,6,1,-1.1],[5,2,-1.1,1]]. It represents the limit roots of the elements of infinite order of length 3 and 4, and their orbits under the actions of elements of length smaller or equal to 5. There are 12212 drawn limits. (Not showing 66 limit roots that created approximation errors coming from a "to be looked at" usage of solve in my code). With a homemade implementation, it took 42 seconds to do the computations of everything from scratch and also the computation of the tetrahedron and the light cone.
-
-  The picture named benchmark2.png shows an image produced with sage with hacks and tweaks. It took around 10 minutes to compute. There are 2347 roots shown. (There was a problem in the production of the roots located at (0,0,0)) These roots is formed as the union of the inversion sets of the elements of length at most 8 obtained via the weak order poset.

 * CoxegerGraph, see #16126
   - Create a class similar to DynkinDiagram
ccca2971-5672-4685-956c-1deb9dcd67bf commented 9 years ago

Description changed:

--- 
+++ 
@@ -2,7 +2,7 @@

 * Experiment with the infrastructure scales and benchmark 

-* CoxegerGraph, see #16126
+* CoxeterGraph, see #16126
   - Create a class similar to DynkinDiagram
     Starter: an edge-labeled graph.
   - Edge labels: m_{i,j}, possibly with number <-1 for oo
@@ -32,7 +32,7 @@
   - Update is_generalized_cartan_matrix

 * CartanType
-  - Possibly update to accept appropriate data to build a CoxeterDiagram (e.g. a matrix)
+  - Possibly update to accept appropriate data to build a CoxeterGraph (e.g. a matrix)
   - Add a base_ring method?
   - Decide on the semantic of is_crystallographic (symmetrizable or
     not?), and if possibly add an is_... method to decide whether the
@@ -80,8 +80,6 @@
 * Update WeylGroups:
   - inversions: use the "root_lattice" by default?

-* Prerequisites:
-  - Add a `__float__` method to UCF, see #16120

 Tests:
jplab commented 9 years ago

Description changed:

--- 
+++ 
@@ -24,7 +24,7 @@
     cartan_matrix.is_generalized_cartan_matrix.
   - adapt column() and row() method to give the labels in the base ring

-  * Update CartanMatrix
+  * Update CartanMatrix, see #17798
   - Add a base ring argument to the constructor
   - Update is_crystallographic
   - Update is_affine
jplab commented 9 years ago

Changed dependencies from #16120, #16126, #16130 to #16120, #16126, #16130, #17798, #18152