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

[jipilab]

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.

[gh-kliem]

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?

[gh-kliem]

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)

[gh-kliem]

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

[gh-kliem]

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

[jipilab]

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?

[gh-kliem]

Replying to jipilab:

One comment:

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

Ok. Will do it.

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

sage: s2 = polytopes.simplex(2)
sage: s2.base_ring()
Integer Ring
sage: s = polytopes.simplex(2)
sage: s.base_ring()
Integer Ring
sage: s = s.change_ring(QQ)
sage: t = s.direct_sum(s)
sage: t.vertices()
(A vertex at (0, 0, 1, 0, 0, 0),
 A vertex at (0, 1, 0, 0, 0, 0),
 A vertex at (1, 0, 0, 0, 0, 0),
 A vertex at (1/3, 1/3, 1/3, -1/3, -1/3, 2/3),
 A vertex at (1/3, 1/3, 1/3, -1/3, 2/3, -1/3),
 A vertex at (1/3, 1/3, 1/3, 2/3, -1/3, -1/3))

Does this answer your question? As mentioned, direct sum (as well as intersection, minkowski difference and face truncation) are only defined for polytopes/polyhedra over a field.

In the same way, that sage: 6/2 returns a rational, I think those operations should return a polytope with base ring constructed by first coercing and then taking the fraction field.

[gh-kliem]

As mentioned. I think this approach is actually more suitable and at some point, we should change intersection accordingly.

---

New commits:

​20ad51f

fixed 28506 by always taking fraction field

[jipilab]

Replying to gh-kliem:

Replying to jipilab:

One comment:

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

Ok. Will do it.

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

sage: s2 = polytopes.simplex(2)
sage: s2.base_ring()
Integer Ring
sage: s = polytopes.simplex(2)
sage: s.base_ring()
Integer Ring
sage: s = s.change_ring(QQ)
sage: t = s.direct_sum(s)
sage: t.vertices()
(A vertex at (0, 0, 1, 0, 0, 0),
 A vertex at (0, 1, 0, 0, 0, 0),
 A vertex at (1, 0, 0, 0, 0, 0),
 A vertex at (1/3, 1/3, 1/3, -1/3, -1/3, 2/3),
 A vertex at (1/3, 1/3, 1/3, -1/3, 2/3, -1/3),
 A vertex at (1/3, 1/3, 1/3, 2/3, -1/3, -1/3))

Does this answer your question? As mentioned, direct sum (as well as intersection, minkowski difference and face truncation) are only defined for polytopes/polyhedra over a field.

Yes, this examples clarifies it. It should probably go right among the first examples to illustrate the construction.

I was extremely confused, but now it makes sense. The problem is when we translate one of them to have center be the origin...

In the same way, that sage: 6/2 returns a rational, I think those operations should return a polytope with base ring constructed by first coercing and then taking the fraction field.

Yes, sounds reasonable.

[git]

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

​ce30313

added output to doctest

[gh-kliem]

Replying to jipilab:

Replying to gh-kliem:

Replying to jipilab:

One comment:

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

Ok. Will do it.

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

sage: s2 = polytopes.simplex(2)
sage: s2.base_ring()
Integer Ring
sage: s = polytopes.simplex(2)
sage: s.base_ring()
Integer Ring
sage: s = s.change_ring(QQ)
sage: t = s.direct_sum(s)
sage: t.vertices()
(A vertex at (0, 0, 1, 0, 0, 0),
 A vertex at (0, 1, 0, 0, 0, 0),
 A vertex at (1, 0, 0, 0, 0, 0),
 A vertex at (1/3, 1/3, 1/3, -1/3, -1/3, 2/3),
 A vertex at (1/3, 1/3, 1/3, -1/3, 2/3, -1/3),
 A vertex at (1/3, 1/3, 1/3, 2/3, -1/3, -1/3))

Does this answer your question? As mentioned, direct sum (as well as intersection, minkowski difference and face truncation) are only defined for polytopes/polyhedra over a field.

Yes, this examples clarifies it. It should probably go right among the first examples to illustrate the construction.

I could of course do it. But doesn't the existing example already illustrate this?

I was extremely confused, but now it makes sense. The problem is when we translate one of them to have center be the origin...

In the same way, that sage: 6/2 returns a rational, I think those operations should return a polytope with base ring constructed by first coercing and then taking the fraction field.

Yes, sounds reasonable.

[git]

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

​7080349

fixed minkowski decomposition

[jipilab]

Replying to gh-kliem:

I could of course do it. But doesn't the existing example already illustrate this?

True.

[jipilab]

The "some tests::" might be superfluous. I would remove it.

[git]

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

​b1c8187

small changes in documentation

[jipilab]

Some tests are failing in the thematic tutorial. See patchbots.

[gh-kliem]

New commits:

​fc62aa6	fixed trac 28506
​fa4ddc1	fixed failing doctest in documentation
​47514e7	Fixed trac 28506

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

​6756d8a

fixed trac 28506

[jipilab]

LGTM