Basic Group Theory

Group

Groups $G$ are algebraic structures which are set and has a binary operation $⨁$ that combines two elements $a,b$ of the set to produce a third element $a⨁b$ in the set. The operation is said to have following properties:

1. Closure: $a\oplus b=c\in G$
2. Associative: $(a\oplus b)\oplus c=a\oplus (b\oplus c)$
3. Existence of Identity element: $a\oplus 0=0\oplus a=a$
4. Existence of unique inverse element for every element of the set: $a\oplus b=0$

Example: $\mathbb{Z}$ is an abelian group while $\mathbb{N}$ is not a group as it doesn’t satisfy inverse element property.

Prove uniqueness of inverse.

Take two elements $b\ne c\in G$ such that $a\cdot b=1$ and $a\cdot c=1$. Prove with contradiction $b=c$.

• A set with only closure and associativity, is called Semigroup.
• Monoid has Closure, associativity, Identity.

Groups which satisfy an additional property: commutativity on the set of elements are known as Abelian groups.

One very obvious question that comes to mind is Why abelian varieties are so significant in cryptography?

First these structures provide perfect abstractions to instantiations of them like a group of integers $\mathbb{Z}$, and due to this abstraction, we can prove theorems for these structures that won’t be possible without introducing their properties like commutativity in abelian groups.¹1. link contains beautiful answers about why these different varieties of a mathematical structure is needed.

Now, set underlying the group can have finite elements, namely Finite Groups. For example: ${\mathbb{Z}}_5$, having elements $0,1,2,3,4$.

Prove in a finite group of order m: $g^m=e$.

Isomorphism in groups: Two groups are isomorphic to each other if there exists a map from $f:G\to H$, and written as $G\simeq H$.

• $f$ is bijection
• group operation commutes: $f(g_1{\oplus }_G{g}_2)=f(g_1){\oplus }_{H}f(g_2)$

Direct product in groups: Given two group $G({\oplus }_G),H({\oplus }_H)$, direct group is written as $G\times H:(g,h)$ where $g\in G,h\in H$, containing $|G|\cdot |H|$ elements, and group operation is applied component wise: $(g,h)\oplus (g^{\prime },h^{\prime })=(g{\oplus }_G{g}^{\prime }),(h{\oplus }_H{h}^{\prime })$.

Using this, crt is proven.

Symmetric Group $S_n$: set of all permutation of set of indices $\{1,2,\dots ,n\}$. Finite group of order $n!$

• Example: $S_2$ has two elements $e,\tau$. Identify both its elements, identity, and inverse.

Prove $S_n$ for $n\ge 3$ is non-abelian.

Symmetric group of a set $T$, defined as $\text{Sym}(T)=\{\text{all bijections }a:T\to T\}$ under composition $a\circ b(t)=a(b(t))$, where $a,b$ are bijections of the set. This can be referred to as automorphism group of T, written as $\text{Aut}(T)$.

We usually define symmetric groups using particular permutation elements. Let $x=(123)$ and $y=(12)$. According to the rules, $x^3=1,y^2=1,yx=x^{2}y$. And the six elements of the group are $\{1,x,y,x^2,xy,x^{2}y\}$.

Subgroup

Subset $H$ of $G$ satisfying group axioms. Expressed as $H\le G$.

• Improper or Trivial subgroups: $G$ itself and identity element.
• Proper subgroups: all other subgroups.

Theorem:

• Non empty subset $H\subset G$ is a subgroup iff H’s operation is multiplication.
• For subgroup $H\le G$ and $h\in G$, $hH=H=Hh$. Can be generalised to any set $S\subset H⟹SH=H=HS$.

Lagrange's theorem: states that for any finite group $G$, order of every subgroup $H$ divides order of group $G$. Formally, for $H$ being subgroup of $G$, $|G|=n|H|$, for some integer $n$.

Proof: Take an element $r_1\in G,r_1\notin H$, then $|r_{1}H|=|H|$. Since $r_{1}H,H$ are disjoint, then $|r_{1}H\cup H|=2|H|$. Take $n$ such subgroups of $G$, such that $|r_{1}H\cup r_{2}H\cup \cdots \cup r_{n}H|=n|H|=G$.

Corollary: let $G$ be a group, and $g\in G$, then order of $g$ divides $|G|$.

Theorem: If $H_1,H_2,\dots$ are subgroups, then $H_1\cap H_2\cap \dots$ is subgroup of each of $H_1,H_2,\dots$.

• Independent elements: $g_i\notin ⟨g_1,\dots ,g_{i-1},g_{i+1},\dots ,g_m⟩$, i.e. $g_i$ isn’t generated by any of the other elements.
• Every finite group has independent set of generators which can be used to define relations.
• Defining relation: Relation defined using independent elements.

\usepackage{tikz-cd}
\begin{document}
\begin{tikzcd}
    T
    \arrow[drr, bend left, "x"]
    \arrow[ddr, bend right, "y"]
    \arrow[dr, dotted, "{(x,y)}" description] & & \\
    K & X \times_Z Y \arrow[r, "p"] \arrow[d, "q"]
    & X \arrow[d, "f"] \\
    & Y \arrow[r, "g"]
    & Z
\end{tikzcd}
\quad \quad
\begin{tikzcd}[row sep=2.5em]
A' \arrow[rr,"f'"] \arrow[dr,swap,"a"] \arrow[dd,swap,"g'"] &&
  B' \arrow[dd,swap,"h'" near start] \arrow[dr,"b"] \\
& A \arrow[rr,crossing over,"f" near start] &&
  B \arrow[dd,"h"] \\
C' \arrow[rr,"k'" near end] \arrow[dr,swap,"c"] && D' \arrow[dr,swap,"d"] \\
& C \arrow[rr,"k"] \arrow[uu,<-,crossing over,"g" near end]&& D
\end{tikzcd}
\end{document}

Example

• $G{L}_n\le \text{Sym}({\mathbb{R}}^n)$

Cyclic Groups

Finite groups that can be represented as $g,g⨁g,\cdots$, i.e. a generator $g$, which can create the complete set with the group operation, written $H=⟨g⟩$.

Fundamental theorem of finite cyclic groups: if $\mathbb{G}$ is a finite cyclic group such that $|G|=n$, and $k:k|n$, then, $\mathbb{G}[k]$ refers to unique finite cyclic subgroup of $\mathbb{G}$ with order $k$.
Proof of above theorem follows from Lagrange’s theorem.

Theorem: Every group of composite order has proper subgroups.

Cauchy’s theorem: states that let $G$ be a finite group, and $p$ a prime dividing $|G|$, then $G$ contains a subgroup of order $p$.

Note: when the group is abelian, i.e. the group operation supports commutativity, the group operation is written mostly additively.

Questions:

• Define and give example of an additive group. Similarly for multiplicative group.
• take a finite group for above example. Modulus can be a prime, composite prime, prime power. give order for all of them.
• define direct product of groups $G\times H$. Prove that for groups $G_1,G_2$, intersection of groups form a subgroup of each base group.

Example

• matrix $\left[\begin{array}{cc}1& 1\\ 0& 1\end{array}\right]$ has infinite order in $G{L}_2(\mathbb{R})$.
• Klein four group V $\left[\begin{array}{cc}\pm 1& \\ & \pm 1\end{array}\right]$ is the simplest non-cyclic group
• Quaternion group $H=\{\pm 1,\pm \mathbf{i},\pm \mathbf{j},\pm \mathbf{k}\}$ of order 8, where $1=\left[\begin{array}{cc}1& 0\\ 0& 1\end{array}\right],\mathbf{i}=\left[\begin{array}{cc}i& 0\\ 0& -i\end{array}\right],\mathbf{j}=\left[\begin{array}{cc}0& 1\\ -1& 0\end{array}\right],\mathbf{k}=\left[\begin{array}{cc}0& i\\ i& 0\end{array}\right]$

Cofactor – It’s the ratio of order of the curve group and order of the subgroup $hr=n$. Usually, cofactor should be very small in order to avoid subgroup attacks on discrete logarithms. But in pairing-based cryptography, the cofactors of $G_1$, $G_2$ and $G_T$ can be very large.
By multiplying by the cofactor, a point on the curve is mapped to the appropriate group known as cofactor clearing. Cofactors for $G_1$ and $G_2$ are as follows:

• $h_1=(\text{x}-1{)}^2/3$
• $h_2=$

Group Homomorphisms

Let $G,G^{\prime }$ be two multiplicative groups, and $\phi :G\to G^{\prime }$ is a map such that $\forall a,b\in G,\phi (ab)=\phi (a)\phi (b)$.

Examples:

• the map $\phi :Z^{+}\to G$ defined by $\phi (n)=a^n$, where $a$ is a given element of $G$
• the sign homomorphism $\sigma :S_n\to \{\pm 1\}$ that sends a permutation to its sign

Group homomorphism determines two important subgroups: kernel and image

• Image of a group homomorphism is the image of the map $\phi$, $\text{im}\phi$
• Kernel is the element in domain G that maps to identity element $\phi (a)=1$

Special kernel groups

• Kernel of determinant homomorphism $G{L}_n\to {\mathbb{R}}^{\times }$ is the special linear group $S{L}_n(\mathbb{R})$.
• Kernel of sign homomorphism $\sigma :S_n\to \{\pm 1\}$ is called Alternating group $A_n$

Left Coset: if $H\le G$ and $a\in G$, notation $aH$ stands for left coset of $H$ in $G$, and denoted as $aH=\{g\in G|g=ah\text{ for some }h\in H\}$

Normal subgroup: A subgroup $N\le G$ is a normal subgroup if for $a\in N$ and $g\in G$, conjugate $ga{g}^{-1}\in N$.

Prove Kernel of a homomorphism is a normal subgroup.

• $S{L}_n$ is a normal subgroup of $G{L}_n$
• $A_n$ is a normal subgroup of $S_n$
• not all subgroups of non-abelian group is normal. For example, $S_3$

Center of a group G, often denoted by $Z$, is the set of elements that commute with all elements of G. $Z=\{z\in G|zx=xz,\forall x\in G\}$.

• Center of group $S{L}_n$ is $\pm I$
• Center of $S_n$ is trivial group for $n\ge 3$

Group Isomorphism

An isomorphism $\phi :G\to G^{\prime }$ is a bijective group homomorphism such that $\phi (ab)=\phi (a)\phi (b),\forall a,b\in G$.

Example

• Exponential map: $e:{\mathbb{R}}^{+}\to \mathbb{R}$ from additive group to multiplicative group of real numbers
• set $\mathcal{P}$ of $n\times n$ permutation matrices, then map $\phi :S_n\to P$ is an isomorphism

Prove $\phi$ is an isomorphism, then ${\phi }^{-1}$ is an isomorphism. $\phi$ is bijective implies ${\phi }^{-1}$ is bijective. Show that ${\phi }^{-1}$ is a homomorphism.

Isomorphic class: set of all groups isomorphic to a given group G form isomorphic class of $G$. Two groups in an isomorphic class is isomorphic.

• Finding all isomorphic groups to a group is too difficult, but easy for some groups like finite cyclic group of prime order p.
• Automorphism: isomorphism from $G\to G$. Example: Conjugate by $g$ is an automorphism.
  • All automorphism of cyclic group of order 10 – Automorphism means group operation is preserved. So, a generator must also be a generator after the morphism.
  • All automorphism of Symmetric group $S_3$ – Since this isn’t a cyclic group, but contains many partitions. Each generator of a partition must map to the other.

Equivalence relation

Relation defined $a\sim b$ on a set $S$ such that following three axioms holds between two elements $a,b$:

• Reflexive
• Symmetric
• Transitive

Examples:

• Relation on a group defined by $a\sim b$ if a,b are elements with same order.
• Conjugacy

Prove Equivalence class defines a partition on set S and conversely partition of S defines an equivalence relation.

Any equivalence relation can be defined by a map $\pi :S\to \bar{S}$ that maps an element $a\in S$ to its equivalence class $\pi (a)=[C_a]$. Set $\bar{S}$ is defined as the set of the equivalence classes of $S$.

The inverse image of an element $\bar{s}\in \bar{S}$ is the set $\{s\in S|f(s)=t\}$. Also called Fibres of the map.

Example: map $f:G\to \mathbb{N}$ where $f(a)$ is the order of the element $a$ of $G$. Here, the fibres are set of elements with same order.

Equivalence relation defined by a group homomorphism $\phi :G\to G^{\prime }$ is referred to as congruence, $a\equiv b$ if $\phi (a)=\phi (b)$. Thus, $a\equiv b$ iff b is in coset $aK$ of G where $K$ is the homomorphism kernel.

References

• Ben Lynn’s notes
• Forney’s Finite Field introduction
• Ben Lynn’s Number theory notes

Footnotes

1. link contains beautiful answers about why these different varieties of a mathematical structure is needed. ↩