# What is the smallest $n$ such that $G\le S_n$? [duplicate]

Cayley's theorem says that every finite group, $G$ can be thought of as a subgroup of some symmetric group, $S_n$, but just how small an $n$ can we take in understanding $G$? It is known that at worst, $n=|G|$ will work, but in the case of say $S_n$ it would be quite silly to embed $S_n$ in $S_{n!}$ when it fits just fine in the MUCH smaller $S_n$. :)

Other cases where it is smaller are $\mathbb{Z}/6$ which narrowly avoids a full embedding in $S_6$ and fits into $S_5$ where it can be modeled as $\langle (1\;2),(3\;4\;5)\rangle$

Indeed, this example lights the way to the general case for abelian groups, since we have the characterization of $G\cong P_1\times P_2\times\ldots\times P_\ell$ where each $P_i$ is the sylow $p_i$ subgroup of $G$ associated to the prime $p_i$.

Starting with the $P_i$, we know $P_i\cong \mathbb{Z}/p_i^{e_{i_1}}\times\mathbb{Z}/p_i^{e_{i_2}}\times\ldots\times \mathbb{Z}/p_i^{e_{i_k}}$, then it should fit into $S_n$ for $n=\sum\limits_{j=1}^k\; p_i^{e_{i_j}}$ and the more general case comes from summing over all the $1\le i\le \ell$, which I don't write out, because three subscripts for an exponent doesn't typeset well.

It's easy to see that this version of the classification gives the smaller of the two candidate values for $n$ because if we do the version where $G\cong A_1\times A_2\times\ldots\times A_k$ where each $A_i$ is cyclic and $|A_{i+1}|$ divides $|A_i|$ for $0< i< k$, since this more or less amounts to $x+y <xy$ for $x,y\ge 2$, since we can, WLOG, assume $y=\max\{ x,y\}$ so that $x+y\le 2y\le xy$.

I'm fairly certain that the $n$ above is the minimal such $n$ for abelian groups, but then some questions which remain are: "Is there a simple proof of this fact?" (my guess is yes), "What can be said for nonabelian groups?", "Can nonabelian groups always fit into $S_n$ with $n<|G|$?", and combining the last two a little, "If so, is there an upper bound for this $n$ in terms of just |G|, which always gives a better estimate than $n\le |G|$?"

-