21.1 Groebner Fans

Module: sage.rings.groebner_fan

SAGE provides much of the functionality of gfan, which is a software package whose main function is to enumerate all reduced Gröbner bases of a polynomial ideal. The reduced Gröbner bases yield the maximal cones in the Gröbner fan of the ideal. Several subcomputations can be issued and additional tools are included. Among these the highlights are:

- Anders Nedergaard Jensen: Wrote the gfan C++ program, which implements algorithms many of which were invented by Jensen, Komei Fukuda, and Rekha Thomas. All the underlying hard work of the Groebner fans functionality of SAGE depends on this C++ program.

- William Stein (2006-04-20): Wrote first version of the SAGE code for working with Groebner fans.

- Tristram Bogart (bogart@math): the design of the SAGE interface to gfan is joint work with Tristram Bogart, who also supplied numerous examples.

Class: GroebnerFan

class GroebnerFan
GroebnerFan( self, I, [is_groebner_basis=False], [symmetry=None], [verbose=False])

INPUT:
    I -- ideal in a multivariate polynomial ring
    is_groebner_basis -- bool (default False).  if True, then
                 I.gens() must be a Groebner basis with
                 respect to the standard degree lexicographic
                 term order.
    symmetry -- default: None; if not None, describes symmetries
                of the ideal
    verbose  -- default: False; if True, printout useful info
                during computations

sage: R.<x,y,z> = PolynomialRing(QQ,3)
sage: I = R.ideal([x^2*y - z, y^2*z - x, z^2*x - y])
sage: G = I.groebner_fan(); G
Groebner fan of the ideal:
Ideal (-1*z + x^2*y, -1*y + x*z^2, y^2*z - x) of Polynomial Ring in x, y, z
over Rational Field

Functions: buchberger,$  $ characteristic,$  $ dimension_of_homogeneity_space,$  $ fvector,$  $ gfan,$  $ homogeneity_space,$  $ ideal,$  $ interactive,$  $ maximal_total_degree_of_a_groebner_basis,$  $ minimal_total_degree_of_a_groebner_basis,$  $ number_of_reduced_groebner_bases,$  $ number_of_variables,$  $ reduced_groebner_bases,$  $ render,$  $ ring,$  $ tropical_basis,$  $ universal_groebner_basis

buchberger( self)

Computes and returns a lexicographic reduced Groebner basis for the ideal.

sage: R.<x,y,z> = PolynomialRing(QQ,3); G = R.ideal([x - z^3, y^2 - x + x^2 - z^3*x]).groebner_fan()
sage: G.buchberger ()
[-1*z^3 + y^2, -1*z^3 + x]

characteristic( self)

Return the characteristic of the base ring.

dimension_of_homogeneity_space( self)

Return the dimension of the homogeneity space.

sage: R.<x,y> = PolynomialRing(QQ,2); G = R.ideal([y^3 - x^2, y^2 - 13*x]).groebner_fan()
sage: G.dimension_of_homogeneity_space()
0

fvector( self)

Return the f-vector for the Grobner fan.

sage: R.<x,y> = PolynomialRing(QQ,2); G = R.ideal([y^3 - x^2, y^2 - 13*x]).groebner_fan()
sage: G.fvector ()
(1, 4, 3)

homogeneity_space( self)

Return the homogeneity space of a the list of polynomials that define this Groebner fan.

sage: R.<x,y> = PolynomialRing(QQ,2); G = R.ideal([y^3 - x^2, y^2 - 13*x]).groebner_fan()
sage: H = G.homogeneity_space()

ideal( self)

Return the ideal the was used to define this Groebner fan.

interactive( self)

See the documentation for self[0].interative()

maximal_total_degree_of_a_groebner_basis( self)

Return the maximal total degree of any Groebner basis.

sage: R.<x,y> = PolynomialRing(QQ,2); G = R.ideal([y^3 - x^2, y^2 - 13*x]).groebner_fan()
sage: G.maximal_total_degree_of_a_groebner_basis()
4

minimal_total_degree_of_a_groebner_basis( self)

Return the minimal total degree of any Groebner basis.

sage: R.<x,y> = PolynomialRing(QQ,2); G = R.ideal([y^3 - x^2, y^2 - 13*x]).groebner_fan()
sage: G.minimal_total_degree_of_a_groebner_basis()
2

number_of_reduced_groebner_bases( self)

