# Tour:Mind's eye test five (beginners)

UP: Introduction five |
PREVIOUS SECTION MIND'S EYE TEST: Mind's eye test four|General instructions for the tour | Pedagogical notes for the tour | Pedagogical notes for this part

## Symmetric groups on sets of small size

1. Prove that the symmetric group of degree two is isomorphic to the cyclic group of order two.
2. Prove that the symmetric group of degree $n$, for $n \ge 3$, is non-abelian.

## Symmetric groups and set-theoretic operations

In the problems below, the symmetric group on a subset $A \subseteq S$ is understood as the subgroup of the symmetric group on $S$, comprising those permutations that fix every element outside $A$. The alternating group on $A$ comprises the even permutations that fix every element outside $A$.

### Intersections of subsets

1. Suppose $A,B \subseteq S$ are subsets. Prove that the symmetric group on $A \cap B$ is the intersection of the symmetric groups on $A$ and on $B$.

### Unions of subsets

Suppose $A$ and $B$ are complements of each other in a set $S$.

1. Prove that the symmetric groups on $A$ and $B$ intersect trivially as subgroups of the symmetric group on $S$. Further prove that every element of the symmetric group on $A$ commutes with every element of the symmetric group on $B$. Using this, show that the subgroup generated by the symmetric group on $A$ and the symmetric group on $B$ is isomorphic to the direct product of these groups. In particular, show that the symmetric group on $S$ contains a subgroup isomorphic to $A \times B$.
2. Prove that the alternating groups on $A$ and $B$ intersect trivially as subgroups of the alternating group on $S$. Further prove that every element of the alternating group on $A$ commutes with every element of the alternating group on $B$. Using this, show that the subgroup generated by the alternating group on $A$ and the alternating group on $B$ is isomorphic to the direct product of these groups.
3. NEEDS SOME THOUGHT: Suppose $a_i, 1 \le i \le r$ are nonnegative integers such that $\sum_{i=1}^r a_i = n$. Prove that the symmetric group on a set of size $n$ has a subgroup of order $\prod_{i=1}^r a_i!$.

### Infinite sets

1. Suppose $G$ is the symmetric group on an infinite set. Prove that $G$ contains a subgroup isomorphic to $G \times \operatorname{Sym}(n)$ for any natural number $n$.
2. NEEDS SOME THOUGHT: Suppose $G$ is the symmetric group on an infinite set, and $H$ is any finite group. Prove that $G$ contains a subgroup isomorphic to $G \times H$.
3. (This uses the fact that every infinite cardinal equals its double): Suppose $G$ is the symmetric group on an infinite set. Prove that $G$ contains a subgroup isomorphic to $G \times G$.
4. NEEDS LOT OF THOUGHT: (breakdown on Cantor-Bernstein-Schroeder equivalent for groups): Give an example of two infinite groups $A$ and $B$ such that $A$ contains a subgroup isomorphic to $B$, $B$ contains a subgroup isomorphic to $A$, but $A$ and $B$ are not isomorphic.

## Group actions

### Group actions on disjoint unions and on products

1. Suppose $G,H$ are groups acting on the sets $S,T$ respectively. Construct a naturally induced action on $G \times H$ on the disjoint union $S \sqcup T$.
2. Suppose $G,H$ are groups acting on the sets $S,T$ respectively. Construct a naturally induced action on $G \times H$ on the product $S \times T$.
3. Using the previous problem, construct a homomorphism $\operatorname{Sym}(m) \times \operatorname{Sym}(n) \to \operatorname{Sym}(mn)$ where $m,n$ are natural numbers.

### Group actions on power sets

1. Suppose $G$ is a group acting on a set $S$. Construct a natural action of $G$ on the set of subsets of $S$. Prove that for this action, any two subsets in the same orbit have the same cardinality.
2. NEEDS SOME THOUGHT: Consider, for the previous problem, the case where $G = \operatorname{Sym}(S)$ acting the usual way. Assume further that $S$ is finite. Prove that two subsets of $S$ are in the same orbit under the action if and only if they have the same cardinality.
3. NEEDS SOME THOUGHT: Consider the case of a group $G$ acting on itself via left multiplication. Prove that the only subsets of $G$ that are fixed under the induced action on subsets are the empty set and the whole group.
4. NEEDS SOME THOUGHT: Consider the case of a group $G$ acting on itself via left multiplication. Prove that the orbit of a subgroup $H$ of $G$ is precisely the set of left cosets of $H$ in $G$.

### Group actions restricted to subgroups and composed with homomorphisms

1. Suppose $H$ is a subgroup of $G$. Given an action of $G$ on a set $S$, construct an action of $H$ on $S$.
2. Suppose $\alpha:H \to G$ is a homomorphism of groups. Given an action of $G$ on a set $S$, construct an action of $H$ on $S$ using $\alpha$ and the original action.
3. Suppose $H$ is a subgroup of $G$. Consider the action of $H$ on $G$ by left multiplication. Prove thatthe orbit of any $g$ in $G$ is the right coset of $H$ in $G$ containing $g$.

## Cycle decomposition and related stuff

### Order and exponent

Recall that the order of an element is the order of the cyclic group it generates, and the exponent of a group is the least common multiple of the orders of all its elements.

1. Prove that the order of a permutation equals the least common multiple of the sizes of all the cycles in its cycle decomposition.
2. Prove that the exponent of the symmetric group on $n$ letters is the lcm of all the numbers from 1 to $n$.
3. Prove that, for the symmetric group on three elements, the order equals its exponent, but there is no element whose order equals that exponent. Also, prove that for $n \ge 4$, the exponent of the symmetric group is always strictly smaller than the order.
4. Prove that for $n \ge 3$, there does not exist any element in the symmetric group $S_n$, whose order equals the exponent of the group.

### Cycle types

Recall that a transposition is a permutation that switches two elements and fixes all the remaining elements.

1. Define $F(k)$ as the set of all permutations that can be expressed as the product of $k$ disjoint transpositions. Prove that the set of all permutations of order 2 is the disjoint union of the $F(k)$s for $1 \le k \le [n/2]$.
2. NEEDS LOT OF THOUGHT: Find a formula for $f(k) = |F(k)|$, and show that it is a unimodal function of $k$: it first increases with $k$, and then decreases with $k$.
3. NEEDS LOT OF THOUGHT: Prove that for $n > 3$, $f(1) \ne f(k)$ for any $k > 1$.

### Abelian subgroups

A cycle or cyclic permutation is a permutation whose cycle decomposition has just one cycle. We say that two cycles are disjoint if they do not share an element.

1. Prove that any two disjoint cycles permute.
2. Consider a collection of disjoint cycles on $n$ elements of sizes $m_1,m_2,\dots,m_r$, such that $\sum m_i = n$. Prove that these cycles generate an abelian subgroup of order $m_1m_2\dots m_r$.
3. NEEDS LOT OF THOUGHT: In the above problem, prove that the size of this Abelian subgroup is maximum when all the $m_i$ are either 2 or 3, with as many 3s as possible. Using this, prove that the size of this Abelian subgroup is bounded from above by $3^{n/3}$.
4. In the symmetric group on four elements, prove that the double transpositions, along with the identity element, form a subgroup. (This gives an example of an Abelian subgroup not contained in any of the form described in problem (1)).