Finding the minimal $n$ such that a given finite group $G$ is a subgroup of $S_n$

It is a theorem that, for every finite group $G$, there exists an $n$ such that $G \leq S_n$. Given a particular group, is there any way to determine or bound the smallest $n$ such that this occurs? The representation of the group is up to you, though bounds that use less information are preferred.

If this problem is too hard, specific special cases are also interesting, as are bounds on $n$.

Solution 1:

This is not easy for general $G$, but we can immediately produce some crude bounds (on the minimal number $\mu(G)$ such that $G$ embeds into $S_{\mu(G)}$):

If we have an embedding $G \hookrightarrow S_n$, we must trivially have $|G| \leq |S_n| = n!$. Of course, this is sharp in the sense that equality holds for $G = S_n$. On the other hand, the regular representation of $G$ determines an embedding $G \hookrightarrow S_{|G|}$, so $\mu(G) \leq |G|$. This latter bound is sharp:

Theorem If $G$ is a group for which there is no embedding $G \hookrightarrow S_n$ for any $n < |G|$, then $G$ is

1. a cyclic group $\Bbb Z_{p^m}$ of prime power order,
2. a generalized quaternion $2$-group, or
3. the Klein 4-group $\Bbb Z_2 \times \Bbb Z_2$.

There are numerous results available for certain classes of $G$. For example, if $\gcd(|G_1|, |G_2|) = 1$, then $\mu(G_1 \times G_2) = \mu(G_1) + \mu(G_2)$.This and (1) above together resolve the problem for abelian groups:

Theorem If $G$ is abelian, so that we can write it as $\Bbb Z_{a_1} \times \cdots \times \Bbb Z_{a_r}$ for (nontrivial) prime powers $a_1, \ldots, a_r$, then $$\mu(G) = a_1 + \cdots + a_r .$$

(Both of the Theorems here are given by D.L. Johnson and recorded in the reference below, which itself contains a bibliography of this topic.)

The realization of $D_8$ as the group of symmetries of the square determines an embedding $D_8 \hookrightarrow S_4$, and it's not too hard to prove that $\mu(D_{2n}) = \mu(\Bbb Z_n)$ and $\mu(A_n) = n$ (both for $n > 2$). These facts together determine $\mu(G)$ for all $G$ of order $<16$ except $Q_{12} \cong \Bbb Z_3 \rtimes \Bbb Z_4$:

• $S_1$: $\{ e \}$
• $S_2$: $\Bbb Z_2$
• $S_3$: $\Bbb Z_3$, $S_3$
• $S_4$: $\Bbb Z_4$, $\Bbb Z_2 \times \Bbb Z_2$, $D_8$, $A_4$
• $S_5$: $\Bbb Z_5$, $\Bbb Z_6$, $D_{10}$
• $S_6$: $\Bbb Z_4 \times \Bbb Z_2$, $\Bbb Z_2 \times \Bbb Z_2 \times \Bbb Z_2$, $\Bbb Z_3 \times \Bbb Z_3$, $D_{12}$
• $S_7$: $\Bbb Z_7$, $\Bbb Z_{10}$, $\Bbb Z_{12}$, $\Bbb Z_2 \times \Bbb Z_6$, $D_{14}$
• $S_8$: $\Bbb Z_8$, $Q_8$, $\Bbb Z_{15}$
• $S_9$: $\Bbb Z_9$, $\Bbb Z_{14}$
• $S_{11}$: $\Bbb Z_{11}$
• $S_{13}$: $\Bbb Z_{13}$

This question gives an explicit proof that $\mu(Q_8) = 8$.

Lemiuex, Stephan R., Minimal degree of faithful permutation representations of finite groups. (1999) Master's thesis.

Solution 2:

In general, this is not straightforward. If $G$ acts on a set $A$ of $n$ elements, you know this induces a homomorphism $\varphi : G \to S_n$ with kernel $\cap_{a \in A} \textrm{Stab}(a)$. So your problem is reduced to analyzing stabilizers.

Of course if $G$ acts on itself, say, by left multiplication, you get an embedding of $G$ into $S_{|G|}$, but this is usually not particularly helpful. Take $D_4$, the group of symmetries of a square. Since $|D_4| = 8$ we know a copy of $D_4$ lives in $S_8$, but this isn't too revealing as also $D_4 < S_4$. A more outrageous example is Cayley's theorem shows $A_5 < S_{60}$, but we know $A_5 < S_5$.

A nice example of such an embedding is as follows: suppose we want to show any simple group of order $60$ is isomorphic to $A_5$. By the Sylow theorems one can show such a group, say $G$, has a subgroup of index $5$, and then we know this induces an injective homomorphism from $G$ into $S_5$, from the claim follows.

Cayley's theorem won't always give you information about a particular group, but it can be used to prove general facts about group theory, i.e. one can reduce a general problem to a specific case concerning $S_n$. For instance, Cayley's theorem can be used to show for any group $G$ there exists a Galois extension $K$ of $\mathbb{Q}$ with a subfield $F$ such that $\textrm{Gal}(K/F) \simeq G$.

Solution 3:

Given a finite group $G$, consider $H$ to be subgroup such that it contains no normal subgroup of $G$ and consider such $H$ of maximum possible order.

Then $G$ permutes cosets of $H$ by left multiplication, and hence gives a homomorphism from $G$ to permutation group of cosets $\{gH\colon g\in G\}$. The kernel of this homomorphism is intersection of all the conjugates of $H$; but, by our assumption, it should be trivial. Hence $G$ embeds in permutation group on $|G/H|$ letters.

This also explains why $H$ is chosen in beginning of maximum order.

This works, as it can be seen for examples in other answers.

Solution 4:

A simple upper bound is $ \# G $ (when finite). This comes from the fact that for a group $G$, for any $g \in G$, the map $x \mapsto gx$ is bijective (you can check it). So let's assume for simplicity that $G = \{ 1, \ldots, n \}$. We are looking for an injective group homomorphism $\phi : G \to S_{n}$. To do this, let $\phi(g) = f_{g} = (x \mapsto gx)$, i.e. say $\phi(g)$ is the (bijective) function taking $\{ 1, \ldots, n \} = G$ to itself that sends $x$ to $gx$. To see this is a homomorphism, let $g, h \in G$. Then $$f_{gh} (x) = (gh) x = g(hx) = f_{g}(hx) = f_{g}(f_{h}(x)) , $$ so $\phi(gh) = \phi(g) \circ \phi(h)$. To see $\phi$ is injective, let $g, h$ be such that $f_{g}(x) = f_{h}(x)$. Then \begin{align*} gx & = hx \\ \Rightarrow gx (x^{-1}) & = hx (x^{-1}) \\ \Rightarrow g & = h . \end{align*} Thus it's injective. Similarly, if $G$ is infinite, then we can imbed it into the group of permutations on the set $G$. This is, however, not always the optimal way. For example, if we begin with the group $G = S_{n}$, then we're imbedding it into $S_{n!}$. So the size of a group bounds the necessary size of the permutation group of which it is a subgroup as stated.