Early on in our mathematical lives, we discover the following basic facts about single-variable polynomials over a field \(F\):
Factor Theorem: a non-trivial polynomial in \(F[x]\) of degree at most \(d\) has at most \(d\) roots.
This follows by factoring \(f(x)=(x-a)g(x)\) and using induction on the degree.
Interpolation Theorem: given \(d\) values in \(F\), there are polynomials in \(F[x]\) of degree at most \(d\) vanishing at these values.
Indeed, one can just take the polynomial \(f(x)=(x-a_1)(x-a_2)\cdots(x-a_d)\in F[x]\).
When considering polynomials with more variables, things are naturally more complicated and more interesting.
For instance, the polynomial \(f(x,y)=xy\) in \(F[x,y]\) has total degree \(2\) but vanishes at more than \(2\) points \((a,b)\in F^2\).
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 the vector space \(\mathbb{F}_q^n\) over a finite field \(\mathbb{F}_q\) 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, have further applications in 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 method 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 the vector space \(\mathbb{F}_3^4\) over the finite field \(\mathbb{F}_3=\mathbb{Z}/3\) with \(3\) elements. A cap set is a line-free subset in the \(n\)-dimensional space \(\mathbb{F}_3^n\), and in 2007 Terry Tao wrote that perhaps his favourite open problem was to determine the maximal size of a cap set. In 2016 the Polynomial Method provided the breakthrough once again, showing that a cap set is exponentially smaller than the cardinality \(3^n\) of the vector space.
This is just a small selection of highlights, and there are many other applications, for instance to graph theory, group theory, sumsets and coding theory.
The idea of using polynomials to understand the size of a discrete set is actually quite old, going back to Hilbert and beyond. For example, 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. an ellipse is given by a degree \(2\) equation, and two distinct ellipses can intersect in at most \(2\times 2=4\) points). Or in number theory, auxiliary polynomials have 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.
The project will involve learning through reading, with a focus on underlying theory, mathematical rigour, and development of conceptual understanding. Students will demonstrate understanding of the method by exploring results and examples, solving relevant problems, and clearly communicating in both written and oral formats.
Algebra
II is essential for good understanding of polynomials over fields.
It would also be highly useful if you studied at least one of Elementary Number Theory II, Cryptography+Codes III or Galois Theory III for further 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