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

这个项目是在应用代数几何领域，并在几个不同的领域的交叉点：代数几何（真实的和复杂的），组合（图形密度不等式）和理论物理（量子纠缠）。将这些领域连接在一起的线索是非负多项式的平方和近似，它在优化和理论计算机科学中也有广泛的应用。研究非负性及其与平方和的关系是真实的代数几何的基本挑战之一，然而这些问题与复数上的代数几何有着紧密的联系。PI和由补助金支持的学生将调查平方和方法的计算能力，同时追求在理论物理，组合数学和优化，以及与复杂代数几何的连接中的应用。数学，工程和自然科学之间的联系通过带来新类型的问题和研究方向来丰富各个方面。这项工作与美国国家科学基金会十大理念之一的量子跳跃紧密相连。非负性及其与平方和的关系的研究是真实的代数几何的基本挑战之一。平方和方法在许多不同的领域，如优化，物理和计算机科学中找到应用。凸对偶将非负多项式与真实的分析的截断矩问题联系起来。量子纠缠的检测在某些情况下可以描述为半代数集上的对称截断矩问题。在极值组合学中，平方和方法被用来证明图密度不等式，解决所谓的图兰问题。一个自然的方法，推广问题的整体非负性，是考虑平方和和非负形式的真实的射影品种。有一个新兴的理解，平方和问题是密切相关的经典研究的性质，如最小的自由决议的坐标环的品种。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.