# Given a group $G$, can we determine the $n$ for which $G$ is a subgroup of $S_{n}$?

I was watching singingbananas video Introduction to Group Theory, and near the end, he says "all other groups can be found contained in some symmetric group", and I wondered "is it possible to find the $n$ for which, say, the monster $M$ is a subgroup of $S_{n}$? (or any other group)

You can always embed a finite group $G$ into $S_n$, where $n=|G|$ is the size of $G$. This is simply Cayley's Theorem: take the underlying set of $G$ as the set on which you act, and let $G$ act by left multiplication on $G$.

Explicitly: let $f_g\colon G\to G$ be the function (not a group homomorphism) defined by $f_g(x) = gx$. This map is a bijection, since $f_{g^{-1}}$ is the inverse map. So we can view $f_g$ as an element of the group of all permutations of the set $G$, which is isomorphic to $S_n$ via any bijection of $G$ with $\{1,\ldots,n\}$. The map that sends $g\in G$ to $f_g$ is a group homomorphism, since $f_{gh} = f_g\circ f_h$; and it one-to-one, since $f_g(x) = x$ for all $x$ if and only if $g=e$. So the homomorphism $g\mapsto f_g$ followed by the isomorphism between the group of permutations on the set $G$ and $S_n$ gives an embedding of $G$ into $S_n$.

However, this is not necessarily the smallest $n$ for which this works; to take an extreme example, it is plain that you can embed $S_5$ in $S_5$, but the argument above would embed it in $S_{120}$, a much, much larger group (size $120!$, as opposed to size $120$ which suffices).

Instead, one is sometimes interested in finding the smallest $n$ for which $G$ is isomorphic to a subgroup of $S_n$. This is called the "minimal permutation representation of $G$". I don't think this is known in general, but you can find some discussion on this in a MathOverflow question asked a few months ago.

There will be infinitely many such $n$, because if $n_1\leq n_2$, then $S_{n_1}$ can be viewed as a subgroup of $S_{n_2}$, so that if there is a copy of $G$ as a subgroup of $S_{n_1}$, it will appear as a subgroup of $S_{n_2}$ as well. But it is quite easy to find an $n$ for which a group $G$ is a subgroup of $S_n$ - namely, $n=|G|$. The idea is that every $g\in G$ sends an element $x\in G$ to a new element of $G$, namely $gx$. This is actually a permutation of the elements of $G$. The collection of all permutations of the elements of $G$ is $S_n$ where $n=|G|$, but not all of them necessarily came from multiplication by some $g$; thus, $G$ will (in general) be a subgroup of $S_n$ where $n=|G|$. See Cayley's Theorem.

Consider a subgroup $H$ of $G$ such that the only normal subgroup of $G$ contained in $H$ is the trivial group, $\{e\}$; then $G$ can be embedded in $S_n$ where $n=|G\colon H|$. If we choose $H$ to be of minimum index possessing such properties, then it will give a smaller (not necessarily smallest) value of $n$ such that $G$ can be embedded in $H$. [Ref: "Generalized Cayley Theorem"- An intro. to theory of groups - Rotman]

The fact that the minimum value of $n$ found in this way need not be the smallest value such that $G$ can embedded in $S_n$ will be clear from the following simple example:

Consider the cyclic group $G$ of order $6$. All its subgroups are normal, so there is only one subgroup $H=\{e\}$ such that the only normal subgroup of $G$ contained in $H$ is $\{e\}$; its index in $G$ is $6$, so $6$ is a smaller integer such that $G$ can be embedded in $S_6$. But we can embed $G$ in $S_5$; since it contains an element of order $6$ namely $(123)(45)$.

You might want to read http://www.math.uic.edu/~rtakloo/papers/group-paper/delta.12.pdf. There has been a lot of research on minimal S_n embeddings.