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