Exercise 4.1.7(Primitive groups of permutations)

Proof. Let $G$ be a transitive permutation group on the finite set $A$.

(a)

Let $a\in G$, and let $B$ be a block containing $a$. We define $$G_B=\{\sigma \in G\mid \sigma (B)=B\}.$$

• By definition, $G_B\subseteq G$, and $1_G(B)=B$, thus $1_B\in G_B$, so $1_G\in G_B$ and $G_B\ne \varnothing$.
• If $\sigma \in G_B$ and $\tau \in G_B$, then $\sigma (B)=B,\tau (B)=B$, thus $(\mathit{𝜎𝜏})(B)=\sigma (\tau (B))=\sigma (B)=B$, so $\mathit{𝜎𝜏}\in G_B$.
• If $\sigma \in G_B$, then $\sigma (B)=B$, therefore $B={\sigma }^{-1}(\sigma (B))={\sigma }^{-1}(B)$, so ${\sigma }^{-1}\in G_B$.

This shows that $G_B$ is a subgroup of $G$. Moreover, since $a\in B$, if $\sigma \in G_a$, then $a=\sigma (a)\in B\cap \sigma (B)$, so $B\cap \sigma (B)\ne \varnothing$. By definition of a block, $\sigma (B)=B$, so $\sigma \in G_B$. This shows that $G_a\le G_B$.

If $B$ is a block containing the element $a$ of $A$, then $G_B$ is a subgroup of $G$ containing $G_a$.

(b)

Let $B$ be a block for $G=\{{\sigma }_1,{\sigma }_2,\dots ,{\sigma }_n\}$. We show that $\{{\sigma }_1(B),{\sigma }_2(B),\dots ,{\sigma }_n(B)\}$ is a partition of $G$.

Suppose that ${\sigma }_i(B)\ne {\sigma }_j(B)$, where $i,j\in [[1,n]]$. Then $({\sigma }_j^{-1}{\sigma }_i)(B)\ne B$. Since ${\sigma }_j^{-1}{\sigma }_i\in G$ and $B$ is a block,

$$\begin{array}{lll}\hfill ({\sigma }_j^{-1}{\sigma }_i)(B)\cap B=\varnothing .& & \hfill \text{(1)}\end{array}$$

Therefore ${\sigma }_i(B)\cap {\sigma }_j(B)=\varnothing$:

if $\gamma \in {\sigma }_i(B)\cap {\sigma }_j(B)$, then ${\sigma }_j^{-1}(\gamma )\in ({\sigma }_j^{-1}{\sigma }_i)(B)\cap B$, in contradiction with (1). So

$$\begin{array}{lll}\hfill {\sigma }_i(B)\ne {\sigma }_j(B)\Rightarrow {\sigma }_i(B)\cap {\sigma }_j(B)=\varnothing (i,j\in [[1,n]]).& & \hfill \text{(2)}\end{array}$$

It remains to prove that $\underset{1\le i\le n}{\bigcup <!--\; FUNCTION\; APPLICATION\; -->}{\sigma }_i(B)=A$.

Since $B\ne \varnothing$, consider a fixed element $a\in B\subseteq A$. Let $b$ be any element in $A$. Since $G$ acts transitively on $A$, there exists some ${\sigma }_i\in G$ such that ${\sigma }_i(a)=b$, so $b\in {\sigma }_i(G)$ for for some $i\in [[1,n]]$. Therefore

$$\begin{array}{lll}\hfill \underset{1\le i\le n}{\bigcup }{\sigma }_i(B)=A& & \hfill \text{(3)}\end{array}$$

Then (2) and (3) prove that all the distinct images of $B$ under the elements of $G$ form a partition of $A$.

