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.
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.
> 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
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: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]).
- (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.
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:The function works for an ideal defined over any field over which polynomial factorization is available.
- (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.
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.
> 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].
> 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; 20So 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
]
]
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