[Math] Blocks in permutation group theory (D&F)

abstract-algebragroup-theorypermutations

I want to solve the following exercise from Dummit & Foote's Abstract Algebra text:

Let $G$ be a transitive permutation group on the finite set $A$. $A$ block is a nonempty subset $B$ of $A$ such that for all $\sigma \in G$ either $\sigma(B)=B$ or $\sigma(B) \cap B= \emptyset$ (here $\sigma(B)$ is the set $\{\sigma(b)\, |\,b \in B\} $).

(a) Prove that if $B$ is a block containing the element $a$ of $A$, then the set $G_B$ defined by $G_B=\{\sigma \in G\, | \, \sigma(B)=B\}$ is a subgroup of $G$ containing $G_a$.

(b) Show that if $B$ is a block and $\sigma_1(B),\sigma_2(B),\dots,\sigma_n(B)$ are all the distinct images of $B$ under the elements of $G$, then these form a partition of $A$.

(c) A (transitive) group $G$ on a set $A$ is said to be primitive if the only blocks in $A$ are the trivial ones: the sets of size 1 and $A$ itself. Show that $S_4$ is primitive on $A=\{1,2,3,4\}$. Show that $D_8$ is not primitive as a permutation group on the four vertices of a square

(d) Prove that the transitive group $G$ is primitive on $A$ if and only if for each $a \in A$, the only subgroups of $G$ containing $G_a$ are $G_a$ and $G$ (i.e., $G_a$ is a maximal subgroup of $G$, cf. Exercise 16, Section 2.4). [Use part (a).]

This is my attempt:

(a) Suppose $\sigma,\tau \in G_B$, the equality $\sigma(B)=B$ gives $B=\sigma^{-1}(B)$, and acting on this by $\tau$ gives
\begin{equation}
B=\tau(B)=\tau(\sigma^{-1}(B))=(\tau \circ \sigma^{-1})(B),
\end{equation}
so $G_B \leq G$. Moreover, if $\sigma \in G_a$ fixes $a \in B$ then $\sigma(B) \cap B \supseteq \{a\}$. Since $B$ is a block the only option is $\sigma(B)=B$. This gives $G_a \subseteq G_B$.

(b) We first prove that the images $\sigma_i(B)$ are disjoint. For suppose $\sigma_i(B) \cap \sigma_j(B)$ is nonempty for $i \neq j$. Acting on this with $\sigma_i^{-1}$ gives that the intersection $B \cap (\sigma_i^{-1} \circ \sigma_j)(B)$ is nonempty. Since $B$ is a block we must have that $(\sigma_i^{-1} \circ \sigma_j)(B)=B$. Acting on this with $\sigma_i$ gives $\sigma_i(B)=\sigma_j(B)$ which is a contradiction, since the images are known to be distinct.

We also need to show that the union of these images is $A$. Suppose by way of contradiction that there is some $a \in A$ with $a \notin \bigcup_{i=1}^n \sigma_i(B)=\bigcup_{\sigma \in G} \sigma(B)$. Since $G$ is transitive, we can find a permutation sending some $b \in B$ to $a$. It follows that $\sigma_0(B) \supseteq \sigma_0(\{b\})=\{a\}$, which is a contradiction.

(c) We prove that there are no blocks $B$ of order 2. Suppose $B=\{i,j\}$ is such a block (and the remaining elements are $k,l$). The permutation $(i \; k)$ shows $B$ is not a block. We also prove that there are no blocks of order 3. Suppose $B=\{i,j,k\}$ is such a block. The permutation $(i \; l)$ shows that $B$ is not a block. Thus the only possible orders for a block $B \subseteq A=\{1,2,3,4\}$ are 1 or 4, and $S_4$ is primitive on $A$.

Since $D_8$ acts on the set of unordered pairs of opposite vertices, we have that such a pair (for example $B=\{1,3\}$) is a block. This is because for any $g \in D_8$ we either have $g \cdot \{1,3\}=\{1,3\}=B$ or $g \cdot \{1,3\}=\{2,4\}$ is disjoint with $B$.

(d) We prove both implications:

  • Suppose for each $a \in A$, the only subgroups of $G$ containing $G_a$ are $G_a$ and $G$, and let $B \subseteq A$ be a block, and let $b$ be a point in that block. Part (a) establishes $G_B$ as a supergroup of $G_b$, and hence gives two possible cases:

    1. $G_B=G$. In that case, we claim that $B=A$, for if $B \subsetneq A$ there is some $b' \in B \setminus A$. Since $G$ is transitive, there is some permutation $\sigma \in G$ sending $b$ to $b'$. But that permutation doesn't fix $B$, which is a contradiction.

    2. $G_B=G_b$. In that case I don't know what to do…

  • The reverse implication should be here someday…

I now have several questions:

  1. Is my proof of parts (a),(b),(c) correct?

  2. Is it necessary that the set $A$ is finite? So far I didn't have to use that even once.

  3. Could anyone please help me fill in the rest? I found a solution here, but the third section from the end seems flawed to me…

Thank you!

Best Answer

I think the link you provided proves the last part correctly. The key is recognizing the correspondence between block and subgroups. Fixing $a \in A$, then there is a correspondence between \begin{align*} \{\text{subgroups } H \text{ with } G_a \subseteq H \subseteq G \} & \longleftrightarrow \{\text{subsets } B \text{ with } \{a\} \subseteq B \subseteq A\}\\ H &\longmapsto \{\sigma(a) : \sigma \in H\}\\ G_B = \{\sigma \in G : \sigma(B) = B\} \ &{\longleftarrow\!\shortmid} \ B \end{align*} which is proven in your link. We can prove part (d) using this fact.

($\Leftarrow$): To complete your argument, note that since the blocks partition $A$, we can choose a block $B$ that contains $a$. You already covered the case $G_B = G$, so suppose $G_B = G_a$. For contradiction, assume $B \neq \{a\}$ so that there is some $b \neq a$ with $b \in B$. Since $G$ is transitive, then there exists $\sigma \in G$ such that $\sigma(a) = b$. Then $b \in \sigma(B) \cap B$, so $\sigma(B) = B$. Then $\sigma \in G_B$ but $\sigma \notin G_a$, contradiction.

($\Rightarrow$): Suppose that $G$ is primitive and there is a subgroup $H$ with $G_a \subseteq H \subseteq G$. Let $B = \{\sigma(a) : \sigma \in H\}$. Since $G$ is primitive, then either $B = \{a\}$ or $B = G$. In the first case ($B = \{a\}$), then every element of $H$ stabilizes $a$, so $H = G_a$. In the latter case ($B = G$), then $H = G_B = G_A = G$ since the link proved $H = G_B$.

Related Question