Subgroups

Tom Judson · GFDL · Abstract Algebra: Theory and Applications, Ch. 2

A subgroup is a subset of a group that is itself a group under the same operation. The cyclic subgroup generated by a single element is the simplest kind. Every group is tiled by its subgroups, and the lattice of subgroups tells you the group's internal architecture.

Two-step subgroup test

A nonempty subset H of G is a subgroup if: (1) for all a, b in H, a * b is in H; (2) for all a in H, a⁻¹ is in H. Equivalently, the one-step test: H is a subgroup if for all a, b in H, a * b⁻¹ is in H.

Scheme

; Subgroup test: is {0, 2} a subgroup of Z4?
; Z4 = integers mod 4 under addition.

(define (mod4+ a b) (modulo (+ a b) 4))
(define (mod4-inv a) (modulo (- 4 a) 4))

(define H '(0 2))

; Test 1: closure
(display "0+0=" ) (display (mod4+ 0 0)) (newline)
(display "0+2=" ) (display (mod4+ 0 2)) (newline)
(display "2+0=" ) (display (mod4+ 2 0)) (newline)
(display "2+2=" ) (display (mod4+ 2 2)) (newline)

; Test 2: inverses
(display "inv(0)=" ) (display (mod4-inv 0)) (newline)
(display "inv(2)=" ) (display (mod4-inv 2)) (newline)
; All results in (0, 2). So (0, 2) is a subgroup of Z4.

Cyclic groups and generators

The cyclic subgroup generated by a is the set of all powers of a: a, a*a, a*a*a, ... until you get back to the identity. The order of a is how many steps that takes. If one element generates the whole group, the group is cyclic. Z_n is cyclic, generated by 1.

Scheme

; Generate the cyclic subgroup of 3 in Z12
; Keep adding 3 until we return to 0.

(define (cyclic-subgroup gen n)
  (let loop ((current gen) (elements (list 0)))
    (if (= current 0)
        (reverse elements)
        (loop (modulo (+ current gen) n)
              (cons current elements)))))

(display "Subgroup generated by 3 in Z12: ")
(display (cyclic-subgroup 3 12)) (newline)
; (0, 3, 6, 9) -- order 4

(display "Subgroup generated by 4 in Z12: ")
(display (cyclic-subgroup 4 12)) (newline)
; (0, 4, 8) -- order 3

(display "Subgroup generated by 1 in Z12: ")
(display (cyclic-subgroup 1 12))
; All of Z12 -- 1 is a generator

Order of an element

The order of an element a, written |a|, is the smallest positive integer n such that a^n = e. In Z12, the order of 3 is 4 because 3+3+3+3 = 12 = 0 mod 12. The order of an element always divides the order of the group.

Scheme

; Order of each element in Z12

(define (order-in-zn a n)
  (let loop ((power a) (count 1))
    (if (= (modulo power n) 0)
        count
        (loop (+ power a) (+ count 1)))))

(display "Orders in Z12:") (newline)
(let loop ((a 1))
  (when (<= a 11)
    (display "  |") (display a) (display "| = ")
    (display (order-in-zn a 12)) (newline)
    (loop (+ a 1))))
; Notice: all orders divide 12.

Subgroup lattice of Z12

The subgroups of Z12 are ordered by inclusion. Drawing them as a lattice reveals which subgroups contain which. Every subgroup of a cyclic group is cyclic, and there is exactly one subgroup for each divisor of 12.

Notation reference

Math	Scheme	Python	Meaning
H ≤ G	subgroup test	subgroup test	H is a subgroup of G
⟨a⟩	(cyclic-subgroup a n)	cyclic(a, n)	Cyclic subgroup generated by a
\|a\|	(order-in-zn a n)	order(a, n)	Order of element a
Z_n	(modulo (+ a b) n)	(a+b)%n	Integers mod n

Neighbors

Algebra track

← Ch.1 Groups — the four axioms
Ch.3 Homomorphisms — maps that preserve group structure

Category theory connections

Milewski Ch.3 — a monoid viewed as a one-object category is a cyclic group when every morphism is invertible

Translation notes

Judson treats cyclic groups in a separate chapter (Ch. 4) and proves the fundamental theorem of cyclic groups: every subgroup of Z_n is of the form Z_(n/d) for a divisor d of n. We compress this into the lattice diagram. The one-step subgroup test (a * b inverse in H) is equivalent to the two-step test but more elegant. The order-divides-group-order fact is a preview of Lagrange's theorem in Ch. 5.

← Groups by june.kim Homomorphisms · 3 of 8 →