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]

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?

[kliem]

comment:6

Replying to @jplab:

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.

[kliem]

comment:7

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

[kliem]

Changed commit from e86ea8b to 20ad51f

[kliem]

Changed branch from public/28506 to public/28506-bis

[jplab]

comment:8

Replying to @kliem:

Replying to @jplab:

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.

[sagetrac-git]

Changed commit from 20ad51f to ce30313

[sagetrac-git]

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

ce30313

added output to doctest

[kliem]

comment:10

Replying to @jplab:

Replying to @kliem:

Replying to @jplab:

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.

[sagetrac-git]

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

7080349

fixed minkowski decomposition

[sagetrac-git]

Changed commit from ce30313 to 7080349

[jplab]

comment:12

Replying to @kliem:

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

True.

[jplab]

Reviewer: Jean-Philippe Labbé

[jplab]

comment:13

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

[sagetrac-git]

Changed commit from 7080349 to b1c8187

[sagetrac-git]

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

b1c8187

small changes in documentation

[jplab]

comment:15

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

[kliem]

Changed commit from b1c8187 to 47514e7

[kliem]

Changed branch from public/28506-bis to public/28506-reb2

[kliem]

New commits:

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

[sagetrac-git]

Changed commit from 47514e7 to 6756d8a

[sagetrac-git]

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

6756d8a

fixed trac 28506

[jplab]

comment:18

LGTM

[vbraun]

Changed branch from public/28506-reb2 to 6756d8a