Topics in Finite Fields

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

• 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

• Finite field basics
• Fourier analysis
• Character sums with polynomial arguments

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