Sage: Ticket #12839: reduced Groebner basis not unique
https://trac.sagemath.org/ticket/12839
<p>
Using sage-4.8
</p>
<pre class="wiki">sage: R.<x,y> = PolynomialRing(ZZ)
sage: I = R*[x^2-y, 2*y]
sage: J = R*[x^2+y, 2*y]
</pre><p>
<code>I</code> and <code>J</code> are visibly the same ideal, but Sage finds different reduced Groebner bases:
</p>
<pre class="wiki">sage: I.groebner_basis()
[x^2 - y, 2*y]
sage: J.groebner_basis()
[x^2 + y, 2*y]
sage: I == J // should say True
False
</pre>en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/12839
Trac 1.1.6john_perryFri, 25 May 2012 19:06:30 GMT
https://trac.sagemath.org/ticket/12839#comment:1
https://trac.sagemath.org/ticket/12839#comment:1
<p>
Correct me if I am wrong, but you cannot have a reduced Groebner basis over a ring that is not a field. Besides, the ideals are <em>not</em> the same, even if their varieties are.
</p>
<p>
Singular seems to feel this way:
</p>
<ul><li>Singular is computing the basis.
</li><li>According to Remark 1.6.14 in <em>A <strong>Singular</strong> Introduction to Commutative Algebra</em>, if you want to compute a <em>standard basis over a ring</em> which is merely Noetherian (not necessarily a field, as in Definition 1.6.1), you need to have agreement of leading <em>terms</em> (which includes coefficients), not leading <em>monomials</em>.
</li><li>See this answer in <a class="ext-link" href="http://www.singular.uni-kl.de/forum/viewtopic.php?f=10&t=1750&p=2349&hilit=std+integer#p2349"><span class="icon"></span>the Singular forums</a>.
</li></ul><p>
Macaulay also feels this way:
</p>
<ul><li>I installed Macaulay2, computed groebner bases for both I and J, and got the same thing singular computes.
</li><li>Macaulay2's <a class="ext-link" href="http://www.math.uiuc.edu/Macaulay2/doc/Macaulay2-1.4/share/doc/Macaulay2/Macaulay2Doc/html/_simple_sp__Groebner_spbasis_spcomputations_spover_spvarious_springs.html"><span class="icon"></span>webpage</a> implies the same.
</li></ul><p>
Unless I'm wrong, this is not a bug.
</p>
<p>
<em>Edit:</em> I had ring and field switched in the first sentence.
</p>
Ticketjohn_perryFri, 25 May 2012 19:18:39 GMT
https://trac.sagemath.org/ticket/12839#comment:2
https://trac.sagemath.org/ticket/12839#comment:2
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12839#comment:1" title="Comment 1">john_perry</a>:
</p>
<blockquote class="citation">
<p>
Besides, the ideals are <em>not</em> the same, even if their varieties are.
</p>
</blockquote>
<p>
This was a dumb thing to say, & I had doubts almost immediately after hitting the Submit button. In fact, Macaulay2 recognizes I==J, even though it computes different gb's. Singular does not recognize this.
</p>
Ticketjohn_perryFri, 25 May 2012 19:48:07 GMT
https://trac.sagemath.org/ticket/12839#comment:3
https://trac.sagemath.org/ticket/12839#comment:3
<p>
I think I see a way to get this to work.
</p>
<p>
The first thing that can be tried is whether the groebner bases are equal, which is what we are doing now. If that succeeds, then great.
</p>
<p>
Otherwise, we can compare by reducing the elements of one groebner basis over the other's groebner basis. If all reductions give us 0, then we return true. Otherwise, we return false.
</p>
<p>
I think this is related to <a class="closed ticket" href="https://trac.sagemath.org/ticket/12802" title="enhancement: test containment of ideals in class MPolynomialIdeal (closed: fixed)">#12802</a>, and this trick should fix both of them: <code>__lt__</code> can test if the first is contained in the second, <code>__gt__</code> can check if the second is contained in the first, and <code>__eq__</code> checks if both are satisfied.
</p>
<p>
This would be easy to implement, but is the algorithm I'm outlining correct?
</p>
Ticketjohn_perryFri, 25 May 2012 23:25:41 GMTstatus changed
https://trac.sagemath.org/ticket/12839#comment:4
https://trac.sagemath.org/ticket/12839#comment:4
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_info</em>
</li>
</ul>
<p>
Hello
</p>
<p>
I'm still of the opinion that what I wrote about reduced Groebner bases in integer rings is correct, given the behavior of Singular and Macaulay2.
</p>
<p>
That said, the incorrect conclusion that <code>I != J</code> is easily fixed, using the algorithm I outlined. I have uploaded a patch to <a class="closed ticket" href="https://trac.sagemath.org/ticket/12802" title="enhancement: test containment of ideals in class MPolynomialIdeal (closed: fixed)">#12802</a> that does precisely this.
</p>
<p>
Assuming that what I've done there is correct, is there a way to mark this patch as a duplicate, or something similar?
</p>
Ticketjohn_perryFri, 25 May 2012 23:25:56 GMTkeywords set
https://trac.sagemath.org/ticket/12839#comment:5
https://trac.sagemath.org/ticket/12839#comment:5
<ul>
<li><strong>keywords</strong>
<em>sd40.5</em> <em>groebner</em> <em>bases</em> <em>ideals</em> added
</li>
</ul>
TicketwasSat, 26 May 2012 02:29:57 GMT
https://trac.sagemath.org/ticket/12839#comment:6
https://trac.sagemath.org/ticket/12839#comment:6
<p>
john_perry: to mark this as a dup:
</p>
<ol><li>Set yourself to reviewer
</li><li>give it positive review
</li><li>change the milestone to sage-duplicate
</li></ol><p>
William
</p>
Ticketjohn_perrySat, 26 May 2012 05:39:10 GMTmilestone changed; reviewer set
https://trac.sagemath.org/ticket/12839#comment:7
https://trac.sagemath.org/ticket/12839#comment:7
<ul>
<li><strong>reviewer</strong>
set to <em>john_perry</em>
</li>
<li><strong>milestone</strong>
changed from <em>sage-5.1</em> to <em>sage-duplicate/invalid/wontfix</em>
</li>
</ul>
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/12839#comment:6" title="Comment 6">was</a>:
</p>
<blockquote class="citation">
<p>
john_perry: to mark this as a dup:
</p>
</blockquote>
<p>
Thx. Since testing equality of ideals is equivalent to testing containment both ways, that's what I'll do.
</p>
Ticketjohn_perrySat, 26 May 2012 05:39:29 GMTstatus changed
https://trac.sagemath.org/ticket/12839#comment:8
https://trac.sagemath.org/ticket/12839#comment:8
<ul>
<li><strong>status</strong>
changed from <em>needs_info</em> to <em>needs_review</em>
</li>
</ul>
Ticketjohn_perrySat, 26 May 2012 05:39:52 GMTstatus changed
https://trac.sagemath.org/ticket/12839#comment:9
https://trac.sagemath.org/ticket/12839#comment:9
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
</ul>
TicketjdemeyerTue, 19 Jun 2012 13:27:57 GMTstatus changed; dependencies, resolution set
https://trac.sagemath.org/ticket/12839#comment:10
https://trac.sagemath.org/ticket/12839#comment:10
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>dependencies</strong>
set to <em>#12802</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
</ul>
TicketjdemeyerTue, 19 Jun 2012 13:28:04 GMTresolution changed
https://trac.sagemath.org/ticket/12839#comment:11
https://trac.sagemath.org/ticket/12839#comment:11
<ul>
<li><strong>resolution</strong>
changed from <em>fixed</em> to <em>duplicate</em>
</li>
</ul>
TicketjdemeyerWed, 20 Jun 2012 13:30:41 GMTreviewer changed
https://trac.sagemath.org/ticket/12839#comment:12
https://trac.sagemath.org/ticket/12839#comment:12
<ul>
<li><strong>reviewer</strong>
changed from <em>john_perry</em> to <em>John Perry</em>
</li>
</ul>
Ticket