2.2 Groups

A group is a concept that combines a set with a particular operation. This set can be anything - numbers, functions, molecules, etc. The operation, which is a kind of rule, takes two elements from the set and combines them to form another element within the set.

What's interesting is that the set can be very diverse. The operation, though, has to follow some specific properties to make the set work as a group. This means we can have different groups using the same set, just by changing the operation.

Let's look at a more formal definition to get a clearer picture:

def: Group

$$\begin{align*} &\sphericalangle \\ &G \in \mathcal S \\ &\cdot: G \times G \to G \\ \text{Associativity:} \,\, &\forall x, y, z \in G: (x \cdot y) \cdot z = x \cdot (y \cdot z) \\ \text{Identity:} \,\,&\exists e \in G: \forall x \in G: e \cdot x = x \cdot e = x \\ \text{Inverse:} \,\, &\forall x \in G: \exists x^{-1}\in G: x\cdot x^{-1} = x^{-1} \cdot x = e & \\ \hline \\ &(G, \cdot) - \text{group} \\ \end{align*}$$

In this definition, we used the notation $\cdot$ to denote the operation within the group. When this symbol is used, it's common to describe the group as "multiplicative." This terminology is inspired by the familiar multiplication operation in arithmetic. In this case, often the notation $1$ is used for $e$.

Alternatively, we could use the symbol $+$ to represent the operation. In such cases, the group is referred to as "additive," echoing the addition operation we all know. In this case, $e$ is denoted by $0$ and $a^{-1}$ by $-a$.

It's important to note that these are just conventions. In theory, any symbol could serve the purpose – be it $\circ$, $\odot$, or $\boxdot$. The choice of symbol is less about mathematical necessity and more about sticking to familiar and widely accepted conventions.

note

To denote that $G$ with operation $\cdot$ is a group, we'll use the notation $G \in \mathcal{G}_{(\cdot)}$ or $(G, \cdot) \in \mathcal{G}_{(\cdot)}$. Here, $\mathcal{G}_{(\cdot)}$ is the class of all groups with operation $\cdot$.

note

Sometimes we'll omit the operation symbol when it's clear from the context what the operation is. For example, instead of writing $a\cdot b$, we'll write $ab$

Group Examples

Example: Additive group of integers

In the group $(\mathbb{Z}, +)$, which pairs the set of integers with addition, the identity element is $e := 0$, and the inverse of any integer $x$ is its negative $-x$.

Example: Multiplicative group of real numbers

The set $(\mathbb{R} \setminus \{0\}, \cdot)$, which consists of all real numbers except zero combined with the multiplication operation, forms a group. In this group, the identity element is $e := 1$, as multiplying any number by 1 leaves it unchanged. The inverse of any element $x$ in this group is given by $x^{-1} = 1/x$.

Example: Multiplicative group of complex numbers

$$\begin{align*} &G:=(\mathbb{C}, \cdot) \\ &e:=1 \\ &x = re^{i\phi} \implies x^{-1} = 1/r\cdot e^{-i\phi} \\ \end{align*}$$

Example: A group of integers modulo n

The group $\Z_n$ is composed of integers ranging from $0$ to $n-1$, where $n$ represents a specified positive integer. Within this set, we can establish two distinct operations, forming two separate groups. These operations are addition ($+$) and multiplication ($\cdot$), defined as follows: first, perform the operation in the usual manner with integers, then take the result and find its remainder upon division by $n$. Since the remainder satisfies $0 \le r \le n-1$, both operations are well-defined.

These operations are commonly denoted as being performed modulo $n$.

For instance, in the group $\Z_5$, which contains the elements ${0, 1, 2, 3, 4}$, consider adding 2 and 4. The sum is 6. Dividing 6 by 5 yields a remainder of 1, therefore $2 + 4 \equiv 1 \pmod n$. Similarly, multiplying 3 and 4 gives $3 \cdot 4 \equiv 2 \pmod n$.

Example: A group of permutations of a finite set

Consider the set $X_n := {1, \ldots, n}$. We then examine all possible permutations on this set. A permutation is a bijective function $\sigma: X_n \to X_n$, where each element in $X_n$ is mapped to another element in a unique way. The collection of all such permutations $\sigma$ is denoted by $S_n$.

Now, when we combine $S_n$ with the operation of function composition, denoted as $\circ$, we get the pair $(S_n, \circ)$. This pairing is, in fact, a group. The operation $\circ$ in this context refers to applying one permutation followed by another. We'll prove that $(S_n, \circ)$ satisfies the properties of a group in a subsequent discussion.

Proposition 2.2.1: Group Properties

$$\begin{align*} &\sphericalangle \\ &(G, \cdot) \in \mathcal{G} \\ \hline \\ \text{Unique identity: }& \exists ! e \tag{a} \\ \text{Unique inverse: }&\forall x \in G: \exists ! x^{-1} \tag{b} \\ &\forall x \in G: (x^{-1})^{-1} = x \tag{c} \\ &\forall x,y \in G: (x\cdot y)^{-1} = y^{-1}\cdot x^{-1} \tag{d} \\ &\forall x, y\in G: \exists!z \in G: x \cdot z=y \tag{e} \\ &\forall x, y\in G: \exists!z \in G: z \cdot x=y \tag{f} \\ \text{Cancellation: }&x\cdot a=x\cdot b \implies a=b \tag{g} \\ \text{Cancellation: }&a\cdot x=b\cdot x \implies a=b \tag{h} \\ \end{align*}$$

Proof

a. Assume $\exists e_1, e_2 \in G \implies e_1=e_1\cdot e_2 = e_2$

b. Assume $x \in G, \exists y_1, y_2: x \cdot y_1= y_1\cdot x =e, x \cdot y_2= y_2\cdot x =e$

$$y_1 = y_1 \cdot e_1=y_1 \cdot (x \cdot y_2) = (y_1 \cdot x) \cdot y_2 = e \cdot y_2 = y_2$$

c. This means that the inverse of $x^{-1}$ is $x$ which trivially follows from $x\cdot x^{-1}=x \cdot x^{-1} = e$

d. $(x\cdot y)^{-1}=(x\cdot y)^{-1}e=(x\cdot y)^{-1}(x\cdot y \cdot y^{-1}\cdot x^{-1})=y^{-1}\cdot x^{-1}$

e. $x \cdot z = y \implies x^{-1} \cdot x \cdot z = x^{-1} \cdot y \implies z = x^{-1} \cdot y$.

Assume $\exists z_1, z_2 \in G: x \cdot z_1 =y, x \cdot z_2 =y \implies \\ x\cdot z_1 = x \cdot z_2 \implies x^{-1}\cdot x \cdot z_1 = x^{-1}\cdot x \cdot z_2 \implies z_1 = z_2$

f. Similar to e.

g. Follows from e., assuming $y=x\cdot a = x\cdot b$

h. Follows from f., assuming $y=a\cdot x = b\cdot x$

Cayley tables

Cayley tables are like a special kind of multiplication or addition table used in group theory. These tables are a simple way to show how elements in a small group combine with each other under a specific group operation, like addition or multiplication.

For example:

$$(\Z_8^*, \cdot):=(\{1, 3, 5, 7\}, \cdot) \subseteq (\Z_8, \cdot) \\ \\ \, \\ \, \begin{array}{c|cccc} & 1 & 3 & 5 & 7 \\ \hline 1 & 1 & 3 & 5 & 7 \\ 3 & 3 & 1 & 7 & 5 \\ 5 & 5 & 7 & 1 & 3 \\ 7 & 7 & 5 & 3 & 1 \\ \end{array}$$ $$(\Z_4, +) \\ \\ \, \\ \, \begin{array}{c|cccc} & 0 & 1 & 2 & 3 \\ \hline 0 & 0 & 1 & 2 & 3 \\ 1 & 1 & 2 & 3 & 0 \\ 2 & 2 & 3 & 0 & 1 \\ 3 & 3 & 0 & 1 & 2 \\ \end{array}$$

def: Group order

$$\begin{align*} &\sphericalangle \\ &G \in \mathcal{G} \\ \hline \\ &|G| - \text{group order} \end{align*}$$

In other words group order is the number of elements in the group.

note

The concept of "order," as number of elements, is used exclusively in group theory, primarily for historical reasons. In contrast, when referring to other mathematical structures such as sets, rings, and fields, the term "cardinality" is used to denote the count of elements within the set.

def: Abelian group

When a group has the additional property of commutativity in its operation, it is called an Abelian group. This is defined as follows:

$$\begin{align*} &\sphericalangle \\ &G\in \mathcal G_{(\cdot)} \\ \text{Commutativity:} \,\, &\forall x, y: x \cdot y = y \cdot x\\ \hline \\ &G-\text{abelian} \\ &G \in \mathcal{G}^{\mathcal A}_{(\cdot)} \end{align*}$$

note

Our study will primarily focus on Abelian groups. As shown in many examples, the groups of numbers are abelian. However, this is not always the case, as demonstrated by the group of permutations.

Subgroups

def: Subgroup

$$\begin{align*} &\sphericalangle \\ &M \in \mathcal{G}_{(\cdot)} \\ &H \subseteq M, H \in \mathcal{G}_{(\cdot)} \\ \hline \\ &H \subseteq_G M \,\,\, (H \text{ is a subgroup of } M) \end{align*}$$

note

The notation $\subseteq_G$ shows that $H$ is not merely a subset of the group $M$, but also a subgroup within it. This notation highlights the preservation of the group structure in $H$.

note

Alternatively, we will use the notation $\subseteq_{(G, +)}$ to provide a clearer understanding of the operation within the subgroup.

Consider a subset $H$ of a group $M$. The operation on $M$ can be naturally restricted to $H$, resulting in the operation $\cdot: H \times H \to H$, given that $H$ is a subset of $M$. This restricted operation is called a restriction.

However, certain conditions must be met for this restriction to be valid. If any of the following scenarios occur, the subset $H$ fails to form a subgroup:

1. An element of $H \times H$ maps to an element in $M \setminus H$.
2. The identity element $e$ of the group $M$ is not in $H$.
3. The inverse of an element $x \in H$ is found in $M \setminus H$.

If any of these conditions are violated, $H$ does not satisfy the group axioms and thus cannot be a subgroup of $M$. Conversely, if none of these conditions occur, $H$ indeed qualifies as a subgroup. This concept is summarized in the following proposition:

Proposition 2.2.2: Subgroup criterion 1

$$H \subseteq_G G\iff \begin{cases} e \in H & (a)\\ \forall h_1, h_2 \in H: h_1 \cdot h_2 \in H & (b) \\ \forall h \in H: h^{-1} \in H & (c) \end{cases}$$

Proof

$\implies$

Obvious

$\impliedby$

(b) implies that operation $\cdot$ is well-defined on $H$. Associativity obviously holds on the $\cdot$ restriction to $H$. Identity existence follows from (a), inverse existence follows from (c). $\square$

Proposition 2.2.3: Subgroup criterion 2

$$H\subseteq_G G\iff \begin{cases} H \neq \empty \\ \forall h, g \in H: g \cdot h^{-1} \in H \end{cases}$$

Proof

$\implies$

Obvious

$\impliedby$

