Primary decomposition

The computation of the radical of an ideal

Santiago Laplagne

Universidad de Buenos Aires

Linz, Febraury 2006

Summary

1. Basics

2. Zero dimensional ideals (Seidenberg, Kemper) 3. Positive characteristic (Matsumoto)

4. General case

Basics

• k[x] = k[x₁, . . . , x_n], k a field

• I ideal in k[x]

The radical of an ideal

√I = {f ∈ k[x] / f^m ∈ I for some m ∈ N}

• I is radical if I = √ I.

• V(I) = V(√ I).

• √

I ∩ J = √

I ∩ √ J. Radical membership

f ∈ √

I ⇐⇒ 1 ∈ hI, tf − 1ik[x, t]

Applications - The Shape Lemma

(Rouillier’s talk) I ⊂ k[x] a zero-dimensional ideal (k perfect).

G a reduced Gr¨obner basis of √

I w.r.t. a lexicographical order x r x_n >> x_n. If x_n separate the points of V¯k(I),

then G has the following form:

G = {g_n(x_n);

x_n−1 − g_n−1(x_n);

. . .

x₁ − g₁(x_n)}

and g_n has no multiple roots in k.

Primary decomposition

Every ideal I ⊂ k[x] can be decomposed as an intersection I = Q₁ ∩ · · · ∩ Q_t

of primary ideals, with √

Q_i = P_i prime.

Primary ideals are a generalization of powers of prime ideals.

√I = p

Q₁ ∩ · · · ∩ p

Q_t = P₁ ∩ · · · ∩ P_t. is the prime decomposition of √

I (some of the primes may be redundant).

The following algorithms don’t work!

• To check if I is radical: Check if f ∈ √

I for all generators of I, using radical membership.

This only says that I ⊂ √ I.

• To compute √

I: compute a Gr¨obner basis G of I and take √ g for each g ∈ G (the usual ”Gr¨obner magic”).

√f = squarefree part of f (= _gcd(f,f^f 0) in characteristic 0)

Perfect and separable

• A polynomial f ∈ k[x] is sep- arable if it has only simple roots in ¯k[x].

• k is perfect if every irre- ducible polynomial f ∈ k[x]

is separable.

• If k is perfect of character- istic p > 0, √^p

a ∈ k for all a ∈ k.

Examples

f = x² − 2 ∈ Q[x] separable

g = x³ − t ∈ Q(t)[x] separable.

g = (x− √³

t)(x−η√³

t)(x−η²√³ t) h = x³ − t ∈ Z₃(t)[x] not separa- ble. h = (x − √³

t)³.

Finite fields, algebraically closed fields and fields of characteristic 0 are perfect.

The 0-dimensional case

Seidenberg algorithm

I ⊂ k[x] a 0-dimensional ideal, k a perfect field.

f_i ∈ I ∩ k[x_i], for i = 1, . . . , n.

g_i = √

f_i, the squarefree part.

Then,

√I = hI, g₁, . . . , g_ni.

Example

I = hy + z, z²i ⊂ Q[y, z].

• z² ∈ I

• y² = (y − z)(y + z) + z² ∈ I. Then,

√I = hy + z, z², y, zi = hy, zi.

The 0-dimensional case

If the field is not perfect, Seiden- berg algorithm might fail.

Example

I = hx^p − t, y^p − ti ⊂ Z_p(t)[x, y].

Both polynomials are squarefree, but x^p − y^p ∈ I and therefore x − y ∈ √

I r I.

The separable part

f = c Q

(x − α_i)^di Q

(x − β_i)^pei Computation of Q

(x − β_i)^ei f⁰ = X

d_i f x − α_i h := gcd(f, f⁰)

= Y

(x − α_i)^di−1 Y

(x − β_i)^pei Iterating,

˜h = Y

(x − β_i)^pei = u(x^p) v := ^p

p˜h = Y

(x − β_i)^ei

∈ K(√^p

t₁, . . . , √^p

t_m)[x]

Computation of Q

(x − α_i)

g = ^f = cQ

(x − α )

Example

Computation of Q

(x − β_i)^ei f = (x − 1)²(x^p − t)

= (x − 1)²(x − √^p t)^p f⁰ = 2(x − 1)(x − √^p

t)^p = 2 f x − 1 h = (x − 1)(x − √^p

t)^p h˜ = (x − √^p

t)^p = x^p − t v = x − √^p

t

Computation of Q

