The
Polynomial Method
Larry Guth
Email: lguth@math.mit.edu
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.
References: In this
section, there are some references to other writing that's relevant to
the
course.
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.