Package sagbi

This article is about a function from ApCoCoA-2. If you are looking for the ApCoCoA-1 version of it, see Category:ApCoCoA-1:Package sagbi.

This page is about the SAGBI package. For a complete function list, see Category:Package sagbi.

Mathematical Definitions

Let Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle K} be a field and let $P=K[x_{1},\ldots ,x_{n}]$ be the polynomial ring over Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle K} in $n$ indeterminates. Most of the definitions here are taken from the book Computational Commutative Algebra 2 by Martin Kreuzer and Lorenzo Robbiano.

Subalgebras

A subset $S\subseteq P$ is called a $K$-subalgebra of $P$, if

• $K\subseteq S$ and
• $S$ is closed under addition and multiplication.

For a subset $F=\{f_{1},\ldots ,f_{s}\}\subseteq P$, we write

$K[F]=K[f_{1},\ldots ,f_{s}]=\{p(f_{1},\ldots ,f_{s})\mid p\in K[y_{1},\ldots ,y_{s}]\}$

where $K[y_{1},\ldots ,y_{s}]$ is a new polynomial ring in $s$ indeterminates for the $K$-subalgebra of $P$ generated by $F$.

SAGBI bases

Let $\sigma$ be a term ordering on $P$ and let $S$ be a $K$-subalgebra of $P$. A set $G\subseteq S$ is called a $\sigma$-SAGBI basis of $S$ if $K[{\rm {LT}}_{\sigma }(f)\mid f\in S]=K[{\rm {LT}}_{\sigma }(f)\mid f\in G]$.

If $S$ is a graded subalgebra and $d\in \mathbb {N}$, then a set $G_{\leq d}$ is called a $d$-truncated $\sigma$-SAGBI basis of $S$, if

$K[{\rm {LT}}_{\sigma }(f)\mid f\in S{\text{ and }}\deg(f)\leq d]=K[{\rm {LT}}_{\sigma }(f)\mid f\in G_{\leq d}].$

Equivalently, a set $G_{\leq d}$ is a $d$-truncated $\sigma$-SAGBI basis of $S$ if there is a $\sigma$-SAGBI basis of $S$ with $G_{\leq d}=\{g\in G\mid \deg(g)\leq d\}$.

The Subalgebra Rewrite Relation

Let $G\subseteq P$ be a set of non-zero polynomials. Furthermore, let $\sigma$ be a term ordering on $\mathbb {T} ^{n}$.

• For $f,g\in P\setminus \{0\}$, we say that $f$ subalgebra reduces to $g$ in one step if there are $f_{1},\ldots ,f_{s}\in G$, a term $t\in \mathbb {T} ^{s}$, and a constant $c\in K$ such that $g=f-ct(f_{1},\ldots ,f_{s})$ and ${\rm {LT}}_{\sigma }(t(f_{1},\ldots ,f_{s}))$ is not anymore in ${\operatorname {Supp} }(g)$. The path from $f$ to $g$ is then called a subalgebra reduction step and denoted by $f{\xrightarrow {G} }_{\rm {ss}}g$.
• The transitive closure of the relation ${\xrightarrow {G} }_{\rm {ss}}$ is denoted by ${\xrightarrow {G} }_{\rm {s}}$ and called the subalgebra rewrite relation defined by $G$. If there are $f,g\in P$ with $f{\xrightarrow {G} }_{\rm {s}}g$, we say that $f$ subalgebra reduces to $g$.
• If $g\in P$ such that there is no $h\in P$ with $h\neq g$ and $g{\xrightarrow {G} }_{\rm {ss}}h$, then $g$ is called irreducible with respect to the relation ${\xrightarrow {G} }_{\rm {s}}$. Sometimes we may also just write that $g$ is irreducible with respect to $G$.

A set $G\subseteq P$ is called interreduced if every element $g\in G$ is monic and irreducible with respect to $G\setminus \{g\}$. If $G$ is a $\sigma$-SAGBI basis of $K[G]$ which is interreduced, then it is called a reduced $\sigma$-SAGBI basis. Analogously to reduced Gröbner bases, it can be shown that every $K$-subalgebra has a unique reduced $\sigma$-SAGBI basis.

