Implement Lawrence extension for polytopes

[LaisRast]

Adding the following methods to base.py:

• lawrence_extension(self, v): Return the Lawrence extension of self on the point v.
• lawrence_polytope(self): Return the Lawrence polytope of self.
• is_lawrence_polytope(self): Return true if self is a Lawrence polytope.

for definitions, see Section 6.6 of Lectures on Polytopes, Günter M. Ziegler, [Zie2007]

CC: @jplab

Component: geometry

Keywords: polytopes, lawrence extension

Author: Laith Rastanawi

Branch: bc1b9cd

Reviewer: Jonathan Kliem

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

[LaisRast]

Commit: a7849b3

[LaisRast]

Branch: public/27534

[LaisRast]

New commits:

a7849b3

adding Lawrence polytope

[kliem]

comment:3

A few small comments.

1. Single quotes (or whatever the name of those things is) is for latex, double for code-style. There is at least one place (using self), where this is inconsistent.
2. The Lawrence extension of P, what is P? How about The Lawrence extension of a polytope P?
3. A comment I just received myself: "These bullet points for INPUT: do not, by general Sage convention, end in a period/full-stop."
4. It seems to me that the requirement of being full dimensional is not necessary. Instead one can require 0 to be contained, if its not full dimensional. If a polytope P satisfies "ax = 0" for all x in P, then the lawrence extension will just satisfie "(a,0)x = 0". I.e. if all hyperplanes containing P are linear, then the Lawrence extension will be contained in the "same" hyperplanes. I propose something like:

-        if not self.is_full_dimensional():
-            raise NotImplementedError("`self` must be full dimensional")
+        if not self.is_full_dimensional():
+            if not self.contains([0]*self.ambient_dim()):
+                raise NotImplementedError("``self`` must be full-dimensional or contain the origin, try ``self.translation``")

Then, one can add an example that explains how to proceed in case of a not full-dimensional polytope:

sage: P = polytopes.permutahedron(4)
sage: Q = lawrence_polytope(P)
Traceback (most recent call last):
...
NotImplementedError: ``self`` must be full-dimensional or contain the origin, try ``self.translation``
sage: T = P.translation(-vector(P.vertices()[0]))
sage: Q = lawrence_polytope(T)
sage: Q
A 26-dimensional polyhedron in ZZ^28 defined as the convex hull of 47 vertices

Maybe add another example like this to the Lawrence extension (maybe Birkhoff_polytope(3)).

5. I find too many commands in one line hard to read:

-            sage: P = polytopes.cube(); Q = P.lawrence_polytope(); Q.is_lawrence_polytope()
-            True
+            sage: P = polytopes.cube()
+            sage: Q = P.lawrence_polytope()
+            sage: Q.is_lawrence_polytope()
+            True

6. I would use True instead of true.
7. You never use d = self.dim().

[kliem]

Reviewer: Jonathan Kliem

[LaisRast]

comment:4

Thanks for your comments.

The functions need to be rewritten entirely: for instance, my function lawrence_polytope does produce a Lawrence polytope, but not the Lawrence polytope of self according to the usual definitions (there are two different definitions for it).

I will come back to this ticket later and fix everything.

[kliem]

comment:5

One more remark.

is_lawrence_polytope is very slow in cases, where the polytope does not have few vertices. Try checking this for permutahedron(6).

Instead of computing the Gale-transform, one could just grap the information from the facets.

1. Create a list of vertices V.
2. Iterate through all facets F containing exactly n-1 vertices.
3. Remove the vertex not contained in F from V (this vertex "is" the origin in the Gale transform).
4. Iterate through all facets F containing exactly n-2 vertices.
5. Let v_1,v_2 not be in F. If v_1 and v_2 in V, remove them.

If at the end of this V is empty, the Gale diagram is centrally symmetric. If not, then it is not.

[jplab]

comment:6

Replying to @kliem:

One more remark.

is_lawrence_polytope is very slow in cases, where the polytope does not have few vertices. Try checking this for permutahedron(6).

