## Monthly Archives: April 2010

### Exhibit generators of an isomorphic copy of Q(8) in Sym(8) via the left regular representation

Use the left regular representation of $Q_8$ to produce two elements of $S_8$ which generate a subgroup isomorphic to $Q_8$.

Recall that $Q_8 = \langle i,j \rangle$.

Now $i(1) = i$, $i(-1) = -i$, $i(i) = -1$, $i(-i) = 1$, $i(j) = k$, $i(-j) = -k$, $i(k) = -j$, and $i(-k) = j$. Thus $i \mapsto (1\ i\ -1\ -i)(j\ k\ -j\ -k)$.

Similarly, $j(1) = j$, $j(-1) = -j$, $j(i) = -k$, $j(-i) = k$, $j(j) = -1$, $j(-j) = -1$, $j(k) = i$, and $j(-k) = -i$. Thus $j \mapsto (1\ j\ -1\ -j)(i\ -k\ -i\ k)$.

With the labeling

 $1 \mapsto 1$ $-1 \mapsto 2$ $i \mapsto 3$ $-i \mapsto 4$ $j \mapsto 5$ $-j \mapsto 6$ $k \mapsto 7$ $-k \mapsto 8$

we have $Q_8 \cong \langle (1\ 3\ 2\ 4)(5\ 7\ 6\ 8), (1\ 5\ 2\ 6)(3\ 8\ 4\ 7) \rangle$.

### Exhibit Dih(8) as a subgroup of Sym(8) in two different ways via the left regular representation

Consider $D_8 = \langle r,s \rangle$.

1. List the elements of $D_8$ as $1,r,r^2,r^3,s,sr,sr^2,sr^3$ and label these with the integers $1,2,3,4,5,6,7,8$, respectively. Compute the image of each element of $D_8$ under the left regular representation of $D_8$ into $S_8$.
2. Relabel the elements of $D_8$ with $1,3,5,7,2,4,6,8$, respectively, and recompute the image of each element under the left regular representation. Show that the two subgroups of $S_8$ obtained in parts 1 and 2 are different.

To save effort we will perform this computation in $S_{D_8}$ and then use the labeling bijections $D_8 \rightarrow \{1,2,\ldots,8\}$ to produce subgroups of $S_8$. Let $\lambda : D_8 \rightarrow S_{D_8}$ be the left regular representation.

1. Clearly $\lambda(1) = 1$.
2. We have $\lambda(r)(1) = r$, $\lambda(r)(r) = r^2$, $\lambda(r)(r^2) = r^3$, $\lambda(r)(r^3) = 1$, $\lambda(r)(s) = rs = sr^3$, $\lambda(r)(sr^3) = rsr^3 = sr^6 = sr^2$, and $\lambda(r)(sr^2) = rsr^2 = sr^5 = sr$. Thus $\lambda(r) = (1\ r\ r^2\ r^3)(s\ sr^3\ sr^2\ sr)$.
3. Note that $\lambda(r^2) = \lambda(r)^2$. Thus $\lambda(r^2) = (1\ r^2)(r\ r^3)(s\ sr^2)(sr\ sr^3)$.
4. Note that $\lambda(r^3) = \lambda(r)^3$. Thus $\lambda(r^3) = (1\ r^3\ r^2\ r)(s\ sr\ sr^2\ sr^3)$.
5. We have $\lambda(s)(1) = s$, $\lambda(s)(s) = 1$, $\lambda(s)(r) = sr$, $\lambda(s)(sr) = r$, $\lambda(s)(r^2) = sr^2$, $\lambda(s)(sr^2) = r^2$, $\lambda(s)(r^3) = sr^3$, and $\lambda(s)(sr^3) = r^3$. Thus $\lambda(s) = (1\ s)(r\ sr)(r^2\ sr^2)(r^3\ sr^3)$.
6. Note that $\lambda(sr) = \lambda(s)\lambda(r)$. Thus $\lambda(sr) = (1\ sr)(r\ sr^2)(r^2\ sr^3)(r^3\ s)$.
7. Note that $\lambda(sr^2) = \lambda(s)\lambda(r^2)$. Thus $\lambda(sr^2) = (1\ sr^2)(r\ sr^3)(r^2\ s)(r^3\ sr)$.
8. Note that $\lambda(sr^3) = \lambda(s)\lambda(r^3)$. Thus $\lambda(sr^3) = (1\ sr^3)(r\ s)(r^2\ sr)(r^3\ sr^2)$.

Now via the labelling

 $1 \mapsto 1$ $r \mapsto 2$ $r^2 \mapsto 3$ $r^3 \mapsto 4$ $s \mapsto 5$ $sr \mapsto 6$ $sr^2 \mapsto 7$ $sr^3 \mapsto 8$

we have the isomorphic image

• $1 \mapsto 1$
• $r \mapsto (1\ 2\ 3\ 4)(5\ 8\ 7\ 6)$
• $r^2 \mapsto (1\ 3)(2\ 4)(5\ 7)(6\ 8)$
• $r^3 \mapsto (1\ 4\ 3\ 2)(5\ 6\ 7\ 8)$
• $s \mapsto (1\ 5)(2\ 6)(3\ 7)(4\ 8)$
• $sr \mapsto (1\ 6)(2\ 7)(3\ 8)(4\ 5)$
• $sr^2 \mapsto (1\ 7)(2\ 8)(3\ 5)(4\ 6)$
• $sr^3 \mapsto (1\ 8)(2\ 5)(3\ 6)(4\ 7)$.

Similarly, via the labeling

 $1 \mapsto 1$ $r \mapsto 3$ $r^2 \mapsto 5$ $r^3 \mapsto 7$ $s \mapsto 2$ $sr \mapsto 4$ $sr^2 \mapsto 6$ $sr^3 \mapsto 8$

