Incidence Theorems: Beyond the Polynomial Method

这个项目的目标是研究由线、点、圆和其他几何物体组成的几何排列的基本性质，这些几何排列中有大量的“偶然性”。在这里，发生率是一个小的子配置，其中发生了一些巧合（例如，许多点位于一条直线上，或者许多线经过一个点）。包含许多事件的结构在许多设置中都很重要，例如编码理论、数据存储、计算复杂性和纯数学。几年前，PI在工作中加速了对这些结构的研究，他将“多项式方法”引入了这一领域。这种方法的工作原理是将给定的结构建模为代数方程的一组解。这允许人们使用代数几何中的工具来分析潜在的关联结构。尽管它取得了成功，但仍有几个重要的问题在很大程度上无法用多项式方法解决。这个项目的目的是在多项式方法（部分或完全）失败的问题上取得进展，通过增加或修改方法，或者在某些情况下，将其全部替换。本项目为研究生提供研究训练机会。本文的主要研究目标包括：(1)扩展多项式方法来解决高维平面的偶然性，并利用这些边界给出具有伪随机性质的图的新的显式结构；(2)将多项式方法扩展到零因子环上定义的问题，其中原始方法完全失败；(3)理解等差数列的Kakeya问题——著名的欧几里得Kakeya猜想的一种方法；(4)通过开发多项式方法的鲁棒类似物来研究实数上的“近似”（或噪声）关联问题。在这些领域中，该项目侧重于几个具体的挑战和开放的问题，每个问题都需要超越多项式方法的新技术。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.