5.3 Cosets, Normal Subgroups, Rings, Integral Domains & Fields

Back to Discrete Mathematics Notes

📚Module 05: Group Theory & Algebraic StructuresTopic 5.3: Cosets, Normal Subgroups, Rings, Integral Domains & Fields⏱️5 min read

🎯High-Yield For:Semester Exams • GATE CSE • Technical Interviews

💡 Core Intuition: The 3-Second Mental Model

🍳 The Everyday Analogy: Slicing Cakes & Adding Multiplication to the Mix

Think of zooming out from a single operation to dual operations:

1. Cosets (Evenly Sliced Cake): You have a large cake ($G$) and a recipe that bakes a baseline slice ($H$). Shifting that baseline slice by different ingredients ($gH$) cuts the entire cake into identical, non-overlapping slices. Every slice has the exact same size as the baseline.
2. Normal Subgroups & Quotient Groups: If a subgroup is symmetrically placed (left slice equals right slice: $gH = Hg$), you can treat each entire slice as a single new object! Grouping slices together produces a smaller, coarser macro-system called the Quotient Group ($G/N$).
3. The Leap to Two Operations (Rings & Fields): Until now, we only had one operation (like addition). But real-world computation requires both Addition and Multiplication:
   • Ring: You can add, subtract, and multiply (like integers $\mathbb{Z}$). But division is not guaranteed!
   • Integral Domain: A ring with no "zero-divisor gremlins" ($a \times b = 0$ strictly means $a = 0$ or $b = 0$).
   • Field: The ultimate algebraic playground! You can add, subtract, multiply, AND divide by any non-zero element (like rational numbers $\mathbb{Q}$, reals $\mathbb{R}$, or prime modulo fields $\mathbb{Z}_p$).

💻 Bridging to Computer Science: Galois Fields in AES & Error-Correcting Codes

In computer systems:

• AES Encryption (Rijndael S-Box): Modern hardware encryption relies entirely on the finite Galois Field $\text{GF}(2^8)$ where byte substitutions perform multiplicative inversions modulo an irreducible polynomial ($x^8 + x^4 + x^3 + x + 1$).
• RAID-6 Storage & Reed-Solomon Erasure Coding: Cloud storage (AWS S3, Google Colossus) calculates parity blocks using linear algebra over Galois Fields $\text{GF}(2^8)$.
• Relational Algebras: SQL engines optimize queries over commutative rings where arithmetic transformations preserve relational algebra invariants.

📑Table of Contents

• 🍰 Cosets: Slicing the Group into Equivalence Classes
• 🛡️ Normal Subgroups & Quotient (Factor) Groups
• 🏛️ The Two-Operation Algebraic Systems: Rings, Domains & Fields
• 📝 Step-by-Step Worked Examples
  • Example 1: Finding Cosets of a Subgroup
  • Example 2: Diagnosing Zero Divisors and Fields
• 🎯 Exam & Interview Pitfall Check

---

🍰 Cosets: Slicing the Group into Equivalence Classes

📖Definition 5.5: Left and Right Cosetsdefinition

Let $H$ be a subgroup of $(G, *)$, and let $a \in G$ be an arbitrary element.

1. The Left Coset of $H$ with representative $a$ is the set: $$aH = \{ a * h \mid h \in H \}$$
2. The Right Coset of $H$ with representative $a$ is the set: $$Ha = \{ h * a \mid h \in H \}$$

In additive notation, left and right cosets are denoted $a + H$ and $H + a$.

📐Theorem 5.7: Fundamental Coset Invariantstheorem

For any subgroup $H \le G$ and elements $a, b \in G$:

1. Self-Containment: $a \in aH$ (since $e \in H \implies a * e = a \in aH$).
2. Identical Size: Every coset has the exact same cardinality as $H$: $$\vert aH \vert = \vert H \vert = \vert Ha \vert$$
3. Equivalence Partition: Any two left cosets $aH$ and $bH$ are either completely identical or completely disjoint: $$aH = bH \iff a^{-1} b \in H \quad (\text{or } a - b \in H)$$ $$aH \cap bH = \emptyset \quad \text{otherwise}$$
4. In general, a left coset $aH$ does NOT have to equal the right coset $Ha$, unless the group is Abelian or $H$ is a normal subgroup!

