# Finite Fields, with Applications to Combinatorics

Share this page
*Kannan Soundararajan*

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.

#### Readership

Undergraduate students interested in finite fields and combinatorics.

#### Table of Contents

# Table of Contents

## Finite Fields, with Applications to Combinatorics

- Cover Cover11
- Title page iii5
- Copyright iv6
- Contents vii9
- Preface xi13
- Chapter 1. Primes and factorization 115
- Chapter 2. Primes in the integers 2741
- Chapter 3. Congruences in rings 4559
- Chapter 4. Primes in polynomial rings: constructing finite fields 6377
- Chapter 5. The additive and multiplicative structures of finite fields 8397
- Chapter 6. Understanding the structure of ℤ/𝕟ℤ 99113
- Chapter 7. Combinatorial applications of finite fields 111125
- 7.1. Sidon sets and perfect difference sets 111125
- 7.2. Proof of Theorem 7.3 116130
- 7.3. The Erdős-Turán bound—Proof of Theorem 7.4 117131
- 7.4. Perfect difference sets—Proof of Theorem 7.8 121135
- 7.5. A little more on finite fields 124138
- 7.6. De Bruijn sequences 126140
- 7.7. A magic trick 129143
- 7.8. Exercises 130144

- Chapter 8. The AKS Primality Test 135149
- 8.1. What is a rapid algorithm? 135149
- 8.2. Primality and factoring 137151
- 8.3. The basic idea behind AKS 141155
- 8.4. The algorithm 143157
- 8.5. Running time analysis 144158
- 8.6. Proof of Lemma 8.8 145159
- 8.7. Generating new relations from old 146160
- 8.8. Proof of Theorem 8.9 147161
- 8.9. Exercises 152166

- Chapter 9. Synopsis of finite fields 155169
- Bibliography 165179
- Index 169183
- Back Cover Back Cover1187