0
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ What is $n$? Is it the total degree of the polynomial? Is it the number of variables? Would it be enough to consider only expressions where the number of terms in each product is at most the total degree of the original polynomial? $\endgroup$
    – D.W.
    Commented Jan 26, 2023 at 2:46
  • $\begingroup$ What's the best algorithm you know so far? I gather this is the same question as math.stackexchange.com/q/4404782/14578? $\endgroup$
    – D.W.
    Commented Jan 26, 2023 at 2:48
  • $\begingroup$ @D.w. $n$ is the rank of the permutation group in the problem. $n=5$ has $120^2$ sets of cases to check. It's not really important to the question so maybe I shouldn't have included it. I asked this question because I can't think of any algorithm to do it at all. $\endgroup$ Commented Jan 26, 2023 at 2:51
  • $\begingroup$ The problem never mentions any permutation group, so I'm not sure what that refers to. I'm still wondering about the prior question about whether we can limit the number of terms in each product, based on the degree of the original polynomial. $\endgroup$
    – D.W.
    Commented Jan 26, 2023 at 2:52
  • $\begingroup$ @D.W. I haven't described the problem that these polynomials come from at all because it's not relevant to the question, so perhaps I shouldn't have mentioned $n=5$. I'm happy to describe what the problem is privately but it would sort of derail the question I think. I can remove the reference to $n$ if needed. $\endgroup$ Commented Jan 26, 2023 at 2:54

1 Answer 1

2
$\begingroup$

Here is a semi-algorithm. I don't know if it is a good one. If your 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).

$\endgroup$
13
  • $\begingroup$ Thanks! Like I said, any algorithm is better than none. I didn't expect one that ran forever if the conjecture fails, but I can work with that. I expect that the conjecture is true anyway. Unfortunately I have a "day job" that is unrelated to this so I won't be able to test this until this weekend. $\endgroup$ Commented Jan 26, 2023 at 11:53
  • $\begingroup$ I think this actually can be made to always terminate. The polynomials are homogeneous, so I think there's a maximum "generic polynomial." $\endgroup$ Commented Jan 26, 2023 at 12:31
  • $\begingroup$ That would be $131,128,140$ terms for degree $10$ in $5$ pairs of variables. Not sure how many variables are feasible for linear programming, but I'm guessing that's not it. Can probably be refined. Anyway, I think this will work. Thanks. $\endgroup$ Commented Jan 26, 2023 at 13:19
  • $\begingroup$ I've thought about your answer all day and I think the way to go is as follows: Find the monomials in the $y$ variables when you $0$ out the $z$ variables and vice versa, then pair these up in all possible ways to get the terms on which to optimize. I think there should be few enough that it will be feasible. $\endgroup$ Commented Jan 26, 2023 at 22:44
  • $\begingroup$ @MattSamuel, a generalization of that is to pick a subset of monomials $T$ and equate their coefficients. This gives a subset of the equalities in the full linear system. If the full linear system is over-constrained, it might be sufficient to pick a subset of equalities, search for a solution to the subsystem, and test whether it happens to give you a solution to the full system (if it doesn't, then the results are inconclusive and have to increase the number of monomials in your subset). $\endgroup$
    – D.W.
    Commented Jan 27, 2023 at 0:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.