Nonnegative coefficients of a product of polynomials

Question

Let $P(x_1,\dots,x_n)\in\mathbb{R}[x_1,\dots,x_n]$. Does there exist an algorithm to decide whether there is a nonzero polynomial $Q(x_1,\dots,x_n)\in\mathbb{R}[x_1,\dots,x_n]$ such that the product $PQ$ has nonnegative coefficients? (The case $n=1$ is well-known and not difficult.)

Answer 1

Assuming $P(1,1,\dots,1) >0$, the condition (necessary and sufficient) on $P$ is that $P_F$ is strictly positive on the strictly positive orthant for all faces of dimension one or more of the Newton polyhedron of $P$ (where $P_F$ is the subpolynomial of $P$ obtained by discarding all the monomials whose exponent does not lie in $F$; we of course have to permit $F$ to be the improper face) [see also {When can a function be made positive by averaging?}], and when that occurs, we can choose $Q$ to be some (unknown) power of $Q_1= \sum x^w$ where $w$ runs over the lattice points in the Newton polytope (yielding a pseudo-algorithm; we don't know if it eventually results in no negative coefficients; it will only do this if a $Q$ exists, and even then, there does not appear to be a way of estimating the power of $Q_1$ required).

Is there an algorithm to decide whether a polynomial is strictly positive on the positive orthant? If so, then it can be applied to all the $P_F$.

If however, as I suspect, there is no algorithm (to decide strict positivity on an orthant), then there is a problem. In the one variable case, if $Q$ exists, it can be chosen of the form $(1+x)^n$, and so we obtain a pseudo-algorithm (we don't know if it will terminate) by repeatedly adding pairs of consecutive coefficients). With more than one variable, no such single poly powers of which will do (in fact, infinitely many are required).

We can get some inkling of what $Q$ should look like, by restricting to faces; assuming the Newton polyhedron of $Q$ is $k$ times that of $P$ (which we can assume for some $k$, except we don't know what the minimum $k$ will be), then $P_F Q_{kF}$ will also have no negative coefficients.