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.
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