The Subalgebra Division Algorithm

Let $\sigma$ be a term ordering on $\mathbb {T} ^{n}$, $f\in P$ and $G=\{f_{1},\ldots ,f_{s}\}\subseteq P$ be a set of non-zero polynomials. Consider the following sequence of instructions.

1. Set $g:=f$.
2. Write $g=c_{1}t_{1}+\cdots +c_{m}t_{m}$ with $t_{i}\in \mathbb {T} ^{n}$, $c_{i}\in K$ for $i=1,\ldots ,m$, and $t_{1}\geq _{\sigma }\cdots \geq _{\sigma }t_{m}$. Set $k:=1$.
3. If $k=m+1$, stop and return $g$. Otherwise, check whether there is a term $t\in \mathbb {T} ^{s}$ such that $t_{k}=t({\rm {LT}}_{\sigma }(f_{1}),\ldots ,{\rm {LT}}_{\sigma }(f_{s}))$. If there is one, set $c=t({\rm {LC}}_{\sigma }(f_{1}),\ldots ,{\rm {LC}}_{\sigma }(f_{s}))$, replace $g$ by $g-{\frac {c_{i}}{c}}t(f_{1},\ldots ,f_{s})$ and go to step~(2). If there is none, increase $k$ by one and repeat this step.

This is an algorithm which returns a polynomial $g\in P$ such that $f{\xrightarrow {G} }_{\rm {s}}g$ and $g$ is irreducible with respect to ${\xrightarrow {G} }_{\rm {s}}$. This algorithm clearly computes a polynomial $g\in P$ with $f{\xrightarrow {G} }_{\rm {s}}g$ and $g$ is irreducible with respect to $G$.

Package Description

All of the previously described definitions are implemented in the SAGBI package.

Basic functions

Given a polynomial ring P and a list F of polynomials in P, one can compute the reduced SAGBI basis of $K$[F] (with respect to the term ordering given by P) using the function SB.SAGBI - as long as a finite one exists.

SB.SAGBI(F);

Note that this function probably runs into an infinite loop if no finite SAGBI basis exists. This can be avoided using the function SB.SAGBITimeout. Given a positive integer s, one can type in

SB.SAGBITimeout(F,s);

which does the same as SB.SAGBI(F), but throws an error if the computation is not finished within s seconds. Given a polynomial f and a list of polynomials G, the function SB.ReductionStep can be used to compute a polynomial g with f${\xrightarrow {G} }_{\rm {s}}$g.

SB.ReductionStep(f,G);

If no such polynomial exists, then f is returned. This function is then used by the function SB.SDA, which is an implementation of the Subalgebra Division Algorithm described above.

SB.SDA(f,G)

Analogously to the CoCoA-5 function interreduced, the SAGBI package contains the function SB.Interreduced which takes as input a list of polynomials G and returns a list G' with $K[G]=K[G']$.

SB.Interreduced(G);

Special Functions for Graded Subalgebras

If G is a set of homogeneous polynomials, then there are additional functions one can use. Given a positive integerd, a d-truncated SAGBI basis can be computed using SB.TruncSAGBI.

SB.TruncSAGBI(G,d);

If additionally, the Hilbert series HS of the subalgebra $K[G]$ is given, one can call

SB.TruncSAGBI(G,d,HS);

which does the same as above, but computes the SAGBI basis Hilbert-driven, which may be a little bit faster. The function SB.SubalgebraHS can be applied to compute the Hilbert series of a graded subalgebra.

SB.SubalgebraHS(G);

If furthermore G is a set of terms, then the function

SB.TorRingHS(G);

can be used to compute its Hilbert series much more efficient.

The Subalgebra Data Type

The package also introduces a new Data type, i.e. a record tagged with "$apcocoa/sagbi.Subalgebra". Given a polynomial ring P and a list of polynomials G from P, one can create the subalgebra $K[G]$ using the function SB.Subalgebra.

Use P ::= QQ[x,y,z];
G := [x^2+y*z,z];
S := SB.Subalgebra(P,G);

