Project IV (MATH4072) 2021-22

The Polynomial Method

Dan Evans

Description

Early on in our mathematical lives, we discover the following simple things about single-variable polynomials over a field:

a degree d polynomial has at most d roots,
given a set of d values x₁,...,x_d, there's always a polynomial of degree at most d that vanishes at them all. Indeed, f(t)=(t-x₁)...(t-x_d) works.

In recent years, multi-variable analogues of these basic facts have 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, which is a discrete analogue of an important problem in analysis called The Kakeya Conjecture, was solved by Dvir in 2009 with an astonishingly 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. What is the maximum possible number of joints in a collection of N lines in ℝ³, where a joint is a point at the intersection of three non-coplanar lines. 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 is given by the Szemerédi–Trotter theorem. This already had a number of proofs, but Guth and Katz extended the Polynomial Method to provide a new way of looking at it by partitioning sets of points using Polynomial Ham Sandwiches. Similar ideas led to their resolution of an old and difficult conjecture of Erdős: what is the minimum 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 ℤ/3ℤ. The Cap Set problem asks how big can a line-free set be and in 2016 the Polynomial Method provided the breakthrough yet again.

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 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, it has made inroads into combinatorics relatively recently, for instance under the guise of the Combinatorial Nullstellensatz.

For this project, we will look at some of the varied applications of these powerful polynomial tools.

Prerequisites and Corequisites

Algebra II and Elementary Number Theory II are essential and Codes & Cryptography III would be useful for experience with polynomials over finite fields.

Resources

As well as the various Wikipedia links above, some online references include:

A blogpost by Terry Tao discussing the finite field Kakeya Problem.
A blogpost by Yufei Zhao discussing the Joints Problem.
Another blogpost by Terry Tao discussing the Szemerédi–Trotter Theorem using the Polynomial Ham Sandwich Theorem.
An on-line article by David Austin discussing the Cap Set Problem.
A survey article by Terry Tao on the Polynomial Method.
Another survey article by Zeev Dvir on applications in Incidence Geometry.
The book Polynomial Methods in Combinatorics (library link) by Larry Guth. There is also an interesting survey article and course notes by the same author.
Another recent book, Extremal Combinatorics by S. Jukna (library link) has a chapter on the Polynomial Method.
Chapters 14 and 15 from this number theory course by Pete Clark gives a self-contained introduction to polynomials over finite fields, including the Chevalley-Warning Theorem, the Combinatorial Nullstellensatz, and various combinatorial applications.

email: Dan Evans