we have the isomorphic image

• $1 \mapsto 1$
• $r \mapsto (1\ 3\ 5\ 7)(2\ 8\ 6\ 4)$
• $r^2 \mapsto (1\ 5)(3\ 7)(2\ 6)(4\ 8)$
• $r^3 \mapsto (1\ 7\ 5\ 3)(2\ 4\ 6\ 8)$
• $s \mapsto (1\ 2)(3\ 4)(5\ 6)(7\ 8)$
• $sr \mapsto (1\ 4)(3\ 6)(5\ 8)(7\ 2)$
• $sr^2 \mapsto (1\ 6)(3\ 8)(5\ 2)(7\ 4)$
• $sr^3 \mapsto (1\ 8)(3\ 2)(5\ 4)(7\ 6)$.

It is easy to see that these two subgroups are different.

### Exhibit Sym(3) as a subgroup of Sym(6) via the left regular representation

List the elements of $S_3$ as $1$, $(1\ 2)$, $(2\ 3)$, $(1\ 3)$, $(1\ 2\ 3)$, $(1\ 3\ 2)$ and label these with the integers $1,2,3,4,5,6$, respectively. Exhibit the image of each element of $S_3$ under the left regular representation of $S_3$ into $S_6$.

We use the notation $\sigma(k) = \sigma \cdot k$.

1. $1 \mapsto 1$
2. We have $(1\ 2)(1) = (1\ 2) = 2$, $(1\ 2)(2) = (1\ 2)(1\ 2) = 1$, $(1\ 2)(3) = (1\ 2)(2\ 3) = (1\ 2\ 3) = 5$, $(1\ 2)(4) = (1\ 2)(1\ 3) = (1\ 3\ 2) = 6$, $(1\ 2)(5) = (1\ 2)(1\ 2\ 3) = (2\ 3) = 3$, and $(1\ 2)(6) = (1\ 2)(1\ 3\ 2) = (1\ 3) = 4$. Thus $(1\ 2) \mapsto (1\ 2)(3\ 5)(4\ 6)$.
3. We have $(2\ 3)(1) = (2\ 3) = 3$, $(2\ 3)(2) = (2\ 3)(1\ 2) = (1\ 3\ 2) = 6$, $(2\ 3)(3) = (2\ 3)(2\ 3) = 1$, $(2\ 3)(4) = (2\ 3)(1\ 3) = (1\ 2\ 3) = 5$, $(2\ 3)(5) = (2\ 3)(1\ 2\ 3) = (1\ 3) = 4$, and $(2\ 3)(6) = (2\ 3)(1\ 3\ 2) = (1\ 2) = 2$. Thus $(2\ 3) \mapsto (1\ 3)(2\ 6)(4\ 5)$.
4. We have $(1\ 3)(1) = (1\ 3) = 4$, $(1\ 3)(2) = (1\ 3)(1\ 2) = (1\ 2\ 3) = 5$, $(1\ 3)(3) = (1\ 3)(2\ 3) = (1\ 3\ 2) = 6$, $(1\ 3)(4) = (1\ 3)(1\ 3) = 1$, $(1\ 3)(5) = (1\ 3)(1\ 2\ 3) = (1\ 2) = 2$, and $(1\ 3)(6) = (1\ 3)(1\ 3\ 2) = (2\ 3) = 3$. Thus $(1\ 3) \mapsto (1\ 4)(2\ 5)(3\ 6)$.
5. We have $(1\ 2\ 3)(1) = (1\ 2\ 3) = 5$, $(1\ 2\ 3)(2) = (1\ 2\ 3)(1\ 2) = (1\ 3) = 4$, $(1\ 2\ 3)(3) = (1\ 2\ 3)(2\ 3) = (1\ 2) = 2$, $(1\ 2\ 3)(4) = (1\ 2\ 3)(1\ 3) = (2\ 3) = 3$, $(1\ 2\ 3)(5) = (1\ 2\ 3)(1\ 2\ 3) = (1\ 3\ 2) = 6$, and $(1\ 2\ 3)(6) = (1\ 2\ 3)(1\ 3\ 2) = 1$. Thus $(1\ 2\ 3) \mapsto (1\ 5\ 6)(2\ 4\ 3)$.
6. We have $(1\ 3\ 2)(1) = (1\ 3\ 2) = 6$, $(1\ 3\ 2)(2) = (1\ 3\ 2)(1\ 2) = (2\ 3) = 3$, $(1\ 3\ 2)(3) = (1\ 3\ 2)(2\ 3) = (1\ 3) = 4$, $(1\ 3\ 2)(4) = (1\ 3\ 2)(1\ 3) = (1\ 2) = 2$, $(1\ 3\ 2)(5) = (1\ 3\ 2)(1\ 2\ 3) = 1$, and $(1\ 3\ 2)(6) = (1\ 3\ 2)(1\ 3\ 2) = (1\ 2\ 3) = 5$. Thus $(1\ 3\ 2) \mapsto (1\ 6\ 5)(2\ 3\ 4)$.

### Exhibit the Klein 4-group as a subgroup of Sym(4) using the left regular representation

Let $G = \{1,a,b,c\}$ be the Klein 4-group.

1. Label the elements $1,a,b,c$ with the integers $1,2,4,3$, respectively, and prove that under the left regular representation of $G$ into $S_4$ the nonidentity elements are mapped as follows: $a \mapsto (1\ 2)(3\ 4)$, $b \mapsto (1\ 4)(2\ 3)$, and $c \mapsto (1\ 3)(2\ 4)$.
2. Relabel the elements $1,a,b,c$ as $1,4,2,3$, respectively, and compute the image of each element of $G$ under the left regular representation of $G$ into $S_4$. Show that the image of $G$ under this labelling is the same subgroup of $S_4$ (even though the individual elements map differently.)