$$H \ne \empty \implies \exists g \in H \implies g \cdot g^{-1} =e \in H \\ \forall h \in H: e\cdot h^{-1} = h^{-1} \in H \\ \forall h_1, h_2 \in H: h_1 \cdot (h_2^{-1})^{-1}=h_1 \cdot h_2 \in H \\$$

$\square$

Subgroup examples

Example 1

Consider a set $n\Z := \{n\cdot k, k \in \Z \}$. It is a subgroup of integers under addition: $n\Z \subseteq_{(G, +)}\Z$

Example 2

$H:=\{1, i, -1, -i\}, H \subseteq_{(G, \cdot)} \mathbb{C}$

Example 3

$\mathbb{Q} \subseteq_{(G, +)} \R \subseteq_{(G, +)} \mathbb{C}$

Example 4

$\mathbb{Q} \setminus \{0\} \subseteq_{(G, \cdot)} \mathbb{R} \setminus \{0\} \subseteq_{(G, \cdot)} \mathbb{C} \setminus \{0\}$

Finitely generated groups

Finitely generated groups serve as the fundamental building blocks in group theory. They allow construction and understanding groups by generating them from a finite set of elements and the operations applied to these elements. This approach simplifies the study of potentially complex groups by reducing them to their basic generating elements and operations.

def: Finitely generated subgroup

$$\begin{align*} &\sphericalangle \\ &L \in \mathcal{G} \\ &S \subseteq L, |S| \lt \infty \\ &\lang S \rang_G: S \subseteq \lang S \rang_G \subseteq_G L \\ &\forall M: S \subseteq M \subseteq_G L \implies \lang S \rang_G \subseteq M \\ \hline \\ &\lang S \rang_G \,\,\,\text{is a finitely generated subgroup by } S \end{align*}$$

note

In other words, $H = \lang S \rang_G$ means that $H$ is a minimal subgroup containing $S$, or the minimum element of the partially ordered set $C:=\{X: S \subseteq X \subseteq_G L\}$ with the partial order $X \leq_P Y:=X \subseteq_G Y$.

note

$\lang S \rang_G$ can be alternatively defined as a group where each element is an expression with elements of $S$ over the group operation and taking inverse.

For example, an expresion over $H=\{1, i, -1, -i\}$ is $(i \cdot 1 \cdot (-i))^{-1} \cdot(-1)$.

note

We will also use a shorthand notation $\lang s_1, ..., s_n\rang_G := \lang \{s_1, ..., s_n\} \rang_G$

Proposition 2.2.4: Finitely generated group in explicit form

$$\begin{align*} &\sphericalangle \\ &G \in \mathcal G \\ &g_1, \ldots, g_n \in G \\ \hline \\ &\lang g_1, \ldots, g_n \rang_G=\{g_1^{\alpha_1}g_2^{\alpha_2}\ldots g_k^{\alpha_k}, \alpha_i \in \Z\} \end{align*}$$

note

$g_i$ in the explicit form might not be different

Proof

$H_1: = \lang g_1, \ldots, g_n \rang_G, H_2:=\{g_1^{\alpha_1}g_2^{\alpha_2}\ldots g_k^{\alpha_k}, \alpha_i \in \Z\}$. Note that since $\{g_1, \ldots, g_n\} \subseteq H_2$, if whe prove $H_2 \subseteq_G H_1$ will mean that $H_1 = H_2$ (because $H_1$ is minimal).

Obviously $H_2 \subseteq H_1$, the set is closed under the group operation and $g_1^0 = e \in H_2$. Finally, $(g_1^{\alpha_1}g_2^{\alpha_2}\ldots g_k^{\alpha_k})^{-1}=g_k^{-\alpha_k}\ldots g_2^{-\alpha_2}g_1^{-\alpha_1}$.

$\square$

Example: Finitely generated subgroup

$\lang i \rang_G=\{1, i, -1, -i\} \subseteq_G \mathbb C \setminus \{0\}$

Cyclic Groups

The complex mathematical characteristics of cyclic groups, especially their connection to difficult problems like the discrete logarithm problem, are crucial for many cryptographic algorithms. Thus, exploring these groups is a natural next step in our study.

Before we proceed, let's first establish some useful notation for exponentiation, which will help our further discussions.

def: Exponentiation

$$\begin{align*} &\sphericalangle \\ &n \in \mathbb{N} \\ \hline \\ &x^n := \overbrace{x \cdot x \cdot ... \cdot x}^{n \text{ times}} \\ &x^{-n} := \overbrace{x^{-1} \cdot x^{-1} \cdot ... \cdot x^{-1}}^{n \text{ times}} \\ &x^0 := 1 \end{align*}$$

note

This notation works for multiplicative groups. For additive groups, will use the notation $nx=\overbrace{x + x + ... + x}^{n \text{ times}}$

Proposition 2.2.5: Exponentiation properties

$$\begin{align} &x^mx^n=x^{m+n} \tag{a} \\ &(x^m)^n=x^{mn} \tag{b} \\ &(gh)^n = (h^{-1}g^{-1})^{-n} \tag{c} \end{align}$$

Proof

Verified directly

Proposition 2.2.6: Generated group representation

$$\begin{align*} &\sphericalangle \\ &G \in \mathcal{G}_{(\cdot)} \\ \hline \\ &\lang a \rang_G=\{a^n, n \in \Z\} \end{align*}$$

Proof

Obviously $\{a^n, n \in \Z\} \subseteq \lang a \rang_G$ as $\lang a \rang_G$ contains all exponents. All we need to check is that $\{a^n, n \in \Z\}$ is a subgroup:

$$a^0 \in \lang a \rang_G \implies \lang a \rang_G \ne \empty \\ \forall g = a^m, h = a^k \in \lang a \rang_G: a^m(a^{k})^{-1}\overset{(2.2.5.b)}=a^ma^{-k}\overset{(2.2.5.a)}= \\ a^{m-k} \in \{a^n, n \in \Z\}$$

$\square$

def: Cyclic group

$$\begin{align*} &\sphericalangle \\ &G \in \mathcal{G} \\ &\exists a \in G: \lang a \rang_G=G \\ \hline \\ &G \in \mathcal{G}^{\circlearrowleft} \,\,\,(G \text{ is a cyclic group}) & \\ &a - \text{group generator} \end{align*}$$

def: Element order

$$\begin{align*} &\sphericalangle \\ &G \in \mathcal{G} \\ &a \in G \\ &A := \{n \in \N: a^{n}=e\} \\ \hline \\ &\text{ord }a:=\begin{cases} \min A &\text{if } A \ne \empty\\ \infty &\text{otherwise} \end{cases} \end{align*}$$

Proposition 2.2.7: Cyclic groups properties

$$\begin{align} &\mathcal{G}^{\circlearrowleft} \subseteq \mathcal{G}^{\mathcal A} \tag{a}\\ &H \subseteq_G G, G \in \mathcal{G}^{\circlearrowleft} \implies H \in \mathcal{G}^{\circlearrowleft} \tag{b}\\ & \text{ord}(a) = |\lang a \rang_G| \tag{c}\\ &G = \lang a \rang_G ,a^k = e \iff \text{ord}(a) \mid k \tag{d}\\ &G=\lang a \rang, \text{ord}(a) \lt \infty \implies \text{ord}(a^k)= \frac{\text{ord }a}{\text{gcd}(\text{ord}(a), k)} \hspace{0.5cm} \tag{e} \end{align}$$

Proof

a. $\forall G \in \mathcal{G}^{\circlearrowleft}, \forall g,h\in G: gh=a^ma^n\overset{(2.2.5.a)}{=}a^na^m=hg$

b.

$H = \{e\} \implies H \in \mathcal{G}^{\circlearrowleft}$.

Assume $H \ne \{e\}$, $\exists b \in H, b = a^x, x \ne 0 \implies a^{-x} \in H$. This mean that the set $X:=\{z:z > 0, a^z\in H\}$ is not empty.

Define $m:=\min X, h:= a^{m}$.

$$\forall g \in H: g=a^y=a^{mq+r}=h^qa^r, 0 \le r \lt m \\ a^r = g(h^q)^{-1} \implies a^r \in H \\ a^r \in H, m = \min X \implies (r \ge m)\vee(r=0) \\ 0 \le r \lt m \implies r = 0 \implies \forall g \in H: g = h^q \implies H=\lang h \rang_G \\$$

c.

We'll leave the case of $\text{ord }a=\infty$ as an exercise to the reader. Assume $\text{ord }a \lt \infty$.

$$\lang a \rang_G \overset{(2.2.6)}{=}\{a^n, n \in \Z\} = \{a^{\text{ord }a \cdot k + r}, k \in \Z, 0 \le r < \text{ord }a \} = \\ = \{a^{r}, 0 \le r < \text{ord }a \}$$

Assume $\exists k, n \in \N: k < n \le \text{ord }a, a^k=a^n$. That would mean that $a^{n-k}=e, 1\le k-n < \text{ord }a$ which contradicts the definition of the order. Thus, all elements of the set $\{a^{r}, 0 < r \leq \text{ord }a \}$ are distinct.

d.

$\implies$

$$n := \text{ord } a \implies \begin{cases} a^n = e \\ \forall r: 0 < r < n: a^r \ne e \end{cases}$$ $$a^k = e \implies a^{nq+r}=e, 0\le r < n \implies a^r=e \implies\\ r=0 \implies n \mid k \\$$

$\impliedby$ - obvious

e.

$m:=\text{ord}(a^k), n:= \text{ord}(a), g:=\text{gcd}(n, k)$. We want to prove $m = n/g$.

$$a^{km}=e \overset{(c)}{\implies} n \mid km \implies n/g \mid mk/g \overset{\gcd(n/g, k/g)=1}{\implies}\\ n/g \mid m \implies m\ge n/g \\ (a^{k})^{n/g}=(a^{n})^{k/g}=e \implies \text{ord }a^k= m \leq n/g$$

$\square$

Cyclic groups of integers

Recall that $\Z_n = {0, ..., n-1}$ represents a set of integers modulo $n$, where the group operation is as defined in the example above.

def: Group of units

$$\Z^*_n:=\{x \in \mathbb{Z}_n:\exists b \in \mathbb{Z}_n: x\cdot b\equiv 1 \pmod n\}$$

Example

Consider $\Z_5$:

$$1 \cdot 1\equiv 1 \pmod 5 \\ 2 \cdot 3\equiv 1 \pmod 5 \\ 3 \cdot 2\equiv 1 \pmod 5 \\ 4 \cdot 4\equiv 1 \pmod 5 \\$$

Thus we have $|\Z^*_5|=4$

def: Euler function

$$\phi(n):=|\{k \in \N: k<n, \text{gcd}(k,n)=1\}|$$

Note that $\phi(5) = 4 = |\Z^*_5|$. This equality is not coincidental, but rather a consequence of the following theorem:

Proposition 2.2.8: Group of units order

$$|\Z^*_n|=\phi(n)$$

Proof

$$\gcd(k, n) = 1 \overset{(2.1.6)}{\iff} \exists x, y \in \Z: k\cdot x+n\cdot y=1 \iff \\ \exists x \in \Z_n: kx \equiv 1 \pmod n \iff k \in \Z^*_n$$

