Unexpected Applications of Polynomials in Combinatorics

In 2007, Zeev Dvir shocked experts by giving a one-page proof of the finite field Kakeya problem. The new idea in the proof was to introduce high degree polynomials into a problem about points and lines. This idea has led to progress on several problems of combinatorial geometry. The most famous of these is the distinct distance problem in the plane. In 1946, Erdos raised the problem how many distinct distances can be determined by n points in the plane, and he observed that a square grid gives roughly n/ (log n)^{1/2} distances. Nets Katz and I recently proved that this bound is sharp up to logarithmic factors. In this talk, we give Dvir's proof and talk about the impact of this new method. We also discuss the philosophical question, why do polynomials play such an important role in these problems?



Massachusetts Institute of Technology