Smallest n for which G embeds in $S_n$?

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?

• How is your group $G$ "given"? By a permutation presentation or By generator + relations presentation, or something else? Though I do not know any answer to your question I feel that it could depend essentially on the way your group is defined. – wood Dec 10 '10 at 14:47
• @Tim: do you mean practically or do you want papers where people studied specific groups? Practically is very hard. There are groups in the libraries where minimal perm reps are not known, despite having been searched for (one gives up after a week or so of computer time). Somewhere I've answered this question before and gave some paper references. I could dig them up again if you wanted. – Jack Schmidt Dec 10 '10 at 15:12
• @Tim: for your second question, SmallerDegreePermutationRepresentation in lib/factgrp.gi has a proposed answer. It often works well, but certainly not always. – Jack Schmidt Dec 10 '10 at 15:23
• @Jim: I sort of consider this as an easy case, because here one needs to find the largest (or a large) maximal subgroup, so my question reduces to one that people know how to solve (or know why it is hard), and where computer algebra systems already do an excellent job. My problem is really about groups for which there is a big difference between the smallest transitive and the smallest non-transitive permutation action (e.g $C_8:(C_{16}\times C_{16}\times C_{16})$ or something like that). – Tim Dokchitser Dec 10 '10 at 17:08
• Possible duplicate of Smallest permutation representation of a finite group? – Stefan Kohl Jan 3 '17 at 21:48

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 (≤107 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.

• That sounds interesting! I am a bit worried though that for groups like $C_8.(C_{16}\times C_{16}\times C_{16})$ the full subgroup lattice will take forever. – Tim Dokchitser Dec 10 '10 at 17:01
• Yup. "Low sectional rank" can mean 1 in practice. Are you primarily interested in p-groups (or nilpotent groups)? I like the idea of finding algorithms for metabelian p-groups P with Ω(P)≤Z(P). It will have no faithful transitive action, and so the problem will be to find trivial intersections of subspaces. – Jack Schmidt Dec 10 '10 at 18:12
• In principle I am interested in all groups that are "not too large", e.g. size at most $10^7$, and $p$-groups are indeed the ones I really need at the moment. (By the way, what do you mean by "no faithful transitive action", sure regular one will do? Or do you mean something else?) – Tim Dokchitser Dec 10 '10 at 22:05
• I think the size and time constraints won't go together; groups of order 60*2^17 and such are not likely to be handled in 5 seconds. For the parentheses: the regular permutation representation is not all that practical for group orders in the millions, and for the question of minimal degree it is (almost) never involved. In other words, it is not part of the search space. – Jack Schmidt Dec 11 '10 at 0:54

Let $\mu(G) = \min\{n \mid G \text{ embeds in } S_n\}$. Here are some results on $\mu(G)$ from this paper by O. Becker:
• $\mu(G)$ is known for abelian groups.
• It is known eactly 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.