# Polynomial in Compact Polytope: PolynomialReduce with positive “poly” terms and zero remainder?

Context: I am trying to code a function in Mathematica by which I can check whether a polynomial is non-negative in some compact polytope such as specified by interval values for each variable. This is very much relevant to this publication here on Handelman's theorem. Relevant problems here with focus on Mathematics and here with focus on programming.

Consider a polynomial. Can we make Mathematica to return terms in PolynomialReduce command such that each term is positive and remainder zero otherwise alert that no solution?

How to find the positive linear combination of products of members of $\{\beta_i\}$ for a polynomial $f$ where each $\beta_i$ corresponds to a constraint on variables of $f$?

Example

I need to find out a way to specify to Mathematica that each term must be positive in the return.

The third term $-x_1$ is negative because $0.2\leq x_1\leq 0.5$. We transform the inequalities to linear form and then try to apply the Handelman's theorem, originally also inequality $0\leq x_2\leq 1$ and $x_3=1$

PolynomialReduce[
x3 - x1*x2 - 2, {x1 - 0.2, -x1 + 0.5, x2, -x2 + 1,
x3 - 1, -x3 + 1}, {x1, x2, x3}]
PolynomialReduce[
x3 - x1*x2, {x1 - 0.2, -x1 + 0.5, x2, -x2 + 1, x3 - 1, -x3 + 1}, {x1,
x2, x3}]
PolynomialReduce[
x3 - x1*x2 - 1, {x1 - 0.2, -x1 + 0.5, x2, -x2 + 1,
x3 - 1, -x3 + 1}, {x1, x2, x3}]


and its picture, where the result of PolynomialReduce cannot be used because of the negative terms. The Handelman requires to find positive linear combination of products of members of $\{\beta_i\}$ where $\beta_i$ terms are the linearised form of each inequality.

• (1) Actual code is much better than an image of code. (2) You should recheck documentation for PolynomialReduce. Giving a pair of polynomials such as x-1/5,x-1/2 is tantamount to stating that 1 is in the ideal. (3) Almost certainly it is the wrong tool for this situation. Some form of quantifier elimination might be needed. – Daniel Lichtblau Aug 2 '16 at 17:01
• Re, "compact polytope" - polytopes are compact by definition. – alancalvitti Aug 2 '16 at 17:13
• Polytopes can be unbounded. – Daniel Lichtblau Aug 2 '16 at 17:29
• Compact means bounded, yes, Also means weak inequalities, that is to say, it includes its boundary. – Daniel Lichtblau Aug 2 '16 at 21:02
• Think of PolynomialReduce as working on equations (it most certainly does not deal with inequalities). If you have equations {x==1/5,x==1/2} then your ideal contains 1: In[435]:= GroebnerBasis[{x == 1/5, x == 1/2}, x] Out[435]= {1} – Daniel Lichtblau Aug 2 '16 at 21:08

Minimize[{x3 - x1*x2 - 2, {1/5 <= x1 <= 1/2, 0 <= x2 <= 1,

• How can you solve the non-negativity with some algebraic geometric method without minimizing directly? See Example 2 where each inequality corresponds to a product term $\beta_i$ to form the set $\{\beta_i\}$. The problem is to find $f=a_1\beta_1+\ldots+a_n\beta_n$ where remainder is zero to use the Handelman's theorem without minimizing the function directly. – hhh Aug 2 '16 at 21:26
• Prof. Handelman sees in terms of product of simplices (apparently simplicial complexes) & aff equivalance here: "if the polytope is not so equivalent, then the positivity condition is much more difficult" -- he refers to his more recent publication but I cannot understand it: what is "praise" in title "In praise of order units"? They show that ordered rings associated to compact convex polyhedra with interior satisfy a positivity property known as order unit cancellation. Can you understand how this could be used for algebraic geometric solution? – hhh Aug 2 '16 at 22:02