MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Possible Duplicates:
Smallest permutation representation of a finite group?
Smallest n for which G embeds in $S_n$?

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|$?"

share|cite|improve this question

marked as duplicate by Ryan Budney, S. Carnahan Jun 8 '11 at 8:58

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

Duplicate of… – Jack Schmidt Apr 4 '11 at 17:23
FWIW: The quaternion group of order 8 cannot be embedded in Sym(7), only in Sym(8) and up. Quaternion groups are about the (unique) worst case, but other groups can be pretty bad. – Jack Schmidt Apr 4 '11 at 17:24
The paper in the other answer, has the abelian proof too. – Jack Schmidt Apr 4 '11 at 17:26

Someone asked this on MO in December, see here.

share|cite|improve this answer
Ah, thanks Jeremy. That didn't show up in the MO list of "questions your question might secretly be" when I was posting it. – Adam Hughes Apr 4 '11 at 17:32
And looking at it, I'm not at all sure why not, as it even has the same example I posted. :rolls: – Adam Hughes Apr 4 '11 at 17:34
So I guess we can close this question. – Gerry Myerson Apr 5 '11 at 0:28

Not the answer you're looking for? Browse other questions tagged or ask your own question.