---

🛡️ Normal Subgroups & Quotient (Factor) Groups

📖Definition 5.6: Normal Subgroupdefinition

A subgroup $N \le G$ is called a Normal Subgroup (denoted $N \trianglelefteq G$) if its left and right cosets coincide for every element in the group:

$$\forall g \in G, \quad gN = Ng$$

Equivalently, $N$ is normal if it is closed under all inner automorphisms (conjugation):

$$\forall g \in G, \; \forall n \in N, \quad g * n * g^{-1} \in N$$

Universal Normal Subgroup Invariants

Conditions under which subgroups are guaranteed to be normal

⭐

Abelian Groups

Universal Normality

• In an Abelian group, EVERY subgroup is automatically a normal subgroup!
• Reason: g * n = n * g for all elements, so gN = Ng trivially holds.

⚖️

Subgroups of Index 2

Index Invariant

• If [G : H] = |G| / |H| = 2, then H is ALWAYS a normal subgroup!
• Reason: There are only 2 cosets: H and G \ H. Both left and right cosets must partition identically.

🎯

Center of a Group Z(G)

Central Elements

• Z(G) = { z ∈ G | ∀ g ∈ G, zg = gz }.
• The center of any group is ALWAYS an Abelian normal subgroup of G.

📖Definition 5.7: Quotient Group (Factor Group G/N)definition

If $N \trianglelefteq G$ is a normal subgroup, the set of all cosets:

$$G/N = \{ gN \mid g \in G \}$$

forms a well-defined group called the Quotient Group (or Factor Group) under coset multiplication:

$$(aN) * (bN) = (a * b)N$$

The order of the quotient group is the index of $N$ in $G$:

$$\vert G/N \vert = [G : N] = \frac{\vert G \vert}{\vert N \vert}$$

(Crucial Invariant: If $N$ is NOT normal, coset multiplication is not well-defined, and $G/N$ fails to be a group!).

---

🏛️ The Two-Operation Algebraic Systems: Rings, Domains & Fields

When a set is equipped with two binary operations (Addition $+$ and Multiplication $\cdot$), we enter the domain of ring theory.

The Hierarchical Tower of Two-Operation Algebraic Structures

Progressive specialization from basic rings to full Galois Fields

Structure 1

Ring (R, +, ·)

💍

(R, +) is an Abelian group, (R, ·) is a Semigroup, and · distributes over +.

Additive identity 0 and additive inverses -a existMultiplication is associative

↓Require Commutative Multiplication & Multiplicative Unity

Structure 2

Commutative Ring with Unity

⚙️

Multiplication is commutative (a · b = b · a) and multiplicative identity 1 exists.

1 · a = a · 1 = aExamples: (ℤ, +, ·), (ℤₙ, +ₙ, ×ₙ)

↓Eliminate Zero Divisors

Structure 3

Integral Domain

🛡️

A commutative ring with unity possessing NO zero divisors.

a · b = 0 ⟹ a = 0 or b = 0Multiplicative cancellation law holds: ab = ac (a ≠ 0) ⟹ b = cExample: (ℤ, +, ·) is an integral domain

↓Require Multiplicative Inverses for All Non-Zero Elements

Structure 4

Field (F, +, ·)

👑

An integral domain where every non-zero element has a multiplicative inverse.

(F, +) is an Abelian group; (F \ {0}, ·) is an Abelian groupDivision is fully defined for all non-zero elementsExamples: (ℚ, +, ·), (ℝ, +, ·), (ℂ, +, ·), and finite fields (ℤₚ, +ₚ, ×ₚ) for prime p

Integral Domain vs Field: The Decisive Multiplicative Inverse Gap

Why every field is an integral domain, but integers fail to form a field

Integral Domain

Integral Domain (e.g., ℤ)

🛡️

Dominant Architecture / DomainZero-Divisor Free Multiplicative Ring

• •Satisfies: Commutative, Unity (1), and Zero-Divisor Free.
• •Missing: Non-zero elements DO NOT need to have multiplicative inverses.
• •Example: In ℤ, element 2 has NO inverse (1/2 ∉ ℤ). You cannot divide!

"No zero divisors, but division is incomplete."

Field

Field (e.g., ℚ, ℝ, ℤₚ)