The multiplication table for $G$ is as follows.

 1 a b c 1 1 a b c a a 1 c b b b c 1 a c c b a 1

We can see that with $1,a,b,c$ labelled as $1,2,4,3$, respectively, since $a1 = a$, $aa = 1$, $ab = c$, and $ac = b$ we have $a(1) = 2$, $a(2) = 1$, $a(3) = 4$, and $a(4) = 3$. Thus $a \mapsto (1\ 2)(3\ 4)$.

Similarly, $b1 = b$, $ba = c$, $bb = 1$, and $bc = a$, so that $b \mapsto (1\ 4)(2\ 3)$. Likewise $c \mapsto (1\ 3)(2\ 4)$.

Now we relabel the elements $1,a,b,c$ as $1,4,2,3$, respectively. Now $a(1) = a1 = a = 4$, $a(2) = ab = c = 3$, $a(3) = ac = b = 2$, and $a(4) = aa = 1$. Thus $a \mapsto (1\ 4)(2\ 3)$. Now $b(1) = b = 2$, $b(2) = bb = 1$, $b(3) = bc = a = 4$, and $b(4) = ba = c = 3$, so that $b \mapsto (1\ 2)(3\ 4)$, and $c(1) = c = 3$, $c(2) = cb = a = 4$, $c(3) = cc = 1$, and $c(4) = ca = b = 2$, so that $c \mapsto (1\ 3)(2\ 4)$. Clearly this is the same subgroup as the image of $G$ under the first labelling.

Let $G$ be a group and $H,K \leq G$ subgroups. For each $x \in G$, define the $(H,K)$ double coset of $x$ by $HxK = \{ hxk \ |\ h \in H, k \in K \}$.

1. Prove that $HxK$ is the union of the left cosets $x_iK$ where $x_iK \in H \cdot xK$.
2. Prove (as above) that $HxK$ is a union of right cosets of $H$.
3. Show that the set of $(H,K)$ double cosets partitions $G$.
4. Prove that $|HxK| = |K| \cdot [H : H \cap xKx^{-1}]$.
5. Prove that $|HxK| = |H| \cdot [K : K \cap x^{-1}Hx]$.

1. $(\subseteq)$ Let $hxk \in HxK$. Now $hxK = h \cdot xK \in H \cdot xK$ and $hxk \in hxK$. Thus $hxk \in \bigcup_{yK \in H \cdot xK} yK$.

$(\supseteq)$ Let $g \in \bigcup_{yK \in H \cdot xK} yK$. Then $g \in yK$ for some $yK \in H \cdot xK$, so that $yK = h \cdot xK = hxK$ for some $h \in H$. Then $g = hxk$ for some $k \in K$. So $g \in HxK$.

2. $(\subseteq)$ Let $hxk \in HxK$. Now $Hxk = Hx \cdot k \in Hx \cdot K$ and $hxk \in Hxk$. Thus $hxk \in \bigcup_{Hy \in Hx \cdot K} Hy$.

$(\supseteq)$ Let $g \in \bigcup_{Hy \in Hx \cdot K} Hy$. Then $g \in Hy$ for some $Hy \in Hx \cdot K$, so that $Hy = Hx \cdot k = Hxk$ for some $k \in K$. Then $g = hxk$ for some $h \in H$. So $g \in HxK$.

3. Note that every element is in some double coset- in particular, $x \in HxK$ for all $x \in G$. So $G = \bigcup_{x \in G} HxK$.

Note that if $y \in HxK$, then $HyK \subseteq HxK$.

Now suppose $x,y \in G$ such that $HxK \cap HyK \neq \emptyset$. Then we have $h_1xk_1 = h_2yk_2$ for some $h_i \in H$ and $k_i \in K$. Then $x = h_1^{-1}h_2yk_2k_1^{-1} \in HyK$, so that $HxK \subseteq HyK$. Similarly $HyK \subseteq HxK$. Thus two double cosets are either disjoint or equal. Thus the $(H,K)$ double cosets form a partition of $G$.

4. First we prove a lemma.

Lemma 1: $\mathsf{stab}_H(xK) = H \cap xKx^{-1}$. Proof: $(\subseteq)$ Suppose $h \in \mathsf{stab}_H(xK)$. Then $hxK = h \cdot xK = xK$, and we have $x^{-1}hx \in K$. So $h \in xKx^{-1}$, hence $h \in H \cap xKx^{-1}$. $(\supseteq)$ Suppose $h \in H \cap xKx^{-1}$. Then $x^{-1}hx \in K$, so that $h \cdot xK = hxK = xK$, thus $h \in \mathsf{stab}_H(xK)$. $\square$

We saw in part 1 above that $HxK = \bigcup_{yK \in H \cdot xK} yK$; moreover, this union is disjoint because the $yK$ are distinct left cosets of $K$, each of order $|K|$. Thus $|HxK| = |K| \cdot |H \cdot xK| = |K| \cdot [H : \mathsf{stab}_H(xK)] = |K| \cdot [H : H \cap xKx^{-1}]$, using Lemma 1.

5. First we prove a lemma.

Lemma 2: $\mathsf{stab}_K(Hx) = K \cap x^{-1}Hx$. Proof: $(\subseteq)$ Suppose $k \in \mathsf{stab}_K(Hx)$. Then $Hxk = Hx \cdot k = Hx$, and we have $xkx^{-1} \in H$. So $k \in x^{-1}Hx$, hence $k \in K \cap x^{-1}Hx$. $(\supseteq)$ Suppose $k \in K \cap x^{-1}Hx$. Then $xkx^{-1} \in H$, so that $Hx \cdot k = Hxk = Hx$, thus $k \in \mathsf{stab}_K(Hx)$. $\square$

