embeddings of finite group into permutation groups Let $G$ be a finite simple group, and let $n$ be the smallest integer such that there exists an embedding  of $G$ into the permutation group of $n$ elements. Is this embedding unique up to conjugation?
 A: More of a supplement to @Derek's excellent answer: the reason you look for counterexamples of the form he gave is that since your group is simple and the embedding is into a minimal $S_n$ your subgroup must be transitive and primitive. The O'Nan-Scott theorem (which you can google) then gives you a list of possible counterexamples.
A: When you talk about the embedding being unique up to conjugation, I assume that you are asking whether all subgroups of $S_n$ isomorphic to $G$ are conjugate in $S_n$.
The answer is not always, but it's not so easy to find counterexamples. You need a simple group with more than one conjugacy class of subgroups of index $n$, where the classes are not all fused by automorphisms of the group. The groups $G_2(q)$ with $q$ not a power of 3 and $q>4$ satisfy this condition. They have two nonisomorphic maximal subgroups with the structure $q^5.{\rm GL}_2(q)$. (When $q$ is a power of 3, these subgroups are fused by the exceptional graph isomorphism. When $q=4$, there is a subgroup $J_2$ of smaller index.)
So the smallest counterexample appears to be $G_2(5)$ with $n=3906$. You can find it in the ATLAS of Finite Groups.
A: Cayley's theorem states that any group is isomorphic to a subgroup of the symmetric group.
This can be seen alternatively from the theory of computability. Any "program" (a group is a set of elements with a group operation) has a representation as a Turing machine, which itself is isomorphic to a subset of a permutation group.
