Problem Set 4: Products and Maps

Let $G$ be a finite group, let $X, Y$ be $G$-sets, and let $\vp: X \to Y$ be a $G$-map.

1. Prove that $\vp$ maps $G$-orbits in $X$ to $G$-orbits in $Y$.

   Solution

   Let $x \in X$. Since $\vp$ is a $G$-map, we have \[ \vp(Gx) = G\vp(x). \] Thus $\vp$ maps orbits to orbits.

2. Hence it follows that we can understand all $G$-maps by understanding the $G$-maps between transitive $G$-sets. Let $H, K \subseteq G$ be subgroups and let $g \in G$. Determine the necessary and sufficient conditions for there to exist a $G$-map $\vp : G/H \to G/K$ which sends $H \mapsto gK$.

   Solution

   If $\vp(H) = gK$ is a $G$-map, then for all $a \in G$ we have \[ \vp(aH) = a\vp(H) = agK. \] So there is at most one such $G$-map. If $h \in H$, then $hH = H$, hence applying $\vp$ we get \[ gK = \vp(H) = \vp(hH) = hgK. \] This is equivalent to $g^{-1}hg \in K$ for all $h \in H$. Hence a necessary condition is that $g^{-1}Hg \subseteq K$. Running this argument backwards, we can see this condition is also sufficient.

3. When are $G/H$ and $G/K$ isomorphic as $G$-sets?

   Solution

   The $G$-sets $G/H$ and $G/K$ are isomorphic if and only if $H$ and $K$ are conjugate subgroups. If $g^{-1}Hg = K$, then we also have $H = g K g^{-1}$. Hence the previous problem shows there is a $G$-map $\vp : G/H \to G/K$ determined by $\vp(H) = gK$ and a map $\psi : G/K \to G/H$ determined by $\psi(K) = g^{-1}H$. Thus $\psi\vp : G/H \to G/H$ is the $G$-map determined by \[ \psi\vp(H) = \psi(gK) = g\psi(K) = gg^{-1}H = H. \] The identity map $1 : G/H \to G/H$ also satisfies this, hence $\psi\vp = 1$. The identity $\vp\psi = 1$ follows similarly. Thus $\vp$ and $\psi$ are inverses, implying that $G/H \cong G/K$.

4. Recall that an automorphism of an object $X$ is an isomorphism $\vp : X \to X$. The collection $\aut(X)$ of all automorphisms of $X$ forms a group with respect to composition. Prove that the automorphism group of $G/H$ is isomorphic to $N_G(H)/H$ where $N_G(H)$ is the normalizer \[ N_G(H) = \{g \in G : g H g^{-1} = H\}. \]

   Solution

   A $G$-map $\vp : G/H \to G/H$ is determined by where it sends $H$. We know that $H \mapsto g^{-1}H$ is a $G$-map if and only if $gHg^{-1} \subseteq H$. Since $H$ is finite, this implies that $gH g^{-1} = H$. Thus we have a surjective homomorphism $\vp : N_G(H) \to \aut(G/H)$ given by $g \mapsto \vp_g : G/H \to G/H$ where $\vp_{g}$ is determined by $\vp_{g}(H) := g^{-1}H$. Note that the inverse here is important; without it we do not get a homomorphism:

   \[\begin{aligned} \varphi_{g_1}\varphi_{g_2}(H) &= \varphi_{g_1}(g_2^{-1}H)\\ &= g_2^{-1}\varphi_{g_1}(H)\\ &= g_2^{-1}g_1^{-1}H\\ &= (g_1g_2)^{-1}H\\ &= \varphi_{g_1g_2}(H). \end{aligned}\]

   The first isomorphism theorem then implies that $\aut(G/H) \cong N_G(H)/\ker(\vp)$. Observe that $g \in \ker(\vp)$ if and only if $\vp_g$ is the identity automorphism of $G/H$, if and only if $gH = H$, if and only if $g \in H$. Hence $\ker(\vp) = H$. Therefore \[ N_G(H)/H \cong \aut(G/H). \]

When we take the product of transitive $G$-sets, the result is typically not transitive anymore. The decomposition of $X \times Y$ tells us the ways in which elements of $X$ and $Y$ can relate to one another, up to symmetry.

