Solution to Abstract Algebra by Dummit & Foote 3rd edition Chapter 4.1 Exercise 4.1.7
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$.
Solution:
(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$.
(3) 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.
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 \cdot \{1,3\} = \{1,3\}$$ $$(1\ 2\ 3\ 4) \cdot \{1,3\} = \{2,4\}$$ $$(1\ 3)(2\ 4) \cdot \{1,3\} = \{1,3\}$$ $$(1\ 4\ 3\ 2) \cdot \{1,3\} = \{2,4\}$$ $$(1\ 3) \cdot \{1,3\} = \{1,3\}$$ $$(1\ 2)(3\ 4) \cdot \{1,3\} = \{2,4\}$$ $$(2\ 4) \cdot \{1,3\} = \{1,3\}$$ $$(1\ 4)(2\ 3) \cdot \{1,3\} = \{2,4\}$$ So that $\{1,3\}$ is a nontrivial block; hence this action is not primitive.
(4) 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$.
