The permutohedron may have additional symmetries. For example, the order 3 permutohedron {(1,2,3),(1,3,2),(2,1,3),(3,1,2),(3,2,1)} is a regular hexagon contained in the plane x+y+z=6, which has more than 6 symmetries.
I think we can solve it as follows:
Let G be a group with finite order n thought via Cayley's representation as a subgroup of S_n.
Let S={A_1,...,A_n} be the set of vertices of a regular simplex centered at the origin in a (n-1)-dimensional real inner product space V. Let r be the distance between the origin and A_1. The set of vertices S is an affine basis for V.
First unproven claim: If a closed ball that has radius r contains S, then it is centered at the origin. Let B be this ball.
The group of isometries that fix S hence contains only isometries that fix the origin and permute the vertices, which can be identified with S_n in the obvious way. The same is true if we replace S by its convex hull.
Now G can be thought of as a group containing some of the symmetries of S.
Let C=k(A_1+2A_2+3A_3+...+nA_n)/(1+2+...+n), with k a positive real that makes the distance between C and the origin a number r' slightly smaller than r.
Let GC={g(C) / g in G}. It has n distinct points, as a consequence of being S an affine basis of V.
Let P be the convex hull of the points of S union GC.
Remark: A closed ball of radius r contains P iff it is B. The intersection of the border of B and P is S.
Second unproven claim: The extremal points of P are the elements of S union GC.
Claim: G is the group of symmetries of P.
If g is in G, g is a symmetry of GB and of S, and it is therefore a symmetry of P.
If T is a symmetry of P, then T(P)=P, and in particular, T(P) is contained in B, and hence T(0)=0 (i.e. T is also a symmetry of B). T must also fix the intersection of P and the border of B, so T permutes the points of S, and it can be thought of as an element s of S_n sending A_i to A_s(i). And since T fixes the set of extremal points of P, T also permutes GC. Let's see that s is in G.
Since T(C) must be an element of g(C) of GC, we have T(C)=g(C). But since T is linear, T(C/k)=g(C/k). Expanding,
(A_s(1)+2A_s(2)+...+nA_s(n)/(1+...+n)=(A_g(1)+2A_g(2)+...+nA_g(n))/(1+...+n).
For each i in {1,...,n} the coefficient that multiplyes A_i is s⁻1(i)/(1+...+n) in the left hand side and g⁻1(i) in the right hand side. It follows that s=g.
I think that, taking n into account, the ratio r'/r can be set to substantiate the second unproven claim. The first unproven claim may be a consequence of Jung's inequality.
EDIT: With the previous argument, we can represent a finite group of order n as the group of linear isometries of a certain polytope in an n-1 dimensional real inner product space.
Now, if a finite group G of linear isometries of an (n-1)-dimensional inner product space V is given, can we define a polytope that has G as its group of symmetries? Yes. I'll give a somehow informal proof.
Let G={g_1,...,g_m}. Let A={a_1,...,a_n} be the set of vertices of a regular n-simplex centered at the origin of V. Let S be the sphere centered at the origin that contains A, and let C be the closed ball. Notice that C is the only minimun closed ball contaiing A.
(Remark: The set A need not be a regular simplex. It may be any finite subset of S that intersects all the possible hemispheres of S. C will then still be only minimum closed ball
containing it.)
Remark: An isometry of V is linear iff it fixes the origin.
Before proceeding, we need to be sure that the m copies of A obtained by making G act on it are disjoint. If that is not the case, our set A is useless but we can find a linear isometry T such that TA does de job. We consider the set M of all linear isometries with the usual operator metric, and look into it for an isometry T such that for all (g,a) and (h,b) distinct elements of GxA the equation g(Ta)=h(Tb) does not hold. Because each of the n*m(n*m-1) equations spoils a closed subset of M with empty interior(*), most of the choices of T will do.
Let K={ga/g in G, a in A}. We know that it has n*m points, which are contained in the sphere S. Now let e be a distance that is smaller than a quarter of any of the distances between different points of K. Now, around each vertex a=a_i of A make a drawing D_i. The drawing consists of a finite set of points of the sphere S, located near a (at a distance smaller than e). One of the points must be a itself, and the others (if any) should be apart from a and very near each other, so that a can be easily distinguished. Furthermore, for i=1 the drawing D_i must have no symmetries, i.e, there must be no linear isometries fixing D_1 other than the identity. For other values of i, we set D_i={a_i}. The union F of all the drawings contains A, but has no symmetries. Notice that each drawing has diameter less than 2*e,
Now let G act on F and let Q be the union of the m copies obtained. Q is a union of n*m drawings. Points of different drawings are separated by a distance larger than 2*e. Hence the drawings can be identified as the maximal subsets of Q having diameter less than 2*e. Also, the ball C can be identified as the only sphere with radius r containing Q. S can be identified as the border of C.
Let's prove that the set of symmetries of Q is G. It is obvious that each element of G is a symmetry. Let T be an isometry that fixes Q. It must fix S, so it must be linear. Also, it must permute the drawings. It must therefore send D_1 to some gD_i with g in G and 1<=i<=n. But i must be 1, because for other values of i, gD_i is a singleton. So we have TD_1=gD_1. Since D_1 has no nontrivial symmetries, T=g.
We have constructed a finite set Q with group of symmetries G. Q is not a polytope, but its convex hull is a polytope, and Q is the set of its extremal points.
(*) To show that for any (g,a) and (h,b) distinct elements of GxA the set of isometries T satisfying equation g(Ta)=h(Tb) has empty interior, we notice that if an isometry T satisfies the equation, any isometry T' with T'a=Ta and T'b=/=Tb must do (since h is injective). Such T' may be found very near T, provided dimV>2. The proof doesn't work for n=1 or 2, but these are just the easy cases.
No comments:
Post a Comment