Package zerodim: Difference between revisions

From ApCoCoAWiki
← Older edit
LongLe (talk | contribs)
115 edits
No edit summary
LongLe (talk | contribs)
115 edits
No edit summary
 
(23 intermediate revisions by the same user not shown)
Line 1: Line 1:
{{Version|2|[[:Category:ApCoCoA-1:Package ZeroDim]]}}
{{Version|2|[[:Category:ApCoCoA-1:Package ZeroDim]]}}
This page describes the zerodim package. The package contains various functions for computing algebraic invariants of zero-dimensional schemes and related computations. For a complete list of functions, see [[:Category:Package zerodim]].
This page describes the <code>zerodim</code> package. The package contains various functions for computing algebraic invariants of zero-dimensional schemes and related computations. For a complete list of functions, see also [[:Category:Package zerodim]].






== Mathematical Definitions ==
== Algebraic Invariants ==
Let <math>K</math> be a field and let <math>P = K[x_1,\ldots,x_n]</math> be the polynomial ring over <math>K</math> in <math>n</math> indeterminates. Most of the definitions here are taken from the book [https://staff.fim.uni-passau.de/kreuzer/cabook2/CCA2.html Computational Commutative Algebra 2] by Martin Kreuzer and Lorenzo Robbiano.
Let <math>K</math> be a field, let <math>P = K[x_1,\ldots,x_n]</math> be the polynomial ring over <math>K</math> in <math>n</math> indeterminates, and let <math>I</math> be a 0-dimensional ideal of <math>P</math> and <math>R=P/I</math>. Then <math>I</math> defines a 0-dimensional scheme <math>X</math> in the affine <math>n</math>-space.
Consider the canonical multiplication map
:<math>\mu: R^e=R\otimes_K R \longrightarrow R, (f,g)\mapsto fg</math>
and its kernel <math>J=\mathrm{Ker}(\mu)</math>. Then <math>J/J^2</math> is a finitely generated <math>R</math>-module
and <math>\mathrm{Ann}_{R^e}(J)</math> is an ideal of the enveloping algebra <math>R^e</math>.


=== Subalgebras ===
* The ideal <math>\vartheta_N(R/K) :=\mu(\mathrm{Ann}_{R^e}(J))</math> is called the <em>Noether different</em> of the algebra <math>R/K</math>.
A subset <math>S \subseteq P</math> is called a <math>K</math>-'''subalgebra''' of <math>P</math>, if
* The <math>R</math>-module <math>\Omega^1_{R/K}:=J/J^2</math> is called the <em>module of Kaehler differential 1-forms</em> of the algebra <math>R/K</math>.
*<math>K \subseteq S</math> and
* The <math>K</math>-linear map <math>d:R\rightarrow\Omega^1_{R/K}, f\mapsto f\otimes 1-1\otimes f + J^2</math>, is called the <em>universal derivation</em> of the algebra <math>R/K</math>.
*<math>S</math> is closed under addition and multiplication.
* For <math>m\ge 0</math>, the exterior power <math>\Omega^m_{R/K}:=\wedge_R^m \Omega^1_{R/K}</math> is called the <em>module of Kaehler differential m-forms</em> of the algebra <math>R/K</math>.
For a subset <math>F = \{f_1,\ldots,f_s\} \subseteq P</math>, we write
* For <math>m\ge 0</math> the <math>m</math>-th Fitting ideal <math>\vartheta_X^{(m)}(R/K)</math> of the module of Kaehler differential 1-forms <math>\Omega^1_{R/K}</math> is called the <em>Kaehler different</em> of the algebra <math>R/K</math>.
:<math>K[F] = K[f_1,\ldots,f_s] = \{p(f_1,\ldots,f_s) \mid p \in K[y_1,\ldots,y_s]\}</math>
where <math>K[y_1,\ldots,y_s]</math> is a new polynomial ring in <math>s</math> indeterminates for the '''<math>K</math>-subalgebra of <math>P</math> generated by <math>F</math>'''.


=== SAGBI bases ===
More generally, for any <math>K</math>-algebra <math>T/S</math>, we can define the Noether different, module of Kaehler differential m-forms, Kaehler different of <math>T/S</math> analogously. In particular, if <math>T/S</math> is graded, then all these invariants are also graded.  
Let <math>\sigma</math> be a [[HowTo:Term Orderings|term ordering]] on <math>P</math> and let <math>S</math> be a <math>K</math>-subalgebra of <math>P</math>. A set <math>G \subseteq S</math> is called a <math>\sigma</math>-SAGBI basis of <math>S</math> if <math>K[{\rm LT}_\sigma(f) \mid f \in S] = K[{\rm LT}_\sigma(f) \mid f \in G]</math>.


If <math>S</math> is a [[HowTo:Gradings|graded subalgebra]] and <math>d \in \mathbb{N}</math>, then a set <math>G_{\leq d}</math> is called a '''<math>d</math>-truncated <math>\sigma</math>-SAGBI basis of <math>S</math>''', if
Now let us embed the scheme <math>X</math> in the projective <math>n</math>-space via <math>X \subseteq D_+(x_0) \subseteq\mathbb{P}^n</math>, where <math>x_0</math> is a new indeterminate. Set <math>S:=P[x_0] = K[x_0,\dots,x_n]</math> and equip <math>S</math> with the standard grading. The homogeneous vanishing ideal of <math>X</math> is the homogenization of <math>I</math> with respect to <math>x_0</math> and denoted by <math>I_X</math>, and the homogeneous coordinate ring of <math>X</math> is the graded 1-dimensional ring <math>R_X = S/I_X</math>. In this case <math>K[x_0]</math> is the Noetherian normalization of <math>R_X</math>, and hence we can define the above invariants for the graded algebra <math>R_X/K[x_0]</math>. Moreover, we have the following further invariants.
:<math>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}].</math>
Equivalently, a set <math>G_{\leq d}</math> is a <math>d</math>-truncated <math>\sigma</math>-SAGBI basis of <math>S</math> if there is a <math>\sigma</math>-SAGBI basis of <math>S</math> with <math>G_{\leq d} = \{g \in G \mid \deg(g) \leq d\}</math>.


