Educational versions of Groebner basis algorithms¶

Following [BW1993], the original Buchberger algorithm (algorithm GROEBNER in [BW1993]) and an improved version of Buchberger’s algorithm (algorithm GROEBNERNEW2 in [BW1993]) are implemented.

No attempt was made to optimize either algorithm as the emphasis of these implementations is a clean and easy presentation. To compute a Groebner basis most efficiently in Sage, use the MPolynomialIdeal.groebner_basis() method on multivariate polynomial objects instead.

Note

The notion of ‘term’ and ‘monomial’ in [BW1993] is swapped from the notion of those words in Sage (or the other way around, however you prefer it). In Sage a term is a monomial multiplied by a coefficient, while in [BW1993] a monomial is a term multiplied by a coefficient. Also, what is called LM (the leading monomial) in Sage is called HT (the head term) in [BW1993].

EXAMPLES:

Consider Katsura-6 with respect to a degrevlex ordering.

Sage

sage: # needs sage.libs.singular sage.rings.finite_rings
sage: from sage.rings.polynomial.toy_buchberger import *
sage: P.<a,b,c,e,f,g,h,i,j,k> = PolynomialRing(GF(32003))
sage: I = sage.rings.ideal.Katsura(P, 6)
sage: g1 = buchberger(I)
sage: g2 = buchberger_improved(I)
sage: g3 = I.groebner_basis()

Python

>>> from sage.all import *
>>> # needs sage.libs.singular sage.rings.finite_rings
>>> from sage.rings.polynomial.toy_buchberger import *
>>> P = PolynomialRing(GF(Integer(32003)), names=('a', 'b', 'c', 'e', 'f', 'g', 'h', 'i', 'j', 'k',)); (a, b, c, e, f, g, h, i, j, k,) = P._first_ngens(10)
>>> I = sage.rings.ideal.Katsura(P, Integer(6))
>>> g1 = buchberger(I)
>>> g2 = buchberger_improved(I)
>>> g3 = I.groebner_basis()

Sage Live

# needs sage.libs.singular sage.rings.finite_rings
from sage.rings.polynomial.toy_buchberger import *
P.<a,b,c,e,f,g,h,i,j,k> = PolynomialRing(GF(32003))
I = sage.rings.ideal.Katsura(P, 6)
g1 = buchberger(I)
g2 = buchberger_improved(I)
g3 = I.groebner_basis()

All algorithms actually compute a Groebner basis:

Sage

sage: # needs sage.libs.singular sage.rings.finite_rings
sage: Ideal(g1).basis_is_groebner()
True
sage: Ideal(g2).basis_is_groebner()
True
sage: Ideal(g3).basis_is_groebner()
True

Python

>>> from sage.all import *
>>> # needs sage.libs.singular sage.rings.finite_rings
>>> Ideal(g1).basis_is_groebner()
True
>>> Ideal(g2).basis_is_groebner()
True
>>> Ideal(g3).basis_is_groebner()
True

Sage Live

# needs sage.libs.singular sage.rings.finite_rings
Ideal(g1).basis_is_groebner()
Ideal(g2).basis_is_groebner()
Ideal(g3).basis_is_groebner()

The results are correct:

Sage

sage: # needs sage.libs.singular sage.rings.finite_rings
sage: Ideal(g1) == Ideal(g2) == Ideal(g3)
True

Python

>>> from sage.all import *
>>> # needs sage.libs.singular sage.rings.finite_rings
>>> Ideal(g1) == Ideal(g2) == Ideal(g3)
True

Sage Live

# needs sage.libs.singular sage.rings.finite_rings
Ideal(g1) == Ideal(g2) == Ideal(g3)

If get_verbose() is \(\ge 1\), a protocol is provided:

Sage

sage: # needs sage.libs.singular sage.rings.finite_rings
sage: from sage.misc.verbose import set_verbose
sage: set_verbose(1)
sage: P.<a,b,c> = PolynomialRing(GF(127))
sage: I = sage.rings.ideal.Katsura(P)
// sage... ideal
sage: I
Ideal (a + 2*b + 2*c - 1, a^2 + 2*b^2 + 2*c^2 - a, 2*a*b + 2*b*c - b)
 of Multivariate Polynomial Ring in a, b, c over Finite Field of size 127
