Opened 11 years ago

Closed 10 years ago

Last modified 10 years ago

#12839 closed defect (duplicate)

reduced Groebner basis not unique

Reported by: Mariah Lennox Owned by: Martin Albrecht
Priority: major Milestone: sage-duplicate/invalid/wontfix
Component: commutative algebra Keywords: sd40.5, groebner bases, ideals
Cc: Merged in:
Authors: Reviewers: John Perry
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: #12802 Stopgaps:

Status badges

Description

Using sage-4.8

sage: R.<x,y> = PolynomialRing(ZZ)
sage: I = R*[x^2-y, 2*y]
sage: J = R*[x^2+y, 2*y]

I and J are visibly the same ideal, but Sage finds different reduced Groebner bases:

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

Change History (12)

comment:1 Changed 11 years ago by John Perry

Correct me if I am wrong, but you cannot have a reduced Groebner basis over a field that is not a ring. Besides, the ideals are not the same, even if their varieties are.

Singular seems to feel this way:

  • Singular is computing the basis.
  • According to Remark 1.6.14 in A Singular Introduction to Commutative Algebra, if you want to compute a standard basis over a ring which is merely Noetherian (not necessarily a field, as in Definition 1.6.1), you need to have agreement of leading terms (which includes coefficients), not leading monomials.
  • See this answer in the Singular forums.

Macaulay also feels this way:

  • I installed Macaulay2, computed groebner bases for both I and J, and got the same thing singular computes.
  • Macaulay2's webpage implies the same.

Unless I'm wrong, this is not a bug.

Version 0, edited 11 years ago by John Perry (next)

comment:2 in reply to:  1 Changed 11 years ago by John Perry

Replying to john_perry:

Besides, the ideals are not the same, even if their varieties are.

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.

comment:3 Changed 11 years ago by John Perry

I think I see a way to get this to work.

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.

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.

I think this is related to #12802, and this trick should fix both of them: __lt__ can test if the first is contained in the second, __gt__ can check if the second is contained in the first, and __eq__ checks if both are satisfied.

This would be easy to implement, but is the algorithm I'm outlining correct?

comment:4 Changed 11 years ago by John Perry

Status: newneeds_info

Hello

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.

That said, the incorrect conclusion that I != J is easily fixed, using the algorithm I outlined. I have uploaded a patch to #12802 that does precisely this.

Assuming that what I've done there is correct, is there a way to mark this patch as a duplicate, or something similar?

comment:5 Changed 11 years ago by John Perry

Keywords: sd40.5 groebner bases ideals added

comment:6 Changed 11 years ago by William Stein

john_perry: to mark this as a dup:

  1. Set yourself to reviewer
  2. give it positive review
  3. change the milestone to sage-duplicate

William

comment:7 in reply to:  6 Changed 11 years ago by John Perry

Milestone: sage-5.1sage-duplicate/invalid/wontfix
Reviewers: john_perry

Replying to was:

john_perry: to mark this as a dup:

Thx. Since testing equality of ideals is equivalent to testing containment both ways, that's what I'll do.

comment:8 Changed 11 years ago by John Perry

Status: needs_infoneeds_review

comment:9 Changed 11 years ago by John Perry

Status: needs_reviewpositive_review

comment:10 Changed 10 years ago by Jeroen Demeyer

Dependencies: #12802
Resolution: fixed
Status: positive_reviewclosed

comment:11 Changed 10 years ago by Jeroen Demeyer

Resolution: fixedduplicate

comment:12 Changed 10 years ago by Jeroen Demeyer

Reviewers: john_perryJohn Perry
Note: See TracTickets for help on using tickets.