$\square$

Theorem 2.2.9: Euler theorem

$$\begin{align*} &\sphericalangle \\ &a, n \in \N \\ &\gcd(a, n)=1 \\ \hline \\ &a^{\phi(n)} \equiv 1 \pmod n \end{align*}$$

Proof

$$a, n\in \mathbb{N}, \text{gcd}(a,n)=1 \implies a\in \Z^*_n$$

It's obvious that $\lang a \rang_G \subseteq_G \Z^*_n$, so by (2.2.17), that we'll prove a bit later, we have $|\lang a \rang_G| \mid |\Z^*_n|$

$$|\lang a \rang_G| \,|\, |\Z^*_n| \overset{(2.2.7.c)}{\implies} \text{ord a } |\, |\Z^*_n| \overset{(2.2.8)}\implies \text{ord a } |\, \phi(n) \overset{(2.2.7.d)}{\implies} \\ \implies a^{\phi(n)} = e \text{ (in } \Z_n \text{)} \implies a^{\phi(n)}\equiv1 \pmod n$$

$\square$

Corrolary 2.2.10: Fermat's little theorem

$$p \in \mathfrak{P} \implies a^{p-1}\equiv 1\pmod p$$

Proof

$\forall p \in \mathfrak{P}: \phi(p)=p-1$

$\square$

note

Fermat's Little Theorem frequently finds application in finite multiplicative groups of prime order for determining the inverse element, as it states that $a^{p-2} = a^{-1} \pmod p$.

Permutations

def: Permutation

$$\begin{align*} &\sphericalangle \\ &\sigma_n:\{1,...,n\} \leftrightarrow \{1,...,n\} \\ \hline \\ &\sigma_n \in S_n \,\,\, (\sigma \text{ is a permutation}) \end{align*}$$

In other words, permutation is a bijective mapping between two finite equal sets of integers.

note

We will represent the set of all permutations of the set $\{1, ..., n\}$ as $S_n$. Interestingly, $S_n$ forms a group (called symmetric group) under the operation of function composition. However, this particular aspect of $S_n$ being a group is not essential for our current discussion.

def: Cycle

$$\begin{align*} &\sphericalangle \\ &\sigma \in S_n \\ &\exists A \subseteq \{1, ..., n\}, A = \{a_1, ..., a_k\} \\ &\sigma(a_1) = a_2, \sigma(a_2) = a_3, ..., \sigma(a_k) = a_1\\ &\forall x\in \{1, ..., n\} \setminus {A}: \sigma(x) = x \\ \hline \\ &\sigma_n \in S_n^{\circlearrowleft} \,\,\,(\sigma \text{ is a cycle}) \\ &\sigma_n = (a_1\, a_2\, \ldots\, a_k) \end{align*}$$

def: Disjoint cycles

$$\begin{align*} &\sphericalangle \\ &\sigma = (a_1, ..., a_k) \\ &\tau = (b_1, ..., b_l) \\ &\{a_1, ..., a_k\} \cap \{b_1, ..., b_l\} = \empty \\ \hline \\ & \sigma \cap \tau = \empty \,\,\,(\sigma, \tau \text{ are disjoint cycles}) \end{align*}$$

Proposition 2.2.11: Disjoint cycles commutativity

$$\sigma \cap \tau = \empty \implies \sigma \circ \tau = \tau \circ \sigma$$

Proof

Clearly, given that cycles are disjoint, each element in the permutations $\sigma \circ \tau$ or $\tau \circ \sigma$ is influenced by only one of the permutations.

$\square$

Proposition 2.2.12: Cyclic representation

$$\forall \sigma\in S_n: \exists \{\sigma_1, ..., \sigma_k\}: \sigma=\sigma_1\circ...\circ\sigma_k, \sigma_i \in S_n^{\circlearrowleft} , \\ i\ne j \implies \sigma_i \cap \sigma_j = \empty$$

Proof

Let's make a proof by construction. Here's the algorithm for finding all $\sigma_i$:

1. $i := 1, X:=\{1, ..., n\}$
2. $a_1 := \min X$
3. $a_2 := \sigma(a_1)$
4. … until
5. $a_1 = \sigma(a_m)$
6. $\sigma_i:=(a_1,...,a_m)$
7. $X:=X \setminus \{a_1, ...,a_m\}$
8. $i:=i+1$
9. If $X \ne \empty,$ go to step 2
10. $\sigma:=\sigma_1\cdot...\cdot\sigma_{i-1}$

Note that we'll eventually reach step 5 because the set $X$ is finite and if we have $\sigma(a_k) = a_j, j<k$ then $j=1$, otherwise $\sigma(a_{j-1})=\sigma(a_{k}), j-1 \ne k$ contradicting to $\sigma$ being a bijection.

$\square$

note

We typically omit such singleton cycles, focusing only on cycles that contain more than one element. For example, instead of writing $\sigma = (1\, 4) \circ (2) \circ (3\, 5)$, where $(2)$ is a cycle with just one element, we simplify it to $\sigma = (1\, 4) \circ (3\, 5)$.

Example: Cycle

Assume $\sigma=(1\, 3\, 6)$ on a set $X:=\{1, ..., 7\}$. That means:

$$\sigma(1)=3 \\ \sigma(2)=2 \\ \sigma(3)=6 \\ \sigma(4)=4 \\ \sigma(5)=5 \\ \sigma(6)=1 \\ \sigma(7)=7 \\$$

Example: Decomposition into disjoint cycles

Consider the permutation $\sigma = (1\, 3\, 6) \circ (3\,6\, 7)$ on a set $X:=\{1, ..., 7\}$. It is important to note that these two cycles are not disjoint. Our objective is to convert this into its disjoint cycles form, following the algorithm outlined in (2.2.12).

To begin with, let's examine how we compute the values for this permutation. Each element is initially permuted using the cycle on the right, and then the outcome of this first permutation is further permuted by the cycle on the left. For instance:

$$$$

Here, we use square brackets to indicate the application of the function, distinguishing it from the parentheses used in cycle notation.

So we have:

$$\sigma(1) = (1\, 3\, 6)[(3\, 6\, 7)[1]] = (1\, 3\, 6)[1] = 3 \\ \sigma(3) = (1\, 3\, 6)[(3\, 6\, 7)[3]] = (1\, 3\, 6)[6] = 1$$

So we get $\sigma_1=(1 \, 3)$. Next:

$$X:= \{2, 4, 5, 6, 7\} \\ \sigma(2) = (1\, 3\, 6)[(3\, 6\, 7)[2]] = (1\, 3\, 6)[2] = 2 \\ \sigma_2 = (2) \\ \\$$ $$X:= \{4, 5, 6, 7\} \\ \sigma(4) = (1\, 3\, 6)[(3\, 6\, 7)[4]] = (1\, 3\, 6)[4] = 4 \\ \sigma_3 = (4) \\$$ $$X:= \{5, 6, 7\} \\ \sigma(5) = (1\, 3\, 6)[(3\, 6\, 7)[5]] = (1\, 3\, 6)[5] = 5 \\ \sigma_4 = (5) \\$$ $$X:= \{6, 7\} \\ \sigma(6) = (1\, 3\, 6)[(3\, 6\, 7)[6]] = (1\, 3\, 6)[7] = 7 \\ \sigma(7) = (1\, 3\, 6)[(3\, 6\, 7)[7]] = (1\, 3\, 6)[3] = 6 \\ \sigma_5 = (6\, 7) \\$$

Finally, by excluding 1-cycles from our consideration, we arrive at the simplified representation $\sigma = (1\, 3) \circ (6\, 7)$

This form is more advantageous than the original expression, because:

1. Cycles here are commutative
2. Only one cycle is necessary to determine the value of a single argument (either left or right)

Cosets

Cosets are very useful in understanding how groups can be broken down into simpler pieces. When we explore factor groups (discussed below), which are like simpler versions of a bigger group, cosets help us see how the original group is organized. This is really important when we're trying to find out if two groups are essentially the same in structure.

def: Coset

$$\begin{align*} &\sphericalangle \\ &H \subseteq_G G \\ &g \in G \\ \hline \\ \text{Left coset } &gH := \{gh, h \in H\} \\ \text{Right coset } &Hg := \{hg, h \in H\} \end{align*}$$

note

In the case of an Abelian group, where the operation is commutative, the left coset and right coset are identical. Consequently, in such contexts, we simply refer to them as a coset.

note

We have used a shorthand notation for group operations, which will be frequently utilized hereafter. In this notation, rather than expressing the operation as $h \cdot g$, we simply denote it as $hg$. This principle is also applicable to cosets.

However, when the operation in the group is explicitly stated, such as in the case of an additive group, the coset notation is adapted accordingly. For example, in the context of an additive group, the coset would be denoted as $g+H$.

Example: $n\Z$

Consider $H:=n\Z, G:=\Z, g:=1$. Then the coset $g+H=\{1+nk, k \in \Z\}$

Example: $\Z_6$

If $H:=\{0, 3\}, G:=\Z_6$, then $0+H = \{0,3\}, 1+H = \{1, 4\}, 2+H=\{2, 5\}$

Example: $\mathbb{C}$

$H:=\{1, i, -1, -i\}, G:=\mathbb{C}, H\subseteq_{(G, \cdot)} G$. Then we have infinite number of cosets. Some examples are $2H = \{2, 2i, -2, -2i\}, iH = H, -1H=H$.

It is obvious that, in many instances, distinct elements of a group often result in identical cosets. Below, we present a criterion that establishes the conditions for coset equality:

Proposition 2.2.13: Coset equality criteria

$$\begin{align*} &\sphericalangle \\ &H \subseteq_G G \\ &g_1, g_2 \in G & \\ \hline \\ &\text{The following are equivalent:} \\ &g_1H = g_2H \tag{a}\\ &Hg_1^{-1} = Hg_2^{-1} \tag{b}\\ &g_2 \in g_1H \tag{c}\\ &g_1^{-1}g_2 \in H \tag{d} \\ &g_1H \subseteq g_2H \tag{e}\\ \end{align*}$$

Proof

(a) $\implies$ (b)

$$g_1h_1=g_2h_2 \iff (g_1h_1)^{-1}=(g_2h_2)^{-1} \iff \\ h_1^{-1}g_1^{-1}=h_2^{-1}g_2^{-1} \iff h_3g_1^{-1}=h_4g_2^{-1}$$

(b) $\implies$ (c)

$$h_1g_1^{-1}=h_2g_2^{-1} \implies g_1h_1^{-1}=g_2h_2^{-1} \implies g_2=g_1h_1^{-1}h_2$$

(c) $\implies$ (d)

$$g_2 = g_1h_1 \implies g_1^{-1}g_2=h_1$$

(d) $\implies$ (e)

$$g_1^{-1}g_2=h_1 \implies g_1=g_2h_1^{-1} \implies \\\forall h_2 \in H: \exists h_3 \in H: g_1h_2=g_2h_1^{-1}h_2=g_2h_3$$

(e) $\implies$ (a)

