Sums of Squares: From Algebraic Geometry to Extremal Combinatorics and Quantum Entanglement

该项目属于应用代数几何领域，位于几个不同领域的交叉点：代数几何（实数和复数）、组合学（图密度不等式）和理论物理学（量子纠缠）。连接这些领域的主线是非负多项式的平方和近似，它在优化和理论计算机科学中也有广泛的应用。非负性及其与平方和的关系的研究是真正的代数几何的基本挑战之一，然而这些问题与复数代数几何有一个日益紧密的联系。PI和受资助的学生将研究平方和方法的计算能力，同时在理论物理、组合学和优化以及与复杂代数几何的联系方面进行应用。数学、工程和自然科学之间的联系带来了新的问题类型和研究方向，丰富了各个方面。这项工作与美国国家科学基金会（NSF）十大创意之一的量子飞跃（Quantum Leap）紧密相关。非负性及其与平方和的关系的研究是实际代数几何的基本挑战之一。平方和方法在许多不同的领域都有应用，比如优化、物理和计算机科学。凸对偶将非负多项式与实数分析的截断矩问题联系起来。在某些情况下，量子纠缠检测可以表述为半代数集上的对称截断矩问题。在极值组合学中，平方和方法被用来证明图密度不等式，这解决了所谓的图兰问题。推广全局非负性问题的一种自然方法是考虑实数射影变化上的平方和和和的非负形式。有一种新兴的理解，即平方和问题与经典研究的性质密切相关，例如品种的坐标环的最小自由分辨率。项目负责人和获资助的学生将在以下几个方向进行进一步研究：变体平方和的研究与其自由分辨率的性质之间的联系，实数投影变体上有理数平方和表示的度界，极值组合中平方和方法的局限性，在证明图密度不等式中使用非负的平方和证明，以及对称性对平方和松弛的影响及其在量子纠缠检测中的应用。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

This project is in the area of applied algebraic geometry, and lies at the intersection of several different areas: algebraic geometry (real and complex), combinatorics (graph density inequalities) and theoretical physics (quantum entanglement). The thread linking these areas together is sum of squares approximation to nonnegative polynomials, which additionally has extensive applications in optimization and theoretical computer science. The study of nonnegativity and its relation with sums of squares is one of the basic challenges of real algebraic geometry, yet there is an emerging tight connection of these questions with algebraic geometry over complex numbers. The PI and students supported by the grant will investigate the computational power of the sums of squares method, while pursuing applications in theoretical physics, combinatorics and optimization, and connections with complex algebraic geometry. Connections between mathematics, engineering and natural sciences enrich all sides by bringing new types of questions and directions of research. This work is firmly aligned with Quantum Leap, one of the NSF's 10 Big Ideas.The study of nonnegativity and its relation with sums of squares is one of the basic challenges of real algebraic geometry. Sums of squares methods found applications in many diverse areas, such as optimization, physics and computer science. Convex duality connects nonnegative polynomials to truncated moment problems of real analysis. Quantum entanglement detection can be stated as a symmetric truncated moment problem on a semialgebaric set in some cases. Within extremal combinatorics the sum of squares approach was used to prove graph density inequalities, which address so-called Turan problems. A natural approach, generalizing questions of global nonnegativity, is to consider sums of squares and nonnegative forms on a real projective variety. There is an emerging understanding that sums of squares questions are intimately related to classically studied properties, such as the minimal free resolution of the coordinate ring of the variety. The PI and students supported by the grant will investigate several directions for further research: connections between the study of sums of squares on a variety and the properties of its free resolution, degree bounds for rational sums of squares representations on real projective varieties, limitations of sums of squares method in extremal combinatorics, using non-sum-of-squares certificates of nonnegativity in proving graph density inequalities, and effects of symmetry on sums of squares relaxations of nonnegativity with applications to quantum entanglement detection.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.