Changing brick polytopes of subword complexes to brick polyhedra

[DennisJahn]

generalize the method brick_polytope() of sage.combinat.subword_complex.py to brick_polyhedron() as done in

https://arxiv.org/abs/2103.03715

Depends on #32669

CC: @stumpc5 @jplab @kliem

Component: combinatorics

Keywords: subword complex, brick vector, brick polyhedron, brick polytope

Author: Dennis Jahn

Branch/Commit: u/gh-DennisJahn/changing_brick_polytopes_of_subword_complexes_to_brick_polyhedra @ b3abcc9

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

[DennisJahn]

Branch: u/gh-DennisJahn/changing_brick_polytopes_of_subword_complexes_to_brick_polyhedra

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

f3b834e

re-added brick_polytope() as deprecated method. Examples for brick_polehedron() fixed

[sagetrac-git]

Commit: f3b834e

[sagetrac-git]

Changed commit from f3b834e to e658d9b

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

e658d9b

Replaced brick polytope by brick polyhedron in documentaion. Methods to be changed/rewritten: kappa_preimage() of facets, is_vertex() of facets, brick_fan of subword complex, minkowski_summand of subword complex.

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

996a180

method is_vertex() for facets rewritten

[sagetrac-git]

Changed commit from e658d9b to 996a180

[sagetrac-git]

Changed commit from 996a180 to f625039

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

f625039

Doc for minkowski_summand() of subword complex and kappa_preimage() of facets

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

24ae7de

rewritten brick_fan() for subword comlexes. Now correct and generalized to coincide with the normal fan of brick_polyhedron()

[sagetrac-git]

Changed commit from f625039 to 24ae7de

[sagetrac-git]

Changed commit from 24ae7de to 167f102

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

167f102

more details in the doc of upper_root_configuration

[mkoeppe]

comment:9

+        from warnings import warn
+        warn("brick_polytope() is deprecated; brick_polyhedron() is used instead; results are different for non-spherical subword complexes", DeprecationWarning)

better to use deprecation from sage.misc.superseded for this

[mkoeppe]

comment:10

if you install the optional package pynormaliz, you can also do exact computations over number fields, this should probably be a user option

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

12cb089

updated files from 32669

[sagetrac-git]

Changed commit from 167f102 to 12cb089

[DennisJahn]

comment:12

Replying to @mkoeppe:

if you install the optional package pynormaliz, you can also do exact computations over number fields, this should probably be a user option

I did install it but keep getting problems with vertices over the universal cyclotomic field:

1.618033988749895? of type <class 'sage.rings.qqbar.AlgebraicReal'> not valid to initialize an element of the universal cyclotomic field

Is there a way to work around this?

[sagetrac-git]

Changed commit from 12cb089 to e011ef5

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

e011ef5

used deprecated_function_alias for brick_polytope instead of warn

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

3a5fca1

corrected the deprecation number

[sagetrac-git]

Changed commit from e011ef5 to 3a5fca1

[sagetrac-git]

Changed commit from 3a5fca1 to 6e6864c

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

6e6864c

added missing 'optional - gap 3' flags

[kliem]

comment:17

diff --git a/src/sage/combinat/root_system/reflection_group_real.py b/src/sage/combinat/root_system/reflection_group_real.py
index 91333f0ca5..1fbf87496e 100644
--- a/src/sage/combinat/root_system/reflection_group_real.py
+++ b/src/sage/combinat/root_system/reflection_group_real.py
@@ -706,8 +706,8 @@ class RealReflectionGroup(ComplexReflectionGroup):
             [0, 1, 2]
         """
         return self._index_set_inverse[i]
-    
-    def bruhat_cone(self, x, y, side = 'upper'):
+
+    def bruhat_cone(self, x, y, side='upper', backend='cdd'):
         r"""
         Return the polyhedral cone generated by the set of positive roots ``beta`` where ``s_beta`` is the reflection corresponding to ``beta`` and:
 
@@ -744,12 +744,16 @@ class RealReflectionGroup(ComplexReflectionGroup):
             raise ValueError("side must be either 'upper' or 'lower'")
         from sage.geometry.polyhedron.constructor import Polyhedron
         if self.is_crystallographic():
-            return Polyhedron(vertices = [[0]*self.rank()], rays = roots, ambient_dim = self.rank())
+            return Polyhedron(vertices = [[0]*self.rank()], rays=roots, ambient_dim=self.rank(), backend=backend)
         else:
-            from warnings import warn
-            warn("Using floating point numbers for roots of unity. This might cause numerical errors!")
-            from sage.rings.real_double import RDF
-            return Polyhedron(vertices = [[0]*self.rank()], rays = roots, ambient_dim = self.rank(), base_ring = RDF)
+            if backend == 'cdd':
+                from warnings import warn
+                warn("Using floating point numbers for roots of unity. This might cause numerical errors!")
+                from sage.rings.real_double import RDF as base_ring
+                backend = 'cdd'
+            else:
+                from sage.rings.qqbar import AA as base_ring
+            return Polyhedron(vertices = [[0]*self.rank()], rays=roots, ambient_dim=self.rank(), base_ring=base_ring, backend=backend)
 
     class Element(RealReflectionGroupElement, ComplexReflectionGroup.Element):
 
diff --git a/src/sage/combinat/subword_complex.py b/src/sage/combinat/subword_complex.py
index bbf750b56d..dc64b5882c 100644
--- a/src/sage/combinat/subword_complex.py
+++ b/src/sage/combinat/subword_complex.py
@@ -638,9 +638,9 @@ class SubwordComplexFacet(Simplex, Element):
 
         - ``coefficients`` -- (optional) a list of coefficients used to
           scale the fundamental weights
-        
+
         - ``sign`` -- (default: ``'positive'``) must be one of the following:
-        
+
           * ``'positive'`` - entries of the extended weight configuration are summed up as they are
           * ``'negative'`` - entries of the extended weight configuration are summed up with a negative sign
 
@@ -1660,9 +1660,9 @@ class SubwordComplex(UniqueRepresentation, SimplicialComplex):
 
         - coefficients -- (optional) a list of coefficients used to
           scale the fundamental weights
-        
+
         - ``sign`` -- (default: ``'positive'``) must be one of the following:
-        
+
           * ``'positive'`` - for brick vectors, entries of the extended weight configuration are summed up as they are
           * ``'negative'`` - for brick vectors, entries of the extended weight configuration are summed up with a negative sign
 
@@ -1690,7 +1690,7 @@ class SubwordComplex(UniqueRepresentation, SimplicialComplex):
 
     def minkowski_summand(self, i):
         r"""
-        Return the `i` th Minkowski summand of ``self``. The brick polyhedron of ``self`` is the 
+        Return the `i` th Minkowski summand of ``self``. The brick polyhedron of ``self`` is the
         Minkowski sum of its associated Bruhat cone and all Minkowski summands.
 
         INPUT:
@@ -1720,7 +1720,7 @@ class SubwordComplex(UniqueRepresentation, SimplicialComplex):
             min_sum = [[QQ(CC(v)) for v in F.extended_weight_configuration()[i]] for F in self]
         return Polyhedron(min_sum)
 
-    def brick_polyhedron(self, coefficients=None, sign='positive'):
+    def brick_polyhedron(self, coefficients=None, sign='positive', backend='cdd'):
         r"""
         Return the brick polyhedron of ``self``.
 
@@ -1731,9 +1731,9 @@ class SubwordComplex(UniqueRepresentation, SimplicialComplex):
 
         - coefficients -- (optional) a list of coefficients used to
           scale the fundamental weights
-        
+
         - ``sign`` -- (default: ``'positive'``) must be one of the following:
-        
+
           * ``'positive'`` - entries of the extended weight configuration are summed up as they are.
             The Bruhat cone is taken with a negative sign.
           * ``'negative'`` - entries of the extended weight configuration are summed up with a negative sign.
@@ -1762,29 +1762,32 @@ class SubwordComplex(UniqueRepresentation, SimplicialComplex):
             sage: SC = SubwordComplex(Q,W.w0)                           # optional - gap3
             sage: SC.brick_polyhedron()                                 # optional - gap3
             A 3-dimensional polyhedron in RDF^3 defined as the convex hull of 32 vertices
-            
+
             sage: W = ReflectionGroup(['B',2])                          # optional - gap3
             sage: Q = W.w0.reduced_word()                               # optional - gap3
             sage: SC = SubwordComplex(Q, W.from_reduced_word([1]))      # optional - gap3
             sage: SC.brick_polyhedron()                                 # optional - gap3
             A 2-dimensional polyhedron in QQ^2 defined as the convex hull of 2 vertices and 2 rays
