Difference between revisions of "Package zerodim"

From ApCoCoAWiki
 
(25 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. 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]].
  
This package contains various functions for computing algebraic invariants of zero-dimensional schemes and related computations.
 
  
The basic idea behind this package is to make the linear optimization program GLPK usable in/with ApCoCoA. The package GLPK contains various functions that let you make use of the GLPK library, rather the stand-alone LP/MIP Solver glpsol.
 
  
<em>Important</em>: For usage under linux, the GLPK-Program glpsol must be in the ApCoCoA package directory under <code>packages/binaries/glpk/examples/glpsol</code> and you must have the permissions to read and write in this directory. For Windows, the glsol.exe has to be in the folder <code>packages\binaries\glpk\w64\glpsol.exe</code>. If you installed ApCoCoA-2 together with the GUI, this should already be the case.
+
== Algebraic Invariants ==
 +
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>.
  
The source code of GLPK can be downloaded at [http://www.gnu.org/software/glpk/].
+
* 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>.
 +
* 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>.
 +
* 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>.
 +
* 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 <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>.
  
== Optimizing Linear Systems Of Equations ==
+
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.  
:''See also: [[/GLPK.LPSolve/]]
 
Let <math>n \in \mathbb{N}</math> and <math>P = \mathbb{Q}[x_1,\ldots,x_n]</math>. Let <math>f_1,\ldots,f_{s_1},g_1,\ldots,g_{s_2},h_1,\ldots,h_{s_3},c \in P</math> be linear polynomials and let <math>l_1,\ldots,l_n,u_1,\ldots,u_n \in \mathbb{Q} \cup \{- \infty,\infty\}</math>. Let <math>S</math> be the system of polynomial (in)equations
 
:<math>\left\{ \begin{array}{ccc}
 
  f_1(b) & = & 0 \\
 
  \vdots & \vdots & \vdots \\
 
  f_{s_1}(b) & = & 0 \\
 
  g_1(b) & \leq & 0 \\
 
  \vdots & \vdots & \vdots \\
 
  g_{s_2}(b) & \leq & 0 \\
 
  h_1(b) & \geq & 0 \\
 
  \vdots & \vdots & \vdots \\
 
  h_{s_3}(b) & \geq & 0.
 
\end{array}\right.</math>
 
Then the function <code>[[/GLPK.LPSolve/]]</code> can be used to find solution <math>b = (b_1,\ldots,b_n) \in [l_1,u_1] \times \cdots \times [l_n,u_n]</math> to <math>S</math> such that <math>c(b) = \min\{c(x) \mid x \in [l_1,u_1] \times \cdots \times [l_n,u_n] \text{ is a solution to } S\}</math> in the following way.
 
  
*Let <code>EQ</code> be the list <math>\{f_1,\ldots,f_{s_1}\}</math>, let <code>LE</code> be the list <math>\{g_1,\ldots,g_{s_2}\}</math>, and let <code>GE</code> be the list <math>\{h_1,\ldots,h_{s_3}\}</math>.
+
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.
*Let <code>l</code> and <code>u</code> be the lists containing the upper and lower bounds for the <math>b_i</math> with <code>l[i]</code><math> = l_i</math> and <code>u[i]</code><math> = u_i</math>, if both are rational numbers. Instead of <math>\infty</math> and <math>- \infty</math>, write <code>l[i] = ""</code> or <code>u[i] = ""</code>. Set <code>B := [ [l[1],u[1]], [l[2],u[2]], ..., [l[n],u[n]] ]</code>.
 
*Choose a string <code>Method</code> from <code>[ "InterP", "Simplex" ]</code> depending on the method you want GLPK to use for solving the problem (<code>"InterP"</code> stands for the inter-point-method and <code>"Simplex"</code> for the simplex method)
 
*Choose a string <code>MinMax</code> from <code>[ "Min", "Max" ]</code> depending on whether you want <math>b</math> to fulfill <math>c(b) = \min\{c(x) \mid x \in [l_1,u_1] \times \cdots \times [l_n,u_n] \text{ is a solution to } S\}</math> or <math>c(b) = \max\{c(x) \mid x \in [l_1,u_1] \times \cdots \times [l_n,u_n] \text{ is a solution to } S\}</math>.
 
Then call
 
<pre>GLPK.LPSolve(c,EQ,LE,GE,B,Method,MinMax)</pre>
 
to get the desired solution as a list <code>b = [b1,...,bn]</code> or the empty list <code>[]</code> if the given system of (in)equalities is unsatisfiable.  
 
  
== Solving Mixed Integer Problems ==
+
* 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>.
:''See also: [[/GLPK.MIPSolve/]]
+
* 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>.
Let <math>I, J \subseteq \{1,\ldots,n\}</math> be disjoint sets. If additionally, a solution <math>b = (b_1,\ldots,b_n)</math> with <math>b_i \in \mathbb{N}</math> for <math>i \in I</math> and <math>b_j \in \{0,1\}</math> for <math>j \in J</math> is searched, then one can use the function <code>[[/GLPK.MIPSolve/]]</code>. Together with <code>c</code>, <code>EQ</code>, <code>LE</code>, <code>GE</code>, <code>B</code> and <code>MinMax</code> from above, the code
+
* 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>.
<pre>GLPK.MIPSolve(c,EQ,LE,GE,B,I,J,MinMax)</pre>
 
produces the desired solution or <code>[]</code> if the given system has no such solution.
 
  
 +
Many interesting properties of the scheme <math>X</math> are reflexed by the algebraic structure of the above invariants.
 +
 +
== Package Description ==
 +
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>.
 +
 +
=== List of main functions ===
 +
 +
[[/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>
 +
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>
 +
[[/HilbertKaehlerDiffRel/]]
 +
<pre>
 +
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>
 +
[[/AffBMAlgo/]]
 +
<pre>
 +
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>
 +
[[/DedekindDifferentRel/]]
 +
<pre>
 +
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>
 +
[[/HilbertDedekindDiffRel/]]
 +
<pre>
 +
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>
 +
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>
 +
[[/KDMOfPoints/]]
 +
<pre>
 +
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>
 +
[[/KDMOfProjectivePoints/]]
 +
<pre>
 +
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>
 +
[[/KDMRel/]]
 +
<pre>
 +
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>
 +
[[/HilbertKDMRel/]]
 +
<pre>
 +
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])
 +
</pre>
 +
 +
=== Examples for computations ===
 +
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/]].
 +
 +
