Finite Fields, with Applications to Combinatorics

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. Cover 1 Title page 5 Copyright 6 Contents 9 Preface 13 Chapter 1. Primes and factorization 15 1.1. Groups 15 1.2. Rings 18 1.3. Integral domains and fields 20 1.4. Divisibility: primes and irreducibles 23 1.5. Ideals and Principal Ideal Domains (PIDs) 26 1.6. Greatest common divisors 27 1.7. Unique factorization 29 1.8. Euclidean domains 31 1.9. Exercises 35 Chapter 2. Primes in the integers 41 2.1. The infinitude of primes 41 2.2. Bertrand’s postulate 46 2.3. How many primes are there? 52 2.4. Exercises 55 Chapter 3. Congruences in rings 59 3.1. Congruences and quotient rings 59 3.2. The ring Z/nZ 63 3.3. Prime ideals and maximal ideals 65 3.4. Primes in the Gaussian integers 69 3.5. Exercises 72 Chapter 4. Primes in polynomial rings: constructing finite fields 77 4.1. Primes in the polynomial ring over a field 77 4.2. An analogue of the proof of Bertrand’s postulate 82 4.3. An analogue of Euler’s proof 85 4.4. Möbius inversion and a formula for π(n;F_{q}) 88 4.5. Exercises 93 Chapter 5. The additive and multiplicative structures of finite fields 97 5.1. More about groups: cyclic groups 97 5.2. More about groups: Lagrange’s theorem 101 5.3. The additive structure of finite fields 104 5.4. The multiplicative structure of finite fields 109 5.5. Exercises 111 Chapter 6. Understanding the structure of Z/nZ 113 6.1. The Chinese Remainder Theorem 113 6.2. The structure of the multiplicative group (Z/nZ)^{×} 117 6.3. Existence of primitive roots mod p^{e}: Proof of Theorem 6.10 119 6.4. Exercises 122 Chapter 7. Combinatorial applications of finite fields 125 7.1. Sidon sets and perfect difference sets 125 7.2. Proof of Theorem 7.3 130 7.3. The Erdős-Turán bound—Proof of Theorem 7.4 131 7.4. Perfect difference sets—Proof of Theorem 7.8 135 7.5. A little more on finite fields 138 7.6. De Bruijn sequences 140 7.7. A magic trick 143 7.8. Exercises 144 Chapter 8. The AKS Primality Test 149 8.1. What is a rapid algorithm? 149 8.2. Primality and factoring 151 8.3. The basic idea behind AKS 155 8.4. The algorithm 157 8.5. Running time analysis 158 8.6. Proof of Lemma 8.8 159 8.7. Generating new relations from old 160 8.8. Proof of Theorem 8.9 161 8.9. Exercises 166 Chapter 9. Synopsis of finite fields 169 9.1. Exercises 175 Bibliography 179 Index 183 Back Cover 187 "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."--Page 4 of cover Uses finite field theory as a hook to introduce the reader to a range of ideas from algebra and number theory. The book constructs all finite fields from scratch and shows that they are unique up to isomorphism.