|
Magma has algorithms for computing the full radical and the
primary decomposition of ideals.
See [BW93, chapter 8], for the relevant definitions
and theory. The implementation of the algorithms presented here in
Magma was based on the algorithms presented in that chapter.
Currently these algorithms work only for ideals of polynomial rings
over fields (Euclidean rings will be supported in the future).
There are also functions for some easier decompositions than the
full primary decomposition: radical decompositions, equidimensional
decompositions and triangular decompositions for zero-dimensional ideals.
The theory behind these is discussed in the relevant function description.
Radical(I) : RngMPol -> RngMPol
Given an ideal I of a polynomial ring P over a field, return the
radical of I. The radical R of I is defined to be the set of all
polynomials f ∈P such that fn ∈I for some n ≥1. The radical
R is also an ideal of P, containing I.
The function works for an ideal defined over any field
over which polynomial factorization is available.
We compute the radical of an ideal of Q[x, y, z, t, u] (which is not
zero-dimensional).
> P<x, y, z, t, u> := PolynomialRing(RationalField(), 5);
> I := ideal<P |
> x + y + z + t + u,
> x*y + y*z + z*t + t*u + u*x,
> x*y*z + y*z*t + z*t*u + t*u*x + u*x*y,
> x*y*z*t + y*z*t*u + z*t*u*x + t*u*x*y + u*x*y*z,
> x*y*z*t*u>;
> R := Radical(I);
> Groebner(R);
> R;
Ideal of Polynomial ring of rank 5 over Rational Field
Order: Lexicographical
Variables: x, y, z, t, u
Homogeneous, Dimension >0, Radical
Groebner basis:
[
x + y + z + t + u,
y^2 + y*t - z*u - u^2,
y*z,
y*u + z*u + u^2,
z^2*u + z*u^2,
z*t,
t*u
]
> // Check that t*u is in the radical of I by another method:
> IsInRadical(t*u, I);
true
PrimaryDecomposition(I) : RngMPol -> [ RngMPol ], [ RngMPol ]
Given an ideal I of a polynomial ring over a field, return the
primary decomposition of I, and also the sequence of associated
prime ideals.
See IsPrimary for the definition of a primary ideal.
The primary decomposition of I is returned
as two parallel sequences Q and P of ideals, both of length k,
having the following
properties:
- (a)
- The ideals of Q are primary.
- (b)
- The intersection of the ideals of Q is I.
- (c)
- The ideals of P are the associated primes of Q; i.e., P[i] is
the radical of Q[i] (so P[i] is prime) for 1 ≤i ≤k.
- (d)
- Q is minimal: no ideal of Q contains the intersection of the rest of
the ideals of Q and the associated prime ideals in P are distinct.
- (e)
- Q and P are sorted so that P is always unique and Q is unique
if I is zero-dimensional. If I is not zero-dimensional, then an embedded
component of Q (one whose associated prime contains another associated
prime from P) will not be unique in general. Yet Magma will always
return the same values for Q and P, given the same I.
The function works for an ideal defined over any field
over which polynomial factorization is available
(inseparable field extensions are handled by an algorithm due to
Allan Steel [Ste05]).
NB: if one only wishes to compute the prime components P, then
the next function RadicalDecomposition should be used,
since this may be much more efficient.
Given an ideal I of a polynomial ring over a field, return the
prime decomposition of the radical of I. This is equivalent to
applying the function PrimaryDecomposition to the radical of I,
but may be a much more efficient than using that method.
The (prime) radical decomposition of I is returned
as a sequence P of ideals of length k having the following properties:
- (a)
- The ideals of P are prime.
- (b)
- The intersection of the ideals of P is the radical of I.
- (c)
- P is minimal: no ideal of P contains the intersection of the rest of
the ideals of P.
- (e)
- P is sorted so that P is always unique.
Thus Magma will always
return the same values for P, given the same I.
The function works for an ideal defined over any field
over which polynomial factorization is available.
Given an ideal I of a polynomial ring P over a field, return a probabilistic
prime decomposition of the radical of I as a sequence of ideals of P.
This function is like the
function RadicalDecomposition except that the ideals returned may
not be prime, but the time taken may be much less.
Given a set or sequence S of ideals of a polynomial ring over a field,
with I = ∩J∈S J (so that S describes a decomposition of I),
return a minimal decomposition M of I as a subset of S such that I
= ∩J∈M J also (so none of the ideals in the decomposition M
are redundant).
Change verbose printing for the (Primary/Radical) Decomposition
algorithm to be v.
Currently the legal values for v are true, false, 0, 1, or 2.
We compute the primary decomposition of the same ideal of Q[x, y, z, t, u]
(which is not zero-dimensional).
> P<x, y, z, t, u> := PolynomialRing(RationalField(), 5);
> I := ideal<P |
> x + y + z + t + u,
> x*y + y*z + z*t + t*u + u*x,
> x*y*z + y*z*t + z*t*u + t*u*x + u*x*y,
> x*y*z*t + y*z*t*u + z*t*u*x + t*u*x*y + u*x*y*z,
> x*y*z*t*u>;
> IsZeroDimensional(I);
false
> Q, P := PrimaryDecomposition(I);
We next print out the primary components Q and associated primes P.
> Q;
[
Ideal of Polynomial ring of rank 5 over Rational Field
Order: Lexicographical
Variables: x, y, z, t, u
Homogeneous, Dimension 1, Non-radical, Primary, Non-prime
Groebner basis:
[
x + 1/2*z + 1/2*u,
y + 1/2*z + 1/2*u,
z^2 + 2*z*u + u^2,
t
],
Ideal of Polynomial ring of rank 5 over Rational Field
Order: Lexicographical
Variables: x, y, z, t, u
Homogeneous, Dimension 1, Non-radical, Primary, Non-prime
Groebner basis:
[
x + 2*z + t,
y - z,
z^2,
u
],
Ideal of Polynomial ring of rank 5 over Rational Field
Order: Lexicographical
Variables: x, y, z, t, u
Homogeneous, Dimension 1, Non-radical, Primary, Non-prime
Groebner basis:
[
x + z + 2*u,
y,
t - u,
u^2
],
Ideal of Polynomial ring of rank 5 over Rational Field
Order: Lexicographical
Variables: x, y, z, t, u
Homogeneous, Dimension 1, Non-radical, Primary, Non-prime
Groebner basis:
[
x - u,
y + t + 2*u,
z,
u^2
],
Ideal of Polynomial ring of rank 5 over Rational Field
Order: Lexicographical
Variables: x, y, z, t, u
Homogeneous, Dimension 1, Non-radical, Primary, Non-prime
Groebner basis:
[
x,
y + 2*t + u,
z - t,
t^2
],
Ideal of Polynomial ring of rank 5 over Rational Field
Order: Lexicographical
Variables: x, y, z, t, u
Homogeneous, Dimension 0, Non-radical, Primary, Non-prime
Size of variety over algebraically closed field: 1
Groebner basis:
[
x + y + z + t + u,
y^2 + y*t + 2*y*u - z*t + z*u + u^2,
y*z^2 - y*z*t + y*t*u - y*u^2 + z^2*t - z^2*u + z*t*u - 2*z*u^2 + t^2*u
+ t*u^2 - u^3,
y*z*t^2 - 2*y*z*u^2 + 3*y*t*u^2 - 2*y*u^3 + z^3*t - z^3*u - z^2*t^2 +
4*z^2*t*u - 4*z^2*u^2 + z*t^2*u + 2*z*t*u^2 - 5*z*u^3 + 3*t^2*u^2 +
2*t*u^3 - 2*u^4,
y*z*t*u + y*z*u^2 - y*t^2*u - 4*y*t*u^2 + 3*y*u^3 - z^3*t + z^3*u +
z^2*t^2 - 3*z^2*t*u + 4*z^2*u^2 - 2*z*t*u^2 + 6*z*u^3 - t^3*u -
5*t^2*u^2 - 3*t*u^3 + 3*u^4,
y*z*u^3 - 5/2*y*t*u^3 + 3/2*y*u^4 + 1/4*z^3*t^2 + 1/2*z^3*u^2 -
3/4*z^2*t^3 + 5/4*z^2*t^2*u - 1/4*z^2*t*u^2 + 9/4*z^2*u^3 -
9/4*z*t^3*u + 1/4*z*t^2*u^2 - 3/4*z*t*u^3 + 13/4*z*u^4 - t^3*u^2 -
5/2*t^2*u^3 - 7/4*t*u^4 + 3/2*u^5,
y*t^3*u - 17/4*y*t*u^3 + 13/4*y*u^4 + 1/8*z^3*t^2 + 5/4*z^3*u^2 -
19/8*z^2*t^3 + 13/8*z^2*t^2*u - 5/8*z^2*t*u^2 + 33/8*z^2*u^3 -
33/8*z*t^3*u - 7/8*z*t^2*u^2 - 31/8*z*t*u^3 + 49/8*z*u^4 + t^4*u +
1/2*t^3*u^2 - 15/4*t^2*u^3 - 31/8*t*u^4 + 13/4*u^5,
y*t^2*u^2 - 3/4*y*t*u^3 - 1/4*y*u^4 + 3/8*z^3*t^2 - 1/4*z^3*u^2 -
1/8*z^2*t^3 + 7/8*z^2*t^2*u + 1/8*z^2*t*u^2 - 5/8*z^2*u^3 -
3/8*z*t^3*u + 11/8*z*t^2*u^2 - 5/8*z*t*u^3 - 5/8*z*u^4 + 1/2*t^3*u^2
+ 3/4*t^2*u^3 - 5/8*t*u^4 - 1/4*u^5,
y*t*u^4 - 2/3*z^2*t^4 + 13/15*z^2*t^2*u^2 - 1/5*z^2*t*u^3 -
31/15*z*t^4*u + 3/5*z*t^3*u^2 - 2/5*z*t^2*u^3 + 23/15*z*t*u^4 -
3/5*t^4*u^2 + 2/15*t^3*u^3 - 1/3*t^2*u^4 + t*u^5,
y*u^5 - 1/2*z^2*t^4 - 1/2*z^2*t^2*u^2 + 1/2*z^2*t*u^3 + 1/2*z^2*u^4 -
3/2*z*t^4*u - 3*z*t^3*u^2 + 5/2*z*t*u^4 + 3/2*z*u^5 - 1/2*t^4*u^2 -
2*t^3*u^3 - 2*t^2*u^4 + 1/2*t*u^5,
z^7,
z^4*t - z^4*u - z^3*t^2 - 3*z^3*u^2 + 2*z^2*t^3 + 2*z^2*t^2*u -
9*z^2*t*u^2 - 3*z^2*u^3 + 7*z*t^3*u + 2*z*t^2*u^2 - z*u^4 +
2*t^3*u^2 - t^2*u^3 + t*u^4,
z^4*u^2 + 7/3*z^2*t^4 - 40/3*z^2*t^2*u^2 + 8*z^2*t*u^3 - 3*z^2*u^4 +
22/3*z*t^4*u - 20*z*t^3*u^2 + 2*z*t^2*u^3 + 31/3*z*t*u^4 - 2*z*u^5 +
t^4*u^2 - 41/3*t^3*u^3 - 10/3*t^2*u^4 + 2*t*u^5,
z^3*t^3 + 1/3*z^2*t^4 + 2/3*z^2*t^2*u^2 + z^2*t*u^3 + 1/3*z*t^4*u -
2*z*t^3*u^2 - z*t^2*u^3 + 1/3*z*t*u^4 - 2/3*t^3*u^3 - 1/3*t^2*u^4,
z^3*t*u - z^2*t^3 + 3*z^2*t*u^2 - 3*z*t^3*u + z*t*u^3 - t^3*u^2,
z^3*u^3 - 1/3*z^2*t^4 + 7/3*z^2*t^2*u^2 - 2*z^2*t*u^3 + 2*z^2*u^4 -
4/3*z*t^4*u + 7*z*t^3*u^2 - 2*z*t^2*u^3 - 13/3*z*t*u^4 + z*u^5 +
14/3*t^3*u^3 + 4/3*t^2*u^4 - t*u^5,
z^2*t^5 - 3*z*t*u^5 + 17/2*t^5*u^2 + 33/2*t^4*u^3 + 9*t^3*u^4 +
15/2*t^2*u^5,
z^2*t^3*u - z^2*t^2*u^2 + z*t^3*u^2,
z^2*t^2*u^3 - 4/5*z*t*u^5 + 16/5*t^5*u^2 + 59/10*t^4*u^3 -
11/10*t^3*u^4,
z^2*t*u^4 - 4/5*z*t*u^5 + 47/10*t^5*u^2 + 42/5*t^4*u^3 - 31/10*t^3*u^4 -
1/2*t^2*u^5,
z^2*u^5 + 6*z*t*u^5 - 2*t^5*u^2 - 4*t^4*u^3 - 4*t^3*u^4 - 7*t^2*u^5,
z*t^5*u + z*t*u^5 - 5/2*t^5*u^2 - 11/2*t^4*u^3 - 3*t^3*u^4 -
5/2*t^2*u^5,
z*t^4*u^2 + 2/5*z*t*u^5 - 11/10*t^5*u^2 - 17/10*t^4*u^3 - 1/5*t^3*u^4 -
1/2*t^2*u^5,
z*t^3*u^3 + 1/5*z*t*u^5 - 3/10*t^5*u^2 - 3/5*t^4*u^3 - 1/10*t^3*u^4 -
1/2*t^2*u^5,
z*t^2*u^4 + 2/5*z*t*u^5 - 8/5*t^5*u^2 - 16/5*t^4*u^3 - 1/5*t^3*u^4,
t^6,
t^5*u^3,
t^4*u^4,
t^3*u^5,
u^6
]
]
> P;
[
Ideal of Polynomial ring of rank 5 over Rational Field
Order: Lexicographical
Variables: x, y, z, t, u
Homogeneous, Dimension 1, Radical, Prime
Groebner basis:
[
x,
y,
z + u,
t
],
Ideal of Polynomial ring of rank 5 over Rational Field
Order: Lexicographical
Variables: x, y, z, t, u
Homogeneous, Dimension 1, Radical, Prime
Groebner basis:
[
x + t,
y,
z,
u
],
Ideal of Polynomial ring of rank 5 over Rational Field
Order: Lexicographical
Variables: x, y, z, t, u
Homogeneous, Dimension >0, Radical, Prime
Groebner basis:
[
x + z,
y,
t,
u
],
Ideal of Polynomial ring of rank 5 over Rational Field
Order: Lexicographical
Variables: x, y, z, t, u
Homogeneous, Dimension 1, Radical, Prime
Groebner basis:
[
x,
y + t,
z,
u
],
Ideal of Polynomial ring of rank 5 over Rational Field
Order: Lexicographical
Variables: x, y, z, t, u
Homogeneous, Dimension 1, Radical, Prime
Groebner basis:
[
x,
y + u,
z,
t
],
Ideal of Polynomial ring of rank 5 over Rational Field
Order: Lexicographical
Variables: x, y, z, t, u
Homogeneous, Dimension 0, Radical, Prime
Size of variety over algebraically closed field: 1
Groebner basis:
[
x,
y,
z,
t,
u
]
]
Notice that P[6] contains other ideals of P so Q[6] is an embedded
primary component of I. Thus the first 5 ideals of Q would the same be in
any primary decomposition of I, while Q[6] could be different in another
primary decomposition of I. Finally, notice that the prime decomposition of
the radical of I is the same as P except for the removal of P[6]
to satisfy the uniqueness condition. The structure of the variety of
I can be easily understood by examining the prime decomposition of
the radical.
> RP := RadicalDecomposition(I);
> #RP;
5
> Set(RP) eq { P[i]: i in [1 .. 5] };
true
Let T be a zero-dimensional ideal of the polynomial ring
K[x1, ..., xn], where K is a field.
T is called triangular if its Gröbner
basis G has length n and the initial term of the i-th polynomial
of G is of the form xiei for each i.
Any radical zero-dimensional ideal has a decomposition
as an intersection of triangular ideals.
The algorithm in Magma for primary decomposition now (since V2.4)
first computes a triangular decomposition and then decomposes each
triangular component to primary ideals since the computation of
a triangular decomposition is usually fast. See [Laz92] for
further discussion of triangular ideals.
Given a zero-dimensional ideal I of a polynomial ring over a field
with lexicographical order, return a triangular decomposition of
I as a sequence Q of ideals such that the intersection of the
ideals of Q equals I and for each ideal J of Q which is
radical, J is triangular (see above for the definition of a
triangular ideal). A second return value indicates whether I
is proven to be radical.
If I is radical,
all entries of Q are triangular. Computing a triangular
decomposition will often be faster than computing the full primary
decomposition and may yield sufficient information for a specific problem.
The algorithm implemented is that given in [Laz92].
We compute the triangular decomposition of the (radical) Cyclic-5
roots ideal and compare it with the full primary decomposition of
the same ideal.
> R<x, y, z, t, u> := PolynomialRing(RationalField(), 5);
> I := ideal<R |
> x + y + z + t + u,
> x*y + y*z + z*t + t*u + u*x,
> x*y*z + y*z*t + z*t*u + t*u*x + u*x*y,
> x*y*z*t + y*z*t*u + z*t*u*x + t*u*x*y + u*x*y*z,
> x*y*z*t*u - 1>;
> IsRadical(I);
true
> time T := TriangularDecomposition(I);
Time: 0.000
> time Q, P := PrimaryDecomposition(I);
Time: 0.010
> #T;
9
> #Q;
20
So we notice that although I decomposes into 9 triangular ideals,
some of these ideals must decompose further since the primary decomposition
consists of 20 prime ideals. We examine the first entry of T. Notice
that it is at least triangular (it has 5 polynomials and for each variable
there is a polynomial whose leading monomial is a power of that variable).
> T[1];
Ideal of Polynomial ring of rank 5 over Rational Field
Order: Lexicographical
Variables: x, y, z, t, u
Inhomogeneous, Dimension 0
Groebner basis:
[
x - 6/5*t^5 - 4*t^4 - 3*t^3 - 3*t^2 - 3*t - 9/5,
y - 2/5*t^5 - 2*t^4 - 3*t^3 - 2*t^2 - 2*t - 8/5,
z + 8/5*t^5 + 6*t^4 + 6*t^3 + 5*t^2 + 6*t + 22/5,
t^6 + 4*t^5 + 5*t^4 + 5*t^3 + 5*t^2 + 4*t + 1,
u - 1
]
> IsPrimary(T[1]);
false
> D := PrimaryDecomposition(T[1]);
> #D;
2
> D;
[
Ideal of Polynomial ring of rank 5 over Rational Field
Order: Lexicographical
Variables: x, y, z, t, u
Inhomogeneous, Dimension 0, Radical, Prime
Size of variety over algebraically closed field: 2
Groebner basis:
[
x - 1,
y - 1,
z + t + 3,
t^2 + 3*t + 1,
u - 1
],
Ideal of Polynomial ring of rank 5 over Rational Field
Order: Lexicographical
Variables: x, y, z, t, u
Inhomogeneous, Dimension 0, Radical, Prime
Size of variety over algebraically closed field: 4
Groebner basis:
[
x + t^3 + t^2 + t + 1,
y - t^3,
z - t^2,
t^4 + t^3 + t^2 + t + 1,
u - 1
]
]
EquidimensionalDecomposition(I) : RngMPol -> [ RngMPol ]
FineEquidimensionalDecomposition(I) : RngMPol -> SeqEnum
Let I be an ideal of a polynomial ring P over a field. Currently for
the two decomposition functions, it is assumed that I has no
embedded associated primes
(e.g., when I is radical). In this case, it can be much faster to compute
an equidimensional decomposition rather than a full primary or radical
one. The equidimensional decomposition is the set of ideals which are the
intersections of all primary components of I associated to primes of the
same dimension. This decomposition (often trivial) is useful for certain
constructions involving the Jacobian ideal.
The first function just computes the highest-dimensional decomposition component.
The second performs the straight decomposition. The third gives a
slightly finer decomposition for the convenience of some applications. In it,
each equidimensional component is possibly further split so that, for each
final equidimensional factor there is a single set of variables which
constitute a maximally independent set of every primary component of the
factor (cf Dimension). A sequence of pairs
consisting of each factor and the indices of its set of variables is returned.
The algorithm from [GP02] is used in the general case. When I
is homogeneous, a faster, more module-theoretic method is employed for
the first two functions. This involves first expressing P/I as a finite module
M over a linear Noether Normalisation (described in the next section) S of
I. Then if E(I) is the equidimensional part of I, E(I)/I as a submodule
of M is equal to the kernel of the natural map of M to its double dual over
S, HomS(HomS(M, S), S). Working with modules over S rather than over P
here allows the "reduction to dimension 0". We could directly over P,
doing a similar computation but with HomS replaced by some ExtiP
(see [EHV92]).
> P<x, y, z> := PolynomialRing(RationalField(), 3);
> P1 := ideal<P|x*y+y*z+z*x>; // dimension 2 prime
> P2 := ideal<P|x^2+y,y*z+2>; // dimension 1 prime
> P3 := ideal<P|x*y-1,y+z>; // dimension 1 prime
> I := P1 meet P2 meet P3;
> time rd := RadicalDecomposition(I);
Time: 3.720
> time ed := EquidimensionalDecomposition(I);
Time: 0.070
> #ed;
2
> ed[1] eq P1;
true
> ed[2] eq (P2 meet P3);
true
[Next][Prev] [Right] [Left] [Up] [Index] [Root]
|