# “Efficient version” of Cayley's Theorem in Group Theory

I'm considering finite groups only. Cayley's theorem says the a group $G$ is isomorphic to a subgroup of $S_{|G|}$. I think it's interesting to ask for smaller values of $n$ for which $G$ is a subgroup of $S_n$. Obviously, it's not always possible to do better than Cayley's theorem. But sometimes it is possible (for example, $\mathbb{Z}_6$ as a subgroup of $S_5$).

1. Given a finite group $G$, is there an algorithmic way to find or approximate the minimal $n$ for which $G$ is isomorphic to a subgroup of $S_n$?
2. If the answer to $(1)$ is not known, is it known for specific classes of groups?
3. In particular, for finite abelian groups, is it true that for a prime $p$, the minimal $n$ for $\mathbb{Z}_{p^{t_1}} \times \mathbb{Z}_{p^{t_2}}$ is $p^{t_1}+p^{t_2}$ (I can prove that is is true for different primes $p_1$ and $p_2$, but have problems when it's the same prime in both factors).

Thanks!

• Here is a relevant question from MO: mathoverflow.net/questions/16858/… – Mikko Korhonen Sep 5 '12 at 14:21
• The answer to 1 is obviously yes - you are presumably looking for an efficient algorithm. The answer to 3 is also yes. You should follow Rose's advice and look at the discussion on MO. – Derek Holt Sep 5 '12 at 14:28
• A simple (no pun intended) special case: If $G$ is simple then the smallest $n$ for which we have an injective homomorphism into $S_n$ is the smallest index of a proper subgroup of $G$. – Sebastian Schoennenbeck Sep 6 '12 at 15:13
• @MikkoKorhonen, why don't you make your comment an answer? The answer you link to on mathoverflow answers this question quite well. – James Mitchell Nov 29 '13 at 20:17
• – MJD Dec 2 '13 at 2:32

The answer to 3) is yes, and more generally if $G$ is a finite abelian group such that
$$G \cong \mathbb{Z}_{p_1^{a_1}} \times \cdots \times \mathbb{Z}_{p_t^{a_t}}$$
where $p_i$ are prime and $a_i \geq 1$, then the minimal $n$ is $p_1^{a_1} + \cdots + p_t^{a_t}$. A proof can be found in the following paper that Jack Schmidt mentions in his MO answer.