Polynomial Methods in Discrete Geometry

California Institute Of Technology, Pasadena CA

Investigators

Abstract

Starting around 2009, a series of difficult longstanding combinatorial problems have been solved by using algebraic techniques. This led to a new subfield that is sometimes called "the Polynomial Method". The philosophy behind this subfield is that collections of objects that exhibit an extremal behavior often have hidden algebraic structure. As a simple example, if a finite set of points in the plane contains many pairs that are at a distance of 1 from each other, one might expect this set to have a grid structure. Once the algebraic structure is found, it can be exploited to gain a better understanding of the original problem. To expose the algebraic structure, one defines polynomials on the studied objects and explores their properties by using algebraic tools, often from Algebraic Geometry. For example, for a problem involving a finite set of points in the plane, one might wish to study the properties of a minimum-degree polynomial that vanishes on the point set. Beyond solving various longstanding problems, this new subfield is also leading to the discovery of interesting connections between Combinatorial Geometry and other fields, such as Harmonic Analysis and Theoretical Computer Science. This project is based on the assumption that the new "algebraic era" in Combinatorial Geometry has not yet reached its peak. It investigates further problems that seem approachable via algebraic techniques, and aims to further develop the current algebraic tools. The first part of this project involves studying several main open problems in Discrete Geometry by using algebraic methods. Specifically, studying the distinct distances problem in R^d, the characterization of point sets that determine few distinct distances, and the problem of deriving stronger and more general bounds for incidence problems. Part of the importance of deriving stronger incidence bounds is that many problems can be reduced to incidence problems (including problems from Combinatorics, Harmonic Analysis, and Number Theory). The second part of the project concerns connections between Discrete Geometry and Additive Combinatorics, also by using polynomial methods. This partly involves further studying known connections between the two fields, but focuses mainly on establishing a new type of connection. This connection consists of defining geometric variants of additive energy and extending some of the known additive energy results to these variants (such as the Balog-Szemeredi-Gowers theorem and higher moment energies).