=== The Subalgebra Rewrite Relation ===
* The graded <math>R_X</math>-module <math>\omega_{R_X} = \mathrm{Hom}_{K[x_0]}(R,K[x_0])(-1)</math> is called the <em>canonical module</em> of the algebra <math>R_X/K[x_0]</math>.  
Let <math>G \subseteq P</math> be a set of non-zero polynomials. Furthermore, let <math>\sigma</math> be a term ordering on <math>\mathbb{T}^n</math>.
* The graded locolization <math>Q^h(R_X)</math> of <math>R_X</math> at <math>x_0</math> is called the <em>homogeneous ring of quotients</em> of <math>R_X</math>.
* For <math>f, g \in P \setminus \{0\}</math>, we say that <math>f</math> '''subalgebra reduces to <math>g</math> in one step''' if there are <math>f_1,\ldots,f_s \in G</math>, a term <math>t \in \mathbb{T}^s</math>, and a constant <math>c \in K</math> such that <math>g = f - c t(f_1,\ldots,f_s)</math> and <math>{\rm LT}_\sigma(t(f_1,\ldots,f_s))</math> is not anymore in <math>{\operatorname{Supp}}(g)</math>. The path from <math>f</math> to <math>g</math> is then called a '''subalgebra reduction step''' and denoted by <math>f {\xrightarrow{G}}_{\rm ss} g</math>.
* When the scheme <math>X</math> is reduced (more general, locally Gorenstein), there is an injection <math>\omega_{R_X}\hookrightarrow  Q^h(R_X)</math> and the inverse of <math>\omega_{R_X}</math> in <math>Q^h(R_X)</math> is called the <em>Dedekind different</em> of <math>R_X/K[x_0]</math>.
* The transitive closure of the relation <math>{\xrightarrow{G}}_{\rm ss}</math> is denoted by <math>{\xrightarrow{G}}_{\rm s}</math> and called the '''subalgebra rewrite relation''' defined by <math>G</math>. If there are <math>f, g \in P</math> with <math>f {\xrightarrow{G}}_{\rm s} g</math>, we say that <math>f</math> '''subalgebra reduces''' to <math>g</math>.
* If <math>g \in P</math> such that there is no <math>h \in P</math> with <math>h \neq g</math> and <math>g {\xrightarrow{G}}_{\rm ss} h</math>, then <math>g</math> is called '''irreducible''' with respect to the relation <math>{\xrightarrow{G}}_{\rm s}</math>. Sometimes we may also just write that <math>g</math> is irreducible with respect to <math>G</math>.
A set <math>G \subseteq P</math> is called '''interreduced''' if every element <math>g \in G</math> is monic and irreducible with respect to <math>G \setminus \{g\}</math>. If <math>G</math> is a <math>\sigma</math>-SAGBI basis of <math>K[G]</math> which is interreduced, then it is called a '''reduced <math>\sigma</math>-SAGBI basis'''. Analogously to reduced Gröbner bases, it can be shown that every <math>K</math>-subalgebra has a unique reduced <math>\sigma</math>-SAGBI basis.


=== The Subalgebra Division Algorithm ===
Many interesting properties of the scheme <math>X</math> are reflexed by the algebraic structure of the above invariants.
Let <math>\sigma</math> be a term ordering on <math>\mathbb{T}^n</math>, <math>f \in P</math> and <math>G = \{f_1,\ldots,f_s\} \subseteq P</math> be a set of non-zero polynomials. Consider the following sequence of instructions.
# Set <math>g := f</math>.
# Write <math>g = c_1t_1 + \cdots + c_m t_m</math> with <math>t_i \in \mathbb{T}^n</math>, <math>c_i \in K</math> for <math>i = 1,\ldots,m</math>, and <math>t_1 \geq_\sigma \cdots \geq_\sigma t_m</math>. Set <math>k := 1</math>.
# If <math>k = m+1</math>, stop and return <math>g</math>. Otherwise, check whether there is a term <math>t \in \mathbb{T}^s</math> such that <math>t_k = t({\rm LT}_\sigma(f_1),\ldots,{\rm LT}_\sigma(f_s))</math>. If there is one, set <math>c = t({\rm LC}_\sigma(f_1),\ldots,{\rm LC}_\sigma(f_s))</math>, replace <math>g</math> by <math>g - \frac{c_i}{c} t(f_1,\ldots,f_s)</math> and go to step~(2). If there is none, increase <math>k</math> by one and repeat this step.
This is an algorithm which returns a polynomial <math>g \in P</math> such that <math>f {\xrightarrow{G}}_{\rm s} g</math> and <math>g</math> is irreducible with respect to <math>{\xrightarrow{G}}_{\rm s}</math>.
This algorithm clearly computes a polynomial <math>g \in P</math> with <math>f {\xrightarrow{G}}_{\rm s} g</math> and <math>g</math> is irreducible with respect to <math>G</math>.


== Package Description ==
== Package Description ==
All of the previously described definitions are implemented in the SAGBI package.
The <code>zerodim</code> package provides functions for computing the introduced invariants of zero-dimensional schemes. In the graded case the package also provides functions for computations of the Hilbert functions of these invariants. Alias of the package is <code>ZD</code>.


