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

点击翻译按钮获取中文摘要

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.