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

So I'm asking:

  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!


Solution 1:

The following question from MathOverflow should answer your questions and more: Smallest permutation representation of a finite group?

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.

Johnson, D. L. "Minimal permutation representations of finite groups." Amer. J. Math. 93 (1971), 857-866. MR 316540 DOI: 10.2307/2373739.