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 an $(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 $S$ being an affine basis of $V$.

Let $P$ be the convex hull of the points of $S \cup 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 \cup GC$.

Claim: $G$ is the group of symmetries of $P$.

If $g$ is in $G$, $g$ is a symmetry of $GC$ 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 \in 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 $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)}+\ldots+nA_{s(n)}/(1+\ldots+n)=(A_{g(1)}+2A_{g(2)}+\ldots+nA_{g(n)})/(1+\ldots+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)/(1+...+n)$ 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 minimum closed ball containing $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 the 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\cdot m(n\cdot 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\cdot 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\cdot e$.

Now let $G$ act on $F$ and let $Q$ be the union of the $m$ copies obtained. $Q$ is a union of $n\cdot m$ drawings. Points of different drawings are separated by a distance larger than $2\cdot e$. Hence the drawings can be identified as the maximal subsets of $Q$ having diameter less than $2\cdot 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 \leq i \leq 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 $G \times A$ 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\neq Tb$ must do (since $h$ is injective). Such $T'$ may be found very near $T$, provided $\dim V>2$. The proof doesn't work for $n=1$ or $n=2$, but these are just the easy cases.

6more comments