-            
+
         REFERENCES: [JahStu]_
         """
         BV = self.brick_vectors(coefficients=coefficients, sign=sign)
         G = self.group()
         if sign == 'positive':
-            BC = -G.bruhat_cone(self.pi(), G.demazure_product(self.word()))
+            BC = -G.bruhat_cone(self.pi(), G.demazure_product(self.word()), backend=backend)
         elif sign == 'negative':
-            BC = G.bruhat_cone(self.pi(), G.demazure_product(self.word()))
+            BC = G.bruhat_cone(self.pi(), G.demazure_product(self.word()), backend=backend)
         else:
             raise ValueError("sign must be either 'positive' or 'negative'")
         if G.coxeter_matrix().is_crystallographic():
-            return Polyhedron(BV, ambient_dim = G.rank()) + BC
+            return Polyhedron(BV, ambient_dim=G.rank(), backend=backend) + BC
         else:
-            from sage.rings.real_double import RDF
-            return Polyhedron(BV, ambient_dim = G.rank(), base_ring = RDF) + BC
-    
+            if backend == 'cdd':
+                from sage.rings.real_double import RDF as base_ring
+            else:
+                from sage.rings.qqbar import AA as base_ring
+            return Polyhedron(BV, ambient_dim=G.rank(), base_ring=base_ring, backend=backend) + BC
+
     from sage.misc.superseded import deprecated_function_alias
     brick_polytope = deprecated_function_alias(32681, brick_polyhedron)

The backend keyword is missing anyway and should be added.

In can be documented similar to what is done in src/sage/geometry/polyhedron/library.py.

A general remark: A keyword assignment should not have spaces guarding =: Polyhedron(backend='cdd').

[sagetrac-git]

Changed commit from e46af36 to 08202bc

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

[sagetrac-git]

Changed commit from 08202bc to 8164229

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

9ca2b2f	added Knutson Miller 2004 and Pilaud Stump 2015 to master reference file
8164229	replacing brick polytopes by brick polyhedra, marked brick polytope as deprecated function, extended brick vectors with a sign for choice of convention, generalized brick fan for brick polyhedra, switched references for master reference file

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

679d177

minor doc change

[sagetrac-git]

Changed commit from 8164229 to 679d177

[sagetrac-git]

Changed commit from 679d177 to 620abf6

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

620abf6

doc intro rewritten for brick polyhedra

[sagetrac-git]

Changed commit from 620abf6 to 436a8ba

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

436a8ba

fixing gap3 doctests

[stumpc5]

comment:36

The code looks good to me! @tscrim, @fchapoton: I am sure you have some comments, at least concerning the formatting and/or the doctests. Could you maybe have a quick look? -- Thanks!

[fchapoton]

comment:37

doc does not build

 /home/sagemath/sage/src/sage/combinat/subword_complex.py:docstring of sage.combinat.subword_complex.SubwordComplex.brick_polyhedron:50: WARNING: citation not found: JS2021

[fchapoton]

comment:38

the new deprecation must be doctested, for exemple in the module documentation near the top of the file

[sagetrac-git]

Changed commit from 436a8ba to b3abcc9

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. New commits:

b3abcc9

one more function, new doctest for new deprecation

[DennisJahn]

comment:40

Replying to Frédéric Chapoton:

doc does not build

 /home/sagemath/sage/src/sage/combinat/subword_complex.py:docstring of sage.combinat.subword_complex.SubwordComplex.brick_polyhedron:50: WARNING: citation not found: JS2021

The reference [JS2021] was added in #32669
I added the doctest for the new deprecation

[fchapoton]

comment:41

I disagree with the replacement of non-gap3-optional doctests with gap3 optional doctests.

[DennisJahn]

comment:42

Replying to Frédéric Chapoton:

I disagree with the replacement of non-gap3-optional doctests with gap3 optional doctests.

The replacement of brick_polytope() by brick_polyhedron() requires the computation of the associated Bruhat cone which is implemented for finite real reflection groups and needs gap3.

[tscrim]

comment:43

Sorry it took me a while to get to this.

It shouldn't be hard to implement the bruhat_cone for Weyl groups. However, you still are removing functionality. This needs to be justified, and, if deemed to be reasonable, deprecated. At least in the short term, you can just have a isinstance(G, RealReflectionGroup): to do the new implementation while keeping the old since they are both fairly short.

Also, I think it would be easier to replace the string sign with a boolean positive[_roots].

[stumpc5]

comment:44

I think using isinstance(G, RealReflectionGroup) is a reasonable workaround.