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.