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
• 期刊: Advances in Mathematics
• 影响因子: 1.7
• 作者: Basu, Saugata;Perrucci, Daniel
• 通讯作者: Perrucci, Daniel

Betti numbers of random hypersurface arrangements

随机超曲面排列的贝蒂数

• DOI: 10.1112/jlms.12658
• 发表时间: 2022
• 期刊: 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
• 期刊: Journal of the European Mathematical Society
• 影响因子: 2.6
• 作者: Basu, Saugata;Patel, Deepam
• 通讯作者: Patel, Deepam

Vandermonde Varieties, Mirrored Spaces, and the Cohomology of Symmetric Semi-algebraic Sets

Vandermonde 簇、镜像空间和对称半代数集的上同调

• DOI: 10.1007/s10208-021-09519-7
• 发表时间: 2021
• 期刊: Foundations of Computational Mathematics
• 影响因子: 3
• 作者: Basu, Saugata;Riener, Cordian
• 通讯作者: Riener, Cordian

CATEGORICAL COMPLEXITY

范畴复杂性

• DOI: 10.1017/fms.2020.26
• 发表时间: 2020
• 期刊: Sigma
• 作者: BASU, SAUGATA;ISIK, UMUT
• 通讯作者: ISIK, UMUT