The polynomial method

Lectures: 3 sessions / week, 1 hour / session

There are no prerequisites for this course.

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 20th 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:

Notes will be made available after each lecture.

There will be four problem sets and an optional project.

Grades will be determined by problem set performance.

Don't show me this again

This is one of over 2,200 courses on OCW. Find materials for this course in the pages linked along the left.

MIT OpenCourseWare is a free & open publication of material from thousands of MIT courses, covering the entire MIT curriculum.

No enrollment or registration. Freely browse and use OCW materials at your own pace. There's no signup, and no start or end dates.

Knowledge is your reward. Use OCW to guide your own life-long learning, or to teach others. We don't offer credit or certification for using OCW.

Made for sharing. Download files for later. Send to friends and colleagues. Modify, remix, and reuse (just remember to cite OCW as the source.)

Learn more at Get Started with MIT OpenCourseWare