How we can find the symmetric group with least $n$ whose subgroup of it is isomorphic to $G$?
By Cayley's Theorem any group $G$ is isomorphic to a subgroup of $S_n$ for $n = |G|$ (since we can think of group actions as permutations of the group elements). And I am asking if there is a general way of calculating the least $n \le |G|$ with such property.
Let me illustrate what I mean by an example: We know that $D_3$ is isomorphic to $S_3$. But by Cayley's Theorem we also know that $D_3$ is isomorphic to a subgroup of $S_6$ (since every group action is a permutation of $3\cdot2 = 6$ elements). In this case least such $n \le |G|$ is $3$. I am asking for a general way of calculating the $n$ for an arbitrary group $G$.
This is an open question and is thought to be hard in general.
While improving my answer I found this answer on MO to the same question, which pretty much covers what I'm going to say.
The answer is known in many cases, such as if $G$ is abelian. The least $n$ is often called the minimal degree or minimal degree of a faithful permutation representation of $G$. The minimal degree of $G$ is denoted $\mu(G)$.
I recommend Minimal Faithful Permutation Representations of Finite Groups by Johnson as a decent starting point for reading about this, but there has been a lot written since then.
Some Results:
Abelian Groups (Johnson)
Let $G=\prod_{i=1}^kC_{p_i^{e_i}}$ where $p_i$ is prime and $e_i\in\mathbb{N}$ for each $i$. Then $\mu(G)=\sum_{i=1}^kp_i^{e_i}$.
Incompressible Groups (Johnson)
We call $G$ incompressible if $\mu(G)=|G|$. These are fully classified by Johnson. A group $G$ is incompressible if and only if $G$ is one of the following:
- Klein $4$-group, $C_2\times C_2$.
- Cyclic of prime power order.
- Generalised quaternion $2$-group.
Simple Groups
If $G$ is simple then any faithful permutation representation of $G$ is equivalent to the action of $G$ on the right cosets of a largest subgroup of $G$. These are known for all simple $G$, but finding a comprehensive list turns out to be quite challenging and some over the years have contained errors. The linked MO question gives some papers with good lists. I also refer to The use of permutation representations in structural computations in large finite matrix groups by Cannon, Holt, Unger for an up to date list.
Direct Products
It's not hard to show that $\mu(G\times H)\le\mu(G)+\mu(H)$, but sometimes this equality holds. The most general results I can find are:
- (Johnson) If $G=\prod_{i=1}^kS_i$ where each $S_i$ is simple then $\mu(G)=\sum_{i=1}^k\mu(S_i)$
- (Becker) If $G$ and $H$ each have central socle (this includes nilpotent groups) then $\mu(G\times H)=\mu(G)+\mu(H)$.
The paper by Becker is called The minimal degree of permutation representations of finite groups.