Automorphism group of a Polyhedron

[vbraun]

The attached patch allows one to compute the automorphism group of a Polyhedron.

[novoselt]

1. I think that it is OK that a private method _affine_coordinates does not check if the input is valid (i.e. you can pass a point which is not in the affine space), but it is worth noting this feature in its documentation.
2. There are some copy-paste typos in the math part of automorphism_group docstring.
3. assert(False) looks really weird, even though I understand what does it mean. Personally, I'd rather not have that line at all.
4. It would be nice to have an action by permutations on polyhedra. (This can wait for another ticket.)
5. The most important point: the description of the computed group is not entirely clear and I am not sure if you planned the behaviour in the examples below. It seems to me that you need to switch to projective embedding to apply the algorithm. It also seems to me that you need to get rid of the lines first since otherwise the computed group becomes very obscure, since even directions of line generators are not uniquely determined.
6. If the computed group is not the group of symmetries in a clear way, I don't think that the name automorphism_group is justified. It should be either more descriptive or take a mandatory parameter specifying its type, like automorphism_group("restricted") with automorphism_group() raising an exception. I think that at least for bounded polyhedra automorphism_group should mean GL(R,n)-symmetries.

Examples:

sage: points = map(vector, [(1,0), (0,1), (-2,-1)])
sage: p = Polyhedron(vertices=points)
sage: p.automorphism_group().order()
2
sage: p = Polyhedron(vertices=[pt - points[0] for pt in points])
sage: p.automorphism_group().order()
6
sage: p = Polyhedron(vertices=[pt - points[1] for pt in points])
sage: p.automorphism_group().order()
6
sage: p = Polyhedron(vertices=[pt - 2*points[1] for pt in points])
sage: p.automorphism_group().order()
1

I want to get the same number in each case. Personally, I like 2 as the number of GL(Z,2)-symmetries, but as I understand the referenced paper, it should be 6, the number of GL(R,2)-symmetries.

[vbraun]

Thanks for catching the translation bug. The restricted automorphism group should be D_6 (dihedral group with 6 elements) in all cases.

I've renamed the method to restricted_automorphism_group().

I don't think that you can't get rid of lines; The Polyhedron class makes no guarantees that the vertex and ray generators are in a common hypersurface of codimension = number of lines. So the restricted automorphism group will always depend on the presentation of the polyhedron. Once you embrace this fact there is no particular reason to disallow permutations of line generators...

[novoselt]

As a follow up to my comments, how about moving _affine_coordinates inside automorphism group and making it discard line generators in computing pivots. This way linear subspaces will not affect the computed group, which is good, in my opinion. The drawback is that translation from permutations to generators will be a bit more complicated, but the function can take care of it and return the group that still acts on all generators, just keeps line ones fixes.

If I am right and the algorithm will compute GL(R,n) symmetries in the compact case, how about keeping the name automorphism_group but issuing a warning like "you have requested the restricted automorphism group of a non-compact polyhedron. Please read the documentation to make sure that it is the group that you want." for non-compact ones?

Also, as I understand it, it is possible to add any extra stuff to graph labels if one wants to, as you have done to prevent mixing ray and vertex generators. How about adding the possibility to add integral lengths (lattice_polytope.integral_length computes it saving you a couple lines ;-)) to these labels so that the computed group is the group of symmetries with respect to GL(Z, n)? Another option can be adding the square of the "real distance" to compute, I guess, O(n) symmetries.

[novoselt]

You are right, discard the first paragraph above, but the second one becomes even more relevant then ;-)

[novoselt]

"Translations do change the restricted automorphism group." I think you missed NOT.

[vbraun]

Yes, the "not" is important :-)

I guess you want the linear automorphism group as automorphism_group()? There is also the combinatorial automorphism group... Note that the restricted automorphism group equals the linear automorphism group in the case of a full-dimensional compact polyhedron.

I think the (linear) automorphism_group() should return the group elements as Euclidean group elements. But there is no class for that, and tuples (A,b) isn't that intuitive. I don't have time to implement it right now, maybe later. Need to figure out what to do with the continuous group generators, too...

