Toric ideals

A toric ideal (associated to an integer matrix \(A\)) is an ideal of the form

\[I_A = \left< x^u - x^v : u,v \in \ZZ_\geq^n , u-v \in \ker(A) \right>\]

In other words, it is an ideal generated by irreducible “binomials”, that is, differences of monomials without a common factor. Since the Buchberger algorithm preserves this property, any Groebner basis is then also generated by binomials.

EXAMPLES:

Sage

sage: A = matrix([[1,1,1], [0,1,2]])
sage: IA = ToricIdeal(A)
sage: IA.ker()
Free module of degree 3 and rank 1 over Integer Ring
User basis matrix:
[-1  2 -1]
sage: IA
Ideal (-z1^2 + z0*z2) of Multivariate Polynomial
Ring in z0, z1, z2 over Rational Field

Python

>>> from sage.all import *
>>> A = matrix([[Integer(1),Integer(1),Integer(1)], [Integer(0),Integer(1),Integer(2)]])
>>> IA = ToricIdeal(A)
>>> IA.ker()
Free module of degree 3 and rank 1 over Integer Ring
User basis matrix:
[-1  2 -1]
>>> IA
Ideal (-z1^2 + z0*z2) of Multivariate Polynomial
Ring in z0, z1, z2 over Rational Field

Here, the “naive” ideal generated by \(z_0 z_2 - z_1^2\) does already equal the toric ideal. But that is not true in general! For example, this toric ideal ([Stu1997], Example 1.2) is the twisted cubic and cannot be generated by \(2=\dim \ker(A)\) polynomials:

Sage

sage: A = matrix([[3,2,1,0], [0,1,2,3]])
sage: IA = ToricIdeal(A)
sage: IA.ker()
Free module of degree 4 and rank 2 over Integer Ring
User basis matrix:
[-1  1  1 -1]
[-1  2 -1  0]
sage: IA
Ideal (-z1*z2 + z0*z3, -z1^2 + z0*z2, z2^2 - z1*z3) of
Multivariate Polynomial Ring in z0, z1, z2, z3 over Rational Field

Python

>>> from sage.all import *
>>> A = matrix([[Integer(3),Integer(2),Integer(1),Integer(0)], [Integer(0),Integer(1),Integer(2),Integer(3)]])
>>> IA = ToricIdeal(A)
>>> IA.ker()
Free module of degree 4 and rank 2 over Integer Ring
User basis matrix:
[-1  1  1 -1]
[-1  2 -1  0]
>>> IA
Ideal (-z1*z2 + z0*z3, -z1^2 + z0*z2, z2^2 - z1*z3) of
Multivariate Polynomial Ring in z0, z1, z2, z3 over Rational Field

The following family of toric ideals is from Example 4.4 of [Stu1997]. One can show that \(I_d\) is generated by one quadric and \(d\) binomials of degree \(d\):

Sage

sage: def I(d):
....:     return ToricIdeal(matrix([[1,1,1,1,1], [0,1,1,0,0], [0,0,1,1,d]]))
sage: I(2)
Ideal (-z3^2 + z0*z4,
       z0*z2 - z1*z3,
       z2*z3 - z1*z4) of
Multivariate Polynomial Ring in z0, z1, z2, z3, z4 over Rational Field
sage: I(3)
Ideal (-z3^3 + z0^2*z4,
       z0*z2 - z1*z3,
       z2*z3^2 - z0*z1*z4,
       z2^2*z3 - z1^2*z4) of
Multivariate Polynomial Ring in z0, z1, z2, z3, z4 over Rational Field
sage: I(4)
Ideal (-z3^4 + z0^3*z4,
       z0*z2 - z1*z3,
       z2*z3^3 - z0^2*z1*z4,
       z2^2*z3^2 - z0*z1^2*z4,
       z2^3*z3 - z1^3*z4) of
Multivariate Polynomial Ring in z0, z1, z2, z3, z4 over Rational Field

Python

>>> from sage.all import *
>>> def I(d):
...     return ToricIdeal(matrix([[Integer(1),Integer(1),Integer(1),Integer(1),Integer(1)], [Integer(0),Integer(1),Integer(1),Integer(0),Integer(0)], [Integer(0),Integer(0),Integer(1),Integer(1),d]]))
>>> I(Integer(2))
Ideal (-z3^2 + z0*z4,
       z0*z2 - z1*z3,
       z2*z3 - z1*z4) of
Multivariate Polynomial Ring in z0, z1, z2, z3, z4 over Rational Field
>>> I(Integer(3))
Ideal (-z3^3 + z0^2*z4,
       z0*z2 - z1*z3,
       z2*z3^2 - z0*z1*z4,
       z2^2*z3 - z1^2*z4) of
Multivariate Polynomial Ring in z0, z1, z2, z3, z4 over Rational Field
>>> I(Integer(4))
Ideal (-z3^4 + z0^3*z4,
       z0*z2 - z1*z3,
       z2*z3^3 - z0^2*z1*z4,
       z2^2*z3^2 - z0*z1^2*z4,
       z2^3*z3 - z1^3*z4) of
Multivariate Polynomial Ring in z0, z1, z2, z3, z4 over Rational Field

Finally, the example in [SH1995b]

Sage

sage: A = matrix(ZZ, [ [15,  4, 14, 19,  2,  1, 10, 17],
....:                  [18, 11, 13,  5, 16, 16,  8, 19],
....:                  [11,  7,  8, 19, 15, 18, 14,  6],
....:                  [17, 10, 13, 17, 16, 14, 15, 18] ])
sage: IA = ToricIdeal(A)     # long time
sage: IA.ngens()             # long time
213

