Subgroups, Cosets and Lagrange’s Theorem

<style> .markdown-body code, .markdown-body tt { color: #eee; background-color: rgba(20, 230, 230, 0.36); } /* a, .open-files-container li.selected a { color: #5EB7E0; } */ </style> In this short note, we discuss subgroups, cosets and prove Lagrange's theorem. These algebraic concepts come up in various places in cryptography research and can be important to internalize. We start with some simple facts. Given a group $(G, \cdot)$, a subgroup $(H, \cdot) \leq (G, \cdot)$ has the same composition rules as the original group, has the same identity element $e$, and composition of two of its elements remains within the subgroup (closed under composition). Composition is associative and the inverse elements are part of the subgroup as well. In other words, $(H, \cdot)$ has all the properties of a group in itself. $G$ itself and $\{e\}$ are both subgroups of $G$, although $G$ is not a *proper* subgroup. Lagrange's theorem is about the orders (or cardinalities) of the subgroups of a group. Given a group $(G, \cdot)$ of order $|G|$, its subgroups cannot simply have any arbitrary order. Langrange's theorem states that the order of any subgroup $(H, \cdot)$ of $(G, \cdot)$ must have an order $|H|$, that divides $|G|$, i.e. $\exists k\in \mathbb{N}$ such that $|G|=k|H|$. This is due to the idea of cosets, (non-intersecting) partitionings of a group, associated with any one of its given subgroups. We will show that each coset in a partition associated with a subgroup has the same cardinality. Therefore, the cardinality of a coset in a partition must divide the order of the group. Further, the subgroup itself is one of the cosets of the partition associated with itself and therefore has an order that divides the order of the group as well. The notation used for a *left* coset of $H$ is $g H$. It is the set $gH = \{h\in H | g \cdot h\}$ where $g$ can be any element of $G$. If $g = e$, the identity element, then $gH = H$ and this is the only coset in the partition associated with $H$ that is a subgroup. The rest of the cosets are not groups themselves since they do not intersect with $H$ and therefore do not contain the identity element $e$, which is a requirement for being a group.  ![](https://i.imgur.com/AEeD2t9.png) In the figure above, left cosets associated with the subgroup $H$ of group $G$ are shown as an example. All the cosets have the same order $|H|$, they partition the entire group $G$, and do not intersect with each other. The only subgroup in the partition is $H=eH$ itself. Note that multiple ($|G|/|H|$ to be precise) group elements, $g^+, g^- \in G$ will map the subgroup $H$ into the same coset, $g^+H = g^-H$, in general. Further, $g_i \in g_iH$ is also easy to show, as $e\in H$. --- **An algorithm to find cosets:** In order to obtain all the left cosets associated with a subgroup $H$, we start with the identity element of the group $g_0 = e$ and a *set of cosets*, $C_H=\{g_0 H=eH=H\}$, which we will incrementally grow. At each step, we pick an element of $G$ that is not in any of the cosets in $C_H$ so far. In the first step, this corresponds to a $g_1\in G$ s.t. $g_1\notin H$. Then, the second coset associated with $H$ is chosen as $g_1H$. This is added to the set, which becomes $C_H=\{H, g_1H\}$. In the second step, we again pick an element of $G$ that is not in any of the cosets in $C_H$ so far. This corresponds to a $g_2\in G$ s.t. $g_2\notin H \cup g_1H$. Then, the third coset associated with $H$ is chosen as $g_2H$. This is added to the set as well, which becomes $C_H=\{H, g_1H, g_2H\}$. We continue this process until we run out of elements of $G$ that are not in the set of cosets so far and we end up with the set of cosets $C_H=\{H, g_1 H, ..., g_{k-1} H\}$. In the next section, we will analyze some of the properties of this resulting set to prove Lagrange's theorem we introduced earlier. --- **Lagrange's theorem:** Lagrange's theorem states that any subgroup $H$ of a group $G$ has an order that evenly divides the order of the group, i.e. $|G|/|H| = k \in \mathbb{N}$. We analyze the coset algorithm and its output to prove this theorem. Given that the algorithm generates a set of cosets associated with subgroup $H$, $C_H=\{H, g_1 H, ..., g_{k-1} H\}$, if each set within $C_H$ has the same cardinality, its elements collectively partition (meaning no intersecting) and cover the group $G$, then $|G|/|H| = k \in \mathbb{N}$ follows. **$C_H$ covers $G$:** Consider the case where $C_H$ did not cover $G$ after the algorithm terminates. In that case, there would exists a $g^+ \in G$ that is not part of any element of $C_H$ and the algorithm could not terminate as there would be another step where a new coset would be added. This leads to a contradiction. Every element of $G$ is in some coset in $C_H$. **$C_H$ partitions $G$:** It is easy to see that every element of each coset in $C_H$ is in $G$ due to the fact that groups are closed under composition. Taken together with with the fact that $C_H$ covers $G$, we can conclude that the union of all cosets in $C_H$ is simply $G$, $\cup g_iH = G$. Based on the above, in order to show that $C_H$ partitions $G$, we only need to show that these cosets are non-intersecting with each other. In other words, we need to show that $\forall (i,j) \in \{1, ..., k\}^2$ s.t. $i\neq j$, $g_iH \cap g_jH = \emptyset$, i.e. their intersection is empty. This requires some care. **Cosets in $C_H$ are non-intersecting:**: Assume that there is a common element in both $H$ and $g_1H$, i.e. $f \in H$ and $f \in g_1H$. Then, since $f \in g_1H$, there must exist another element $h\in H$ that satisfies $f = g_1 \cdot h$. Since $h$ has an inverse $h^{-1}\in H$ as well, $f\cdot h^{-1} =g_1 \cdot h \cdot h^{-1} = g_1$ should remain within the subgroup $H$ due to closure under composition. However, $g_1$ was specifically chosen to be an element of $G$ that is not an element of $H$, which leads to a contradiction. Now, assume that $H \cap g_1H = \emptyset$ but $g_1H \cap g_2H \neq \emptyset$. Then, there must be a common element $f \in g_1H$ and $f \in g_2H$. Similarly, There must exist an $h_1 \in H$ and $h_2 \in H$ that satisfy, $f = g_1 \cdot h_1$ and $f = g_2 \cdot h_2$ respectively. Then, we can consider $h_2^{-1} \in H$ and the right multiplication $f \cdot h_2^{-1} = g_1 \cdot h_1 \cdot h_2^{-1} = g_2 \cdot h_2 \cdot h_2^{-1} = g_2$. We know that $g_1 \cdot h_1 \cdot h_2^{-1} = g_2$ is an element of $g_1 H$ since $h_1 \cdot h_2^{-1}$ is in $H$. But, we specifically chose $g_2$ to be not in $H$ or $g_1 H$. This lead to a contradiction. A similar argument can be made for the case where $H \cap g_1H = \emptyset$ but $H \cap g_2H \neq \emptyset$, which similarly leads to a contradiction. Using the same argument, we can show that all cosets are non-intersecting with each other. Since the cosets in $C_H$ are non-intersecting and $\cup g_iH = G$, $C_H$ partitions $G$. **Proof of Lagrange's theorem**: Finally, we need to show that all the cosets in $C_H$ have the same cardinality $|H|$, which would imply $|G|/|H| = k \in \mathbb{N}$. Given any coset $g_iH = \{h\in H | g_i \cdot h\}$, it is clear that its cardinality cannot exceed $|H|$ from the definition. Suppose that $g_iH$ has an element $f$ that is mapped to from two different elements of the subgroup, $h_s, h_p \in H$ s.t. $h_s\neq h_p$, i.e. $f=g_i \cdot h_s = g_i \cdot h_p$. However, $g_i \in G$ has an inverse element $g_i^{-1} \in G$ that could be left multiplied with $f$ to obtain $g_i^{-1}\cdot f= g_i^{-1}\cdot g_i \cdot h_s = g_i^{-1}\cdot g_i \cdot h_p$. This would imply that $h_s = h_p$ which is a contradiction. Therefore, every unique element $h\in H$ maps to a unique element $f\in g_iH$ for all cosets $g_i$ and each coset has cardinality $|H|$. As a corollary, $|G| = k|H|$ for a $k \in \mathbb{N}$. This concludes the proof of Lagrange's theorem.