6. What is a group?

In lesson 1. What are rings and fields?, we learned the definitions of ring and field. In the next lesson we'll need one more algebraic concept — group. This lesson gives some basic facts about groups.

6.1. An introductory example

Before giving the definition of group, let us start with an example of a group that will also be useful later in this topic. Let $\mathcal F$ be a field and $a$ a non-zero element of it. Let us consider the field's subset $S = \{ a^k\ |\ k \in \mathbb Z \} = \{\ldots,\ a^{-3}, a^{-2}, a^{-1}, 1, a, a^2, a^3, \ldots \}$, the set of integer powers of $a$, where we define negative powers using the formula $a^{-n} = (a^{-1})^n$, and we define the zeroth power to be the identity element.

For example, if we take $\mathcal F$ to be the residue class field $\mathbb F_7 = \mathbb Z_7$ and $a = 4$, then it turns out that $S = \{ 1,\ 2,\ 4\}$. Explanation.

The set $S$ inherits some algebraic structure from the field $\mathcal F$: the set $S$ is closed under multiplication because it can be easily shown that the rule $a^i a^j = a^{i+j}$ holds for all integers $i$ and $j$. However, $S$ is not a field itself since in general it is in general not closed under addition of $\mathcal F$. But we can regard $S$ as an algebraic structure with only one operation: multiplication. This operation has some nice properties: $S$ is closed under taking inverses because $(a^i)^{-1} = a^{-i}$ for all integers $i$, as is easy to see; it contains the identity since $a^0 = 1$ by definition; multiplication is associative and commutative because of the field axioms. Such algebraic structures with only one operation are called abelian groups, rigorously defined below.

6.2. Definition of group

A set $S$ together with a binary operation $\cdot$ on it is called a group if it satisfies the following properties.

  1. The set $S$ is closed under the operation $\cdot$.
  2. $\cdot$ is associative: $a \cdot (b \cdot c) = (a \cdot b) \cdot c$ for all $a, b, c \in S$.
  3. $\cdot$ has an identity element, i. e. there exists an element $e \in S$ such that $e \cdot a = a \cdot e = a$ for all $a \in S$.
  4. For every $a \in S$ there exists $b \in S$ such that $a \cdot b = b \cdot a = e$; the element $b$ is called the inverse of $a$ and denoted by $a^{-1}$.

A group $(S; \cdot)$ is called an abelian group if $\cdot$ is commutative, i. e. $a \cdot b = b \cdot a$ for all $a, b \in S$.

6.3. More important examples and non-examples of groups

  • If $(\mathcal F; +, \cdot)$ is a field and $\mathcal F^*$ denotes the set of its non-zero elements, then $(\mathcal F^*; \cdot)$ is an abelian group, called the multiplicative group of $\mathcal F$. The group's identity element $e$ is the multiplicative identity $1$ (which belongs to $\mathcal F^*$ since $0 \neq 1$) and the inverse of an element $a$ in the group is its multiplicative inverse $a^{-1}$ in the field. This is the group we will be most interested in in this topic.Proof that this is a group
  • If $(\mathcal F; +, \cdot)$ is a field, then $(\mathcal F; +)$ is a group. In other words, a field is a group if we forget about the multiplication operation of the field and regard addition as the group operation $\cdot$. Indeed, the definition of field guarantees the associativity of addition, the existence of identity element with respect to the $+$ operation (which is $0$, the zero element of the field) and that every element $a \in \mathcal F$ has an additive inverse (which is $-a$, the opposite element of $a$). The group $(\mathcal F; +)$ is called the additive group of $\mathcal F$. It is an abelian group.
  • If $(\mathcal F; +, \cdot)$ is a field, then $(\mathcal F; \cdot)$ is not a group. This is because the third group axiom fails: $0$ has no multiplicative inverse.
  • Although the concrete groups we will meet in this material will usually be abelian, there are also many important non-abelian groups in mathematics. For example $GL(n, \mathbb R)$, the group of invertible $n \times n$ matrices of real numbers, where the group operation is matrix multiplication, is not abelian for $n > 1$. Another example is $SO(3)$, the group of rotations about the origin in 3-dimensional space, where the group operation is the application of one rotation after another.

6.4. Some notes on notation

In the definition of group we have used multiplicative notation, where the group operation is denoted by $\cdot$ or juxtaposition and called multiplication, and the inverse of an element $a^{-1}$. When talking about additive groups of fields, such notation can create confusion, since the operation of the group is then not the field's multiplication and the inverse element in the group is not what is denoted by $a^{-1}$ in the field. Therefore another common notation in literature is additive notation, where the group operation is denoted by $+$ and called addition and inverse element is denoted by $-a$. Sometimes also other notations are used in literature. In this material we will in general stick to the multiplicative notation.

