11
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

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}$.

$\endgroup$
  • 3
    $\begingroup$ 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}$. $\endgroup$ – Travis Jan 4 '16 at 3:18
  • 4
    $\begingroup$ What happens if $\sigma = (1 2)(3 4 5)$ and $\tau = (1 2)(3 5)$? $\endgroup$ – David Jan 4 '16 at 3:20
  • 3
    $\begingroup$ In the reference you linked to, $D_{12}$ appears as a subgroup under the name "direct product of $S_3$ and $Z_2$." $\endgroup$ – David Jan 4 '16 at 3:25
  • 1
    $\begingroup$ Ah, you're right, cheers! $\endgroup$ – Travis Jan 4 '16 at 3:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.