We saw in part 2 above that $HxK = \bigcup_{Hy \in Hx \cdot K} Hy$; moreover, this union is disjoint. Thus $|HxK| = |H| \cdot |Hx \cdot K| = |H| \cdot [K : \mathsf{stab}_K(Hx)] = |K| \cdot [K : K \cap x^{-1}Hx]$.

### Transitive group actions induce transitive actions on the orbits of the action of a subgroup

Suppose $G \leq S_A$ acts transitively on $A$ and let $H \leq G$ be normal. Let $O_1, O_2, \ldots, O_r$ be the distinct orbits of $H$ on $A$.

1. Prove that $G$ permutes the sets $O_k$ in the sense that for each $g \in G$ and each $i \in \{1,2,\ldots,r\}$ there exists a $j$ such that $g \cdot O_i = O_j$. Prove that $G$ is transitive on $\{ O_1,O_2,\ldots,O_r \}$. Deduce that all orbits of $H$ on $A$ have the same cardinality.
2. Prove that if $a \in O_1$ then $|O_1| = [H : H \cap \mathsf{stab}_G(a)]$ and that $r = [G : H \mathsf{stab}_G(a)]$. [Hint: Note that $H \cap \mathsf{stab}_G(a) = \mathsf{stab}_H(a)$ and use the Second Isomorphism Theorem.]

1. Let $g \in G$ and $a \in A$. Now $H \cdot a$ is an arbitrary orbit of $H$ on $A$. Moreover, $g \cdot a = b$ for some $b \in A$. Then $g \cdot (H \cdot a) = gH \cdot a = Hg \cdot a = H \cdot (g \cdot a) = H \cdot b$, since $H$ is normal. Thus $G$ permutes the orbits $\{ H \cdot a \ |\ a \in A \}$.

Now let $a,b \in A$ be arbitrary; since the action of $G$ on $A$ is transitive, there exists $g \in G$ such that $g \cdot a = b$. Then $g \cdot (H \cdot a) = gH \cdot a = Hg \cdot a = H \cdot (g \cdot a) = H \cdot b$; thus the action of $G$ on the orbits $\{ H \cdot a \ |\ a \in A \}$ is transitive.

Let $a,b \in A$ be arbitrary, and let $g \in G$ such that $g \cdot a = b$. Because $H$ is normal, for every $h \in H$ there exists a unique $k \in H$ such that $gh = kg$. We have a mapping $\varphi_g : H \cdot a \rightarrow H \cdot b$ given by $\varphi_g(h \cdot a) = k \cdot b$. Because $gH = Hg$, this mapping $\varphi_g$ is bijective, and $|H \cdot a| = |H \cdot b|$. Because the action of $G$ is transitive on the orbits, all orbits have the same cardinality.

2. Let $a \in A$. We can restrict the action of $G$ on the orbits of $H$ to $H$; with this action we have $|H \cdot a| = [H : \mathsf{stab}_H(a)]$. Clearly $\mathsf{stab}_H(a) = H \cap \mathsf{stab}_G(a)$; thus $|H \cdot a| = [H : H \cap \mathsf{stab}_G(a)]$. Considering now the (transitive) action of $G$ on the orbits of $H$, we have $r = |\{ H \cdot a \ |\ a \in A \}| = [G : \mathsf{stab}_G(H \cdot a)]$.

We claim that $\mathsf{stab}_G(H \cdot a) = H \mathsf{stab}_G(a)$. Proof of claim: Suppose $g \in \mathsf{stab}_G(H \cdot a)$. Now $Hg \cdot a = gH \cdot a = g \cdot (H \cdot a) = H \cdot a$, so that in particular $g \cdot a = h \cdot a$ for some $h \in H$. Then $h^{-1}g \cdot a = a$, so that $h^{-1}g \in \mathsf{stab}_G(a)$. Thus $g \in H \mathsf{stab}_G(a)$. Now suppose $g \in H \mathsf{stab}_G(a)$. Then $g = hx$ for some $h \in H$ and $x \in \mathsf{stab}_G(a)$. Now $g \cdot (H \cdot a) = gH \cdot a = Hg \cdot a = Hhx \cdot a = H \cdot a$, so that $g \in \mathsf{stab}_G(H \cdot a)$. Thus $r = [G : H \mathsf{stab}_G(a)]$.

### Every doubly transitive group action is primitive

A transitive permutation group $G \leq S_A$ acting on $A$ is called doubly transitive if for all $a \in A$, the subgroup $\mathsf{stab}(a)$ is transitive on $A \setminus \{a\}$.

1. Prove that $S_n$ is doubly transitive on $\{1,2,\ldots,n\}$ for all $n \geq 2$.
2. Prove that a doubly transitive group is primitive. Deduce that $D_8$ is not doubly transitive in its action on the four vertices of a square.

1. We know that $S_n$ is transitive on $A = \{1,2,\ldots,n\}$. Now if $n \geq 2$ and $k \in A$, we have a natural isomorphism $\mathsf{stab}(k) \cong S_{A \setminus \{k\}}$; this permutation group is also transitive in its action on $A \setminus \{k\}$. Thus $S_n$ is doubly transitive.
2. Let $G \leq S_A$ act transitively on $A$, and suppose further that the action is doubly transitive. Let $B \subseteq A$ be a proper block; then there exist elements $b \in B$ and $a \in A \setminus B$. By a previous exercise, we have $\mathsf{stab}(b) \leq \mathsf{stab}(B)$. Thus if $\sigma \in \mathsf{stab}(b)$, we have $\sigma[B] = B$. Suppose now that there exists an element $c \in B$ with $c \neq b$. Because $G$ is doubly transitive on $A$, there exists an element $\tau \in \mathsf{stab}(b)$ such that $\tau(c) = a$. Thus $\tau[B] \neq B$, a contradiction. So no such element $c$ exists and we have $B = \{b\}$. Now every block is trivial, thus the action of $G$ on $A$ is primitive.

