ToricIdealBasis - Maple Help
For the best experience, we recommend viewing online help using Google Chrome or Microsoft Edge.

Groebner

 ToricIdealBasis
 compute Groebner bases of toric ideals

 Calling Sequence ToricIdealBasis(A, v, T, opts)

Parameters

 A - integer Matrix defining a toric ideal v - list of variables T - a MonomialOrder or ShortMonomialOrder opts - optional arguments of the form keyword=value

Description

 • The ToricIdealBasis command computes a reduced Groebner basis of the toric ideal defined by the integer matrix A with respect to the monomial order T.  Let a[i] denote the i-th column of A. Then ToricIdealBasis(A, v, T) computes the reduced Groebner basis with respect to T of the elimination ideal  intersected with K[v].
 • The first argument A must be a Matrix with integer entries.  Otherwise an error is returned.
 • The optional argument method=hs or du specifies the algorithm to be used by ToricIdealBasis. 'hs' denotes the algorithm of Hosten and Sturmfels (GRIN), while 'du' denotes the algorithm by Di Biase and Urbanke. The default algorithm is 'hs'.
 • The optional argument grading=table([v[1]=w[1], ..., v[n]=w[n]]) is used to specify a system of weights for the variables v. The Hosten and Sturmfels algorithm assumes that the toric ideal is homogeneous with respect to a grading that has a positive weight on each variable. An obvious weight system is given by a row of A containing all positive entries. The 'hs' algorithm will detect and use this weight system automatically, however you can also specify your own weights using this option. The weights w[i] must all be positive integers.

Examples

Primitive partition identities by Groebner basis of Lawrence lifting:

 > $\mathrm{with}\left(\mathrm{Groebner}\right):$
 > $A≔\mathrm{Matrix}\left(6,8,\left[\left[1,1,1,1,0,0,0,0\right],\left[1,2,3,4,0,0,0,0\right],\left[1,0,0,0,1,0,0,0\right],\left[0,1,0,0,0,1,0,0\right],\left[0,0,1,0,0,0,1,0\right],\left[0,0,0,1,0,0,0,1\right]\right]\right)$
 ${A}{≔}\left[\begin{array}{cccccccc}{1}& {1}& {1}& {1}& {0}& {0}& {0}& {0}\\ {1}& {2}& {3}& {4}& {0}& {0}& {0}& {0}\\ {1}& {0}& {0}& {0}& {1}& {0}& {0}& {0}\\ {0}& {1}& {0}& {0}& {0}& {1}& {0}& {0}\\ {0}& {0}& {1}& {0}& {0}& {0}& {1}& {0}\\ {0}& {0}& {0}& {1}& {0}& {0}& {0}& {1}\end{array}\right]$ (1)
 > $\mathrm{zs}≔\left[\mathrm{seq}\left({z}_{i},i=1..8\right)\right]$
 ${\mathrm{zs}}{≔}\left[{{z}}_{{1}}{,}{{z}}_{{2}}{,}{{z}}_{{3}}{,}{{z}}_{{4}}{,}{{z}}_{{5}}{,}{{z}}_{{6}}{,}{{z}}_{{7}}{,}{{z}}_{{8}}\right]$ (2)
 > $\mathrm{grd}≔\mathrm{table}\left(\left[\mathrm{seq}\left({\mathrm{zs}}_{i}=1,i=1..8\right)\right]\right)$
 ${\mathrm{grd}}{≔}{table}{}\left(\left[{{z}}_{{1}}{=}{1}{,}{{z}}_{{2}}{=}{1}{,}{{z}}_{{3}}{=}{1}{,}{{z}}_{{4}}{=}{1}{,}{{z}}_{{6}}{=}{1}{,}{{z}}_{{5}}{=}{1}{,}{{z}}_{{7}}{=}{1}{,}{{z}}_{{8}}{=}{1}\right]\right)$ (3)
 > $\mathrm{ToricIdealBasis}\left(A,\mathrm{zs},\mathrm{plex}\left(\mathrm{op}\left(\mathrm{zs}\right)\right),\mathrm{method}='\mathrm{hs}',\mathrm{grading}=\mathrm{grd}\right)$
 $\left[{{z}}_{{2}}{}{{z}}_{{4}}{}{{z}}_{{7}}^{{2}}{-}{{z}}_{{3}}^{{2}}{}{{z}}_{{6}}{}{{z}}_{{8}}{,}{{z}}_{{1}}{}{{z}}_{{4}}{}{{z}}_{{6}}{}{{z}}_{{7}}{-}{{z}}_{{3}}{}{{z}}_{{5}}{}{{z}}_{{8}}{}{{z}}_{{2}}{,}{{z}}_{{1}}{}{{z}}_{{4}}^{{2}}{}{{z}}_{{7}}^{{3}}{-}{{z}}_{{3}}^{{3}}{}{{z}}_{{5}}{}{{z}}_{{8}}^{{2}}{,}{{z}}_{{1}}{}{{z}}_{{3}}{}{{z}}_{{6}}^{{2}}{-}{{z}}_{{2}}^{{2}}{}{{z}}_{{5}}{}{{z}}_{{7}}{,}{{z}}_{{1}}^{{2}}{}{{z}}_{{4}}{}{{z}}_{{6}}^{{3}}{-}{{z}}_{{2}}^{{3}}{}{{z}}_{{5}}^{{2}}{}{{z}}_{{8}}\right]$ (4)