sage: buchberger(I)  # random
(a + 2*b + 2*c - 1, a^2 + 2*b^2 + 2*c^2 - a) => -2*b^2 - 6*b*c - 6*c^2 + b + 2*c
G: set([a + 2*b + 2*c - 1, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c])

(a^2 + 2*b^2 + 2*c^2 - a, a + 2*b + 2*c - 1) => 0
G: set([a + 2*b + 2*c - 1, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c])

(a + 2*b + 2*c - 1, 2*a*b + 2*b*c - b) => -5*b*c - 6*c^2 - 63*b + 2*c
G: set([a + 2*b + 2*c - 1, 2*a*b + 2*b*c - b, -5*b*c - 6*c^2 - 63*b + 2*c, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c])

(2*a*b + 2*b*c - b, a + 2*b + 2*c - 1) => 0
G: set([a + 2*b + 2*c - 1, 2*a*b + 2*b*c - b, -5*b*c - 6*c^2 - 63*b + 2*c, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c])

(2*a*b + 2*b*c - b, -5*b*c - 6*c^2 - 63*b + 2*c) => -22*c^3 + 24*c^2 - 60*b - 62*c
G: set([a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c])

(2*a*b + 2*b*c - b, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c) => 0
G: set([a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c])

(2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a) => 0
G: set([a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c])

(a + 2*b + 2*c - 1, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c) => 0
G: set([a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c])

(a^2 + 2*b^2 + 2*c^2 - a, 2*a*b + 2*b*c - b) => 0
G: set([a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c])

(-2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c) => 0
G: set([a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c])

(a + 2*b + 2*c - 1, -5*b*c - 6*c^2 - 63*b + 2*c) => 0
G: set([a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c])

(a^2 + 2*b^2 + 2*c^2 - a, -5*b*c - 6*c^2 - 63*b + 2*c) => 0
G: set([a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c])

(-5*b*c - 6*c^2 - 63*b + 2*c, -22*c^3 + 24*c^2 - 60*b - 62*c) => 0
G: set([a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c])

(a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c) => 0
G: set([a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c])

(a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c) => 0
G: set([a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c])

(-2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -22*c^3 + 24*c^2 - 60*b - 62*c) => 0
G: set([a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c])

(2*a*b + 2*b*c - b, -22*c^3 + 24*c^2 - 60*b - 62*c) => 0
G: set([a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c])

(a^2 + 2*b^2 + 2*c^2 - a, -22*c^3 + 24*c^2 - 60*b - 62*c) => 0
G: set([a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c])

15 reductions to zero.
[a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c]

Python

>>> from sage.all import *
>>> # needs sage.libs.singular sage.rings.finite_rings
>>> from sage.misc.verbose import set_verbose
>>> set_verbose(Integer(1))
>>> P = PolynomialRing(GF(Integer(127)), names=('a', 'b', 'c',)); (a, b, c,) = P._first_ngens(3)
>>> I = sage.rings.ideal.Katsura(P)
// sage... ideal
>>> I
Ideal (a + 2*b + 2*c - 1, a^2 + 2*b^2 + 2*c^2 - a, 2*a*b + 2*b*c - b)
 of Multivariate Polynomial Ring in a, b, c over Finite Field of size 127