👑

Dominant Architecture / DomainUniversal Arithmetic with Non-Zero Inversion

• •Satisfies: All integral domain axioms PLUS multiplicative inverses.
• •Every a ≠ 0 has a⁻¹ such that a · a⁻¹ = 1.
• •Wedderburn's Theorem: EVERY finite integral domain is automatically a field!

"Complete arithmetic: Addition, Subtraction, Multiplication, and Division."

📐Theorem 5.8: Wedderburn's Theorem & Modulo Field Classificationtheorem

1. Wedderburn's Little Theorem: Every finite integral domain is automatically a field!
2. Modulo Arithmetic Classification:
   • $(\mathbb{Z}_n, +_n, \times_n)$ is a commutative ring with unity for all $n \ge 2$.
   • $(\mathbb{Z}_n, +_n, \times_n)$ is an integral domain if and only if $n$ is a prime number $p$!
   • Consequently, $(\mathbb{Z}_p, +_p, \times_p)$ is a Field (Galois Field $\text{GF}(p)$) if and only if $p$ is prime!
   • If $n$ is composite ($n = a \cdot b$ with $1 \lt a, b \lt n$), then $a \times_n b \equiv 0 \pmod n$, making $a$ and $b$ non-zero zero divisors. Hence, composite $\mathbb{Z}_n$ is never an integral domain and never a field!
3. Symmetric & Permutation Groups: The set of all bijective functions on a finite set of $n$ elements forms a group under function composition, known as the Symmetric Group $S_n$.
   • Order: $\vert S_n \vert = n!$.
   • For $n \ge 3$, $S_n$ is strictly non-Abelian.
   • The alternating subgroup $A_n$ (all even permutations) has order $n! / 2$, index $[S_n : A_n] = 2$, and is therefore a normal subgroup.

---

📝 Step-by-Step Worked Examples

Example 1: Finding Cosets of a Subgroup

Problem Statement: Let $G = (\mathbb{Z}_{12}, +_{12})$ and let $H = \{0, 4, 8\}$ be a subgroup of $G$.

1. Find all distinct left cosets of $H$ in $G$.
2. Verify Lagrange's partition invariant and compute the index $[G : H]$.
3. Construct the quotient group $G/H$.

Step-by-Step Solution:

1. Step 1: Compute Left Cosets

   • In additive notation, the coset is $a + H = \{(a + h) \bmod 12 \mid h \in H\}$.
   • Coset 1 ($a = 0$): $$0 + H = \{0, 4, 8\} = H$$
   • Coset 2 ($a = 1$): $$1 + H = \{1, 5, 9\}$$
   • Coset 3 ($a = 2$): $$2 + H = \{2, 6, 10\}$$
   • Coset 4 ($a = 3$): $$3 + H = \{3, 7, 11\}$$
   • Next element is $4$: $4 + H = \{4, 8, 12 \equiv 0\} = \{0, 4, 8\} = 0 + H$ (repetition).

2. Step 2: Verify Lagrange's Partition Invariant

   • The four distinct cosets are $\{0+H, 1+H, 2+H, 3+H\}$.
   • They are completely mutually disjoint: $$\{0, 4, 8\} \cup \{1, 5, 9\} \cup \{2, 6, 10\} \cup \{3, 7, 11\} = \mathbb{Z}_{12}$$
   • Total elements: $4 \times 3 = 12 = \vert G \vert$.
   • The index of $H$ in $G$ is: $$[G : H] = \frac{\vert G \vert}{\vert H \vert} = \frac{12}{3} = 4$$

3. Step 3: Quotient Group $G/H$

   • Since $\mathbb{Z}_{12}$ is Abelian, $H$ is a normal subgroup.
   • The quotient group is: $$G/H = \{0+H, 1+H, 2+H, 3+H\}$$
   • $\vert G/H \vert = 4$. This quotient group is cyclic and isomorphic to $(\mathbb{Z}_4, +_4)$.

Key Takeaway: Cosets perfectly partition the parent group into $[G : H]$ equal-sized, mutually disjoint subsets.

---

Example 2: Diagnosing Zero Divisors and Fields

Problem Statement: Determine whether the following algebraic structures are integral domains and/or fields:

1. $(\mathbb{Z}_5, +_5, \times_5)$
2. $(\mathbb{Z}_8, +_8, \times_8)$
3. $(\mathbb{Z}, +, \cdot)$ (the standard integers)

Step-by-Step Solution:

1. Analysis of $(\mathbb{Z}_5, +_5, \times_5)$:

   • $5$ is a prime number.
   • Elements are $\{0, 1, 2, 3, 4\}$.
   • Non-zero products modulo 5:
     • $1 \times 1 = 1$
     • $2 \times 3 = 6 \equiv 1$
     • $4 \times 4 = 16 \equiv 1$
   • No two non-zero elements multiply to $0$. Zero divisors = none.
   • Every non-zero element has a multiplicative inverse: $1^{-1} = 1, 2^{-1} = 3, 3^{-1} = 2, 4^{-1} = 4$.
   • Conclusion: $(\mathbb{Z}_5, +_5, \times_5)$ is both an Integral Domain AND a Field ($\text{GF}(5)$)!

2. Analysis of $(\mathbb{Z}_8, +_8, \times_8)$:

   • $8$ is composite ($8 = 2 \times 4$).
   • Consider elements $2, 4 \in \mathbb{Z}_8$ ($2 \neq 0, 4 \neq 0$): $$2 \times_8 4 = 8 \equiv 0 \pmod 8$$
   • The product of two non-zero elements is zero!
   • Thus, $2$ and $4$ are zero divisors.
   • Conclusion: $(\mathbb{Z}_8, +_8, \times_8)$ is NEITHER an Integral Domain NOR a Field!

3. Analysis of $(\mathbb{Z}, +, \cdot)$:

   • For standard integers, if $a \cdot b = 0$, then $a = 0$ or $b = 0$. Zero divisors = none.
   • Commutative with unity ($1$).
   • It is an Integral Domain.
   • However, for any integer $n \notin \{1, -1\}$, its reciprocal $1/n$ is not an integer.
   • Conclusion: $(\mathbb{Z}, +, \cdot)$ is an Integral Domain, but NOT a Field!

Key Takeaway: Primes produce finite fields ($\mathbb{Z}_p$), composites contain zero divisors and fail to be domains, while integers form an infinite integral domain that lacks multiplicative inverses.

---

🎯 Exam & Interview Pitfall Check

Core Conceptual Questions

Question 1: Can a subgroup of index 2 ever fail to be a normal subgroup? Key Focus Points: No! By Theorem 5.7, if $[G : H] = 2$, there are only 2 left cosets ($H$ and $G \setminus H$) and only 2 right cosets ($H$ and $G \setminus H$). Because both must partition $G$, the left cosets and right cosets are identical ($gH = Hg$). Thus, every subgroup of index 2 is strictly normal!

Question 2: Does the cancellation law $a \cdot b = a \cdot c \implies b = c$ hold in every commutative ring? Key Focus Points: No! The cancellation law only holds if $a$ is NOT a zero divisor. In an integral domain (or field), there are no zero divisors, so multiplicative cancellation holds for all $a \neq 0$. In general rings with zero divisors (like $\mathbb{Z}_6$ where $2 \cdot 1 = 2 \cdot 4 = 2$), cancellation fails!

Common Interview Traps: Architectural Trade-Offs

Trap 1: Attempting to construct a quotient group from a non-normal subgroup Why it fails: If $H$ is not normal, coset multiplication $(aH)(bH) = (ab)H$ is ill-defined: picking different representatives from the same coset produces different result cosets! $G/H$ only forms a group if $H$ is strictly normal.

Trap 2: Assuming all finite fields have prime order Why it fails: Finite fields (Galois Fields) exist for any prime power $q = p^k$ (e.g., $\text{GF}(2^8) = \text{GF}(256)$ used in AES). While $\mathbb{Z}_n$ is a field only when $n$ is prime, fields of order $p^k$ are constructed as polynomial quotient rings $\mathbb{Z}_p[x] / \langle f(x) \rangle$ using irreducible polynomials!

🗺️View Complete Discrete Mathematics Roadmap & Syllabus

← Previous Topic5.2 Cyclic Groups, Generators, Subgroups & Lagrange's TheoremNext Topic →6.1 Propositions, Connectives, Truth Tables & Logical Equivalences