We saw that the action of $D_8$ on the four vertices of a square is not primitive in the previous exercise. Thus this action is not doubly transitive.

### Basic properties of blocks of a group action

Let $G \leq S_A$ act transitively on the set $A$. A block is a nonempty subset $B \subseteq A$ such that for all $\sigma \in G$ either $\sigma[B] = B$ or $\sigma[B] \cap B = \emptyset$.

1. Prove that if $B$ is a block containing $a \in A$ and we define $\mathsf{stab}(B) = \{ \sigma \in G \ |\ \sigma[B] = B \}$ then $\mathsf{stab}(a) \leq \mathsf{stab}(B) \leq G$.
2. Prove that if $B$ is a block then $\mathcal{B} = \{ \sigma[B] \ |\ \sigma \in G \}$ is a partition of $A$.
3. A (transitive) group $G \leq S_A$ is called primitive if the only blocks in $A$ are the trivial ones- the singletons and $A$ itself. Prove that $S_4$ is primitive on $A = \{1,2,3,4\}$. Prove that $D_8$ is not primitive as a permutation group on the four vertices of a square.
4. Let $G \leq S_A$ act transitively on $A$. Prove that $G$ is primitive on $A$ if and only if for all $a \in A$, $\mathsf{stab}(a)$ is maximal in $G$.

1. Note that $\mathsf{stab}(B)$ is not empty since $1[B] = B$. Now let $\sigma, \tau \in \mathsf{stab}(B)$. Note that $\tau^{-1}[B] = \tau^{-1}\tau [B] = B$, so that $\sigma\tau^{-1}[B] = B$. Thus $\sigma\tau^{-1} \in \mathsf{stab}(B)$. By the subgroup criterion, $\mathsf{stab}(B) \leq G$.

Now suppose $\sigma \in \mathsf{stab}(a)$. We have $\sigma(a) = a$, so that $\{a\} \subseteq \sigma[B] \cap B$. Hence $\sigma[B] \cap B$ is nonempty, and we have $\sigma[B] = B$ since $B$ is a block. Thus $\sigma \in \mathsf{stab}(B)$. By a previous exercise, $\mathsf{stab}(a) \leq \mathsf{stab}(B)$.

2. First we show that $\bigcup_{\sigma \in G} \sigma[B] = A$. The $(\subseteq)$ direction is clear. $(\supseteq)$: Let $a \in A$ and $b \in B$. Since the action of $G$ is transitive, there exists $\sigma \in G$ such that $a = \sigma(b)$. Then $a \in \sigma[B]$, so that $aA \subseteq \bigcup_{\sigma \in G} \sigma[B]$.

Now suppose $\sigma[B] \cap \tau[B] \neq \emptyset$. Then there exist $a,b \in B$ such that $\sigma(a) = \tau(b)$. Now $a = \sigma^{-1}\tau \cdot b$, so that $\sigma^{-1}\tau[B] \cap B$ is not empty. Thus $\sigma^{-1}\tau[B] = B$, and we have $\sigma[B] = \tau[B]$. So elements of $\mathcal{B}$ are pairwise disjoint; hence $\mathcal{B}$ is a partition of $A$.

1. Let $B \subseteq A = \{1,2,3,4\}$ be a proper nonempty subset. Then there exist elements $x \in B$ and $y \in A \setminus B$. Suppose $B$ is a block. Consider $\sigma = (x\ y) \in S_4$; since $\sigma(x) \notin B$, we have $\sigma[B] \cap B = \emptyset$. Let $w$ and $z$ be the remaining elements of $A$. If $w \in B$, then $w \in \sigma[B] \cap B$, a contradiction; similarly for $z$. Thus $B = \{x\}$. Now clearly $A$ itself is a block, and any proper block must be a singleton. Thus this action of $S_4$ is primitive.
2. We saw previously that $D_8 \cong \langle (1\ 3), (1\ 2\ 3\ 4) \rangle$, where $A = \{1,2,3,4\}$ are labels on the vertices of a square (written clockwise). Consider the set $\{1,3\}$. We see that
1. $1 \cdot \{1,3\} = \{1,3\}$
2. $(1\ 2\ 3\ 4) \cdot \{1,3\} = \{2,4\}$
3. $(1\ 3)(2\ 4) \cdot \{1,3\} = \{1,3\}$
4. $(1\ 4\ 3\ 2) \cdot \{1,3\} = \{2,4\}$
5. $(1\ 3) \cdot \{1,3\} = \{1,3\}$
6. $(1\ 2)(3\ 4) \cdot \{1,3\} = \{2,4\}$
7. $(2\ 4) \cdot \{1,3\} = \{1,3\}$
8. $(1\ 4)(2\ 3) \cdot \{1,3\} = \{2,4\}$

So that $\{1,3\}$ is a nontrivial block; hence this action is not primitive.

3. We begin with some lemmas.

Lemma 1: Let $G \leq S_A$ act transitively on $A$ and let $B \subseteq A$ be a block under the action. Then $\mathsf{stab}(B) = G$ if and only if $B = A$. Proof: The $(\Leftarrow)$ direction is clear. $(\Rightarrow)$ Suppose $B$ is a proper subset and let $x \in B$, $y \in A \setminus B$. Now $y \in (x\ y)[B]$ and $y \notin B$, so that $(x\ y)[B] \neq B$. Since $B$ is a block, we have $(x\ y)[B] \cap B = \emptyset$. But $x \in (x\ y)[B] \cap B$ since $x \in B$ and $y \notin B$, a contradiction. So $B$ is not proper, and we have $A = B$. $\square$

Now we move to the main result.

