# Is the set of permutations in $S_{36}$ that move at most 4 elements a subgroup of $S_{36}$?

I am truly lost as to what this problem is asking. I did post this on another forum and received what my have been wonderful advice. However, even after multiple hours and many "Google" searches I am still confused. Please anyone....

The problem states: If $\sigma$ is a permutation of a set $A$, we say that $\sigma$ moves $a\in A$ iff $\sigma(a)\neq a$.

For the symmetric group $S_{36}$ of all permutations of 36 elements, let $H$ be a subset of $S_{36}$ containing all permutations that move no more than four elements. Is $H$ a subgroup of $S_{36}$? Prove.

I am not looking for an answer but more an explanation of what the problem is saying. I do not know what "move no more than four elements" means. I am feeling really stupid. Any help appreciated.

## 2 Answers

Let's look at $S_3$ instead. There are six permutations: $\left(\begin{array}{ccc} 1 & 2 & 3 \\ 1 & 2 & 3 \end{array}\right)$, $\left(\begin{array}{ccc} 1 & 2 & 3 \\ 1 & 3 & 2 \end{array}\right)$, $\left(\begin{array}{ccc} 1 & 2 & 3 \\ 2 & 1 & 3 \end{array}\right)$, $\left(\begin{array}{ccc} 1 & 2 & 3 \\ 2 & 3 & 1 \end{array}\right)$, $\left(\begin{array}{ccc} 1 & 2 & 3 \\ 3 & 1 & 2 \end{array}\right)$, and $\left(\begin{array}{ccc} 1 & 2 & 3 \\ 3 & 2 & 1 \end{array}\right)$.

$\left(\begin{array}{ccc} 1 & 2 & 3 \\ 1 & 2 & 3 \end{array}\right)$ moves no elements. $\left(\begin{array}{ccc} 1 & 2 & 3 \\ 1 & 3 & 2 \end{array}\right)$, $\left(\begin{array}{ccc} 1 & 2 & 3 \\ 3 & 2 & 1 \end{array}\right)$, and $\left(\begin{array}{ccc} 1 & 2 & 3 \\ 2 & 1 & 3 \end{array}\right)$ move two elements. $\left(\begin{array}{ccc} 1 & 2 & 3 \\ 3 & 1 & 2 \end{array}\right)$ and $\left(\begin{array}{ccc} 1 & 2 & 3 \\ 2 & 1 & 3 \end{array}\right)$ move three elements. Just look at how many are left where they started. With Arturo's answer, you should be on your way.

• @Ross Millikan: Oops: our notations just collided; I'm using cycle notation, you are using abbreviated 2-line notation... I just added a coda to my answer to clarify that. – Arturo Magidin Dec 14 '10 at 22:19
• @Arturo Magadin: Right you are. I though spelling it out this way would help OP, but didn't look at the notation closely enough. – Ross Millikan Dec 14 '10 at 22:38
• @Ross: Actually, I was adding the cycle notation while you were editing, so it was not lack of observation on your part. – Arturo Magidin Dec 15 '10 at 0:57
• @Arturo Magadin: I think we are in synch now. – Ross Millikan Dec 15 '10 at 1:02
• @Ross: Except for the spelling of my last name, anyway. (-; – Arturo Magidin Dec 15 '10 at 1:04

Imagine you have 36 volumes of an encyclopedia in front of you. A permutation $\sigma\in S_{36}$ is a set of instructions of how to swap positions of the volumes of that encyclopedia. For instance, the permutation $\sigma=(1,2,3,4)$ (this is cycle notation: it says element 1 is sent to element 2, element 2 is sent to element 3, 3 to 4, and 4 to 1; if you are used to two-line or abbreviated two-line notation, then this is the permutation that has $$\left(\begin{array}{cccccccc} 1 & 2 & 3 & 4 & 5 & 6 & \cdots & 36\\ 2 & 3 & 4 & 1 & 5 & 6 & \cdots & 36 \end{array}\right).$$ as its two-line description) tells you to take volumes $1$ through $4$, and move volume $1$ to the second position, volume $2$ to the third position, volume $3$ to the fourth position, and volume $4$ to the first position. Even though $\sigma$ is a permutation of all 36 volumes, in fact you only need to move four of the volumes to perform the permutation $\sigma$. So we say that $\sigma$ fixes 32 volumes (volumes 5 through 36 are left untouched) and moves 4 volumes (volumes 1 through 4).

For each permutation $\sigma\in S_n$, which acts on the set $[n]=\{1,2,\ldots,n\}$, you can ask for the set $\mathrm{Fix}(\sigma) = \{ a\in[n]\mid \sigma(a)=a\}$, the set of elements fixed by $\sigma$.

What are the elements "moved" by $\sigma$? They are the elements of $[n]-\mathrm{Fix}(\sigma)$, the complement of $\mathrm{Fix}(\sigma)$.

A $\sigma\in S_{36}$ will lie in $H$ if and only if $-\mathrm{Fix}(\sigma)$ has at most $4$ elements; that is, if and only if $\sigma$ fixes at least 32 of the elements of the numbers in $=\{1,2,3,\ldots,36\}$.

The question is whether $H$ is a subgroup. It is easy to check that it is nonempty and closed under inverses (though you should do that). The trick is going to be figuring out if it is closed under products: if you have $\sigma$ and $\tau$, and each of them fix at least $32$ elements (though possibly not the same 32 elements), can $\sigma\tau$ fix fewer than 32 elements?

• For Closure: "...can στ fix fewer than 32 elements?" yes. My reasoning: Let σ, τ be in set H. If σ moves elements {1, 2, 3, 4} of A and τ moves elements {5, 6, 7, 8} of A, then στ can move up to 7 elements and therefore, H is not closed under permutation multiplication and H is not a subgroup. Am I close? Argh! – JaxASL Dec 15 '10 at 0:20
• @user4755: You are close. If $\sigma$ moves {1,2,3,4} among themselves and $\tau$ moves {5,6,7,8} among themselves, then $\sigma\tau$ would move all eight. But you are right that it moves more than four and that proves H is not closed and not a subgroup. – Ross Millikan Dec 15 '10 at 0:24