=== Basic functions ===
=== List of main functions ===
Given a polynomial ring <code>P</code> and a list <code>F</code> of polynomials in <code>P</code>, one can compute the reduced SAGBI basis of <math>K</math>[<code>F</code>] (with respect to the term ordering given by <code>P</code>) using the function [[/SB.SAGBI/]] - as long as a finite one exists.
 
[[/MinQuotIdeal/]]
<pre>
MinQuotIdeal(P, I, J): computes a min. homog. system
          of generators of homog. ideal (I+J)/I.
    input: P=K[x[1..N]], I and J homog. ideals of P
    output: list of polys
</pre>
[[/AffineNoetherDiff/]]
<pre>
AffineNoetherDiff(P, I): computes a generating system";
          of the Noether different of algebra R/K, R=P/I";
    input: P=K[x[1..N]], I an ideal of P";
    output: list of polys";
</pre>
[[/NoetherDifferent/]]
<pre>
NoetherDifferent(P, I): computes a min.homog. gen. system
          of the Noether different of algebra R/K, R=P/I.
    input: P=K[x[1..N]], I an homog. ideal of P
    output: list of polys
</pre>
[[/NoetherDifferentRel/]]
<pre>
NoetherDifferentRel(P, Ix): computes a min.homog. gen. system
          of the Noether different of R/K[x[0]], R=P/Ix.
    input: P=K[x[0..N]], Ix vanishing ideal of a 0-dim scheme X
            in P^n_K such that intersect(X,Z(x[0])) is empty
    output: list of polys
</pre>
[[/HilbertNoetherDiff/]]
<pre>
HilbertNoetherDiff(P, I): computes the Hilbert function
          of the Noether different of R/K, R=P/I.
    input: P=K[x[1..N]], I an homog. ideal of P
    output: the Hilbert function
</pre>
[[/HilbertNoetherDiffRel/]]
<pre>
HilbertNoetherDiffRel(P, Ix): computes the Hilbert function
          of the Noether different of R/K[x[0]], R=P/Ix.
    input: P=K[x[0..N]], Ix vanishing ideal of a 0-dim scheme X
            in P^n_K such that intersect(X,Z(x[0])) is empty
    output: the Hilbert function
</pre>
[[/AffineKaehlerDiff/]]
<pre>
AffineKaehlerDiff(P,I,m): computes a generating system
          of the m-th Kaehler different of algebra R/K, R=P/I.
    input: P=K[x[1..N]], I an ideal of P, m non-neg integer
    output: list of polys
</pre>
[[/KaehlerDifferent/]]
<pre>
KaehlerDifferent(P,I,m): computes a min.homog.gen. system
          of the m-th Kaehler different of algebra R/K, R=P/I.
    input: P=K[x[1..N]], I an homog. ideal, m non-neg integer
    output: list of polys
</pre>
[[/KaehlerDifferentRel/]]
<pre>
KaehlerDifferentRel(P, Ix): computes a min. homog.gen. system
          of the Kaehler different of R/K[x[0]], R=P/Ix.
    input: P=K[x[0..N]], Ix vanishing ideal of a 0-dim scheme X
            in P^n_K such that intersect(X,Z(x[0])) is empty
    output: list of polys
</pre>
[[/HilbertKaehlerDiff/]]
<pre>
<pre>
SB.SAGBI(F);
HilbertKaehlerDiff(P,I,m): computes the Hilbert function
          of the m-th Kaehler different of R/K, R=P/I.
    input: P=K[x[1..N]], I an homog. ideal, m non-neg integer
    output: the Hilbert function
</pre>
</pre>
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 <code>s</code>, one can type in
[[/HilbertKaehlerDiffRel/]]
<pre>
<pre>
SB.SAGBITimeout(F,s);
HilbertKaehlerDiffRel(P, Ix): computes the Hilbert function
          of the Kaehler different of R/K[x[0]], R=P/Ix.
    input: P=K[x[0..N]], Ix vanishing ideal of a 0-dim scheme X
            in P^n_K such that intersect(X,Z(x[0])) is empty
    output: the Hilbert function
</pre>
</pre>
which does the same as <code>SB.SAGBI(F)</code>, but throws an error if the computation is not finished within <code>s</code> seconds.
[[/AffBMAlgo/]]
Given a polynomial <code>f</code> and a list of polynomials <code>G</code>, the function [[/SB.ReductionStep/]] can be used to compute a polynomial <code>g</code> with <code>f</code><math>{\xrightarrow{G}}_{\rm s}</math><code>g</code>.
<pre>
<pre>
SB.ReductionStep(f,G);
AffBMAlgo(LX,O): computes a list [GBasis,OrderIdeal,Separators]
          for a 0-dim ideal with its primary components LX.
    input: P=K[x[1..N]], LX list of 0-dim primary ideals
            q_j associated to a 0-dim ideal of P
            O list of K-bases of P/q_j
    output: [GBasis,OrderIdeal,Separators] of P/intersection(q_j)
</pre>
</pre>
If no such polynomial exists, then <code>f</code> is returned. This function is then used by the function [[/SB.SDA/]], which is an implementation of the Subalgebra Division Algorithm described above.
[[/DedekindDifferentRel/]]
<pre>SB.SDA(f,G)</pre>
Analogously to the CoCoA-5 function <code>interreduced</code>, the SAGBI package contains the function [[/SB.Interreduced/]] which takes as input a list of polynomials <code>G</code> and returns a list <code>G'</code> with <math>K[G] = K[G']</math>.
<pre>
<pre>
SB.Interreduced(G);
DedekindDifferentRel(P,Points): computes a min.homog.gen. system
          of the Dedekind different of R/K[x[0]], where R=P/Ix
          and Ix is the vanishing ideal of Points.
    input: P=K[x[0..N]], Points=list of points in P^n_K
            not in Z(x[0])
    output: list of polys
</pre>
</pre>
 