>>> buchberger(I)  # random
(a + 2*b + 2*c - 1, a^2 + 2*b^2 + 2*c^2 - a) => -2*b^2 - 6*b*c - 6*c^2 + b + 2*c
G: set([a + 2*b + 2*c - 1, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c])
<BLANKLINE>
(a^2 + 2*b^2 + 2*c^2 - a, a + 2*b + 2*c - 1) => 0
G: set([a + 2*b + 2*c - 1, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c])
<BLANKLINE>
(a + 2*b + 2*c - 1, 2*a*b + 2*b*c - b) => -5*b*c - 6*c^2 - 63*b + 2*c
G: set([a + 2*b + 2*c - 1, 2*a*b + 2*b*c - b, -5*b*c - 6*c^2 - 63*b + 2*c, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c])
<BLANKLINE>
(2*a*b + 2*b*c - b, a + 2*b + 2*c - 1) => 0
G: set([a + 2*b + 2*c - 1, 2*a*b + 2*b*c - b, -5*b*c - 6*c^2 - 63*b + 2*c, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c])
<BLANKLINE>
(2*a*b + 2*b*c - b, -5*b*c - 6*c^2 - 63*b + 2*c) => -22*c^3 + 24*c^2 - 60*b - 62*c
G: set([a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c])
<BLANKLINE>
(2*a*b + 2*b*c - b, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c) => 0
G: set([a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c])
<BLANKLINE>
(2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a) => 0
G: set([a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c])
<BLANKLINE>
(a + 2*b + 2*c - 1, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c) => 0
G: set([a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c])
<BLANKLINE>
(a^2 + 2*b^2 + 2*c^2 - a, 2*a*b + 2*b*c - b) => 0
G: set([a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c])
<BLANKLINE>
(-2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c) => 0
G: set([a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c])
<BLANKLINE>
(a + 2*b + 2*c - 1, -5*b*c - 6*c^2 - 63*b + 2*c) => 0
G: set([a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c])
<BLANKLINE>
(a^2 + 2*b^2 + 2*c^2 - a, -5*b*c - 6*c^2 - 63*b + 2*c) => 0
G: set([a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c])
<BLANKLINE>
(-5*b*c - 6*c^2 - 63*b + 2*c, -22*c^3 + 24*c^2 - 60*b - 62*c) => 0
G: set([a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c])
<BLANKLINE>
(a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c) => 0
G: set([a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c])
<BLANKLINE>
(a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c) => 0
G: set([a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c])
<BLANKLINE>
(-2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -22*c^3 + 24*c^2 - 60*b - 62*c) => 0
G: set([a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c])
<BLANKLINE>
(2*a*b + 2*b*c - b, -22*c^3 + 24*c^2 - 60*b - 62*c) => 0
G: set([a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c])
<BLANKLINE>
(a^2 + 2*b^2 + 2*c^2 - a, -22*c^3 + 24*c^2 - 60*b - 62*c) => 0
G: set([a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c])
<BLANKLINE>
15 reductions to zero.
[a + 2*b + 2*c - 1, -22*c^3 + 24*c^2 - 60*b - 62*c, 2*a*b + 2*b*c - b, a^2 + 2*b^2 + 2*c^2 - a, -2*b^2 - 6*b*c - 6*c^2 + b + 2*c, -5*b*c - 6*c^2 - 63*b + 2*c]

Sage Live

# needs sage.libs.singular sage.rings.finite_rings
from sage.misc.verbose import set_verbose
set_verbose(1)
P.<a,b,c> = PolynomialRing(GF(127))
I = sage.rings.ideal.Katsura(P)
I
buchberger(I)  # random

The original Buchberger algorithm performs 15 useless reductions to zero for this example:

Sage

sage: # needs sage.libs.singular sage.rings.finite_rings
sage: gb = buchberger(I)
...
15 reductions to zero.

Python

>>> from sage.all import *
>>> # needs sage.libs.singular sage.rings.finite_rings
>>> gb = buchberger(I)
...
15 reductions to zero.

Sage Live

# needs sage.libs.singular sage.rings.finite_rings
gb = buchberger(I)

The ‘improved’ Buchberger algorithm in contrast only performs 1 reduction to zero:

Sage

sage: # needs sage.libs.singular sage.rings.finite_rings
sage: gb = buchberger_improved(I)
...
1 reductions to zero.
sage: sorted(gb)
[a + 2*b + 2*c - 1, b*c + 52*c^2 + 38*b + 25*c,
 b^2 - 26*c^2 - 51*b + 51*c, c^3 + 22*c^2 - 55*b + 49*c]

Python

>>> from sage.all import *
>>> # needs sage.libs.singular sage.rings.finite_rings
>>> gb = buchberger_improved(I)
...
1 reductions to zero.
>>> sorted(gb)
[a + 2*b + 2*c - 1, b*c + 52*c^2 + 38*b + 25*c,
 b^2 - 26*c^2 - 51*b + 51*c, c^3 + 22*c^2 - 55*b + 49*c]

