Of course it is exhausting, having to reason all the time
in a universe which wasn’t meant to be reasonable.
Solutions must be typeset in LaTeX and written in complete, grammatical sentences. You must list all your collaborators explicitly. Feel free to DM on Discord if you have any questions. Problems marked (Challenge) are optional but encouraged.
3.1Orbits and Coproducts
A standard method in mathematics and science for trying to understand a curious object is to break it down into its fundamental components. For example, we factor numbers into primes and decompose molecules into atoms (which we then smash apart in massive colliders). The same principle applies to $G$-sets. The following terms help us put a name to the fundamental components of $G$-sets.
Definition 3.1
Let $G$ be a group, let $X$ be a $G$-set, and let $x \in X$. The orbit of $x$ is the set \[ Gx := \{gx : g \in G\} \subseteq X, \] of all elements of $X$ which may be reached from $x$ by applying elements of $G$. We say $X$ is transitive if $X = Gx$ for some $x \in X$.
Problem 3.1
Let $G$ be a group and let $X$ be a $G$-set. Define the relation $\sim$ on $X$ by $x \sim y$ if there is an element $g \in G$ such that $y = gx$.
(Reflexive) Prove that $x \sim x$ for all $x \in X$.
Solution
Since $1x = x$ for all $x \in X$ it follows that $x \sim x$.
(Symmetric) Prove that $x \sim y$ implies $y \sim x$ for all $x, y \in X$.
Solution
If $x \sim y$, then there is some $g \in G$ such that $y = gx$. Thus $x = g\inv y$ and $g\inv \in G$ implies that $y \sim x$.
(Transitive) Prove that $x \sim y$ and $y \sim z$ together imply $x \sim z$ for all $x, y, z \in X$.
Solution
Suppose that $y = hx$ and $z = gy$. Then substitution yields
and thus $gh \in G$ implies that $x \sim z$.
(Equivariance) Prove that $x \sim y$ implies $gx \sim gy$ for all $g \in G$ and $x, y \in X$.
Solution
Let $h \in G$ be such that $y = hx$. Then
Thus $gx \sim gy$.
Prove that the following are equivalent
- $x \sim y$,
- $y \in Gx$,
- $Gx = Gy$.
Solution
If $x \sim y$, then $y = gx$ by definition. Hence $y \in Gx$. Conversely, if $y \in Gx$, then $y = gx$ for some $g \in G$ which implies $x \sim y$. Thus (a) and (b) are equivalent.
If $x \sim y$, then $y = hx$ for some $h \in G$. If $gy \in Gy$, then $gy = ghx \in Gx$. Thus $Gy \subseteq Gx$. Since $\sim$ is symmetric, we also have $y \sim x$ and thus the same argument implies $Gx \subseteq Gy$. Therefore $x \sim y$ implies $Gx = Gy$. Conversely, if $Gx = Gy$, then $1 \in G$ implies that
Hence $y \in Gx$.
A reflexive, symmetric, transitive relation is called an equivalence relation. Equivalence relations behave essentially like equality; they measure some sense of “sameness”. A collection of elements which are all equivalent to one another under an equivalence is called an equivalence class. In Problem 3.1 you showed that $G$-orbits are equivalence classes in $X$. Thus any two elements of an orbit generate the entire orbit. By construction, an orbit is closed under the action of $G$. Hence orbits are themselves $G$-sets which cannot be be broken into smaller pieces.
Problem 3.1 implies that orbits are either identical or they are disjoint. Hence every $G$-set may be expressed as a union of orbits. We may also formally construct new $G$-sets by combining various orbits. First, a digression on disjoint unions.
If $X$ and $Y$ are sets, then their union $X \cup Y$ is the smallest set that contains both $X$ and $Y$. When $X$ and $Y$ have some overlap, we may have $|X \cup Y| < |X| + |Y|$. There is a closely related operation on sets called disjoint union and denoted $X \sqcup Y$ which fixes this issue. The set $X \sqcup Y$ contains all the elements of $X$ and $Y$ together with tags that remember which set each element came from. These “tags” mean that even if the sets had some element in common, that will element will appear twice in the disjoint union, once with each label. We may construct $X \sqcup Y$ in several ways, but I like to think of it as the set of all elements of the form $a_X$ or $b_Y$ where $a \in X$ and $b \in Y$ (the subscripts are the tags). One nice feature of the disjoint union is that $|X \sqcup Y| = |X| + |Y|$ is always true.1
Definition 3.2
Let $G$ be a group and let $X, Y$ be $G$-sets. Then $G$ acts on $X \sqcup Y$ by the actions inherited from $X$ and $Y$. That is, every element $z \in X \sqcup Y$ belongs to either $X$ or $Y$ but not both, and $g \in G$ acts on $z$ depending on which set $z$ belongs to. We call $X \sqcup Y$ together with this action the coproduct or sum of $X$ and $Y$. We also write $X + Y$ as an alternative notation for $X \sqcup Y$.
Problem 3.1 implies the following result.
Proposition 3.3
Let $G$ be a group and let $X$ be a $G$-set. Then $X$ is isomorphic to a sum of transitive $G$-sets in an essentially unique way.
3.2Stabilizers and Coset Actions
Proposition 3.3 reduces the problem of classifying $G$-sets to the classification of transitive $G$-sets. The key to understanding the transitive $G$-sets lies in the concept of a stabilizer.
Definition 3.4
Let $G$ be a group, let $X$ be a $G$-set, and let $x \in X$. The stabilizer of $x$ is the set \[ G_x := \{g \in G : gx = x\} \subseteq G, \] of all elements of $G$ which leave $x$ fixed.
Problem 3.2
Let $G$ be a group, let $X$ be a $G$-set, and let $x \in X$. Prove that the stabilizer $G_x$ is a subgroup of $G$.
Solution
We show $G_x$ is closed, contains inverses, and contains the identity.
If $g, h \in G_x$, then using the definition of the stabilizer we have
Thus $gh \in G_x$.
If $g \in G_x$, then $x = gx$. Multiplying both sides by $g\inv$ we get
Thus $g\inv \in G_x$.
- By definition, $1x = x$, hence $1 \in G_x$.
Therefore $G_x$ is a subgroup.
Different points in an orbit can have different stabilizers, but they are all related to one another.
Problem 3.3
Let $G$ be a group and let $X$ be a transitive $G$-set. If $x, y \in X$, what is the relationship between $G_x$ and $G_y$? In this circumstance, $y = gx$ for some $g \in G$. Try to phrase the relationship in terms of $g$.
Solution
If $y = gx$, then the stabilizers of $x$ and $y$ are conjugates, $G_y = g G_x g\inv$. Let's prove it: Suppose $h \in G_x$. Then $x = g\inv y$ and
Thus $y = gx$ implies $g G_x g\inv \subseteq G_y$.
We also have $x = g\inv y$ which by the same reasoning gives us $g\inv G_y g \subseteq G_x$. Conjugating this containment by $g$ we have $G_y \subseteq g G_x g\inv$, which completes the proof that $G_y = g G_x g\inv$.
Thus every choice of element in a $G$-set $X$ gives rise to a corresponding subgroup $G_x$. Flipping this around we may ask: Which subgroups $H \subseteq G$ are stabilizers of an element in some $G$-set? It turns out that every subgroup is the stabilizer for some action.
Problem 3.4
Let $G$ be a group and let $H \subseteq G$ be a subgroup. Define a transitive action of $G$ on the set of left cosets $G/H$ such that $G_H = H$.
Solution
There are several possible actions, but only one that will give you the right stabilizer and that is simply left multiplication. Namely, if $kH \in G/H$ and $g \in G$, then \[ g(kH) := (gk)H. \] This action is transitive by the definition of $G/H$. The stabilizer of $H$ is, by definition
To what extent does the stabilizer of an element in a transitive $G$-set determine that $G$-set?
Problem 3.5
Let $G$ be a group and let $H \subseteq G$ be a subgroup. Classify up to $G$-set isomorphism all of the transitive $G$-sets $X$ which have an element $x \in X$ with $G_x = H$. If $G$ is finite, what does $G_x = H$ tell us about the size of $X$?
Solution
Suppose that $X$ is a transitive $G$-set and that $x \in X$ has $G_x = H$. Consider the function $f : G/H \to X$ defined by \[ f(gH) := gx. \] Since cosets have more than one representative, we first need to check that this function is well-defined. Suppose that $g_1 H = g_2 H$. Then the coset equality criteria implies that $g_1 = g_2 h$ for some $h \in H$. Since $G_x = H$ we then have
Thus $f$ is well-defined. Next we argue that $f$ is $G$-equivariant. Observe that
Hence $f$ is a $G$-map.
Our assumption that $X$ is transitive immediately implies that $f$ is surjective. Suppose that $f(g_1H) = f(g_2H)$. Then $g_1x = g_2x$ which implies that $g_2\inv g_1 x = x$. Hence $g_2\inv g_1 \in G_x = H$. Thus $g_1 = g_2 h$ for some $h \in H$ and the coset equality criteria implies that $g_1H = g_2H$. Therefore $f$ is injective. Altogether that proves $f$ is an isomorphism of $G$-sets $G/H \cong X$.
An isomorphism of $G$-sets is, in particular, a bijection. Therefore when $G$ is finite we have
If $x \in X$, then $X$ transitive implies that $X = Gx$ and $H = G_x$. Then in that case (3.0.1) reduces to \[ |G| = |Gx||G_x|, \] which is known as the orbit-stabilizer theorem. In particular, this tells us that the size of any transitive $G$-set is a divisor of the order of $G$.
3.3Examples
Let's put our theory of orbits and stabilizers into action.
Problem 3.6
The dihedral group $D_6$ naturally acts on a regular hexagon and preserves its special features. This gives us induced actions on the vertices and edges of the hexagon.
What is the stabilizer of $v_i$ for $0 \leq i \leq 5$?
Solution
The stabilizer of $v_0$ is $\langle s \rangle$. Since $r^i v_0 = v_i$, Problem 3.3 implies that the stabilizer of $v_i$ is \[ \langle r^i s r^{-i}\rangle = \langle r^{2i}s\rangle. \]
What is the stabilizer of the edge $\overline{v_0v_1}$?
Solution
The stabilizer of $\overline{v_0v_1}$ is $\langle rs\rangle$. To see that this is the correct reflection, note that $rs v_0 = r v_0 = r_1$ and $rs v_1 = r v_5 = v_0$, hence $rs$ swaps $v_0$ and $v_1$.
Problem 3.7
Let $p$ be a prime and let $\FF_p$ be the field with $p$ elements. Recall that $\gl_2(\FF_p)$ is the group of $2\times 2$ invertible matrices with entries in $\FF_p$. The group $\gl_2(\FF_p)$ naturally acts on the $\FF_p$-vector space $\FF_p^2$. Let's view $\FF_p^2$ as a space of 2-dimensional column vectors. \[ \mat a b c d \vec x y := \vec {ax + by} {cx + dy} \]
Prove that $\gl_2(\FF_p)$ acts transitively on the nonzero vectors in $\FF_p^2$.
Solution
Suppose $v := \vec a c$ is a nonzero vector. Linear algebra implies there is another nonzero vector $w := \vec b d$ such that $\{v,w\}$ forms a basis of $\FF_p^2$. Thus there is a unique invertible linear transformation $A$ which sends $Ae_1 = v$ and $Ae_2 = w$. This linear transformation is given by the matrix \[ A = \mat a b c d \in \gl_2(\FF_p). \] Since $A e_1 = v$, it follows that $\gl_2(\FF_p)$ acts transitively on nonzero vectors.
Determine the stabilizer of $e_1 := \vec 1 0$. What is the order of the stabilizer?
Solution
If $A \in \gl_2(\FF_p)$ stabilizes $e_1$, then the first column of $A$ is $e_1$. The assumption that $A \in \gl_2(\FF_p)$ is equivalent to the second column $\vec b d$ of $A$ being linearly independent of $e_1$. This reduces to $d \neq 0$ and no condition on $b$. Thus \[ \gl_2(\FF_p)_{e_1} = \Big\{\mat 1 b 0 d : d \neq 0\Big\}. \] The order of this subgroup is $p(p-1)$.
What is the order of $\gl_2(\FF_p)$?
Solution
The orbit-stabilizer theorem implies that
- Even when $X$ and $Y$ are infinite and we interpret the equation appropriately. ↩