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
– 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
– 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,
- Noga Alon, Discrete mathematics: methods and challenges.
- Gyula Károlyi, The polynomial method in additive combinatorics.
- Simeon Ball, Polynomials in Finite Geometries, The polynomial method in Galois Geometries.
- Peter Sziklai, Polynomials in finite geometry, Applications of Polynomials over Finite Fields.
- Terence Tao and Van Vu, Chapter 9 in Additive Combinatorics.
- Zeev Dvir, Incidence Theorems and Their Applications.
- Terence Tao, Algebraic combinatorial geometry: the polynomial method in arithmetic combinatorics, incidence combinatorics, and number theory.