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

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

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.