# The smallest symmetric group $S_m$ into which a given dihedral group $D_{2n}$ embeds

Several questions, both here and on MathOverflow, address the issue of determining for a given group $G$ the smallest integer $\mu(G)$ for which there is an embedding (injective homomorphism) $G \hookrightarrow S_{\mu(G)}$. In general this is a difficult problem, but it's not hard to resolve the question for $G$ of small order, and $\mu(G)$ has been determined for some important classes of groups $G$. For example, for $G$ abelian, so that we can write $G$ uniquely (up to reordering) as $\Bbb Z_{a_1} \times \cdots \times \Bbb Z_{a_r}$ for (nontrivial) prime powers $a_1, \ldots, a_r$, $$\mu(G) = a_1 + \cdots + a_r .$$ And of course, $\mu(S_m) = m$.

I have not been able to find, however, where this has been resolved for the dihedral groups; my question is:

For each dihedral group $D_{2n}$ (of order $2 n$), what is the smallest symmetric group into which $D_{2n}$ embeds, that is, what is $\mu_n := \mu(D_{2n})$?

Of course, $D_2 \cong S_2$ and $D_6 \cong S_3$, and so $\mu_1 = 2$ and $\mu_3 = 3$; also, $D_4 \cong \Bbb Z_2 \times \Bbb Z_2$, so by the above result $\mu_2 = \mu(D_4) = 4$.

For any group $G$ and subgroup $H \leq G$, an embedding $G \hookrightarrow S_m$ determines an embedding $H \hookrightarrow S_m$, and so $\mu(H) \leq \mu(G)$. Thus, since $D_{2n} \cong \Bbb Z_n \rtimes \Bbb Z_2$, we have $\mu_n = \mu(D_{2n}) \geq \mu(\Bbb Z_n)$, which by the above is the sum $\Sigma_n$ of the prime powers in the prime factorization of $n$. On the other hand, for $n > 2$, the usual action by rotations and reflections of $D_{2n}$ on an $n$-gon is faithful and so determines an embedding $D_{2n} \hookrightarrow S_n$; in particular, this gives the upper bound $\mu_n \leq n$.

Already, these bounds together give $\mu_4 = 4$ (realized by the embedding of the symmetry group of the square into the symmetric group on its vertices) and more generally that $\mu_a = a$ for prime powers $a > 2$.

This is not sufficient, however, to determine $\mu_n$ for other integers $> 5$; for example, $\mu(\Bbb Z_6) = 5$, so these bounds only give $5 \leq \mu_6 \leq 6$. It turns out that $D_{12}$ can be embedded in $S_5$ (as David points out in a comment under his question, this embedding can be realized explicitly as $\langle(12)(345), (12)(34)\rangle$), and this settles $\mu_6 = 5$. The above results together determine the subsequence $$(\mu_1, \ldots, \mu_9) = (2, 4, 3, 4, 5, 5, 7, 8, 9) ,$$ which in particular does not appear in the OEIS.

Edit Per David's answer, the sequence $(\mu_n)$ appears to be given by $$\mu_n := \left\{\begin{array}{cl}2, & n = 1\\ 4, & n = 2\\ \Sigma_n, & n > 2 \end{array}\right. ,$$ and $(\Sigma_n)$ itself appears in the OEIS as sequence A008475.

If $n > 2$, then $\mu_n$ is the sum of the prime powers appearing in the decomposition of $n$.

$D_{2n}$ is embeddable in $S_k$ if and only if the following things happen: (1) We can find an element $\sigma$ of order $n$ in $S_k$. (2) We can find an element $\tau$ of order $2$ in $S_k$ such that $\tau \sigma \tau^{-1} = \sigma^{-1}.$
(3) $\tau$ is not a power of $\sigma$. (But (3) follows from (2) if $n > 2$, since otherwise $\tau$ would commute with $\sigma$, so we would have $\sigma = \sigma^{-1}$.)

