Sage: Ticket #26922: Wrong f-vector for unbounded polyhedra
https://trac.sagemath.org/ticket/26922
<p>
<a class="closed ticket" href="https://trac.sagemath.org/ticket/28625" title="enhancement: Let CombinatorialPolyhedron handle f_vector of polyhedra (closed: fixed)">#28625</a> fixed the <code>f_vector</code> in the case of unpointed polyhedra/polyhedra with lines.
</p>
<p>
We add doctests showing that <a class="closed ticket" href="https://trac.sagemath.org/ticket/28625" title="enhancement: Let CombinatorialPolyhedron handle f_vector of polyhedra (closed: fixed)">#28625</a> fixed a bug in <code>f_vector</code>.
</p>
<p>
Before:
</p>
<pre class="wiki">sage: Polyhedron(ieqs=[[1,-1,0],[1,1,0]]).f_vector()
(1, 2, 1)
</pre><p>
But this polyhedron does not have zero-dimensional faces, and <a class="closed ticket" href="https://trac.sagemath.org/ticket/28625" title="enhancement: Let CombinatorialPolyhedron handle f_vector of polyhedra (closed: fixed)">#28625</a> has correctly changed that:
</p>
<pre class="wiki">sage: Polyhedron(ieqs=[[1,-1,0],[1,1,0]]).f_vector()
(1, 0, 2, 1)
</pre><p>
Also we add documentation, specifically warning users that the methods
</p>
<ul><li><code>vertices</code>,
</li><li><code>vertices_list</code>,
</li><li><code>vertices_generator</code>
</li><li><code>vertices_matrix</code>,
</li><li><code>n_vertices</code>,
</li></ul><p>
treat vertices of the <code>Vrepresentation</code> and not vertices of the polyhedron in the unpointed case.
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/26922
Trac 1.1.6gh-kliemSat, 12 Jan 2019 16:43:43 GMT
https://trac.sagemath.org/ticket/26922#comment:1
https://trac.sagemath.org/ticket/26922#comment:1
<p>
This will be probably solved at some point by
<a class="closed ticket" href="https://trac.sagemath.org/ticket/26887" title="enhancement: Implement the class CombinatorialPolyhedron (closed: fixed)">#26887</a>
The calculation is correct there.
</p>
<p>
Also it can be corrected quickly now by calculating the dimension of the first level in the face lattice.
</p>
TicketembrayTue, 15 Jan 2019 18:15:21 GMTmilestone changed
https://trac.sagemath.org/ticket/26922#comment:2
https://trac.sagemath.org/ticket/26922#comment:2
<ul>
<li><strong>milestone</strong>
changed from <em>sage-8.6</em> to <em>sage-8.7</em>
</li>
</ul>
<p>
Retarging tickets optimistically to the next milestone. If you are responsible for this ticket (either its reporter or owner) and don't believe you are likely to complete this ticket before the next release (8.7) please retarget this ticket's milestone to sage-pending or sage-wishlist.
</p>
TicketjipilabThu, 14 Mar 2019 15:59:47 GMTmilestone changed
https://trac.sagemath.org/ticket/26922#comment:3
https://trac.sagemath.org/ticket/26922#comment:3
<ul>
<li><strong>milestone</strong>
changed from <em>sage-8.7</em> to <em>sage-8.8</em>
</li>
</ul>
TicketembrayFri, 14 Jun 2019 14:54:19 GMTmilestone deleted
https://trac.sagemath.org/ticket/26922#comment:4
https://trac.sagemath.org/ticket/26922#comment:4
<ul>
<li><strong>milestone</strong>
<em>sage-8.8</em> deleted
</li>
</ul>
<p>
As the Sage-8.8 release milestone is pending, we should delete the sage-8.8 milestone for tickets that are not actively being worked on or that still require significant work to move forward. If you feel that this ticket should be included in the next Sage release at the soonest please set its milestone to the next release milestone (sage-8.9).
</p>
TicketjipilabMon, 22 Jul 2019 12:37:40 GMT
https://trac.sagemath.org/ticket/26922#comment:5
https://trac.sagemath.org/ticket/26922#comment:5
<p>
In principle, the problem is that the face lattice has four elements, but the elements on the second level are not 0-dimensional, but 1-dimensional.
</p>
<p>
So, depending on the definition of the f-vector:
</p>
<ul><li>Counting the number of elements at each level of the face lattice
</li><li>Vector counting the number of faces by dimension
</li></ul><p>
It should return different things.
</p>
<p>
One thing that should be done, is to make this explicit in the documentation of <code>f_vector</code> once this ticket is fixed and give an example of the difference with unbounded polyhedra.
</p>
Ticketgh-kliemMon, 22 Jul 2019 19:00:21 GMT
https://trac.sagemath.org/ticket/26922#comment:6
https://trac.sagemath.org/ticket/26922#comment:6
<p>
<a class="closed ticket" href="https://trac.sagemath.org/ticket/27063" title="task: Transition of combinatorial computations of Polyhedron to ... (closed: invalid)">#27063</a> will change the calculation of the f-vector (hopefully soon) to make use of <code>CombinatorialPolyhedron</code>.
</p>
<p>
This will count the number of faces per dimension, as the docstring of <code>f_vector</code> states (there is a +2 or -2 two missing, as the first entry gives the -1-dimensional faces count.
</p>
<p>
We could make this ticket depend on <a class="closed ticket" href="https://trac.sagemath.org/ticket/27063" title="task: Transition of combinatorial computations of Polyhedron to ... (closed: invalid)">#27063</a> and then just append the docstring accordingly.
</p>
<p>
One could also fix it for now (just append a few zeros according to <code>n_lines</code>).
</p>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/26922#comment:5" title="Comment 5">jipilab</a>:
</p>
<blockquote class="citation">
<p>
In principle, the problem is that the face lattice has four elements, but the elements on the second level are not 0-dimensional, but 1-dimensional.
</p>
<p>
So, depending on the definition of the f-vector:
</p>
<ul><li>Counting the number of elements at each level of the face lattice
</li></ul></blockquote>
<p>
I think f-vectors of fixed dimension polyhedra should be have sums/addition.
Also if one considers how adding or deleting inequalities can alter the f-vector this is strange.
Anyway, it's most important to be precise, which one we use. Adding a zero or deleting it, if one really depends one version is trivial.
</p>
<blockquote class="citation">
<ul><li>Vector counting the number of faces by dimension
</li></ul><p>
It should return different things.
</p>
<p>
One thing that should be done, is to make this explicit in the documentation of <code>f_vector</code> once this ticket is fixed and give an example of the difference with unbounded polyhedra.
</p>
</blockquote>
TicketjipilabThu, 17 Oct 2019 12:00:21 GMT
https://trac.sagemath.org/ticket/26922#comment:7
https://trac.sagemath.org/ticket/26922#comment:7
<p>
ping!
</p>
Ticketgh-kliemFri, 18 Oct 2019 09:41:48 GMTstatus changed; author, dependencies, branch, milestone, commit set
https://trac.sagemath.org/ticket/26922#comment:8
https://trac.sagemath.org/ticket/26922#comment:8
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
<li><strong>author</strong>
set to <em>Jonathan Kliem</em>
</li>
<li><strong>dependencies</strong>
set to <em>#28625</em>
</li>
<li><strong>branch</strong>
set to <em>public/26922</em>
</li>
<li><strong>milestone</strong>
set to <em>sage-9.0</em>
</li>
<li><strong>commit</strong>
set to <em>3c9085ec178d0ad052612d9db53fe588940fe48a</em>
</li>
</ul>
<p>
<a class="closed ticket" href="https://trac.sagemath.org/ticket/28625" title="enhancement: Let CombinatorialPolyhedron handle f_vector of polyhedra (closed: fixed)">#28625</a> fixes this.
</p>
<p>
I added some tests, improved the documentation of <code>f_vector</code> and fixed a tiny typo.
</p>
<hr />
<p>
New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit?id=b89610e0a70bdde272d632ef1d7972941ab19311"><span class="icon"></span>b89610e</a></td><td><code>added combinatorial polyhedron as an attribute for polyhedra</code>
</td></tr><tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit?id=326602c596658236784ad8cf325c382ed8b419c6"><span class="icon"></span>326602c</a></td><td><code>f_vector of CombinatorialPolyhedron is a vector</code>
</td></tr><tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit?id=dfbe2adcb176affcbece7b92ae5d75b6b6009c35"><span class="icon"></span>dfbe2ad</a></td><td><code>Merge branch 'public/28607' of git://trac.sagemath.org/sage into public/28621</code>
</td></tr><tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit?id=ed5518bcfc80d185bf9979fae5a5076fd61ba42c"><span class="icon"></span>ed5518b</a></td><td><code>used CombinatorialPolyhedron to compute f_vector</code>
</td></tr><tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit?id=9bdd0055054b6cbc8c665904083e06748553329c"><span class="icon"></span>9bdd005</a></td><td><code>give an error message for polytopes in some cases; removed incorrect example</code>
</td></tr><tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit?id=acd671d2d21c0a2eda565d8f9281d88a1f046233"><span class="icon"></span>acd671d</a></td><td><code>now we get a precice error message for inexact truncated dodecahedron</code>
</td></tr><tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit?id=bf85a62865c1a3da76857065169caa7754ba4cd8"><span class="icon"></span>bf85a62</a></td><td><code>subsequent calls for f_vector fail if first attempt fails</code>
</td></tr><tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit?id=3c9085ec178d0ad052612d9db53fe588940fe48a"><span class="icon"></span>3c9085e</a></td><td><code>give doctests that f_vector for unbounded polyhedra works now</code>
</td></tr></table>
TicketjipilabSat, 19 Oct 2019 10:27:40 GMTstatus changed
https://trac.sagemath.org/ticket/26922#comment:9
https://trac.sagemath.org/ticket/26922#comment:9
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
It would be nice if the note that you gave be in a NOTE environment followed by an appropriate example illustrating what is meant.
</p>
TicketgitTue, 22 Oct 2019 12:32:48 GMTcommit changed
https://trac.sagemath.org/ticket/26922#comment:10
https://trac.sagemath.org/ticket/26922#comment:10
<ul>
<li><strong>commit</strong>
changed from <em>3c9085ec178d0ad052612d9db53fe588940fe48a</em> to <em>cbcc4c42cb427c2967097098d00a771a6d47eb44</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=cbcc4c42cb427c2967097098d00a771a6d47eb44"><span class="icon"></span>cbcc4c4</a></td><td><code>Comment to f_vector in NOTE environment; warnings of ambigious meaning of vertex</code>
</td></tr></table>
Ticketgh-kliemTue, 22 Oct 2019 12:46:11 GMTstatus, description changed
https://trac.sagemath.org/ticket/26922#comment:11
https://trac.sagemath.org/ticket/26922#comment:11
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/26922?action=diff&version=11">diff</a>)
</li>
</ul>
TicketjipilabThu, 24 Oct 2019 08:56:12 GMTcc, status changed; reviewer set
https://trac.sagemath.org/ticket/26922#comment:12
https://trac.sagemath.org/ticket/26922#comment:12
<ul>
<li><strong>cc</strong>
<em>moritz</em> added; <em>mortiz</em> removed
</li>
<li><strong>reviewer</strong>
set to <em>Jean-Philippe Labbé</em>
</li>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>needs_work</em>
</li>
</ul>
<p>
May I suggest the following:
</p>
<div class="wiki-code"><div class="code"><pre>
<span class="gd">- In case of a polyhedron with lines (unpointed polyhedron),
- return the number of vertices of the ``Vrepresentation``.
- Wheras the polyhedron has no vertices, this number corresponds
- to the number of `k`-faces, where `k` is the number of lines.
</span><span class="gi">+ If the polyhedron has lines, returns the number of vertices in
+ the ``Vrepresentation``. As the represented polyhedron has
+ no 0-dimensional faces (i.e. vertices), this number corresponds
+ to the number of `k`-faces, where `k` is the number of lines.
</span></pre></div></div><p>
Somehow, even though I corrected the above warning. I do not like what it says at all for the following reason:
</p>
<pre class="wiki">sage: P = Polyhedron(rays=[[1,0,0]],lines=[[0,1,0]])
sage: P.vertices()
(A vertex at (0, 0, 0),)
sage: Q = Polyhedron(lines=[[0,1,0],[0,0,1]])
sage: Q.vertices()
(A vertex at (0, 0, 0),)
sage: R = Polyhedron(rays=[[1,0,0],[0,1,0]],vertices=[[0,1,0],[1,0,0]],lines=[[0,0,1]])
sage: R.vertices()
(A vertex at (0, 1, 0), A vertex at (1, 0, 0))
</pre><p>
In Sage, the computational convention (or compromise) is that polyhedra without vertices in their V-representation still receive a canonically computed vertex in order to do computations.
</p>
<p>
With this in mind, the second sentence is wrong. Just look at the above polyhedron <code>R</code>. It has lines, and two vertices.
</p>
<p>
---> This warning is more confusing than anything. Please rephrase taking the above three examples in mind and the convention in Sage.
</p>
TicketgitFri, 25 Oct 2019 09:53:02 GMTcommit changed
https://trac.sagemath.org/ticket/26922#comment:13
https://trac.sagemath.org/ticket/26922#comment:13
<ul>
<li><strong>commit</strong>
changed from <em>cbcc4c42cb427c2967097098d00a771a6d47eb44</em> to <em>1c5378cd38b1f65717a2556ae7dc9ca7f756a150</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=1c5378cd38b1f65717a2556ae7dc9ca7f756a150"><span class="icon"></span>1c5378c</a></td><td><code>clearified warnings</code>
</td></tr></table>
Ticketgh-kliemFri, 25 Oct 2019 09:54:21 GMTstatus changed
https://trac.sagemath.org/ticket/26922#comment:14
https://trac.sagemath.org/ticket/26922#comment:14
<ul>
<li><strong>status</strong>
changed from <em>needs_work</em> to <em>needs_review</em>
</li>
</ul>
TicketjipilabSun, 27 Oct 2019 15:39:18 GMTstatus changed
https://trac.sagemath.org/ticket/26922#comment:15
https://trac.sagemath.org/ticket/26922#comment:15
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
</ul>
<p>
Looks good to me now
</p>
TicketvbraunMon, 28 Oct 2019 23:51:27 GMTstatus, branch changed; resolution set
https://trac.sagemath.org/ticket/26922#comment:16
https://trac.sagemath.org/ticket/26922#comment:16
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>branch</strong>
changed from <em>public/26922</em> to <em>1c5378cd38b1f65717a2556ae7dc9ca7f756a150</em>
</li>
</ul>
Ticket