Note that all the classes of this partition are blocks: consider a class $C={\sigma }_i(B)$, where ${\sigma }_i\in G$. For any $\sigma \in G$, If $\sigma (C)\ne C$, then $(\sigma {\sigma }_i)(B)\ne {\sigma }_i(B)$, so $({\sigma }_i^{-1}\sigma {\sigma }_i)(B)\ne B$. Since $B$ is a block, this shows that $({\sigma }_i^{-1}\sigma {\sigma }_i)(B)\cap B=\varnothing$. Therefore $(\sigma {\sigma }_i)(B)\cap {\sigma }_i(B)=\varnothing$: if $x\in (\sigma {\sigma }_i)(B)\cap {\sigma }_i(B)$, then ${\sigma }_i^{-1}(x)\in ({\sigma }_i^{-1}\sigma {\sigma }_i)(B)\cap B=\varnothing$, which is impossible. So $\sigma (C)\cap C=\varnothing$, for every $\sigma \in G$ such that $\sigma (C)\ne C$. This shows that $C={\sigma }_i(C)$ is a block.

(c)

We show that $S_4$ is primitive on $A=\{1,2,3,4\}$. Let $B$ be a non trivial block. Then $|B|=2$ or $|B|=3$.

• If $|B|=2$, then $B=\{a,b\}$, where $a\ne b$. Let $\{c,d\}$ be the complementary set of $B$ in $A$, so that $\{a,b,c,d\}=\{1,2,3,4\}=A$, where $a,b,c,d$ are distinct. Consider the permutation

  $$\sigma =\left(\begin{array}{cccc}\hfill a\hfill & \hfill b\hfill & \hfill c\hfill & \hfill d\hfill \\ \hfill a\hfill & \hfill c\hfill & \hfill b\hfill & \hfill d\hfill \end{array}\right)$$

  Then $\sigma (B)=\sigma (\{a,b\})=\{a,c\}\ne B$ and $\sigma (B)\cap B=\{a,c\}\cap \{a,b\}=\{a\}\ne \varnothing$. So $B$ is not a block.

• If $|B|=3$, then $B=\{a,b,c\}$ where $a,b,c$ are distinct. Let $\{d\}$ be the complementary set of $B$ in $A$, and consider the permutation

  $$\tau =\left(\begin{array}{cccc}\hfill a\hfill & \hfill b\hfill & \hfill c\hfill & \hfill d\hfill \\ \hfill a\hfill & \hfill b\hfill & \hfill d\hfill & \hfill c\hfill \end{array}\right)$$

  Then $\tau (B)=\{a,b,d\}\ne B$, and $\tau (B)\cap B=\{a,b,d\}\cap \{a,b,c\}=\{a,b\}\ne \varnothing$. So $B$ is not a block.

Since a block $B$ cannot have $2$ or $3$ elements, $B$ is a trivial block. This shows that $S_4$ is primitive on $A=\{1,2,3,4\}$.

Now we show that $D_8$ is not primitive as a permutation group on the four vertices of a square, numbered $1,2,3,4$ as in the figure p.24. Then

$$\begin{array}{llll}\hfill D_8& =⟨(1234),(13)⟩& \hfill & \\ \hfill & =\{(),(13),(1234),(13)(24),(12)(34),(14)(23),(1432),(24)\}.& \hfill & \end{array}$$

Consider the two generators $\sigma =(1234)$ and $\tau =(13)$ of $D_8$. If $B=\{1,3\}$, then $\sigma (B)=\{2,4\}$, so $\sigma (B)\cap B=\varnothing$ and $\tau (B)=B$. Since $D_8=⟨\sigma ,\tau ⟩$, for every permutation $\lambda \in D_8$, $\lambda (B)=B$ or $\lambda (B)\cap B=\varnothing$. Therefore $\{1,3\}$ is a non trivial block (and also $\{2,4\}=\sigma (B)$). This shows that $D_8$ is not primitive as a permutation group on the four vertices of a square.

(d)

Suppose that for each $a\in A$, $G_a$ is a maximal subgroup of $G$. Assume for the sake of contradiction that there is some non trivial block $B_0$. By part (b), there is a block $B={\sigma }_i(B_0)$ which contains $a$. Since $|B|=|B_0|$, $B$ is not a trivial block. By part (a), $$G_a\le G_B\le G.$$

Since $G_a$ is a maximal subgroup of $G$ by hypothesis, $G_B=G$ or $G_a=G_B$.