In the multiplicative notation, the product $a \cdot \ldots \cdot a$ where the element $a$ occurs $n$ times is denoted by $a^n$ and called the $n$th power of $a$. Negative powers of $a$ are defined as powers of the inverse of $a$ (e. g. $a^{-3} = (a^{-1})^3$), and the zeroth power is defined to be the identity element (i. e. $a^0 := e$).

6.5. Subgroups

A group can contain a smaller group as a subset. Such a subset is called a subgroup of the larger group. For example, consider $\mathbb F_{7}^*$, the multiplicative group of the field $\mathbb F_{7} = \mathbb Z_7$. The set $\{-1, 1\} = \{10, 1\} \subset \mathbb F_{7}^*$ is a group itself with respect to the multiplication in $\mathbb F_{7}^*$ since it is closed under multiplication, every element has an inverse in $S$ since both elements are their own inverses and multiplication of elements of $S$ is associative because multiplication is associative on $\mathbb F_{7}^*$. Another example of subgroup of $\mathbb F_{7}^*$ is the subset $\{1, 2, 4\}$ that we considered in the introductory example.

Let $\mathcal G$ be a group. A subset $\mathcal H \subseteq \mathcal G$ is called a subgroup of $\mathcal G$ if $\mathcal H$ is a group itself with respect to the group operation of $\mathcal G$.

More examples and non-examples of subgroups.

  • The multiplicative group of real numbers $(\mathbb R^*; \cdot)$ has the set of non-zero rational numbers $\mathbb Q^*$ as a subgroup. Indeed, $(\mathbb Q^*; \cdot)$ is a group since $\cdot$ is a binary operation on $\mathbb Q$ since the product of two rational numbers is a rational number; associativity and existence of identity element are obvious; for every non-zero rational number, the set $\mathbb Q^*$ also contains its inverse.
  • The set of positive integers is also a subset of $\mathbb R^*$ but not a subgroup of the group $(\mathbb R^*; \cdot)$ since it is not closed under taking inverses.
  • The subset $\{1, 2, 5\} \subset \mathbb F_7^*$ is not a subgroup of $\mathbb F_7^*$ since it is not closed under multiplication: $2 \cdot 5 = 3 \not\in \{1, 2, 5\}$.

A criterion for checking whether a subset is a subgroup is as follows.

Lemma. Let $(G; \cdot)$ be a group. A subset $H \subset G$ is a subgroup of $G$ if and only if $H$ is closed under multiplication and taking inverses and contains the identity element of $G$.

6.6. Subgroup generated by an element

An example of subgroup is the subgroup generated by an element, defined as follows.

Let $(G; \cdot)$ be a group and $a \in G$. The set $\langle a \rangle := \{ a^k\ |\ k \in \mathbb Z \} = \{\ldots,\ a^{-3}, a^{-2}, a^{-1}, e, a, a^2, a^3, \ldots \}$, i. e. the set of all integer powers of $a$, is called the subgroup generated by $a$.

The subgroup generated by an element is indeed always a subgroup, as follows from the simple lemma below.

Lemma. If $G$ is a group and $a \in G$, then $a^i a^j = a^{i+j}$ and $(a^i)^{-1} = a^{-i}$ for all integers $i$ and $j$.

Proof.

Indeed, from the lemma it follows that the subgroup generated by an element is closed under multiplication and taking inverses; it also contains the identity since $a^0 = e$ by definition, therefore it is a subgroup. The subgroup generated by $a$ is the smallest subgroup which contains the element $a$, since any subgroup containing $a$ must also contain all its integer powers to be closed under multiplication and taking inverses.

Examples.

  • In the group $(\mathbb R^*; \cdot)$, the subgroup generated by the element $2 \in \mathbb R^*$ is $\langle 2 \rangle = \{\ldots,\ \frac18,\ \frac14,\ \frac12,\ 1,\ 2,\ 4,\ 8,\ 16,\ \ldots \}$.
  • Consider the multiplicative group of the field $\mathbb Z_7$, i. e. the group $(\mathbb Z_7^*; \cdot)$, where $\mathbb Z_7^* = \{1, 2, 3, 4, 5, 6\}$ is the set of invertible remainders modulo $7$. Then the subgroup generated by $4 \in \mathbb Z_7^*$ is $\langle 4 \rangle = \{1, 4, 2\} \subset \mathbb Z_7^*$ (this is because the powers start to repeat with period $3$ because $4^3 = 1$, as explained at the introductory example).

What is the subgroup generated by the element $5$ in the multiplicative group of the field $\mathbb Z_{13}$? Answer.

6.7. Order

As we shall see, in any finite group (i. e. a group that contains a finite number of elements) the situation is similar to the last example about $\mathbb Z_7^*$: the powers of an element start to repeat because some positive power of the element is the identity.

Lemma. Let $G$ be a finite group and $a \in G$. Then there exists a positive integer $n$ such that $a^n = e$.

Proof.