If your polytope is a lattice polytope then the restricted automorphism group is automatically a subgroup of the lattice Euclidean group GL(d,Z) |x Z^d.

[novoselt]

First of all, let me correct myself - when I was talking about GL-symmetries, of course I meant affine-linear ones - they just happen to be the same for reflexive polytopes and I forgot about general situation.

I am more interested in the linear automorphism group and even more in the lattice preserving one, rather than in the combinatorial one. I think the abundance of automorphism groups indicates that maybe we should never have a method called just automorphism_group, but always indicate its kind, as it is done in the new patch.

The current implementation does not preserve the lattice - the example that I have given above is the polytope of WP(1,1,2) and one of the edges has length 2 while others only 1. So there is only one lattice-preserving symmetry. (But that's OK for this ticket.)

Previously raised issues were addressed, but I have some new comments :-)

1. "Note that there are no translations possible since Q contains only a single vertex." is a bit misleading. "Separate" translations are possible iff there is a non-trivial linear subspace. In this case you probably meant that there are no "translation components" attached to matrices, since there is only a single vertex. I think this either should be explained in more detail, or not mentioned at all.
2. I don't understand how the floating point part works. I am not at all an expert on such cases, but I don't understand how calling a function returning x == 0 is any different from direct comparison with 0, which should not be done for floating point numbers anyway. How can it ever return True for anything but exactly zero? It seems to me that you should be comparing x-c with the absolute value of x and c and if the ratio is too small, declare it to be zero. Probably some care should be taken in the case when x or c is actually zero. Fixing some absolute threshold in advance for x-c will lead to incorrect work with "small" polyhedra, but maybe some rough estimate for the diameter can be used. E.g. it is relatively cheap to compute the bounding box of the polyhedra generators and then declare its size divided by 10⁶ or so to be zero. Or one can try to be more clever and choose this tolerance based on the actual "edge colors" before rounding. The current version seems to be too fragile to me.
3. I think you should treat vertices and rays/lines differently when constructing v_list, adding 1 to vertices (which fixed translation issues above) and 0 to others. Otherwise

   sage: p = Polyhedron(vertices=[(1,0), (1,1)], rays=[(1,0)])
   sage: p.restricted_automorphism_group().order()
   1
   

   while it should be 2, I think.

[vbraun]

1. I meant that in the concrete case of the quadrant there are no translations. I'll try to re-word it.

2. The _is_zero(x) method is abs(x)<1e-7 if the Polyhedron.field() is RDF. So that implements the fuzzy zero. Its definitely simple-minded, but then thats what cdd uses internally:

   sage: Polyhedron(vertices=[(0,), (1e-8,)], field=RDF)
   A 0-dimensional polyhedron in RDF^1 defined as the convex hull of 1 vertex.
   

3. Thanks, forgot about that %-)

[novoselt]

Ah, now that makes sense! I guess I just have an issue with _is_zero because I looked at the source code of it for some polyhedron (which happened to be exact) using ?? and saw x == 0 without paying too much attention to the details. The Polyhedron class itself does not have such a method at all. Is really speed-crucial to set it to a lambda-expression instead of having an honest method with if-check for the type of the field each time? (For the purposes of this ticket 2 is resolved.)

[vbraun]

I'm planning to make _is_zero, _is_nonneg and _is_positive into overloaded methods when I split up Polyhedron into different backends. But first I wanted to commit the outstanding patches I have.

I'm not sure that labeling the edges with the number of lattice points restricts to the lattice Euclidean group automatically. Can't you still map a minimal 2-d triangle, say, to one with an interior point (but no lattice point on the edges)? Thats of course not a counterexample, but its not clear to me that that might not happen on faces of higher-dimensional polyhedra...

Updated patch for 1. and 3. is attached. I've also added a combinatorial_automorphism_group() method to compare with.

[vbraun]

Updated patch

[novoselt]

You are right, it is not that easy to make this algorithm work for lattice-preserving automorphisms. Let's save this for later ;-)

The latest patch looks and works fine, positive review!

[jdemeyer]

"Euclidean group" should be "affine group", see #20063.