Cosets and Lagrange's Theorem

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

A subgroup H partitions a group G into cosets of equal size. Since the cosets tile G without overlap, |H| must divide |G|. That is Lagrange's theorem: the order of any subgroup divides the order of the group. This one fact constrains everything.

Left cosets

Given a subgroup H of G and an element g in G, the left coset gH is the set of all g * h for h in H. Two cosets are either identical or disjoint. Together they partition G into pieces of the same size as H.

Scheme

; Cosets of H = (0, 3) in Z6

(define H '(0 3))

(define (coset g H n)
  (map (lambda (h) (modulo (+ g h) n)) H))

(display "0 + H = ") (display (coset 0 H 6)) (newline)
(display "1 + H = ") (display (coset 1 H 6)) (newline)
(display "2 + H = ") (display (coset 2 H 6)) (newline)
(display "3 + H = ") (display (coset 3 H 6)) (newline)
(display "4 + H = ") (display (coset 4 H 6)) (newline)
(display "5 + H = ") (display (coset 5 H 6)) (newline)
; 0+H = 3+H, 1+H = 4+H, 2+H = 5+H
; Three distinct cosets, each of size 2.

Lagrange's theorem

If H is a subgroup of a finite group G, then |H| divides |G|. This is Lagrange's theorem. The number of distinct cosets is |G|/|H|, called the index of H in G. Consequence: the order of any element divides the order of the group.

Scheme

; Lagrange's theorem in action
; G = Z12, |G| = 12
; Subgroups have order dividing 12: 1, 2, 3, 4, 6, 12

(define (cyclic 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 each element of Z12:") (newline)
(let loop ((g 0))
  (when (< g 12)
    (let ((sub (cyclic (if (= g 0) 12 g) 12)))
      (display "  <") (display g) (display "> has order ")
      (display (length sub))
      (display (if (= 0 (modulo 12 (length sub))) " | divides 12" " ERROR"))
      (newline))
    (loop (+ g 1))))

Notation reference

Math	Scheme	Python	Meaning
gH	(coset g H n)	coset(g, H, n)	Left coset of g
[G:H]	(/ \|G\| \|H\|)	len(G)//len(H)	Index: number of cosets
\|H\| \| \|G\|	divides	divides	Lagrange's theorem

Neighbors

Algebra track

← Ch.4 Isomorphisms — coset counting constrains possible isomorphisms
Ch.6 Rings — adding a second operation

Translation notes

Judson proves Lagrange's theorem in Ch. 6 after introducing cosets. The proof is combinatorial: cosets partition G into equal-sized pieces, so |G| = [G:H] * |H|. Normal subgroups and quotient groups (which enable the first isomorphism theorem) are a direct extension: a normal subgroup is one where left and right cosets coincide, making the set of cosets itself a group.

← Isomorphisms by june.kim Rings · 6 of 8 →