[[/HilbertDedekindDiffRel/]]
=== Special Functions for Graded Subalgebras ===
<pre>
If <code>G</code> is a set of [[HowTo:Gradings|homogeneous]] polynomials, then there are additional functions one can use. Given a positive integer<code>d</code>, a <code>d</code>-truncated SAGBI basis can be computed using [[/SB.TruncSAGBI/]].
HilbertDedekindDiffRel(P,Points): computes the Hilbert function
          of the Dedekind different of R/K[x[0]], where R=P/Ix
          and Ix is the vanishing ideal of Points.
    input: P=K[x[0..N]], Points=list of points in P^n_K
            not in Z(x[0])
    output: the Hilbert function
</pre>
[[/KaehlerDiffModule/]]
<pre>
KaehlerDiffModule(P, Ix, m): computes a submodule U of P^t
          such that the module of Kaehler differential m-form
          has Omega^m(R/K)=P^t/U, R=P/Ix, t=binom{n}{m}.
    input: P=K[x[1..N]], Ix a non-zero ideal, m non-neg integer
    output: submodule with generators
</pre>
[[/HilbertKDM/]]
<pre>
<pre>
SB.TruncSAGBI(G,d);
HilbertKDM(P, Ix, m): computes the Hilbert function of
          the module of Kaehler differential m-form.
    input: P=K[x[1..N]], Ix a non-zero homog. ideal, 0<m<n+1
    output: HF of Omega^m(R/K)
</pre>
</pre>
If additionally, the Hilbert series <code>HS</code> of the subalgebra <math>K[G]</math> is given, one can call
[[/KDMOfPoints/]]
<pre>
<pre>
SB.TruncSAGBI(G,d,HS);
KDMOfPoints(P,Points,m): computes a submodule U of P^t such that
          the module of Kaehler differential m-form has
          Omega^m(R/K)=P^t/U, R=P/I_Points, t=binom{n}{m}.
    input: P=K[x[1..N]], Points=list of points, m non-neg integer
    output: submodule with generators
</pre>
</pre>
which does the same as above, but computes the SAGBI basis Hilbert-driven, which may be a little bit faster.
[[/KDMOfProjectivePoints/]]
The function [[/SB.SubalgebraHS/]] can be applied to compute the Hilbert series of a graded subalgebra.
<pre>
<pre>
SB.SubalgebraHS(G);
KDMOfProjectivePoints(P,Points,m): computes a submodule U of P^t
          such that the module of Kaehler differential m-form has
          Omega^m(R/K)=P^t/U, R=P/I_Points, t=binom{n}{m}.
    input: P=K[x[1..N]], Points=list of projective points,
            m non-neg integer
    output: submodule with generators
</pre>
</pre>
If furthermore <code>G</code> is a set of terms, then the function
[[/KDMRel/]]
<pre>
<pre>
SB.TorRingHS(G);
KDMRel(P, Ix, m): computes a submodule U of P^t such that
          the module of Kaehler differential m-form of R/K[x[0]]
          has Omega^m(R/K[x[0]])=P^t/U, R=P/Ix, t=binom{n}{m}.
    input: P=K[x[0..N]], Ix a non-zero homog. ideal such that
            K[x[0]] is the Noetherian normalization of R,
            m non-neg integer
    output: submodule with generators
</pre>
</pre>
can be used to compute its Hilbert series much more efficient.
[[/HilbertKDMRel/]]
 
=== The Subalgebra Data Type ===
The package also introduces a new ''Data type'', i.e. a record tagged with <code>"$apcocoa/sagbi.Subalgebra"</code>. Given a polynomial ring <code>P</code> and a list of polynomials <code>G</code> from <code>P</code>, one can create the subalgebra <math>K[G]</math> using the function [[/SB.Subalgebra/]].
<pre>
<pre>
Use P ::= QQ[x,y,z];
HilbertKDMRel(P, Ix, m): computes the Hilbert function of
G := [x^2+y*z,z];
          the module of Kaehler differential m-form of R/K[x[0]].
S := SB.Subalgebra(P,G);
    input: P=K[x[0..N]], Ix a non-zero homog. ideal such that
            K[x[0]] is the Noetherian normalization of R,
            m non-neg integer";
    output: HF of Omega^m(R/K[x_0])