It is hard to have an algorithm that gets faster as the input gets larger!

In spite of that, yes, it might not be optimized, but I would not go into intricate implementation of the function unless there is yet a known use case.

One suggestion:

Perles' example of a non-rational polytope uses lawrence extension to be constructed. It would be nice to add the example to the library of polytopes (either using lawrence extension or just hard-coding the vertices. Or even better, hard-coding the vertices and in the test of the function for the polytope, construct the polytope using lawrence extension and check that it is really combinatorially isomorphic.

[jplab]

comment:7

The Title of the ticket should be more precise about what the ticket provides.

In order to make this ticket more accessible, it would be nice to have related keywords: polytopes and lawrence extension.

[kliem]

comment:8

Replying to @jplab:

Replying to @kliem:

One more remark.

is_lawrence_polytope is very slow in cases, where the polytope does not have few vertices. Try checking this for permutahedron(6).

It is hard to have an algorithm that gets faster as the input gets larger!

Sure. But its also nice to not recalculate something that is already known.

In spite of that, yes, it might not be optimized, but I would not go into intricate implementation of the function unless there is yet a known use case.

Whether a polytope is a Lawrence polytope can simply be decided from the incidence matrix. It is simply the question, whether the vertices V can be labeled v₁,...,v_n,w₁,...,w_2m such that V{v_i} and V{w_2j,w_2j+1} is a facet.

Moreover, the current version has issues. We discovered that gale_transform() is not normalized. At the moment the answer depends on the realization of the polytope. Also, the current code will return True for the bipyramid over a triangle. To my understanding this is not a Lawrence polytope as the Gale diagram is not symmetric with respect to multiplicity.

[kliem]

comment:9

Is a pyramid over a Lawrence polytope a Lawrence polytope? I think the definition should allow for an arbitrary number of points at the origin of the Gale diagram.

polymake's construction of a Lawrence polytope of a polytope with a vertex at the origin will even have an odd number of points. This construction is according to Bernd Sturmfels' definition, I think.

Let V be the vertex matrix of a polytope. The Lawrence polytope will have the following vertices according to Günter Ziegler (Lectures on Polytopes):

            \begin{pmatrix}
             V      &   V    \\
             I_n    &   2*I_n
            \end{pmatrix},

