| 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 self-dual. 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
|
Error-correcting 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 (Z2[x])x3 + x + 1: see code III in section 25A of Childs, A Concrete Introduction to Higher Algebra. Generalizations to [2r – 1, 2r – 1 – r] Hamming codes. See Example in section 24.4 for an alternate construction of the Hamming codes using linear algebra over Z2.
|
|
W 4/27
|
36
|
|
|
T 4/26
|
35
|
Example: (Z3[x])x2 + 1, a finite field with 9 elements. The congruence class [x] is a square root of –1, so this field is essentially Z3[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 Zp×, a number of which work for finite fields more generally). Most use Theorem 22.8.2 (a polynomial over field has no more than degree-many 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. Diffie-Hellman secret sharing: first published public-key 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 Zp[x] of degree n, then (Zp[x])π(x) is a finite field of pn elements (Theorem 23.3).
- Stated but not proved in class: Every finite field has pn elements for some prime p and some n ≥ 1 (section 23.2), and every such finite field can be represented as (Zp[x])π(x) for some irreducible π(x) of degree n in Zp[x] (follows from Theorem 23.4). Moreover, up to isomorphism there is a unique field of size pn for each prime power pn (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 (Z2[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 orbit-counting lemma (Theorem 21.4). Six-bead two-color necklace example redux. Proof of Burnside’s lemma. Counting copies of Symm(□) inside S4. Counting edge colorings of a regular tetahedron.
|
|
W 4/6
|
28
|
Burnside’s orbit-counting lemma (Theorem 21.4). Example: how many different 6-bead 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 orbit-stablizer formula (Theorem 21.3). Example: Symmetries of a regular n-gon 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 A4. Subgroup diagram for A4 (Example p.275–276 in section 20.8). The converse of Lagrange’s theorem is false: A4 has no subgroups of order 6 .
|
|
Θ 3/31
|
26
|
|
|
W 3/30
|
25
|
|
|
T 3/29
|
24
|
The groups A3 and A4. Half the permutations of Sn 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 Sn is a product of transpositions. Theorem: the parity of the number of transpositions in any product-of-transpositions 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 S4 and their cycle type; Symm
(43□12), the symmetries of a square with the given labeled vertex locations, as a subgroup of S4 (see also Table 21.1.1).
|
|
T 3/22
|
21
|
Permutation groups. Sn, the symmetric group on n letters. Cycles and k-cycles, disjoint cycles. Cycle notation; multiplying elements in cycle notation. Cycle type. Counting elements of a particular cycle type. Order of a k-cycle, of a product of disjoint cycles. See sections 10.6, 12.5.
Coming up next: S4; 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 n-gon; 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 Z13× and using it to solve a mod-13 equation. If you’d like to read more about discrete logarithms / indices, see section 8.6 of Lozano-Robledo, Number Theory and Geometry, or some lecture notes of Dr. Wyss-Gallifent.
Symm(▵) is generated by r := rot(120°) and f := flip(|); these satisfy relations r3 = f2 = 1 and fr = r2f (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 Zm×.
|
|
Θ 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. Z2 × Z3 is cyclic but Z2 × Z2 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 Zm (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: ak = 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 Zm (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.
|
