Groebner Fans

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

• Commands for computing tropical varieties.
• Interactive walks in the Groebner fan of an ideal.
• Commands for graphical renderings of Groebner fans and monomial ideals.

AUTHORS:

• 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: the design of the Sage interface to gfan is joint work with Tristram Bogart, who also supplied numerous examples.
• Marshall Hampton (2008-03-25): Rewrote various functions to use gfan-0.3. This is still a work in progress, comments are appreciated on sage-devel@googlegroups.com (or personally at hamptonio@gmail.com).

EXAMPLES:

sage: x,y = QQ['x,y'].gens() 
sage: i = ideal(x^2 - y^2 + 1)
sage: g = i.groebner_fan()
sage: g.reduced_groebner_bases()
[[x^2 - y^2 + 1], [-x^2 + y^2 - 1]]

TESTS:

sage: x,y = QQ['x,y'].gens() 
sage: i = ideal(x^2 - y^2 + 1)
sage: g = i.groebner_fan()
sage: g == loads(dumps(g))
True

REFERENCES:

• Anders N. Jensen; Gfan, a software system for Groebner fans; available at http://www.math.tu-berlin.de/~jensen/software/gfan/gfan.html

class sage.rings.polynomial.groebner_fan.GroebnerFan(I, is_groebner_basis=False, symmetry=None, verbose=False)

Bases: sage.structure.sage_object.SageObject

buchberger()

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

EXAMPLES:

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

characteristic()

Return the characteristic of the base ring.

EXAMPLES:

sage: R.<x,y,z> = PolynomialRing(QQ,3)
sage: i1 = ideal(x*z + 6*y*z - z^2, x*y + 6*x*z + y*z - z^2, y^2 + x*z + y*z)
sage: gf = i1.groebner_fan()
sage: gf.characteristic()
0

dimension_of_homogeneity_space()

Return the dimension of the homogeneity space.

EXAMPLES:

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

gfan(cmd='', I=None, format=True)

Returns the gfan output as a string given an input cmd; the default is to produce the list of reduced Groebner bases in gfan format.

EXAMPLES:

sage: R.<x,y> = PolynomialRing(QQ,2)
sage: gf = R.ideal([x^3-y,y^3-x-1]).groebner_fan()
sage: gf.gfan()
'Q[x,y]\n{{\ny^9-1-y+3*y^3-3*y^6,\nx+1-y^3}\n,\n{\ny^3-1-x,\nx^3-y}\n,\n{\ny-x^3,\nx^9-1-x}\n}\n'

homogeneity_space()

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

EXAMPLES:

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

ideal()

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

EXAMPLES:

sage: R.<x1,x2> = PolynomialRing(QQ,2)
sage: gf = R.ideal([x1^3-x2,x2^3-2*x1-2]).groebner_fan()
sage: gf.ideal()
Ideal (x1^3 - x2, x2^3 - 2*x1 - 2) of Multivariate Polynomial Ring in x1, x2 over Rational Field

interactive(*args, **kwds)

See the documentation for self[0].interactive(). This does not work with the notebook.

EXAMPLES:

sage: print "This is not easily doc-testable; please write a good one!"
This is not easily doc-testable; please write a good one!

maximal_total_degree_of_a_groebner_basis()

Return the maximal total degree of any Groebner basis.

EXAMPLES:

sage: R.<x,y> = PolynomialRing(QQ,2)
sage: 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()

Return the minimal total degree of any Groebner basis.

EXAMPLES:

sage: R.<x,y> = PolynomialRing(QQ,2)        
sage: 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()

Return the number of reduced Groebner bases.

EXAMPLES:

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

number_of_variables()

Return the number of variables.

EXAMPLES:

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

sage: R = PolynomialRing(QQ,'x',10)
sage: R.inject_variables(globals())
Defining x0, x1, x2, x3, x4, x5, x6, x7, x8, x9
sage: G = ideal([x0 - x9, sum(R.gens())]).groebner_fan()
sage: G.number_of_variables()
10

polyhedralfan()

Returns a polyhedral fan object corresponding to the reduced Groebner bases.

EXAMPLES:

sage: R3.<x,y,z> = PolynomialRing(QQ,3)
sage: gf = R3.ideal([x^8-y^4,y^4-z^2,z^2-1]).groebner_fan()
sage: pf = gf.polyhedralfan()
sage: pf.rays()
[[0, 0, 1], [0, 1, 0], [1, 0, 0]]

reduced_groebner_bases()

EXAMPLES:

