Algorithm for determining an algebraic positivity property of a multivariate polynomial

Question

I am considering multivariate polynomials with integer coefficients that can be expressed as sums of products of terms of the form $y_i-z_j$ for positive integers $i$ and $j$. I am trying to find an algorithm to determine if there is a way to express them in terms of these linear factors in such a way that the terms have nonnegative coefficients. I have a conjecture that this is always true for the polynomials that I am considering, and I want to do some extensive testing of it.

For example, my program outputs the following in one case (for reasons of speed, absolutely no simplification is done intermediately; computing the coefficients is at best $\#P$-complete even when the degree of the polynomial is $0$): $$-2 (y_2 - z_1) (y_1 - z_1) + 2 (y_1 + y_2 - z_1 - z_2) (y_1 + y_2 - z_1 - z_3) - (-(y_2 - z_1) (y_1 - z_1) + (y_1 + y_2 - z_1 - z_2) (y_1 + y_2 - z_1 - z_3))$$ This is not expressed in a positive manner, but there is cancelation you can do to get $$(y_2-z_1)(y_2-z_3)+(y_1-z_2)(y_1-z_1)+(y_1-z_2)(y_2-z_3)$$ and this would pass the test.

For context, it's considered a hopelessly difficult unsolved problem to determine whether computing the degree $0$ coefficients is in $\#P$, though the problem is known to be in $\mathrm{GapP}^+$.

When I plug this example into Maple and call simplify, I get $$y_1^2 + (y_2 - z_1 - z_2 - z_3)*y_1 + y_2^2 + (-z_1 - z_2 - z_3)*y_2 + (z_2 + z_3)*z_1 + z_2*z_3$$ which is not really very helpful.

A conjecture that would be easier to check is that, when expanded, the polynomial has nonnegative coefficients in terms of $y_i$ and $-z_j$, but this is not quite the same.

I am really just looking for any algorithm at all; it doesn't have to be fast.

Answer 1

Here is a semi-algorithm. I don't know if it is a good one. If you conjecture is true, it always terminates. In particular, if a solution exists, it will find it; if no solution exists, it will run forever, searching for one.

Let $p(x)$ be the original polynomial; it can be expressed in the form $$p(x) = \sum_S \alpha_S \prod_{(v,w) \in S} (v-w),$$ where $S$ is a set of pairs $(v,w)$ of variables (here $v$ is some $y_i$ and $w$ is some $z_j$). Let $q(x)$ be the re-expressed polynomial we are trying to search for. Let $k$ be an upper bound on the number of terms in the product, which might initially be set to 2. Then the general form of the non-negative polynomial is $$q(x) = \sum_S \beta_S \prod_{(v,w) \in S} (v-w),$$ where the sum is over all sets $S$ of pairs, such that $|S|\le k$. We require that $p(x)=q(x)$ and $\beta_S \ge 0$ for all $S$. Given the $\alpha$'s, our goal is to find $\beta$'s that satisfy these conditions.

Notice that we can multiply out each product above, putting $p(x)$ into the following form:

$$p(x) = \sum_T \delta_T \prod_{v \in T} v,$$

where $T$ ranges over multisets of variables. Here $\delta_T$ can be expressed as a linear function of the $\alpha_S$'s. Since the $\alpha$'s are given, this means we can compute each $\delta_T$ as an explicit constant. Similarly,

$$q(x) = \sum_T \gamma_T \prod_{v \in T} v,$$

where $\gamma_T$ is a known linear function of the $\beta_S$'s. $\gamma_T$ is not known, but it is a linear function of the $\beta$ variables.

Finally, since we want to have $p(x) = q(x)$, this means we require $\delta_T = \gamma_T$ for all $T$, which means we equate the known constant $\delta_T$ to the linear function of $\beta$'s that represents $\gamma_T$. Also, we have the inequality $\beta_S \ge 0$ for all $S$.

Putting it together, this gives us a system of linear equalities and inequalities on the $\beta_S$'s. We can then use linear programming to check whether there exists a solution to this linear system. If there exists a solution, then we have found a way to express $p(x)$ in the desired form.

If there is no solution, then we can increase $k$ and try again. Repeat until we find a solution. If a solution exists, we will eventually find it. The complexity will be exponential, as there can be exponentially many $S$'s and $T$'s, but it is something that can be implemented. However, if no solution exists, this will run forever.

To test your conjecture, as a heuristic, you could set an upper bound on $k$, and then any polynomial where no solution is found up to that value of $k$ is a candidate that might violate the conjecture; and if no such candidate is found, then it increases confidence in your conjecture (but of course does not prove it).