Return the number of reduced Groebner bases.

sage: R.<x,y> = PolynomialRing(QQ,2); G = R.ideal([y^3 - x^2, y^2 - 13*x]).groebner_fan()
sage: G.number_of_reduced_groebner_bases()
3

number_of_variables( self)

Return the number of variables.

sage: R.<x,y> = PolynomialRing(QQ,2); G = R.ideal([y^3 - x^2, y^2 - 13*x]).groebner_fan()
sage: G.number_of_variables()
2

sage: x = PolynomialRing(QQ,10).gens(); G = ideal([x[0]-x[9], sum(x)]).groebner_fan()
sage: G.number_of_variables()
10

reduced_groebner_bases( self)

sage: R.<x,y,z> = PolynomialRing(QQ,3); G = R.ideal([x^2*y - z, y^2*z - x, z^2*x - y]).groebner_fan()
sage: X = G.reduced_groebner_bases()
sage: len(X)
33
sage: X[0]
[-1*z + z^15, -1*z^11 + y, -1*z^9 + x]
sage: X[0].ideal()
Ideal (-1*z + z^15, -1*z^9 + x, -1*z^11 + y) of Polynomial Ring in x, y, z
over Rational Field
sage: X[:5]
[[-1*z + z^15, -1*z^11 + y, -1*z^9 + x],
[z^11 - y, -1*z + y*z^4, -1*z^8 + y^2, -1*z^9 + x],
[z^8 - y^2, -1*z + y*z^4, -1*y + y^2*z^3, -1*z^5 + y^3, -1*y^2*z + x],
[z^5 - y^3, -1*z + y*z^4, -1*y + y^2*z^3, -1*z^2 + y^4, -1*y^2*z + x],
[z^2 - y^4, -1*y + y^6*z, -1*z + y^9, -1*y^2*z + x]]

render( self, file, [larger=False], [shift=0], [show=False])

Render a Groebner fan as an xfig file.

More precisely, the output is a drawing of the Groebner fan intersected with a traingle. The corners of the triangle are (1,0,0) to the right, (0,1,0) to the left and (0,0,1) at the top. If there are more than three variables in the ring we extend these coordinates with zeros.

INPUT:
    shift -- shift the positions of the variables in
             the drawing.  For example, with shift=1,
             the corners will be b (right), c (left),
             and d (top).  The shifting is done modulo
             the number of variables in the polynomial
             ring.   The default is 0.
    larger -- bool (default: False); if True, make
             the triangle larger so that the shape of
             of the Groebner region appears.
    show  -- bool (default: True); if True, pop up
             xfig displaying the resulting file (this
             requires xfig).

sage: R.<x,y> = PolynomialRing(QQ,2); G = R.ideal([y^3 - x^2, y^2 - 13*x]).groebner_fan()
sage: G.render('a.fig')

sage: R.<x,y,z> = PolynomialRing(QQ,3); G = R.ideal([x^2*y - z, y^2*z - x, z^2*x - y]).groebner_fan()
sage: G.render('a.fig', show=True, larger=True)

ring( self)

Return the multivariate polynomial ring.

tropical_basis( self, [check=True])

Return a tropical basis for the tropical curve associated to this ideal.

INPUT:
    check -- bool (default: True); if True raises a ValueError
             exception if this ideal does not define a tropical curve
             (i.e., the condition that R/I has dimension equal
             to 1 + the dimension of the homogeneity space is
             not satisfied).

sage: R.<x,y,z> = PolynomialRing(QQ, 3); G = R.ideal([y^3-3*x^2, z^3-x-y-2*y^3+2*x^2]).groebner_fan()
sage: G
Groebner fan of the ideal:
Ideal (y^3 - 3*x^2, z^3 - y - 2*y^3 - x + 2*x^2) of Polynomial Ring in x,
y, z over Rational Field
sage: G.tropical_basis ()
[z^3 - y - x - 4*x^2, y^3 - 3*x^2]

Special Functions: __getitem__,$  $ __iter__,$  $ _gfan_ideal,$  $ _gfan_maps,$  $ _gfan_mod,$  $ _gfan_reduced_groebner_bases,$  $ _gfan_stats,$  $ _gfan_vardict,$  $ _repr_

_gfan_ideal( self)

Return the ideal in gfan's notation (with variables mapped to a,b,c, etc.)