sage: R.<x,y,z> = PolynomialRing(QQ, 3, order='lex')
sage: 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]
[z^15 - z, y - z^11, x - z^9]
sage: X[0].ideal()
Ideal (z^15 - z, y - z^11, x - z^9) of Multivariate Polynomial Ring in x, y, z over Rational Field
sage: X[:5]
[[z^15 - z, y - z^11, x - z^9],
[-y + z^11, y*z^4 - z, y^2 - z^8, x - z^9],
[-y^2 + z^8, y*z^4 - z, y^2*z^3 - y, y^3 - z^5, x - y^2*z],
[-y^3 + z^5, y*z^4 - z, y^2*z^3 - y, y^4 - z^2, x - y^2*z],
[-y^4 + z^2, y^6*z - y, y^9 - z, x - y^2*z]]
sage: R3.<x,y,z> = PolynomialRing(GF(2477),3)
sage: gf = R3.ideal([300*x^3-y,y^2-z,z^2-12]).groebner_fan()
sage: gf.reduced_groebner_bases()
[[z^2 - 12, y^2 - z, x^3 + 933*y],
[-y^2 + z, y^4 - 12, x^3 + 933*y],
[z^2 - 12, -300*x^3 + y, x^6 - 1062*z],
[-828*x^6 + z, -300*x^3 + y, x^12 + 200]]

render(file=None, larger=False, shift=0, rgbcolor=(0, 0, 0), polyfill=<function max_degree at 0x1c54d848>, scale_colors=True)

Render a Groebner fan as sage graphics or save as an xfig file.

More precisely, the output is a drawing of the Groebner fan intersected with a triangle. 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:

• file - a filename if you prefer the output saved to a file. This will be in xfig format.
• 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. Affects the xfig file but probably not the sage graphics (?)
• rgbcolor - This will not affect the saved xfig file, only the sage graphics produced.
• polyfill - Whether or not to fill the cones with a color determined by the highest degree in each reduced Groebner basis for that cone.
• scale_colors - if True, this will normalize color values to try to maximize the range

EXAMPLES:

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

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

TESTS:

Testing the case where the number of generators is < 3. Currently, this should raise a NotImplementedError error.

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

render3d(verbose=False)

For a Groebner fan of an ideal in a ring with four variables, this function intersects the fan with the standard simplex perpendicular to (1,1,1,1), creating a 3d polytope, which is then projected into 3 dimensions. The edges of this projected polytope are returned as lines.

EXAMPLES:

sage: R4.<w,x,y,z> = PolynomialRing(QQ,4)
sage: gf = R4.ideal([w^2-x,x^2-y,y^2-z,z^2-x]).groebner_fan()
sage: three_d = gf.render3d()

TESTS:

Now test the case where the number of generators is not 4. Currently, this should raise a NotImplementedError error.

sage: P.<a,b,c> = PolynomialRing(QQ, 3, order="lex")
sage: sage.rings.ideal.Katsura(P, 3).groebner_fan().render3d()
...
NotImplementedError

ring()

Return the multivariate polynomial ring.

EXAMPLES:

sage: R.<x1,x2> = PolynomialRing(QQ,2)
sage: gf = R.ideal([x1^3-x2,x2^3-x1-2]).groebner_fan()
sage: gf.ring()
Multivariate Polynomial Ring in x1, x2 over Rational Field

tropical_basis(check=True, verbose=False)

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).

EXAMPLES:

sage: R.<x,y,z> = PolynomialRing(QQ,3, order='lex')
sage: 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 (-3*x^2 + y^3, 2*x^2 - x - 2*y^3 - y + z^3) of Multivariate Polynomial Ring in x, y, z over Rational Field
sage: G.tropical_basis()
[-3*x^2 + y^3, 2*x^2 - x - 2*y^3 - y + z^3, 3/4*x + y^3 + 3/4*y - 3/4*z^3]

tropical_intersection(ideal_arg=False, *args, **kwds)

Returns information about the tropical intersection of the polynomials defining the ideal.

EXAMPLES:

sage: R.<x,y,z> = PolynomialRing(QQ,3)
sage: i1 = ideal(x*z + 6*y*z - z^2, x*y + 6*x*z + y*z - z^2, y^2 + x*z + y*z)
sage: gf = i1.groebner_fan()
sage: pf = gf.tropical_intersection()
sage: pf.rays()
[[-2, 1, 1]]

weight_vectors()

Returns the weight vectors corresponding to the reduced Groebner bases.

EXAMPLES:

sage: r3.<x,y,z> = PolynomialRing(QQ,3)
sage: g = r3.ideal([x^3+y,y^3-z,z^2-x]).groebner_fan()
sage: g.weight_vectors()
[(3, 7, 1), (5, 1, 2), (7, 1, 4), (1, 1, 4), (1, 1, 1), (1, 4, 1), (1, 4, 10)]
sage: r4.<x,y,z,w> = PolynomialRing(QQ,4)
sage: g4 = r4.ideal([x^3+y,y^3-z,z^2-x,z^3 - w]).groebner_fan()
sage: len(g4.weight_vectors())
23

class sage.rings.polynomial.groebner_fan.PolyhedralCone(gfan_polyhedral_cone, ring=Rational Field)

Bases: sage.structure.sage_object.SageObject

ambient_dim()

Returns the ambient dimension of the Groebner cone.

EXAMPLES:

sage: R3.<x,y,z> = PolynomialRing(QQ,3)
sage: gf = R3.ideal([x^8-y^4,y^4-z^2,z^2-2]).groebner_fan()
sage: a = gf[0].groebner_cone()
sage: a.ambient_dim()
3

dim()

Returns the dimension of the Groebner cone.

EXAMPLES:

sage: R3.<x,y,z> = PolynomialRing(QQ,3)
sage: gf = R3.ideal([x^8-y^4,y^4-z^2,z^2-2]).groebner_fan()
sage: a = gf[0].groebner_cone()
sage: a.dim()
3

facets()

Returns the inward facet normals of the Groebner cone.

EXAMPLES:

sage: R3.<x,y,z> = PolynomialRing(QQ,3)
sage: gf = R3.ideal([x^8-y^4,y^4-z^2,z^2-2]).groebner_fan()
sage: a = gf[0].groebner_cone()
sage: a.facets()
[[0, 0, 1], [0, 1, 0], [1, 0, 0]]

lineality_dim()

Returns the lineality dimension of the Groebner cone. This is just the difference between the ambient dimension and the dimension of the cone.

EXAMPLES:

sage: R3.<x,y,z> = PolynomialRing(QQ,3)
sage: gf = R3.ideal([x^8-y^4,y^4-z^2,z^2-2]).groebner_fan()
sage: a = gf[0].groebner_cone()
sage: a.lineality_dim()
0

relative_interior_point()

Returns a point in the relative interior of the Groebner cone.

EXAMPLES:

sage: R3.<x,y,z> = PolynomialRing(QQ,3)
sage: gf = R3.ideal([x^8-y^4,y^4-z^2,z^2-2]).groebner_fan()
sage: a = gf[0].groebner_cone()
sage: a.relative_interior_point()
[1, 1, 1]

class sage.rings.polynomial.groebner_fan.PolyhedralFan(gfan_polyhedral_fan)

Bases: sage.structure.sage_object.SageObject

ambient_dim()

Returns the ambient dimension of the Groebner fan.

EXAMPLES:

sage: R3.<x,y,z> = PolynomialRing(QQ,3)
sage: gf = R3.ideal([x^8-y^4,y^4-z^2,z^2-2]).groebner_fan()
sage: a = gf.polyhedralfan()
sage: a.ambient_dim()
3

dim()

Returns the dimension of the Groebner fan.

EXAMPLES:

sage: R3.<x,y,z> = PolynomialRing(QQ,3)
sage: gf = R3.ideal([x^8-y^4,y^4-z^2,z^2-2]).groebner_fan()
sage: a = gf.polyhedralfan()
sage: a.dim()
3

lineality_dim()

Returns the lineality dimension of the Groebner fan. This is just the difference between the ambient dimension and the dimension of the cone.

EXAMPLES:

sage: R3.<x,y,z> = PolynomialRing(QQ,3)
sage: gf = R3.ideal([x^8-y^4,y^4-z^2,z^2-2]).groebner_fan()
sage: a = gf.polyhedralfan()
sage: a.lineality_dim()
0

rays()

Returns a list of rays of the polyhedral fan.

EXAMPLES:

sage: R.<x,y,z> = PolynomialRing(QQ,3)
sage: i2 = ideal(x*z + 6*y*z - z^2, x*y + 6*x*z + y*z - z^2, y^2 + x*z + y*z)
sage: gf2 = i2.groebner_fan(verbose = False)
sage: pf = gf2.polyhedralfan()
sage: pf.rays()
[[-1, 0, 1], [-1, 1, 0], [1, -2, 1], [1, 1, -2], [2, -1, -1]]

class sage.rings.polynomial.groebner_fan.ReducedGroebnerBasis(groebner_fan, gens, gfan_gens)

Bases: sage.structure.sage_object.SageObject, list

groebner_cone(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

EXAMPLES:

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

ideal()

Return the ideal generated by this basis.

EXAMPLES:

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

interactive(latex=False, flippable=False, wall=False, inequalities=False, weight=False)

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

EXAMPLES:

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

sage.rings.polynomial.groebner_fan.max_degree(list_of_polys)

Computes the maximum degree of a list of polynomials

EXAMPLES:

sage: from sage.rings.polynomial.groebner_fan import max_degree
sage: R.<x,y> = PolynomialRing(QQ,2)
sage: p_list = [x^2-y,x*y^10-x]
sage: max_degree(p_list)
11.0

sage.rings.polynomial.groebner_fan.prefix_check(str_list)

Checks if any strings in a list are prefixes of another string in the list.

EXAMPLES:

sage: from sage.rings.polynomial.groebner_fan import prefix_check
sage: prefix_check(['z1','z1z1'])
False
sage: prefix_check(['z1','zz1'])
True