Group theory through GAP

Since the cosets of \(H\) form a partition of \(G\) intk \(g \geq 1\) parts of size \(\abs{H}\), we have \[ \abs{G} = \abs{H} \cdot k. \]

Let \(\abs{G} = n\).

If the order of \(g\) is \(k\), then the subgroup \((g)\) has \(k\) elements, so \(k \mid n\) by Lagrange's theorem.

Let \(\sigma \in S_n\). Define \(X_1\) to be \[ \left\{ 1, \sigma(1), \sigma^2(1), \dots \right\}. \] The set \(X_1\) is finite because \(X\) is finite. If \(X_1 = X\), we are done. Otherwise, let \(i \in X\) be the smallest element not in \(X_1\). Continue by induction. Define \[ \sigma_j(x) = \begin{cases} \sigma(x) & x \in X_j \\ x & x \not\in X_j \end{cases} \] Then \(\sigma = \sigma_1\sigma_2 \dots \sigma_k\).

First note that \(k \neq 1\). If \(k = 2\), we are done. Assume \(k \geq 3\). Assume that the lemma holds for \(k' < k\).

Since \(k \geq 3\), we have 4 possibilities for \(\tau_{k-1}\) and \(\tau_k\).

1. \((ab)(ab) = \operatorname{id}\)
2. \((ab)(ac) = (ac)(bc)\)
3. \((bc)(ab) = (ac)(bc)\)
4. \((cd)(ab) = (ab)(cd)\)

If case 1 holds, then \(\operatorname{id} = \tau_1\dots, \tau_k = \tau_1\tau_2 \cdots \tau_{k-2}\), so we are done by the inductive hypothesis.

If any of the remaining cases holds then we can change the last two transpositions according to the chart. This rewrites the identity as \[ \operatorname{id} = \tau_1 \cdots \tau_{k-2} \tau_{k-1}' \tau_k' \] where the symbol \(a\) doe not appear in \(\tau_k'\) but does appear in \(\tau_{k-1}'\).

Now consider the product \(\tau_{k-2} \tau_{k-1}'\). Again we have four possibilities as above. If \(\tau_{k-2} = \tau_{k-1}'\), then we are done. Otherwise we can write the identity as \[ \operatorname{id} = \tau_1 \tau_2 \cdots \tau_{k-3} \tau_{k-2}' \tau_{k-1}'' \tau_k. \] where \(a\) is fixed by the last two transpositions but not by \(\tau_{k-2}'\). We continue this process until we either find two consecutive transpositions that cancel each other out, when we are done by the inductive hypothesis, or we have an expression of the form \[ \operatorname{id} = \tau_1^{ * } \tau_2^{ * } \cdots \tau_k^{ * }, \] where \(a\) is fixed by \(t_i^{ * }\) for all \(i \geq 2\), but not by \(\tau_1^{ * }\). This contradicts the product being the identity.

Suppose \(\alpha_1 \cdots \alpha_k = \sigma = \beta_1 \cdots \beta_m\) for transpositions \(\alpha_i, \beta_j\). Then \[ \operatorname{id} = \alpha_1 \cdots \alpha_k \beta_m^{-1} \cdots \beta_k^{-1} \] is a product of transpositions. By the identity permutation parity lemma, \(k + m\) is even, therefore \(k\) and \(m\) have the same parity.

Let \(X\) be the set of all even permutations. Let \(Y\) be the set of all odd permutations.

Let \(\sigma\) be a fixed transposition (e.g. (12)). Define \[ f_\sigma : X \rightarrow Y \] as \(f_{\sigma}(\tau) = \sigma\tau\). Clearly \(f_{\sigma}\) is well-defined.

Suppose that \(f_{\sigma}(x) = f_\sigma(y)\). Then also \(\sigma x = \sigma y\), so \(x = y\), so \(f_{\sigma}\) is injective. If \(\tau\) is any element in \(Y\) then \(\sigma \tau \in X\) and \(f_{\sigma}(\sigma\tau) = \tau\sigma\tau = \tau\), so \(f_{\sigma}\) is surjective.

An exercise in the exercise sheets states that if \(H\) is a subgroup of \(G\) of index 2, then \(H\) contains all squares.

Note that the square of a 3-cycle is its inverse, which is distinct. Thus if \(A_4\) had a subgroup of index 2, it would have to contain all the 3-cycles, of which there are 8, and also the identity, so it is impossible for us to have 6 elements.

First let us observe that \(\rho_{\varphi}\) is a well-defined permutatio of the set \(X\). Let us verify that \(\rho_{\varphi}\) is a group homomorphism.

\(\rho_{\varphi}(gh)\) is a function given by \(x \mapsto x^{(gh)^{-1}}\). Thus \(\rho_{\varphi}(gh) = \rho_{\varphi}(g) \rho_{\varphi}(h)\) and hence \(\rho_{\varrho}\) is a homomorphism.

For the converse, let \(\rho : G \rightarrow S_X\) be a homomorphism. Then \((x, g) \mapsto \rho(g)(x)\) is a well-defined action. To see this, note that if \(g = \operatorname{id}_G\) then \(\rho(g) = \operatorname{Id}_{S_X}\) and thus \((x, g) \mapsto x\). The fact that the ation is associative follows from the fact that the operation in \(S_X\) is associative.

For the first part, suppose we have \(z \in x^G \cap y^G\). Then there exist \(a, b \in G\) such that \(x^a = z\) and \(y^b = z\). Then \(x^a = y^b\) so \(x = (y^b)^{a^{-1}} = y^{ba^{-1}}\) which means that \(x\) and \(y\) are in the same orbit.

To see \(G_x\) is a subgroup note that \(\operatorname{id}_G \in G_x\) and clearly if \(a, b \in G_x\) then \(a^{-1}\) and \(b^{-1}\) fix \(x\), which means that \(ab^{-1}\) fixes \(x\).

Suppose \(y = x^g\). Then

\begin{align*} h \in G_y &\iff (x^g)^h = x^g = y \\ &\iff x^{ghg^{-1}} = x \\ &\iff ghg^{-1} \in G_x \\ &\iff h \in g^{-1}G_x g. \end{align*}

Thus \(G_y = g^{-1} G_x g\).

Finally suppose \(x^g = x^h\). Then

\begin{align*} x^g = x^h &\iff x^{gh^{-1}} = x \\ &\iff gh^{-1} \in G_x \\ &\iff G_xg = G_xh \end{align*}

Note that for cosets we have \(Ha = Hb\) if and only if \(ab^{-1} \in H\)

By the previous theorem \(\varphi : x^G \rightarrow G/G_x\) given by \[ x^g \mapsto G_x g \] is bijective.

We can rewrite the expression as follows

\begin{align*} \frac{1}{\abs{G}} \sum\limits_{g \in G}^{} \operatorname{Fix}(g) &= \frac{1}{\abs{G}} \sum\limits_{x \in X}^{} \abs{G_X} \\ &= \frac{1}{\abs{G}} \sum\limits_{x \in X }^{} \frac{\abs{G}}{\abs{x^G}}\\ &= \sum\limits_{x \in X}^{} \frac{1}{\abs{x^G}} \\ &= \sum\limits_{\text{orbits}}^{} \sum\limits_{\text{elements in orbits}}^{} \frac{1}{\abs{x^G}} \\ &= \sum\limits_{\text{orbits}}^{} \cdot 1 \\ &= N \end{align*}

Since \(G\) is transitive, the number of orbits \(N\) is equal to 1. By Burnside's lemma we have \[ 1 = \frac{1}{\abs{G}} \sum\limits_{g \in G}^{} \operatorname{Fix}(g) \] Now \(\operatorname{Fix}(\operatorname{id_G}) = \abs{X}\). If every element of \(G\) fixes at least 1 point, then the right side of the equality is above 1, which is a contradiction.

Define \(f : S \times T \rightarrow ST\) by \((s, t) \mapsto st\). Then \(f\) is clearly surjective. It suffices to show that for every \(x \in ST\), we have \(\abs{f^{-1}(x)} = \abs{S \cap T}\).

We will show that \[ f^{-1}(x) = \left\{ (sd, d^{-1}t) \mid d \in S \cap T \right\}. \] Where \(x = st\). Note that \(f(sd, d^{-1}t) = sdd^{-1}t = st\).

For the other inclusion, let \((s, t)\) and \((\sigma, \tau)\) be in \(f^{-1}(x)\). That is, \(st = x = \sigma\tau\). Then \(s^{-1}\sigma = t\tau^{-1}\). Note that \(s^{-1}\sigma \in S\) and \(t \tau^{-1} \in T\), so they are both in the intersection.

Let \(d = s^{-1}\sigma = t\tau^{-1}\). Then \[ \sigma = s(s^{-1}\sigma) = sd \quad \text{and} \quad d^{-1} t = \tau t^{-1}t = \tau. \] Then \((\sigma, \tau) = (sd, d^{-1}t)\). as required, proving that \[ (\sigma, \tau) \in \left\{ (sd, d^{-1}t) \mid d \in S \cap T \right\}. \]

We have shown that \(\abs{f^{-1}(x)} = \abs{S \cap T}\), and therefore \(\abs{ST} \abs{S \cap T} = \abs{S} \abs{T}\).