$g_1 \in g_1H, g_1H \subseteq g_2H \implies g_1 \in g_2H \implies g_1 = g_2h \implies \\ g_2 = g_1h^{-1} \implies g_2h_1=g_1h^{-1}h_1 \implies g_2H \subseteq g_1H$

$\square$

Proposition 2.2.14: Cosets partition

$$\begin{align*} &\sphericalangle \\ &H \subseteq_G G \\ \hline \\ &\forall g_1, g_2 \in G: (g_1H=g_2H) \vee (g_1H\cap g_2H =\empty) \tag{a}\\ &\bigcup_{g \in G}gH = G \tag{b} \end{align*}$$

Proof

a.

$$g_1H\cap g_2H \neq\empty \implies \exists a: a=g_1h_1=g_2h_2 \implies \\ g_2 = g_1h_1h_2^{-1} \in g_1H \overset{(2.2.13.c)}\implies g_1H=g_2H$$

b. Obvious (assume $h=e$)

Proposition 2.2.15: Number of left and right cosets

$$\begin{align*} &\sphericalangle \\ &H \subseteq_G G \\ &C_l:=\{gH, g\in G\} \\ &C_r:=\{Hg, g\in G\}: \\ \hline \\ &|C_l| = |C_r| \end{align*}$$

Proof

Consider a mapping $\phi: C_l \to C_r$, defined by $gH \mapsto Hg^{-1}$. Our goal is to demonstrate that this mapping is bijective.

$$Hg_1^{-1}=Hg_2^{-1} \overset{(2.2.13)}\iff g_1H=g_2H$$

Thus $\phi$ is well-defined and injective.

Lastly, it is surjective since for every element $Hg$ in $C_r$, there exists a pre-image under $\phi$, which is $\phi^{-1}(Hg) = g^{-1}H$.

$\square$

Given that the number of left and right cosets of a group are equal, we can introduce the following definition:

def: Subgroup index

$$\begin{align*} &\sphericalangle \\ &H \subseteq_G G \\ \hline \\ &[G:H] := |\{gH, g \in G\}|=|\{Hg, g \in G\}| \,\,\, \end{align*}$$

In other words, Subgroup index of $H$ is a number of different cosets formed by $H$.

Example: Subgroup index in $\Z_6$

Consider $H = \{0, 3\}, H \subseteq_G \Z_6$. Then $[\Z_6:H] = 3$, because we have 3 cosets that partition $\Z_6: H, 1+H, 2+H$.

Example: Subgroup index in $\mathbb C$

$H = \{1, i, -1, -i\}, H \subseteq_G \mathbb{C} \setminus \{0\} \implies |\mathbb{C}:H| = \infty$

Lemma 2.2.16: Coset size

$$\begin{align*} &\sphericalangle \\ &H \subseteq_G G \\ &\phi_g: H \to gH, h \mapsto gh \\ \hline \\ &\phi_g: H \leftrightarrow gH \tag{a} \\ &|gH| = |H| \tag{b} \\ &\forall g_1, g_2 \in G: |g_1H| = |g_2H| \tag{c} \\ \end{align*}$$

Proof

a.

$$\phi_g(h_1)=\phi_g(h_2) \implies gh_1 = gh_2 \overset{(2.2.1.g)}{\implies} h_1 = h_2 \implies \phi_g: H \overset{1-1}{\to} gH$$ $$\forall a \in gH:a =gh, \phi_g^{-1}(a)=h \in H \implies \phi_g(H)=gH$$

b., c.

Follows immediately from a.

Theorem 2.2.17: Lagrange

$$\begin{align*} &\sphericalangle \\ &H \subseteq_G G \\ &|G| \lt \infty \\ \hline \\ &[G:H]=|G|/|H| \end{align*}$$

Proof

From (2.2.15), (2.2.16) we know that $G$ is divided into $[G:H]$ partitions, each having $|H|$ elements. Hence $|G| = [G:H]\cdot |H|$

$\square$

Corrolary 2.2.18: Subgroup order

$$\begin{align*} &\sphericalangle \\ &H \subseteq_G G \\ &|G| \lt \infty \\ \hline \\ &|H| \mid |G| \text{ (order of } H \text{ divides order of } G \text{)} \end{align*}$$

Proof

Follows from (2.2.17)

Corrolary 2.2.19: Group of prime order is cyclic

$$\begin{align*} &\sphericalangle \\ &G \in \mathcal{G} \\ &|G| \in \mathfrak{P} \\ \hline \\ &G \in \mathcal{G}^{\circlearrowleft} \\ &\forall g \in G, g \ne e: G = \lang g \rang_G \end{align*}$$

Proof

$$g \in G, g \ne e \overset{(2.2.18)}{\implies} |\lang g \rang_G|\, | \,|G| \overset{|G| \in \mathfrak{P}}{\implies} |\lang g \rang_G|\, = \,|G| \implies \lang g \rang_G = G$$

$\square$

Factor groups and Normal subgroups

Factor groups and normal subgroups are important in the study of abstract algebra, particularly in the context of isomorphisms and extensions within groups, rings, and fields. These concepts will be heavily utilized in the upcoming sections of our discussion, so it's essential to having a firm understanding of these concepts.

def: Normal subgroup

$$\begin{align*} &\sphericalangle \\ &H \subseteq_G M \\ &\forall g \in M: gH = Hg \\ \hline \\ &H \lhd_G M \,\,\, (H \text{ is a normal subgroup of } M) \end{align*}$$

Example: Normal subgroup in $\R^2$

Consider a group $(\R^2, +)$ and it's subgroup $H:=\{(x, 0), x \in \R \}$. It's normal, since obviously $\forall g \in G: g + H = H + g$.

Example: Not normal subgroup in $S_3$

Consider $S_3$ - a set of permutations of the set $\{1, 2, 3\}$.

First let $H:=\{e, (1\, 2)\}, H \subseteq_G G$:

$$(1\, 2\, 3)H = \{(1\, 2\, 3), (1\, 3)\} \ne \{(1\, 2\, 3), (2\, 3)\}=H(1\, 2\, 3)$$

Thus, $H$ is not a normal subgroup of G.

Now consider $N:=\{e, (1\, 2\, 3), (1\, 3\, 2)\}, N \subseteq_G G$:

$$(1\, 2)N = N(1 \, 2) = \{(1 \, 2), (1 \, 3), (2 \, 3)\} \\ (1\, 3)N = N(1 \, 3) = \{(1 \, 2), (1 \, 3), (2 \, 3)\} \\ (2\, 3)N = N(2 \, 3) = \{(1 \, 2), (1 \, 3), (2 \, 3)\} \\ (1\, 2\, 3)N = N(1\, 2 \, 3) = N \\ (1\, 3\, 2)N = N(1\, 3 \, 2) = N \\ eN = Ne = N \\$$

So $N \lhd_GG$.

Proposition 2.2.20: Abelian group has only normal subgroups

$$\begin{align*} &\sphericalangle \\ &G \in \mathcal{G}^{\mathcal A} \\ &H \subseteq_G G \\ \hline \\ &H \lhd_G G \end{align*}$$

Proof

Obvious

Proposition 2.2.21: Normal group criteria

$$\begin{align*} &\sphericalangle \\ &G \in \mathcal{G} \\ &N \subseteq_G G \\ \hline \\ &\text{The following are equivalent}: \\ &\begin{align} &N \lhd_G G \tag{a} \\ &\forall g \in G: gNg^{-1} \subseteq N \hspace{1cm} \tag{b} \\ &\forall g \in G: gNg^{-1} = N \tag{c} \\ \end{align} \end{align*}$$

Proof

$(a) \implies (b)$

$$\forall g \in G: gN = Ng \implies \forall n_1 \in N: \exists n_2 \in N: gn_1 = n_2g \implies \\ gn_1g^{-1}=n_2 \implies gNg^{-1} \subseteq N$$

$(b) \implies (c)$

Fix some $g \in G$:

$$\forall n \in N: \exists n_2 \in N:g^{-1}ng = g^{-1}n(g^{-1})^{-1} \overset{g^{-1}N(g^{-1})^{-1} \subseteq N}{=} \\ n_2 \in N \implies n = gn_2g^{-1} \implies N \supseteq gNg^{-1}$$

$(c) \implies (a)$

Fix some $g \in G$:

$$\forall n \in N: \exists n_2 \in N: gng^{-1}=n_2 \implies gn=n_2g \implies gN \subseteq Ng \\ \forall n_2 \in N: \exists n \in N: gng^{-1}=n_2 \implies gn=n_2g \implies gN \supseteq Ng$$

$\square$

def: Factor group

$$\begin{align*} &\sphericalangle \\ &K \in \mathcal{G} \\ &N \lhd_G K \\ &K/N:=(\{gN, g \in K\}, \cdot:g_1N \cdot g_2N \mapsto g_1g_2N) \\ \hline \\ &K/N - \text{factor group} \\ \end{align*}$$

Proposition 2.2.22: Factor group is a group

$$\begin{align*} &\sphericalangle \\ &G \in \mathcal{G} \\ &N \lhd_G G \\ \hline \\ &\begin{align*} &G/N \in \mathcal G \tag{a} \\ &|G/N| = [G:N] \hspace{1cm} \tag{b} \end{align*} \end{align*}$$

Proof

a.

First, we need to establish that the group operation $\cdot$ on $G/N$ is well-defined. That is $\forall a, b, c, d \in G: aN=bN, cN=dN$, we have $aN\cdot cN = bN\cdot dN$

$$aN=bN, cN=dN \implies \exists n_1, n_2 \in N: a=bn_1, c=dn_2 \implies \\ aN\cdot cN =acN = bn_1dn_2N = bn_1dN\overset{N \lhd_G G }{=}bn_1Nd=bNd=bdN= \\ = bN \cdot dN$$

Associativity is obvious, identity is $N$, $(gN)^{-1} := g^{-1}N$.

b. Obvious by definition of $[G:N]$

$\square$

note

It's important to note that a subgroup must be normal for the concept of a factor group to be meaningful. The significance of normal subgroups will be further developed in the section discussing isomorphisms.

Example: $\Z/n\Z$

A factor group $\Z/n\Z = \{n\Z, 1+n\Z, ..., n-1+n\Z\}$. Note that it's very similar to the group $(\Z_n, +)$. Actually, we will establish below that these groups are isomorphic.

Example: $\R^2/(y=0)$

Consider a group $(\R^2, +)$ and it's subgroup $H:=\{(x, 0), x \in \R \}$. $\R^2/H = \{a+H, a \in \R\}$. Thus, $R^2/H$ is very similar to $\R$.

Homomorphisms

Homomorphisms offer insights into the nature and relationships of groups. Homomorphisms are particularly useful in identifying and exploring underlying similarities between different groups.

def: Group homomorphism

$$\begin{align*} &\sphericalangle \\ &G_1 \in \mathcal G_{(\cdot)} \\ &G_2 \in \mathcal G_{(\circ)} \\ &\phi: G_1 \to G_2 \\ &\forall g, h \in G_1: \phi(g \cdot h) = \phi(g)\circ \phi(h) \\ \hline \\ &\phi: G_1 \rightsquigarrow_G G_2 \text{ or } G_1 \overset{\phi}{\rightsquigarrow}_G G_2\,\,\,\\ &(\phi \text{ is a homomorphism from } G_1 \text{ to } G_2) \end{align*}$$

