9
$\begingroup$

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)

$\endgroup$
14
$\begingroup$

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.

$\endgroup$
10
$\begingroup$

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.

$\endgroup$
8
$\begingroup$

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)$.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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