reduce in quotient rings is broken

[mwageringel]

Reduction modulo ideals in quotient rings does not return unique minimal representatives.

In this example, the ideal J in the quotient ring Q = R/I contains the element t^2 - z^2, so reduce should return 0.

sage: R.<T,U,V,W,X,Y,Z> = PolynomialRing(QQ, order='lex')
sage: I = R.ideal([T^2+U^2-1, V^2+W^2-1, X^2+Y^2+Z^2-1])
sage: Q.<t,u,v,w,x,y,z> = R.quotient(I)
sage: J = Q.ideal([u*v-x, u*w-y, t-z])
sage: J.reduce(t^2 - z^2)  # should be 0
w^2*z^2 - w^2 + y^2
sage: J.reduce(t^2 - z^2).lift() in I  # reduction is not unique mod I, i.e. result is not even mathematically unique in Q
False

These results do not agree with the documentation:

sage: J.reduce?
   ...
   Reduce an element modulo the reduced Groebner basis for this ideal.
   This returns 0 if and only if the element is in this ideal. In any
   case, this reduction is unique up to monomial orders.
   ...

The expected behavior would be the same as lifting the ideal J to the cover ring R, perform reduction there (in terms of the ideal generated by I and the lifted generators of J) and map the result back to Q (by e.g. Thm. 9.19 in [https://doc.sagemath.org/html/en/reference/references/index.html#bw1993 [BW1993]]):

sage: Q(Q.cover().inverse_image(J).reduce((t^2 - z^2).lift()))  # correct
0

Possibly related: #27508, #32291

CC: @mjungmath @tscrim

Component: commutative algebra

Author: Markus Wageringel

Branch/Commit: 0cc8b67

Reviewer: Travis Scrimshaw

Issue created by migration from https://trac.sagemath.org/ticket/33217

[mwageringel]

comment:1

Currently, the implementation first computes J.groebner_basis() which seems to compute the Gröbner basis in the cover ring R and maps the result to Q, discarding elements that are 0. Then it performs reduction with respect to this sequence of quotient ring elements (which does not appear meaningful – are Gröbner bases even defined for quotient rings?). This has likely never worked.

[mwageringel]

comment:2

The example in the description comes from this computation which depends on the correct behavior of reduce:

sage: A.<x,y,z> = QQ['X,Y,Z'].quotient('X^2+Y^2+Z^2-1')
sage: B.<t,u,v,w> = QQ['T,U,V,W'].quotient(['T^2+U^2-1', 'V^2+W^2-1'])
sage: psi = A.hom([v*u, w*u, t], B)
sage: psi(z^2) == t^2  # z^2 is a preimage
True
sage: psi.inverse_image(t^2)  # but z^2 is a preimage
...
ValueError: element -u^2 + 1 does not have preimage

[mwageringel]

comment:3

The equivalent computation in Singular works correctly:

> ring R = 0, (t,u,v,w,x,y,z), lp;
> ideal I = t^2+u^2-1, v^2+w^2-1, x^2+y^2+z^2-1;
> qring Q = std(I);
> ideal J = u*v-x, u*w-y, t-z;
> reduce(t^2 - z^2, std(J));
0

Also, Singular returns the same Gröbner basis for J as Sage does:

> std(J);
_[1]=w2z2-w2+y2
_[2]=vy-wx
_[3]=vwz2-vw+xy
_[4]=vwx+w2y-y
_[5]=u-vx-wy
_[6]=t-z

sage: J.groebner_basis()
[t - z, u - v*x - w*y, v*w*x + w^2*y - y, v*w*z^2 - v*w + x*y, v*y - w*x, w^2*z^2 - w^2 + y^2]

So perhaps Gröbner bases in quotient rings can be meaningful, but the implementation of reduce in Sage does not handle this case correctly.

[mwageringel]

Description changed:

--- 
+++ 
@@ -23,7 +23,7 @@
    ...

-The expected behavior would be the same as lifting the ideal J to the cover ring R, perform reduction there (in terms of the ideal generated by I and the lifted generators of J) and map the result back to Q: +The expected behavior would be the same as lifting the ideal J to the cover ring R, perform reduction there (in terms of the ideal generated by I and the lifted generators of J) and map the result back to Q (by e.g. Thm. 9.19 in [https://doc.sagemath.org/html/en/reference/references/index.html#bw1993 [BW1993]]):

 sage: Q(Q.cover().inverse_image(J).reduce((t^2 - z^2).lift()))  # correct

[mwageringel]

Author: Markus Wageringel

[mwageringel]

Branch: u/gh-mwageringel/33217

[mwageringel]

Commit: 927f3ac

[mwageringel]

comment:5

The result of J.groebner_basis() in the quotient ring is indeed meaningful in the sense that, when combined with I.groebner_basis() (and only then) one obtains a Gröbner basis of J lifted to the cover ring R.

More precisely: If J0, I are ideals in R (such that J = (J0+I)/I) and if G0, H are Gröbner bases of J0+I, I, then in particular the union G0 ∪ H is a Gröbner basis of J0+I. Therefore, also the union G ∪ H is a (possibly non-reduced) Gröbner basis of J0+I, where G is defined as the reduction of G0 modulo I (as returned by J.groebner_basis()).

This is also what Singular does via kNF > kNF2 > initS.

I have fixed this for the reduce method of multivariate polynomial ideals in quotient rings. For the reduce method of generic quotient ring elements (which does not claim to return minimal results), I have just added a warning about this to the documentation.

---

New commits:

927f3ac

33217: fix reduction for ideals in quotient polynomial rings

[tscrim]

comment:7

I am not sure how I feel about testing if the ring is a quotient ring versus doing a proper subclass of the ideal for quotient rings. Granted, it is not too much technical debt as it is easy to separate later.

Are there any other methods that will need similar changes (such as groebner_basis())? I don't think so from a quick look, but perhaps you know better.

[kwankyu]

comment:8

Replying to @mwageringel:

More precisely: If J0, I are ideals in R (such that J = (J0+I)/I) and if G0, H are Gröbner bases of J0+I, I,

You mean J0 here, not J0+I. Right?

then in particular the union G0 ∪ H is a Gröbner basis of J0+I.

Then you say G0 ∪ H is a Groebner basis of J0 + I? This is not generally true.

[mwageringel]

comment:9

Replying to @tscrim:

I am not sure how I feel about testing if the ring is a quotient ring versus doing a proper subclass of the ideal for quotient rings. Granted, it is not too much technical debt as it is easy to separate later.

You are right. It is better to move this to a subclass. I will try to implement it. Something similar is done in #33237 right now, but probably there is no overlap with multivariate polynomial rings.

Are there any other methods that will need similar changes (such as groebner_basis())? I don't think so from a quick look, but perhaps you know better.

The groebner_basis method works for rings backed by Singular. The more obscure cases like rings over large finite fields or the polydict implementation result in an error:

sage: R.<T,U,V,W,X,Y,Z> = PolynomialRing(GF(2147483659), order='lex')
sage: Q.<t,u,v,w,x,y,z> = R.quotient(R.ideal([T^2+U^2-1, V^2+W^2-1, X^2+Y^2+Z^2-1]))
verbose 0 (3837: multi_polynomial_ideal.py, groebner_basis) Warning: falling back to very slow toy implementation.
sage: J = Q.ideal([u*v-x, u*w-y, t-z])
sage: J.groebner_basis()
...
AttributeError: 'QuotientRing_generic_with_category' object has no attribute 'monomial_pairwise_prime'

Though, this might be a problem of the quotient ring class rather than the ideal.

Replying to @kwankyu:

Replying to @mwageringel:

More precisely: If J0, I are ideals in R (such that J = (J0+I)/I) and if G0, H are Gröbner bases of J0+I, I,

You mean J0 here, not J0+I. Right?

No, J0+I is actually what I meant, since it is the preimage of J, when J0 is defined as the ideal generated by representatives of generators of J. Then G0 ∪ H is a Gröbner basis as it is a super set of the Gröbner basis G0 of J0+I.

J.groebner_basis() computes the Gröbner basis in terms of J0+I, not just J0 – otherwise it would indeed be a problem.

[kwankyu]

comment:11

Replying to @mwageringel:

More precisely: If J0, I are ideals in R (such that J = (J0+I)/I) and if G0, H are Gröbner bases of J0+I, I,

You mean J0 here, not J0+I. Right?

No, J0+I is actually what I meant, since it is the preimage of J, when J0 is defined as the ideal generated by representatives of generators of J. Then G0 ∪ H is a Gröbner basis as it is a super set of the Gröbner basis G0 of J0+I.

Okay. Now I understand. Thanks.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 927f3ac to e0d5533

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

96c242e	33217: fix reduction for ideals in quotient polynomial rings
e0d5533	33217: implement richcmp for ideals in polynomial quotient rings

[mwageringel]

comment:13

Replying to @tscrim:

Are there any other methods that will need similar changes (such as groebner_basis())? I don't think so from a quick look, but perhaps you know better.

I have now moved the implementation to a new subclass. I have also fixed the implementations of _contains_ and __richcmp__ which could otherwise return wrong results. These are the only methods I could find that can silently return incorrect results. Many other methods will raise an error though.

[tscrim]

comment:14

Thank you. I think you are correct in your assessment that the issue you bring up is with the quotient ring implementation.

One thing that should be reverted is the change to quotient_ring.py in the latest commits. That is needed for the modularization IIRC.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from e0d5533 to 0cc8b67

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

0cc8b67

33217: revert import for modularization

[mwageringel]

comment:16

Replying to @tscrim:

One thing that should be reverted is the change to quotient_ring.py in the latest commits. That is needed for the modularization IIRC.

Thanks for catching that. I have reverted the import to its previous format. Though, I have to admit I do not fully understand the reasoning behind it yet.

[tscrim]

comment:17

Replying to @mwageringel:

Replying to @tscrim:

One thing that should be reverted is the change to quotient_ring.py in the latest commits. That is needed for the modularization IIRC.

Thanks for catching that. I have reverted the import to its previous format. Though, I have to admit I do not fully understand the reasoning behind it yet.

My understanding is it is because someone (in the future I think, not yet) could have loaded/installed the quotient rings but not the polynomial rings. This removes it as a compile-time dependency IIRC.

Does anyone else have any other comments? I am ready to set this to a positive review (once the patchbot gets around to it).

[tscrim]

Reviewer: Travis Scrimshaw

[tscrim]

comment:18

The patchbot is green. If there are any other comments, feel free to revert the positive review.

[mwageringel]

comment:19

Thank you both for your comments.

[vbraun]

Changed branch from u/gh-mwageringel/33217 to 0cc8b67