Finite Fields, with Applications to Combinatorics

✍ Scribed by Kannan Soundararajan

• Publisher: American Mathematical Society
• Year: 2022
• Tongue: English
• Leaves: 187
• Series: Student Mathematical Library, 99
• Category: Library

✦ Synopsis

This book uses finite field theory as a hook to introduce the reader to a range of ideas from algebra and number theory. It constructs all finite fields from scratch and shows that they are unique up to isomorphism. As a payoff, several combinatorial applications of finite fields are given: Sidon sets and perfect difference sets, de Bruijn sequences and a magic trick of Persi Diaconis, and the polynomial time algorithm for primality testing due to Agrawal, Kayal and Saxena. The book forms the basis for a one term intensive course with students meeting weekly for multiple lectures and a discussion session. Readers can expect to develop familiarity with ideas in algebra (groups, rings and fields), and elementary number theory, which would help with later classes where these are developed in greater detail. And they will enjoy seeing the AKS primality test application tying together the many disparate topics from the book. The pre-requisites for reading this book are minimal: familiarity with proof writing, some linear algebra, and one variable calculus is assumed. This book is aimed at incoming undergraduate students with a strong interest in mathematics or computer science.

✦ Table of Contents

Cover
Title page
Copyright
Contents
Preface
Chapter 1. Primes and factorization
1.1. Groups
1.2. Rings
1.3. Integral domains and fields
1.4. Divisibility: primes and irreducibles
1.5. Ideals and Principal Ideal Domains (PIDs)
1.6. Greatest common divisors
1.7. Unique factorization
1.8. Euclidean domains
1.9. Exercises
Chapter 2. Primes in the integers
2.1. The infinitude of primes
2.2. Bertrand’s postulate
2.3. How many primes are there?
2.4. Exercises
Chapter 3. Congruences in rings
3.1. Congruences and quotient rings
3.2. The ring ℤ/𝕟ℤ
3.3. Prime ideals and maximal ideals
3.4. Primes in the Gaussian integers
3.5. Exercises
Chapter 4. Primes in polynomial rings: constructing finite fields
4.1. Primes in the polynomial ring over a field
4.2. An analogue of the proof of Bertrand’s postulate
4.3. An analogue of Euler’s proof
4.4. Möbius inversion and a formula for 𝜋(𝑛;𝔽_{𝕢})
4.5. Exercises
Chapter 5. The additive and multiplicative structures of finite fields
5.1. More about groups: cyclic groups
5.2. More about groups: Lagrange’s theorem
5.3. The additive structure of finite fields
5.4. The multiplicative structure of finite fields
5.5. Exercises
Chapter 6. Understanding the structure of ℤ/𝕟ℤ
6.1. The Chinese Remainder Theorem
6.2. The structure of the multiplicative group (ℤ/𝕟ℤ)^{×}
6.3. Existence of primitive roots 𝑚𝑜𝑑 𝑝^{𝑒}: Proof of Theorem 6.10
6.4. Exercises
Chapter 7. Combinatorial applications of finite fields
7.1. Sidon sets and perfect difference sets
7.2. Proof of Theorem 7.3
7.3. The Erdős-Turán bound—Proof of Theorem 7.4
7.4. Perfect difference sets—Proof of Theorem 7.8
7.5. A little more on finite fields
7.6. De Bruijn sequences
7.7. A magic trick
7.8. Exercises
Chapter 8. The AKS Primality Test
8.1. What is a rapid algorithm?
8.2. Primality and factoring
8.3. The basic idea behind AKS
8.4. The algorithm
8.5. Running time analysis
8.6. Proof of Lemma 8.8
8.7. Generating new relations from old
8.8. Proof of Theorem 8.9
8.9. Exercises
Chapter 9. Synopsis of finite fields
9.1. Exercises
Bibliography
Index
Back Cover