For details about the structure of this data type, see the function page. While nearly all functionalities of the SAGBI package can be used without touching this data type, it has many advantages to do so because it stores informations of previous computations, see the example below. This is also the reason why many of the getter functions need the subalgebra to be called by reference. The following getter function can be used to get informations about the subalgebra:

SB.GetCoeffRing(S); -- returns the coefficient ring
SB.GetGens(S); -- returns the set G
SB.GetID(S); -- returns the unique ID of S
SB.GetLTSA(ref S); -- returns the subalgebra K[LT(f) | f in S]
SB.GetRing(S); -- returns P
SB.GetSAGBI(ref S); -- returns the reduced SAGBI basis of S (if a finite one exists)

If additionally, G is a set of homogeneous polynomials, one can call the following getter functions:

SB.GetHS(ref S); -- returns the Hilbert Series of S
SB.GetTruncSAGBI(ref S,d); -- returns a d-truncated SAGBI basis of S
SB.GetTruncDeg(S); -- returns the truncation degree of the currently stored SAGBI basis

To optain a $K$-vector space basis of the set $K[G]_{d}$ of all homogeneous polynomials of degree $d$ in $K[G]$, the function SB.GetInDeg can be used:

SB.GetInDeg(S);

Testing Subalgebra Membership

Let f be a polynomial in the polynomial ring P, let G be a list of polynomials in P and let S be a subalgebra generated by G. Then the SAGBI package provides four functions to check whether f is an element of the subalgebra S:

SB.IsInSubalgebra(f,G);
SB.IsInSA(f,S);

If G is a list of homogeneous polynomials, the following functions can also be used:

SB.IsInSubalgebra_SAGBI(f,G);
SB.IsInSA_SAGBI(f,ref S);

While the first two functions test the membership using implicitization, these two functions use truncated SAGBI bases for the membership test, which may be more efficient. It depends on the application which of these two possibilities is the fastest one.

Example for the Subalgebra Data Type

So what advantages does the Subalgebra data type have? Consider the following example.

Use P ::= QQ[x,y,z];
G := [x^2 -z^2,  x*y +z^2,  y^2 -2*z^2];
L := SB.SAGBI(G);
f := x^10*y^2 +x^6*y^6 -2*x^10*z^2 -5*x^8*y^2*z^2 +6*x^5*y^5*z^2 +10*x^8*z^4 +10*x^6*y^2*z^4 +15*x^4*y^4*z^4 -20*x^6*z^6 -10*x^4*y^2*z^6 +20*x^3*y^3*z^6 +20*x^4*z^8 +20*x^2*y^2*z^8 -10*x^2*z^10 +6*x*y*z^10 -y^2*z^10 +3*z^12;
b := SB.IsInSubalgebra(f,G);
h := SB.SubalgebraHS(G);

Here, first a SAGBI basis is computed, then the subalgebra membership is tested using implicitization and at the end, the Hilbert series of K[G] is computed. But after computing a SAGBI basis, one could also test the Subalgebra membership using the Subalgebra Division Algorithm and compute the Hilbert Series of . The Subalgebra data type does this automatically. Instead of the code above, we can write the following:

Use P ::= QQ[x,y,z];
G := [x^2 -z^2,  x*y +z^2,  y^2 -2*z^2];
S := SB.Subalgebra(P,G);
L := SB.GetSAGBI(ref S);
f := x^10*y^2 +x^6*y^6 -2*x^10*z^2 -5*x^8*y^2*z^2 +6*x^5*y^5*z^2 +10*x^8*z^4 +10*x^6*y^2*z^4 +15*x^4*y^4*z^4 -20*x^6*z^6 -10*x^4*y^2*z^6 +20*x^3*y^3*z^6 +20*x^4*z^8 +20*x^2*y^2*z^8 -10*x^2*z^10 +6*x*y*z^10 -y^2*z^10 +3*z^12;
b := SB.IsInSA(f,ref S);
h := SB.GetHS(ref S);

While this is only a simple example, the second code is much faster. At the time this is written, the second computation is approximately two times as fast as the first one.