Is every finite group a group of "symmetries"?

Question

I was trying to explain finite groups to a non-mathematician, and was falling back on the "they're like symmetries of polyhedra" line. Which made me realize that I didn't know if this was actually true:

Does there exist, for every finite group G, a positive integer n and a convex subset S of R^n such that G is isomorphic to the group of isometries of R^n preserving S?

If the answer is yes (or for those groups for which the answer is yes), is there a simple construction for S?

I feel like this should have an obvious answer, that my sketchy knowledge of representations is not allowing me to see.

Answer 1

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+\cdots+nA_n)/(1+2+\cdots+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)}+\cdots+nA_{s(n)}/(1+\cdots+n)=(A_{g(1)}+2A_{g(2)}+\cdots+nA_{g(n)})/(1+\cdots+n).$

For each $i \in \{1,...,n\}$ the coefficient that multiplyes $A_i$ is $s^{-1}(i)/(1+\cdots+n)$ in the left hand side and $g^{-1}(i)/(1+\cdots+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.

Answer 2

Here's a sketch of an ugly argument. First construct an undirected graph whose automorphism group is G. You can do this by starting with a vertex v_g for each element g of G and gluing in a path of length n(g^-1h) from v_g to v_h with an extra leaf attached to the internal vertex of this path nearest to v_g. Here n is an injective function from G to {3, 4, 5, ...}. (This construction might need |G| >= 4 or so, but clearly we can handle the smaller cases by hand.)

Now make the vertices of this graph into a metric space where the distance between two nonadjacent vertices is 1 and the distance between two adjacent vertices is 1-ε. Now we need to embed this metric space into some R^N. You can either appeal to some results about embedding finite metric spaces into R^N, or convince yourself that the map (x1, ..., xn) in (R^N)^n |-> (d(xi, xj)^2)_{1 <= i < j <= n} is a submersion near the regular simplex of edge length 1.

Answer 3

I think I have a solution that will work, but I'm not 100% certain.

Let V be a faithful representation of G (so the map G→GL(V) has no kernel). Pick a "sufficiently generic" point of V and consider the convex hull of the orbit of that point. G includes into the group of symmetries of this polytope, but it could have additional symmetries. For example, Z/4 acts on the plane by rotation. If you take any point, its orbit is a square, which has additional symmetries (reflections).

You can fix this by modifying the above construction as follows. Replace the point by a set of points S which is totally asymmetric (has no symmetries at all in GL(V)). Think of this set S as being a small cluster of points very far from the origin, so all the images of S under the action of G are easily distinguishable. Since S was totally asymmetric, the only symmetries of the union of these images should be elements of G.

If you're careful with how you chose your S, you shouldn't "lose too much asymmetry" when you take the convex hull of the union of the images of S.

Answer 4

An old paper of mine (Proc AMS 62 No 1 (1977) pp28-30) shows that if $G$ is a finite subgroup of $GL(V)$, where $V$ is a finite dimensional vector space over an infinite field, then there exists a subset $X$ of $V$ such that $G$ is the full setwise stabilizer of $X$. Furthermore, if $G$ is absolutely irreducible in its action on $V$, it is possible to take $X$ to be a single $G$-orbit. A key fact used in the proof is that $V$ cannot be the union of finitely many proper subspaces.

Answer 5

Here is an explicit (and short) version of Anton Geraschenko's answer.

Let $G$ act on a regular $(n-1)$-dimensional simplex $\Delta$ permuting its vertices as in Cayley's theorem ($n$ in the order of $G$). Let $p_0,\dots,p_{n-1}$ be the vertices of this simplex.

Cut off a small simplex $\Delta'$ (located near $p_0$) constructed as follows: for $k=1,\dots,n-1$, let $p'_k$ be the point on the edge $[p_0p_k]$ at the distance $k\varepsilon$ from $p_0$, where $\varepsilon=1/100n$. The simplex $\Delta'$ is the convex hull of $p_0,p'_1,\dots,p'_{n-1}$, you cut is off from $\Delta$ by the hyperplane through points $p'_1,\dots,p'_{n-1}$. Also, cut off all images of $\Delta'$ under the action of $G$.

The resulting polytope does not have any extra symmetries, so $G$ is its group of self-isometries.

Answer 6

Suppose one has a convex 4-gon in the plane. What symmetry groups can it have?

The graph of this convex 4-gon is a 4-cycle so as a graph its automorphism group is the dihedral group which I will denote D(4) which has 8 elements. Now there is a convex 2-dimensional polygon which has this as its group, namely a square. However, The group D(4) has a cyclic subgroup of order 4, yet there is NO convex 4-gon which has the cyclic group of order 4 as its set of isometries. There is a rectangle with unequal sides which has a group of order 4 as its symmetry group but this is the Klein group, not the cyclic group, of order 4.

For 3-dimensions, a similar thing can happen. It is known that the vertex-edge graph of any 3-dimensional convex polytope is a planar and 3-connected graph and the converse holds. This is Steinitz's Theorem. Suppose H is such a graph (e.g. planar and 3-connected) and the (full) automorphism group of H is G. There is a beautiful theorem of Peter Mani's which states H can be realized in 3-space by a metric polytope P which has group G as its group of isometries. However, it does not follow that for any subgroup I of G that there is a 3-dimensional convex polyhedron whose group of isometries is I. In fact, for the group with 48 elements which is the isometry group of the graph of the 3-cube there is a subgroup of order 24, the rotation group, but there is no 3-dimensional convex polyhedron which is combinatorially a 3-cube which has 24 isometries.

Here is the reference for Mani's paper:

P. Mani, Automorphismen von polyedrischen Graphen, Math. Ann. 192 (1971) 279–303.

This is a generalization of this theorem to complexes, as mentioned in this paper:

http://arxiv.org/abs/math/0310165

If you restrict your attention to graphs rather than polytopes there is a nice theorem of Roberto Frucht.

For any finite group H, there is a graph G(H) such that the automorphism group of G(H) is H.

There are extensions of Frucht's Theorem including to 3-valent graphs. If there was an extension of Frucht's theorem to planar 3-connected graphs than via Steinitz's Theorem the original question would be answered. I am not sure if this has been done or not.

A survey paper (about graphs with specified automorphism groups and related matters) of Babai's is available:

www.cs.uchicago.edu/files/tr_authentic/TR-94-10.ps

Answer 7

I consulted Laszlo Babai (University of Chicago) who has written extensively on the subject of automorphism groups, on the following issue:

Given any group H is there always a planar 3-connected graph G (hence a 3-polytopal graph by Steinitz's Theorem) such that the automorphism group of G is H? (By a theorem of Peter Mani's if such a graph G existed for H then there would be a realization of the graph G as the vertex-edge graph of a 3-polytope P such that the isometries of P would be H.)

Professor Babai informed me that there is no universal theorem here. He offered the 8 element quaternion group as an example of a group H which does not arise as the automorphism group of a planar 3-connected graph.

Here are references to some of his papers that treat aspects of this and related issues:

L. Babai, and W. Imrich: On groups of polyhedral graphs, Discrete Math. 5 (1973), 101-103.

L. Babai: Automorphism groups of planar graphs I, Discrete Math. 2 (1972), 285-307.

L. Babai: Automorphism groups of planar graphs II, in, Infinite and finite sets (Proc. Conf. Keszthely, Hungary, 1973, A. Hajnal et al eds.) Bolyai - North-Holland (1975), 29-84.

L. Babai: Groups of graphs on given surfaces, Acta Math. Acad. Sci. Hung. 24 (1973), 215-221.

L. Babai: Automorphism groups of graphs and edge-contraction, Discrete Math. 8 (1974), 13-20.

L. Babai: Vertex-transitive graphs and vertex-transitive maps, J. Graph Theory 15 (1991), 587--627.

It also turns out there is a paper by: Jurgen Bokowski, G. Ewald, and P. Kleinschmidt, On the combinatorial and affine automorphisms of polytopes, Israel J. of Math., 47 (1984) 123-130 with the following abstract, which may be of interest to those thinking about this circle of ideas:

Abstract We disprove the longstanding conjecture that every combinatorial automorphism of the boundary complex of a convex polytope in euclidean space E d can be realized by an affine transformation of Ed.

Answer 8

Here is my take on a short proof.

Let' start like some other answers: fix some orthogonal matrix group $\Gamma\subset\mathrm O(\Bbb R^d)$ isomorphic to $G$ and try to choose a set of points $\smash{X=\{x_1,...,x_r\}\subseteq\Bbb S^{d-1}}$ on the unit sphere whose orbit has the desired symmetries: $\mathrm{Aut}(\Gamma X)=\Gamma$. Then its convex hull is the desired convex set. But how do we know that such a set of points $X$ exists?

Try this: choose $X\subset\Bbb S^{d-1}$ so that $\mathrm{Aut}(\Gamma X)$ is as small as possible. If there is a $g\in \mathrm{Aut}(\Gamma X)\setminus \Gamma$, then we can find an $x\in \Bbb S^{d-1}$ not in $\ker(g-\bar g)$ for any $\bar g\in \Gamma$ (this is possible by dimension considerations). Set $\bar X:=X\cup \{x\}$ and observe that $g\not\in \mathrm{Aut}(\Gamma\bar X)\subsetneq\mathrm{Aut}(\Gamma X)$ in contradiction to the assumption of minimality. Thus we must have had $\mathrm{Aut}(\Gamma X)\setminus\Gamma=\varnothing$ as desired.

Answer 9

This has troubled my sleep for a long time, and I keep wanting to offer a variant of the following answer: Consider the regular representation $\mathbb R G$ of $G$. For any 'natural' choice of inner product on $\mathbb R G$ (such as one making $G$ an orthonormal basis), the action is by isometries, and preserves some obvious convex bodies (such as the simplex spanned by $G$); but, for most such choices, $G$ is obviously far smaller than the full group of symmetries.

Inner products on $\mathbb R G$ are the same as $G$-square matrices satisfying certain conditions; the one that I suggested corresponds to the identity matrix. I tried to come up with an argument that showed that a small but suitably 'deranged' perturbation of that matrix would give us a pairing such that $G$ still acted by isometries, but any other symmetries of the basic simplex were killed off. Well --no luck so far, and it's not much different from Anton's suggestion; but, as a representation theorist, I just couldn't resist the appeal of using an 'obvious' vector space (albeit with a non-obvious Euclidean structure).

Answer 10

From Wikipedia: "In group theory, Cayley's theorem, named in honor of Arthur Cayley, states that every group G is isomorphic to a subgroup of the symmetric group on G. This can be understood as an example of the group action of G on the elements of G."

So if I well understand, every finite group G is a subgroup of symmetric group G, so if You have symmetric group, and can visualise it, probably by some kind of graph, then there the same picture is useful for visualising subgroup. There is no matter which geometric object is under this picture... So the my answer ( of course partial ) is: try to visualise symmetric group only.

---

Some remarks: 1: Your question should state that You are interested in symmetries which are exactly from group G, and not any more. If You allow convex bodies for which given group G is only a part of its group of symmetries, the answer would be YES, and sphere gives You model for all finite groups which is trivial.

2:You should do not allow to "degenerate symmetries" that is for example to count some axis symmetries twice ( for example triangle may have 3 axis of symmetry - which may represent for some group elements of order 2, and You do not want them to represent 6 symmetries of order 2 paired together)

Then: I have read the whole question, and I think that the answer is - in general case - NO, asuming You consider 1,2 as requirements, and YES if You from 1,2 above from the list of requirements. Full symmetric group is the case where is not possible to point such convex subset, because if something has such big symmetry it has also have more symmetries inside, but I cannot show any proof for that statement.

However it would be very interesting to see what numbers n of needed R^n are in the series when You order finite groups by their size....