Abstract: Let X be a finite set of points in R^n. A polynomial p nonnegative on X can be written as a sum of squares of rational functions modulo the vanishing ideal I(X). From the point of view of applications, such as polynomial optimization, we are interested in rational function representations of small degree. We derive a general upper bound in terms of the Hilbert function of X, and we show that this upper bound is tight for the case of quadratic functions on the hypercube C={0,1}^n, a very well studied case in combinatorial optimization. Using the lower bounds for C we construct a family of globally nonnegative quartic polynomials, which are not sums of squares of rational functions of small degree. To our knowledge this is the first construction for Hilbert's 17th problem of a family of polynomials of bounded degree which need increasing degrees in rational function representations as the number of variables n goes to infinity. We note that representation theory of the symmetric group S_n play a crucial role in our proofs of the lower bounds.
Recommendations
Cites work
- scientific article; zbMATH DE number 1601019 (Why is no real title available?)
- scientific article; zbMATH DE number 1601795 (Why is no real title available?)
- scientific article; zbMATH DE number 4160796 (Why is no real title available?)
- scientific article; zbMATH DE number 177492 (Why is no real title available?)
- scientific article; zbMATH DE number 704831 (Why is no real title available?)
- A new semidefinite programming hierarchy for cycles in binary matroids and cuts in graphs
- An elementary recursive bound for effective Positivstellensatz and Hilbert's 17th problem
- An explicit equivalent positive semidefinite program for nonlinear 0-1 programs
- Cayley-Bacharach theorems and conjectures
- Certificates of impossibility of Hilbert-Artin representations of a given degree for definite polynomials and functions
- Global optimization with polynomials and the problem of moments
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Lower Bound for the Number of Iterations in Semidefinite Hierarchies for the Cut Polytope
- Positive polynomials and sums of squares
- Semidefinite Optimization and Convex Algebraic Geometry
- Semidefinite programming relaxations for semialgebraic problems
- Semidefinite representations for finite varieties
- Sparse sums of squares on finite abelian groups and improved semidefinite lifts
- Theta bodies for polynomial ideals
Cited in
(17)- Sums of squares of polynomials with rational coefficients
- scientific article; zbMATH DE number 6093164 (Why is no real title available?)
- Union of hypercubes and 3D Minkowski sums with random sizes
- Symmetric sums of squares over \(k\)-subset hypercubes
- Sum of squares lower bounds from symmetry and a good story
- Positivity certificates and polynomial optimization on non-compact semialgebraic sets
- On vanishing sums of roots of unity in polynomial calculus and sum-of-squares
- Sharp degree bounds for sum-of-squares certificates on projective curves
- The Spectrum of the Grigoriev–Laurent Pseudomoments
- Sparse sums of squares on finite abelian groups and improved semidefinite lifts
- Query complexity in expectation
- Error bounds for polynomial optimization over the hypercube using Putinar type representations
- Harmonic Hierarchies for Polynomial Optimization
- scientific article; zbMATH DE number 1757257 (Why is no real title available?)
- Computing sparse Fourier sum of squares on finite abelian groups in quasi-linear time
- An elementary recursive bound for effective Positivstellensatz and Hilbert's 17th problem
- On sumfree subsets of hypercubes
This page was built for publication: Sums of squares on the hypercube
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q329957)