1. For example, let $G = S_6$ and let $[6] = \{1,2,\ldots, 6\}$. (In general we write $[n] := \{1, 2, \ldots, n\}$.) Consider $X = \binom{[6]}{2}$ and $Y = \binom{[6]}{3}$ where $X$ is the set of 2 element subsets of $[6]$ and $Y$ is the set of 3 element subsets of $[6]$. Find representatives for each orbit of $S_6$ on $X \times Y$. Given a pair $(x,y) \in X \times Y$, can you succinctly describe the key feature of $x$ and $y$ which determines which orbit it belongs to?

   Solution

   The orbits are determined by the size of the overlap between $x$ and $y$. There are thus three orbits represented by

   1. $(\{1,2\}, \{3,4,5\})$
   2. $(\{1,2\}, \{2,3,4\})$
   3. $(\{1,2\}, \{1,2,3\})$.

2. Next let $G = D_6$ and let $V$ and $E$ be the sets of vertices and edges of a regular hexagon. These are both $D_6$-sets. Draw a picture to illustrate representatives for the orbits of $D_6$ on $V \times E$.

   Solution

   Fix a vertex $v_0$. Every orbit of $D_6$ on $V \times E$ contains a pair of the form $(v_0, e)$, and two such pairs $(v_0, e)$ and $(v_0, e')$ lie in the same orbit exactly when $e' = ge$ for some $g$ in the stabilizer of $v_0$. That stabilizer is $\{1, s\}$ where $s$ is the reflection across the axis through $v_0$ and $v_3$, and $s$ pairs up the six edges into three pairs. Hence there are three orbits, determined by how far the edge is from the vertex: the edge contains the vertex, the edge is one step away, or the edge is two steps away (adjacent to the opposite vertex).

   Since $|V \times E| = 36$ and $D_6$ has order $12$, each of the three orbits has exactly $12$ elements, so the stabilizer of each pair $(v_0, e)$ is trivial.

We know that every transitive $G$-set is isomorphic to $G/H$ for some subgroup $H \subseteq G$. So if $H, K \subseteq G$, how do we decompose the $G$-set $G/H \times G/K$?

1. Prove that every orbit in $G/H \times G/K$ contains an element of the form $(H,gK)$ for some $g \in G$.

   Solution

   Every element of $G/H \times G/K$ looks like $(g_1H, g_2K)$ for some $g_1, g_2 \in G$. Multiplying by $g_1^{-1}$ gives us \[ g_1^{-1}(g_1 H, g_2 K) = (H, g_1^{-1}g_2K). \] Hence let $g := g_1^{-1}g_2$, then $(H, gK)$ belongs to the orbit of $(g_1H, g_2K)$.

2. What is the stabilizer of $(H,gK)$?

   Solution

   Note that $g'$ belongs to the stabilizer of $(H,gK)$ if and only if $(g'H, g'gK) = (H,gK)$, which is equivalent to $g' \in H$ and $g^{-1}g'g \in K$. And this is equivalent to $g' \in H \cap gKg^{-1}$. Hence the stabilizer of $(H, gK)$ is $H \cap gKg^{-1}$.

3. Given an element $g \in G$ and subgroups $H, K \subseteq G$, the set \[ HgK = \{hgk : h \in H, k\in K\} \] is called a double coset. Let $H\backslash G /K$ denote the set of all double cosets $H g K$. Prove there is a bijection between $H\backslash G /K$ and the orbits of $G$ on $G/H \times G/K$. Be sure to show that your function is well-defined!

   Solution

   Let $Y := (G/H \times G/K)/G$ denote the set of $G$-orbits on this product space. Let $\psi : H\backslash G /K \to Y$ be defined by $\psi(HgK) = G (H,gK)$. If $Hg_1K = Hg_2K$, then $g_2 = hg_1k$ for some $h \in H, k \in K$. Then

   Hence $G (H, g_1K) = G(H,g_2K)$, which shows that $\psi$ is well-defined.

   Part 1 shows that $\psi$ is surjective, hence it remains to show that $\psi$ is injective. Suppose that $G(H,g_1K) = G(H,g_2K)$. Then there exists some $g \in G$ such that \[ (H, g_2K) = g(H,g_1K) = (gH,gg_1K). \] Comparing first coordinates we see that $g \in H$ and that $g_2K = gg_1K$. Thus the coset equality criteria implies that $g_2 = gg_1k$ for some $k \in K$. Hence \[ Hg_2K = Hgg_1kK = Hg_1K. \] Thus $\psi$ is a bijection.

1. What are the 0 and 1 elements in $B(G)$? Construct $G$-sets that represent them and explain why they work as additive and multiplicative identities.

   Solution

   The empty set $\emptyset$ represents the 0 element of $B(G)$ and the singleton set $\{*\}$ with the trivial $G$-action represents the 1 element. The empty set is clearly an additive identity with respect to union, and the singleton is an identity with respect to products. Finally note that $X \times \emptyset = \emptyset$ for all sets $X$, which shows that $[X]0 = 0$.

2. The isomorphism classes $[G/H]$ corresponding to each conjugacy class of subgroups $H$ form an additive basis for $B(G)$. If $G = S_3$, there are 4 conjugacy classes of subgroups represented by $H = \langle \ve\rangle$, $\langle (12)\rangle$, $\langle (123)\rangle$, and $S_3$ itself. Write \[ 1 = [S_3/S_3], \quad T_2 = [S_3/\langle (123)\rangle], \quad T_3 = [S_3/\langle (12)\rangle], \quad T_6 = [S_3/\langle \ve\rangle], \] so that $T_n$ is the class of a transitive $S_3$-set with $n$ elements, and $1$ is the multiplicative identity from the previous part. Make a multiplication table which shows the product of each pair of elements in our additive basis $1, T_2, T_3, T_6$.

   Solution

   Concretely, $1$ is a point, $T_2$ is $S_3$ acting on $\{\pm 1\}$ by sign, $T_3$ is the natural action on $\{1,2,3\}$, and $T_6$ is $S_3$ acting on itself by left multiplication. Our previous problem tells us how to decompose a product: the orbits of $S_3/H \times S_3/K$ correspond to double cosets $HgK \in H\backslash S_3/K$, and the orbit of $(H, gK)$ is isomorphic to $S_3/(H \cap gKg^{-1})$. Since $1$ is the multiplicative identity, we only need to compute the products of $T_2$, $T_3$, and $T_6$.

   • Products with $T_6$. If $H = \langle \ve \rangle$, then $H \cap gKg^{-1}$ is trivial for every $K$ and $g$, so every orbit of $S_3 \times S_3/K$ is isomorphic to $S_3$ itself. If $S_3/K$ has $n$ elements, then counting elements gives $6n = 6\cdot(\text{number of orbits})$, so there are $n$ orbits and $T_6T_n = nT_6$. Hence $T_6 T_2 = 2T_6$, $T_6T_3 = 3T_6$, and $T_6^2 = 6T_6$.
   • $T_2^2$. The subgroup $A_3 = \langle (123) \rangle$ is normal, so $A_3 \cap gA_3g^{-1} = A_3$ for every $g$ and every orbit of $S_3/A_3 \times S_3/A_3$ is isomorphic to $S_3/A_3$. There are $4/2 = 2$ orbits, so $T_2^2 = 2T_2$. (Concretely, the orbits of $S_3$ on $\{\pm 1\}^2$ are $\{(1,1), (-1,-1)\}$ and $\{(1,-1),(-1,1)\}$.)
   • $T_2T_3$. The intersection $\langle (123) \rangle \cap g\langle (12) \rangle g^{-1}$ is trivial by Lagrange's theorem, since the subgroups have orders $3$ and $2$. Thus every orbit of $\{\pm 1\} \times \{1,2,3\}$ is isomorphic to $S_3$, and since there are only $6$ elements, there is a single orbit: $T_2T_3 = T_6$.
   • $T_3^2$. The action of $S_3$ on $\{1,2,3\}^2$ has two orbits: the diagonal $\{(i,i)\}$, which is isomorphic to $\{1,2,3\}$, and the six pairs $(i,j)$ with $i \neq j$, on which $S_3$ acts freely (a permutation fixing $i$ and $j$ also fixes the third point). Thus $T_3^2 = T_3 + T_6$. In terms of double cosets, if $H = \langle (12) \rangle$ then $H \backslash S_3 / H = \{H, H(13)H\}$ with $H \cap (13)H(13)^{-1} = \langle (12) \rangle \cap \langle (23) \rangle = \langle \ve \rangle$.

   Putting this together, the multiplication table for $B(S_3)$ is: \[ \renewcommand{\arraystretch}{1.3} \begin{array}{c|cccc} \cdot & 1 & T_2 & T_3 & T_6 \\ \hline 1 & 1 & T_2 & T_3 & T_6 \\ T_2 & T_2 & 2T_2 & T_6 & 2T_6 \\ T_3 & T_3 & T_6 & T_3 + T_6 & 3T_6 \\ T_6 & T_6 & 2T_6 & 3T_6 & 6T_6 \end{array} \]

Let $\P$ be the set of all subsets of $[3]$ and let $\G$ be the set of all simple graphs² with vertex set $[3]$ (so $\G$ has $2^3 = 8$ elements, one for each subset of the three possible edges). Both are $S_3$-sets via the relabeling action. Use the notation $T_2, T_3, T_6$ from the previous problem.

1. Express $[\P]$ as a sum of basis elements of $B(S_3)$.

   Solution

   The orbit of a subset $S \subseteq [3]$ is determined by $|S|$, since $S_3$ can move any $k$-element subset to any other. The subsets $\emptyset$ and $[3]$ are fixed by all of $S_3$, so each forms an orbit isomorphic to a point. The three $1$-element subsets form one orbit, and the stabilizer of $\{1\}$ is $\langle (23)\rangle$, which is conjugate to $\langle (12) \rangle$, so this orbit is isomorphic to $S_3/\langle (12) \rangle$. The same holds for the three $2$-element subsets (take complements). Therefore \[ [\P] = 1 + T_3 + T_3 + 1 = 2 + 2T_3. \]

2. Express $[\G]$ as a sum of basis elements of $B(S_3)$.

   Solution

   Up to relabeling there are four graphs on $[3]$, determined by the number of edges: the empty graph, a single edge, a path with two edges, and the triangle. The empty graph and the triangle are fixed by $S_3$, giving two orbits isomorphic to a point. The graph with the single edge $\{1,2\}$ has stabilizer $\langle (12) \rangle$, so the three single-edge graphs form an orbit isomorphic to $S_3/\langle (12) \rangle$. Likewise the path $1 - 2 - 3$ has stabilizer $\langle (13)\rangle$, so the three paths form an orbit isomorphic to $S_3/\langle (12) \rangle$. Therefore \[ [\G] = 2 + 2T_3. \] (Alternatively: a graph on $[3]$ is the same thing as a subset of the three edges, and $S_3$ permutes the edges the same way it permutes the vertices, so $\G \cong \P$ as $S_3$-sets.)

3. A graph with terminals is a graph on $[3]$ together with a distinguished subset of its vertices (the terminals), that is, an element of $\G \times \P$. Use the multiplication table for $B(S_3)$ to express $[\G \times \P]$ as a sum of basis elements. How many graphs with terminals are there up to relabeling?

   Solution

   Using the table for $B(S_3)$ and $T_3^2 = T_3 + T_6$,

   \[\begin{aligned} [\G \times \P] &= (2 + 2T_3)(2 + 2T_3) = 4 + 8T_3 + 4T_3^2\\ &= 4 + 8T_3 + 4(T_3 + T_6) = 4 + 12T_3 + 4T_6. \end{aligned}\]

   Each basis element is a single orbit, so there are $4 + 12 + 4 = 20$ graphs with terminals up to relabeling: $4$ fixed by all of $S_3$, $12$ with orbits of size $3$, and $4$ with orbits of size $6$. As a check on the sizes, $4\cdot 1 + 12 \cdot 3 + 4 \cdot 6 = 64 = 8 \cdot 8 = |\G \times \P|$.

   As a check, we can list the orbits directly. First choose a graph $\Gamma$ from each of the four orbits of $\G$, and then the orbits of $\G \times \P$ containing $(\Gamma, S)$ correspond to the orbits of the stabilizer $\aut(\Gamma)$ on subsets $S \subseteq [3]$. The size of the orbit of $(\Gamma, S)$ in $\G \times \P$ is $6/|\aut(\Gamma) \cap \mathrm{Stab}(S)|$.

   • Empty graph, $\aut(\Gamma) = S_3$: the orbits of subsets are determined by size, giving $4$ orbits. For $S = \emptyset, [3]$ the pair $(\Gamma, S)$ is fixed by $S_3$ (orbit size $1$); for $|S| = 1, 2$ the orbit has size $3$.
   • Triangle, $\aut(\Gamma) = S_3$: exactly the same, $2$ orbits of size $1$ and $2$ of size $3$.
   • Single edge $\{1,2\}$, $\aut(\Gamma) = \langle (12)\rangle$: the subsets $\emptyset$, $\{3\}$, $\{1,2\}$, $\{1,2,3\}$ are each fixed by $(12)$ and give $4$ orbits of size $3$, while $\{1\} \sim \{2\}$ and $\{1,3\}\sim\{2,3\}$ give $2$ orbits of size $6$.
   • Path $1 - 2 - 3$, $\aut(\Gamma) = \langle (13) \rangle$: the same count, $4$ orbits of size $3$ and $2$ orbits of size $6$.

   Altogether we find $4$ orbits of size $1$, $4 + 4 + 4 = 12$ orbits of size $3$, and $2 + 2 = 4$ orbits of size $6$, for a total of $20$, exactly as predicted by $4 + 12T_3 + 4T_6$.