One of the first basic theorems in group theory is Cayley’s theorem, which links abstract finite groups with concrete finite groups (otherwise known as permutation groups).

Theorem 1 (Cayley’s theorem) Let ${G}$ be a group of some finite order ${n}$. Then ${G}$ is isomorphic to a subgroup ${\tilde G}$ of the symmetric group ${S_n}$ on ${n}$ elements ${\{1,\dots,n\}}$. Furthermore, this subgroup is simply transitive: given two elements ${x,y}$ of ${\{1,\dots,n\}}$, there is precisely one element ${\sigma}$ of ${\tilde G}$ such that ${\sigma(x)=y}$.

One can therefore think of ${S_n}$ as a sort of “universal” group that contains (up to isomorphism) all the possible groups of order ${n}$.

Proof: The group ${G}$ acts on itself by multiplication on the left, thus each element ${g \in G}$ may be identified with a permutation ${\sigma_g: G \rightarrow G}$ on ${G}$ given by the map ${\sigma_g(h) := gh}$. This can be easily verified to identify ${G}$ with a simply transitive permutation group on ${G}$. The claim then follows by arbitrarily identifying ${G}$ with ${\{1,\dots,n\}}$. $\Box$

More explicitly, the permutation group ${\tilde G}$ arises by arbitrarily enumerating ${G}$ as ${\{s_1,\dots,s_n\}}$ and then associating to each group element ${g \in G}$ the permutation ${\sigma_g: \{1,\dots,n\} \rightarrow \{1,\dots,n\}}$ defined by the formula

$\displaystyle g s_i = s_{\sigma_g(i)}.$

The simply transitive group ${\tilde G}$ given by Cayley’s theorem is not unique, due to the arbitrary choice of identification of ${G}$ with ${\{1,\dots,n\}}$, but is unique up to conjugation by an element of ${S_n}$. On the other hand, it is easy to see that every simply transitive subgroup of ${S_n}$ is of order ${n}$, and that two such groups are isomorphic if and only if they are conjugate by an element of ${S_n}$. Thus Cayley’s theorem in fact identifies the moduli space of groups of order ${n}$ (up to isomorphism) with the simply transitive subgroups of ${S_n}$ (up to conjugacy by elements of ${S_n}$).

One can generalise Cayley’s theorem to groups of infinite order without much difficulty. But in this post, I would like to note an (easy) generalisation of Cayley’s theorem in a different direction, in which the group ${G}$ is no longer assumed to be of order ${n}$, but rather to have an index ${n}$ subgroup that is isomorphic to a fixed group ${H}$. The generalisation is:

Theorem 2 (Cayley’s theorem for ${H}$-sets) Let ${H}$ be a group, and let ${G}$ be a group that contains an index ${n}$ subgroup isomorphic to ${H}$. Then ${G}$ is isomorphic to a subgroup ${\tilde G}$ of the semidirect product ${S_n \ltimes H^n}$, defined explicitly as the set of tuples ${(\sigma, (h_i)_{i=1}^n)}$ with product

$\displaystyle (\sigma, (h_i)_{i=1}^n) (\rho, (k_i)_{i=1}^n) := (\sigma \circ \rho, (h_{\rho(i)} k_i)_{i=1}^n )$

and inverse

$\displaystyle (\sigma, (h_i)_{i=1}^n)^{-1} := (\sigma^{-1}, (h_{\sigma(i)}^{-1})_{i=1}^n).$

(This group is a wreath product of ${H}$ with ${S_n}$, and is sometimes denoted ${H \wr S_n}$, or more precisely ${H \wr_{\{1,\dots,n\}} S_n}$.) Furthermore, ${\tilde G}$ is simply transitive in the following sense: given any two elements ${x,y}$ of ${\{1,\dots,n\}}$ and ${h,k \in H}$, there is precisely one ${(\sigma, (h_i)_{i=1}^n)}$ in ${\tilde G}$ such that ${\sigma(x)=y}$ and ${k = h_x h}$.

