Sums of Squares on the Hypercube

Understand

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.