add .is_self_dual method for polytopes

[LaisRast]

A polytope is self-dual if its face lattice is isomorphic to the face lattice of its dual polytope.

In this tickets I will add is_self_dual method to the Polyhedron class to check (combinatorially) if a polytope is self-dual.

CC: @jplab @kliem

Component: geometry

Keywords: self-dual, polytope, dual, days100

Author: Laith Rastanawi

Branch/Commit: 11041eb

Reviewer: Simon King

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

[LaisRast]

Branch: public/28256

[LaisRast]

Commit: 28bf771

[LaisRast]

New commits:

28bf771

implement is_self_dual for polytopes

[kliem]

comment:2

Please have in mind that the check should also work for non-fulldimensional polyhedra (e.g. Simplex).

Unfortunately, git.sagemath is down at the moment, so I don't see your code.

[kliem]

comment:3

Never mind.

[LaisRast]

comment:4

Replying to @kliem:

Please have in mind that the check should also work for non-fulldimensional polyhedra (e.g. Simplex).

Unfortunately, git.sagemath is down at the moment, so I don't see your code.

It does work for non-full dimensional polytopes. The 3-simplex (a positive example) and the 2nd 4-hypersimplex (a negative example) are already in the doctest.

[kliem]

comment:5

Instead of testing whether the matrix is square, I would check first thing that n_facets equals n_vertices (incidence matrix does take some time).

