Smallest $n$ for which $G$ embeds in $S_n$?

Question

Question: Given a finite group $G$, how do I find the smallest $n$ for which $G$ embeds in $S_n$?

Equivalently, what is the smallest set $X$ on which $G$ acts faithfully by permutations? This looks like a basic question, but I seem not to be able to find answers or even this question in the literature. If this is known to be hard, is there at least a good strategy that would give a small (if not the smallest) $n$ for many groups?

Note: I do not care whether $G$ acts transitively on $X$, so for example for $G=C_6$ the answer is $n=5$ (mapping the generator to (123)(45)), not $n=6$ (regular action).

Edit: If this is not specific enough, is there a method that could find the smallest $n$ (or one close to the smallest one) for any group of size $\le 10^7$ in 5 seconds on some computer algebra system?

Answer 1

Maybe this part of the answer helps. It was sufficient for many tasks, but fails at some reasonable problems.

A permutation action is a multi-set of conjugacy classes of subgroups of a group. The degree of the action is the total of the indices of representatives from each class (with multiplicity). The kernel of the action is the intersection of all the classes, or equivalently, the intersection of the normal cores of the representatives from each class.

If you have a collection of subgroups, organize them into conjugacy classes, sort them by their normal core (first by size, then by actual subgroup). For each normal core (especially starting with the small ones), choose the largest subgroup (smallest index) with that core. These largest subgroups are your ingredients.

Now roughly speaking try all combinations: compute the index and the kernel, and keep the best one, save any improvements to disk if you plan on letting this run for a while.

If you don't have a collection of subgroups handy, then you need to use group-specific ideas to get yourself some. If the Fitting subgroup is small, then cores are unlikely to be a real problem, so you just want big subgroups that are cheap. For small (≤10⁷ or so) groups, you can compute local subgroups pretty cheaply.

If the Fitting subgroup is large or weird, then cores will be plentiful and weird or at least hard to avoid (a particularly awful situation is a unique minimal normal subgroup of order 2). In this case, one computes a full subgroup lattice. You can use recent versions of magma to get a fast answer, but be sure to read the changelogs to make sure you weren't affected by a missing subgroup.

At any rate, in practice this method failed to handle some of the perfect groups in the perfect group library. Perfect groups with large Fitting can require very large permutation representations, but the theoretical lower bounds were often quite a bit lower than what I was able to achieve in practice.

---

If your groups are finitely presented and you have no good starting permutation rep, then you may find that coset enumeration is faster for finitely presented groups than for millions-of-points permutation groups. In other words, typically speaking you start with some permutation representation, because it is going to be faster than any finite presentation. However, for really bad permutation representations (close to regular), you may find coset enumeration is much faster. In particular, finding the index or core of a subgroup might be faster to use ACE than to use permutation group code.

---

If your groups are small and solvable with low sectional rank, just compute the subgroup lattice and sort.

Answer 2

Please see

Elias, Ben; Silberman, Lior; Takloo-Bighash, Ramin Minimal permutation representations of nilpotent groups. Experiment. Math. 19 (2010), no. 1, 121–128.

Answer 3

Let $\mu(G) = \min\{n \mid G \text{ embeds in } S_n\}$. Here are some results on $\mu(G)$ from "The minimal degree of permutation representations of finite groups" by O. Becker:

• $\mu(G)$ is known for abelian groups.
• It is known exactly when $\mu(G) = |G|$. If $\mu(G) < |G|$, then $\mu(G) \le \frac{5}{6}|G|$.
• The identity $\mu(G\times H) = \mu(G) + \mu(H)$ holds for a wide family of groups, for instance — for all $G$, $H$ with central socle.

Answer 4

There has been some recent progress on algorithms for this problem. Das & Thakkar STOC '24 give the following algorithms:

• For groups with no abelian normal subgroups, given by a generating set of permutations, they can find the min faithful perm rep in randomized polynomial time in the input size
• For primitive permutation groups, they can find it in quasi-polynomial ($n^{(\log n)^c}$) time

In terms of "is it known to be hard": They show that, for arbitrary groups given by generating permutations, the corresponding decision problem is in NP, but they leave open whether it is NP-complete (so: it is not yet formally known to be hard). Most of the complexity-theoretic results that would suggest it is not NP-hard are also open, e.g. is it in coAM or coNP?

(They have other results as well, but they are less relevant for this question.)