Motivation: “To prove that P=NP”. More seriously, there is a very powerful technique, called Sum of Squares (SOS) of polynomials in the optimization. For instance, if , where and are some polynomials it is obvious that is non-negative. Unfortunately, this does not work in opposite direction. There are examples of positive polynomials that are not a sum of squares of other polynomials. Therefore, automatic generation of non-negative polynomials that are not sums of squares allows to extend applicability of SOS technique. If we would be enable to generate enough of such polynomials the global minimum of any polynomial function would be accessible. Consequently, P would be equal NP. This post has modest goal is to understand how to generate algorithmically a single positive polynomial that is not a sum of squares of other polynomials in arbitrary dimension. In a sense this is a formalization of previous post.
Let , where is an arbitrary unique symbol denoting variable. For example, . Let being evaluation of the set at point . For example, for any point x, . , where . Let polynomial be a linear combination of elements of , where enumerates elements of the set.
NP-complete integer partition problem
Let . Integer partition problem is asking whether , e.g. whether it is possible to divide set of integers into two complementary sets that have equal sum. This problem is NP-complete.
Proposition 1 Integer partition problem is equivalent to the question whether global minimum of polynomial is greater than zero or not.
Proof Since the polynomial is a sum of squares of real variables, it is non-negative and can be zero only when each term is zero. the first sum can only be zero at the values of . The second sum at given values can be zero only when partition exists
Corollary To prove P=NP it is sufficient to analyse quartic polynomials.
Zeros of quadratics on hyper-cube
Here we would like to establish some properties of the quadratic polynomials on the hyper-cube
Propostiion 2 Consider quadratic polynomial . If than .
, taking into account second case.
Finally, , which is clearly 0 for , since in each term in the sum either first or second factor is 0
Quartics that vanish on
, taking into account second case.
Additionally, we want quartics to preserve sign around , since we are interested in positive polynomials. Necessary condition is that gradient equals 0 for corresponding points.
is splitted into 2 cases. and
together with that lead to
split again into the same cases.
together with and that lead to .
. The last condition counted over triplet lead to Robinson perturbation term
Combining all conditions together we get
Now we need to analyze the possible values of coefficients that guarantee positiveness of quartic polynomial.
Update Jan 6 2016
What is interesting is that
(1) if quartic is positive and has zeros forming n-simplex than its form is constrained. After a linear transformation this simplex can be transformed into standard orthogonal simplex with zeros being at
This leads to constraints on the coefficients of positive quartic polynomials. For instance, zero at 0 lead to . Zero gradient (necessary for quartic being positive) leads to . Zeros at other vertices lead to the following constraint , whereas zero gradient leads to leading to null-space , i.e. for any which leads to polynomial
, where have no single variable term. Therefore, this simple requirement leads to representation of quartic positive polynomial as sums of squares plus some perturbation.
(2) It is sufficient to spread enough zeros across space, not necessary on the corner of hyper-cube to nullify all coefficient of quadratics. There are coefficients in quadratics. For the corresponding quartic we need at least generic points where quartic and its gradient vanish. That leads to constraints. We need more coefficients to have some freedom. That is achievable for the dimension more than 5. That is saying that perturbation can be very strong.
To be continued.