To demonstrate, we recompute this basis using F4 and the Groebner walk.

 > $\mathrm{sys}≔\left[\mathrm{seq}\left({\mathrm{zs}}_{i}-\mathrm{mul}\left({x}_{j}^{{A}_{j,i}},j=1..6\right),i=1..8\right)\right]$
 ${\mathrm{sys}}{≔}\left[{-}{{x}}_{{1}}{}{{x}}_{{2}}{}{{x}}_{{3}}{+}{{z}}_{{1}}{,}{-}{{x}}_{{1}}{}{{x}}_{{2}}^{{2}}{}{{x}}_{{4}}{+}{{z}}_{{2}}{,}{-}{{x}}_{{1}}{}{{x}}_{{2}}^{{3}}{}{{x}}_{{5}}{+}{{z}}_{{3}}{,}{-}{{x}}_{{1}}{}{{x}}_{{2}}^{{4}}{}{{x}}_{{6}}{+}{{z}}_{{4}}{,}{{z}}_{{5}}{-}{{x}}_{{3}}{,}{{z}}_{{6}}{-}{{x}}_{{4}}{,}{{z}}_{{7}}{-}{{x}}_{{5}}{,}{{z}}_{{8}}{-}{{x}}_{{6}}\right]$ (5)
 > $X≔\left[\mathrm{seq}\left({x}_{j},j=1..6\right)\right]$
 ${X}{≔}\left[{{x}}_{{1}}{,}{{x}}_{{2}}{,}{{x}}_{{3}}{,}{{x}}_{{4}}{,}{{x}}_{{5}}{,}{{x}}_{{6}}\right]$ (6)
 > $G≔\mathrm{remove}\left(\mathrm{has},\mathrm{Basis}\left(\mathrm{sys},\mathrm{lexdeg}\left(X,\mathrm{zs}\right),\mathrm{method}=\mathrm{direct}\right),X\right)$
 ${G}{≔}\left[{{z}}_{{2}}{}{{z}}_{{4}}{}{{z}}_{{7}}^{{2}}{-}{{z}}_{{3}}^{{2}}{}{{z}}_{{6}}{}{{z}}_{{8}}{,}{{z}}_{{1}}{}{{z}}_{{4}}{}{{z}}_{{6}}{}{{z}}_{{7}}{-}{{z}}_{{3}}{}{{z}}_{{5}}{}{{z}}_{{8}}{}{{z}}_{{2}}{,}{{z}}_{{1}}{}{{z}}_{{3}}{}{{z}}_{{6}}^{{2}}{-}{{z}}_{{2}}^{{2}}{}{{z}}_{{5}}{}{{z}}_{{7}}{,}{{z}}_{{1}}{}{{z}}_{{4}}^{{2}}{}{{z}}_{{7}}^{{3}}{-}{{z}}_{{3}}^{{3}}{}{{z}}_{{5}}{}{{z}}_{{8}}^{{2}}{,}{{z}}_{{1}}^{{2}}{}{{z}}_{{4}}{}{{z}}_{{6}}^{{3}}{-}{{z}}_{{2}}^{{3}}{}{{z}}_{{5}}^{{2}}{}{{z}}_{{8}}\right]$ (7)
 > $\mathrm{Walk}\left(G,\mathrm{tdeg}\left(\mathrm{op}\left(\mathrm{zs}\right)\right),\mathrm{plex}\left(\mathrm{op}\left(\mathrm{zs}\right)\right)\right)$
 $\left[{{z}}_{{2}}{}{{z}}_{{4}}{}{{z}}_{{7}}^{{2}}{-}{{z}}_{{3}}^{{2}}{}{{z}}_{{6}}{}{{z}}_{{8}}{,}{{z}}_{{1}}{}{{z}}_{{4}}{}{{z}}_{{6}}{}{{z}}_{{7}}{-}{{z}}_{{3}}{}{{z}}_{{5}}{}{{z}}_{{8}}{}{{z}}_{{2}}{,}{{z}}_{{1}}{}{{z}}_{{4}}^{{2}}{}{{z}}_{{7}}^{{3}}{-}{{z}}_{{3}}^{{3}}{}{{z}}_{{5}}{}{{z}}_{{8}}^{{2}}{,}{{z}}_{{1}}{}{{z}}_{{3}}{}{{z}}_{{6}}^{{2}}{-}{{z}}_{{2}}^{{2}}{}{{z}}_{{5}}{}{{z}}_{{7}}{,}{{z}}_{{1}}^{{2}}{}{{z}}_{{4}}{}{{z}}_{{6}}^{{3}}{-}{{z}}_{{2}}^{{3}}{}{{z}}_{{5}}^{{2}}{}{{z}}_{{8}}\right]$ (8)