Example: Homomorphism from integers to any group

$\phi: (\Z, +) \to G, n \mapsto g^{n}$. We can easily check that $\phi(n_1 + n_2) = g^{n_1 + n_2} = g^{n_1} \cdot g^{n_2} = \phi(n_1) \cdot \phi(n_2)$. Thus, $(\Z, +) \overset{\phi}{\rightsquigarrow}_G G$

Example: Homomorphism of real and complex numbers

$\phi: (\R, +) \to (\mathbb{C}, \cdot), x \mapsto e^{ix}$. Similarly to the example above, $(\mathbb{R}, +) \overset{\phi}{\rightsquigarrow}_G (\mathbb{C}, \cdot)$

Proposition 2.2.23: Homomorphisms properties

$$\begin{align*} &\sphericalangle \\ &G_1, G_2 \in \mathcal G \\ &G_1 \overset{\phi}{\rightsquigarrow}_G G_2 \\ \hline \\ &\begin{align*} & \phi(e_1)=e_2 \tag{a}\\ & \forall g \in G_1: \phi(g^{-1})=\phi(g)^{-1} \tag{b}\\ & H_1 \subseteq_G G_1 \implies \phi(H_1) \subseteq_G G_2 \tag{c}\\ & H_2 \subseteq_G G_2 \implies \phi^{-1}(H_2) \subseteq_G G_1 \tag{d}\\ & H_2 \lhd_G G_2 \implies \phi^{-1}(H_2) \lhd_G G_1 \tag{e}\\ \end{align*} \end{align*}$$

Proof

a.

$$e_2\phi(e_1)=\phi(e_1)=\phi(e_1e_1)=\phi(e_1)\phi(e_1) \implies e_2=\phi(e_1)$$

b.

$$\phi(g^{-1})\phi(g)=\phi(g^{-1}g)=\phi(e_1)=e_2 \implies \phi(g^{-1})=\phi(g)^{-1}$$

c.

$$(a) \implies \phi(H_1) \ne \empty \\ \forall x, y \in \phi(H_1):\exists a, b\in H_1:\phi(a)=x, \phi(b)=y \\ xy^{-1}=\phi(a)\phi(b)^{-1} = \phi(ab^{-1}) \in \phi(H_1)\overset{(2.2.3)}{\implies} \square$$

d.

$$H_1:=\phi^{-1}(H_2) \\ (a) \implies e_1 \in H_1 \\ a, b \in H_1 \implies \phi(ab^{-1})=\phi(a)\phi(b)^{-1}\in H_2 \implies ab^{-1} \in H_1 \overset{2.2.3}{\implies} \square$$

e.

$$H_2 \lhd_G G_2 \\ H_1:=\phi^{-1}(H_2) \\ g, h \in H_1: \phi(g^{-1}hg)=\phi(g)^{-1}\phi(h)\phi(g) \in H_2 \implies g^{-1}hg \in H_1 \implies \square$$

$\square$

def: Homomorphism kernel

$$\begin{align*} &\sphericalangle \\ &G_1, G_2 \in \mathcal G \\ &G_1 \overset{\phi}{\rightsquigarrow}_G G_2 \\ \hline \\ &\ker \phi:= \phi^{-1}(e_2) \end{align*}$$

Example: Kernel of $\R \rightsquigarrow \mathbb C$

$\phi: (\R, +) \to (\mathbb{C}, \cdot), x \mapsto e^{ix}$. Then $\ker \phi=\{2\pi n, n \in \Z\}$

Proposition 2.2.24: Homomorphism kernel is a normal subgroup

$$\begin{align*} &\sphericalangle \\ &G_1, G_2 \in \mathcal G \\ &G_1 \overset{\phi}{\rightsquigarrow}_G G_2 \\ \hline \\ &\ker \phi \lhd_G G_1 \end{align*}$$

Proof

Follows trivially from (2.2.23.e)

$\square$

Proposition 2.2.25: Injective homomorphism

$$\begin{align*} &\sphericalangle \\ &G_1, G_2 \in \mathcal G \\ &G_1 \overset{\phi}{\rightsquigarrow}_G G_2 \\ &\ker \phi = \{e\} \\ \hline \\ &\begin{align*} &\phi: G_1 \overset{1-1}{\to}G_2 \tag{a}\\ &\phi: G_1 \leftrightarrow \phi(G_1) \hspace{1cm} \tag{b}\\ \end{align*} \end{align*}$$

Proof

a.

$$\phi(a) =\phi(b) \implies \phi(a)\phi(b)^{-1} = e \implies \\ \phi(ab^{-1})=e \implies ab^{-1}=e \implies a = b$$

b.

Obvoius from (a)

$\square$

note

Ocasionally, we will use the notation $\ker \phi = \{e\}$ to denote injective homomorphism.

Example: Homomorphisms from $\Z_5$ to $\Z_9$

Let's determine what homomorpisms we can build from $\Z_5$ to $\Z_9$. We know that $\ker \phi$ is should be a subgroup of $\Z_5$. $\Z_5$ has only two subgroups - $\{0\}$ and $\Z_5$ by $(2.2.18)$. If $\ker \phi = 0$ then by $(2.2.25)$ $\phi$ is injective and $|\phi(\Z_5)|=|\Z_5|=5$. But by $(2.2.23.c)$ - $\phi(\Z_5) \subseteq_G \Z_9$. But this is impossible by $(2.2.18)$.

Than means that $\Z_5 \overset{\phi}{\rightsquigarrow}_G \Z_{9} \implies \phi: x \mapsto 0$

def: Natural homomorphism

$$\begin{align*} &\sphericalangle \\ &G \in \mathcal G \\ &H \lhd_G G \\ &\phi: G \to G/H, g \mapsto gH \\ \hline \\ &\phi - \text{natural homomorphism} \end{align*}$$

note

It's easy to see that $\phi$ is indeed a homomorphism.

$$\phi(g_1g_2)=g_1g_2H=g_1Hg_2H=\phi(g_1)\phi(g_2)$$

Isomorphisms

Isomorphisms take homomorphisms a step further showing two groups are fundamentally the same in structure, despite possible differences in their presentation or elements.

def: Group isomorphism

$$\begin{align*} &\sphericalangle \\ &G_1, G_2 \in \mathcal G \\ &G_1 \overset{\phi}{\rightsquigarrow}_G G_2 \\ &G_1 \overset{\phi}{\leftrightarrow} G_2 \\ \hline \\ &\phi: G_1 {\cong}_G G_2 \text{ or } G_1 \overset{\phi}{\cong}_G G_2 \\ &\phi - \text{isomorphism between } G_1 \text{ and } G_2 \\ &\text{(or } G_1 \text{ is isomorphic to } G_2 \text{)} \end{align*}$$

note

Two isomorphic groups can be seen as the same group, but just in different forms or with different elements. This is because everything important about how the groups work — the rules and relationships between elements — is exactly the same in both. This concept is very useful because it allows us to study one group and apply what we learn to its isomorphic counterpart, saving time and effort in understanding different groups with similar structures.

Example: Integers and complex numbers

$\Z_4 \overset{\phi}{\cong}_G \lang i \rang_G, \phi: n \mapsto i^n$. Obviously $\Z_4 \overset{\phi}{\leftrightarrow} \lang i \rang_G$. $\phi(m+n)=i^{m+n}=i^{m}i^{n}=\phi(m)\phi(n)$.

Example: Integers and cartesian product of integers

$\Z_8^*=\{1, 3, 5, 7\} \overset{\phi}{\cong}_G (\Z_2, +) \times (\Z_2, +)$.

$$\phi(1) = (0, 0) \\ \phi(3) = (0, 1) \\ \phi(5) = (1, 0) \\ \phi(7) = (1, 1)$$

It can be clearly seen from the Cayley tables that these two groups are actually the same.

$$\Z_8^*: \begin{array}{c|cccc} & 1 & 3 & 5 & 7 \\ \hline 1 & 1 & 3 & 5 & 7 \\ 3 & 3 & 1 & 7 & 5 \\ 5 & 5 & 7 & 1 & 3 \\ 7 & 7 & 5 & 3 & 1 \\ \end{array} \\ \, \\ \\ (\Z_2, +) \times (\Z_2, +): \begin{array}{c|cccc} & (0,0) & (0,1) & (1,0) & (1,1) \\ \hline (0,0) & (0,0) & (0,1) & (1,0) & (1,1) \\ (0,1) & (0,1) & (0,0) & (1,1) & (1,0) \\ (1,0) & (1,0) & (1,1) & (0,0) & (0,1) \\ (1,1) & (1,1) & (1,0) & (0,1) & (0,0) \\ \end{array}$$

Proposition 2.2.26: Isomorphism properties

$$\begin{align*} &\sphericalangle \\ &G_1, G_2 \in \mathcal G \\ & G_1 \overset{\phi}{\cong}_G G_2 \\ \hline \\ &\begin{align} &G_2 \overset{\phi^{-1}}{\cong}_G G_1\tag{a} \\ &|G_1| = |G_2| \tag{b} \\ &G_1 \in \mathcal{G}^{\mathcal A} \implies G_2 \in \mathcal{G}^{\mathcal A}\tag{c} \\ &G_1 \in \mathcal{G}^{\circlearrowleft} \implies G_2 \in \mathcal{G}^{\circlearrowleft}\tag{d} \\ &\forall H_1 \subseteq_G G_1: \exists H_2 \subseteq_G G_2: |H_1| = |H_2|\tag{e} \hspace{1cm} \\ \end{align} \end{align*}$$

Proof

a.

$$\forall g_2, h_2 \in G_2: \exists g_1, h_1 \in G_1: \phi(g_1)=g_2, \phi(h_1)=h_2 \\ \phi(g_1h_1)=\phi(g_1)\phi(h_1)=g_2h_2 \implies \\ \phi^{-1}(g_2h_2)=g_1h_1 = \phi^{-1}(g_2)\phi^{-1}(h_2)$$

b. Obvious

c.

$$\forall g_2, h_2 \in G_2: \exists g_1, h_1 \in G_1: \phi(g_1)=g_2, \phi(h_1)=h_2 \\ g_2h_2=\phi(g_1)\phi(h_1)=\phi(g_1h_1)=\phi(h_1g_1)=\phi(h_1)\phi(g_1)=h_2g_2$$

d.

$$\exists a \in G_1: G_1=\lang a \rang_G \overset{(2.2.6)}{=} \{a^n, n \in \Z\} \\ \forall b \in G_2, \exists n: b=\phi(a^n)=\phi(a)^n \implies G_2 = \lang \phi(a) \rang_G$$

e.

Follows from $(2.2.23.c)$ and the fact that $\phi$ is a bijection.

$\square$

Theorem 2.2.27: First isomorphism theorem

$$\begin{align*} &\sphericalangle \\ &G_1, G_2 \in \mathcal G \\ &G_1 \overset{\psi}{\rightsquigarrow}_G G_2 \\ &\phi:G_1 \to G_1/\ker \psi - \text{natural homomorphism} \\ \hline \\ &\exists! \eta: G_1/\ker \psi \overset{\eta}{\cong}_G \psi(G_1), \psi = \eta \phi \end{align*}$$

