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 be a group of some finite order . Then is isomorphic to a subgroup of the symmetric group on elements . Furthermore, this subgroup is simply transitive: given two elements of , there is precisely one element of such that .

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

*Proof:* The group acts on itself by multiplication on the left, thus each element may be identified with a permutation on given by the map . This can be easily verified to identify with a simply transitive permutation group on . The claim then follows by arbitrarily identifying with .

More explicitly, the permutation group arises by arbitrarily enumerating as and then associating to each group element the permutation defined by the formula

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

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 is no longer assumed to be of order , but rather to have an index subgroup that is isomorphic to a fixed group . The generalisation is:

Theorem 2 (Cayley’s theorem for -sets)Let be a group, and let be a group that contains an index subgroup isomorphic to . Then is isomorphic to a subgroup of the semidirect product , defined explicitly as the set of tuples with productand inverse

(This group is a wreath product of with , and is sometimes denoted , or more precisely .) Furthermore, is simply transitive in the following sense: given any two elements of and , there is precisely one in such that and .

Of course, Theorem 1 is the special case of Theorem 2 when is trivial. This theorem allows one to view as a “universal” group for modeling all groups containing a copy of as an index subgroup, in exactly the same way that is a universal group for modeling groups of order . 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 is normal, in which case one can embed into the wreath product , which is a subgroup of .)

*Proof:* The basic idea here is to replace the category of sets in Theorem 1 by the category of -sets, by which we mean sets with a right-action of the group . A morphism between two -sets is a function which respects the right action of , thus for all and .

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

As has index in , we see that is (non-canonically) isomorphic (as an -set) to the -set with the obvious right action of : . It is easy to see that the group of -set automorphisms of can be identified with , with the latter group acting on the former -set by the rule

(it is routine to verify that this is indeed an action of by -set automorphisms. It is then a routine matter to verify the claims (the simple transitivity of follows from the simple transitivity of the action of on itself).

More explicitly, the group arises by arbitrarily enumerating the left-cosets of in as and then associating to each group element the element , where the permutation and the elements are defined by the formula

By noting that is an index normal subgroup of , we recover the classical result of Poincaré that any group that contains as an index subgroup, contains a normal subgroup of index dividing that is contained in . (Quotienting out the right-action, we recover also the classical *proof* of this result, as the action of on itself then collapses to the action of on the quotient space , the stabiliser of which is .)

Exercise 1Show that a simply transitive subgroup of contains a copy of as an index subgroup; in particular, there is a canonical embedding of into , and can be viewed as an -set.

Exercise 2Show that any two simply transitive subgroups of are isomorphic simultaneously as groups and as -sets (that is, there is a bijection that is simultaneously a group isomorphism and an -set isomorphism) if and only if they are conjugate by an element of .

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

## 9 comments

Comments feed for this article

7 October, 2014 at 3:51 am

Mark MeckesNice. I think I may assign this as a homework problem this semester.

7 October, 2014 at 9:41 am

Johannes HahnThis is just the Kaloujnine-Krasner embedding if I’m not mistaken.

7 October, 2014 at 10:31 am

Terence TaoThanks for the reference! (Strictly speaking, it seems that the Kaloujnine-Krasner embedding covers the case when is normal, and then one embeds into the wreath product rather than , but I agree that it is “essentially” the same embedding.) I’ve updated the post to reflect this.

16 October, 2014 at 6:00 am

Frieder LadischThis argument can be used when defining tensor induction (of group representations); for example, essentially the same result appears as Lemma (13.3) in Curtis and Reiner, Methods of Representation theory 1.

19 October, 2014 at 5:03 pm

Benjamin SteinbergYou might find amusing how Ribes and I used this embedding to give fairly easy proofs of some classical theorems from combinatorial group theory like Nielsen-Schreier. See http://arxiv.org/abs/0812.0027 and I apologize for the self-promotion.

19 October, 2014 at 7:23 pm

Benjamin SteinbergTerry,

By the way a more general version of this can be found as Chapter II Proposition 2.1 of Eilenberg’s Automata, Languages and Machines. He considers and embeds the faithful quotient of G acting on G/K into the wreath product of the faithful quotient of H acting on H/K with the faithful product of G acting on G/H, as permutation groups. Your statement is the special case K=1.

Eilenberg says in the chapter notes that this is all “folklore going back to probably to Frobenius”.

The most general version of your argument I know is due essentially to Schutzenberger. He uses the language of monomial representations but it is essentially the same.

Namely the endomorphism monoid of the free H-set on n-generators, i.e., Hx{1,…,n} is the wreath product of H with the monoid of all mappings on n letters. The same argument you give in your post shows that if S is a semigroup acting transitively on the right of a set X and H acts freely by automorphisms of the S-action, then S embeds in the semidirect product of H^n and T where T is the quotient of S acting faithfully on $X/H$. A key example, is where S is a finite semigroup and e is an idempotent of its minimal ideal. The eS is acted on by the right by S and on the left by eSe. In this case eSe is a group acting freely on eS by automorphisms and so the above applies. Schutzenberger proved an analogue for any idempotent but here one must allow wreath products if partial transformation semigroups with groups.

30 October, 2014 at 4:58 am

kevinalhReblogged this on Complejidad improbable.

22 May, 2015 at 3:02 am

Groups and Group Actions: Lecture 16 | Theorem of the week[…] Terry Tao on a generalisation of Cayley’s theorem (this comes with a health warning: the post is not […]

18 May, 2016 at 2:08 am

Groups and Group Actions: Lecture 16 | Theorem of the week[…] Terry Tao on a generalisation of Cayley’s theorem (this comes with a health warning: the post is not […]