bug in polyhedron over RDF

[videlec]

verts = [[159852/261157, 227425/261157],
 [9/10, 7/10],
 [132/179, 143/179],
 [8/11, -59/33],
 [174/167, 95/167],
 [3/2, -1/2],
 [-1162016360399650274197433414376009691155/1045602428815736513789288687833080060779,
  1626522696050475596930360993440360903664/1045602428815736513789288687833080060779],
 [-112565666321600055047037445519656973805313121630809713051718/76591188009721216624438400001815308369088648782156930777145,
  -15318574020578896781701071673537253327221557273483622682053/76591188009721216624438400001815308369088648782156930777145],
 [-222823992658914823798345935660863293259608796350232624336738123149601409997996952470726909468671437285720616325991022633438/141046287872967162025203834781636948939209065735662536571684677443277621519222367249160281646288602157866548267640061850035,
  -20857694835570598502487921801401627779907095024585170129381924208334510445828894861553290291713792691651471189597832832973/28209257574593432405040766956327389787841813147132507314336935488655524303844473449832056329257720431573309653528012370007],
 [-100432602675156818915933977983765863676402454634873648118147187022041830166292457614016362515164/169296796161110084211548448622149955145002732358082778064645608216077666698460018565094060494217,
  -429364759737031049317769174492863890735634068814210512342503744054527903830844433491149538512537/169296796161110084211548448622149955145002732358082778064645608216077666698460018565094060494217]]
P = Polyhedron(verts, base_ring=RDF)
P.faces(1)

with traceback

sage: P.faces(1)
---------------------------------------------------------------------------
KeyError                                  Traceback (most recent call last)
<ipython-input-4-5c776b0f6df7> in <module>()
----> 1 P.faces(Integer(1))