Proof

Define unique $\eta$

Remeber that by $(2.2.24)$ $\ker \psi \lhd_G G_1$, so the factor group $G_1 / \ker \psi$ is well-defined.

Now we define $\eta: g\ker\psi \mapsto \psi(g)$. Let's prove that it's well-defined. $g_1\ker\psi = g_2\ker\psi \implies \exists h \in \ker\psi: g_1 = g_2h \implies \psi(g_1) = \psi(g_2 h)=\psi(g_2)\psi(h) = \psi(g_2)$.

Next, $\eta$ is uniquely defined (as a map) because $\psi = \phi\eta$. This means that we know exactly $\psi(g)$ and use this value to define how $\eta$ maps the coset from $G_1 / \ker \psi$ to $\psi(G_1)$.

$\eta$ is bijective

Obviously, $\eta(G_1/\ker \psi) = \psi(G_1)$.

$$\eta(g\ker\psi)=e \iff \psi(g)=e \iff g \in \ker \psi \implies \\ \eta^{-1}(e)=\ker \psi$$

Since $\ker \psi$ is identity in $G_1 / \ker \psi$, by $(2.2.25)$ $\eta$ is injective.

Thus, we proved that $\eta: G_1/\ker \psi \leftrightarrow \psi(G_1)$.

$\eta$ is a homomorphism

$$\eta(g_1\ker\psi \cdot g_2\ker\psi)=\eta(g_1 g_2\ker\psi)=\psi(g_1g_2)=\\ =\psi(g_1)\psi(g_2) = \eta(g_1\ker \psi)\eta(g_2\ker \psi)$$

$\square$

Theorem 2.2.28: Second isomorphism theorem

$$\begin{align*} &\sphericalangle \\ &G \in \mathcal G \\ &H \subseteq_G G \\ &N \lhd_G G \\ \hline \\ &\begin{align*} & HN \subseteq_G G \tag{a}\\ & H \cap N \lhd_G H \tag{b}\\ & HN/N \cong_G H / (H \cap N) \hspace{1cm} \tag{c}\\ \end{align*} \end{align*}$$

Proof

a.

$HN:=\{hn, h \in H, n \in N \}$, fix some $h_1, h_2 \in H, n_1, n_2 \in N$,

$$e \in HN, \\ N \lhd_G G \implies (h_2)^{-1}n_1h_2 \in N \implies \\ (h_1n_1)(h_2n_2)=\underbrace{h_1h_2}_{\in H}\underbrace{(h_2^{-1}n_1h_2)n_2}_{\in N} \in HN, \\ (h_1n_1)^{-1}=n_1^{-1}h_1^{-1}=h_1^{-1}(h_1n_1^{-1}h_1^{-1})\in HN$$

By $(2.2.2)$ $HN \subseteq_G G$.

b.

$$h \in H, l \in N \cap H \implies h^{-1}lh \in H, h^{-1}lh \in N \implies N \cap H \lhd_G H$$

c.

$$\phi: H \to HN/N, h \to hN \\ \forall h \in H, n \in N: \phi^{-1}(hnN)=\phi^{-1}(hN)=h \in H \implies \phi(H) = HN/N \\$$ $$\forall h_1, h_2 \in H: \phi(h_1h_2)=h_1h_2N=h_1Nh_2N =\phi(h_1)\phi(h_2) \implies \\ H \overset{\phi}{\rightsquigarrow}_G HN/N$$

Next, $\ker \phi = \{h\in H: hN=N\}=H\cap N$. Combining all these facts:

$$H \overset{\phi}{\rightsquigarrow} HN/N, \ker \phi = H\cap N, \phi(H)=HN/N \overset{(2.2.27)}{\implies} \\ H/(H\cap N) \overset{\phi}{\cong}_G HN/N$$

$\square$

Theorem 2.2.29: Correspondence theorem (fourth isomorphism theorem)

$$\begin{align*} &\sphericalangle \\ &G \in \mathcal G \\ &N \lhd_G G \\ &\mathfrak H :=\{H: N\subseteq_G H \subseteq_G G\} \\ &\mathfrak H_N :=\{H_N: H_N \subseteq_G G/N\} \\ &\phi: \mathfrak H \to \mathfrak H_N, H \mapsto H/N \\ \hline \\ &\begin{align*} & \phi - \text{well-defined} \tag{a} \\ & \phi^{-1}(H_N) =\{g \in G: gN \in H_N\} \tag{b}\\ & \phi: \mathfrak H \leftrightarrow \mathfrak H_N \tag{c}\\ &N \subseteq_G H \lhd_G G \implies \phi(H) \lhd_G G / N \hspace{1cm} \tag{d}\\ & H_N \lhd_G G/N \implies \phi^{-1}(H_N) \lhd_G G \hspace{1cm} \tag{e}\\ \end{align*} \end{align*}$$

Proof

a.

To prove that that $\phi$ is well-defined, we need establish that

1. $H/N$ is a well-defined factor-group
2. $H/N \in \mathfrak H_N$

Assume $H \in \mathfrak H$. Obviously $N \lhd_G H$, so the factor group $H/N$ is well-defined. Since $H/N$ are just cosets $hN$, it's easy to see that $H/N \subseteq G/N$. Let's prove $H/N \subseteq_G G/N$

$$\begin{cases} H/N \ne \empty \\ \forall aN, bN \in H/N: aN(bN)^{-1}=ab^{-1}N \in H/N \end{cases} \implies \\ H/N \subseteq_G G/N \implies H/N \in \mathfrak H_N$$

b., c.

Consider $H_N \subseteq_G G/N$. Let's define a set

$$\phi^{-1}(H_N):=\{g \in G: gN \in H_N\}$$

Note that this definition is not yet telling us that $\phi^{-1}(H_N)$ is the inverse of the subgroup $H_N$ under our mapping $\phi: H \mapsto H/N$. Rather this is something we need to establish further. We will do it in three steps:

1. Prove that $\phi^{-1}(H_N) \in \mathfrak H$
2. Prove that $\phi(\phi^{-1}(H_N))=H_N$
3. Prove that $\phi$ is injective

After proving each of these statements we see that $\phi^{-1}(H_N)$ is actually is in pre-image of $H_N$ under $\phi$ and this pre-image has exactly this one element. Since $H_N$ is arbitrary this also means that $\phi$ is surjective thus we'll finish proving $(b)$ and $(c)$.

1. Prove that $\phi^{-1}(H_N) \in \mathfrak H$

We need to prove that $N \subseteq_G \phi^{-1}(H_N) \subseteq_G G$:

1. $N \in H_N \implies e \in \phi^{-1}(H_N)$
2. $a, b \in \phi^{-1}(H_N) \implies aN, bN \in H_N \implies abN \in H_N \implies ab \in \phi^{-1}(H_N)$
3. $a \in \phi^{-1}(H_N) \implies aN \in H_N \implies a^{-1}N \in H_N \implies a^{-1} \in \phi^{-1}(H_N)$

So we have $\phi^{-1}(H_N) \subseteq_G G$. Next,

$$n \in N \implies nN \in H_N \implies n \in \phi^{-1}(H_N)$$

So $N \subseteq_G \phi^{-1}(H_N)$.

2. Prove that $\phi(\phi^{-1}(H_N))=H_N$

$$aN \in H_N \iff a \in \phi^{-1}(H_N) \iff \\ aN \in \phi^{-1}(H_N)/N = \phi(\phi^{-1}(H_N))$$

3. Prove that $\phi$ is injective

$$\phi(H_1)=\phi(H_2) \implies H_1/N = H_2/N \\ h_1 \in H_1 \iff h_1N \in H_1/N \iff \\ h_1N \in H_2/N \iff h_1 \in H_2 \\ H_1 = H_2$$

d.

Assume $N \subseteq_G H \lhd_G G$. Consider a map $\psi: G/N \to G/H, gN \mapsto gH$. This map is a homomorphism:

$$\psi(aNbN)=\psi(abN)=abH=aHbH=\psi(aN)\psi(bN)$$

Next, $\ker \psi=\{gN, g\in H\} = H/N \overset{(2.2.24)}{\implies} H/N \lhd_G G/N \implies \phi(H) \lhd_G G/N$

e.

Assume $\phi(H)=H/N\lhd_G G/N$. Then we can define homomorphism $\psi$ as a composition of two natural homomorphisms: $G \to G/N \to \frac{G/N}{H/N}$. Now let's think - what is a neutal element in $\frac{G/N}{H/N}$? It is a set of cosets $\{aN \in G/N: aN \in H/N\}$. Thus $\ker \psi = H \overset{(2.2.24)}{\implies} H \lhd_G G$.

$\square$

Theorem 2.2.30: Third isomorphism theorem

$$\begin{align*} &\sphericalangle \\ &G \in \mathcal G \\ &H \lhd_G G \\ &N \lhd_G G \\ &N \subseteq H \\ \hline \\ &G/H \cong_G \frac{G/N}{H/N} \end{align*}$$

Proof

Consider mapping $\psi$ in the proof of (2.2.29.e). Obviously, this homomorphism is surjective. From $(2.2.29.e)$ $\ker \psi = H$, thus from $(2.2.27)$ $G/H \cong_G \frac{G/N}{H/N}$.

$\square$

Abelian groups structure

Proposition 2.2.31: Cyclic groups are isomorphic to integers

$$\begin{align*} &\sphericalangle \\ &G \in \mathcal G^\circlearrowleft \\ \hline \\ &\begin{align*} &|G| = \infty \implies G \cong_G \Z \hspace{1cm} \tag{a}\\ &|G| = n \implies G \cong_G \Z_n \tag{b}\\ \end{align*} \end{align*}$$

Proof

Let $a$ be the group generator, that is $G = \lang a \rang_G$.

a.

Define $\phi: \Z \to G, n \mapsto a^n$.

Let's prove that

$$|G|=\infty, a^x=e \implies x = 0$$

Assume otherwise:

$$\exists x \ne 0: a^x=e \implies \forall y \in \Z: a^y = a^{qx+r}=a^r, 0 \le r < x \implies \\ |G| < \infty$$

Next,

$$\phi(m) = \phi(n) \implies a^m = a^n \implies a^{m-n} =e \overset{|G|=\infty}{\implies} \\ m=n \implies f: \Z \overset{1-1}{\to} G\\ (2.2.6) \implies f(\Z)= G$$

So we proved that $\phi: \Z \leftrightarrow G$. Finally, let's prove that $\phi: \Z \rightsquigarrow G$:

$$\phi(m+n)=a^{m+n}=a^ma^n = \phi(m)\phi(n)$$

b.

$|G|=n$. Define $\phi: \Z_n \to G, x \mapsto a^x$. $\phi$ is well-defined because $a^n=e$.

$$\phi(m) = \phi(k) \implies a^m = a^k \implies a^{k-m} =e\\ k-m = qn+r, 0 \le r < n \implies a^r=e \overset{|G|=n, G \in \mathcal G^\circlearrowleft, (2.2.6)}{\implies} \\ r=0 \implies k-m = qn \implies k \equiv m \text{ (mod } n \text{)} \implies \\ f: \Z_n \overset{1-1}{\to} G \\ (2.2.6) \implies \forall b \in G: \exists n \in \Z:b = a^n \implies f(\Z_n)= G$$

