AF: Small: Quantitative and Algorithmic Aspects of Semi-algebraic Sets and Partitions

AF：小：半代数集和分区的定量和算法方面

• 批准号: 1618981
• 负责人: Saugata Basu
• 金额: $ 39.96万
• 依托单位: Purdue University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2016
• 资助国家: 美国
• 起止时间: 2016-07-01 至 2020-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1618981&HistoricalAwards=false
• 关键词: AF; Small; Quantitative; Algorithmic; Aspects

"Divide and conquer," a time-honored technique in computer science andmathematics, partitions a problem into smaller pieces to make iteasier to solve. This project deepens the study of partitioning in twodirections, both in the context of semi-algebraic geometry -- which isthe study of geometric and topological properties of sets defined byreal polynomial equalities and inequalities.The first direction is to systematize polynomial partitioning, whichhas recently become a powerful tool capable of tackling manylong-standing open questions in the area of incidence geometry. Incomputational geometry, the space or sets being partitioned are oftencomplex but partitioning is by simple objects: splitting by planes orcutting into trapezoids. Polynomial partitioning allows high degreecutting polynomials, necessitating more precise degree-based upperbounds on the topology of semi-algebraic sets and real varieties thanthe ones known before, and leading to a very fruitful interactionbetween the fields of real algebraic geometry and discrete geometry.The PI will develop new techniques in semi-algebraic geometry to meetthe new demands imposed on the field by the developments in discretegeometry, and develop a new theory of polynomial partitioning that cansystematize their study and lead to new applications as well.The second is to generalize quantitative and algorithmicsemi-algebraic geometry to a much more general and geometric setting-- the category of constructible sheaves. Constructible sheaves comewith an underlying semi-algebraic partition (on whose elements thestalks of the sheaf are locally constant). Kashiwara and Schapiraproved a fundamental theorem on the stability of this category underthe six standard sheaf operations (analogous to Tarski-Seidenbergprinciple for semi-algebraic sets). The PI will study the quantitativeand algorithmic questions related to constructible sheaves. Thecomplexity upper bounds and algorithmic results would have wideapplications.The project will have impact in several areas of mathematics andcomputation -- including quantitative and algorithmic semi-algebraicgeometry, discrete and computational geometry, computationalcomplexity theory and quantitative study of the solutions to linearsystems of partial differential equations. The project will train agraduate student and a postdoctoral researcher in quantitative andalgorithmic real algebraic geometry and its modern applications.

“分而治之”是计算机科学和数学中一项历史悠久的技术，它将问题分成更小的部分，以便更容易解决。该项目在半代数几何的背景下深化了两个方向的划分研究——半代数几何是对由实多项式等式和不等式定义的集合的几何和拓扑性质的研究。第一个方向是系统化多项式划分，它最近已成为一个强大的工具，能够解决入射几何领域许多长期悬而未决的问题。在计算几何中，被划分的空间或集合通常很复杂，但划分是通过简单的对象：按平面分割或切割成梯形。 多项式划分允许高次切割多项式，在半代数集和实簇拓扑上需要比以前已知的更精确的基于次数的上限，并导致实代数几何和离散几何领域之间非常富有成效的相互作用。PI将开发半代数几何新技术，以满足离散几何发展对该领域提出的新要求，并开发多项式划分的新理论可以系统化他们的研究并带来新的应用。第二个是将定量和算法半代数几何推广到更一般和几何的设置——可构造滑轮的类别。 可构造的滑轮带有一个底层的半代数分区（在其元素上，滑轮的茎是局部恒定的）。 Kashiwara 和 Schapira 在六种标准层操作下证明了该范畴的稳定性基本定理（类似于半代数集的 Tarski-Seidenberg 原理）。 PI 将研究与可构造滑轮相关的定量和算法问题。复杂性上限和算法结果将具有广泛的应用。该项目将在数学和计算的多个领域产生影响——包括定量和算法半代数几何、离散和计算几何、计算复杂性理论以及偏微分方程线性系统解的定量研究。 该项目将在定量和算法实代数几何及其现代应用方面培训一名研究生和一名博士后研究员。

项目成果

Zeroes of polynomials on definable hypersurfaces: pathologies exist, but they are rare

可定义超曲面上多项式的零点：病理现象存在，但很少见

• DOI: 10.1093/qmath/haz022
• 发表时间: 2019-10
• 期刊: The Quarterly Journal of Mathematics
• 作者: Basu, Saugata;Lerario, Antonio;Natarajan, Abhiram
• 通讯作者: Natarajan, Abhiram