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.

*Preliminaries*

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.

**Proof** Obvious

*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 .

**Proof**

Consequitively,

.

.

, 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 *

.

Consequently,

.

.

, 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.

.

Consequently,

.

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.

To be continued.