# How powerful is Cayley's theorem?

So the Cayley's theorem gives a subgroup $$H$$ of $$S_n$$ for a $$G$$ such that $$G$$ is isomorphic to $$H$$. So $$S_n$$ behaves like a Universal set to $$G.$$

Is there a smaller universal object for all groups of size $$n$$?

It is probably worth noting that embeddings in symmetric groups of minimal degree have been studied by multiple authors, amongst them, D. L. Johnson, Minimal permutation representations of finite groups, Amer. J. Math. 93 (1971), 857-866, D. Wright, Degrees of minimal embeddings for some direct products, Amer. J. Math. 97 (1975), 897–903. See also N. Saunders, Minimal Faithful Permutation Degrees of Finite Groups, Aust. Math. Soc. Gazette 35, no.2 (2008), 332-338, and Strict inequalities for minimal degrees of direct products, Bull. Aust. Math. Soc. 79, no.1 (2009), 23–30 by the same author.

Further, and to be complete, I should mention the paper by David Easdown and Cheryl Praeger, On minimal faithful permutation representations of finite groups, Bull. Austral. Math. Soc. 38 (1988), 207-220, and a more "recent" paper that bears the same title, but was authored by L.G. Kovács and Cheryl Praeger, Bull. Austral. Math. Soc. 62 (2000), 311-317.

Finally, in Minimal embeddings of small finite groups (see https://arxiv.org/abs/1706.09286) Robert Heffernan, Des MacHale and Brendan McCann determine the groups of minimal order in which all groups of order $$n$$ can embedded for $$1 \leq n \leq 15$$. They further determine the order of a minimal group in which all groups or order $$n$$ or less can be embedded, also for $$1 \leq n \leq 15$$.

One nice result is the following: Let $$G$$ be a group of minimal order in which all groups of order $$12$$ can be embedded. Then $$G \cong S_3 \times S_4$$.

• Nice. An OEIS entry turns out to be A340514, based on Heffernan, MacHale and McCann. Oct 6, 2021 at 22:36
• There are 74 groups of order 256 into which all groups of order 16 embed. (That paper proves that no group of order 128 works.) Oct 7, 2021 at 8:19
• Just an excerpt out of your lastly added resource (Easdown & Praeger): "...The minimal (faithful) degree $μ(G)$ of a finite group $G$ is the least positive integer $n$ such that $G ≲ S_n$. Clearly if $H ≤ G$ then $μ(H) ≤ μ(G)$. However if $N ◃ G$ then it is possible for $μ(G/N)$ to be greater than $μ(G)$; such groups $G$ are here called exceptional..." (emphasys is mine).
– user943729
Oct 7, 2021 at 10:56
• Yes thanks and this is exceptional indeed, that the minimal degree of a quotient becomes larger than that of the group itself. Oct 7, 2021 at 11:03
• Agreed, but it still is counterintuitive. Oct 7, 2021 at 12:34

The answer is 'sometimes'. For example, all groups of order $$6$$ ($$C_6$$ and $$S_3$$) lie in $$S_5$$, but the quaternion group $$Q_8$$ of order $$8$$ requires $$S_8$$. There are infinitely many $$n$$ such that there is a group of order $$n$$ that does not embed in $$S_{n-1}$$, and infinitely many for which this is not true.

Edit: More easily, cyclic groups of order $$p^n$$ cannot embed in $$S_{p^n-1}$$.

But if $$n$$ is not a prime power then all groups of order $$n$$ do embed in $$S_{n-1}$$. To see this, since $$G$$ does not have order a prime power it is divisible by two primes $$p$$ and $$q$$. Then $$G$$ has an element of order $$p$$ and an element of order $$q$$, $$x$$ and $$y$$ say. The action on the cosets of $$\langle x\rangle$$ union the action on the cosets of $$\langle y\rangle$$ yields a (faithful!) embedding of $$G$$ into a symmetric group of degree $$|G|/p+|G|/q<|G|$$.

Edit 2: If one just wants a proper subgroup of $$S_n$$ containing all groups of order $$n$$, then this is always the case for all $$n>2$$. The only cases that need to be dealt with are $$n$$ a prime power, as above. But then all $$p$$-groups are contained in a Sylow $$p$$-subgroup, which has order the $$p$$-part of $$n!$$. This is (obviously) much smaller than $$n!$$.

In general, I (although Nicky Hekster apparently has) have never seen any work on constructing a minimal group containing all groups of order $$n$$. For $$n=6$$, for example, this group is the dihedral group $$D_{12}$$, which is $$C_2\times S_3$$. This is much smaller than $$S_5$$, the smallest symmetric group containing both groups of order $$6$$. If $$|G|=p^2$$ then this is $$C_{p^2}\times C_p$$, of order $$p^3$$.

• You are right that a cyclic group of order $p$ does not embed into $S_{p-1}$. However the universal group for $n=p$ prime is simply $\mathbb{Z}_p$. You can't beat that! Oct 7, 2021 at 13:39
• @freakish Indeed. See paragraph 4 of my answer. Oct 7, 2021 at 13:49

As a first example of such a "smaller universe", think of any finite $$G$$ having a proper normal subgroup, $$H$$. Then, $$G$$ acts by conjugation on $$H$$, and the kernel of this action is $$C_G(H)$$. Therefore, if $$C_G(H)$$ is trivial, then $$G$$ embeds into $$S_{|H|}$$, which is a "smaller universe" than (Cayley's) $$S_{|G|}$$. For instance, $$C_{S_4}(A_4)=\{1\}$$ and hence $$S_4\hookrightarrow S_{12}$$ (with no claim that this is the minimal embedding).

On the contrary, if $$|G| = p > m$$ is prime, then $$p \not\mid |S_m| = m!$$. Therefore there cannot be an embedding $$G \hookrightarrow S_m$$, because its image would be a subgroup of order $$p$$, contradicting Lagrange's theorem. So, in this case, Cayley's one is the "smallest possible universe".

Perhaps the simplest example of such a "sharper" (though no claim about its minimality) embedding, is the one of $$D_n$$ into $$S_n$$ (which is smaller than Cayley's $$S_{2n}$$). In fact, with the standard notation for the elements of $$D_n$$, let $$H:=\{1,s\}\le D_{n}$$; then, $$rHr^{-1}=\{1,r^2s\}$$ and hence $$H\cap rHr^{-1}=\{1\}$$ as soon as $$n>2$$. This suffices to make the normal core of $$H$$ in $$G$$ trivial, and hence the action of $$D_n$$ on the left quotient set $$D_n/H$$ (of size $$n$$) faithful.