/opt/sage/local/lib/python2.7/site-packages/sage/geometry/polyhedron/base.pyc in faces(self, face_dimension)
   3890             ()
   3891         """
-> 3892         fl = self.face_lattice().level_sets()
   3893         codim = self.dim() - face_dimension
   3894         index = len(fl) - 1 - codim

/opt/sage/local/lib/python2.7/site-packages/sage/misc/cachefunc.pyx in sage.misc.cachefunc.CachedMethodCallerNoArgs.__call__ (build/cythonized/sage/misc/cachefunc.c:13441)()
   2375         if self.cache is None:
   2376             f = self.f
-> 2377             self.cache = f(self._instance)
   2378         return self.cache
   2379 

/opt/sage/local/lib/python2.7/site-packages/sage/geometry/polyhedron/base.pyc in face_lattice(self)
   3814         return Hasse_diagram_from_incidences\
   3815             (atoms_incidences, coatoms_incidences,
-> 3816              face_constructor=face_constructor, required_atoms=atoms_vertices)
   3817 
   3818     def faces(self, face_dimension):

/opt/sage/local/lib/python2.7/site-packages/sage/geometry/hasse_diagram.pyc in Hasse_diagram_from_incidences(atom_to_coatoms, coatom_to_atoms, face_constructor, required_atoms, key, **kwds)
    180     # Make sure that coatoms are in the end in proper order
    181     tail = [faces[atoms, frozenset([coatom])]
--> 182             for coatom, atoms in enumerate(coatom_to_atoms)]
    183     tail.append(faces[A, frozenset()])
    184     new_order = [n for n in new_order if n not in tail] + tail

KeyError: (frozenset([7]), frozenset([3]))

Actually the obtained polygon has 9 vertices and 10 edges

sage: P.n_vertices()
9
sage: P.n_facets()
10

CC: @jplab @fchapoton

Component: geometry

Keywords: days93, days100

Author: Jean-Philippe Labbé

Branch/Commit: 00819d9

Reviewer: Frédéric Chapoton

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

[videlec]

Description changed:

--- 
+++ 
@@ -17,3 +17,104 @@
 P = Polyhedron(verts, base_ring=RDF)
 P.plot()
 ```
+with traceback
+
+```
+.../sage/geometry/polyhedron/base.pyc in
+plot(self, point, line, polygon, wireframe, fill, projection_direction, **kwds)
+    789                 return polyhedron.projection()
+    790 
+--> 791         projection = project(self)
+    792         try:
+    793             plot_method = projection.plot
+
+.../sage/geometry/polyhedron/base.pyc
+in project(polyhedron)
+    787                 return polyhedron.schlegel_projection()
+    788             else:
+--> 789                 return polyhedron.projection()
+    790 
+    791         projection = project(self)
+
+.../sage/geometry/polyhedron/base.pyc
+in projection(self)
+   4165         """
+   4166         from .plot import Projection
+-> 4167         self.projection = Projection(self)
+   4168         return self.projection
+   4169 
+
+.../sage/geometry/polyhedron/plot.pyc
+in __init__(self, polyhedron, proj)
+    492 
+    493         if polyhedron.ambient_dim() == 2:
+--> 494             self._init_from_2d(polyhedron)
+    495         elif polyhedron.ambient_dim() == 3:
+    496             self._init_from_3d(polyhedron)
+
+.../sage/geometry/polyhedron/plot.pyc
+in _init_from_2d(self, polyhedron)
+    748         self.dimension = 2
+    749         self._init_points(polyhedron)
+--> 750         self._init_lines_arrows(polyhedron)
+    751         self._init_area_2d(polyhedron)
+    752 
+
+.../sage/geometry/polyhedron/plot.pyc in
+_init_lines_arrows(self, polyhedron)
+    812             if not obj[i].is_vertex(): continue
+    813             for j in range(len(obj)):
+--> 814                 if polyhedron.vertex_adjacency_matrix()[i,j] == 0: continue
+    815                 if i < j and obj[j].is_vertex():
+    816                     l = [obj[i].vector(), obj[j].vector()]
+
+.../site-packages/sage/misc/cachefunc.pyx
+in sage.misc.cachefunc.CachedMethodCallerNoArgs.__call__ (build/cythonized/sage/misc/cachefunc.c:13441)()
+   2375         if self.cache is None:
+   2376             f = self.f
+-> 2377             self.cache = f(self._instance)
+   2378         return self.cache
+   2379 
+
+.../sage/geometry/polyhedron/base.pyc
+in vertex_adjacency_matrix(self)
+   2036             (0, 0, 1, 1, 0) A vertex at (3, 0)
+   2037         """
+-> 2038         return self._vertex_adjacency_matrix()
+   2039 
+   2040     adjacency_matrix = vertex_adjacency_matrix
+
+.../sage/geometry/polyhedron/base.pyc
+in _vertex_adjacency_matrix(self)
+    334             M[j, i] = 1
+    335 
+--> 336         face_lattice = self.face_lattice()
+    337         for face in face_lattice:
+    338             Vrep = face.ambient_Vrepresentation()
+
+.../sage/misc/cachefunc.pyx
+in sage.misc.cachefunc.CachedMethodCallerNoArgs.__call__ (build/cythonized/sage/misc/cachefunc.c:13441)()
+   2375         if self.cache is None:
+   2376             f = self.f
+-> 2377             self.cache = f(self._instance)
+   2378         return self.cache
+   2379 
+
+.../sage/geometry/polyhedron/base.pyc
+in face_lattice(self)
+   3814         return Hasse_diagram_from_incidences\
+   3815             (atoms_incidences, coatoms_incidences,
+-> 3816              face_constructor=face_constructor, required_atoms=atoms_vertices)
+   3817 
+   3818     def faces(self, face_dimension):
+
+.../sage/geometry/hasse_diagram.pyc
+in Hasse_diagram_from_incidences(atom_to_coatoms, coatom_to_atoms, face_constructor, required_atoms, key, **kwds)
+    180     # Make sure that coatoms are in the end in proper order
+    181     tail = [faces[atoms, frozenset([coatom])]
+--> 182             for coatom, atoms in enumerate(coatom_to_atoms)]
+    183     tail.append(faces[A, frozenset()])
+    184     new_order = [n for n in new_order if n not in tail] + tail
+
+KeyError: (frozenset([7]), frozenset([3]))
+```

[videlec]

Description changed:

--- 
+++ 
@@ -15,101 +15,39 @@
  [-100432602675156818915933977983765863676402454634873648118147187022041830166292457614016362515164/169296796161110084211548448622149955145002732358082778064645608216077666698460018565094060494217,
   -429364759737031049317769174492863890735634068814210512342503744054527903830844433491149538512537/169296796161110084211548448622149955145002732358082778064645608216077666698460018565094060494217]]
 P = Polyhedron(verts, base_ring=RDF)
-P.plot()
+P.faces(1)
 ```
 with traceback
 
 ```
-.../sage/geometry/polyhedron/base.pyc in
-plot(self, point, line, polygon, wireframe, fill, projection_direction, **kwds)
-    789                 return polyhedron.projection()
-    790 
---> 791         projection = project(self)
-    792         try:
-    793             plot_method = projection.plot
+sage: P.faces(1)
+---------------------------------------------------------------------------
+KeyError                                  Traceback (most recent call last)
+<ipython-input-4-5c776b0f6df7> in <module>()
+----> 1 P.faces(Integer(1))
 
-.../sage/geometry/polyhedron/base.pyc
-in project(polyhedron)
-    787                 return polyhedron.schlegel_projection()
-    788             else:
---> 789                 return polyhedron.projection()
-    790 
-    791         projection = project(self)
+/opt/sage/local/lib/python2.7/site-packages/sage/geometry/polyhedron/base.pyc in faces(self, face_dimension)
+   3890             ()
+   3891         """
+-> 3892         fl = self.face_lattice().level_sets()
+   3893         codim = self.dim() - face_dimension
+   3894         index = len(fl) - 1 - codim
 