$(\Rightarrow)$ Suppose $G$ is primitive on $A$; then the only blocks of $A$ are $A$ and the singletons. Now let $a \in A$ and let $H \leq G$ be a subgroup with $\mathsf{stab}(a) \leq H \leq G$. We consider the set $H \cdot a = \{ h \cdot a \ |\ h \in H \}$.

We claim that $H \cdot a$ is a block. Proof of claim: $H \cdot a$ is not empty since $a = 1 \cdot a \in H \cdot a$. Now let $\sigma \in G$. If $\sigma \in H$, then $\sigma \cdot (H \cdot a) = \sigma H \cdot a = H \cdot a$. If $\sigma \notin H$, then $\sigma \cdot (H \cdot a) = \sigma H \cdot a$. Suppose that $\sigma H \cdot a \cap H \cdot a \neq \emptyset$; say that $\sigma\tau_1 \cdot a = \tau_2 \cdot a$ for some $\tau_1, \tau_2 \in H$. Then $\tau_2^{-1} \sigma \tau_1 \cdot a = a$, so that $\tau_2^{-1} \sigma \tau_1 \in \mathsf{stab}(a) \leq H$. But then $\sigma \in \tau_2H\tau_1^{-1} = H$, a contradiction. Thus if $\sigma \notin H$, then $\sigma[H \cdot a] \cap H \cdot a = \emptyset$. Hence $H \cdot a$ is a block.

Next we claim that $\mathsf{stab}(H \cdot a) = H$. Proof of claim: $(\supseteq)$ If $\tau \in H$, then $\tau \cdot (H \cdot a) = \tau H \cdot a = H \cdot a$. $(\subseteq)$ Suppose $\sigma \cdot (H \cdot a) = \sigma H \cdot a = H \cdot a$. Then $\sigma \cdot a = \tau \cdot a$ for some $\tau \in H$, hence $\tau^{-1} \sigma \cdot a = a$. Then $\tau^{-1} \sigma \in \mathsf{stab}(a) \leq H$, so that $\sigma \in H$.

Since $G$ is primitive on $a$ and $a \in H \cdot a$, we have $H \cdot a = \{a\}$ or $H \cdot a = A$. If $H \cdot a = \{a\}$, we have $H \leq \mathsf{stab}(a)$, so that $H = \mathsf{stab}(a)$. If $H \cdot a = A$, we have $H = \mathsf{stab}(H \cdot a) = \mathsf{stab}(A) = G$. Thus $\mathsf{stab}(a)$ is a maximal subgroup of $G$.

$(\Leftarrow)$ Suppose that for all $a \in A$, $\mathsf{stab}(a)$ is a maximal subgroup in $G$. Let $B \subseteq A$ be a block with $a \in B$. Now $\mathsf{stab}(a) \leq \mathsf{stab}(B) \leq G$ by part 1 above. Since $\mathsf{stab}(a)$ is maximal, there are two cases.

If $\mathsf{stab}(B) = \mathsf{stab}(a)$ and $b \in B$ such that $b \neq a$, then since $G$ acts transitively there exists $\sigma \in G$ such that $\sigma \cdot a = b$. Now $\sigma \in \mathsf{stab}(B) = \mathsf{stab}(a)$, a contradiction. Thus $B = \{a\}$.

If $\mathsf{stab}(B) = G$, then by Lemma 1 we have $B = A$.

Thus $G$ is primitive on $A$.

### Compute some orbits of an action by Sym(4) on polynomials in four variables

As in this previous exercise, let $S_4$ act on the set $R$ of all polynomials with integer coefficients in the independent variables $x_1,x_2,x_3,x_4$ by permuting the indices: $\sigma \cdot p(x_1,x_2,x_3,x_4) = p(x_{\sigma(1)}, x_{\sigma(2)}, x_{\sigma(3)}, x_{\sigma(4)})$.

1. Find the polynomials in the orbit of $x_1 + x_2$. (Recall from a previous exercise that the stabilizer of this element has order 4.)
2. Find the polynomials in the orbit of $x_1x_2 + x_3x_4$. (Recall that the stabilizer of this element has order 8.)
3. Find the polynomials in the orbit of $(x_1 + x_2)(x_3 + x_4)$.

1. We have $[S_4 : \mathsf{stab}(x_1+x_2)] = 6$. A simple calculation then shows that this orbit is $\{ x_1+x_2, x_1+x_3, x_1+x_4,$ $x_2+x_3, x_2+x_4, x_3+x_4 \}$.
2. We have $[S_4 : \mathsf{stab}(x_1x_2 + x_3x_4)] = 3$. A simple calculation then shows that this orbit is $\{ x_1x_2+x_3x_4, x_1x_3+x_2x_4, x_1x_4+x_2x_3 \}$.
3. We saw in a previous exercise that $\mathsf{stab}((x_1+x_2)(x_3+x_4)) = \mathsf{stab}(x_1x_2+x_3x_4)$. Thus $[S_4 : \mathsf{stab}((x_1+x_2)(x_3+x_4))] = 3$. A simple calculation then shows that this orbit is $\{ (x_1+x_2)(x_3+x_4),$ $(x_1+x_3)(x_2+x_4),$ $(x_1+x_4)(x_2+x_3) \}$.

### Compute the orbits, cycle decompositions, and stabilizers of some group actions of Sym(3)

Repeat the previous example with each of the following actions.

1. $S_3$ acting on the set $A = \{ (i,j,k) \ |\ 1 \leq i,j,k \leq 3 \}$ by $\sigma \cdot (i,j,k) = (\sigma(i), \sigma(j), \sigma(k))$
2. $S_3$ acting on the set $B$ of all nonempty subsets of $\{1,2,3\}$ by $\sigma \cdot X = \sigma[X]$.