Of course, Theorem 1 is the special case of Theorem 2 when ${H}$ is trivial. This theorem allows one to view ${S_n \ltimes H^n}$ as a “universal” group for modeling all groups containing a copy of ${H}$ as an index ${n}$ subgroup, in exactly the same way that ${S_n}$ is a universal group for modeling groups of order ${n}$. This observation is not at all deep, but I had not seen it before, so I thought I would record it here. (EDIT: as pointed out in comments, this is a slight variant of the universal embedding theorem of Krasner and Kaloujnine, which covers the case when ${H}$ is normal, in which case one can embed ${G}$ into the wreath product ${H \wr G/H}$, which is a subgroup of ${H \wr S_n}$.)

Proof: The basic idea here is to replace the category of sets in Theorem 1 by the category of ${H}$-sets, by which we mean sets ${X}$ with a right-action of the group ${H}$. A morphism between two ${H}$-sets ${X,Y}$ is a function ${f: X \rightarrow Y}$ which respects the right action of ${H}$, thus ${f(x)h = f(xh)}$ for all ${x \in X}$ and ${h \in H}$.

Observe that if ${G}$ contains a copy of ${H}$ as a subgroup, then one can view ${G}$ as an ${H}$-set, using the right-action of ${H}$ (which we identify with the indicated subgroup of ${G}$). The left action of ${G}$ on itself commutes with the right-action of ${H}$, and so we can represent ${G}$ by ${H}$-set automorphisms on the ${H}$-set ${G}$.

As ${H}$ has index ${n}$ in ${G}$, we see that ${G}$ is (non-canonically) isomorphic (as an ${H}$-set) to the ${H}$-set ${\{1,\dots,n\} \times H}$ with the obvious right action of ${H}$: ${(i,h) k := (i,hk)}$. It is easy to see that the group of ${H}$-set automorphisms of ${\{1,\dots,n\} \times H}$ can be identified with ${S^n \ltimes H}$, with the latter group acting on the former ${H}$-set by the rule

$\displaystyle (\sigma, (h_i)_{i=1}^n) (i,h) := (\sigma(i), h_i h)$

(it is routine to verify that this is indeed an action of ${S^n \ltimes H}$ by ${H}$-set automorphisms. It is then a routine matter to verify the claims (the simple transitivity of ${\tilde G}$ follows from the simple transitivity of the action of ${G}$ on itself). $\Box$

More explicitly, the group ${\tilde G}$ arises by arbitrarily enumerating the left-cosets of ${H}$ in ${G}$ as ${\{s_1H,\dots,s_nH\}}$ and then associating to each group element ${g \in G}$ the element ${(\sigma_g, (h_{g,i})_{i=1}^n )}$, where the permutation ${\sigma_g: \{1,\dots,n\} \rightarrow \{1,\dots,n\}}$ and the elements ${h_{g,i} \in H}$ are defined by the formula

$\displaystyle g s_i = s_{\sigma_g(i)} h_{g,i}.$

By noting that ${H^n}$ is an index ${n!}$ normal subgroup of ${S_n \ltimes H^n}$, we recover the classical result of Poincaré that any group ${G}$ that contains ${H}$ as an index ${n}$ subgroup, contains a normal subgroup ${N}$ of index dividing ${n!}$ that is contained in ${H}$. (Quotienting out the ${H}$ right-action, we recover also the classical proof of this result, as the action of ${G}$ on itself then collapses to the action of ${G}$ on the quotient space ${G/H}$, the stabiliser of which is ${N}$.)

Exercise 1 Show that a simply transitive subgroup ${\tilde G}$ of ${S_n \ltimes H^n}$ contains a copy of ${H}$ as an index ${n}$ subgroup; in particular, there is a canonical embedding of ${H}$ into ${\tilde G}$, and ${\tilde G}$ can be viewed as an ${H}$-set.

Exercise 2 Show that any two simply transitive subgroups ${\tilde G_1, \tilde G_2}$ of ${S_n \ltimes H^n}$ are isomorphic simultaneously as groups and as ${H}$-sets (that is, there is a bijection ${\phi: \tilde G_1 \rightarrow \tilde G_2}$ that is simultaneously a group isomorphism and an ${H}$-set isomorphism) if and only if they are conjugate by an element of ${S_n \times H_n}$.

[UPDATE: Exercises corrected; thanks to Keith Conrad for some additional corrections and comments.]