I was playing around with gröbner basis and s-polynomials and I fell upon the PolynomialReduce, and I was wondering why it gives different results when I move around the polynomials in its second parameter,

PolynomialReduce[x^2 (x^2 + y) - 1 (x^2 y + 1), {x^2 y + 1, y + x^2, x^4 - 1}, {x, y}]


{{-1, x^2, 0}, 0}


PolynomialReduce[ x^2 (x^2 + y) - 1 (x^2 y + 1), {y + x^2, x^2 y + 1, x^4 - 1}, {x, y}]


{{x^2 - y, 0, 0}, -1 + y^2}

which is obviously wrong** as it is very apparent that the coefficients is just x^2 and -1.

Can anybody shed some light on this? It's very disturbing and confusing.

[edit] **the result might not be wrong, but it does not give the minimal b as per instruced by the documentation http://reference.wolfram.com/language/ref/PolynomialReduce.html


It appears that the only thing that PolynomialReduce guarantees is that

p[x,y]= c1 b1[x,y] + c2 b2[x,y] + ... + cn bn[x,y] + r

where {{c1,c2,...,cn},r} is the result of polynomial reduce, as it is for your example.

Not that the result is in any way minimal or unique. In your example p[x,y] = x^4 - 1, so in fact the 'best' result would be {{0,0,1},0}, but this is only obtained when x^4 -1 is the first polynomial.

I am quite sure that result of general polynomial division is not unique unless over a (reduced) Groebner basis. The Groebner basis for the ideal generated by your two polynomial sets are, of course, the same.

  • $\begingroup$ (John I'm sure knows this but...) just to chime in, this response is correct in every detail. $\endgroup$ – Daniel Lichtblau Aug 5 '14 at 14:18
  • $\begingroup$ An additional though: in the linear algebra case if v, u1, u2 are vectors in Rn then projecting v onto u1, then projecting (v - proj(v,u1)) onto u2 will also give a different result than projecting onto u2 first, unless u1,u2 are orthogonal. $\endgroup$ – John McGee Aug 5 '14 at 14:27
  • $\begingroup$ But the specification reference.wolfram.com/language/ref/PolynomialReduce.html Actually guarantees that 'b is minimal' ? $\endgroup$ – DrLime2k10 Aug 5 '14 at 14:59
  • $\begingroup$ Yes, for a suitable definition of "minimal". It simply means that b cannot be further reduced by the list of polynomials. For "canonical" you need to first create a Groebner basis, per this response. $\endgroup$ – Daniel Lichtblau Aug 5 '14 at 15:39
  • $\begingroup$ Can you explain why I am getting the following results then when I am reducing it to a groebner basis? gb := GroebnerBasis[{y + x^2, x^2 y + 1, x^4 - 1}, {y, x}] PolynomialReduce[x^2 (x^2 + y) - 1 (x^2 y + 1), gb, {y, x}] (*gives result*) {{1, 0}, 0} Now these are just not correct in any sense. $\endgroup$ – DrLime2k10 Aug 5 '14 at 18:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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