Incidence Theorems: Beyond the Polynomial Method

这个项目的目标是研究几何排列的基本性质，这些几何排列由直线、点、圆和其他几何对象组成，在这些几何对象中有大量的“偶发事件”。在这里，入射是发生某种重合的一个小的子配置(例如，多个点位于一条线上或多条线穿过一个点)。包含许多关联的结构在许多环境中都很重要，例如编码理论、数据存储、计算复杂性和纯数学。几年前，PI在工作中加速了对这些结构的研究，他们将“多项式方法”引入了这一领域。这种方法的工作原理是将给定的配置建模为代数方程的一组解。这使得人们可以使用代数几何中的工具来分析潜在的关联结构。尽管它取得了成功，但几个重要的问题在很大程度上仍然不受多项式方法的影响。这个项目的目的是通过增加或修改多项式方法，或在某些情况下将其全部替换，从而在多项式方法(部分或完全)失败的问题上取得进展。该项目为研究生提供了研究培训的机会。建议的主要研究目标包括：(1)扩展多项式方法以处理高维平坦的关联问题，并利用这些界给出具有伪随机性质的图的新的显式构造；(2)将多项式方法扩展到定义在具有零因数的环上的问题，其中原始方法完全失败；(3)理解算术级数的Kakeya问题--著名的欧几里德Kakeya猜想的方法之一；以及(4)通过开发多项式方法的稳健类比来研究实数上的“近似”(或噪声)关联问题。在这些领域内，该项目专注于几个具体的挑战和公开的问题，每个问题都需要超越多项式方法的新技术。这个奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

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.