• If $G_B=G$, then for all $\sigma \in G$, $\sigma (B)=B$. Since $B$ is not a trivial block, $B\ne A$, so there is some $b\in A$ such that $b\notin B$. Since $G$ acts transitively on $A$, there is some ${\sigma }_0\in G$ such that ${\sigma }_0(a)=b$. Therefore $b\in {\sigma }_0(B)=B$. This is a contradiction, which proves that $G_B\ne B$.

• Therefore $G_a=G_B$. Since $|B|>1$, there is some $c\in B$ such that $c\ne a$, and since $G$ is transitive, there is some $\sigma \in G$ such that $\sigma (a)=c$, so $c\in B\cap \sigma (B)$. This shows that $B\cap \sigma (B)\ne \varnothing$. Since $B$ is a block $\sigma (B)=B$, and since $G_a=G_B$, we obtain $c=\sigma (a)=a$: this is a contradiction, which proves that there is no nontrivial block. So $G$ is primitive on $A$.

  Conversely, assume that $G$ is primitive on $A$, so that the only blocks in $A$ are the trivial ones. Let $a\in A$ and assume for the sake of contradiction that $G_a$ is not a maximal subgroup. Since $G$ is transitive, $G_a\ne G$, and $G_a$ is not maximal, so there is some subgroup $H$ of $G$ such that

  $$G_a<H<G.$$

  Consider

  $$B=\{\tau (a)\mid \tau \in H\}.$$

  We show that $B$ is a block. Let $\sigma$ be any permutation of $G$.

  • If $\sigma \in H$, then the map $\phi :H\to H$ defined by $\phi (\sigma )=\mathit{𝜎𝜏}$ is a bijection, therefore

    $$\begin{array}{lll}\hfill & \sigma (B)=\{(\mathit{𝜎𝜏})(a)\mid \tau \in H\}=\{\tau (a)\mid \tau \in H\}=B.& \hfill \text{(4)}\end{array}$$

  • If $\sigma \in G-H$, then $B\cap \sigma (B)=\varnothing$:

    if there is some $x$ such that $x\in B\cap \sigma (B)$, then $x=\tau (a)$ for some $\tau \in H$, and $x=(\mathit{𝜎𝜆})(a)$ for some $\lambda \in H$. Then

    $$\tau (a)=(\mathit{𝜎𝜆})(a).$$

    Therefore $({\lambda }^{-1}{\sigma }^{-1}\tau )(a)=a$, so $\lambda {\sigma }^{-1}\tau \in G_a$, thus ${\sigma }^{-1}\in \lambda G_a{\tau }^{-1}\subseteq H$, so ${\sigma }^{-1}\in H$, and $\sigma \in H$, in contradiction with $\sigma \in G-H$. This shows

    $$\begin{array}{lll}\hfill & B\cap \sigma (B)=\varnothing & \hfill \text{(5)}\end{array}$$

  By (4) and (5), $B$ is a block.

  By hypothesis, $H-G_a\ne \varnothing$, so there exists some permutation ${\tau }_0\in H-G_a$. Since ${\tau }_0\notin G_a$, $\tau (a)\ne a$, and $\{a,\tau (a)\}\subseteq B$, so $|B|\ge 2$. Since $G$ is primitive, this implies

  $$\begin{array}{lll}\hfill A=B=\{\tau (a)\mid \tau \in H\}.& & \hfill \text{(6)}\end{array}$$

  Since $G-H\ne \varnothing$, there is some permutation $\xi \in G-H$. Then $\xi (a)\in A$, and by (6), $\xi (a)=\tau (a)$ for some $\tau \in H$. Hence ${\tau }^{-1}\xi \in G_a$, thus $\xi \in \tau G_a\subseteq H$, which gives $\xi \in H$. Since $\xi \in G-H$, this is a contradiction, which proves that $G_a$ is a maximal subgroup of $G$.

In conclusion, $G$ is primitive on $A$ if and only if for each $a\in A$, $G_a$ is a maximal subgroup of $G$.