The Polynomial Method

Larry Guth
Office: 2-371

Class times: MWF 2-3, 2-151.

Class Announcements:  There will be no class on Monday Sep. 17 and Wednesday Sep. 26.  To make up for one of these, we will have class on Friday Sep. 21 at the usual time and place (even though it's a student holiday).  There will be no class on Friday September 28, because of the math department retreat.

We will have office hours on Tuesday September 25 at 4 pm, Wednesday October 17 after class.

Problem Set 2 is postponed.  It is now due on Friday October 26 (in class).  We will have office hours on Wednesday (Oct. 24) after class.

We will have office hours on Wed. Nov. 14 and Fri. Nov. 16 after class.

There will be no class on Friday Nov. 30.

Problem Sets:

Problem Set 1, due on Friday September 28.  There will be an envelope on my office door.

Problem Set 2, now due on Friday Oct. 26 in class.  (Problem 6 was updated slightly on October 12.)

Problem Set 3, due on Monday Nov. 19 in class.  (Problem 4b corrected on Nov. 9.)

Problem Set 4
, due on Friday Dec. 7 in class.

Project List
These are some totally optional questions/projects for anyone who's interested in thinking further about the topics of the class.  (Or you can make up your own...)

Notes: In this section, I'll post notes for some of the material in the class. Hopefully, we'll have notes for most/all of the lectures.  Some of the notes are by me, and other notes are contributed by students as noted.  Some students have been taking .tex notes of all the lectures, and their notes
are below.

1. Introduction

Fundamental examples of the polynomial method

2. The Berlekamp-Welch algorithm

3. The finite field Nikodym and Kakeya theorems

4. The joints problem

5. Why polynomials? (part 1)

Background in incidence geometry

6. Introduction to incidence geometry, Notes by Adam Hesterberg

7. Crossing numbers and the Szemeredi-Trotter theorem

8. Crossing numbers and distance problems, Notes by Laszlo Lovasz

9. Crossing numbers and distinct distances

10. Reguli; the Zarankiewicz problem

11. The Elekes-Sharir approach to the distinct distance problem, Notes by Rik Sengupta

Algebraic structure

12. Degree reduction

13. Bezout theorem

14. Special points and lines of algebraic surfaces, Notes by Sean Simmons

15. An application to incidence geometry

16. Taking stock

Cell decompositions

17. Introduction to the cellular method

18. Polynomial cell decompositions

19. Using cell decompositions

20. Incidence bounds in three dimensions, Notes by Adam Hesterberg

21. What's special about polynomials? (a geometric perspective)

Ruled surfaces and projection theory

22. Detection lemmas and projection theory

23. Local to global arguments

24. The regulus detection lemma

The polynomial method in number theory

25. Introduction to Thue's theorem on diophantine approximation

26. Integer polynomials that vanish at rational points, Notes by Yufei Zhao

27. Thue's proof part II: polynomials of two variables

28. Thue's proof part III

Introduction to the Kakeya problem

29. Background on connections between analysis and combinatorics (Loomis-Whitney)

29. Notes by Gaku Liu

29. Notes by Yi Sun

30. Hardy-Littlewood-Sobolev inequality, Notes by Chiheon Kim

31. Oscillating integrals and Besicovitch's arrangement of tubes

32. Besictovitch's construction, Notes by Andrey Grinshpun

33. The Kakeya problem, Notes by Ben Yang
33. The Kakeya problem, notes by Efrat Shaposhnik

34. A version of the joints theorem for long thin tubes

Class Notes by Sam Elder

Class Notes by Adam Hesterberg 

On submitting notes:
During the course, each student who's enrolled will write up notes for one
lecture.  Ideally, the notes will be more or less in the style above.  If it's helpful, here is the latex file for the notes on the BW algorithm: latex file of notes.
  You can email me your notes in a latex file.  Please send me your notes within a week of the lecture, and if you can do it sooner that would be great.

In this section, there are some references to other writing that's relevant to the

Last year, Zeev Dvir taught a class at Princeton with a lot of relevant material.  You can find
his webpage and notes here: Dvir's class on incidence theorems and thair applications

I gave a survey talk about the polynomial method: Survey talk on the polynomial method

Description of the class:

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 first main goal of the course is to study these proofs. 

The polynomial method is also connected to ideas in other areas, including computer science, number theory, and analysis.  A second goal is to study these connections.  We mention a couple here.

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.

The polynomial method is also 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.