# Topics in Finite Fields

## MAT 1304

## CSC 2429, Section 2

## Course Info

Instructor: Swastik Kopparty (swastik.kopparty@utoronto.ca)

Class Time and Place: Mondays 12 noon -3 pm, University College Room 87

Office Hours: TBD

Prerequisites: undergraduate level abstract algebra, combinatorics, probability, graduate level mathematical maturity

References: Lidl & Niederrieter (Finite Fields), Schmidt (Equations over Finite Fields), Tao & Vu (Additive Combinatorics)

## Syllabus

This course will cover some important classical and modern themes in the study of finite fields. These will include:
- Solutions of equations
- Pseudorandomness
- Exponential sums and Fourier techniques
- Algebraic curves over finite fields, the Weil theorems
- Additive combinatorics and the sum-product phenomenon
- Algorithms for computing with finite fields
- Extremal and pseudorandom combinatorial constructions using finite fields
- Applications to Theoretical Computer Science, Combinatorics, and Number Theory

There will be 2-3 problem sets.

## Homework

- HW 1 due Monday, October 16

## Notes

## Lecture Schedule

- September 11: finite field basics: existence, uniqueness, construction, etc.
- September 18: finite field basics continued, introduction to the Fourier transform
- September 25: the Fourier transform, Gauss sums
- October 2: Applications of Gauss sums, the Waring problem over finite fields
- October 9: NO CLASS (Thanksgiving)
- October 16: Character sum bounds with polynomial argments (the Mordell bound), Kloosterman sums, Berlekamp's algorithm for square roots
- October 23: Algorithms for factoring univariate polynomials, Agrawal-Biswas randomized primality test
- October 30: Agrawal-Kayal-Saxena deterministic primality test, Sidon sets, subexponential time discrete log algorithm via smooth numbers
- November 6: NO CLASS (Fall reading week)
- November 13: Sum-free sets, the Cauchy-Davenport theorem, the Combinatorial Nullstellensatz. 3AP free sets, Behrend's construction, Fourier analytic proof of Roth's theorem in F_3^n
- November 20: Multivariate polynomials representing functions, bounds on their number of zeroes, Schwartz-Zippel lemma(s), bounds on 3AP free sets via polynomials (Croot-Lev-Pach-Ellenberg-Gijswijit)
- November 27: the Chevalley Warning theorem, norm polynomials, FFTs, fast polynomial multiplication over all finite fields via FFTs, fast integer multiplication
- December 4: The sum product theorem
- Thursday, December 7: MAKEUP CLASS (SF 3208, 12 Noon) The Weil bounds and applications: Paley graphs, nearly-orthogonal vectors in R^n