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

10

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.