# Is every finite group a group of “symmetries”?

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.

-
There's a lot of variants of your question. Every finite group can also be realized as the group of isometries of some compact hyperbolic surface. Similarly, it can be realized as the group of symmetries of a hyperbolic 3-manifold. – Ryan Budney Feb 16 '10 at 8:10
Every group is the automorphism group of some graph. – Kevin O'Bryant Feb 16 '10 at 19:05
Every group is the automorphism group of some topology. – Kevin O'Bryant Feb 16 '10 at 19:05
@RB and KO'B: I was aware of the variants you mention, and there are certainly more one can cook up. What I wanted to say to the non-mathematician is the most literal generalization of symmetry in the colloquial sense: that every finite group is the isometry group of some polytope in R^n. – Andrew McIntyre Feb 16 '10 at 20:04
@RB: Do you have a reference for every finite group being the automorphism group of a Riemann surface? I seem to recall hearing this as folklore, but it occurs to me that I have no idea how it is proved. That suggests another question: is there an "equivariant" embedding theorem for manifolds with symmetries? I.e. if a hyperbolic surface X has nontrivial automorphisms, is there an embedding of X in R^n for some n, such that every automorphism of X is induced by an isometry of R^n preserving the image of X? – Andrew McIntyre Feb 16 '10 at 20:12

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.

-
This is a really nice argument. I like that it is effective: given an explicit description of a group, one could easily find the vertices of the polyhedron P. It's even almost visualizable. – Andrew McIntyre Feb 22 '10 at 15:39
This construction shows that a finite group G of order n can be realized as exactly the isometries of a convex polyhedron in R^n. Now, suppose m is the least positive integer such that G has a faithful representation in GL(m,R). Typically m is much smaller than n. I am curious whether it is possible to use your strategy to produce a polyhedron in R^m, whose symmetries are exactly the elements of G, considered as elements in GL(m,R). If that could be done, it would be a solution to the original problem with minimal dimension. – Andrew McIntyre Feb 22 '10 at 15:50

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 vg for each element g of G and gluing in a path of length n(g-1h) from vg to vh with an extra leaf attached to the internal vertex of this path nearest to vg. 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.

-
Thanks, this is ugly but also neat! I am convinced now. I am still wondering whether there is a "nice" construction. I don't know how to define "nice", but I am getting the feeling that, for any reasonable candidate for "nice", one could construct counterexamples (I suspect that any construction that is too "simple" should end up with accidental symmetries, as noted by A.G. below). – Andrew McIntyre Oct 18 '09 at 16:05

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.

-
Thanks! I was thinking basically along those lines, but I got stuck on trying to prove the "shouldn't lose too much asymmetry" step. I also couldn't convince myself that every rep in GL(V) would reduce to the orthogonal group (this is probably easy, but I couldn't see it). – Andrew McIntyre Oct 18 '09 at 15:58
That argument's a standard trick: if you start with an inner product (u, v), define a new one by (u, v)' = 1/|G| sum (gu, gv). This inner product is G-invariant so the representation is orthogonal with respect to it. – Qiaochu Yuan Oct 18 '09 at 21:30
You know, I use that trick at least once a week in the context of Poincaré series. I don't know why I didn't see it here. Thanks! – Andrew McIntyre Oct 19 '09 at 2:45

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.

-

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.

-

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

-
Neat! Do you know if there are analogous results in higher dimensions? A refinement of the original question, (assuming that previous commenters and I are all correct, and the answer is yes), would be to find lower and upper bounds for the integer n, as a function of the order of the group (or some other data from the group). This would be sort of analogous to embedding theorems for manifolds. If the permutohedron argument suggested by Mariano S-A works, we would have the order of the group as an upper bound. – Andrew McIntyre Feb 19 '10 at 15:03
I have edited my post above to include some additional information which address some of what your raise above. – Joseph Malkevitch Feb 19 '10 at 20:39

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).

-
Hee hee, I'm glad it troubled your sleep! I have an intuitive feeling that the inner product has too few degrees of freedom to kill symmetries as flexibly as needed. But I can't back up that feeling with an actual proof. It would be lovely if one could find a clean, representation theoretical answer to this question! – Andrew McIntyre Feb 19 '10 at 15:08

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.

-

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....

-
You did not read the whole question. As you mention, any finite group is a subgroup of a symmetric group; answering the question for the symmetric group would answer it for all finite groups. However, I was not looking to visualize the group as symmetries of "some kind of graph" (which is straightforward), but as isometries of a convex set in R^n. Note that the previous commenters have given good answers. – Andrew McIntyre Feb 15 '10 at 15:48
Is the group of Euclidean symmetries of a permutohedron (built as the convex hull of the point $(1,2,\dots,n)$ and all its permutations in $\mathbb R^n$ larger that $S_n$? – Mariano Suárez-Alvarez Feb 15 '10 at 20:59
ok, I was wrong. Thank You. – kakaz Feb 16 '10 at 9:19
@Mariano S-A: Thanks, I didn't know about the permutohedron! I'll have to check details, but I think your suggestion answers the second part of my original question, giving a simple construction for the required convex set. Just give the group G as a subset of S_n, and then truncate the permutohedron appropriately to restrict its symmetries to the subgroup. – Andrew McIntyre Feb 16 '10 at 19:46
@kakaz: the conditions 1 and 2 you say should be added to the original question are, if I understand them correctly, contained in the word "isomorphic". Reid B and Anton G's answers above show that the answer is yes, with 1 and 2 as requirements. – Andrew McIntyre Feb 16 '10 at 19:49