# Algorithm for expressing a homogeneous polynomial with integer coefficients nonnegatively (if possible) in terms of specific dependent binomials

I have specific homogeneous polynomials expressed in terms of binomials of the form $$x_i+y_j$$ for $$i,j\in\mathbb N$$ with integer coefficients that I conjecture can have nonnegative coefficients when expressed in terms of these binomials. I have an algorithm for generating the polynomials, but the specific expressions the algorithm generates often do not have nonnegative coefficients; in fact if the algorithm did express them visibly with nonnegative coefficients, provably in all cases, I'd likely win a Fields medal. I'm looking for an algorithm for expressing these polynomials with nonnegative coefficients (if possible) in terms of these binomials, starting with an expression that can have arbitrary, possibly negative, coefficients. I suspect my algorithm generates expressions where this can be achieved with cancellation by inspection, but I have no evidence for this.

I think this is probably something where a general algorithm, starting with an arbitrary polynomial with integer coefficients in terms of products of binomials of the form $$x_i+y_j$$ and ending with an expression with nonnegative coefficients (if possible) would be preferable instead of me telling you what the specific polynomials are, as I don't think it would help to know them. For those "in the know," or those who want to look it up, they are the result of applying a skew divided difference operator to a double Schubert polynomial, i.e. there are permutations $$u,v,w$$ such that the polynomial is $$\partial_u^w(\mathfrak{S}_v(x;-y))$$ Skew divided difference operators (with different conventions from mine, though for this purpose it is irrelevant) are defined in this paper where the symmetric group acts trivially on the $$y$$ variables, and double Schubert polynomials are defined here, though I assure you the references will likely not help.

As requested, an example polynomial where my algorithm generates a negative coefficient is $$-(y_{1}+ z_{1}) (y_{1} + z_{2}) + (y_{1} + z_{1}) (y_{4} + z_{1}) + (y_{1} + z_{2}) (y_{1} + y_{3} + z_{1} + z_{2}) + (y_{3} + z_{2}) (y_{4} + z_{1})$$ It should not be difficult to eyeball the cancellation that makes this representable positively.

• Why is there no $y_2$? And why does the tetranom $(y_1 + y_3 + z_1 + z_2)$ occur? Apr 1, 2022 at 8:42
• @Christian It's a simplification done by my computer algebra program. There's no $y_2$ because that's just how that example works out. Apr 1, 2022 at 16:32