Python

>>> from sage.all import *
>>> A = matrix(ZZ, [ [Integer(15),  Integer(4), Integer(14), Integer(19),  Integer(2),  Integer(1), Integer(10), Integer(17)],
...                  [Integer(18), Integer(11), Integer(13),  Integer(5), Integer(16), Integer(16),  Integer(8), Integer(19)],
...                  [Integer(11),  Integer(7),  Integer(8), Integer(19), Integer(15), Integer(18), Integer(14),  Integer(6)],
...                  [Integer(17), Integer(10), Integer(13), Integer(17), Integer(16), Integer(14), Integer(15), Integer(18)] ])
>>> IA = ToricIdeal(A)     # long time
>>> IA.ngens()             # long time
213

AUTHORS:

• Volker Braun (2011-01-03): Initial version

class sage.schemes.toric.ideal.ToricIdeal(A, names='z', base_ring=Rational Field, polynomial_ring=None, algorithm='HostenSturmfels')

Bases: MPolynomialIdeal

This class represents a toric ideal defined by an integral matrix.

INPUT:

• A – integer matrix; the defining matrix of the toric ideal

• names – string (optional); names for the variables. By default, this is 'z' and the variables will be named z0, z1, …

• base_ring – a ring (default: \(\QQ\)); the base ring of the ideal. A toric ideal uses only coefficients \(\pm 1\).

• polynomial_ring – a polynomial ring (optional); the polynomial ring to construct the ideal in

  You may specify the ambient polynomial ring via the polynomial_ring parameter or via the names and base_ring parameter. A ValueError is raised if you specify both.

• algorithm – string (optional); the algorithm to use. For now, must be 'HostenSturmfels' which is the algorithm proposed by Hosten and Sturmfels in [SH1995b].

EXAMPLES:

Sage

sage: A = matrix([[1,1,1], [0,1,2]])
sage: ToricIdeal(A)
Ideal (-z1^2 + z0*z2) of Multivariate Polynomial Ring
in z0, z1, z2 over Rational Field

Python

>>> from sage.all import *
>>> A = matrix([[Integer(1),Integer(1),Integer(1)], [Integer(0),Integer(1),Integer(2)]])
>>> ToricIdeal(A)
Ideal (-z1^2 + z0*z2) of Multivariate Polynomial Ring
in z0, z1, z2 over Rational Field

First way of specifying the polynomial ring:

Sage

sage: ToricIdeal(A, names='x,y,z', base_ring=ZZ)
Ideal (-y^2 + x*z) of Multivariate Polynomial Ring
in x, y, z over Integer Ring

Python

>>> from sage.all import *
>>> ToricIdeal(A, names='x,y,z', base_ring=ZZ)
Ideal (-y^2 + x*z) of Multivariate Polynomial Ring
in x, y, z over Integer Ring

Second way of specifying the polynomial ring:

Sage

sage: R.<x,y,z> = ZZ[]
sage: ToricIdeal(A, polynomial_ring=R)
Ideal (-y^2 + x*z) of Multivariate Polynomial Ring
in x, y, z over Integer Ring

Python

>>> from sage.all import *
>>> R = ZZ['x, y, z']; (x, y, z,) = R._first_ngens(3)
>>> ToricIdeal(A, polynomial_ring=R)
Ideal (-y^2 + x*z) of Multivariate Polynomial Ring
in x, y, z over Integer Ring

It is an error to specify both:

Sage

sage: ToricIdeal(A, names='x,y,z', polynomial_ring=R)
Traceback (most recent call last):
...
ValueError: you must not specify both variable names and a polynomial ring

Python

>>> from sage.all import *
>>> ToricIdeal(A, names='x,y,z', polynomial_ring=R)
Traceback (most recent call last):
...
ValueError: you must not specify both variable names and a polynomial ring

A()

Return the defining matrix.

OUTPUT: integer matrix

EXAMPLES:

Sage

sage: A = matrix([[1,1,1], [0,1,2]])
sage: IA = ToricIdeal(A)
sage: IA.A()
[1 1 1]
[0 1 2]

Python

>>> from sage.all import *
>>> A = matrix([[Integer(1),Integer(1),Integer(1)], [Integer(0),Integer(1),Integer(2)]])
>>> IA = ToricIdeal(A)
>>> IA.A()
[1 1 1]
[0 1 2]

ker()

Return the kernel of the defining matrix.

OUTPUT: the kernel of self.A().

EXAMPLES:

Sage

sage: A = matrix([[1,1,1], [0,1,2]])
sage: IA = ToricIdeal(A)
sage: IA.ker()
Free module of degree 3 and rank 1 over Integer Ring
 User basis matrix: [-1  2 -1]

Python

>>> from sage.all import *
>>> A = matrix([[Integer(1),Integer(1),Integer(1)], [Integer(0),Integer(1),Integer(2)]])
>>> IA = ToricIdeal(A)
>>> IA.ker()
Free module of degree 3 and rank 1 over Integer Ring
 User basis matrix: [-1  2 -1]

nvariables()

Return the number of variables of the ambient polynomial ring.

OUTPUT: integer; the number of columns of the defining matrix A()

EXAMPLES:

Sage

sage: A = matrix([[1,1,1], [0,1,2]])
sage: IA = ToricIdeal(A)
sage: IA.nvariables()
3

Python

>>> from sage.all import *
>>> A = matrix([[Integer(1),Integer(1),Integer(1)], [Integer(0),Integer(1),Integer(2)]])
>>> IA = ToricIdeal(A)
>>> IA.nvariables()
3