What’s Cayley’s theorem? Give an example of a group of order \(n\) that embeds in \(S_m\) for some \(m\) smaller than \(n\).
Give an example of a group where you have to use \(S_n\).
Solution
1. Cayley’s theorem says that every group \(G\) is isomorphic to a subgroup of the symmetric group on the underlying set of \(G\).
For each \(g\in G\), let \(\lambda_g:G\to G\) be left multiplication, \(\lambda_g(x)=gx\). Each \(\lambda_g\) is a permutation of the set \(G\), and \[ \lambda_{gh}=\lambda_g\lambda_h. \] Thus \[ \lambda:G\longrightarrow \operatorname{Sym}(G),\qquad g\longmapsto\lambda_g \] is a homomorphism. If \(\lambda_g\) is the identity, then \(g=\lambda_g(e)=e\), so \(\lambda\) is injective. For finite \(|G|=n\), choosing a labeling of the underlying set identifies \(\operatorname{Sym}(G)\) with \(S_n\).
2. A group of order \(n\) can sometimes embed in \(S_m\) with \(m<n\).
The group \(S_3\) has order \(6\) and is a subgroup of \(S_3\), so here \(m=3<6=n\).
3. For a prime \(p\), the cyclic group \(C_p\) cannot embed in \(S_m\) for any \(m<p\); hence Cayley’s degree \(n=p\) is minimal for \(C_p\).
Suppose \(C_p\hookrightarrow S_m\). Then \(S_m\) contains an element of order \(p\), namely the image of a generator. By Lagrange’s theorem, \(p\) divides \(|S_m|=m!\). If \(m<p\), then none of the integers \(1,\ldots,m\) is divisible by \(p\), so \(p\nmid m!\), a contradiction. Thus \(m\ge p\).
Conversely, \(C_p\) embeds in \(S_p\) as the subgroup generated by the \(p\)-cycle \((1\,2\,\cdots\,p)\). Therefore the minimal faithful permutation degree of \(C_p\) is exactly \(p\).