[Next] [Prev] [Right] [Left] [Up] [Index] [Root]
Radical and Primary Decomposition of Ideals

Radical and Primary Decomposition of Ideals

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).

Example RngMPol_Radical (H29E22)

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
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

PrimaryDecomposition(I) : RngMPol -> [ RngMPol ], [ RngMPol ]
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).
RadicalDecomposition(I) : RngMPol -> [ RngMPol ]
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).
ProbableRadicalDecomposition(I) : RngMPol -> [ RngMPol ]
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.
SetVerbose("Decomposition", v) : MonStgElt, RngIntElt ->
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.

Example RngMPol_PrimaryDecomposition (H29E23)

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
    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

[Next] [Prev] [Right] [Left] [Up] [Index] [Root]