# Let $n \ge 3$. Prove that there are $n!$ different one-to-one homomorphisms from $D_n$ to $S_n$

Let $n \ge 3$. Prove that there are $n!$ different one-to-one homomorphisms from $D_n$ to $S_n$.

I know there are $n!$ elements in $S_n$, but this fact didn't get me anywhere.

I tried many things but nothing seems to be the right way for solving this question. Any help or hint will be appreciated.

• I suppose your notation is such that $D_n$ has $2n$ elements? – Henning Makholm Dec 5 '15 at 15:44
• yes , the dihedral group – user101010 Dec 5 '15 at 15:46
• x @gpgpgp: The trouble is that there are two different notations for dihedral groups. Some authors call the set of symmetries of a square $D_4$; others call it $D_8$. – Henning Makholm Dec 5 '15 at 15:47
• @gpgpgp That's understood, but there are two competing notations for the dihedral group of order $2n$. Some use $D_n$, others use $D_{2n}$. – pjs36 Dec 5 '15 at 15:48
• if I understand correctly it is $D_{2n}$ – user101010 Dec 5 '15 at 15:49

Let $D_n$ be the group generated by $x$ and $y$ with the relations $x^n=e$, $y^2=e$, $yx=x^{-1}y$.

Beware that the question is (hopefully) only asking you to prove that there are at least $n!$ injective homomorphisms $D_n\to S_n$. In most cases there will be more than that.

For example for $n=15$, @orangeskid's construction gives you $15!$ different homomorphisms, but there are ones that don't arise in that way; for example the one given by \begin{align} x \mapsto {} & (1\;2\;3)(4\;5\;6\;7\;8) \\ y \mapsto {} & (2\;3)(5\;8)(6\;7) \end{align}

As noted by the answer by orangeskid, considering the actions of $D_n$ on the corners of a regular $n$-gon will give you $n!$ different homomorphisms given by different labellings of the corners provided that $n$ is odd.

For the case of even $n$, note that $D_n$ acts both on the corners of the $n$-gon and on its sides. And the action of $y$ on the sides is clearly distinguishable from the action on the corners.

(Bonus exercise: Prove that there are exactly $n!$ injective homomorphisms if and only if $n$ is a prime power.)

• I was thinking about your $x$ and $y$. $y$ should be a reflection, so shouldn't it leave exactly one member of $\{1, \ldots, 15\}$ fixed? – pjs36 Dec 5 '15 at 16:33
• P.S.: Id've guessed that $n$ needed to be prime for exactitude. Thanks for the bonus exercise! – Cameron Buie Dec 5 '15 at 16:33
• @pjs36: No -- when we're just asking for some "one-to-one homomorphism" from $D_n$ to $S_n$, the homomorphism conditions are all we're asking for, and "being a reflection" is not something that can be expressed in terms of those. We're just concerned with the group structure of $D_n$ here, not with its geometric interpretation. – Henning Makholm Dec 5 '15 at 16:40
• Fair enough, it does check out! I guess I'm just surprised that the geometry can be difficult to recover from the abstract structure. I'd assumed that the geometry and actions would be "baked in" in a straightforward way, no matter how it was represented with permutations. – pjs36 Dec 5 '15 at 16:48
• @pjs36: For more surprises, consider that there are automorphisms of $D_n$ that don't respect the geometrical structure -- in particular, $(x\mapsto x^k, y\mapsto y)$ whenever $k$ is coprime to $n$. So you can't even see from a homomorphism into $S_n$ which elements of $D_n$ were the basic rotations by $360^\circ/n$. – Henning Makholm Dec 5 '15 at 17:30

HINT:

$D_n$ is the group of symmetries or a regular $n$-gon, so is a subgroup of the group of permutations of the vertices . You can label the vertices of the $n$-gon with the numbers $1, \ldots ,n$ in $n!$ ways. Each such labelling provides a map from $D_n$ to $S_n$.

$\bf{Added:}$ As noticed by @Henning Makholm:, if $n$ is even, we will not get in this way $n!$ distinct maps, but rather $\frac{n!}{2}$, since relabelling with a symmetry wr to the center of the polygon produces the same mapping. So this is still incomplete.

I'll try to explain to myself what happens. Let $i\colon D_n \subset S_n$ with the standard imbedding ( the standard labelling of the vertices). Each permutation of the labelling $\sigma \in S_n$ gives the map $\sigma \circ i \circ \sigma^{-1}$. However, note that there may be $\sigma$ in $S_n$ that commute with the all the elements that are in $i(D_n)$, and those give the same $i$. OK, this happens only if $n$ is even, and the centralized of $i(D_n)$ has two elements, id and the reflection $r$ wr to the center. Hence, $\sigma$ and $\sigma \circ r$ give the same imbedding of $D_n$.

• This works to show there are at least $n!$ homomorphisms, provided that $n$ is odd. But when $n$ is even, two different labellings don't necessarily correspond to different homomorphisms. You can rotate the labellings by 180° and get the same homomorphism out of it. – Henning Makholm Dec 5 '15 at 15:48
• @Henning Makholm: I see, you are totally correct, thanks, I should add that. – Orest Bucicovschi Dec 5 '15 at 15:55

If I understand correctly what $D_n$ means for you, it is a group generated by two elements--say $x$ and $y$--such that $x^n=y^2=xyxy=1.$

If a homomorphism $\varphi:D_n\to S_n$ is be a one-to-one mapping, then, the following conditions hold:

• $\varphi(x)$ has order $n$
• $\varphi(y)$ has order $2$
• $\varphi(xy)=\varphi(x)\varphi(y)$ has order $2$

You should also be able to show that if $\varphi:D_n\to S_n$ is a homomorphism with these three properties, then it is one-to-one. Hence, we must equivalently find enough homomorphisms with those three properties.

One might start by determining the elements of order $n$ in $S_n$--readily, there are at least $(n-1)!$ such--and the elements of order $2$--again readily, there are at least $\binom{n}{2}=\frac12 n(n-1)$ such. Then, one might determine for which $\sigma$ of order $n$ there is some $\tau$ of order $2$ for which $\sigma\tau$ has order $2,$ and how many such $\tau$ there are for each such $\sigma.$ Alternately, one might determine for which $\tau$ of order $2$ there is a $\sigma$ of order $n$ such that $\sigma\tau$ has order $2,$ and how many such $\sigma$ there are for each such $\tau.$

As a side note, having both $\tau$ and $\sigma\tau$ of order $2$ is equivalent to saying that $\tau$ has order $2$ and $\tau\sigma\tau^{-1}=\sigma^{-1}.$

Does that give you some ideas to work with?