70
$\begingroup$

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.

$\endgroup$
11
  • 4
    $\begingroup$ 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. $\endgroup$ Feb 16, 2010 at 8:10
  • 10
    $\begingroup$ Every group is the automorphism group of some graph. $\endgroup$ Feb 16, 2010 at 19:05
  • 4
    $\begingroup$ Every group is the automorphism group of some topology. $\endgroup$ Feb 16, 2010 at 19:05
  • 2
    $\begingroup$ @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? $\endgroup$ Feb 16, 2010 at 20:12
  • 2
    $\begingroup$ If X is a compact manifold and G is a finite group acting on it, then there's an equivarient embedding of X into R^n where G acts on R^n linearly. I wrote this up (in more detail than necessary) on a blog here: cornellmath.wordpress.com/2007/10/24/… $\endgroup$ Feb 19, 2010 at 22:38

10 Answers 10

28
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ Feb 22, 2010 at 15:39
  • 4
    $\begingroup$ 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. $\endgroup$ Feb 22, 2010 at 15:50
  • $\begingroup$ Could one replace the explicit choice of C by a generic one? Like, there is a null-set such that for every C outside that null-set the convex hull of G.C has automorphism group G? $\endgroup$ Jun 11, 2021 at 11:20
30
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ 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). $\endgroup$ Oct 18, 2009 at 16:05
17
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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). $\endgroup$ Oct 18, 2009 at 15:58
  • 2
    $\begingroup$ 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. $\endgroup$ Oct 18, 2009 at 21:30
  • $\begingroup$ 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! $\endgroup$ Oct 19, 2009 at 2:45
14
$\begingroup$

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.

$\endgroup$
13
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Feb 19, 2010 at 15:03
  • $\begingroup$ I have edited my post above to include some additional information which address some of what your raise above. $\endgroup$ Feb 19, 2010 at 20:39
2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Isn't the case for 3-connected planar graphs (aka. polyhedra) pretty easy? The finite subgroups of $O(\Bbb R^3)$ are completely classified (point groups). Any group not in this list cannot be the group of isometries of a polyhedron, e.g. already groups as $C_3\times C_3$. $\endgroup$
    – M. Winter
    Feb 23, 2019 at 22:42
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ 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! $\endgroup$ Feb 19, 2010 at 15:08
-1
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$ Feb 15, 2010 at 15:48
  • $\begingroup$ 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$? $\endgroup$ Feb 15, 2010 at 20:59
  • $\begingroup$ @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. $\endgroup$ Feb 16, 2010 at 19:46
  • $\begingroup$ @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. $\endgroup$ Feb 16, 2010 at 19:49
  • $\begingroup$ OK, I should be more careful and dig into details. Thanks again! $\endgroup$
    – kakaz
    Feb 16, 2010 at 20:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.