The functions in this section deal with free resolutions and associated properties. Free resolutions are returned as chain complexes (see Chapter CHAIN COMPLEXES).
Minimal: BoolElt Default: true
Limit: RngIntElt Default: 0
Homogenize: BoolElt Default: true
Al: MonStgElt Default: "LaScala"
Given an R-module M, return a free resolution M as a complex C, and a comparison homomorphism f: C0 -> M (where C0 is the term of C of degree 0).By default, the free resolution will be minimal. Setting the parameter Minimal to {false} will construct a non-minimal resolution (which is constructed via a sequence of successive syzygy modules, with no minimization).
Magma has two algorithms for computing resolutions:
By default the LS algorithm is used if M is homogeneous and the coefficient ring of R is a finite field or the rational field, since this tends to be faster in general. But for some inputs the iterative algorithm may be significantly faster, particularly for some modules over the rationals. So one may set the parameter Al to "Iterative" to select the iterative algorithm. Uniqueness of the terms in the resolution is as follows.
- (1)
- The La Scala (LS) [SS98] algorithm, which works with a homogeneous module. The Magma implementation involves an extension of this algorithm which uses techniques from the Faug{ère F4 [Fau99] algorithm to compute many normal forms together in a block.
- (2)
- The Iterative algorithm, which simply computes successive syzygy modules progressively (minimizing as it goes if and only a minimal resolution is desired).
If the parameter Limit is set to a non-zero value l, then at most l terms (plus the term corresponding to the free module) are computed. If R is an affine algebra or exterior algebra of rank n, then by default the limit is set to n, since the resolution is not finite in general.
- (1)
- If M is homogeneous or defined over a local ring R, then the resulting complex C is guaranteed to be minimal, so the ranks of the terms in C and the associated Betti numbers will be unique.
- (2)
- If M is non-homogeneous and over a global ring R, then the boundary maps of C will not have any entries which are units, but C cannot be guaranteed to be an absolutely minimal free resolution, so the ranks of the terms and the associated Betti numbers will not be unique in general. Also, Magma may choose to compute C by computing the free resolution CH of a homogenization MH of M, and then specializing CH to yield C, since this method is usually faster (since the LS algorithm can then be used). One may set the parameter Homogenize to {true} or {false} to force Magma to use this homogenization technique or not.
(Procedure.) Change the verbose printing level for the free resolution algorithm and related functions to be v.
> R<x,y,z,t> := PolynomialRing(RationalField(), 4, "grevlex");
> B := [
> -x^2 + y*t, -y*z + x*t, x*z - t^2,
> x*y - t^2, -y*z + x*t, -x^2 + z*t
> ];
> M := GradedModule(Ideal(B));
> M;
Graded Module R^1/<relations>
Relations:
[-x^2 + y*t],
[-y*z + x*t],
[ x*z - t^2],
[ x*y - t^2],
[-y*z + x*t],
[-x^2 + z*t]
> C := FreeResolution(M);
> C;
Chain complex with terms of degree 4 down to -1
Dimensions of terms: 0 1 5 5 1 0
> Terms(C);
[
Free Graded Module R^0,
Free Graded Module R^1 with grading [5],
Free Graded Module R^5 with grading [3, 3, 3, 3, 3],
Free Graded Module R^5 with grading [2, 2, 2, 2, 2],
Free Graded Module R^1,
Free Graded Module R^0
]
> B := BoundaryMaps(C);
> B;
[*
Graded module homomorphism (0 by 1),
Graded module homomorphism (1 by 5) of degree 0
Ambient matrix:
[ x*z - t^2 x^2 - z*t -y*t + z*t y*z - x*t -x*y + t^2],
Graded module homomorphism (5 by 5) of degree 0
Ambient matrix:
[-y x 0 -t 0]
[ 0 -z y 0 t]
[ t -z 0 x 0]
[ 0 -t t 0 x]
[-z 0 x -t z],
Graded module homomorphism (5 by 1) of degree 0
Ambient matrix:
[x^2 - z*t]
[x*y - t^2]
[x*z - t^2]
[y*z - x*t]
[y*t - z*t],
Graded module homomorphism (1 by 0)
*]
> B[2]*B[3];
Module homomorphism (1 by 5)
Ambient matrix:
[0 0 0 0 0]
> B[3]*B[4];
Module homomorphism (5 by 1)
Ambient matrix:
[0]
[0]
[0]
[0]
[0]
> Image(B[3]) eq Kernel(B[4]);
true
> R<x,y> := PolynomialRing(RationalField(), 2, "grevlex");
> L := [<0, 0>, <1, 0>, <0, 1>, <2, 1>, <1, 2>, <3, 3>];
> I := Ideal(L, R);
> I;
Ideal of Polynomial ring of rank 2 over Rational Field
Graded Reverse Lexicographical Order
Variables: x, y
Inhomogeneous, Dimension 0
Groebner basis:
[
x^3 - 5*x^2 + 2*x*y - 2*y^2 + 4*x + 2*y,
x^2*y - 5*x^2 + 3*x*y - 4*y^2 + 5*x + 4*y,
x*y^2 - 4*x^2 + 3*x*y - 5*y^2 + 4*x + 5*y,
y^3 - 2*x^2 + 2*x*y - 5*y^2 + 2*x + 4*y
]
I is not homogeneous, and we compute a non-minimal free resolution
of the module R/I.
> M := QuotientModule(I);
> M;
Reduced Module R^1/<relations>
Relations:
[ x^3 - 5*x^2 + 2*x*y - 2*y^2 + 4*x + 2*y],
[x^2*y - 5*x^2 + 3*x*y - 4*y^2 + 5*x + 4*y],
[x*y^2 - 4*x^2 + 3*x*y - 5*y^2 + 4*x + 5*y],
[ y^3 - 2*x^2 + 2*x*y - 5*y^2 + 2*x + 4*y]
> C := FreeResolution(M: Minimal := false);
> C;
Chain complex with terms of degree 3 down to -1
Dimensions of terms: 0 3 4 1 0
> B := BoundaryMaps(C);
> B;
[*
Module homomorphism (0 by 3),
Module homomorphism (3 by 4)
Ambient matrix:
[-y + 5 x - 8 6 -2]
[ 4 -y - 8 x + 8 -4]
[ 2 -6 -y + 8 x - 5],
Module homomorphism (4 by 1)
Ambient matrix:
[ x^3 - 5*x^2 + 2*x*y - 2*y^2 + 4*x + 2*y]
[x^2*y - 5*x^2 + 3*x*y - 4*y^2 + 5*x + 4*y]
[x*y^2 - 4*x^2 + 3*x*y - 5*y^2 + 4*x + 5*y]
[ y^3 - 2*x^2 + 2*x*y - 5*y^2 + 2*x + 4*y],
Module homomorphism (1 by 0)
*]
> IsZero(B[2]*B[3]);
true
As noted in [CLO98], the 3 by 3 minors of the boundary map
from R3 to R4 generate the ideal I again, and this is due
to the Hilbert-Burch Theorem.
> U := Minors(Matrix(B[2]), 3);
> U;
[
y^3 - 2*x^2 + 2*x*y - 5*y^2 + 2*x + 4*y,
x*y^2 - 4*x^2 + 3*x*y - 5*y^2 + 4*x + 5*y,
x^2*y - 5*x^2 + 3*x*y - 4*y^2 + 5*x + 4*y,
x^3 - 5*x^2 + 2*x*y - 2*y^2 + 4*x + 2*y
]
> Ideal(U) eq I;
true
Each of the functions in this section compute numerical properties of a free resolution of a module M. Each function takes the same parameters as the function FreeResolution (not repeated here), thus allowing control of the construction of the underlying resolution.
In particular, by default the minimal free resolution of M is used (so the Betti numbers correspond to that), so the relevant invariant is guaranteed to be unique if M is graded or over a local ring R. Otherwise, one may set the parameter Minimal to {false} to give the Betti numbers for a non-minimal resolution.
Note: If M is graded and the LS algorithm is used (which will be the case by default), then computing any of the invariants to do with Betti numbers in this section may be quicker than computing the full resolution (since minimization of the actual resolution is needed for the latter). Thus it is preferable just to use one of the following functions instead of FreeResolution if only the numerical invariants are desired.
Given a module M, return the Betti numbers of M, which is simply the sequence of integers consisting of the degrees of the non-zero terms of the free resolution of M. See the discussion above concerning the parameters. Since the underlying resolution is minimal by default, if M is graded or over a local ring, then the result is unique.
Given a module M and integers i, j≥0, return the graded Betti number βi, j of M as an integer. This is the number of generators of degree j in the i-th term Fi of the free resolution of M.
Given a module M and an integer i≥0, return the maximum degree of the generators in the i-th term of the free resolution of M. Equivalently, this is the maximum j such that BettiNumber(M, i, j) is non-zero.
Given a module M, return the Betti table of M as a sequence S of sequences of integers, and a shift s. This is designed so that if M is non-zero, then S[1, 1] is always non-zero and S[i, j] equals BettiNumber(M, i, j - i + s). (So the degrees are shifted by s.)
Given an R-module M which is either graded or over a local ring, return the Castelnuovo-Mumford regularity. This is the least r such that in a minimal free resolution of M, the maximum of the degrees of the generators of the i-th term Fi is at most i + r. A simple consequence of this is that M is generated by elements of degree at most r. See [Eis95, Sec. 20.5] or [DL06, p. 167].
Given a module M, return the homological dimension of M. This is just the length of a minimal free resolution of M (the number of non-zero boundary maps).
> Q := RationalField();
> n := 3;
> R<[x]> := PolynomialRing(Q, n);
> I := Ideal([R.i: i in [1 .. n]]);
> M := QuotientModule(I);
> M;
Graded Module R^1/<relations>
Relations:
[x[1]],
[x[2]],
[x[3]]
> C := FreeResolution(M);
> C;
Chain complex with terms of degree 4 down to -1
Dimensions of terms: 0 1 3 3 1 0
> BoundaryMaps(C);
[*
Module homomorphism (0 by 1),
Module homomorphism (1 by 3)
Ambient matrix:
[ x[3] -x[2] x[1]],
Module homomorphism (3 by 3)
Ambient matrix:
[-x[2] x[1] 0]
[-x[3] 0 x[1]]
[ 0 -x[3] x[2]],
Module homomorphism (3 by 1)
Ambient matrix:
[x[1]]
[x[2]]
[x[3]],
Module homomorphism (1 by 0)
*]
In general, the i-th Betti number is (n choose i).
We can see this for n=10. Each boundary map consists of linear
relations alone, so the regularity is zero.
> n := 10;
> R<[x]> := PolynomialRing(Q, n);
> I := Ideal([R.i: i in [1 .. n]]);
> M := QuotientModule(I);
> time C := FreeResolution(M);
Time: 0.060
> C;
Chain complex with terms of degree 11 down to -1
Dimensions of terms: 0 1 10 45 120 210 252 210 120 45 10 1 0
> Terms(C);
[
Free Graded Module R^0,
Free Graded Module R^1 with grading [10],
Free Graded Module R^10 with grading [9, 9, 9, 9, 9, 9, 9, 9, 9, 9],
Free Graded Module R^45 with grading [8^^45],
Free Graded Module R^120 with grading [7^^120],
Free Graded Module R^210 with grading [6^^210],
Free Graded Module R^252 with grading [5^^252],
Free Graded Module R^210 with grading [4^^210],
Free Graded Module R^120 with grading [3^^120],
Free Graded Module R^45 with grading [2^^45],
Free Graded Module R^10 with grading [1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
Free Graded Module R^1,
Free Graded Module R^0
]
> B := BoundaryMaps(C);
> B: Minimal;
[*
Graded module homomorphism (0 by 1),
Graded module homomorphism (1 by 10) of degree 0,
Graded module homomorphism (10 by 45) of degree 0,
Graded module homomorphism (45 by 120) of degree 0,
Graded module homomorphism (120 by 210) of degree 0,
Graded module homomorphism (210 by 252) of degree 0,
Graded module homomorphism (252 by 210) of degree 0,
Graded module homomorphism (210 by 120) of degree 0,
Graded module homomorphism (120 by 45) of degree 0,
Graded module homomorphism (45 by 10) of degree 0,
Graded module homomorphism (10 by 1) of degree 0,
Graded module homomorphism (1 by 0)
*]
> [Binomial(n, i): i in [0 .. n]];
[ 1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1 ]
> BettiTable(M);
[
[ 1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1 ]
]
> $1 eq [[Binomial(n, i): i in [0 .. n]]];
true
> Regularity(M);
0
> Q := RationalField();
> n := 3;
> R<[x]> := ExteriorAlgebra(Q, n);
> I := Ideal([R.i: i in [1 .. n]]);
> M := QuotientModule(I);
> M;
Reduced Module R^1/<relations>
Relations:
[x[1]],
[x[2]],
[x[3]]
> BettiNumbers(M);
[ 1, 3, 6, 10, 15 ]
> [Binomial(i + n - 1, n - 1): i in [0..4]];
[ 1, 3, 6, 10, 15 ]
> C := FreeResolution(M);
> C;
Chain complex with terms of degree 5 down to -1
Dimensions of terms: 0 15 10 6 3 1 0
> BoundaryMaps(C);
[*
Graded module homomorphism (0 by 15),
Graded module homomorphism (15 by 10) of degree 0
Ambient matrix:
[x[3] 0 0 0 0 0 0 0 0 0]
[ 0 x[3] 0 x[2] 0 0 0 0 0 0]
[ 0 0 x[2] 0 0 0 0 0 0 0]
[ 0 x[2] x[3] 0 0 0 0 0 0 0]
[x[2] 0 0 x[3] 0 0 0 0 0 0]
[ 0 0 0 0 x[3] 0 0 0 0 x[1]]
[ 0 0 0 0 0 x[2] 0 0 x[1] 0]
[ 0 0 0 0 x[2] x[3] 0 x[1] 0 0]
[ 0 0 0 0 0 0 x[1] 0 0 0]
[ 0 0 0 0 0 x[1] x[2] 0 0 0]
[ 0 0 0 0 x[1] 0 x[3] 0 0 0]
[ 0 0 0 x[1] 0 0 0 x[3] 0 x[2]]
[ 0 0 x[1] 0 0 0 0 0 x[2] 0]
[ 0 x[1] 0 0 0 0 0 x[2] x[3] 0]
[x[1] 0 0 0 0 0 0 0 0 x[3]],
Graded module homomorphism (10 by 6) of degree 0
Ambient matrix:
[x[3] 0 0 0 0 0]
[ 0 x[3] x[2] 0 0 0]
[ 0 x[2] 0 0 0 0]
[x[2] 0 x[3] 0 0 0]
[ 0 0 0 x[3] 0 x[1]]
[ 0 0 0 x[2] x[1] 0]
[ 0 0 0 x[1] 0 0]
[ 0 0 x[1] 0 x[3] x[2]]
[ 0 x[1] 0 0 x[2] 0]
[x[1] 0 0 0 0 x[3]],
Graded module homomorphism (6 by 3) of degree 0
Ambient matrix:
[x[3] 0 0]
[ 0 x[2] 0]
[x[2] x[3] 0]
[ 0 0 x[1]]
[ 0 x[1] x[2]]
[x[1] 0 x[3]],
Graded module homomorphism (3 by 1) of degree 0
Ambient matrix:
[x[3]]
[x[2]]
[x[1]],
Graded module homomorphism (1 by 0)
*]
> R<x,y,z> := PolynomialRing(RationalField(), 3, "grevlex"); > R3 := RModule(R, 3); > B := [R3 | [x*y, x^2, z], [x*z^3, x^3, y], [y*z, z, x], > [z, y*z, x], [y, z, x]]; > M := quo<R3 | B>; > M; Reduced Module R^3/<relations> Relations: [ x*y, x^2, z], [x*z^3, x^3, y], [ y*z, z, x], [ z, y*z, x], [ y, z, x] > BettiNumbers(M); [ 3, 5, 4, 2 ] > BettiNumbers(Localization(M)); [ 3, 5, 3, 1 ]Since M is non-homogeneous, the Betti numbers are not unique. If we create a second module M2 which is equivalent to M and compute the Betti numbers this time without homogenization (in the internal free resolution algorithm), then we obtain different Betti numbers for M2. But since the Betti numbers over a local ring are unique, we get the same result for the localization of M2.
> M2 := quo<R3 | B>; > BettiNumbers(M2: Homogenize :=false); [ 3, 6, 5, 2 ] > BettiNumbers(Localization(M2): Homogenize:=false); [ 3, 5, 3, 1 ]
> function HilbertNumeratorBetti(M) > P<t> := PolynomialRing(IntegerRing()); > return &+[ > (-1)^i*BettiNumber(M, i, j)*t^j: > j in [0 .. MaximumBettiDegree(M, i)], > i in [0 .. #BettiNumbers(M)] > ]; > end function;We then check that this function agrees with the Magma internal function HilbertNumerator for some modules. (Since the modules do not have negative gradings, we do not have to worry about the denominator shift which is 0 for these modules.) First we try the Twisted Cubic.
> Q := RationalField(); > R<x,y,z,t> := PolynomialRing(Q, 4, "grevlex"); > B := [ > -x^2 + y*t, -y*z + x*t, x*z - t^2, > x*y - t^2, -y*z + x*t, -x^2 + z*t > ]; > M := GradedModule(Ideal(B)); > HilbertNumeratorBetti(M); -t^5 + 5*t^3 - 5*t^2 + 1 > HilbertNumerator(M); -t^5 + 5*t^3 - 5*t^2 + 1 0Now we apply the function to the module M=R1/I where I is the ideal generated by the 2 x 2 minors of a generic 4 x 4 matrix. Computing the Hilbert series numerator via the Betti numbers takes a little time since the resolution is non-trivial. Note the components of the Betti table which contribute to the terms of the Hilbert series numerator.
> n := 4;
> R<[x]> := PolynomialRing(Q, n^2, "grevlex");
> A := Matrix(n, [R.i: i in [1 .. n^2]]);
> A;
[ x[1] x[2] x[3] x[4]]
[ x[5] x[6] x[7] x[8]]
[ x[9] x[10] x[11] x[12]]
[x[13] x[14] x[15] x[16]]
> I := Ideal(Minors(A, 2));
> #Basis(I);
36
> M := QuotientModule(I);
> time HilbertNumeratorBetti(M);
-t^12 + 36*t^10 - 160*t^9 + 315*t^8 - 288*t^7 + 288*t^5 - 315*t^4 + 160*t^3 -
36*t^2 + 1
Time: 0.470
> time HilbertNumerator(M);
-t^12 + 36*t^10 - 160*t^9 + 315*t^8 - 288*t^7 + 288*t^5 - 315*t^4 + 160*t^3 -
36*t^2 + 1
0
Time: 0.000
> assert $1 eq $2;
> BettiNumbers(M);
[ 1, 36, 160, 315, 388, 388, 315, 160, 36, 1 ]
> BettiTable(M);
[
[ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
[ 0, 36, 160, 315, 288, 100, 0, 0, 0, 0 ],
[ 0, 0, 0, 0, 100, 288, 315, 160, 36, 0 ],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 1 ]
]
0
> wts := [ 1, 5, 9, 13, 17, 5, 1, 1, 1 ]; > K := GF(32003); > R<x0,x1,x2,x3,x4,y0,y1,u,t> := PolynomialRing(K, wts); > I := Ideal([ > x0*y0 - y1^3*u^3 - x1*t, > x1*y1 - x0*u^5 - t^6, > x1^2 - x0*x2 + y1^2*u^3*t^5, > x2^2 - x1*x3 + y0*y1*u^8*t^4, > x3^2 - x2*x4 + y0^2*u^13*t^3, > x3*y0 - u^18 - x4*t, > x4*y1 - x3*u^5 - y0^3*t^3, > x1*x2 - x0*x3 + y0*y1^2*u^3*t^4 + y1*u^8*t^5, > x2^2 - x0*x4 + y0*y1*u^8*t^4 + u^13*t^5, > x2*x3 - x1*x4 + y0^2*y1*u^8*t^3 + y0*u^13*t^4, > x1*y0 - y1^2*u^8 - x2*t, > x2*y0 - y1*u^13 - x3*t, > x2*y1 - x1*u^5 - y0*t^5, > x3*y1 - x2*u^5 - y0^2*t^4]); > IsHomogeneous(I); true > M := GradedModule(I); > time Regularity(M); 67 Time: 3.360 > IL := LeadingMonomialIdeal(I); > ML := GradedModule(IL); > time Regularity(ML); 92 Time: 0.530 > BettiNumbers(M); [ 1, 14, 45, 72, 76, 58, 29, 8, 1 ] > BettiNumbers(ML); [ 1, 42, 210, 505, 723, 659, 388, 144, 31, 3 ]
We work over the field GF(101), which will be referred to as K and the polynomial ring R will be the 4 variable polynomial ring over K. The construction begins by choosing a random 8 x 3 matrix with entries given by random linear and quadratic polynomials of R in appropriate positions. The minimal free resolution of the reduced module having this as the matrix of relations is computed. The image of the second boundary map of the resolution is the module referred to as (G) * in the above reference. Taking the submatrix of rows of a certain weighting of the matrix defining this map, we multiply by a 6 x 8 matrix with random entries in K. The resulting matrix represents a map from a free module F of rank 6 to (G) * , whose kernel is isomorphic to R as a submodule of F. The 6 coordinates of a generator of the kernel generate the desired ideal I. This kernel is computed with a syzygy computation (note: we could also use Kernel for the matrix giving the map). We also check that the quotient module of I has a minimal free resolution of the right form.
> K := GF(101); > R<x,y,z,t> := PolynomialRing(GF(101),4,"grevlex"); > v := [1,1,1,1,1,1,2,2]; > // generate the base random relations with appropriate linear and quadratic > // entries using the Random function for multivariate polynomials. > rels := [[Random(i,R,0): j in [1..3]] : i in v]; > Matrix(8,3,[TotalDegree(e) : e in &cat(rels)]); [1 1 1] [1 1 1] [1 1 1] [1 1 1] [1 1 1] [1 1 1] [2 2 2] [2 2 2] > // get the quotient module > F := RModule(R,3); > M := quo<F|rels>;Get the minimal free resolution and check that it has the correct Betti table.
> res := MinimalFreeResolution(M);
> BettiTable(res);
[
[ 3, 6, 0, 0, 0 ],
[ 0, 2, 8, 0, 0 ],
[ 0, 0, 3, 10, 4 ]
]
0
Get the 2nd boundary map matrix and then the 8 x 8 submatrix of linear and
quadratic entry rows.
> mat := Matrix(BoundaryMap(res,2)); > Nrows(mat); Ncols(mat); 11 8 > u := [1,1,2,2,2,2,2,2]; > mat := Matrix(R,[ri : i in [1..11] | > &and[(ri[j] eq 0) or (TotalDegree(ri[j]) eq u[j]): > j in [1..8]] where ri is Eltseq(mat[i])]); > Nrows(mat); Ncols(mat); 8 8 > Matrix(8,8,[TotalDegree(m) :m in Eltseq(mat)]); [1 1 2 2 2 2 2 2] [1 1 2 2 2 2 2 2] [1 1 2 2 2 2 2 2] [1 1 2 2 2 2 2 2] [1 1 2 2 2 2 2 2] [1 1 2 2 2 2 2 2] [1 1 2 2 2 2 2 2] [1 1 2 2 2 2 2 2]Now generate the random 6 x 8 matrix over K, compute the kernel of the composition via syzygies and generate the matrix I.
> mat1 := Matrix(R,6,8,[Random(K) : i in [1..48]]); > matc := mat1*mat; > F1 := EModule(R,[2-x : x in u]); > syz := SyzygyModule(sub<F1|RowSequence(matc)>); > B := MinimalBasis(syz); > #B; 1 > I := ideal<R|Eltseq(B[1])>;Finally, check I has the right dimension (2) and degree (12) and that R/I has the correct minimal free resolution with Betti table as given in [ST02].
> Dimension(I); Degree(I);
2 [ 3, 4 ]
12
> OC := QuotientModule(I);
> BettiTable(MinimalFreeResolution(OC));
[
[ 1, 0, 0, 0 ],
[ 0, 0, 0, 0 ],
[ 0, 0, 0, 0 ],
[ 0, 0, 0, 0 ],
[ 0, 6, 2, 0 ],
[ 0, 0, 6, 3 ]
]
0