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 must defined over fields (ideals defined over Euclidean rings will be be supported in the future).
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 in P such that f^n in I for some n >= 1. The radical R is also an ideal of P. Currently the algorithm works for any zero-dimensional ideal over any field, but the algorithm works for non zero-dimensional ideals only if a function field over the coefficient field is perfect (which means in Magma that the coefficient field must currently have characteristic zero in this case).
> 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
Lexicographical Order
Variables: x, y, z, t, u
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:
Currently the algorithm works for any zero-dimensional ideal over any field, but the algorithm works for non zero-dimensional ideals only if a function field over the coefficient field is perfect (which means in Magma that the coefficient field must currently have characteristic zero in this case).
- The ideals of Q are primary.
- The intersection of the ideals of Q is I.
- 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.
- 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.
- 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.
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 little 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:
Currently the algorithm works for any zero-dimensional ideal over any field, but the algorithm works for non zero-dimensional ideals only if a function field over the coefficient field is perfect (which means in Magma that the coefficient field must currently have characteristic zero in this case).
- The ideals of P are prime.
- The intersection of the ideals of P is the radical of I.
- P is minimal: no ideal of P contains the intersection of the rest of the ideals of P.
- 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 and also the ideal I need not be zero-dimensional for non-perfect coefficient fields.
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
Lexicographical Order
Variables: x, y, z, t, u
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
Lexicographical Order
Variables: x, y, z, t, u
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
Lexicographical Order
Variables: x, y, z, t, u
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
Lexicographical Order
Variables: x, y, z, t, u
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
Lexicographical Order
Variables: x, y, z, t, u
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
Lexicographical Order
Variables: x, y, z, t, u
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
Lexicographical Order
Variables: x, y, z, t, u
Dimension 1, Radical, Prime
Groebner basis:
[
x + t,
y,
z,
u
],
Ideal of Polynomial ring of rank 5 over Rational Field
Lexicographical Order
Variables: x, y, z, t, u
Dimension 1, Radical, Prime
Groebner basis:
[
x + z,
y,
t,
u
],
Ideal of Polynomial ring of rank 5 over Rational Field
Lexicographical Order
Variables: x, y, z, t, u
Dimension 1, Radical, Prime
Groebner basis:
[
x,
y,
z + u,
t
],
Ideal of Polynomial ring of rank 5 over Rational Field
Lexicographical Order
Variables: x, y, z, t, u
Dimension 1, Radical, Prime
Groebner basis:
[
x,
y + t,
z,
u
],
Ideal of Polynomial ring of rank 5 over Rational Field
Lexicographical Order
Variables: x, y, z, t, u
Dimension 1, Radical, Prime
Groebner basis:
[
x,
y + u,
z,
t
],
Ideal of Polynomial ring of rank 5 over Rational Field
Lexicographical Order
Variables: x, y, z, t, u
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[x_1, ..., x_n], 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 x_i^(e_i) 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). 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.060 > time Q, P := PrimaryDecomposition(I); Time: 0.230 > #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
Lexicographical Order
Variables: x, y, z, t, u
Dimension 0, Radical, Non-primary, Non-prime
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
Lexicographical Order
Variables: x, y, z, t, u
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
Lexicographical Order
Variables: x, y, z, t, u
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
]
]