Sage Live

# needs sage.libs.singular sage.rings.finite_rings
gb = buchberger_improved(I)
sorted(gb)

AUTHORS:

Martin Albrecht (2007-05-24): initial version
Marshall Hampton (2009-07-08): some doctest additions

sage.rings.polynomial.toy_buchberger.LCM(f, g)[source]¶

sage.rings.polynomial.toy_buchberger.LM(f)[source]¶

sage.rings.polynomial.toy_buchberger.LT(f)[source]¶

sage.rings.polynomial.toy_buchberger.buchberger(F)[source]¶

Compute a Groebner basis using the original version of Buchberger’s algorithm as presented in [BW1993], page 214.

INPUT:

F – an ideal in a multivariate polynomial ring

OUTPUT: a Groebner basis for F

Note

The verbosity of this function may be controlled with a set_verbose() call. Any value >=1 will result in this function printing intermediate bases.

EXAMPLES:

Sage

sage: from sage.rings.polynomial.toy_buchberger import buchberger
sage: R.<x,y,z> = PolynomialRing(QQ)
sage: I = R.ideal([x^2 - z - 1, z^2 - y - 1, x*y^2 - x - 1])
sage: set_verbose(0)
sage: gb = buchberger(I)                                                        # needs sage.libs.singular
sage: gb.is_groebner()                                                          # needs sage.libs.singular
True
sage: gb.ideal() == I                                                           # needs sage.libs.singular
True

Python

>>> from sage.all import *
>>> from sage.rings.polynomial.toy_buchberger import buchberger
>>> R = PolynomialRing(QQ, names=('x', 'y', 'z',)); (x, y, z,) = R._first_ngens(3)
>>> I = R.ideal([x**Integer(2) - z - Integer(1), z**Integer(2) - y - Integer(1), x*y**Integer(2) - x - Integer(1)])
>>> set_verbose(Integer(0))
>>> gb = buchberger(I)                                                        # needs sage.libs.singular
>>> gb.is_groebner()                                                          # needs sage.libs.singular
True
>>> gb.ideal() == I                                                           # needs sage.libs.singular
True

Sage Live

from sage.rings.polynomial.toy_buchberger import buchberger
R.<x,y,z> = PolynomialRing(QQ)
I = R.ideal([x^2 - z - 1, z^2 - y - 1, x*y^2 - x - 1])
set_verbose(0)
gb = buchberger(I)                                                        # needs sage.libs.singular
gb.is_groebner()                                                          # needs sage.libs.singular
gb.ideal() == I                                                           # needs sage.libs.singular

sage.rings.polynomial.toy_buchberger.buchberger_improved(F)[source]¶

Compute a Groebner basis using an improved version of Buchberger’s algorithm as presented in [BW1993], page 232.

This variant uses the Gebauer-Moeller Installation to apply Buchberger’s first and second criterion to avoid useless pairs.

INPUT:

F – an ideal in a multivariate polynomial ring

OUTPUT: a Groebner basis for F

Note

The verbosity of this function may be controlled with a set_verbose() call. Any value >=1 will result in this function printing intermediate Groebner bases.

EXAMPLES:

Sage

sage: from sage.rings.polynomial.toy_buchberger import buchberger_improved
sage: R.<x,y,z> = PolynomialRing(QQ)
sage: set_verbose(0)
sage: sorted(buchberger_improved(R.ideal([x^4 - y - z, x*y*z - 1])))            # needs sage.libs.singular
[x*y*z - 1, x^3 - y^2*z - y*z^2, y^3*z^2 + y^2*z^3 - x^2]

Python

>>> from sage.all import *
>>> from sage.rings.polynomial.toy_buchberger import buchberger_improved
>>> R = PolynomialRing(QQ, names=('x', 'y', 'z',)); (x, y, z,) = R._first_ngens(3)
>>> set_verbose(Integer(0))
>>> sorted(buchberger_improved(R.ideal([x**Integer(4) - y - z, x*y*z - Integer(1)])))            # needs sage.libs.singular
[x*y*z - 1, x^3 - y^2*z - y*z^2, y^3*z^2 + y^2*z^3 - x^2]

Sage Live

