Book Review: Polynomial methods in combinatorics

Abstract

Polynomials P (x 1 , x 2 , . . ., x d ) of one or more variables x 1 , . . ., x d and the algebraic varieties {P 1 (x 1 , . . ., x d ) = • • • = P k (x 1 , . . ., x d ) = 0} that they cut out are of course fundamental objects in algebra in general and in algebraic geometry in particular.But it has gradually been realised over time that they are also fundamentally important in other areas of mathematics and theoretical computer science, such as combinatorial incidence geometry, harmonic analysis, differential geometry, and error correcting codes.One particularly striking manifestation of this phenomenon has been the dramatic successes in recent years of the polynomial method in combinatorial geometry, which has been used to solve (or nearly solve) some major open probelms in the subject that did not, on first glance, seem at all related to polynomials.Roughly speaking, combinatorial geometry is the study of configurations of finitely many geometric objects (such as points, lines, planes, or circles) in some standard geometry (e.g., the Euclidean plane R 2 , a higher-dimensional Euclidean space R n , or a vector space k n over a more general field k).One is often interested in extremal questions, in which one tries to maximise or minimise some combinatorial quantity involving these configurations subject to various constraints.There are many questions in this subject; we will just mention two of these, which are also extensively discussed in the book under review.(1) Finite field Kakeya problem.Suppose one is given a subset E of a finitedimensional vector space F d q over a finite field F q of q elements.Suppose also that E is a finite field Kakeya set, which means that it contains a line in every direction (i.e., for every non-zero v ∈ F d q , there exists a line {x + tv : t ∈ k} that is contained in E).For a given choice of k and q, what is the minimum cardinality |E| of E?(2) Erdős distinct distances problem.Suppose one is given a set P of n points in the Euclidean plane R 2 .For a given choice of n, what is the minimum number of distinct distances that are formed between the points in P , that is to say what is the minimum cardinality of the set {|p 1p 2 | : p 1 , p 2 ∈ P, p 1 = p 2 }?

Locations

• Bulletin of the American Mathematical Society - View - PDF
• Bulletin of the American Mathematical Society - View - PDF
• Bulletin of the American Mathematical Society - View - PDF