Probabilistic and Topological methods in Real Algebraic Geometry and Computational Complexity

实代数几何和计算复杂性中的概率和拓扑方法

• 批准号: EP/V003542/1
• 负责人: Abhiram Natarajan
• 金额: $ 38.22万
• 依托单位: University of Warwick
• 依托单位国家: 英国
• 项目类别: Fellowship
• 财政年份: 2021
• 资助国家: 英国
• 起止时间: 2021 至 无数据
• 项目状态: 未结题
• 来源: https://gtr.ukri.org/projects?ref=EP%2FV003542%2F1
• 关键词: Probabilistic; Topological; methods; Real; Algebraic

Algebraic geometry is concerned with the study of the zeros of polynomials (called varieties). Besides being prominent in pure mathematics, it has applications in a plethora of areas such as physics, computational geometry, and machine learning. This proposal aims to study topological properties of certain kinds of varieties, with a view toward applications in incidence combinatorics and computational complexity theory.Our first direction is the topological study of random polynomials. Studying random polynomials represents a shift in algebraic geometry - instead of worst-case analysis, which, for example, asks for the largest possible number of points in an intersection of curves, randomness gives an average-case understanding, thus providing a more realistic view. Via Erdos' astonishing 'probabilistic method', one can obtain deterministic results by introducing randomness into a question that apriori had nothing to do with randomness. We focus on a probability distribution on the space of homogeneous polynomials, which is an actively studied probability distribution with strong algebro-geometric significance.Specifically, we are interested in bounds on the topological complexity, as measured by Betti numbers, of random varieties restricted to sets in o-minimal geometry. O-minimal geometry is a framework in which sets (called definable sets) more general than varieties are allowed. The field of o-minimal incidence geometry, which involves combinatorial questions about definable sets, is badly in need of a polynomial partitioning theorem - a tool which has been a panacea in traditional incidence geometry. However, it has proved difficult because the worst-case topological complexity of definable sets restricted to varieties can be "bad".We propose to study the average-case complexity of definable sets restricted to random varieties instead. By doing so, we hope to demonstrate that topologically "bad" polynomials are unusual (we have already proved this for certain definable sets). Thus, if the measure of polynomials suitable for partitioning is large enough, we will have proved the existence of a partitioning polynomial, with "good" topological complexity, via the probabilistic method. This will provide a tremendous boost to o-minimal incidence geometry.Our second direction is algebro-topological questions with applications in computational complexity theory. Computational complexity theory is a mathematical area that classifies problems according to the resources required to solve them. The most important open question in the field is the exceedingly difficult P vs NP problem. There has been a recent impetus towards the problem, under the Geometric Complexity Theory (GCT) program, which involves casting related problems in algebraic language. The hope is that advanced tools in the fertile areas of algebraic geometry and representation theory will allow us to make progress on the problem.The central objective of the GCT program is to separate certain spaces called orbit closures. While that is obviously a lofty aim, our goal is to compute the topology of these orbit closures. Computing the topology helps in obtaining a coarse understanding of the geometry of the objects involved. Also, it is well known that obtaining quantitative bounds on the topology of a space helps in understanding the fundamental limitations of computational procedures that operate on the space.We shall also study the notion of Ulrich complexity, which quantifies the 'complexity' of polynomials in a different way. While it is conveniently defined using commutative-algebraic notions, and is evidently easier to work with, little is understood about it in general. We shall investigate the average Ulrich complexity of Kostlan polynomials. It is known that obtaining lower bounds on the Ulrich complexity of polynomials could potentially have implications on an important conjecture in commutative algebra, as well as the P vs NP problem.

代数几何涉及多项式零点（称为簇）的研究。除了在纯数学中表现突出之外，它还在物理学、计算几何和机器学习等众多领域中有着广泛的应用。本提案旨在研究某些簇的拓扑性质，以期在关联组合学和计算复杂性理论中得到应用。我们的第一个方向是随机多项式的拓扑研究。研究随机多项式代表了代数几何的转变 - 与最坏情况分析不同，例如，最坏情况分析要求曲线交集中尽可能多的点，随机性给出了平均情况的理解，从而提供了更现实的视图。通过埃尔多斯令人惊叹的“概率方法”，人们可以通过将随机性引入到先验与随机性无关的问题中来获得确定性结果。我们关注齐次多项式空间上的概率分布，这是一种积极研究的概率分布，具有很强的代数几何意义。具体来说，我们感兴趣的是随机簇的拓扑复杂性的界限（通过贝蒂数测量）设置为 o-最小几何。 O-最小几何是一个框架，其中允许比变体更通用的集合（称为可定义集合）。 o-最小关联几何领域涉及可定义集合的组合问题，迫切需要多项式划分定理——这一工具一直是传统关联几何中的万能药。然而，事实证明这很困难，因为限制于簇的可定义集合的最坏情况拓扑复杂性可能是“坏的”。我们建议转而研究限制于随机簇的可定义集合的平均情况复杂性。通过这样做，我们希望证明拓扑“坏”多项式是不寻常的（我们已经针对某些可定义的集合证明了这一点）。因此，如果适合划分的多项式的测度足够大，我们将通过概率方法证明具有“良好”拓扑复杂性的划分多项式的存在。这将为最小关联几何提供巨大的推动。我们的第二个方向是代数拓扑问题及其在计算复杂性理论中的应用。计算复杂性理论是一个数学领域，它根据解决问题所需的资源对问题进行分类。该领域最重要的开放问题是极其困难的 P 与 NP 问题。最近，在几何复杂性理论（GCT）计划下，这个问题得到了推动，该计划涉及用代数语言来解决相关问题。希望代数几何和表示论领域的先进工具能够让我们在这个问题上取得进展。GCT 计划的中心目标是分离某些称为轨道闭合的空间。虽然这显然是一个崇高的目标，但我们的目标是计算这些轨道闭合的拓扑。计算拓扑有助于粗略地了解所涉及对象的几何形状。此外，众所周知，获得空间拓扑的定量界限有助于理解在空间上运行的计算程序的基本限制。我们还将研究乌尔里希复杂度的概念，它量化了多项式的“复杂性”另一种方式。虽然它可以使用交换代数概念方便地定义，并且显然更容易使用，但总体上人们对它了解甚少。我们将研究 Kostlan 多项式的平均乌尔里希复杂度。众所周知，获得多项式乌尔里希复杂度的下界可能会对交换代数中的一个重要猜想以及 P 与 NP 问题产生潜在影响。

项目成果

Betti numbers of random hypersurface arrangements

随机超曲面排列的贝蒂数

• DOI: http://dx.10.1112/jlms.12658
• 发表时间: 2022
• 期刊: Journal of the London Mathematical Society
• 作者: Basu S