# 33.2 Groebner Fans

Module: `sage.rings.polynomial.groebner_fan`

Groebner Fans

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:

• Commands for computing tropical varieties.

• Interactive walks in the Gröbner fan of an ideal.

• Commands for graphical renderings of Gröbner fans and monomial ideals.

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

```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()
True
```

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, order='lex')
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 (x^2*y - z, -x + y^2*z, x*z^2 - y) of Multivariate 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)
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( 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)
sage: 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)
sage: 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)
sage: 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)
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( self)
Return the minimal total degree of any Groebner basis.

```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( self)
Return the number of reduced Groebner bases.

```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( self)
Return the number of variables.

```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
```

 reduced_groebner_bases( self)

```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]]
```

 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)
sage: G = R.ideal([y^3 - x^2, y^2 - 13*x]).groebner_fan()
sage: G.render(SAGE_TMP + '/test.fig')
```

```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: G.render(SAGE_TMP + '/test.fig', show=False, 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, 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 ()
[-4*x^2 - x - y + z^3, -3*x^2 + y^3]
```

Special Functions: __eq__, __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)
sage: G = R.ideal([x^2*y - z, y^2*z - x, z^2*x - y]).groebner_fan()
sage: G._gfan_ideal()
'{a^2*b - c, b^2*c - a, a*c^2 - b}'
```

 _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)
sage: G = R.ideal([x^2*y - z, y^2*z - x, z^2*x - y]).groebner_fan()
sage: G._gfan_maps()
(Ring morphism:
From: Multivariate Polynomial Ring in x, y, z over Rational Field
To:   Multivariate Polynomial Ring in a, b, c over Rational Field
Defn: x |--> a
y |--> b
z |--> c,
Ring morphism:
From: Multivariate Polynomial Ring in a, b, c over Rational Field
To:   Multivariate 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)

```sage: R.<x,y> = PolynomialRing(QQ)
sage: 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)
sage: 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)
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( 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)
sage: G = R.ideal([y^3 - x^2, y^2 - 13*x]).groebner_fan()
sage: G[0].interactive()      # not tested
Initializing gfan interactive mode
*********************************************
*********************************************
....
```

 weight_vector( self)
Return the weight vector of this reduced Groebner basis.

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

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

Special Functions: _gfan, _gfan_gens, _repr_