Finite Fields and Algebraic Preliminaries

Corresponds to Lecture topic 5, treated at increasing depth across three sessions (a basic treatment, a more advanced treatment, and a treatment with worked examples), plus the Moebius inversion formula. Reviews groups, rings, and fields as the minimal algebraic vocabulary needed, then develops finite fields $\mathrm{GF}(q)$ in depth: they exist and are unique for every prime power $q = p^n$, their nonzero elements always form a cyclic group under multiplication, and they can be constructed concretely as $\mathbb F_p[x]/(f(x))$ for an irreducible polynomial $f$ — the algebraic machinery every code in the rest of the course (BCH, Reed-Solomon, Reed-Muller) is built over. See number-theory-for-cryptography for a complementary, cryptography- flavored treatment of finite groups and modular arithmetic. The Moebius inversion formula inverts a sum over divisors (here, most usefully, counting the number of irreducible polynomials of each degree over $\mathbb F_q$, which the field constructions above need to guarantee enough irreducibles exist).

Outline (TODO — flesh out each)

• Groups, rings, and fields — basic definitions
• Finite fields — existence and uniqueness
• The multiplicative group of a finite field is cyclic
• Constructing finite fields via irreducible polynomials
• Worked examples
• The Moebius inversion formula; counting irreducible polynomials