Monomial order when testing ideal membership with PolynomialReduce?

Question

The documentation for PolynomialReduce points out that, to test membership in an ideal, the list of polynomials must be a Groebner basis for that ideal. But does the monomial order specified to PolynomialReduce need to agree with the monomial order that was earlier specified to GroebnerBasis? In the examples in the documentation, those two orders always agree; but it isn't clear whether that agreement is required.

If those two orders do need to agree, suppose that I specify Sort->True when calling GroebnerBasis. How can I find out what variable ordering GroebnerBasis actually used, so that I can specify that same ordering to PolynomialReduce?

Answer 1

First question. Yes, the monomial orders must agree in order to have the guarantees that come with Groebner bases, for example to conclusively check membership in an ideal.

Let me take the following example from the PolynomialReduce documentation:

f=2*x^3+y^3+3*y;
polys={x^2+y^2-1,x*y-2};

Three examples:

• Lexicographic respectively Lexicographic:

gb=GroebnerBasis[polys,{x,y}];
PolynomialReduce[f,gb,{x,y}]
(* {{...}, 0} *)

This recognizes that f is in the ideal, as expected.

• Lexicographic respectively DegreeLexicographic:

gb=GroebnerBasis[polys,{x,y}];
PolynomialReduce[f,gb,{x,y},MonomialOrder->DegreeLexicographic]
(* {{...},-2 x+2 x^3+4 y} *)

This fails to recognize that f is in the ideal.

• Finally, note that also the order of the variables is part of the definition of the monomial order. In this example, I use Lexicographic in both cases but I use {y,x} for the reduction:

gb=GroebnerBasis[polys,{x,y}];
PolynomialReduce[f,gb,{y,x}]
(* {{...},-2 x+2 x^3+4 y} *)

Again, this fails to recognize that f is in the ideal.

Second question (edit based on comment by @DanielLichtblau). As OP says, it then follows that also Sort->True can also cause this problem.

To illustrate this, let me take the following example from the GroebnerBasis documentation:

polys={3 x^7+5 x y z^2-10 y^2 z-6 x z+y^3+w,
       -2 x^2 z+3 x^3 y^2+y^4-12 x z-8 x z^2+3 y^2 z-11 w x y^2,
       10 x^2 w-7 y z w^2-2 x z^4 w+4 x^2 y+3 x y^2-6 y z^3-w+2,
       w^3-w x^2 y+x y z^2-2 w x z^2-3 w-2 x y^2-3};

If we use Sort->True then this fails to recognize that the third of the original polynomials is in the ideal:

gb=GroebnerBasis[polys,{w,x,y,z},Sort->True,MonomialOrder->DegreeReverseLexicographic];
PolynomialReduce[polys[[3]],gb,{w,x,y,z},MonomialOrder->DegreeReverseLexicographic]
(* {{...},2-w+10 w x^2+4 x^2 y+3 x y^2-7 w^2 y z-6 y z^3-2 w x z^4} *)

Based on the comment of @DanielLichtblau we can do the following:

sortvars = Last[GroebnerBasis`DistributedTermsList[polys,{w,x,y,z},
                Sort->True,MonomialOrder->DegreeReverseLexicographic]]
(* {w,z,y,x} *)

Now

PolynomialReduce[polys[[3]],gb,sortvars,MonomialOrder->DegreeReverseLexicographic]
(* {{...}, 0} *)