from sage.rings.polynomial.toy_buchberger import buchberger_improved
R.<x,y,z> = PolynomialRing(QQ)
set_verbose(0)
sorted(buchberger_improved(R.ideal([x^4 - y - z, x*y*z - 1])))            # needs sage.libs.singular

sage.rings.polynomial.toy_buchberger.inter_reduction(Q)[source]¶

Compute inter-reduced polynomials from a set of polynomials.

INPUT:

Q – set of polynomials

OUTPUT:

if Q is the set \(f_1, ..., f_n\), this method returns \(g_1, ..., g_s\) such that:

\((f_1,...,f_n) = (g_1,...,g_s)\)
\(LM(g_i) \neq LM(g_j)\) for all \(i \neq j\)
\(LM(g_i)\) does not divide \(m\) for all monomials \(m\) of \(\{g_1,...,g_{i-1}, g_{i+1},...,g_s\}\)
\(LC(g_i) = 1\) for all \(i\).

EXAMPLES:

Sage

sage: from sage.rings.polynomial.toy_buchberger import inter_reduction
sage: inter_reduction(set())
set()

Python

>>> from sage.all import *
>>> from sage.rings.polynomial.toy_buchberger import inter_reduction
>>> inter_reduction(set())
set()

Sage Live

from sage.rings.polynomial.toy_buchberger import inter_reduction
inter_reduction(set())

Sage

sage: P.<x,y> = QQ[]
sage: reduced = inter_reduction(set([x^2 - 5*y^2, x^3]))                        # needs sage.libs.singular
sage: reduced == set([x*y^2, x^2 - 5*y^2])                                      # needs sage.libs.singular
True
sage: reduced == inter_reduction(set([2*(x^2 - 5*y^2), x^3]))                   # needs sage.libs.singular
True

Python

>>> from sage.all import *
>>> P = QQ['x, y']; (x, y,) = P._first_ngens(2)
>>> reduced = inter_reduction(set([x**Integer(2) - Integer(5)*y**Integer(2), x**Integer(3)]))                        # needs sage.libs.singular
>>> reduced == set([x*y**Integer(2), x**Integer(2) - Integer(5)*y**Integer(2)])                                      # needs sage.libs.singular
True
>>> reduced == inter_reduction(set([Integer(2)*(x**Integer(2) - Integer(5)*y**Integer(2)), x**Integer(3)]))                   # needs sage.libs.singular
True

Sage Live

P.<x,y> = QQ[]
reduced = inter_reduction(set([x^2 - 5*y^2, x^3]))                        # needs sage.libs.singular
reduced == set([x*y^2, x^2 - 5*y^2])                                      # needs sage.libs.singular
reduced == inter_reduction(set([2*(x^2 - 5*y^2), x^3]))                   # needs sage.libs.singular

Python

>>> from sage.all import *
>>> P = QQ['x, y']; (x, y,) = P._first_ngens(2)
>>> reduced = inter_reduction(set([x**Integer(2) - Integer(5)*y**Integer(2), x**Integer(3)]))                        # needs sage.libs.singular
>>> reduced == set([x*y**Integer(2), x**Integer(2) - Integer(5)*y**Integer(2)])                                      # needs sage.libs.singular
True
>>> reduced == inter_reduction(set([Integer(2)*(x**Integer(2) - Integer(5)*y**Integer(2)), x**Integer(3)]))                   # needs sage.libs.singular
True

Sage Live

P.<x,y> = QQ[]
reduced = inter_reduction(set([x^2 - 5*y^2, x^3]))                        # needs sage.libs.singular
reduced == set([x*y^2, x^2 - 5*y^2])                                      # needs sage.libs.singular
reduced == inter_reduction(set([2*(x^2 - 5*y^2), x^3]))                   # needs sage.libs.singular

sage.rings.polynomial.toy_buchberger.select(P)[source]¶

Select a polynomial using the normal selection strategy.

INPUT:

P – list of critical pairs

OUTPUT: an element of P

EXAMPLES:

Sage

