Date 
Class 
Topics 
W 5/4

39


T 5/3

38

Platonic solids: the five platonic solids, their numerology, and their rotational symmetry groups. Duality between the cube and the octahedron and between the dodecahedron and the icosahedron; the tetrahedron is selfdual. Classification of finite rotation groups. See section 5.9 (Finite subgroups of the rotation group) in Artin’s Algebra for a nice presentation.

Θ 4/28

37

Errorcorrecting codes. Examples: parity check code, repetition code. Linear codes. Hamming distance and Hamming weight (see section 24.1). If the minimimum Hamming weight of a nonzero element in a linear code is at least s + 1 (respectively, 2s + 1) then the code detects (respectively, corrects) s errors: see Theorem 24.1. Hamming’s [7, 4] code constructed using arithmetic in (Z_{2}[x])_{x3 + x + 1}: see code III in section 25A of Childs, A Concrete Introduction to Higher Algebra. Generalizations to [2^{r} – 1, 2^{r} – 1 – r] Hamming codes. See Example in section 24.4 for an alternate construction of the Hamming codes using linear algebra over Z_{2}.

W 4/27

36


T 4/26

35

Example: (Z_{3}[x])_{x2 + 1}, a finite field with 9 elements. The congruence class [x] is a square root of –1, so this field is essentially Z_{3}[i]. One can also show that it is the same as (Z[i])_{3}, the field of residue classes modulo 3 in the Gaussian integers.
Theorem 23.4 (primitive root theorem): if F is a finite field, then its unit group U(F) is cyclic. A primitive root of F is a generator of U(F). There are many proofs of Theorem 23.4: see Prof. Conrad’s notes on the cyclicity of Z_{p}^{×}, a number of which work for finite fields more generally). Most use Theorem 22.8.2 (a polynomial over field has no more than degreemany distinct roots) plus one additional fact. The proof given in class is the third proof of the Conrad notes, and the additional fact is Conrad’s Theorem 3.1 (in a finite abelian group, the order of every element divides the maximal order of any element; see also optional problem (10) on HW #11). The proof in the textbook (basically the first proof of the Conrad notes) uses Theorem 20.9 as the additional fact instead.
Public key cryptography. DiffieHellman secret sharing: first published publickey protocol, 1976. RSA public crypography, 1978. See chapter 7 of Judson.

Θ 4/21

34

Consquences of division algorithm in F[x] for a field F.
 Chain of reasoning: Division algorithm implies Euclid’s algorithm (section 22.6), which implies Bézout’s lemma (Theorem 22.6), which implies the fundamental lemma (Exercise 22.7.4), which implies unique factorization into irreducibles (Theorem 22.7).
 Congruence modulo a polynomial f(x) is an equivalence relation, and addition and multiplication is well defined on the resulting set of residue classes. Thus (F[x])_{f(x)} is a commuative ring, and the division algorithm implies that its elements are in bijection with polynomials in F[x] of degree < deg f(x).
 If f(x) is irreducible in F[x], then (F[x])_{f(x)} is a field (use Bézout’s lemma).
 In particular, if p is prime and π(x) is an irreducible polynomial in Z_{p}[x] of degree n, then (Z_{p}[x])_{π(x)} is a finite field of p^{n} elements (Theorem 23.3).
 Stated but not proved in class: Every finite field has p^{n} elements for some prime p and some n ≥ 1 (section 23.2), and every such finite field can be represented as (Z_{p}[x])_{π(x)} for some irreducible π(x) of degree n in Z_{p}[x] (follows from Theorem 23.4). Moreover, up to isomorphism there is a unique field of size p^{n} for each prime power p^{n} (existence: Theorem 23.9).
 Primitive element theorem (Theorem 23.4): The multiplicative group of any finite field is cyclic. Proof postponed to next class.
Running example of (Z_{2}[x])_{x3 + x + 1}, a finite field with 8 elements.

T 4/19

33

Division algorithm for polynomials over a field (Theorem 22.5; more generally you can divide by a monic polynomial over any commutative ring). Corollary: the element a of a field F is a root of the polynomial f(x) in F[x] if and only if x – a divides f (Theorem 22.8.1; more generally this is true over any commutative ring). A polynomial of degree n over a field has no more than n distinct roots (Theorem 22.8.2).

Θ 4/14

32

Polynomial functions on a commutative ring R vs. polynomials as elements of R[x]. Degree of a polynomial. How many roots can a polynomial have? Over a field, the degree of a product of two polymomials is the sum of their degrees, but this is not true over a general ring (see pp. 304–305). Second quiz. (Taught by Prof. Pollack.)

W 4/13

31

More on rings, their multiplicative groups of units (invertible elements), and fields. Examples: Z[√ 2] and Z[i]. Polynomial rings. (Taught by Prof. Pollack.)

T 4/12

30


Θ 4/7

29

More on Burnside’s orbitcounting lemma (Theorem 21.4). Sixbead twocolor necklace example redux. Proof of Burnside’s lemma. Counting copies of Symm(□) inside S_{4}. Counting edge colorings of a regular tetahedron.

W 4/6

28

Burnside’s orbitcounting lemma (Theorem 21.4). Example: how many different 6bead necklaces can be made out of out blue and yellow beads?

T 4/5

27

Proof of part (4) of the fundamental theorem of group actions. Proof of the orbitstablizer formula (Theorem 21.3). Example: Symmetries of a regular ngon acting on the set of n vertices. Example: Rotational symmetries of a regular tetrahedron acting on the set of 4 vertices (Example p.287 in section 21.3). Example: Rotational symmetries of a regular tetrahedron acting on the set of 6 edges. Review from class 25: the group of rotational symmetries of a tetrahedron is A_{4}. Subgroup diagram for A_{4} (Example p.275–276 in section 20.8). The converse of Lagrange’s theorem is false: A_{4} has no subgroups of order 6 .

Θ 3/31

26


W 3/30

25


T 3/29

24

The groups A_{3} and A_{4}. Half the permutations of S_{n} are even and half are odd (Theorem 12.6.2). Orbits and stabilizers for a group G of permutations of a set X, definitions and examples (see section 21.2).

Θ 3/24

23

Even and odd permutations (section 12.6): Every permutation in S_{n} is a product of transpositions. Theorem: the parity of the number of transpositions in any productoftranspositions representation of a permutation is the same (see Theorem 12.6.1 or user Cheerful Parsnip’s math.stackexchange answer for the proof given in class). Sign of a permutation. The alternating group (section 21.1).

W 3/23

22

Examples: elements of S_{4} and their cycle type; Symm
(_{4}^{3}□_{1}^{2}), the symmetries of a square with the given labeled vertex locations, as a subgroup of S_{4} (see also Table 21.1.1).

T 3/22

21

Permutation groups. S_{n}, the symmetric group on n letters. Cycles and kcycles, disjoint cycles. Cycle notation; multiplying elements in cycle notation. Cycle type. Counting elements of a particular cycle type. Order of a kcycle, of a product of disjoint cycles. See sections 10.6, 12.5. Coming up next: S_{4}; the sign of a permutation (section 12.6); chapter 21.

Θ 3/17

20


W 3/16

19


T 3/15

18

Lagrange’s theorem and consequences; see Theorems 20.8.2, 20.8.3, 20.8.4. Dihedral groups: symmetries of a regular ngon; see Prof. Keith Conrad’s writeup on dihedral groups.

Θ 3/3

17

(Left) cosets of a subgroup H in a group G: definition and examples. The cosets of H in G partition G. See section 20.8 and especially Theorem 20.8.1.

W 3/2

16

Discrete logarithm (or index) table for Z_{13}^{×} and using it to solve a mod13 equation. If you’d like to read more about discrete logarithms / indices, see section 8.6 of LozanoRobledo, Number Theory and Geometry, or some lecture notes of Dr. WyssGallifent.
Symm(▵) is generated by r := rot(120°) and f := flip(); these satisfy relations r^{3} = f^{2} = 1 and fr = r^{2}f (and in fact these generate all the relations that r and f satisfy).
Subgroup diagram for Symm(▵).

T 3/1

15

Fermat’s little theorem and Euler’s theorem (see end of section 13.3). Computing powers modulo m. Finding inverses and solving linear equations modulo m. Finding a generator for Z_{m}^{×}.

Θ 2/24

14

Subgroups. The subgroup generated by a set of elements in a group. Subgroup diagrams (also called subgroup lattices). Examples.
Theorem: any subgroup of a cyclic group is cyclic. (This theorem is proved in the textbook indirectly as part of Theorem 20.9; for the proof given in class, see Theorem 4.10 of Judson, an algebra textbook available free online.)

Θ 2/17


The order of a group element is the order of the cyclic subgroup it generates. Z_{2} × Z_{3} is cyclic but Z_{2} × Z_{2} is not. Exercise sheet #3, especially 1a and 1b. Quiz #1 return.

W 2/16


Theorem: any cyclic group is isomorphic either to Z (if it is generated by an element of infinite order) or to Z_{m} (if it is generated by an element of order m). See section 20.6 to the start of the first full paragraph on pp. 269.

T 2/15

11

Cyclic groups and generators: definitions and examples. See section 20.5. Quiz #1.

Θ 2/10

10

The order of an element a in a group. Examples. Theorem: a^{k} = 1 if and only if the order of a divides k. See section 20.4 and Theorem 20.4.

W 2/9

9


ΠΆ 2/8

8

Units modulo m as a group under multiplication (section 13.3 and especially Theorem 13.3.1). Equivalence relation definitions (sections 7.2, 7.3, and 12.2).

Θ 2/3

7

Group isomorphisms (see section 20.5). Rot(□) and Symm(▭) are not isomorphic. Two perspectives on Z_{m} (see section 13.2 for the “math” perspective). Integers modulo m form a group of order m under addition.

W 2/2

6

Group table for Symm(▵). Sudoku (or latin square property) of group tables: classification of groups of order 2 and 3 up to relabeling. Both Rotations(square) and Symm(nonsquare rectangle) have four elements: are these groups the same up to relabeling?

T 2/1

5

First properties of groups. Uniqueness of identity and inverses. Right and left cancelation. Group tables and latin squares. See section 20.3.

Θ 1/27

4

The defintion of a group. First examples: subsets of various number systems under addition and multiplication. Symm(▵) as a group and its group table. See sections 20.1, 20.2.

W 1/26

3

Exercise sheet #1 again, especially (5a) and (5b). Sketch of the proof of Theorem 5.4 (set maps are invertible iff bijective).

T 1/25


Functions. Injective, surjective, bijective functions. Composition of functions. Identity function. Inverse functions. A functions is invertible if and only it is bijective (Thereom 5.4).
Exercise sheet #1.

Θ 1/20


Syllabus. First examples of groups. A bit about integers modulo m. Symmetries of an equilateral triangle.