The order of an element $\sigma$ is the lcm of its cycle lengths. Say the order of $\sigma$ is $n$, and $\sigma$ moves as few elements as possible. Clearly, no prime factor can appear in the length of more than one cycle of $\sigma$. (If a factor $p^a$ appears in one cycle to a lower power than in another, simply divide the length of that cycle by $p^a$ to get a shorter permutation $\sigma$ without changing the lcm of its cycle lengths.) Also, each cycle must have prime power order, for if a cycle had length $ab$ with $a$ and $b$ relatively prime (and $> 1$), we could replace the cycle with two cycles of respective lengths $a$ and $b$ to obtain a shorter $\sigma$. Consequently the best we can do is have $\sigma$ with cycle lengths each of the prime power factors of $n$.

The only problem now is to show that $\tau$ can be chosen without increasing $k$. If one of the cycles in $\sigma$ is $(a_1, a_2, \dots, a_r)$, then let $\tau(a_1) = a_r$, $\tau(a_2) = a_{r-1}$, ..., $\tau(a_r) = a_1$. Define $\tau$ this way on each of the orbits of $\sigma$. Then $\tau$ has order $2$ and $\tau \sigma \tau^{-1} = \sigma^{-1}$.

• Perhaps I'm missing something, but the claim doesn't seem to be true: We have $6 = 2 \cdot 3$, but $D_{12}$ does not appear to embed into $S_5$ (see groupprops.subwiki.org/wiki/…) and so $\mu_6 = 6 \neq 5 = 2 + 3$. It's certainly true that the sum of the prime powers appearing in the decomposition of $n$, which (as in the question) is $\mu(\Bbb Z_n)$ is a lower bound for $\mu(D_{2n})$, as $\Bbb Z_n < D_{2n}$. Jan 4, 2016 at 3:18
• What happens if $\sigma = (1 2)(3 4 5)$ and $\tau = (1 2)(3 5)$? Jan 4, 2016 at 3:20
• In the reference you linked to, $D_{12}$ appears as a subgroup under the name "direct product of $S_3$ and $Z_2$." Jan 4, 2016 at 3:25
• Ah, you're right, cheers! Jan 4, 2016 at 3:26

There is also a following geometric way to explain the solution by David.

Let us recall that $$D_{2n}$$ is the group of symmetries of a regular $$n$$-gon. The idea is that one should consider the action of $$D_{2n}$$ on regular polygons with smaller number of vertices that are inscribed into the given regular n-gon.

To clarify the construction, let us first consider $$n=6$$. There are two regular 3-gons and three regular 2-gons whose vertices are the vertices of the given regular 6-gon. Every element of $$D_{12}$$ acts on the set of two regular 3-gons and acts on the set of three regular 2-gons, thus one has $$D_{12} \rightarrow S_2 \times S_3$$.

It is easy to see that this map is injective. Its composition with tautological embedding $$S_2 \times S_3 \rightarrow S_{2+3}$$ is the necessary map.

Now let us consider a general $$n = \prod_{i=1}^s p_i^{k_i}$$. A regular $$n$$-gon has $$p_i^{k_i}$$ regular $$n/p_i^{k_i}$$-gons, which gives us a map $$D_{2n} \to S_{p_i^{k_i}}$$. Now by Chinese remainder theorem and thoughtful look one proves that the map $$D_{2n} \to \prod_{i=1}^s S_{p_i^{k_i}}$$ is an injection.

(Equivalently, suppose that a symmetry $$g \in D_{2n}$$ preserves every regular $$n/p_i^{k_i}$$-gon in the given $$n$$-gon. Consider any vertex $$v$$ of the given $$n$$-gon. The vertex $$v$$ lies in a certain $$n/p_1^{k_1}$$-gon, in a certain $$n/p_2^{k_2}$$-gon, etc. Each of them is preserved by $$g$$ and their intersection consists of $$v$$ only, thus $$v$$ is preserved by $$g$$).

Thus $$D_{2n} \hookrightarrow S_{\sum_{i=1}^s p_i^{k_i}}$$ and $$\mu(D_{2n}) \leqslant \sum_{i=1}^s p_i^{k_i}$$. But it can not be smaller by the argument by David.