33
$\begingroup$

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!

$\endgroup$
6
  • 7
    $\begingroup$ Here is a relevant question from MO: mathoverflow.net/questions/16858/… $\endgroup$ – Mikko Korhonen Sep 5 '12 at 14:21
  • $\begingroup$ 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. $\endgroup$ – Derek Holt Sep 5 '12 at 14:28
  • 2
    $\begingroup$ 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$. $\endgroup$ – Sebastian Schoennenbeck Sep 6 '12 at 15:13
  • $\begingroup$ @MikkoKorhonen, why don't you make your comment an answer? The answer you link to on mathoverflow answers this question quite well. $\endgroup$ – James Mitchell Nov 29 '13 at 20:17
  • 1
    $\begingroup$ Related: Finding the smallest set on which a group acts faithfully $\endgroup$ – MJD Dec 2 '13 at 2:32
11
$\begingroup$

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.

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