(x − α_i)^di g₁ = ^(x−1)_(x−1)(x^2(xp^p−t)^−t) = x − 1

sep(f) = (x − 1)(x − √^p t)

The 0-dimensional case over non-perfect fields

Kemper algorithm (2002) I ⊂ k[x] 0-dim ideal, k = K(t₁, . . . , t_m), K perfect of char- acteristic p > 0.

f_i ∈ I ∩ k[x_i], for i = 1, . . . , n.

sep(f_i) ∈ K( ^pri√

t₁ . . . ^pri√

t_m)[x_i] Take g_i ∈ k[y₁, . . . , y_m, x_i] s.t.

sep(f_i) = g_i(√^q

t₁, . . . , √^q

t_m, x_i), q = p^r, r = max{r₁, . . . , r_n},

J = Ik[x₁, . . . , x_n, y₁, . . . , y_m]+

+ hg₁, . . . , g_ni+

+ hy^q − t , . . . , y^q − t i

Example

I = hx^p₁ − t, x^p₂ − ti

⊂ Z_p(t)[x₁, x₂] sep(x^p_i − t) = x_i − √^p

t g_i = x_i − y

J = hx^p₁ − t, x^p₂ − ti+

+ hx₁ − y, x₂ − yi+

+ hy^p − ti ⊂ k[x₁, x₂, y]

G = {y − x₂, x₁ − x₂, x^p₂ − t}

√I = hx − x , x^p − ti

The general case over finite fields

Matsumoto algorithm (2001)

I ⊂ k[x] an ideal, with k a finite field of p^r elements φ : f 7→ f^p, f ∈ k[x], morphism

I ⊂ φ⁻¹(I) ⊂ √

I and I = √

I ⇐⇒ I = φ⁻¹(I).

φ_c(P

a_m1,...,mnx^m₁ ¹ . . . x^m_n ⁿ) := P

a^p_m1,...,mnx^m₁ ¹ . . . x^m_n ⁿ φ_v(f(x₁, . . . , x_n)) := f(x^p₁, . . . , x^p_n)

φ = φ_v ◦ φ_c

Matsumoto algorithm

Let I = hf₁, . . . , f_si.

Computation of φ⁻¹_c (I)

φ⁻¹_c (I) = hφ⁻¹_c (f₁), . . . , φ⁻¹_c (f_s)i Computation of φ⁻¹_v (I)

J = I + hy₁ − x^p₁, . . . , y_n − x^p_ni φ⁻¹_v (I) = J ∩ k[y₁, . . . , y_n], with y_i replaced by x_i.

We have

φ⁻¹(I) = φ⁻¹_v (φ⁻¹_c (I)).

If I = φ⁻¹(I), then √

I = I.

Example in Z₂[x, y, z, w].

• I = hy + z, xz²w, x²z²i

• φ⁻¹_c (I) = I

• J = I +hX −x², Y −y², Z − z², W − w²i

• G = {Y + Z, XZ, w² + W, z² + Z, y + z, xZW, xwZ, x² + X}, Gr¨obner base of J for lexicographical order.

• φ⁻¹(I) = hy + z, xzi

If we iterate, we obtain the same ideal. Therefore,

General case - Reduction to the 0-dimensional case

Maximal independent set u ⊂ x is independent if

I ∩ k[u] = h0i.

u is a maximal independent set if it is not properly included in any other independent set.

Reduction. If u is a maximal independent set,

Ik(u)[x r u]

is 0-dimensional in k(u)[x r u].

pIk(u)[x r u] can be computed by the 0-dimensional case.

Example Let

I = hy+z, xz²w, x²z²i ⊂ Q[x, y, z, w].

u = {x, w} is a maximal inde- pendent set.

I Q(x, w)[y, z] = hy + z, z²i is 0-dimensional in Q(x, w)[y, z].

pI Q(x, w)[y, z] = hy, zi

How to use the 0-dimensional case?

I = Q₁ ∩ · · · ∩ Q_t (unknown) s.t.

Q_i ∩ k[u] = {0} for 1 ≤ i ≤ s and Q_i ∩ k[u] 6= {0} for s + 1 ≤ i ≤ t Then:

• Ik(u)[x r u] ∩ k[x] = Q₁ ∩ · · · ∩ Q_s

• √

I = √

Q₁ ∩ · · · ∩ Q_s ∩ p

Q_s+1 ∩ · · · ∩ √ Q_t

