Syllabus | The Polynomial Method | Mathematics

Course Meeting Times

Lectures: 3 sessions / week, 1 hour / session

Prerequisites

There are no prerequisites for this course.

Course Description

This course has five major goals. The first is to study the strikingly short applications of the polynomial method. I’ll emphasize three examples: the Berlekamp-Welch algorithm, the finite field Nikodym and Kakeya problems, and the joints problem. The next goal is to learn the context of these results. In particular, we will learn about incidence geometry: combinatorial estimates about how lines and other basic geometric objects intersect each other. The third goal of the course is to prove the estimate about the distinct distance problem. The fourth goal is to explore connections between the polynomial method and different parts of mathematics. The fifth goal is to mull over some philosophical questions related to the polynomial method. For example, what is special about polynomials? Why are polynomials involved in these problems?

In the last five years, several open problems from combinatorics have been solved by a new approach using polynomials. Some of the proofs are very short, but they are somewhat unexpected because the problems don't involve polynomials. Main examples include the finite field Kakeya problem, the joints problem, and the distinct distance problem in the plane.

The polynomial method is also connected to ideas in other areas, including computer science, number theory, and analysis. The polynomial method was based on ideas from computer science. For example, suppose we have a fairly low degree polynomial over a finite field. Suppose we write a table of the values of the polynomial, and then the table gets corrupted, so that one third of the entries are replaced by errors. From this corrupted table, is it possible to recover the original polynomial? Can it be done efficiently? In the 80's and 90's, computer scientists found interesting answers to this type of question. Their approach to polynomials was adapted to attack the combinatorial problems above.

Additionally, the polynomial method is similar to work on Diophantine equations from the early 20^th century by Thue and others. This work was important because it gave much more general results than previous methods. Previous methods were usually tailored to one particular Diophantine equation. Thue was able to prove that if P(x,y) is an irreducible homogenous polynomial of degree at least 3, and n is any integer, then the equation P(x,y) = n has only finitely many integer solutions.

Topics will include: