32
$\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!

  • 7
    Here is a relevant question from MO: http://mathoverflow.net/questions/16858/smallest-permutation-representation-of-a-finite-group2012-09-05
  • 0
    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.2012-09-05
  • 2
    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$.2012-09-06
  • 0
    @MikkoKorhonen, why don't you make your comment an answer? The answer you link to on mathoverflow answers this question quite well.2013-11-29
  • 0
    @JamesMitchell: Done.2013-12-01
  • 1
    Related: [Finding the smallest set on which a group acts faithfully](http://math.stackexchange.com/questions/522901/finding-the-smallest-set-on-which-a-group-acts-faithfully)2013-12-02

1 Answers 1