• For $S_3$ acting on $A$:
• We compute the orbits as follows.
• $1 \cdot (1,1,1) = (2\ 3) \cdot (1,1,1) = (1,1,1)$, $(1\ 2) \cdot (1,1,1) = (1\ 2\ 3) \cdot (1,1,1) = (2,2,2)$, and $(1\ 3) \cdot (1,1,1) = (1\ 3\ 2) \cdot (1,1,1) = (3,3,3)$, so that $\mathcal{O}_1 = \{ (1,1,1), (2,2,2), (3,3,3) \}$.
• $1 \cdot (1,1,2) = (1,1,2)$, $(1\ 2) \cdot (1,1,2) = (2,2,1)$, $(1\ 3) \cdot (1,1,2) = (3,3,2)$, $(2\ 3) \cdot (1,1,2) = (1,1,3)$, $(1\ 2\ 3) \cdot (1,1,2) = (2,2,3)$ and $(1\ 3\ 2) \cdot (1,1,2) = (3,3,1)$, so that $\mathcal{O}_2 = \{ (1,1,2), (2,2,1), (3,3,2),$ $(1,1,3), (2,2,3), (3,3,1) \}$.
• $1 \cdot (1,2,1) = (1,2,1)$, $(1\ 2) \cdot (1,2,1) = (2,1,2)$, $(2\ 3) \cdot (1,2,1) = (1,3,1)$, $(1\ 2\ 3) \cdot (1,2,1) = (2,3,2)$, and $(1\ 3\ 2) \cdot (1,2,1) = (3,1,3)$, so that $\mathcal{O}_3 = \{ (1,2,1), (2,1,2), (3,2,3),$ $(1,3,1), (2,3,2), (3,1,3) \}$.
• $1 \cdot (2,1,1) = (2,1,1)$, $(1\ 2) \cdot (2,1,1) = (1,2,2)$, $(1\ 3) \cdot (2,1,1) = (2,3,3)$, $(2\ 3) \cdot (2,1,1) = (3,1,1)$, $(1\ 2\ 3) \cdot (2,1,1) = (3,2,2)$, and $(1\ 3\ 2) \cdot (2,1,1) = (1,3,3)$, so that $\mathcal{O}_4 = \{ (2,1,1), (1,2,2),$ $(2,3,3), (3,1,1),$ $(3,2,2), (1,3,3) \}$.
• $1 \cdot (1,2,3) = (1,2,3)$, $(1\ 2) \cdot (1,2,3) = (2,1,3)$, $(1\ 3) \cdot (1,2,3) = (3,2,1)$, $(2\ 3) \cdot (1,2,3) = (1,3,2)$, $(1\ 2\ 3) \cdot (1,2,3) = (2,3,1)$, and $(1\ 3\ 2) \cdot (1,2,3) = (3,1,2)$, so that $\mathcal{O}_5 = \{ (1,2,3), (2,1,3),$ $(3,2,1), (1,3,2),$ $(2,3,1), (3,1,2) \}$.

This exhausts the elements of $A$.

• We fix the labeling
 $\alpha_{1} = (1,1,1)$ $\alpha_{10} = (2,1,1)$ $\alpha_{19} = (3,1,1)$ $\alpha_{2} = (1,1,2)$ $\alpha_{11} = (2,1,2)$ $\alpha_{20} = (3,1,2)$ $\alpha_{3} = (1,1,3)$ $\alpha_{12} = (2,1,3)$ $\alpha_{21} = (3,1,3)$ $\alpha_{4} = (1,2,1)$ $\alpha_{13} = (2,2,1)$ $\alpha_{22} = (3,2,1)$ $\alpha_{5} = (1,2,2)$ $\alpha_{14} = (2,2,2)$ $\alpha_{23} = (3,2,2)$ $\alpha_{6} = (1,2,3)$ $\alpha_{15} = (2,2,3)$ $\alpha_{24} = (3,2,3)$ $\alpha_{7} = (1,3,1)$ $\alpha_{16} = (2,3,1)$ $\alpha_{25} = (3,3,1)$ $\alpha_{8} = (1,3,2)$ $\alpha_{17} = (2,3,2)$ $\alpha_{26} = (3,3,2)$ $\alpha_{9} = (1,3,3)$ $\alpha_{18} = (2,3,3)$ $\alpha_{27} = (3,3,3)$.

Now under the permutation representation $S_3 \rightarrow S_{27}$, we have

