3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I suppose your notation is such that $D_n$ has $2n$ elements? $\endgroup$ – Henning Makholm Dec 5 '15 at 15:44
  • $\begingroup$ yes , the dihedral group $\endgroup$ – user101010 Dec 5 '15 at 15:46
  • $\begingroup$ 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$. $\endgroup$ – Henning Makholm Dec 5 '15 at 15:47
  • $\begingroup$ @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}$. $\endgroup$ – pjs36 Dec 5 '15 at 15:48
  • $\begingroup$ if I understand correctly it is $D_{2n}$ $\endgroup$ – user101010 Dec 5 '15 at 15:49
4
$\begingroup$

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.)

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – pjs36 Dec 5 '15 at 16:33
  • 1
    $\begingroup$ P.S.: Id've guessed that $n$ needed to be prime for exactitude. Thanks for the bonus exercise! $\endgroup$ – Cameron Buie Dec 5 '15 at 16:33
  • $\begingroup$ @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. $\endgroup$ – Henning Makholm Dec 5 '15 at 16:40
  • $\begingroup$ 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. $\endgroup$ – pjs36 Dec 5 '15 at 16:48
  • 1
    $\begingroup$ @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$. $\endgroup$ – Henning Makholm Dec 5 '15 at 17:30
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Henning Makholm Dec 5 '15 at 15:48
  • $\begingroup$ @Henning Makholm: I see, you are totally correct, thanks, I should add that. $\endgroup$ – Orest Bucicovschi Dec 5 '15 at 15:55
1
$\begingroup$

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?

$\endgroup$

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.