The approach seems somewhat hacky. How about taking the vertex_facet_graph and checking that it is isomorphic to its reverse (I assume that isomorphism does distinct directions, didn't ckeck).

[jplab]

comment:6

The approach seems somewhat hacky. How about taking the vertex_facet_graph and checking that it is isomorphic to its reverse (I assume that isomorphism does distinct directions, didn't ckeck).

I'd rather qualify this as a clever algorithm. This gets rid of automorphisms of the polytope directly while you will have to deal with them in the oriented graphs. The complexity should be exactly the same and most likely equivalent, because adding the special vertex is equivalent to specify the orientation.

Now, I do not know how isomorphism of graphs is preparsing things, but most likely there is something dealing with bipartite graphs.

[kliem]

comment:7

Replying to @jplab:

The approach seems somewhat hacky. How about taking the vertex_facet_graph and checking that it is isomorphic to its reverse (I assume that isomorphism does distinct directions, didn't ckeck).

I'd rather qualify this as a clever algorithm. This gets rid of automorphisms of the polytope directly while you will have to deal with them in the oriented graphs. The complexity should be exactly the same and most likely equivalent, because adding the special vertex is equivalent to specify the orientation.

Yes, most likely both approaches take almost the same time. I just figured, it's a lot of lines to create a graph that is basically the vertex_facet_graph.

Instead of the current approach, I find some prechecking and

G1 = self.vertex_facet_graph()
G2 = G1.reverse()
return G1.is_isomorphic(G2)

to be more transparent.

Now, I do not know how isomorphism of graphs is preparsing things, but most likely there is something dealing with bipartite graphs.

[LaisRast]

comment:8

Replying to @kliem:

Instead of testing whether the matrix is square, I would check first thing that n_facets equals n_vertices (incidence matrix does take some time).

Agree

The approach seems somewhat hacky. How about taking the vertex_facet_graph and checking that it is isomorphic to its reverse (I assume that isomorphism does distinct directions, didn't ckeck).

It turns out that 'is_isomorphic' does see the directions. So less lines and more readable code.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 28bf771 to 11041eb

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

11041eb

algorithm uses vertex-facet graph and its reversed-direction copy

[kliem]

comment:10

This looks good to me now (remember that I haven't tested this on a computer).

[simon-king-jena]

comment:11

The pyflakes plugin complains. But apparently it only complains about lines that aren't touched by the patch and thus shouldn't be a problem for this ticket.

Tests on a patchbot pass. And the code and docs look good to me. I believe this can constitute a positive review.

[simon-king-jena]

Reviewer: Simon King

[mkoeppe]

comment:12

Shouldn't this method be called is_combinatorially_self_dual to distinguish the tested property from geometric self duality (self polarity)?

[kliem]

comment:13

Replying to @mkoeppe:

Shouldn't this method be called is_combinatorially_self_dual to distinguish the tested property from geometric self duality (self

What do you mean by geometric self duality?

From many ways one could distinguish polyhedra Sage only knows identical and combinatorially equivalent, doesn't it (affinely equivalent and projectively would make sense as well, but I couldn't find this anywhere).

For self duality being exactly self dual doesn't make any sense (once we are at least 2 dimensional). So I would figure the question is a combinatorial one.

In #27689, on the other hand we check of a polyhedron is a prism etc. Here it makes sense to ask for exactly and up to combinatorially equivalence. Maybe one could provide a keyword for cases, where the question has multiple meanings.

[jplab]

comment:14

Replying to @mkoeppe:

Shouldn't this method be called is_combinatorially_self_dual to distinguish the tested property from geometric self duality (self polarity)?

+1

I would vote to simply rename the function to that. It is a combinatorial self duality and should not be confused with the eventual property that self.polar() == self.

[kliem]

comment:15

Replying to @mkoeppe:

Shouldn't this method be called is_combinatorially_self_dual to distinguish the tested property from geometric self duality (self polarity)?

+1

Convinced.

Btw, potentially there is also the method is_combinatorially_dual(self, other). Here, specifying 'combinatorially' is even more important. One should name this ticket's method consistently. (Even though checking for self polarity is probably not worth a method.)

[jplab]

comment:16

Btw, potentially there is also the method is_combinatorially_dual(self, other). Here, specifying 'combinatorially' is even more important. One should name this ticket's method consistently. (Even though checking for self polarity is probably not worth a method.)

A compact polyhedron is always dual to another one using polarity. So this name is incomplete, the self is important there.

[jplab]

comment:17

Replying to @jplab:

Btw, potentially there is also the method is_combinatorially_dual(self, other). Here, specifying 'combinatorially' is even more important. One should name this ticket's method consistently. (Even though checking for self polarity is probably not worth a method.)

A compact polyhedron is always dual to another one using polarity. So this name is incomplete, the self is important there.

Oops, my bad. Didn't see the other.

I would say that this could be done in a different ticket, if someone expresses the need.

[LaisRast]

comment:18

Replying to @mkoeppe:

Shouldn't this method be called is_combinatorially_self_dual to distinguish the tested property from geometric self duality (self polarity)?

I would still vote for leaving it as is_self_dual instead of is_combinatorially_self_dual. I am following the convention that duality is defined for abstract polytopes (face lattices), while polarity is defined for geometric realizations of polytopes (and more generally any subset of an Euclidean space).

For that you can refer to ‎Grünbaum's book (Convex Ptolytopes). In section 3.4, he defined two (geometric realizations of two) polytopes to be dual to each other if there is an inclusion-reversing bijection between their face lattices. And later, in the same section, he defined polarity for geometric polytopes by the well know definition.

On the other hand, for is_self_polar, since The only set A for which A == A.polar() is the unit ball (Theorem 3.1 of [1]), the definition should be more loosely than what is suggested. In [1], this is the definition of self-polarity: A subset A of R^d is self-polar provided there exists some orthogonal transformation U of R^d such that A = U*A.polar(). This is of course can be done in a different ticket.

[1]: Alathea Jensen, Self-polar polytopes https://arxiv.org/pdf/1902.00784.pdf

[kliem]

comment:19

I'm totally confused by now and don't know what to think.

I figured we name everything that can be confused with the combinatorially prefix. Now in #27689, JP voted against that. If find the property self-dual far less ambiguous as being a prism. The name is_combinatorially_self_dual is also hard to find via tab completion.

Overall, I think people with stronger opinions on names than me should decide.

[vbraun]

Changed branch from public/28256 to 11041eb