• $1 \mapsto 1$
• $(1\ 2) \mapsto (\alpha_1\ \alpha_{14})$ $(\alpha_2\ \alpha_{13})$ $(\alpha_3\ \alpha_{15})$ $(\alpha_4\ \alpha_{11})$ $(\alpha_5\ \alpha_{10})$ $(\alpha_6\ \alpha_{12})$ $(\alpha_7\ \alpha_{17})$ $(\alpha_8\ \alpha_{16})$ $(\alpha_9\ \alpha_{18})$ $(\alpha_{19}\ \alpha_{23})$ $(\alpha_{20}\ \alpha_{22})$ $(\alpha_{21}\ \alpha_{24})$ $(\alpha_{25}\ \alpha_{26})$
• $(1\ 3) \mapsto (\alpha_1\ \alpha_{27})$ $(\alpha_2\ \alpha_{26})$ $(\alpha_3\ \alpha_{25})$ $(\alpha_4\ \alpha_{24})$ $(\alpha_5\ \alpha_{23})$ $(\alpha_6\ \alpha_{22})$ $(\alpha_7\ \alpha_{21})$ $(\alpha_8\ \alpha_{20})$ $(\alpha_9\ \alpha_{19})$ $(\alpha_{10}\ \alpha_{18})$ $(\alpha_{11}\ \alpha_{17})$ $(\alpha_{12}\ \alpha_{16})$ $(\alpha_{13}\ \alpha_{15})$
• $(2\ 3) \mapsto (\alpha_2\ \alpha_3)$ $(\alpha_4\ \alpha_7)$ $(\alpha_5\ \alpha_{9})$ $(\alpha_6\ \alpha_{8})$ $(\alpha_{10}\ \alpha_{19})$ $(\alpha_{11}\ \alpha_{21})$ $(\alpha_{12}\ \alpha_{20})$ $(\alpha_{13}\ \alpha_{25})$ $(\alpha_{14}\ \alpha_{27})$ $\alpha_{15}\ \alpha_{26})$ $(\alpha_{16}\ \alpha_{22})$ $(\alpha_{17}\ \alpha_{24})$ $(\alpha_{18}\ \alpha_{23})$
• $(1\ 2\ 3) \mapsto (\alpha_1\ \alpha_{14}\ \alpha_{27})$ $(\alpha_2\ \alpha_{15}\ \alpha_{25})$ $(\alpha_3\ \alpha_{13}\ \alpha_{26})$ $(\alpha_{4}\ \alpha_{17}\ \alpha_{21})$ $(\alpha_5\ \alpha_{18}\ \alpha_{19})$ $(\alpha_6\ \alpha_{16}\ \alpha_{20})$ $(\alpha_7\ \alpha_{11}\ \alpha_{24})$ $(\alpha_8\ \alpha_{12}\ \alpha_{22})$ $(\alpha_9\ \alpha_{10}\ \alpha_{23})$
• $(1\ 3\ 2) \mapsto (\alpha_1\ \alpha_{27}\ \alpha_{14})$ $(\alpha_2\ \alpha_{25}\ \alpha_{15})$ $(\alpha_3\ \alpha_{26}\ \alpha_{13})$ $(\alpha_{4}\ \alpha_{21}\ \alpha_{17})$ $(\alpha_5\ \alpha_{19}\ \alpha_{18})$ $(\alpha_6\ \alpha_{20}\ \alpha_{16})$ $(\alpha_7\ \alpha_{24}\ \alpha_{11})$ $(\alpha_8\ \alpha_{22}\ \alpha_{12})$ $(\alpha_9\ \alpha_{23}\ \alpha_{10})$
• If $x \in \mathcal{O}_1$, then $[S_3 : \mathsf{stab}(x)] = 3$ so that $|\mathsf{stab}(x)| = 2$. In particular, consider $(3,3,3) \in \mathcal{O}_1$. Since $(1\ 2) \cdot (3,3,3) = (3,3,3)$, we have $\mathsf{stab}((3,3,3)) = \langle (1\ 2) \rangle$.

Each remaining orbit has order 6. Thus, if $x \in \mathcal{O}_k$, $2 \leq k \leq 5$, then $|\mathsf{stab}(x)| = 1$; hence $\mathsf{stab}(x) = 1$.

• For $S_3$ acting on $B$:
• We compute the orbits as follows.
• We have $1 \cdot \{1\} = (2\ 3) \cdot \{1\} = \{1\}$, $(1\ 2) \cdot \{1\} = (1\ 2\ 3) \cdot \{1\} = \{2\}$, and $(1\ 3) \cdot \{1\} = (1\ 3\ 2) \cdot \{1\} = \{3\}$. Thus $\mathcal{O}_1 = \{ \{1\}, \{2\}, \{3\} \}$.
• We have $1 \cdot \{1,2\} = (1\ 2) \cdot \{1,2\} = \{1,2\}$, $(1\ 3) \cdot \{1,2\} = (1\ 2\ 3) \cdot \{1,2\} = \{2,3\}$, and $(2\ 3) \cdot \{1,2\} = (1\ 3\ 2) \cdot \{1,2\} = \{1,3\}$. Thus $\mathcal{O}_2 = \{ \{1,2\}, \{1,3\}, \{2,3\} \}$.
• There is only one remaining element of $B$. Thus $\mathcal{O}_3 = \{ \{1,2,3\} \}$.
• We fix the labeling
 $\alpha_{1} = \{1\}$ $\alpha_{5} = \{1,3\}$ $\alpha_{2} = \{2\}$ $\alpha_{6} = \{2,3\}$ $\alpha_{3} = \{3\}$ $\alpha_{7} = \{1,2,3\}$ $\alpha_{4} = \{1,2\}$

Under the permutation representation $S_3 \rightarrow S_7$,

• $1 \mapsto 1$
• $(1\ 2) \mapsto (\alpha_1\ \alpha_2)(\alpha_5\ \alpha_6)$
• $(1\ 3) \mapsto (\alpha_1\ \alpha_3)(\alpha_4\ \alpha_6)$
• $(2\ 3) \mapsto (\alpha_2\ \alpha_3)(\alpha_4\ \alpha_5)$
• $(1\ 2\ 3) \mapsto (\alpha_1\ \alpha_2\ \alpha_3)(\alpha_4\ \alpha_6\ \alpha_5)$
• $(1\ 3\ 2) \mapsto (\alpha_1\ \alpha_3\ \alpha_2)(\alpha_4\ \alpha_5\ \alpha_6)$
• If $x \in \mathcal{O}_1$, then $[S_3 : \mathsf{stab}(x)] = 3$, so that $|\mathsf{stab}(x)| = 2$. In particular, since $(2\ 3) \cdot \{1\} = \{1\}$, we have $\mathsf{stab}(\{1\}) = \langle (2\ 3) \rangle$.

If $x \in \mathcal{O}_2$, we similarly have $|\mathsf{stab}(x)| = 2$. In particular, since $(2\ 3) \cdot \{2,3\} = \{2,3\}$, we have $\mathsf{stab}(\{2,3\}) = \langle (2\ 3) \rangle$.

Now $[S_3 : \mathsf{stab}(\{1,2,3\})] = 1$, so that $\mathsf{stab}(\{1,2,3\}) = S_3$.