2
$\begingroup$

Prove that $H_n=\{\sigma \in S_n \mid \sigma (i) \equiv i \pmod 3 \}$ with $n≥2$ is a subgroup of $S_n$.

I'm doing this problem and I don't know if my approach is correctly done.

First of all, we see that $id\in H_n$, because $id(i)=i\equiv i\! \pmod 3$, and $H_n$ is not empty.

We have to see now that if $\sigma$, $\tau \in H_n$, then $\sigma\tau^{-1}\in H_n$.

First, we see that if $\tau \in H_n$, then $\tau (i) \equiv i$ (mod $3$). Furthermore, $\tau^{-1} (i) \equiv i \pmod 3$. So $$\sigma\tau^{-1}(i)=\sigma(\tau^{-1}(i))=\sigma(i+3k)\equiv i+3k \!\!\!\pmod 3 \equiv i\!\!\! \pmod 3 \in H_n.$$

So $H_n$ is a subgroup of $S_n$.

I know that this is an easy exercise, but I'm having some troubles with the permutation groups, so I would like someone to say if I made any mistakes

Thank you.

$\endgroup$
  • $\begingroup$ Yeah, it seems ok. Notice that really any permutation of the residue 1 elts, the residue 2 elts, etc works... So your group $H$ seems to be the cartesian product of three symmetric groups of order about $n/3$... $\endgroup$ – Theo Apr 7 '15 at 0:42
2
$\begingroup$

There seems to be absolutely no problem with your proof. You don't seem to have any issues with symmetric groups at all. What I sometimes find useful is just to draw a picture. Something like this is what I'm talking about. It helps you comprehend how elements are "mapped" to each other which is very helpful in giving you intuition and insight before coming up with a proof. For an example if you drew the picture with respect to this problem you will see that any element must be mapped to itself or can be displaced by three elements at a time either way. You can also discover that you can draw out all the elements that are congruent to each other modulo $3$ and see that elements in this set must be mapped to itself.

Another advice would be to delve deeper into exercises you find easy and look for other hidden patterns. For an example, given this problem it would be a fabulous exercise to think of how many elements actually are in $H_n$. That is given $S_n $ find out the number of mappings $\sigma \in S_n$ such that $\sigma(i) \equiv i \pmod 3$. I think for $n = 3(k + 1)$ there are $ 3 k! $, for $n = 3k + 2$ there are $ 2k! + (k- 1)! $ and for $n = 3k + 1$ there are $k! + 2(k-1)!$ number of such mappings. You wanna get better at manipulating symmetric groups? Then check if my claim is right.

$\endgroup$
  • $\begingroup$ Thank you very much! Tomorrow I'll try to find how many elements are in $H_n$ (it's almost 4 am here). Thanks again! $\endgroup$ – Relure Apr 7 '15 at 1:36
  • $\begingroup$ @Abrahamlure: No Problem. $\endgroup$ – Ishfaaq Apr 7 '15 at 2:06
0
$\begingroup$

This is not exactly a problem in modular arithmetic. Let $X$ be a set and $G$ be the group of all permutations of $X$. Take a partition of the set $X$, say $X=\bigcup_j X_j$. Now the set of all permutations that preserve this partition is a subgroup of $G$: that is $\{\sigma\in G\mid \sigma(X_j)\subset X_j\forall j \}$ this is a subgroup (in fact isomorphic to the direct product of symmetric groups of degrees equal to the cardinalities of all these $X_j$'s.

In your case the partition is on the set $\{1,2,\ldots, n\}$ given by the residue classes modulo 3. Viewed this way you will see that this is not a problem in number theory.

$\endgroup$
-1
$\begingroup$

Complete proof without any mistake

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