sage: R.<x,y,z> = PolynomialRing(QQ,3); G = R.ideal([x^2*y - z, y^2*z - x, z^2*x - y]).groebner_fan()
sage: G._gfan_ideal()
'{-1*c + a^2*b, -1*b + a*c^2, b^2*c - a}'

_gfan_maps( self)

INPUT:
    none
OUTPUT:
    -- map from SAGE ring to gfan ring
    -- map from gfan ring to SAGE ring

sage: R.<x,y,z> = PolynomialRing(QQ,3); G = R.ideal([x^2*y - z, y^2*z - x, z^2*x - y]).groebner_fan()
sage: G._gfan_maps()
(Ring morphism:
  From: Polynomial Ring in x, y, z over Rational Field
  To:   Polynomial Ring in a, b, c over Rational Field
  Defn: x |--> a
        y |--> b
        z |--> c,
 Ring morphism:
  From: Polynomial Ring in a, b, c over Rational Field
  To:   Polynomial Ring in x, y, z over Rational Field
  Defn: a |--> x
        b |--> y
        c |--> z)

_gfan_mod( self)

Return the extra options to the gfan command that are used by this object to account for working modulo a prime or in the presence of extra symmetries.

_gfan_stats( self)

Return various statistics about this Groebner fan.

sage: R.<x,y> = PolynomialRing(QQ,2); G = R.ideal([y^3 - x^2, y^2 - 13*x]).groebner_fan()
sage: G._gfan_stats()
{'Number of reduced Groebner bases': 3, 'Maximal total degree of a Groebner
basis': 4, 'Dimension of homogeneity space': 0, 'Number of variables': 2,
'Minimal total degree of a Groebner basis': 2}

Class: ReducedGroebnerBasis

class ReducedGroebnerBasis
ReducedGroebnerBasis( self, groebner_fan, gens, gfan_gens)

Functions: groebner_cone,$  $ ideal,$  $ interactive,$  $ weight_vector

groebner_cone( self, [restrict=False])

Return defining inequalities for the full-dimensional Groebner cone associated to this marked minimal reduced Groebner basis.

INPUT:
    restrict -- bool (default: False); if True, add an inequality for
                each coordinate, so that the cone is restricted to
                the positive orthant.

OUTPUT:
    tuple of integer vectors

sage: R.<x,y> = PolynomialRing(QQ,2); G = R.ideal([y^3 - x^2, y^2 - 13*x]).groebner_fan()
sage: G[1].groebner_cone()
((-1, 2), (1, -1))
sage: [g.groebner_cone() for g in G]
[((0, 1), (1, -2)), ((-1, 2), (1, -1)), ((-1, 2), (-1, 1), (1, 0))]
sage: G[1].groebner_cone(restrict=True)
((-1, 2), (1, -1), (1, 0), (0, 1))

ideal( self)

Return the ideal generated by this basis.

sage: R.<x,y,z> = PolynomialRing(QQ,3); G = R.ideal([x - z^3, y^2 - 13*x]).groebner_fan()
sage: G[0].ideal()
Ideal (-13*z^3 + y^2, -1*z^3 + x) of Polynomial Ring in x, y, z over
Rational Field

interactive( self, [latex=False], [flippable=False], [wall=False], [inequalities=False], [weight=False])

Do an interactive walk of the Groebner fan starting at this reduced Groebner basis.

sage: R.<x,y> = PolynomialRing(QQ,2); G = R.ideal([y^3 - x^2, y^2 - 13*x]).groebner_fan()
sage: G[0].interactive()
Initializing gfan interactive mode
*********************************************
*     Press control-C to return to SAGE     *
*********************************************
....

weight_vector( self)

Return the weight vector of this reduced Groebner basis.

sage: R.<x,y,z> = PolynomialRing(QQ,3); G = R.ideal([x - z^3, y^2 - 3*x]).groebner_fan()
sage: [g.weight_vector() for g in G]
[(2, 1, 0), (0, -1, 0), (-1, 0, 0)]

sage: R.<x,y,z> = PolynomialRing(GF(3),3); G = R.ideal([x - z^3, y^2 - 3*x]).groebner_fan()
sage: [g.weight_vector() for g in G]
[(1, 0, 0), (-1, 0, 0)]

Special Functions: _gfan,$  $ _gfan_gens,$  $ _repr_

See About this document... for information on suggesting changes.