Early on in our mathematical lives, we discover the following basic facts about single-variable polynomials over a field:
a degree \(d\) polynomial \(f(x)\) can vanish at no more than \(d\) values \(a_1,a_2,...,a_d\),
given \(d\) values \(a_1,a_2,...,a_d\), there are polynomials of degree at most \(d\) which vanish at all these values. Indeed, one can just take the polynomial \(f(x)=(x-a_1)(x-a_2)...(x-a_d)\).
If we consider multi-variable polynomials, things are naturally more complicated. For instance, finite degree polynomials such as \(f(x,y)=xy\) can vanish infinitely often if the field is infinite. However, one can still formulate multi-variable analogues of the above basic facts which informally say:
the vanishing set of a low degree polynomial tends to be “not very complicated”, e.g. \(f(x,y)=xy\) vanishes only on the \(x\) and \(y\) axes,
given a “not very complicated” set of points, one can find a low degree polynomial vanishing at those points, e.g. if the points are all on the \(x\) and \(y\) axes then \(f(x,y)=xy\) vanishes at all of them.
The interplay between precise forms of these principles has led to some surprisingly simple proofs of previously unknown or difficult results in combinatorics, geometry and number theory. The Polynomial Method involves a collection of ideas which consider how polynomials vanish on a given set of points in a vector space in order to obtain combinatorial information about the set. Some recent successes of the method, each concerning arrangements of lines in various spaces are:
The Finite Field Kakeya Problem. How large must a subset of a vector space over a finite field be if it contains a line in every direction? This question is a discrete analogue of an important problem in analysis called the Kakeya Conjecture, and was solved by Dvir in 2009 with an unexpectedly short proof. The methods, involving counting polynomials over finite fields, are also applicable to coding theory and constructing randomness extractors in cryptography.
The Joints Problem. Given a set of lines in \(\mathbb{R}^3\), a joint is a point at the intersection of three non-coplanar lines in the set. What is the maximum possible number of joints in a set of \(N\) lines in \(\mathbb{R}^3\)? This problem, originally motivated by hidden-surface removal algorithms in 3D computer graphics, was solved in 2010 by Guth and Katz using the Polynomial Method. Again mathematicians were surprised at how short the proof was.
Point-line incidence Problems. Given a set of points and lines, an incidence is a point-line pair such that the point lies on the line. An upper bound for the number of incidences between \(n\) points and \(m\) lines in the Euclidean plane \(\mathbb{R}^2\) is given by the Szemerédi–Trotter theorem. This already had a number of proofs, but Guth and Katz found a new proof by providing a powerful way of partitioning sets of points via Polynomial Ham Sandwiches. Similar ideas led to their (almost) resolution of an old and difficult conjecture of Erdős: what is the minimum possible number of distinct distances between \(N\) points in the plane?
The Cap Set Problem. The card game Set boils down to finding lines in a subset of a vector space over the finite field \(\mathbb{Z}/3\). The Cap Set problem asks how big can a line-free set be in this space, and in 2016 the Polynomial Method provided the breakthrough once again.
This is just a small selection of highlights, and there are many other applications of the method. The idea of using polynomials to understand the size of a discrete set is actually quite old, going back to Hilbert and beyond. For instance, you may have heard of a classical result Bezout’s Theorem which tells us how often two algebraic curves can intersect in terms of their degrees (e.g. two distinct ellipses can intersect in at most \(4\) points). Or in number theory, the use of auxiliary polynomials has proved very useful for the study of Diophantine Approximation and Diophantine Equations, such as in Thue’s Theorem which says that certain two-variable polynomial equations have only finitely many integer solutions. However, the idea has made inroads into combinatorics relatively recently, for instance under the guise of the Combinatorial Nullstellensatz which is a discrete version of the famous Hilbert’s Nullstellensatz from algebraic geometry.
For this project, we will look at some of the varied applications of these powerful polynomial tools.
Algebra II and Elementary Number Theory II are essential. It would also be very useful if you studied either Cryptography+Codes III or Galois Theory III for suitable experience with polynomials over finite fields.
As well as the various Wikipedia links given, some blogposts discussing the four applications above:
A blogpost by Terry Tao about the finite field Kakeya Problem.
A blogpost by Yufei Zhao about the Joints Problem.
A blogpost by Terry Tao about the Szemerédi–Trotter Theorem using the Polynomial Ham Sandwich Theorem.
An AMS Feature Column by David Austin about the Cap Set Problem.
The Polynomial Method has made its way into a few recent textbooks:
Polynomial Methods in Combinatorics (library link ) by Larry Guth.
Polynomial Methods and Incidence Theory (library link) by Adam Sheffer.
Extremal Combinatorics ( library link ) by Stasys Jukna has a chapter on combinatorial applications of the Polynomial Method.
There are also various survey articles and lecture course notes:
A survey article by Terry Tao on the Polynomial Method.
A survey article by Zeev Dvir on applications in Incidence Geometry.
A survey article by Larry Guth and course notes by the same author.
Combinatorial Nullstellensatz by Noga Alon. This is the original paper stating this important result and is itself a very nice survey of some applications in combinatorics, number theory and graph theory.
A number theory course by Pete Clark gives a self-contained introduction to polynomials over finite fields in chapters 14 and 15, including the Chevalley-Warning Theorem, the Combinatorial Nullstellensatz, and various combinatorial applications.
If you have any questions, feel free to drop me a message at daniel.evans@durham.ac.uk