-.../sage/geometry/polyhedron/base.pyc
-in projection(self)
-   4165         """
-   4166         from .plot import Projection
--> 4167         self.projection = Projection(self)
-   4168         return self.projection
-   4169 
-
-.../sage/geometry/polyhedron/plot.pyc
-in __init__(self, polyhedron, proj)
-    492 
-    493         if polyhedron.ambient_dim() == 2:
---> 494             self._init_from_2d(polyhedron)
-    495         elif polyhedron.ambient_dim() == 3:
-    496             self._init_from_3d(polyhedron)
-
-.../sage/geometry/polyhedron/plot.pyc
-in _init_from_2d(self, polyhedron)
-    748         self.dimension = 2
-    749         self._init_points(polyhedron)
---> 750         self._init_lines_arrows(polyhedron)
-    751         self._init_area_2d(polyhedron)
-    752 
-
-.../sage/geometry/polyhedron/plot.pyc in
-_init_lines_arrows(self, polyhedron)
-    812             if not obj[i].is_vertex(): continue
-    813             for j in range(len(obj)):
---> 814                 if polyhedron.vertex_adjacency_matrix()[i,j] == 0: continue
-    815                 if i < j and obj[j].is_vertex():
-    816                     l = [obj[i].vector(), obj[j].vector()]
-
-.../site-packages/sage/misc/cachefunc.pyx
-in sage.misc.cachefunc.CachedMethodCallerNoArgs.__call__ (build/cythonized/sage/misc/cachefunc.c:13441)()
+/opt/sage/local/lib/python2.7/site-packages/sage/misc/cachefunc.pyx in sage.misc.cachefunc.CachedMethodCallerNoArgs.__call__ (build/cythonized/sage/misc/cachefunc.c:13441)()
    2375         if self.cache is None:
    2376             f = self.f
 -> 2377             self.cache = f(self._instance)
    2378         return self.cache
    2379 
 
-.../sage/geometry/polyhedron/base.pyc
-in vertex_adjacency_matrix(self)
-   2036             (0, 0, 1, 1, 0) A vertex at (3, 0)
-   2037         """
--> 2038         return self._vertex_adjacency_matrix()
-   2039 
-   2040     adjacency_matrix = vertex_adjacency_matrix
-
-.../sage/geometry/polyhedron/base.pyc
-in _vertex_adjacency_matrix(self)
-    334             M[j, i] = 1
-    335 
---> 336         face_lattice = self.face_lattice()
-    337         for face in face_lattice:
-    338             Vrep = face.ambient_Vrepresentation()
-
-.../sage/misc/cachefunc.pyx
-in sage.misc.cachefunc.CachedMethodCallerNoArgs.__call__ (build/cythonized/sage/misc/cachefunc.c:13441)()
-   2375         if self.cache is None:
-   2376             f = self.f
--> 2377             self.cache = f(self._instance)
-   2378         return self.cache
-   2379 
-
-.../sage/geometry/polyhedron/base.pyc
-in face_lattice(self)
+/opt/sage/local/lib/python2.7/site-packages/sage/geometry/polyhedron/base.pyc in face_lattice(self)
    3814         return Hasse_diagram_from_incidences\
    3815             (atoms_incidences, coatoms_incidences,
 -> 3816              face_constructor=face_constructor, required_atoms=atoms_vertices)
    3817 
    3818     def faces(self, face_dimension):
 
