Opened 3 years ago

Closed 3 years ago

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

Reported by: Owned by: jipilab major sage-9.0 geometry polytopes gh-LaisRast, gh-kliem Jonathan Kliem Jean-Philippe Labbé N/A 6756d8a 6756d8a870674020479fcceef4a8d450fb87ea4f

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.

### comment:1 Changed 3 years ago by 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?

### comment:2 Changed 3 years ago by 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)
```

### comment:3 Changed 3 years ago by gh-kliem

• Authors set to Jonathan Kliem
• Branch set to public/28506
• Commit set to e86ea8b2bbd1fdd017aa22a9318d3f08c3c3cfe6
• Description modified (diff)
• Status changed from new to needs_review
• Summary changed from Direct sum of polyhedron is broken to Direct sum of polyhedron is broken, so is minkowski difference and face truncation

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`

### comment:4 Changed 3 years ago by 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`

### comment:5 follow-up: ↓ 6 Changed 3 years ago by 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?

### comment:6 in reply to: ↑ 5 ; follow-up: ↓ 8 Changed 3 years ago by gh-kliem

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.

### comment:7 Changed 3 years ago by gh-kliem

• Branch changed from public/28506 to public/28506-bis
• Commit changed from e86ea8b2bbd1fdd017aa22a9318d3f08c3c3cfe6 to 20ad51f952b05e8ec8888e54501365f72ca527a4

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`

### comment:8 in reply to: ↑ 6 ; follow-up: ↓ 10 Changed 3 years ago by 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.

### comment:9 Changed 3 years ago by git

• Commit changed from 20ad51f952b05e8ec8888e54501365f72ca527a4 to ce30313f34389112c87c250181e16c3c9f211917

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

 ​ce30313 `added output to doctest`

### comment:10 in reply to: ↑ 8 ; follow-up: ↓ 12 Changed 3 years ago by gh-kliem

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.

### comment:11 Changed 3 years ago by git

• Commit changed from ce30313f34389112c87c250181e16c3c9f211917 to 7080349f1d4255d8211657689181cc13b9096977

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

 ​7080349 `fixed minkowski decomposition`

### comment:12 in reply to: ↑ 10 Changed 3 years ago by jipilab

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

True.

### comment:13 Changed 3 years ago by jipilab

• Milestone changed from sage-pending to sage-9.0
• Reviewers set to Jean-Philippe Labbé

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

### comment:14 Changed 3 years ago by git

• Commit changed from 7080349f1d4255d8211657689181cc13b9096977 to b1c81876e5c2a7b765df8984320ca1d3514764b6

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

 ​b1c8187 `small changes in documentation`

### comment:15 Changed 3 years ago by jipilab

• Status changed from needs_review to needs_work

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

### comment:16 Changed 3 years ago by gh-kliem

• Branch changed from public/28506-bis to public/28506-reb2
• Commit changed from b1c81876e5c2a7b765df8984320ca1d3514764b6 to 47514e7d31f9d22227ea16c67b18fb4330f134f4
• Status changed from needs_work to needs_review

New commits:

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

### comment:17 Changed 3 years ago by git

• Commit changed from 47514e7d31f9d22227ea16c67b18fb4330f134f4 to 6756d8a870674020479fcceef4a8d450fb87ea4f

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

 ​6756d8a `fixed trac 28506`

### comment:18 Changed 3 years ago by jipilab

• Status changed from needs_review to positive_review

LGTM

### comment:19 Changed 3 years ago by vbraun

• Branch changed from public/28506-reb2 to 6756d8a870674020479fcceef4a8d450fb87ea4f
• Resolution set to fixed
• Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.