Example 12.7 in Sturmfels' Groebner Bases and Convex Polytopes:

 > $B≔\mathrm{Matrix}\left(4,8,\left[\left[1,2,3,4,0,1,4,5\right],\left[2,3,4,1,1,4,5,0\right],\left[3,4,1,2,4,5,0,1\right],\left[4,1,2,3,5,0,1,4\right]\right]\right)$
 ${B}{≔}\left[\begin{array}{cccccccc}{1}& {2}& {3}& {4}& {0}& {1}& {4}& {5}\\ {2}& {3}& {4}& {1}& {1}& {4}& {5}& {0}\\ {3}& {4}& {1}& {2}& {4}& {5}& {0}& {1}\\ {4}& {1}& {2}& {3}& {5}& {0}& {1}& {4}\end{array}\right]$ (9)
 > $\mathrm{ToricIdealBasis}\left(B,\mathrm{zs},\mathrm{plex}\left(\mathrm{op}\left(\mathrm{zs}\right)\right)\right)$
 $\left[{{z}}_{{4}}^{{4}}{-}{{z}}_{{6}}{}{{z}}_{{8}}^{{3}}{,}{{z}}_{{3}}^{{4}}{-}{{z}}_{{5}}{}{{z}}_{{7}}^{{3}}{,}{{z}}_{{2}}{}{{z}}_{{8}}^{{2}}{-}{{z}}_{{4}}^{{3}}{,}{{z}}_{{2}}{}{{z}}_{{4}}{-}{{z}}_{{6}}{}{{z}}_{{8}}{,}{{z}}_{{2}}^{{2}}{}{{z}}_{{8}}{-}{{z}}_{{6}}{}{{z}}_{{4}}^{{2}}{,}{{z}}_{{2}}^{{3}}{-}{{z}}_{{4}}{}{{z}}_{{6}}^{{2}}{,}{{z}}_{{1}}{}{{z}}_{{7}}^{{2}}{-}{{z}}_{{3}}^{{3}}{,}{{z}}_{{1}}{}{{z}}_{{3}}{-}{{z}}_{{5}}{}{{z}}_{{7}}{,}{{z}}_{{1}}^{{2}}{}{{z}}_{{7}}{-}{{z}}_{{3}}^{{2}}{}{{z}}_{{5}}{,}{{z}}_{{1}}^{{3}}{-}{{z}}_{{3}}{}{{z}}_{{5}}^{{2}}\right]$ (10)

References

 Di Biase, Fausto, and Urbanke, Rudiger. "An Algorithm to Calculate the Kernel of Certain Polynomial Ring Homomorphisms." Experimental Mathematics, (1995): 227-234.
 Hosten, Serkan, and Shapiro, Jay. "Primary Decomposition of Lattice Basis Ideals." Journal of Symbolic Computation, (May 2000): 625-639.
 Sturmfels, B. "Groebner Bases and Convex Polytopes." University Lecture Series, No. 8. Providence, Rhode Island: American Mathematical Society, 1996.