Subgroups and cyclic subgroups

Section 5.3 Subgroups and cyclic subgroups

One of the features that makes groups such a fascinating and useful mathematical object is that they contain smaller group-like structures inside of them. These smaller pieces, called subgroups, carry the operation of the larger group, but on a smaller, self-contained set of elements.

Definition 5.3.1.

Let \(G\) be a group. A subset \(H \subset G\) is called a subgroup of \(G\) if \(H\) is a group with respect to the group operation of \(G\text{.}\)

Some obvious subgroups are the trivial subgroup \(H = \{e\}\) and the whole group \(H = G\text{.}\) Nontrivial subgroups of \(G\) are those subgroups that are neither \(\{e\}\) or \(G\text{.}\) For example, let \(G = \Z_6\text{.}\) Then the set \(H = \{0, 3\}\) is a subgroup of \(G\text{.}\)

Instead of checking the entire definition of a group each time that we want to see if a given subset \(H\) is a subgroup of \(G\text{,}\) we can take advantage of the fact that \(H\) inherits the structure of the operation on \(G\text{.}\) Essentially, then, we just need to make sure that \(H\) is closed under the group operation. That is, we need

The identity \(e \in H\text{.}\)
\(H\) closed under the group operation.
\(H\) contains an inverse for each element in \(H\text{.}\)

A convenient set of equivalent conditions is given in the following theorem.

Theorem 5.3.2. Conditions for a subgroup.

\(H\)\(G\)\(G\)

\(H\) is nonempty
\(g \in H\) and \(h \in H\) imply that \(gh \in H\text{,}\) and
\(g \in H\) implies that \(g\inv \in H\text{.}\)

Certain subgroups have an extraordinarily rigid structure, in that they are generated by a single element. We have seen this concept already in the form of the primitive roots of \(\F_p\text{.}\) In these cyclic subgroups, each element can be expressed as a power (or multiple in the additive setting) of the generator.

Definition 5.3.3.

Let \(G\) be a group. For an element \(g \in G\text{,}\) the cyclic subgroup generated by \(g\) is the set

\begin{equation} \langle g \rangle = \{x \in G: x = g^n \text{ for } n\in \Z\}.\label{eq-cyc-def}\tag{5.3.1} \end{equation}

If it is the case that \(G = \langle g \rangle\) for some element \(g\text{,}\) then \(G\) is called a cyclic group. For example, consider the group \(F_7\ad\) and the element \(3\text{.}\)

\begin{equation*} \langle 3 \rangle = \{3, 3^2 = 2, 3^3 = 6, 3^4 = 4, 3^5 = 5, 3^6 = 1\} = \F_7\ad \text{.} \end{equation*}

It is not the case that every element of a cyclic group is a generator, of course. Once again with \(G = \F_7\ad\text{,}\) consider the cyclic subgroup generated by 2.

\begin{equation*} \langle 2 \rangle = \{2, 2^2 = 4, 2^3 = 1\}. \end{equation*}

The following theorem is an important structural theorem about cyclic groups. The proof will be left as an exercise.

Theorem 5.3.4.

\(G\)\(G\)

Proof.

Left as an exercise.

There are several ways to investigate subgroups of cyclic groups using python. We're going to give an example that will compute the subgroups of \(\Z_n\) with the group operation of addition mod n. Note that every group \(\Z_n\) is generated by 1.

We will see how subgroups can be used to modify the Elgamal Digital Signature scheme to make it more computationally tractable to use.

Mathematical Cryptography