AF: Small: Symmetry, Randomness and Computations in Real Algebraic Geometry

AF：小：实代数几何中的对称性、随机性和计算

• 批准号: 1910441
• 负责人: Saugata Basu
• 金额: $ 40万
• 依托单位: Purdue University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2019
• 资助国家: 美国
• 起止时间: 2019-10-01 至 2024-09-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1910441&HistoricalAwards=false
• 关键词: AF; Small; Symmetry; Randomness; Computations

Sets defined in terms of real polynomial inequalities, called semi-algebraic sets, are ubiquitous in science and engineering. Consequently, it is very important to have efficient algorithms for computing properties of semi-algebraic sets. One drawback of semi-algebraic geometry is the very high algorithmic complexity for such algorithms. Semi-algebraic sets tend to get topologically very complicated as the number and the degrees of the polynomials defining them, as well as the dimension of the ambient space, increases. Thus it is very important to identify situations, especially from the point of view of practical applications, where this increase in topological as well as algorithmic complexity can be controlled in a better way. The project will address several key questions in algorithmic and quantitative semi-algebraic geometry concentrating on the phenomenon of reduction in complexity induced by symmetry, as well as by randomness, in various situations. The project will have impact on several areas of mathematics and computer science and will train two graduate students in quantitative and algorithmic real algebraic geometry and its modern applications.A part of the project will deal with quantitative and algorithmic questions related to semi-algebraic sets equipped with a group action. Since the action of the group descends to the cohomology of such sets, the cohomology spaces get an extra structure of being finite-dimensional modules over the group. This gives the advantage that one can study the cohomology of such sets and compute their dimensions using the structure of this module. The investigator plans to exploit this basic idea to develop algorithms with exponentially better complexity than the best algorithms for the same problems for general semi-algebraic sets. Since semi-algebraic sets equipped with group actions occur frequently in practice, these algorithms will have many practical applications. The second part of the project will deal with random algebraic geometry, which is a relatively new and rapidly developing topic. Since, unlike complex discriminants, real discriminants disconnect spaces of parameters, there is no unique generic situation in real algebraic geometry. Thus, study of real algebraic geometry often involves difficult classification problems that soon become intractable, e.g. Hilbert's sixteenth problem. An attractive alternative that also has practical applications is to choose an appropriate measure and study expected statistics (such as Betti numbers) of real varieties, rather than consider all possibilities. The investigator will explore several problems through the probabilistic lens afforded by a widely studied Kostlan measure, with the goal of proving that the typical behavior of semi-algebraic sets defined by randomly chosen polynomials is often much better than the worst-case deterministic behavior, and translate this reduction of complexity into corresponding algorithmic results.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.

根据实多项式不等式定义的集合，称为半代数集合，在科学和工程中普遍存在。 因此，拥有计算半代数集性质的有效算法非常重要。 半代数几何的一个缺点是此类算法的算法复杂性非常高。随着定义半代数集的多项式的数量和次数以及周围空间的维数增加，半代数集在拓扑上往往会变得非常复杂。因此，识别情况非常重要，特别是从实际应用的角度来看，可以以更好的方式控制拓扑和算法复杂性的增加。 该项目将解决算法和定量半代数几何中的几个关键问题，重点关注各种情况下由对称性和随机性引起的复杂性降低的现象。 该项目将对数学和计算机科学的多个领域产生影响，并将在定量和算法实代数几何及其现代应用方面培养两名研究生。该项目的一部分将处理与配备的半代数集相关的定量和算法问题通过集体行动。 由于群的作用下降到此类集合的上同调，因此上同调空间获得了作为群上的有限维模的额外结构。这样做的优点是可以研究此类集合的上同调并使用该模块的结构计算它们的维数。 研究人员计划利用这一基本思想来开发算法，其复杂度比针对一般半代数集的相同问题的最佳算法要好得多。由于具有群作用的半代数集在实践中经常出现，因此这些算法将具有许多实际应用。 该项目的第二部分将涉及随机代数几何，这是一个相对较新且发展迅速的主题。由于与复判别式不同，实判别式断开参数空间，因此实代数几何中不存在唯一的通用情况。 因此，实代数几何的研究经常涉及困难的分类问题，这些问题很快就会变得棘手，例如希尔伯特第十六个问题。 一个有吸引力且具有实际应用价值的替代方案是选择适当的度量并研究真实品种的预期统计数据（例如贝蒂数），而不是考虑所有可能性。研究人员将通过广泛研究的 Kostlan 测度提供的概率透镜来探索几个问题，目的是证明由随机选择的多项式定义的半代数集的典型行为通常比最坏情况的确定性行为要好得多，并且将这种复杂性的降低转化为相应的算法结果。该奖项反映了 NSF 的法定使命，并且通过使用基金会的智力优点和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

Topology of real multi-affine hypersurfaces and a homological stability property

真实多重仿射超曲面的拓扑及其同调稳定性

• DOI: 10.1016/j.aim.2023.108982
• 发表时间: 2023-05
• 期刊: Advances in Mathematics
• 影响因子: 1.7
• 作者: Basu, Saugata;Perrucci, Daniel
• 通讯作者: Perrucci, Daniel

Betti numbers of random hypersurface arrangements

随机超曲面排列的贝蒂数

• DOI: 10.1112/jlms.12658
• 发表时间: 2022-07
• 期刊: Journal of the London Mathematical Society
• 作者: Basu, Saugata;Lerario, Antonio;Natarajan, Abhiram
• 通讯作者: Natarajan, Abhiram

VC density of definable families over valued fields

有价值领域中可定义家族的 VC 密度

• DOI: 10.4171/jems/1056
• 发表时间: 2021-01
• 期刊: Journal of the European Mathematical Society
• 影响因子: 2.6
• 作者: Basu, Saugata;Patel, Deepam
• 通讯作者: Patel, Deepam

Efficient simplicial replacement of semialgebraic sets

半代数集的高效单纯替换

• DOI: 10.1017/fms.2023.36
• 发表时间: 2023-01
• 期刊: Sigma
• 作者: Basu, Saugata;Karisani, Negin
• 通讯作者: Karisani, Negin

Persistent Homology of Semialgebraic Sets

半代数集的持久同调

• DOI: 10.1137/22m1494415
• 发表时间: 2023-09
• 期刊: SIAM Journal on Applied Algebra and Geometry
• 影响因子: 1.2
• 作者: Basu, Saugata;Karisani, Negin
• 通讯作者: Karisani, Negin