Direct sum of polyhedron is broken, so is minkowski difference and face truncation

[jplab]

The following returns a TypeError:

sage: s2 = polytopes.simplex(2)
sage: s3 = polytopes.simplex(3)
sage: t = s2.direct_sum(s3)

H-Polyhedra might have non-integral vertices and it is hard to tell from the H-Representation, whether this this is the case.

We fix direct_sum, minkowski_difference and face_truncation to try the quotient ring, if the given base ring does not work.

CC: @LaisRast @kliem

Component: geometry

Keywords: polytopes

Author: Jonathan Kliem

Branch/Commit: 6756d8a

Reviewer: Jean-Philippe Labbé

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

[kliem]

comment:1

I'll fix it. Should be fast.

As far as I know, it's difficult to determine, whether this operation can be done with ring ZZ. So there are basically two options:

• try the operation with coerced base rings and go to quotient field, if it fails (this is how intersection handles it)
• just go to field in all cases.

What do you think is better?

[kliem]

comment:2

minkowski_difference fails for the same reason. This fails, as coercing base rings may not suffice:

sage: Q = Polyhedron([[1,0],[0,1]])
sage: S = Polyhedron([[0,0],[1,2]])
sage: S.minkowski_difference(Q)

Same for face_truncation (also there is no example of linear coefficients in the docstring):

sage: P = polytopes.permutahedron(3)
sage: P.face_truncation(P.faces(0)[0], linear_coefficients=[0,1,2], cut_frac=1)

[kliem]

comment:3

I did both approaches. The approach that always takes the fraction is pushed into public/28506-bis.

I guess there are pros and cons of both methods. I think most important cons are:

• try ... except might take more much more time (I assume it can theoretically compute almost everything)
• try ... except is a bad approach, if there was ever a thing as a lazy polyhedron (but then again, its a bad idea to set up a lazy Polyhedron in ZZ from inequalities and don't check, whether this works)
• always taking fraction field changes the behavior of the methods (and it looks awful for Minkowski decomposition)

---

New commits:

fa1a517	added doctests that 28506 is fixed
e86ea8b	fixed 28506 by trying fraction field at failure

[kliem]

Author: Jonathan Kliem

[kliem]

Description changed:

--- 
+++ 
@@ -6,3 +6,6 @@
 sage: t = s2.direct_sum(s3)
 ```
 
+H-Polyhedra might have non-integral vertices and it is hard to tell from the H-Representation, whether this this is the case.
+
+We fix `direct_sum`, `minkowski_difference` and `face_truncation` to try the quotient ring, if the given base ring does not work.

[kliem]

Branch: public/28506

[kliem]

Commit: e86ea8b

[kliem]

comment:4

Btw, the constructor sets up all H-Polyhedra with base ring as field unless one specifies a specific base ring.

Actually, I think this is the better approach, as construction should be done with a parent, for which they are well-defined, e.g.:

• intersection of Polyhedra in ZZ^2 are only well-defined in QQ^2, it's strange if some constructions have parent ZZ^2, while others have parent QQ^2
• face_truncation for Polyhedra over ZZ is only well-defined if we lift them up to QQ

[jplab]

comment:5

One comment:

The tests should actually return something, so I would remove t = and let the output get printed.

I am still a bit puzzled as to why it did not work for direct sum. What was going on there?