= p

Ik(u)[x r u] ∩ k[x] ∩ p

Q_s+1 ∩ · · · ∩ √ Q_t

= (p

Ik(u)[x r u] ∩ k[x]) ∩ p

Q_s+1 ∩ · · · ∩ √ Q_t.

• J := p

Ik(u)[x r u] ∩ k[x] can be computed (by saturation).

p √

Krick-Logar algorithm (1991)

J := p

Ik(u)[x r u] ∩ k[x]

∃h ∈ k[u] such that

√I = J ∩ p

(I, h).

Now u is not independent with respect to hI, hi.

We can compute p

hI, hi by induction on the number of independent sets.

Example We have

• I = hy + z, xz²w, x²z²i.

• p

I Q(x, w)[y, z]∩Q[x] = hy, zi.

• We can take h := xw.

• √

I = hy, zi ∩ p

hI, xwi.

• Carrying on the algorithm, we get p

hI, xwi = p

hy + z, xi ∩ phw, y + z, z²i.

The last component is redundant.

√I = hy, zi∩p

hy + z, xi = hy+z, xzi.

A different algorithm

J := p

Ik(u)[x r u] ∩ k[x]

√I = J ∩ p

Q_s+1 ∩ · · · ∩ Q_t If √

I 6= J, ∃g in any set of gen- erators of J such that g 6∈ √

I. Then ∃P minimal prime s.t. g 6∈

P and

(I : g^∞) = \

g6∈P_i

Q_i

is the intersection of some com- ponets among Q_s+1, . . . , Q_t.

Iterating with (I : g^∞), we get

Example

• We look for g ∈ hy, zi such that g 6∈ √

I (using Radical Membership).

We take g := z 6∈ √ I.

• (I : z^∞) = hy + z, xw, x²i intersection of new primary components of I.

Let’s finish the example

• I = hy + z, xz²w, x²z²i.

• p

I Q(x, w)[y, z] ∩ Q[x] = hy, zi.

• z 6∈ √

I and I₂ := (I : z^∞) = hy + z, xw, x²i contains only new primary components of I.

• u := {z, w} is a maximal independent set w.r.t. I₂.

• p

I₂ Q(z, w)[x, y] ∩ Q[x] = hy + z, xi.

• We intersect the two ideals found.

P˜ = hy, zi ∩ hy + z, xi = hy + z, xzi.

• All the generators of ˜P are in √

I. Then, √

I ⊂ P˜ ⊂ √ I.

• √

I = hy + z, xzi.

There is a kind of situation that occurs quite frequently when Grobner basis computations are involved:

Even the most sophisticated complexity theory is -at least at present- not strong enough to allow a clear decision between two possible versions of an algorithm. One has therefore to rely on

practical experience, and it is not impossible for different people to arrive at different conclusions.

Thomas Becker, Volher Weispfenning. Gr¨obner Bases.

Springer-Verlag, 1993

References

[1] W. Decker, G. Gruel, G. Pfister. Primary Decomposition: Algorithms and Comparisons.

Algorithmic algebra and number theory, 187-220, 1999.

[2] P. Gianni, B. Trager, and G. Zacharias. Bases and primary decomposition of ideals. J. Symbolic Computation, (6):149–167, 1988.

[3] G. Kemper. The calculation of radical ideals in positive characteristic. J. Symbolic Computation, (34):229–238, 2002.

[4] T. Krick and A. Logar. An algorithm for the computation of the radical of an ideal in the ring of polynomials. AAECC9, Springer LNCS, (539):195–205, 1991.

[5] M. Kreuzer and L. Robbiano. Computational Commutative Algebra 1. Springer-Verlag, 2000.

[6] R. Matsumoto. Computing the radical of an ideal in positive characteristic. J. Symbolic Computation, (32):263–271, 2001.

[7] A. Seidenberg. Constructions in algebra. Trans. Amer. Math. Soc., (197):273–313, 1974.

Other algorithms

M. Caboara, P. Conti, and C. Traverso. Yet another algorithm for ideal decomposition. Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, (12):39–54, 1997.

D. Eisenbud, C. Huneke, and W. Vasconcelos. Direct methods for primary decomposition. Invent.

Math., (110):207–235, 1992.

E. Fortuna, P. M. Gianni, B. M. Trager. Derivations and Radicals of Polynomial Ideals over Fields of Arbitrary Characteristic. J. Symb. Comput., (33):609–625, 2002.