[Next][Prev] [Right] [Left] [Up] [Index] [Root]
Subsections
This section describes embedded modules over affine algebras
(multivariate polynomial rings and their quotients) in Magma.
Multivariate polynomial rings are not principal ideal rings in general,
so the standard matrix echelonization algorithms are not applicable.
Magma allows computations in modules over such rings by
adding a column field to each monomial of a polynomial and then by using
all the ideal machinery based on Gröbner bases.
This method is much more efficient than that of
introducing new variables to represent
the columns since the number of columns does not affect the total number of
variables.
Quotient modules are fully supported and modules over quotient rings
of multivariate polynomial rings (affine algebras) are also supported
(which is done by simply adding appropriate quotient relations to
each module).
The coefficient ring of the multivariate
polynomial ring may be a field or general Euclidean ring.
Suppose P = R[x1, ..., xn] is a multivariate polynomial ring over
the ring R.
A monomial-column pair of P is a pair consisting of a monomial s
of P and a column number c (with c ≥1), written as s[c].
Suppose the monomial order for P is <. There are two natural module
monomial orders which can be placed on the monomial-column pairs of P
(see [AL94, Def. 3.5.2 and 3.5.3] for motivation and
further discussion).
The term over position module order (TOP) compares the pairs
s1[c1] and s2[c2] as follows: s1[c1] < s2[c2] if and only
if s1 < s2 or s1 = s2 and c1 < c2. Thus the monomials
are compared first, and then the columns.
The position over term module order (POT) compares the pairs
s1[c1] and s2[c2] as follows: s1[c1] < s2[c2] if and only
if c1 < c2 or c1 = c2 and s1 < s2. Thus the columns
are compared first, and then the monomials.
(The terminology "term" and "position" is more standard than
"monomial" or "column" when discussing module orders so that
is why it is used here -- see also [AL94, Sec. 3.5].)
The TOP order is generally preferable since it tends to give
simpler Gröbner bases (see below), and is thus the default order used
when a specific module order is not given.
For a fixed module monomial order <,
a module polynomial is a linearly ordered sum of terms of the form
a.s[c], where a∈P is the coefficient, and s[c] is a monomial-column
pair. Finally, a module M of degree r over P is a structure
whose elements are module polynomials with columns in the range [1 .. r].
The module M may be full (or generic), containing all valid module
polynomials. Otherwise, M is proper (or a submodule of a full module).
Within Magma, a module M over the multivariate polynomial ring P is
thought of (and implemented) as an ideal I of P with columns attached
to all monomials of I (called a "column-extended ideal").
The ideal I is stored in M and is used for
many of the operations applied to M. Thus many of the concepts associated
with ideals of polynomial rings carry over to M (which concepts do not
necessarily exist for other module types). Thus M has a current basis
(the current basis
of I), a Gröbner basis (the Gröbner basis of I), and so on.
Elements of M have a normal form, and the S-polynomial of two
elements of M can be formed if and only if their leading terms have the
same columns.
Sometimes the column structure of the module M and its elements is in view;
at other times, the polynomial ideal structure is in view and the
column structure is ignored.
A given module M may possess quotient relations. A module not
possessing quotient relations is called free. For each module M,
there is a free module F corresponding to M which has the same coefficient
ring and degree. The quotient relations of M are stored as a sequence
R of elements of F such that M is isomorphic
to the quotient of F by the submodule S of F generated by R.
R is stored in M as the Gröbner basis of the submodule S.
All elements of M are always reduced to normal form with respect to R
so all elements of M have a unique representation. This means that elements
of the basis of M are always reduced with respect to R also.
Submodules of M
have the same quotient relations R as M and their bases are also reduced
with respect to R. A module with quotient
relations is created by means of the quo constructor, like other
categories within Magma. Note, however, that the resulting module is
still a module within the same category -- there is no separate category
for quotient modules. This makes it easy to create quotient modules, and then
quotient modules of these, and so on, without confusion. Two modules are said
to be compatible if they have the same coefficient rings, degrees,
and quotient relations. Most binary operations only work for compatible
modules since it is obvious that comparing two modules with different
coefficient rings, degrees, or quotient relations is meaningless.
Let Q be a quotient ring formed by dividing the polynomial ring
P by an ideal I of P. A module M can be created over Q by simply
creating the corresponding module over P but with the (possibly extra)
quotient relations given by all the vectors having any entry an element
of a basis of I. This is the way modules over such quotient rings
is handled in Magma.
It is possible to place weights on the columns of a module M.
Such a module is called weighted or graded.
This is a natural extension of graded polynomial rings; see the section on
graded polynomial rings in the multivariate polynomial chapter.
Within a fixed graded module M the weighted degree of a monomial-column
pair s[c] is the sum of the weighted degree of the monomial s and
the weight for column c. (A module created without specific column weights
is assumed to have weight 0 for each column.)
The elements of a module M can be printed in two styles: matrix or polynomial.
In the matrix printing style, an element is printed as a vector with entries
from the coefficient ring P (and a basis of the module is printed as a
matrix similarly).
In the polynomial printing style, an element is printed just like a polynomial
but with the column number printed in square brackets after each monomial.
The matrix printing style is used by default since one usually thinks
of elements of such modules as vectors.
But the polynomial printing style is in fact often more natural
because of the way the module M is thought of as a column-extended ideal
I and since the
elements are actually implemented as module polynomials. In fact, if the
TOP order is used (the default), then the columns of the
terms of a module polynomial, taken in order, may not successively increase or
decrease (since the monomial
order dominates) which is a little unintuitive but reflects the true order
used in the ideal I. See below for methods for changing the printing style.
A generic free module M is created by giving the coefficient ring P
(which may be a polynomial ring or a quotient of such),
the degree r, and, optionally, an argument specifying the type of
module order.
The ideal I corresponding to M is the column-extended ideal of P
with the basis consisting of the module polynomials 1[c] for each column c.
The following Module functions,
which may be changed in future releases,
create generic free modules with the default weights of 0 for each column.
A generic free module M can also now be created by the RModule function,
with the parameter Embedded.
Given a multivariate polynomial ring or quotient ring P over a field
or Euclidean ring R,
create the generic free module of degree r over P with TOP module
order.
Given a multivariate polynomial ring or quotient ring P over a field
or Euclidean ring R, create
the generic free module of degree r over P with order specified by
the string S. S may be the string "top" or the string
"pot".
Embedded: BoolElt Default: false
Given a multivariate polynomial ring or quotient ring P over a field
or Euclidean ring R and the parameter Embedded, set to {true},
create the generic embedded free module of degree r over P
with TOP module order.
The following functions create graded generic free modules.
Given a multivariate polynomial ring or quotient ring P over a field or
Euclidean ring R, together with
an integer sequence W of length r, create the generic free module of degree
r over P with TOP order and with column weights given by W.
Given a multivariate polynomial ring or quotient ring P over a field
or Euclidean ring R,
together with
an integer sequence W of length r and a string S, create
the generic free module of degree r over P with order specified by
the string S and with column weights given by W.
S may be the string "top" or the string "pot".
We construct simple generic free modules over Q[x, y, z]. The first
module has default weights 0 on its columns, while the second has weights
1, 2, and 3 respectively on its columns.
> P<x, y, z> := PolynomialRing(RationalField(), 3);
> M := Module(P, 3);
> M;
Full Module of degree 3
TOP Order
Coefficient ring:
Polynomial ring of rank 3 over Rational Field
Lexicographical Order
Variables: x, y, z
> GM := Module(P, [1, 2, 3], "pot");
> GM;
Full Module of degree 3
POT Order
Column weights: 1 2 3
Coefficient ring:
Polynomial ring of rank 3 over Rational Field
Lexicographical Order
Variables: x, y, z
We now construct a module over a quotient ring.
> P<x, y, z> := PolynomialRing(RationalField(), 3);
> Q<a, b, c> := quo<P | y^3 + z*x - 2>;
> M := Module(Q, 3);
> M;
Full Quotient Module of degree 3
TOP Order
Coefficient ring:
Ideal of Quotient Ring by
Ideal of Polynomial ring of rank 3 over Rational Field
Lexicographical Order
Variables: x, y, z
Basis:
[
x*z + y^3 - 2
]
Preimage ideal:
Polynomial ring of rank 3 over Rational Field
Lexicographical Order
Variables: x, y, z
Quotient Relations:
( 0 0 x*z + y^3 - 2)
( 0 x*z + y^3 - 2 0)
(x*z + y^3 - 2 0 0)
The following functions allow the changing of the printing style of
module elements (and the bases of modules). See the definition section of
this chapter for a description of the printing styles.
This attribute is used to change the default printing for
all modules created after the AssertAttribute command
is executed.
If l is true, then the matrix printing style will be subsequently
used by default. Otherwise, the polynomial printing style will be used.
The default can be overruled for a particular module
by use of the AssertAttribute option listed below.
The value of this attribute is obtained by use of HasAttribute(ModMPol,
"MatrixPrinting").
This function is used to find the current default printing style for
all modules.
It returns true (since this attribute is always defined for ModMPol),
and also returns the current value of the attribute.
The procedure AssertAttribute(ModMPol, "MatrixPrinting", l) may be
used to control the value of this flag.
This function is used to change the current printing style for the module M.
If l is true, then the matrix printing style will be subsequently
used for M. Otherwise, the polynomial printing style will be used for M.
The value of this attribute is obtained by use of
HasAttribute(M, "MatrixPrinting").
This function is used to find the current printing style for the module M.
It returns true (since this attribute is always defined for a module),
and also returns the current value of the attribute.
The procedure AssertAttribute(M, "MatrixPrinting", l) may be
used to control the value of this flag.
Module elements (internally module polynomials) are
constructed in general by giving
a sequence or vector of elements from the coefficient ring P.
Suppose M is a module over the multivariate polynomial ring or quotient
ring P of
degree r. Given a sequence Q = [a1, ..., ar] of ring elements
such that the ai are coercible into P, construct the element of
M corresponding to Q.
Suppose M is a module over the multivariate polynomial ring or quotient
ring P of
degree r. Given a vector v from the R-space Pr, construct
the element of M corresponding to v.
Zero(M) : ModMPol -> ModMPolElt
Create the zero element of the module M.
Suppose M is a module over the multivariate polynomial ring or quotient
ring P of
degree r. Given an integer i in the range [1 .. r], construct
the i-th unit vector of M
(the vector with 1 in the i-th column and 0 elsewhere)
whose parent is the generic module of M (since it may not lie in M itself).
Note that this not the same as the function BasisElement
(see below).
The following functions allow simple access and operations on module elements.
Some of them use the module structure and refer to the column structure of
an element; others use the polynomial structure and ignore the column structure.
Given an element f of the module M over P and of degree r,
return the sequence [f1, ..., fr] of r elements from P
corresponding to f.
sigind
f[i] : ModMPolElt, RngIntElt -> RngMPolElt
Given an element f of the module M over P and of degree r, together
with an integer i in the range [1 .. r], return the i-th component
of f as an element of P.
Given elements f and g of the module M, return the sum f + g of f
and g.
Note that the result is always reduced to the unique normal form
modulo the quotient relations of M.
Given elements f and g of the module M, return the difference f - g
of f and g.
Note that the result is always reduced to the unique normal form
modulo the quotient relations of M.
Given an element f of the module M, return the negation -f of f.
Given a scalar ring element s and an element f of the module M, such
that s is coercible into the coefficient ring of M, return the element
sf.
Given a scalar ring element s and an element f of the module M, such
that s is coercible into the coefficient ring of M, return the element
fs.
Given a scalar ring element s and an element f of the module M, such
that s is coercible into the coefficient ring of M and s divides all
components of f, return the quotient of f by s.
(Procedure.)
Given a scalar ring element s and an element f of the module M, such
that s is coercible into the coefficient ring of M and s divides all
components of f, replace f by the quotient of f by s.
Given elements f and g of the module M such that the leading monomials
of f and g have the same column, return the S-polynomial of f and g.
Note that the result is always reduced to the unique normal form
modulo the quotient relations of M.
Given an element f of the module M, return whether f is the zero
element of M.
Given elements f and g of the module M, return whether f and g
are equal.
Given an element f of a module S together with a compatible module M,
return whether f is in M.
Given an element f of the module M, return the normalized form of
f (so that the leading monomial of f is normalized).
Given an element f of the module S, together with a compatible module
M, return the normal form of f with respect to M.
Given an element f of the module S, together with a compatible module
M such that f is in M, return the coordinates of f with respect to
the basis of M (whose components lie in the coefficient ring of M).
We demonstrate elementary operations on module elements.
> P<x, y, z> := PolynomialRing(RationalField(), 3);
> M := Module(P, 3);
> a := M ! [1, x, y];
> b := M ! [x, y, z];
> a;
(1 x y)
> b;
(x y z)
> a + b;
(x + 1 x + y y + z)
> z*a;
( z x*z y*z)
> Eltseq(z * a + b);
[
x + z,
x*z + y,
y*z + z
]
The following functions allow the construction of submodules and quotient
modules. See above for the definition of submodules and quotient modules.
Given a module M over a multivariate polynomial ring or quotient ring P,
return the submodule of M (with the same quotient relations as M)
generated by the elements of M specified by
the list L. Each term of the list L must be an expression defining
an object of one of the following types:
- (a)
- An element of M;
- (b)
- A set or sequence of elements of M;
- (c)
- A submodule of M;
- (d)
- A set or sequence of submodules of M.
Given a module M over a multivariate polynomial ring or quotient ring P,
return the quotient module of M by the elements of M specified by
the list L. Each term of the list L must be an expression defining
an object of one of the following types:
- (a)
- An element of M;
- (b)
- A set or sequence of elements of M;
- (c)
- A submodule of M;
- (d)
- A set or sequence of submodules of M.
The resulting module Q has the quotient relations of M together with
those specified in L. The terms of L must be compatible with M.
Thus if M is free, the quotient relations for Q are obtained by all
the terms of L which must all lie in a free module compatible with M.
The following functions access simple properties of a module M.
Given a module M, return the generic (or full) module containing M.
BaseRing(M) : ModMPol -> ModMPol
Given a module M, return the coefficient ring P of M (the multivariate
polynomial ring or quotient ring over which M is defined).
Given a module M, return the degree of M.
Given a module M, return the quotient relations of M as a sorted sequence
of elements (a Gröbner basis) of the generic free module corresponding to
M. If M is free, the empty sequence is returned.
The following functions test predicates of modules. For binary operations,
the modules must be compatible.
Given a module M, return whether M is the zero module.
Given compatible modules M and N, return whether M is a submodule of N.
Given compatible modules M and N, return whether M equals N.
Given a module M, return whether M is homogeneous (w.r.t. the weights
on the columns of M and the variables of the coefficient ring P).
The following functions allow one to manipulate the bases of modules.
Note that a Gröbner basis for a module will be automatically generated when
necessary; the Groebner procedure just allows explicit immediate
construction of the Gröbner basis.
Given a module M, return the current basis (whether it has been
converted to a Gröbner basis or not) of M.
Given a module M together with an integer i, return the i-th element
of the current basis of M. Note that this is not the same as M.i.
Given a module M, return the basis matrix of M, which is a k by
r matrix over P, where k is the length of the basis of M and
r is the degree of M.
(Procedure.) Explicitly force a Gröbner basis for the module M to be constructed.
The following functions construct new modules from old. For binary operations,
the modules must be compatible.
Given compatible modules M and N, return the sum of M and N.
Given compatible modules M and N, return the intersection of M and N.
Given compatible modules M and N, return the quotient module M/N.
This has the same effect as using the quo constructor.
We construct simple submodules and quotient modules and demonstrate the
operations on them.
> P<x, y, z> := PolynomialRing(RationalField(), 3);
> M := Module(P, 3);
> S := sub<M | [1, x, x^2+y], [z, y, x*y^2+1],
> [y, z, x+z]>;
> Groebner(S);
> S;
Module of degree 3
TOP Order
Coefficient ring:
Polynomial ring of rank 3 over Rational Field
Lexicographical Order
Variables: x, y, z
Groebner basis:
( -x*z + y^2 + y x*y^2 - x*y + z y^3 + z)
( x*y - y*z - 1 x*z - x - z^2 -y - z^2)
( y z x + z)
( y^3 - z y^2*z - y y^2*z - 1)
> a := M ! [y, z, x+z];
> a;
( y z x + z)
> a in S;
true
> BasisElement(S, 1);
( -x*z + y^2 + y x*y^2 - x*y + z y^3 + z)
> Q := quo<M | [x, y, z]>;
> Q;
Full Quotient Module of degree 3
TOP Order
Coefficient ring:
Polynomial ring of rank 3 over Rational Field
Lexicographical Order
Variables: x, y, z
Quotient Relations:
(x y z)
> a := Q![x, y, 0];
> b := Q![0, 0, z];
> a;
( 0 0 -z)
> b;
(0 0 z)
> a+b;
(0 0 0)
> Q ! [x,y,z];
(0 0 0)
> QQ := quo<Q | [x^2, 0, y+z]>;
> QQ;
Full Quotient Module of degree 3
TOP Order
Coefficient ring:
Polynomial ring of rank 3 over Rational Field
Lexicographical Order
Variables: x, y, z
Quotient Relations:
( 0 x*y x*z - y - z)
( x y z)
The following functions deal with homogeneous modules. Homogeneity depends
on the column weights, just as in graded polynomial rings.
Given a homogeneous module M, return a minimal basis of M.
A basis is minimal if no proper subset of it generates the same submodule as it.
MinimalBasis(S) : { ModMPolElt } -> [ ModMPolElt ]
Given a set or sequence S of homogeneous module elements from a module
M, return a minimal basis of the submodule of M generated by S.
A basis is minimal if no proper subset of it generates the same submodule as it.
Given a homogeneous submodule M of the generic module G, return the
Hilbert series HM(t) of the quotient module G/M as an element of the
univariate function field over the ring of integers.
We construct the Hilbert series of a simple homogeneous module.
> P<x, y, z> := PolynomialRing(RationalField(), 3);
> M := Module(P, 3);
> S := sub<M | [x, 0, z], [x^5 + y^5, z^5, y^3*x^2]>;
> IsHomogeneous(S);
true
> H<t> := HilbertSeries(S);
> H;
1/(t^2 - 2*t + 1)
The following functions construct syzygy modules.
Given a module M, return the syzygy module S of M. If the basis B of
M has length k, the syzygy module S has degree k and elements of
S express a syzygy amongst the k elements of the basis B. Note that
the degree of the resulting module thus depends on the current basis of M.
Given a homogeneous module M, return the syzygy module S of the
minimal basis of M. If the minimal basis B of
M has length k, the syzygy module S has degree k and elements of
S express a syzygy amongst the k elements of the minimal basis B.
We construct the syzygy module of a simple module.
> P<x, y, z> := PolynomialRing(RationalField(), 3);
> M := Module(P, 3);
> B := [[y, x^2, z], [z^3, x^3, y],
> [z, y^2, x], [x, y, z]];
> S := sub<M | B>;
> Z := SyzygyModule(S);
> Groebner(Z);
> Z;
Module of degree 4
TOP Order
Coefficient ring:
Polynomial ring of rank 3 over Rational Field
Lexicographical Order
Variables: x, y, z
Groebner basis:
(x^5 - x^3*z^2 - x*y^3 - x*y*z^3 + y^2*z^4 + y^2*z -x^4 +
x^2*z^2 + x*y^2*z + x*y^2 - y^3*z - y*z^2 -x^4*z + x^3*y*z
+ x^3*y - x^2*z^4 - y^3 + y*z^4 -x^4*y + x^3*z^3 + x^3*z^2
- x^2*y*z + y^4 - y^2*z^4)
The following functions compute with free resolutions.
Given a module M, return a free resolution of M.
The free resolution is returned as a sequence F such that F[1] is
M, F[i + 1] is the syzygy module of F[i] for i<#F, and the last element
of F is free (its basis has no syzygies).
The basis of M is not minimized first so it can affect the structure
of F. Use MinimalFreeResolution to assure a minimal free resolution.
Given a module M, return a minimal free resolution of M.
The minimal free resolution is returned as a sequence F such that F[1] is
M, F[i + 1] is the syzygy module of F[i] for i<#F, and the last element
of F is free (its basis has no syzygies).
The basis of M is minimized first and also the bases of each of the
modules in F are minimized before the syzygy module computations.
Given a module M, return the homological dimension of M. This is
just the length of a minimal free resolution of M minus 1 (taking
account of the fact that M is always included in the free resolution).
We construct the free resolution of a certain module.
> P<x, y, z> := PolynomialRing(RationalField(), 3, "grevlex");
> M := Module(P, 3);
> B := [[x*y, x^2, z], [x*z^3, x^3, y], [y*z, z, x],
> [z, y*z, x], [y, z, x]];
> S := sub<M | B>;
> F := MinimalFreeResolution(S);
> #F;
3
> #Basis(F[2]);
35
> #MinimalBasis(F[2]);
5
> #Basis(F[3]);
6
> #MinimalBasis(F[3]);
3
> MinimalBasis(F[3]);
[
(-x*y*z + x*z^2 + x^2 + 2*x*y - 2*x -3*y + z + 2 1 -y
0),
(x*y*z - x*y + z^2 -x + y x -x 0),
(x^2*y*z^2 - x^2*z^3 - 3*x^2*y*z + x^2*z^2 + 2*x^2*y + x*z -
2*x x^2*y + 3*x*y*z - x*z^2 - 3*x*y - 3*y + 3 -y
x*y*z - x*y + 1 -y*z + y)
]
> HomologicalDimension(S);
2
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
|