sage: from sage.rings.polynomial.toy_buchberger import select
sage: R.<x,y,z> = PolynomialRing(QQ, order='lex')
sage: ps = [x^3 - z - 1, z^3 - y - 1, x^5 - y - 2]
sage: pairs = [[ps[i], ps[j]] for i in range(3) for j in range(i + 1, 3)]
sage: select(pairs)
[x^3 - z - 1, -y + z^3 - 1]

Python

>>> from sage.all import *
>>> from sage.rings.polynomial.toy_buchberger import select
>>> R = PolynomialRing(QQ, order='lex', names=('x', 'y', 'z',)); (x, y, z,) = R._first_ngens(3)
>>> ps = [x**Integer(3) - z - Integer(1), z**Integer(3) - y - Integer(1), x**Integer(5) - y - Integer(2)]
>>> pairs = [[ps[i], ps[j]] for i in range(Integer(3)) for j in range(i + Integer(1), Integer(3))]
>>> select(pairs)
[x^3 - z - 1, -y + z^3 - 1]

Sage Live

from sage.rings.polynomial.toy_buchberger import select
R.<x,y,z> = PolynomialRing(QQ, order='lex')
ps = [x^3 - z - 1, z^3 - y - 1, x^5 - y - 2]
pairs = [[ps[i], ps[j]] for i in range(3) for j in range(i + 1, 3)]
select(pairs)

sage.rings.polynomial.toy_buchberger.spol(f, g)[source]¶

Compute the S-polynomial of f and g.

INPUT:

f, g – polynomials

OUTPUT: the S-polynomial of f and g

EXAMPLES:

Sage

sage: R.<x,y,z> = PolynomialRing(QQ)
sage: from sage.rings.polynomial.toy_buchberger import spol
sage: spol(x^2 - z - 1, z^2 - y - 1)
x^2*y - z^3 + x^2 - z^2

Python

>>> from sage.all import *
>>> R = PolynomialRing(QQ, names=('x', 'y', 'z',)); (x, y, z,) = R._first_ngens(3)
>>> from sage.rings.polynomial.toy_buchberger import spol
>>> spol(x**Integer(2) - z - Integer(1), z**Integer(2) - y - Integer(1))
x^2*y - z^3 + x^2 - z^2

Sage Live

R.<x,y,z> = PolynomialRing(QQ)
from sage.rings.polynomial.toy_buchberger import spol
spol(x^2 - z - 1, z^2 - y - 1)

sage.rings.polynomial.toy_buchberger.update(G, B, h)[source]¶

Update G using the set of critical pairs B and the polynomial h as presented in [BW1993], page 230. For this, Buchberger’s first and second criterion are tested.

This function implements the Gebauer-Moeller Installation.

INPUT:

G – an intermediate Groebner basis
B – set of critical pairs
h – a polynomial

OUTPUT: a tuple of

an intermediate Groebner basis
a set of critical pairs

EXAMPLES:

Sage

sage: from sage.rings.polynomial.toy_buchberger import update
sage: R.<x,y,z> = PolynomialRing(QQ)
sage: set_verbose(0)
sage: update(set(), set(), x*y*z)
({x*y*z}, set())
sage: G, B = update(set(), set(), x*y*z - 1)
sage: G, B = update(G, B, x*y^2 - 1)
sage: G, B
({x*y*z - 1, x*y^2 - 1}, {(x*y^2 - 1, x*y*z - 1)})

Python

>>> from sage.all import *
>>> from sage.rings.polynomial.toy_buchberger import update
>>> R = PolynomialRing(QQ, names=('x', 'y', 'z',)); (x, y, z,) = R._first_ngens(3)
>>> set_verbose(Integer(0))
>>> update(set(), set(), x*y*z)
({x*y*z}, set())
>>> G, B = update(set(), set(), x*y*z - Integer(1))
>>> G, B = update(G, B, x*y**Integer(2) - Integer(1))
>>> G, B
({x*y*z - 1, x*y^2 - 1}, {(x*y^2 - 1, x*y*z - 1)})

Sage Live

from sage.rings.polynomial.toy_buchberger import update
R.<x,y,z> = PolynomialRing(QQ)
set_verbose(0)
update(set(), set(), x*y*z)
G, B = update(set(), set(), x*y*z - 1)
G, B = update(G, B, x*y^2 - 1)
G, B