A timeline of the polynomial method up-to combinatorial nullstellensatz

Over the past 30-40 years, the so-called polynomial method has developed into a powerful tool in combinatorics and (additive) number theory. There has been a lot of recent interest in it after Dvir’s  paper on the Kakeya conjecture, where he solved a major open problem by a short and easy polynomial argument. After that, many prominent mathematicians from different areas of mathematics started looking into these techniques, and in some cases, ended up resolving some famous open problems: On the Erdős distinct distances problem in the plane.

In this post I will give a timeline of some important papers (in my opinion) related to the polynomial method, starting from Tom H. Koornwinder’s paper on equiangular lines till the appearance of Combinatorial Nullstellensatz by Noga Alon (1999) (so, this timeline will cover only the part A of polynomial method as mentioned here). But first, here are some quotes that describe the general philosophy behind the polynomial method:

Given a set of points (or vectors, or sets) that satisfy some property, we want to say something about the size or the structure of this set. The approach is then to associate to this set a polynomial, or a collection of polynomials, and use properties of polynomials to obtain information on the size or structure of the set.

– Aart Blokhuis, 1993

Broadly speaking, the strategy is to capture (or at least partition) the arbitrary sets of objects (viewed as points in some configuration space) in the zero set of a polynomial whose degree (or other measure of complexity) is under control; for instance, the degree may be bounded by some function of the number of objects. One then uses tools from algebraic geometry to understand the structure of this zero set, and thence to control the original sets of object.

– Terence Tao, 2013

A note on the absolute bound for systems of lines, by Koornwinder

On Two-Distance Sets in Euclidean Space, by Larmen, Rogers and Seidel
Covering finite fields with cosets of subspaces, by Jamison

The blocking number of an affine space, by Brouwer and Schrijver

A New Upper Bound for The Cardinality of 2-Distance Sets in Euclidean Space, by Blokhuis
Intersection theorems  with geometric consequences, by Frankl and Wilson
Remarks on a theorem of Rédei, by Lovasz and Schrijver

Regular subgraphs of almost regular graphs, by Alon, Friedland and Kalai
Every 4-regular graph plus an edge contains a 3-regular subgraph, by Alon, Friedland and Kalai

– A characterization of exterior lines of certain sets of points in PG (2, q), by Blokhuis and Wilbrink

A nowhere zero point in linear mappings, by Alon and Tarsi
A short proof of the nonuniform Ray-Chaudhuri-Wilson inequality, by Babai
Balancing set of vectors, by Alon, Bergmann, Coppersmith and Odlyzko

Sum zero (mod n), size n subsets of integers, by Bailey and Richter

Multilinear polynomials and Frankl-Ray-Chaudhuri-Wilson type intersection theorems, by Alon, Babai and Suzuki

Polynomial multiplicities over finite fields and intersection sets, by Bruen
Colorings and orientations of graphs, by Alon and Tarsi

The Dinitz problem solved for rectangles, by Janssen
Covering the Cube by Affine Hyperplanes, by Alon and Furedi
Polynomials in finite geometries and combinatorics, by Blokhuis
Zero-sum sets of prescribed size, by Alon and Dubiner

On the size of a blocking set in PG(2,p), by Blokhuis
On nuclei and affine blocking sets, by Blokhuis
– On multiple nuclei and a conjecture of Lunelli and Sce, by Blokhuis

Tools from higher algebra, by Alon
Adding Distinct Congruence Classes Modulo a Prime, by Alon, Nathanson and Ruzsa
A new proof of several inequalities on codes and sets, by Babai, Snevily and Wilson
The number of directions determined by a function f on a finite field, by Blokhuis, Brouwer and Szonyi

The Polynomial Method and Restricted Sums of Congruence Classes, by Alon, Nathanson and Ruzsa
Multiple blocking sets and arcs in finite planes, by Ball

Blocking sets in Desarguesian affine and projective planes, by Szonyi
– Some Applications of Algebraic Curves in Finite Geometry and Combinatorics, by Szonyi

An easier proof of the maximal arcs conjecture, by Ball and Blokhuis
Sumsets in Vector Spaces over Finite Fields, by Eliahou and Kervaire

– Multilinear Polynomials and a Conjecture of Frankl and Füredi, by Sankar and Vishwanathan
Combinatorial Nullstellensatz, by Alon

Beyond this, many excellent surveys on the polynomial method are available in which one can find further developments. For example,


About Anurag Bishnoi

Currently a maths PhD student at Ghent University working in the Incidence Geometry research group. I am broadly interested in combinatorics, finite geometry and group theory.
This entry was posted in Combinatorics, Finite Geometry, Polynomial Method and tagged , , , . Bookmark the permalink.

One Response to A timeline of the polynomial method up-to combinatorial nullstellensatz

  1. Also of relevance:
    – Lückenhafte Polynome über endlichen Körpern (Lacunary polynomials over finite fields), by Redei

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s