Magma has powerful algorithms for computing the full radical and the
primary decomposition of any ideal defined over a perfect field.
See Becker & Weispfenning, 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.
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 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 the coefficient field is perfect (which means in Magma that the coefficient field must have characteristic zero).
> 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. 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 the coefficient field is perfect (which means in Magma that the coefficient field must have characteristic zero).
- 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 the coefficient field is perfect (which means in Magma that the coefficient field must have characteristic zero).
- 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