Incidence Theorems: Beyond the Polynomial Method

Princeton University, Princeton NJ

Investigators

Abstract

The goal of this project is to study basic properties of geometric arrangements, composed of lines, points, circles, and other geometric objects in which there is an abundance of ''incidences''. Here, an incidence is a small sub-configuration in which some coincidence occurs (for example, many points lying on a single line or many lines passing through a single point). Structures that include many incidences are important in many settings such as coding theory, data storage, computational complexity, and pure mathematics. The study of these structures was accelerated several years ago in work by the PI, who introduced the ''Polynomial Method'' to this area. This method works by modeling a given configuration as a set of solutions to an algebraic equation. This allows one to use tools from algebraic geometry to analyze the underlying incidence structure. Despite its success, several important problems remained largely impervious to the polynomial method. This project is aimed at making progress on problems in which the polynomial method fails (partially or completely) by augmenting or modifying the method or, in some cases, replacing it all together. The project provides research training opportunities for graduate students. The main research objectives of the proposal include (1) extensions of the polynomial method to tackle incidences of high-dimensional flats and the use of these bounds to give new explicit constructions of graphs with pseudo-random properties, (2) extending the polynomial method to problems defined over rings with zero divisors, where the original method fails completely, (3) understanding the Kakeya problem for arithmetic progressions - one of the approaches to the famous Euclidean Kakeya conjecture, and (4) studying ''approximate'' (or noisy) incidence problems over the real numbers by developing robust analogs of the polynomial method. Within these areas, the project focuses on several concrete challenges and open problems, each requiring new techniques that go beyond the polynomial method. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.