According to Bernd Sturmfels (https://arxiv.org/pdf/math/0202104.pdf):

            \begin{pmatrix}
             V      &   0    \\
             I_n    &   I_n
            \end{pmatrix},

Both construction yield centrally symmetric Gale diagrams, but the second construction might not have an odd number of points, as pointed out.

Only the first construction will "add" for each point x in the Gale diagram a point -x.

Btw, the first construction will not have gale_transform be centrally symmetric, before normalizing. E.g. when applying it for the cube, those are the coordinates of the Gale transform:

sage: P = polytopes.cube()
sage: I_n = matrix.identity(8)
sage: V = P.vertices_matrix()
sage: lambda_V = block_matrix([[V,V],[I_n, 2*I_n]])
sage: Polyhedron(lambda_V.transpose()).gale_transform()

[(2, 0, 0, 0),
 (-1, 0, 0, 0),
 (0, 2, 0, 0),
 (0, -1, 0, 0),
 (0, 0, 2, 0),
 (0, 0, -1, 0),
 (-2, -2, -2, 0),
 (1, 1, 1, 0),
 (0, 0, 0, 2),
 (0, 0, 0, -1),
 (-2, -2, 0, -2),
 (1, 1, 0, 1),
 (-2, 0, -2, -2),
 (1, 0, 1, 1),
 (4, 2, 2, 2),
 (-2, -1, -1, -1)]

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

69cd2c3

improve is_lawrence and fix lawrence_polytope

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from a7849b3 to 69cd2c3

[LaisRast]

comment:11

Replying to @kliem:

One more remark.

is_lawrence_polytope is very slow in cases, where the polytope does not have few vertices. Try checking this for permutahedron(6).

Instead of computing the Gale-transform, one could just grap the information from the facets.

1. Create a list of vertices V.
2. Iterate through all facets F containing exactly n-1 vertices.
3. Remove the vertex not contained in F from V (this vertex "is" the origin in the Gale transform).
4. Iterate through all facets F containing exactly n-2 vertices.
5. Let v_1,v_2 not be in F. If v_1 and v_2 in V, remove them.

If at the end of this V is empty, the Gale diagram is centrally symmetric. If not, then it is not.

This is really helpful and fast. I implemented this in is_lawrence_polytope.

Both construction yield centrally symmetric Gale diagrams, but the second construction might not have an odd number of points, as pointed out.

I decided to only put the construction given by Ziegler. It works in the case where the polytope is not full-dimensional.

[LaisRast]

comment:12

Replying to @jplab:

One suggestion:

Perles' example of a non-rational polytope uses lawrence extension to be constructed. It would be nice to add the example to the library of polytopes (either using lawrence extension or just hard-coding the vertices. Or even better, hard-coding the vertices and in the test of the function for the polytope, construct the polytope using lawrence extension and check that it is really combinatorially isomorphic.

This would be a very nice example. I think this needs its own ticket "adding Perles's example to polytopes library". After that we can add it to the test of the function lawrence_extension .

[LaisRast]

Description changed:

--- 
+++ 
@@ -1,6 +1,6 @@
 Adding the following methods to base.py:
 * `lawrence_extension(self, v)`: 
-  Return the Lawrence extension of `self` on the vertex `v`.
+  Return the Lawrence extension of `self` on the point `v`.
 * `lawrence_polytope(self)`:
   Return the Lawrence polytope of `self`.
 * `is_lawrence_polytope(self)`:

[LaisRast]

Changed keywords from none to polytopes, lawrence extension

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

a975b55

change the name of the variable non_vertices to facet_non_vertices

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 69cd2c3 to a975b55

[LaisRast]

comment:15

Sorry. I know this is on "needs_review". I only changed the name of a variable from non_vertices to facet_non_vertices.

[kliem]

comment:16

+src/sage/geometry/polyhedron/base.py:509: undefined name 'x'
+src/sage/geometry/polyhedron/base.py:4030: 'sage.matrix.constructor.block_matrix' imported but unused

Maybe one could add x = None, before line 503. Then we don't get that pyflakes error anymore.

Delete line 4030.

[kliem]

comment:17

Tiny things:

-        I_n= matrix.identity(n)
-        lambda_V = block_matrix([[V, I_n],[V, 2*I_n]])
+        I_n = matrix.identity(n)
+        lambda_V = block_matrix([[V, I_n], [V, 2*I_n]])

+            For more information, see [BaSt1990]_.
-
+        """
-

I think, there are in general no blank lines after the end of the docstring """.

Also there is a double blank line.

sage: Q = polytopes.regular_polygon(4).pyramid()

Instead of Q, I would maybe use something more descriptive as egyptian or egyptian_py. Then one does not have to read all of polytopes.regular_polygon(4).pyramid() to understand the construction.

This is all that I can come up with.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from a975b55 to e5c6cad

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

e5c6cad

fixing pyflakes undefined variable error/cleaning the code

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from e5c6cad to bc1b9cd

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

bc1b9cd

change variable name from egyption_py to egyption_pyramid

[kliem]

comment:20

Looks fine to me.

[vbraun]

Changed branch from public/27534 to bc1b9cd

[jplab]

comment:22

Here is one things that could have been changed in this ticket:

-     raise NotImplementedError("self must be a polytope")
+     raise NotImplementedError("Only polytopes (compact polyhedra) are allowed.")

like in bounding_box or

-     raise NotImplementedError("self must be a polytope")
+     raise NotImplementedError("The polytope has to be compact.")

like in barycentric_subdivision. Usually self is replaced by something more informative about the actual object and making the requirement precise (in this case 'compactness'). Since polytope is not a universally defined word, mentioning compactness makes thing completely unambiguous.

This could be changed some other time when practical.

[jplab]

Changed commit from bc1b9cd to none