-.../sage/geometry/hasse_diagram.pyc
-in Hasse_diagram_from_incidences(atom_to_coatoms, coatom_to_atoms, face_constructor, required_atoms, key, **kwds)
+/opt/sage/local/lib/python2.7/site-packages/sage/geometry/hasse_diagram.pyc in Hasse_diagram_from_incidences(atom_to_coatoms, coatom_to_atoms, face_constructor, required_atoms, key, **kwds)
     180     # Make sure that coatoms are in the end in proper order
     181     tail = [faces[atoms, frozenset([coatom])]
 --> 182             for coatom, atoms in enumerate(coatom_to_atoms)]
@@ -118,3 +56,11 @@
 
 KeyError: (frozenset([7]), frozenset([3]))
 ```
+Actually the obtained polygon has 9 vertices and 10 edges
+
+```
+sage: P.n_vertices()
+9
+sage: P.n_facets()
+10
+```

[jplab]

comment:3

Perhaps this a is quintessence new polygon that you found there!

[fchapoton]

comment:4

may be related to #18214

[jplab]

comment:5

On version 8.8.beta3 I get:

┌────────────────────────────────────────────────────────────────────┐
│ SageMath version 8.8.beta3, Release Date: 2019-04-18               │
│ Using Python 2.7.15. Type "help()" for help.                       │
└────────────────────────────────────────────────────────────────────┘
┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓
┃ Warning: this is a prerelease version, and it may be unstable.     ┃
┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛
sage: verts = [[159852/261157, 227425/261157],
....:  [9/10, 7/10],
....:  [132/179, 143/179],
....:  [8/11, -59/33],
....:  [174/167, 95/167],
....:  [3/2, -1/2],
....:  [-1162016360399650274197433414376009691155/1045602428815736513789288687833080060779,
....:   1626522696050475596930360993440360903664/1045602428815736513789288687833080060779],
....:  [-112565666321600055047037445519656973805313121630809713051718/76591188009721216624438400001815308369088648782156930777145,
....:   -15318574020578896781701071673537253327221557273483622682053/76591188009721216624438400001815308369088648782156930777145],
....:  [-222823992658914823798345935660863293259608796350232624336738123149601409997996952470726909468671437285720616325991022633438/141046287872967162025203834781636948939209065735662536571684677443277621519222
....: 367249160281646288602157866548267640061850035,
....:   -20857694835570598502487921801401627779907095024585170129381924208334510445828894861553290291713792691651471189597832832973/2820925757459343240504076695632738978784181314713250731433693548865552430384447
....: 3449832056329257720431573309653528012370007],
....:  [-100432602675156818915933977983765863676402454634873648118147187022041830166292457614016362515164/169296796161110084211548448622149955145002732358082778064645608216077666698460018565094060494217,
....:   -429364759737031049317769174492863890735634068814210512342503744054527903830844433491149538512537/169296796161110084211548448622149955145002732358082778064645608216077666698460018565094060494217]]
....: P = Polyhedron(verts, base_ring=RDF)
....: P.faces(1)
....: 
(A 1-dimensional face of a Polyhedron in RDF^2 defined as the convex hull of 2 vertices,
 A 1-dimensional face of a Polyhedron in RDF^2 defined as the convex hull of 2 vertices,
 A 1-dimensional face of a Polyhedron in RDF^2 defined as the convex hull of 2 vertices,
 A 1-dimensional face of a Polyhedron in RDF^2 defined as the convex hull of 2 vertices,
 A 1-dimensional face of a Polyhedron in RDF^2 defined as the convex hull of 2 vertices,
 A 1-dimensional face of a Polyhedron in RDF^2 defined as the convex hull of 2 vertices,
 A 1-dimensional face of a Polyhedron in RDF^2 defined as the convex hull of 2 vertices,
 A 1-dimensional face of a Polyhedron in RDF^2 defined as the convex hull of 2 vertices,
 A 1-dimensional face of a Polyhedron in RDF^2 defined as the convex hull of 2 vertices,
 A 1-dimensional face of a Polyhedron in RDF^2 defined as the convex hull of 2 vertices)
sage: P.n_vertices()
10
sage: P.n_facets()
10

On stable 8.7, I get:

┌────────────────────────────────────────────────────────────────────┐
│ SageMath version 8.7, Release Date: 2019-03-23                     │
│ Using Python 2.7.15. Type "help()" for help.                       │
└────────────────────────────────────────────────────────────────────┘
sage: verts = [[159852/261157, 227425/261157],
....:  [9/10, 7/10],
....:  [132/179, 143/179],
....:  [8/11, -59/33],
....:  [174/167, 95/167],
....:  [3/2, -1/2],
....:  [-1162016360399650274197433414376009691155/1045602428815736513789288687833080060779,
....:   1626522696050475596930360993440360903664/1045602428815736513789288687833080060779],
....:  [-112565666321600055047037445519656973805313121630809713051718/76591188009721216624438400001815308369088648782156930777145,
....:   -15318574020578896781701071673537253327221557273483622682053/76591188009721216624438400001815308369088648782156930777145],
....:  [-222823992658914823798345935660863293259608796350232624336738123149601409997996952470726909468671437285720616325991022633438/141046287872967162025203834781636948939209065735662536571684677443277621519222
....: 367249160281646288602157866548267640061850035,
....:   -20857694835570598502487921801401627779907095024585170129381924208334510445828894861553290291713792691651471189597832832973/2820925757459343240504076695632738978784181314713250731433693548865552430384447
....: 3449832056329257720431573309653528012370007],
....:  [-100432602675156818915933977983765863676402454634873648118147187022041830166292457614016362515164/169296796161110084211548448622149955145002732358082778064645608216077666698460018565094060494217,
....:   -429364759737031049317769174492863890735634068814210512342503744054527903830844433491149538512537/169296796161110084211548448622149955145002732358082778064645608216077666698460018565094060494217]]
....: P = Polyhedron(verts, base_ring=RDF)
....: P.faces(1)
....: 
(<1,2>, <0,2>, <1,4>, <3,5>, <4,5>, <0,6>, <6,7>, <7,8>, <8,9>, <3,9>)
sage: P.n_vertices()
10
sage: P.n_facets()
10

Should this become a doctest?

[jplab]

Author: Jean-Philippe Labbé

[jplab]

Branch: u/jipilab/24877

[jplab]

Commit: 00819d9

[jplab]

New commits:

00819d9

Added doctest

[jplab]

Changed keywords from days93 to days93, days100