</pre>
</pre>
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, <code>G</code> is a set of homogeneous polynomials, one can call the following getter functions:
=== Examples for computations ===
[[/SB.GetHS/]](ref S); -- returns the Hilbert Series of S
Now let us apply the <code>zerodim</code> package to some concrete examples. Recall that the alias of the package is <code>ZD</code>, and so to call a function from this package in computation one uses [[/ZD.functions-name/]].
[[/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 <math>K</math>-vector space basis of the set <math>K[G]_d</math> of all homogeneous polynomials of degree <math>d</math> in <math>K[G]</math>, the function [[/SB.GetInDeg/]] can be used:
[[/SB.GetInDeg/]](S);


=== Testing Subalgebra Membership ===
Consider the first example, where X is the scheme defined by the homogeneous ideal Ix.
Let <code>f</code> be a polynomial in the polynomial ring <code>P</code>, let <code>G</code> be a list of polynomials in <code>P</code> and let <code>S</code> be a subalgebra generated by <code>G</code>. Then the SAGBI package provides four functions to check whether <code>f</code> is an element of the subalgebra <code>S</code>:
<pre>
  [[/SB.IsInSubalgebra/]](f,G);
Use P ::= QQ[X[0..2]];
  [[/SB.IsInSA/]](f,S);
Ix := ideal(X[0]*X[1] -X[1]^2, X[1]^2*X[2] -X[1]*X[2]^2, 2*X[0]^2*X[2] -3*X[0]*X[2]^2 +X[2]^3);
If <code>G</code> is a list of homogeneous polynomials, the following functions can also be used:
</pre>
[[/SB.IsInSubalgebra_SAGBI/]](f,G);
Then we calculate the differents of X as follows:
[[/SB.IsInSA_SAGBI/]](f,ref S);
<pre>
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.
-- Computes the Noether different of R/K:
ZD.NoetherDifferent(P,Ix);
  []
-- Computes the Noether different of R/K[x_0]:
ZD.NoetherDifferentRel(P,Ix);
  [X[1]^3 -2*X[1]*X[2]^2, 2*X[0]^3 -6*X[0]*X[2]^2 -2*X[1]*X[2]^2 +3*X[2]^3,  X[2]^4]
-- Computes the Hilbert function of the Noether different of R/K[x_0]:
ZD.HilbertNoetherDiffRel(P,Ix);
  H(0) = 0
  H(1) = 0
  H(2) = 0
  H(3) = 2
  H(t) = 5, for t >= 4
-- Computes the Kaehler different of R/K[x_0]:
ZD.KaehlerDifferentRel(P,Ix);
  [X[1]^3 -2*X[1]*X[2]^2, 2*X[0]^3 -6*X[0]*X[2]^2 -2*X[1]*X[2]^2 +3*X[2]^3,  X[2]^4]
-- Computes the Hilbert function of the Kaehler different of R/K[x_0]:
ZD.HilbertKaehlerDiffRel(P,Ix);
  H(0) = 0
  H(1) = 0
  H(2) = 0
  H(3) = 2
  H(t) = 5, for t >= 4
</pre>
The module of Kaehler differentials 1-forms of R/K is determined by a submodule U of P^3 which is computed by:
<pre>
U := ZD.KaehlerDiffModule(P,Ix,1); indent(U);
  SubmoduleRows(F, matrix([
    [X[1], X[0] -2*X[1], 0],
    [0, 2*X[1]*X[2] -X[2]^2, X[1]^2 -2*X[1]*X[2]],
    [4*X[0]*X[2] -3*X[2]^2, 0, 2*X[0]^2 -6*X[0]*X[2] +3*X[2]^2],
    [X[0]*X[1] -X[1]^2, 0, 0],
    [2*X[0]^2*X[2] -3*X[0]*X[2]^2 +X[2]^3, 0, 0],
    [0, X[0]*X[1] -X[1]^2, 0],
    [0, 2*X[0]^2*X[2] -3*X[0]*X[2]^2 +X[2]^3, 0],
    [0, 0, X[0]*X[1] -X[1]^2],
    [0, 0, X[1]^2*X[2] -X[1]*X[2]^2],
    [0, 0, 2*X[0]^2*X[2] -3*X[0]*X[2]^2 +X[2]^3]
  ]))
</pre>


=== Example for the Subalgebra Data Type ===
Next, let us consider the example, where X is given by a set of 10 points:
So what advantages does the Subalgebra data type have? Consider the following example.
<pre>
<pre>
Use P ::= QQ[x,y,z];
Use P::=QQ[X[0..2]];
G := [x^2 -z^2,  x*y +z^2,  y^2 -2*z^2];
Points := [[1,1,0], [1,3,0], [1,1,1], [1,2,1], [1,3,1], [1,0,2], [1,1,2], [1,2,2], [1,3,2], [1,3,3]];
L := SB.SAGBI(G);
</pre>
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;
We can compute the Dedekind different of X and its Hilbert function by:
b := SB.IsInSubalgebra(f,G);
<pre>
h := SB.SubalgebraHS(G);
ZD.DedekindDifferentRel(P,Points);
  [X[2]^6,  X[1]*X[2]^5,  X[0]*X[2]^5,  X[1]^2*X[2]^4,  X[0]*X[1]*X[2]^4,   
    X[0]^2*X[2]^4,  X[1]^3*X[2]^3,  X[0]*X[1]^2*X[2]^3,  X[1]^6,  X[0]*X[1]^5]
ZD.HilbertDedekindDiffRel(P,Points);
  H(0) = 0
  H(1) = 0
  H(2) = 0
  H(3) = 0
  H(4) = 0
  H(5) = 0
  H(t) = 10, for t >= 6
</pre>
The module of Kaehler differential 3-forms of R/K can be computed by
<pre>
ZD.KDMOfProjectivePoints(P,Points,3);
  submodule(FreeModule(RingWithID(144, "QQ[X[0],X[1],X[2]]"), 1),
    [[(-1/2)*X[0]*X[1]^2 +(-19/27)*X[1]^3 +(-85/18)*X[0]^2*X[2] +(563/27)*X[0]*X[1]*X[2]
      +(85/27)*X[1]^2*X[2] +(-61/3)*X[0]*X[2]^2 +(-301/18)*X[1]*X[2]^2 +(47/3)*X[2]^3],
      [-X[0]^2*X[2] +(3/2)*X[0]*X[2]^2 +(-1/2)*X[2]^3], [-2*X[0]^2*X[1] +4*X[0]*X[1]^2  
      +(-4/3)*X[1]^3 +X[1]^2*X[2] +(-23/6)*X[0]*X[2]^2 +(-4/3)*X[1]*X[2]^2 +(13/6)*X[2]^3],
      [-X[0]^3 +(13/3)*X[0]*X[1]^2 +(-16/9)*X[1]^3 +(11/6)*X[1]^2*X[2] +(-253/36)*X[0]*X[2]^2
      +(-22/9)*X[1]*X[2]^2 +(143/36)*X[2]^3],
      [(40/9)*X[0]*X[1]^2 +(-52/27)*X[1]^3 +X[0]*X[1]*X[2] +(19/9)*X[1]^2*X[2]
      +(-563/54)*X[0]*X[2]^2 +(-85/27)*X[1]*X[2]^2 +(301/54)*X[2]^3],
      [2*X[0]*X[1]*X[2] -2*X[0]*X[2]^2 +(-3/2)*X[1]*X[2]^2 +(3/2)*X[2]^3],
      [3*X[0]^2*X[2] +(-11/3)*X[0]*X[2]^2 +X[2]^3],
      [2*X[0]*X[1]^2 +(-4/3)*X[1]^3 -2*X[0]*X[2]^2 +(23/6)*X[1]*X[2]^2 +(-5/2)*X[2]^3],
      [3*X[0]^2*X[1] +(-13/9)*X[1]^3 +(-11/3)*X[0]*X[2]^2 +(253/36)*X[1]*X[2]^2 +(-55/12)*X[2]^3],
      [4*X[0]^3 +(-40/27)*X[1]^3 +(-1/2)*X[1]^2*X[2] +(-85/18)*X[0]*X[2]^2 +(563/54)*X[1]*X[2]^2 +(-61/9)*X[2]^3]
    ])
</pre>
</pre>


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.
[[Category:Package zerodim]]
 
[[Category:Package alggeozd]]
[[Category:Package sagbi]]
[[Category:Package borderbasis]]
[[Category:ApCoCoA Packages]]
[[Category:ApCoCoA Packages]]

Latest revision as of 23:25, 17 November 2022

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

This page describes the zerodim package. The package contains various functions for computing algebraic invariants of zero-dimensional schemes and related computations. For a complete list of functions, see also Category:Package zerodim.


Algebraic Invariants

Let K be a field, let P=K[x1,…,xn] be the polynomial ring over K in n indeterminates, and let I be a 0-dimensional ideal of P and R=P/I. Then I defines a 0-dimensional scheme X in the affine n-space. Consider the canonical multiplication map

μ:Re=R⊗KR⟶R,(f,g)↦fg

and its kernel J=Ker(μ). Then J/J2 is a finitely generated R-module and AnnRe(J) is an ideal of the enveloping algebra Re.

  • The ideal ϑN(R/K):=μ(AnnRe(J)) is called the Noether different of the algebra R/K.
  • The R-module ΩR/K1:=J/J2 is called the module of Kaehler differential 1-forms of the algebra R/K.
  • The K-linear map d:R→ΩR/K1,f↦f⊗1−1⊗f+J2, is called the universal derivation of the algebra R/K.
  • For m≥0, the exterior power ΩR/Km:=∧RmΩR/K1 is called the module of Kaehler differential m-forms of the algebra R/K.
  • For m≥0 the m-th Fitting ideal ϑX(m)(R/K) of the module of Kaehler differential 1-forms ΩR/K1 is called the Kaehler different of the algebra R/K.

More generally, for any K-algebra T/S, we can define the Noether different, module of Kaehler differential m-forms, Kaehler different of T/S analogously. In particular, if T/S is graded, then all these invariants are also graded.

Now let us embed the scheme X in the projective n-space via X⊆D+(x0)⊆ℙn, where x0 is a new indeterminate. Set S:=P[x0]=K[x0,…,xn] and equip S with the standard grading. The homogeneous vanishing ideal of X is the homogenization of I with respect to x0 and denoted by IX, and the homogeneous coordinate ring of X is the graded 1-dimensional ring RX=S/IX. In this case K[x0] is the Noetherian normalization of RX, and hence we can define the above invariants for the graded algebra RX/K[x0]. Moreover, we have the following further invariants.

  • The graded RX-module ωRX=HomK[x0](R,K[x0])(−1) is called the canonical module of the algebra RX/K[x0].
  • The graded locolization Qh(RX) of RX at x0 is called the homogeneous ring of quotients of RX.
  • When the scheme X is reduced (more general, locally Gorenstein), there is an injection ωRX↪Qh(RX) and the inverse of ωRX in Qh(RX) is called the Dedekind different of RX/K[x0].

Many interesting properties of the scheme X are reflexed by the algebraic structure of the above invariants.

Package Description

The zerodim package provides functions for computing the introduced invariants of zero-dimensional schemes. In the graded case the package also provides functions for computations of the Hilbert functions of these invariants. Alias of the package is ZD.

List of main functions

MinQuotIdeal 

MinQuotIdeal(P, I, J): computes a min. homog. system
          of generators of homog. ideal (I+J)/I.
     input: P=K[x[1..N]], I and J homog. ideals of P
     output: list of polys

AffineNoetherDiff 

AffineNoetherDiff(P, I): computes a generating system";
          of the Noether different of algebra R/K, R=P/I";
     input: P=K[x[1..N]], I an ideal of P";
     output: list of polys";

NoetherDifferent 

NoetherDifferent(P, I): computes a min.homog. gen. system
          of the Noether different of algebra R/K, R=P/I.
     input: P=K[x[1..N]], I an homog. ideal of P
     output: list of polys

NoetherDifferentRel 

NoetherDifferentRel(P, Ix): computes a min.homog. gen. system
          of the Noether different of R/K[x[0]], R=P/Ix.
     input: P=K[x[0..N]], Ix vanishing ideal of a 0-dim scheme X
            in P^n_K such that intersect(X,Z(x[0])) is empty
     output: list of polys

HilbertNoetherDiff 

HilbertNoetherDiff(P, I): computes the Hilbert function
          of the Noether different of R/K, R=P/I.
     input: P=K[x[1..N]], I an homog. ideal of P
     output: the Hilbert function

HilbertNoetherDiffRel 

HilbertNoetherDiffRel(P, Ix): computes the Hilbert function
          of the Noether different of R/K[x[0]], R=P/Ix.
     input: P=K[x[0..N]], Ix vanishing ideal of a 0-dim scheme X
            in P^n_K such that intersect(X,Z(x[0])) is empty
     output: the Hilbert function

AffineKaehlerDiff 

AffineKaehlerDiff(P,I,m): computes a generating system
          of the m-th Kaehler different of algebra R/K, R=P/I.
     input: P=K[x[1..N]], I an ideal of P, m non-neg integer
     output: list of polys

KaehlerDifferent 

KaehlerDifferent(P,I,m): computes a min.homog.gen. system
          of the m-th Kaehler different of algebra R/K, R=P/I.
     input: P=K[x[1..N]], I an homog. ideal, m non-neg integer
     output: list of polys

KaehlerDifferentRel 

KaehlerDifferentRel(P, Ix): computes a min. homog.gen. system
          of the Kaehler different of R/K[x[0]], R=P/Ix.
     input: P=K[x[0..N]], Ix vanishing ideal of a 0-dim scheme X
            in P^n_K such that intersect(X,Z(x[0])) is empty
     output: list of polys

HilbertKaehlerDiff 

HilbertKaehlerDiff(P,I,m): computes the Hilbert function
          of the m-th Kaehler different of R/K, R=P/I.
     input: P=K[x[1..N]], I an homog. ideal, m non-neg integer
     output: the Hilbert function

HilbertKaehlerDiffRel 

HilbertKaehlerDiffRel(P, Ix): computes the Hilbert function
          of the Kaehler different of R/K[x[0]], R=P/Ix.
     input: P=K[x[0..N]], Ix vanishing ideal of a 0-dim scheme X
             in P^n_K such that intersect(X,Z(x[0])) is empty
     output: the Hilbert function

AffBMAlgo 

AffBMAlgo(LX,O): computes a list [GBasis,OrderIdeal,Separators]
          for a 0-dim ideal with its primary components LX.
     input: P=K[x[1..N]], LX list of 0-dim primary ideals
            q_j associated to a 0-dim ideal of P
            O list of K-bases of P/q_j
     output: [GBasis,OrderIdeal,Separators] of P/intersection(q_j)

DedekindDifferentRel 

DedekindDifferentRel(P,Points): computes a min.homog.gen. system
          of the Dedekind different of R/K[x[0]], where R=P/Ix
          and Ix is the vanishing ideal of Points.
     input: P=K[x[0..N]], Points=list of points in P^n_K
            not in Z(x[0])
     output: list of polys

HilbertDedekindDiffRel 

HilbertDedekindDiffRel(P,Points): computes the Hilbert function
          of the Dedekind different of R/K[x[0]], where R=P/Ix
          and Ix is the vanishing ideal of Points.
     input: P=K[x[0..N]], Points=list of points in P^n_K
            not in Z(x[0])
     output: the Hilbert function

KaehlerDiffModule 

KaehlerDiffModule(P, Ix, m): computes a submodule U of P^t
          such that the module of Kaehler differential m-form
          has Omega^m(R/K)=P^t/U, R=P/Ix, t=binom{n}{m}.
     input: P=K[x[1..N]], Ix a non-zero ideal, m non-neg integer
     output: submodule with generators

HilbertKDM 

HilbertKDM(P, Ix, m): computes the Hilbert function of
          the module of Kaehler differential m-form.
     input: P=K[x[1..N]], Ix a non-zero homog. ideal, 0<m<n+1
     output: HF of Omega^m(R/K)

KDMOfPoints 

KDMOfPoints(P,Points,m): computes a submodule U of P^t such that
          the module of Kaehler differential m-form has
          Omega^m(R/K)=P^t/U, R=P/I_Points, t=binom{n}{m}.
     input: P=K[x[1..N]], Points=list of points, m non-neg integer
     output: submodule with generators

KDMOfProjectivePoints 

KDMOfProjectivePoints(P,Points,m): computes a submodule U of P^t
          such that the module of Kaehler differential m-form has
          Omega^m(R/K)=P^t/U, R=P/I_Points, t=binom{n}{m}.
     input: P=K[x[1..N]], Points=list of projective points,
            m non-neg integer
     output: submodule with generators

KDMRel 

KDMRel(P, Ix, m): computes a submodule U of P^t such that
          the module of Kaehler differential m-form of R/K[x[0]]
          has Omega^m(R/K[x[0]])=P^t/U, R=P/Ix, t=binom{n}{m}.
     input: P=K[x[0..N]], Ix a non-zero homog. ideal such that
            K[x[0]] is the Noetherian normalization of R,
            m non-neg integer
     output: submodule with generators

HilbertKDMRel 

HilbertKDMRel(P, Ix, m): computes the Hilbert function of
          the module of Kaehler differential m-form of R/K[x[0]].
     input: P=K[x[0..N]], Ix a non-zero homog. ideal such that
            K[x[0]] is the Noetherian normalization of R,
            m non-neg integer";
     output: HF of Omega^m(R/K[x_0])

Examples for computations

Now let us apply the zerodim package to some concrete examples. Recall that the alias of the package is ZD, and so to call a function from this package in computation one uses ZD.functions-name.

Consider the first example, where X is the scheme defined by the homogeneous ideal Ix. 

Use P ::= QQ[X[0..2]];
Ix := ideal(X[0]*X[1] -X[1]^2, X[1]^2*X[2] -X[1]*X[2]^2, 2*X[0]^2*X[2] -3*X[0]*X[2]^2 +X[2]^3);

Then we calculate the differents of X as follows: 

-- Computes the Noether different of R/K:
ZD.NoetherDifferent(P,Ix); 
   []
-- Computes the Noether different of R/K[x_0]:
ZD.NoetherDifferentRel(P,Ix); 
   [X[1]^3 -2*X[1]*X[2]^2,  2*X[0]^3 -6*X[0]*X[2]^2 -2*X[1]*X[2]^2 +3*X[2]^3,  X[2]^4]
-- Computes the Hilbert function of the Noether different of R/K[x_0]:
ZD.HilbertNoetherDiffRel(P,Ix);
   H(0) = 0
   H(1) = 0
   H(2) = 0
   H(3) = 2
   H(t) = 5, for t >= 4
-- Computes the Kaehler different of R/K[x_0]:
ZD.KaehlerDifferentRel(P,Ix);
   [X[1]^3 -2*X[1]*X[2]^2,  2*X[0]^3 -6*X[0]*X[2]^2 -2*X[1]*X[2]^2 +3*X[2]^3,  X[2]^4]
-- Computes the Hilbert function of the Kaehler different of R/K[x_0]:
ZD.HilbertKaehlerDiffRel(P,Ix);
   H(0) = 0
   H(1) = 0
   H(2) = 0
   H(3) = 2
   H(t) = 5, for t >= 4

The module of Kaehler differentials 1-forms of R/K is determined by a submodule U of P^3 which is computed by: 

U := ZD.KaehlerDiffModule(P,Ix,1); indent(U);
   SubmoduleRows(F, matrix([
     [X[1], X[0] -2*X[1], 0],
     [0, 2*X[1]*X[2] -X[2]^2, X[1]^2 -2*X[1]*X[2]],
     [4*X[0]*X[2] -3*X[2]^2, 0, 2*X[0]^2 -6*X[0]*X[2] +3*X[2]^2],
     [X[0]*X[1] -X[1]^2, 0, 0],
     [2*X[0]^2*X[2] -3*X[0]*X[2]^2 +X[2]^3, 0, 0],
     [0, X[0]*X[1] -X[1]^2, 0],
     [0, 2*X[0]^2*X[2] -3*X[0]*X[2]^2 +X[2]^3, 0],
     [0, 0, X[0]*X[1] -X[1]^2],
     [0, 0, X[1]^2*X[2] -X[1]*X[2]^2],
     [0, 0, 2*X[0]^2*X[2] -3*X[0]*X[2]^2 +X[2]^3]
   ]))

Next, let us consider the example, where X is given by a set of 10 points: 

Use P::=QQ[X[0..2]];
Points := [[1,1,0], [1,3,0], [1,1,1], [1,2,1], [1,3,1], [1,0,2], [1,1,2], [1,2,2], [1,3,2], [1,3,3]];

We can compute the Dedekind different of X and its Hilbert function by: 

ZD.DedekindDifferentRel(P,Points);
   [X[2]^6,  X[1]*X[2]^5,  X[0]*X[2]^5,  X[1]^2*X[2]^4,  X[0]*X[1]*X[2]^4,  
    X[0]^2*X[2]^4,  X[1]^3*X[2]^3,  X[0]*X[1]^2*X[2]^3,  X[1]^6,  X[0]*X[1]^5]
ZD.HilbertDedekindDiffRel(P,Points);
   H(0) = 0
   H(1) = 0
   H(2) = 0
   H(3) = 0
   H(4) = 0
   H(5) = 0
   H(t) = 10, for t >= 6

The module of Kaehler differential 3-forms of R/K can be computed by 

ZD.KDMOfProjectivePoints(P,Points,3);
   submodule(FreeModule(RingWithID(144, "QQ[X[0],X[1],X[2]]"), 1), 
     [[(-1/2)*X[0]*X[1]^2 +(-19/27)*X[1]^3 +(-85/18)*X[0]^2*X[2] +(563/27)*X[0]*X[1]*X[2] 
       +(85/27)*X[1]^2*X[2] +(-61/3)*X[0]*X[2]^2 +(-301/18)*X[1]*X[2]^2 +(47/3)*X[2]^3], 
      [-X[0]^2*X[2] +(3/2)*X[0]*X[2]^2 +(-1/2)*X[2]^3], [-2*X[0]^2*X[1] +4*X[0]*X[1]^2 
       +(-4/3)*X[1]^3 +X[1]^2*X[2] +(-23/6)*X[0]*X[2]^2 +(-4/3)*X[1]*X[2]^2 +(13/6)*X[2]^3], 
      [-X[0]^3 +(13/3)*X[0]*X[1]^2 +(-16/9)*X[1]^3 +(11/6)*X[1]^2*X[2] +(-253/36)*X[0]*X[2]^2 
       +(-22/9)*X[1]*X[2]^2 +(143/36)*X[2]^3], 
      [(40/9)*X[0]*X[1]^2 +(-52/27)*X[1]^3 +X[0]*X[1]*X[2] +(19/9)*X[1]^2*X[2] 
       +(-563/54)*X[0]*X[2]^2 +(-85/27)*X[1]*X[2]^2 +(301/54)*X[2]^3], 
      [2*X[0]*X[1]*X[2] -2*X[0]*X[2]^2 +(-3/2)*X[1]*X[2]^2 +(3/2)*X[2]^3], 
      [3*X[0]^2*X[2] +(-11/3)*X[0]*X[2]^2 +X[2]^3], 
      [2*X[0]*X[1]^2 +(-4/3)*X[1]^3 -2*X[0]*X[2]^2 +(23/6)*X[1]*X[2]^2 +(-5/2)*X[2]^3], 
      [3*X[0]^2*X[1] +(-13/9)*X[1]^3 +(-11/3)*X[0]*X[2]^2 +(253/36)*X[1]*X[2]^2 +(-55/12)*X[2]^3], 
      [4*X[0]^3 +(-40/27)*X[1]^3 +(-1/2)*X[1]^2*X[2] +(-85/18)*X[0]*X[2]^2 +(563/54)*X[1]*X[2]^2 +(-61/9)*X[2]^3]
     ])
Retrieved from "https://app.apcocoa.uni-passau.de/wiki/index.php?title=Package_zerodim&oldid=16395"