We proved that $\phi: \Z_n \leftrightarrow G$. Let's prove that $\phi: \Z_n \rightsquigarrow G$:

$$\phi(m+_nk)=a^{m+k+qn}=\\ =a^ma^k=\phi(m)\phi(n) \implies$$

$\square$

Corrolary 2.2.32: Any group of a prime order is isomorphic to integers

$$\begin{align*} &\sphericalangle \\ &G \in \mathcal G \\ &|G|=p \in \mathfrak P \\ \hline \\ &G \cong_G \Z_p \end{align*}$$

Proof

From $(2.2.19)$ we know that $G \in G^{\circlearrowleft}$. Using $(2.2.31)$ we finish the proof.

$\square$

Proposition 2.2.33: Internal direct product is isomorphic to external direct product

$$\begin{align*} &\sphericalangle \\ &G \in \mathcal G \\ &H_1, \ldots, H_n \subseteq_G G \\ &H_i \cap H_j = \{e\} \\ &\forall h_i \in H_i, h_j \in H_j: h_ih_j=h_jh_i \\ \hline \\ &H_1H_2\ldots H_n \cong_G H_1 \times H_2 \times \ldots \times H_n \end{align*}$$

Proof

We will make the proof for $n=2$. For other $n$, the proof is exactly the same.

Define $\phi: H_1H_2 \to H_1 \times H_2, h_1k_1 \mapsto (h_1, k_1)$. Let's prove that it's well-defined:

$$\forall h_1, h_2 \in H_1, k_1, k_2 \in H_2: h_1k_1=h_2k_2 \overset{H_1 \cap H_2 = \{e\} }\implies \\ h_2^{-1}h_1=k_2k_1^{-1} = e \implies h_1=h_2, k_1=k_2$$

Now let's prove $\phi: H_1H_2 \rightsquigarrow H_1 \times H_2$:

$$\forall g_1, g_2 \in G, h_1, h_2 \in H_1, k_1, k_2 \in H_2: \\ g_1=h_1k_1, g_2=h_2k_2: \\ \phi(g_1g_2)=\phi(h_1k_1h_2k_2)=\phi(h_1h_2k_1k_2)=(h_1h_2, k_1k_2) = \\ = (h_1,k_1)(h_2,k_2)=\phi(g_1)\phi(g_2)$$

Finally, let's prove that $\phi$ is bijective:

$$(h_1, k_1)=(h_2, k_2) \implies h_1k_1=h_2k_2 \\ \phi^{-1}((h_1, k_1))=h_1k_1$$

$\square$

Lemma 2.2.34: Existence of an element of a prime order

$$\begin{align*} &\sphericalangle \\ &G \in \mathcal G^{\mathcal A} \\ &p \in \mathfrak P \\ &p \mid |G| \\ \hline \\ &\exists g \in G: \text{ord }g = p \end{align*}$$

Proof

$n:=|G|$, we use induction on $n$.

$n=1$ is trivial.

Assume that the proposition is true $\forall k < n$. We want to consider two cases:

1. Only trivial subgroups of $G$ exist
2. Non-trivial subgroup of $G$ exists

1. Only trivial subgroups of $G$ exist

Assume $\nexists H \subset_G G, H \ne \{e\}$, then $\forall a \in G, a \ne e: \lang a \rang_G = G$. We want to prove that $n \in \mathfrak P$ in this case. Assume otherwise:

$$n \notin \mathfrak P \implies n = pq, 1< p < n, p \in \mathfrak P \overset{(2.2.7.e)}\implies \\ \text{ord }a^p=\frac{n}{\gcd(n, p)}=\frac{n}{p} \implies 1 < |\lang a^p \rang_G| < n$$

Which is a contraction to $\nexists H \subset G, H \ne \{e\}$.

So $n \in \mathfrak P$ and $p \mid n \implies n=p$. So $\text{ord }a=p$.

2. Non-trivial subgroup of $G$ exists

Now assume $\exists H \subset_G G, H \ne \{e\}$.

If $p \mid |H|$ then by induction hypothesis we're done.

So we only need to consider the case $p \nmid |H|$.

$$G \in \mathcal G^{\mathcal A} \implies H \lhd_GG \overset{(2.2.17), (2.2.22.b)}\implies |G|=|H|\cdot|G/H| \overset{p \mid |G|, p \nmid |H| }\implies p \mid |G/H| \overset{\text{induction hypothesis}} \implies \\ \exists aH \in G/H: \text{ord }(aH)=p \implies H=(aH)^p=a^pH \implies a^p \in H, a \notin H \\$$

Note that $a \notin H$, otherwise $aH=H$ and $\text{ord }aH=1$. Denote $r := |H|$, then

$$(2.2.18) \implies \text{ord }a^p \mid r \overset{(2.2.7)} \implies 1=(a^p)^r= (a^r)^p \overset{(2.2.7)}\implies \text{ord }a^r \mid p \implies \\ (\text{ord }a^r = 1) \vee (\text{ord }a^r = p)$$

Thus all we need to prove is $a^r \ne e$.

$$p \nmid |H| \implies p \nmid r \implies \gcd(r, p)=1 \implies \exists s, q: rs+pq=1 \implies \\ a = a^{rs+pq}=(a^r)^s(a^p)^q$$

If we assume that $a^r=e$ then $a = (a^p)^q \overset{a^p \in H}\implies a \in H$ which is a contradiction.

$\square$

def: p-group

$$\begin{align*} &\sphericalangle \\ &G \in \mathcal G^{\mathcal A} \\ &p \in \mathfrak P \\ & \forall g \in G: \exists k \in \N \cup \{0\}: \text{ord }g = p^k \\ \hline \\ &G \text{ is a }p\text{-group} \end{align*}$$

Example: Cyclic group is a $p$-group

Any cyclic group of a prime order is a $p$-group

Example: Non-cyclic group

$\Z_2 \times \Z_2$ is not a cyclic group. However it's a $p$-group with $p=2$

Proposition 2.2.35: p-group criterion

$$\begin{align*} &\sphericalangle \\ &G \in \mathcal G^{\mathcal A} \\ &|G| < \infty \\ &p \in \mathfrak P \\ \hline \\ &G \text{ is a }p\text{-group}\iff \exists n: |G| = p^n \end{align*}$$

Proof

$\implies$

$$|G| \ne p^n \implies \exists q \in \mathfrak P: \gcd(p, q) = 1, q \mid |G| \overset{(2.2.34)}\implies \exists a \in G: \forall n: \text{ord }a = q \ne p^n$$

$\impliedby$

$$|G| = p^n \implies \forall a \in G: \text{ord }a \mid p^n \overset{p \in \mathfrak P}\implies \text{ord }a = p^k$$

$\square$

Proposition 2.2.36: p-group structure

$$\begin{align*} &\sphericalangle \\ &G \in \mathcal G^{\mathcal A} \\ &|G| = p^n, p \in \mathfrak P, n \ge 1 \\ &g \in G: \forall h \in G: \text{ord } h \leq \text{ord } g\\ \hline \\ &G = \lang g \rang_G H \cong_G \lang g \rang_G \times H, H \subset_G G, \lang g \rang_G \cap H = \{e\} \end{align*}$$

Proof

We'll make induction on $n$.

$n=1 \implies |G|=p \overset{(2.2.19)}\implies \lang g \rang_G=G, H = \{e\}$.

Assume the proposition is true for $k<n$. If $G = \lang g \rang_G$ then we're done.

So we only consider the case $G \ne \lang g \rang_G$. Denote $m$ to be the power of $p$ that equals to the maximal order in the group:

$$m:\text{ord }g = p^m$$

Since it's the maximal order we have:

$$\forall a \in G: a^{p^m}=e \\$$

Now consider an element $h \in G \setminus \lang g\rang_G$ such that it has minimal order in $G \setminus \lang g\rang_G$:

$$h \in G \setminus \lang g \rang_G: \forall x \in G \setminus \lang g \rang_G: \text{ord }h \leq \text{ord }x \\$$

Let's make a cyclic subgroup from this element:

$$H:=\lang h \rang_G \\$$

Now we want to make an outline for the rest of the proof:

1. Prove that $\text{ord }h=p$
2. Prove that for $gH \in G/H: \text{ord } gH = p^m$
3. Consider factor group $G/H$ that will fall under the induction hypothesis and build our decomposition from it

1. Prove that $\text{ord }h=p$

The idea of the proof is building an element $a \in G \setminus \lang g \rang_G$ such that $\text{ord }a = p$. From the minimality of $h$ order we'll necessary have $\text{ord }h = p$, since every element in $G$ has order $p^l$ for some $l \ge 0$ and $e \notin G \setminus \lang g \rang_G$.

We'll construct the element $a$ by first finding some $r \in \N: h^p=g^r$, then proving $p \mid r$ and finally defining $a := g^{-r/p}h$.

Now let's make the actual proof:

$$\text{ord }h=p^k \implies \gcd (\text{ord h}, p) = p \\ \text{ord } h^p \overset{(2.2.7)}= \frac{\text{ord }h}{p} < \text{ord } h$$

Since $h$ has minimal order in $G \setminus \lang g \rang_G$, we conclude that $h^p \in \lang g \rang_G$.

$$h^p \in \lang g \rang_G \implies \exists r \in \Z: h^p = g^r \\ (g^r)^{p^{m-1}}=h^{p^m}=e \implies (g^{p^{m-1}})^r=e \overset{(2.2.7.d)}\implies \text{ord }g^{p^{m-1}} \mid r \implies \\ \exists l \ge 0: p^l \mid r$$

Since $\text{ord }g = p^m$, we know that $g^{p^{m-1}}\ne e$, so $l \ge 1$. Thus $p^l \mid r \implies p \mid r \implies r = ps$ for some $s$.

Now we define:

$$a:=g^{-s}h$$

If $a$ were in $\lang g \rang_G$ then $h$ would be in $\lang g \rang_G$ which is a contradiction. So $a \in G \setminus \lang g \rang_G \implies a \ne e \implies \text{ord } a \ge p$. But on the other hand $\text{ord } a \le p$ because:

$$a^p=g^{-sp}h^p=g^{-r}h^p=h^{-p}h^p=e \implies \text{ord }a \mid p \implies \text{ord a} \le p$$

So we proved $\text{ord }a = p$ and thus (as mentioned in the proof outline) $\text{ord }h = p$ and $|H|=p$.

2. Prove that for $gH \in G/H: \text{ord } gH = p^m$

$|H|=p, p \in \mathfrak P$ means that $H$ has only trivial subgroups $\{e\}$ and $H$. So $\forall y \in H, y \ne e: \lang y \rang_G=H$. If there was an element $y \in \lang g \rang_G \cap H, y \ne e$ that would mean that $H=\lang y \rang_G \subseteq \lang g \rang_G$ and so $h \in \lang g \rang_G$ which contradicts the definition of $h$. This means that:

$$\lang g \rang_G \cap H = \{e\}$$

