Polynomial decompositions with invariance and positivity inspired by tensors

Abstract

We present a framework to decompose real multivariate polynomials while preserving invariance and positivity. This framework has been recently introduced for tensor decompositions, in particular for quantum many-body systems. Here we transfer results about decomposition structures, invariance under permutations of variables, positivity, rank inequalities and separations, approximations, and undecidability to real polynomials. Specifically, we define invariant decompositions of polynomials and characterize which polynomials admit such decompositions. We then include positivity: We define invariant separable and sum-of-squares decompositions, and characterize the polynomials similarly. We provide inequalities and separations between the ranks of the decompositions, and show that the separations are not robust with respect to approximations. For cyclically invariant decompositions, we show that it is undecidable whether the polynomial is nonnegative or sum-of-squares for all system sizes. Our work sheds new light on polynomials by putting them on an equal footing with tensors, and opens the door to extending this framework to other tensor product structures.

arXiv commentv2: 39 pages, close to published version

References in corpus (9)

• Separability Criterion for Density Matrices
• Tensor networks for complex quantum systems
• Symmetry groups, semidefinite programs, and sums of squares
• Lifts of convex sets and cone factorizations
• Matrix product operators and states: NP-hardness and undecidability
• Positive semidefinite rank
• Fundamental limitations in the purifications of tensor networks
• On the Waring problem for polynomial rings
• Mixed states in one spatial dimension: decompositions and correspondence with nonnegative matrices

Cited by in corpus (2)

• Border Ranks of Positive and Invariant Tensor Decompositions: Applications to Correlations
• Positive Moments Forever: Undecidable and Decidable Cases