Consider the first example, where X is the scheme defined by the homogeneous ideal Ix.
 +
<pre>
 +
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);
 +
</pre>
 +
Then we calculate the differents of X as follows:
 +
<pre>
 +
-- 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>
 +
 +
Next, let us consider the example, where X is given by a set of 10 points:
 +
<pre>
 +
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]];
 +
</pre>
 +
We can compute the Dedekind different of X and its Hilbert function by:
 +
<pre>
 +
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>
 +
 +
[[Category:Package zerodim]]
 +
[[Category:Package alggeozd]]
 +
[[Category:Package borderbasis]]
 
[[Category:ApCoCoA Packages]]
 
[[Category:ApCoCoA Packages]]
[[Category:Package glpk]]
 

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 be a field, let be the polynomial ring over in indeterminates, and let be a 0-dimensional ideal of and . Then defines a 0-dimensional scheme in the affine -space. Consider the canonical multiplication map

and its kernel . Then is a finitely generated -module and is an ideal of the enveloping algebra .

  • The ideal is called the Noether different of the algebra .
  • The -module is called the module of Kaehler differential 1-forms of the algebra .
  • The -linear map , is called the universal derivation of the algebra .
  • For , the exterior power is called the module of Kaehler differential m-forms of the algebra .
  • For the -th Fitting ideal of the module of Kaehler differential 1-forms is called the Kaehler different of the algebra .

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

Now let us embed the scheme in the projective -space via , where is a new indeterminate. Set and equip with the standard grading. The homogeneous vanishing ideal of is the homogenization of with respect to and denoted by , and the homogeneous coordinate ring of is the graded 1-dimensional ring . In this case is the Noetherian normalization of , and hence we can define the above invariants for the graded algebra . Moreover, we have the following further invariants.

  • The graded -module is called the canonical module of the algebra .
  • The graded locolization of at is called the homogeneous ring of quotients of .
  • When the scheme is reduced (more general, locally Gorenstein), there is an injection and the inverse of in is called the Dedekind different of .

Many interesting properties of the scheme 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]
     ])