We know that $(gH)^{p^m}=g^{p^m}H=H \implies \text{ord }gH \mid p^m \implies \text{ord }gH = p^l, l \leq m$.

$$H = (gH)^{p^l}=g^{p^l}H \implies g^{p^l} \in \lang g \rang_G \cap H = \{e\} \implies g^{p^l} = e$$

But $l<m$ contradicts the fact that $\text{ord }g = p^m$, so $l=m$ and $\text{ord }gH = p^m$.

3. Consider factor group $G/H$ that will fall under induction hypothesis and build our decomposition from it

First it's clear that $gH$ has maximal order in $G / H$, since $\forall a \in G: (aH)^{p^i}=a^{p^i}H$. In addition, the group $G / H$ has order $|G/H|=|G|/|H|=p^{n-1}$. So by the induction hypothesis:

$$G/H = \lang gH \rang_G M \cong_G \lang gH \rang_G \times M$$

By $(2.2.29)$ $\exists K \subseteq_G G: M = K/H$ so we have:

$$G/H = \lang gH \rang_G (K/H) \cong_G \lang gH \rang_G \times K/H$$

Fix $b \in \lang g \rang_G \cap K$ then $b \in \lang g \rang_G \implies bH \in \lang gH \rang_G$ and $b \in K \implies bH \in K/H$. So $bH \in \lang gH \rang_G \cap K/H$

$$bH \in \lang gH \rang_G \cap K/H \overset{\text{induction hypothesis}}{=} \{ H \} \implies bH=H \implies b \in H\\ b \in \lang g \rang_G \cap H = \{e\} \implies b = e \\$$

Since $b$ was arbitrary in $\lang g \rang_G \cap K$ we just proved

$$\lang g \rang_G \cap K = \{e\}$$

Moreover:

$$G/H = \lang gH \rang_G (K/H) \cong_G \lang gH \rang_G \times K/H \implies \\ \forall x \in G: \exists h_1, h_2, h_3 \in H, k \in K, l \ge 0: xh_1=g^lh_2kh_3 \implies \\ x = g^lkh_4 \overset{H \subseteq K}{\implies} x = g^lk_1, k_1 \in K \implies \\ G = \lang g \rang_G K$$

Finally

$$G = \lang g \rang_G K, \lang g \rang_G \cap K = \{e\}\overset{(2.2.33)}\implies G \cong_G \lang g \rang_G \times K$$

$\square$

note

It's clear that the group $H$ is also a $p$-group so we can continue decomposition. Thus any $p$-group is isomorphic to the external product of cyclic groups:

$$G = \lang g_1 \rang_G \times \ldots \times \lang g_k \rang_G$$

Lemma 2.2.37: Internal direct product representation

$$\begin{align*} &\sphericalangle \\ &G \in \mathcal G^{\mathcal A} \\ &|G|=p_1^{\alpha_1}\cdot \ldots \cdot p_k^{\alpha_k}, p_i \in \mathfrak P \\ &G_i:=\{g \in G: \exists n \in \N: \text{ord }g=p_i^n\} \\ \hline \\ &\begin{align*} &G_i \subseteq_G G \tag{a}\\ &|G_i| - p_i\text{-group} \tag{b}\\ &G_i \cap G_j = \{e\} \tag{c}\\ &G=G_1G_2\ldots G_k \hspace{1cm} \tag{d}\\ \end{align*} \end{align*}$$

Proof

a.

$$\text{ord }e=1=p_i^0 \implies e \in G_i \\$$ $$g \in G_i \implies \text{ord }g = p_i^r \implies \begin{cases} g^{p_i^r}=e \\ \forall k < p_i^r: g^k \ne e \end{cases} \implies \\ \begin{cases} (g^{-1})^{p_i^r}=e \\ \forall k < p_i^r: (g^{-1})^k \ne e \end{cases} \implies \text{ord }g^{-1} = p_i^r \implies g^{-1} \in G_i$$ $$g, h \in G_i \implies \text{ord }g = p_i^r, \text{ord }h = p_i^s \implies \\ (gh)^{p_i^{\max(r, s)}}=g^{p_i^{\max(r, s)}}h^{p_i^{\max(r, s)}} = 1 \implies \text{ord }gh \mid p_i^{\max(r, s)} \implies \\ \text{ord }gh = p_i^t \implies gh \in G_i$$

b.

Obvious by construction

c.

$$g \in G_i \cap G_j \implies \exists r, s: \text{ord }g = p_i^r, \text{ord }g = p_j^s \overset{\gcd(p_i, p_j)=1} \implies \\ \text{ord }g = 1 \implies g = e$$

d.

$$g \in G \implies \text{ord }g \mid |G| \implies \text{ord }g=p_1^{\beta_1}\ldots p_k^{\beta_k} \\ a_i:=\text{ord }g / p_i^{\beta_i} \implies \gcd(a_1, \ldots, a_k)=1 \implies \\ \exist b_i: \sum_i a_ib_i = 1 \\ g = g^{\sum_i a_ib_i}=g^{a_1b_1} \ldots g^{a_kb_k} \\ g^{a_ib_ip_i^{\beta_i}}=g^{b_i\text{ord }g} = e \implies \text{ord } g^{a_ib_i} \mid p_i^{\beta_i} \implies \\\text{ord } g^{a_ib_i} = p_i^{\gamma_i} \implies g^{a_ib_i} \in G_i$$

Now assuming $g_i:=g^{a_ib_i} \in G_i$ we finish the proof.

$\square$

Proposition 2.2.38: Fundamental Theorem of Finite Abelian Groups

$$\begin{align*} &\sphericalangle \\ &G \in \mathcal G^{\mathcal A} \\ &|G|= p_1^{\alpha_1}\ldots p_n^{\alpha_n}\\ \hline \\ &G \cong_G \Z_{p_{i_1}^{\beta_1}}\times \Z_{p_{i_2}^{\beta_2}} \times \ldots \times \Z_{p_{i_k}^{\beta_k}}, 1 \le i_j \le n, \beta_j \le \alpha_{i_j} \end{align*}$$

Proof

By $(2.2.37)$ we can break $G$ into internal direct product of $p_i$-groups $G_i$. By $(2.2.33)$ it's isomorphic to external direct product. By $(2.2.36)$, each $G_{i}$ is decomposed into a product of cyclic groups, $|G_i| = p_i^{\alpha_i}$. By $(2.2.31)$ each of these groups is isomorphic to some $\Z_{p_i^{\alpha_i}}$.

$\square$

Proposition 2.2.39: d-torsion group structure

$$\begin{align*} &\sphericalangle \\ &G \in \mathcal G^\mathcal A \\ &|G| = n^r \\ &G[d]:= \{g \in G: g^d=e\}\\ &d \mid n \implies |G[d]|=d^r \\ \hline \\ &G \cong_G \Z_n^r \end{align*}$$

Proof

Let's start with proving that $|\Z_{p^{a}}[p^b]|=p^{\min(a, b)}$:

$$\forall b \ge a: p^a \mid p^b \implies |\Z_{p^{a}}[p^b]|=p^a \\ \forall b < a:\Z_{p^{a}}[p^b]=\{n \in \Z_{p^a}:p^b\cdot n = 0\} = \{0, p^{a-b}, 2p^{a-b}, \ldots, (p^b-1)p^{a-b} \} \implies \\ |\Z_{p^{a}}[p^b]|=p^{b} \\$$

Now we will consider the case $n = p^{\beta}, p \in \mathfrak P$.

By $(2.2.38)$:

$$G \cong_G \Z_{p^{\alpha_{1}}} \times \Z_{p^{\alpha_{2}}} \times \ldots \Z_{{p}^{\alpha_{k}}}, \sum_i \alpha_i = \beta r$$

So we have $|G[p^b]|=p^{\min(\alpha_1, b)} \ldots p^{\min(\alpha_k, b)}$. On the other hand we know that $|G[p^b]| = p^{br}$, so:

$$\forall b: \sum_{i=1}^k \min(\alpha_i, b)=br \\$$

From that we can derive:

$$b = \min{\alpha_i} \implies bk=br \implies k = r \\ b = \max{\alpha_i} \implies \beta r = \sum_{i=1}^r \alpha_i=br \implies \max{\alpha_i} =b= \beta \\$$

Since all $\alpha_i \ge 1$ and $\max{\alpha_i} = \beta$ and $\sum_{i=1}^r \alpha_i = \beta r$ it follows that $\alpha_i = \beta$. So

$$G \cong_G \Z_{p^{\beta}}^r$$

So we finished the proof for the case $n = p^{\beta}, p \in \mathfrak P$.

Now consider general case $n = p_1^{\beta_1}\ldots p_n^{\beta_n}$. By $(2.2.38)$:

$$G \cong_G \underbrace{\Z_{p_1^{\alpha_{1, 1}}} \times \ldots \times \Z_{p_1^{\alpha_{1, k_1}}}}_{H_1} \times \ldots \times \underbrace{\Z_{p_n^{\alpha_{n, 1}}} \times \ldots \times \Z_{p_n^{\alpha_{n, k_n}}}}_{H_n}$$

First note that $\forall g \in \Z_{p_i^\alpha}: g^{p_j^\beta} = e \implies \text{ord }g \mid p_j^b, \text{ord }g \mid p_i^\alpha \implies \text{ord } g = 1 \implies g = e$. So we have:

$$\forall \alpha, i: |G[p_i^\alpha]|=|H_i[p_i^\alpha]|$$

But that means that the conditions of theorem holds for $H_i$ with $|H_i|=p_i^{\beta_i}$. So we proved above that:

$$H_i \cong_G \Z_{p_i^{\beta_i}}^r$$

So we know that:

$$G \cong_G \Z_{p_1^{\beta_1}}^r \times \ldots \times \Z_{p_n^{\beta_n}}^r$$

By the Chinese remainder theorem $(2.3.14)$ that we'll prove in the next section:

$$\Z_n \cong_G \Z_{p_1^{\beta_1}} \times \ldots \times \Z_{p_k^{\beta_k}}$$

And thus we finish the proof

$\square$

Exercises

1. How many distinct groups (up to relabeling the elements, that is up to isomorphism) of order 4 exist?

2. How many non-trivial subgroups does the group $\Z_2 \times \Z_2$ have? (trivial subgroups are $\{e\}$ and the group itself)

3. Is $\Z_2 \times \Z_2 \cong_G \Z_4$?

4. What is the order of $6 \in \Z_{15}$

5. What is the order of $64 \in \Z^*_{257}$

6. What is the order of $(6, 15, 4) \in \Z_{30} \times \Z_{45} \times \Z_{24}$

7. If $a$ and $b$ have orders 31 and 32, what is the order of the group $\lang a \rang_G \cap \lang b \rang_G$?

8. Compute $5^{3^{999}+3^{999}+3}\pmod {3^{1000}}$

9. Make a disjoint cycle representation of $(1\, 4\, 2 \, 3)(2\, 4)(5\, 6)(1 \, 3 \, 2 \, 4)$

10. Is $\Z_8^* \cong_G \Z_4$?

11. What is the number of different isomorphisms for $\Z_6 \cong_G \Z_6$

12. How many different abelian groups of order 720 exist?