If $a^n = e$, then the powers of an element of a finite group repeat with period $n$ since $a^{n+i} = a^n a^i = e a^i = a^i$ for all integers $i$. Therefore we can define the order of an element as follows.

Let $(G; \cdot)$ be a finite group. The order of an element $a \in G$ is the smallest positive integer $n$ such that $a^n = e$ where $e$ denotes the identity element. The order of $a$ is denoted by $\operatorname{ord} a$.

For example, in $\mathbb{Z}_7^*$ the order of the element $4$ is $3$ because $4^3 = 1$ but $4^1 = 4 \neq 1$ and $4^2 = 2 \neq 1$.

Another use of the word order is the order of a group, defined below. The use of the same word order for two different things (order of an element and order of a group) might be a little confusing, but the lemma below shows that these concepts are related.

Let $(G; \cdot)$ be a finite group. The order of the group $G$ is the number of elements in $G$.

Lemma. Let $(G; \cdot)$ be a finite group and $a \in G$. The order of the element $a$ is the order of the subgroup generated by it.

Proof.

For example, we have found that in $\mathbb{Z}_7^*$ the order of the element $4$ is $3$ and the subgroup generated by the element $4$ is $\{1, 2, 4\}$, which indeed contains $3$ elements.

6.8. Lagrange's Theorem

Let us note a useful property of orders of subgroups.

Theorem (Lagrange). Let $(G;\ \cdot)$ be a finite group and $H \subseteq G$ a subgroup. Then the order of $H$ divides the order of $G$.

Proof.

Corollary. The order of any element of a finite group divides the order of the group.

For example, we have found that the order of the element $4$ in $\mathbb{Z}_7^*$ is $3$; this indeed divides the order of the group $\mathbb{Z}_7^*$, which is $6$.

Corollary (Generalized Fermat's Little Theorem). Let $G$ be a finite group of order $n$. Then $a^{n} = e$ for all $a \in G$.

Proof.

If we take $G$ to be the multiplicative group of the field $\mathbb Z_p$ then the last corollary above gives us Fermat's Little Theorem: if $p$ is a prime then $a^{p-1} \equiv 1\ (\operatorname{mod} p)$.

6.9. Group homomorphisms and isomorphisms

Analogously to the case of rings (4. Isomorphisms, homomorphisms, automorphisms. Classification of all finite fields), two groups are called isomorphic if the elements of one group can be “relabeled” so that we obtain the other group. Only instead of two operations (ring addition and multiplication) we now have only one (group multiplication). Also analogously to the homomorphism of rings, one defines homomorphism of groups — a map preserving the group operation, but not necessarily one-to-one or onto.

Let $\mathcal F$ and $\mathcal G$ be two groups.

A function $\kappa : \mathcal F \to \mathcal G$ is called a homomorphism if it satisfies $\kappa(a \cdot b) = \kappa(a) \cdot \kappa(b)$ for all $a, b \in \mathcal F$.

A homomorphism $\kappa : \mathcal F \to \mathcal G$ is called an isomorphism if it is one-to-one and onto. Two groups are called isomorphic if there exists an isomorphism between them.

An isomorphism $\kappa : \mathcal F \to \mathcal F$ is called an automorphism of $\mathcal F$.

With a short proof one can show that a group homomorphism always satisfies $\kappa(e) = e$ and $\kappa(a^{-1}) = \kappa(a)^{-1}$.

6.10. Exponentiation and discrete logarithm

Although there exist many different groups that may be quite difficult to describe1), it is not hard to see that in any group the subgroup generated by an element has a very simple and familiar structure: it can be identified with the additive group $\mathbb Z_n$ for some $n$, as stated by the theorem below.

Theorem. Let $a$ be an element of order $n$ of a finite group. Then the map $\operatorname{exp}_a : \mathbb Z_n \to \langle a \rangle$ with $\operatorname{exp}_a(i) = a^i$ is a group isomorphism from the additive group of $\mathbb Z_n$ to the subgroup generated by $a$.

Proof.

The inverse map of the exponentiation map $\operatorname{exp}_a$ is the discrete logarithm $\operatorname{log}_a : \langle a \rangle \to \mathbb Z_n$. In other words, if $b \in \langle a \rangle$ is an element of the subgroup generated by $a$ then its discrete logarithm $\log_a(b)$ is the number $i \in \mathbb Z_n$ such that $b = a^i$. In some groups, the discrete logarithm turns out to be much harder to compute than the exponential of an element. This asymmetry has found use in several cryptographic algorithms.


1) It is interesting to note that even the classification of all finite simple groups, a subclass of finite groups, is one of the greatest achievements of algebra in the 20th century, the proof consisting of thousands of pages in hundreds of journal articles. Mathematicians haven't yet found a general classification of all finite groups. (However, for finite abelian groups, a simple classification actually does exist.)
finite_fields/06_groups.txt · Last modified: 2014/01/20 11:22 by marje