Kombinatorische kommutative Algebra 001

KOMBINATORISCHE KOMMUTATIVE ALGEBRA STEFAN FUMASOLI

1. Monomialideale 1.1. Terme. Festsetzung 1.1. N := {0, 1, 2, . . . }. Unter einem Ring verstehen wir immer einen kommutativen Ring mit Eins ungleich Null. Wir fixieren im folgenden einen Ring R, eine nat¨ urliche Zahl n ∈ N und einen Polynomring u ¨ber R in n Unbestimmten S := R[X1 , . . . , Xn ]. Die leere Vereinigung von Mengen sei leer. Der leere Durchschnitt von Teilmengen T einer festen T Menge M sei M . Ist M eine Menge von M engen, so schreiben wir M := A∈M A. Notation 1.2. Sind M ein R-Modul und N ⊂ M eine Teilmenge, so bezeichnet hN iR ⊂ M den von N in M erzeugten R-Untermodul.

Definition 1.3. Ein Monoid ist ein Paar (M, ∗), bestehend aus einer Menge M und einer assoziativen und kommutativen Verkn¨ upfung ∗ : M × M → M , so dass ein f¨ ur diese Verkn¨ upfung neutrales Element e ∈ M existiert. Seien (M, ∗) und (M 0 , ∗0 ) zwei Monoide. Eine Abbildung µ : M → M 0 ist ein Homomorphismus von Monoiden, wenn µ(u ∗ v) = µ(u) ∗0 µ(v) f¨ ur alle u, v ∈ M gilt und wenn µ(e) ∈ M 0 das neutrale Element von M 0 ist, wo e ∈ M das neutrale Element von M ist. Das Monoid (M 0 , ∗0 ) heisst Untermonoid von (M, ∗), falls M 0 eine Teilmenge von M und die Inklusion ein Homomorphismus von Monoiden ist. Beispiele 1.4. A) Die Menge Nn zusammen mit der komponentenweisen Addition + : Nn × Nn → Nn , (a, b) 7→ (a1 + b1 , . . . , an + bn ) ist ein Monoid. B) Jede abelsche Gruppe ist ein Monoid. C) Jeder Ring ist ein Monoid bez¨ uglich seiner Multiplikation. D) Es bestehen die Untermonoide (Nn , +) ⊂ (Zn , +) ⊂ (Qn , +) ⊂ (Rn , +). Notation 1.5. Sei (M, ∗) ein Monoid. F¨ ur zwei Teilmengen A, B ⊂ M setze A ∗ B := {a ∗ b | a ∈ A, b ∈ B}. Definition 1.6. Definiere den Homomorphismus von Monoiden X . : Nn → S, Q n a 7→ X a := ni=1 Xiai . Die Elemente der Menge T(R, n) := X N heissen Terme Date: 9. Februar 2006.

1

2

STEFAN FUMASOLI

von S. Es besteht somit ein kanonischer Isomorphismus von Monoiden Nn ∼ = T(R, n). Besteht u ¨ber R und n keine Unklarheit, so schreiben wir T statt T(R, n). Definition 1.7. Die Menge M := R · T heisst Menge der Monome von S. P Definition 1.8. Ist f ∈ S, so k¨onnen wir f = u∈T γR (f, u) u schreiben mit eindeutigen Koeffizienten γR (f, u) ∈ R, wovon nur endlich viele von 0 verschieden sind. Ist f ∈ S, so heisst die Menge suppR (f ) := {u ∈ T(R, n) | γR (f, u) 6= 0} der Tr¨ager von f . Ist f ∈ M ein Monom der Gestalt f = γu mit γ ∈ R \ {0} und u ∈ T, so setze Lt(f ) := u und Lc(f ) := γ. Ferner setze Lc(0) := 0. Beispiel 1.9. Betrachten wir f := x2 z + y 5 zt3 + xy 2 z 3 t4 + y 3 z 5 t7 ∈ R[x, y, z, t]. Es gilt • • • • •

suppR (f ) = {x2 z, y 5 zt3 , xy 2 z 3 t4 , y 3 z 5 t7 }; suppR[x] (f ) = {z, y 5 zt3 , y 2 z 3 t4 , y 3 z 5 t7 }; suppR[x,y] (f ) = {z, zt3 , z 3 t4 , z 5 t7 }; suppR[x,y,z] (f ) = {1, t3 , t4 , t7 }; suppR[x,y,z,t] (f ) = {1}.

Lemma 1.10. Seien A ⊂ Nn eine nicht leere Teilmenge und f ∈ hX A iS ∩ M ein Monom. Dann existiert a ∈ A, so dass X a |f . Beweis. Ohne Einschr¨ankung sei f 6= 0. Es existieren endlich Pr vieleai a1 , . . . , ar ∈ A und Monome f1 , . . . , fr ∈ M \ {0}, so dass f = ist. Ini=1 fi X dem wir die u ussigen Summanden streichen, k¨onnen wir ferner annehmen, ¨berfl¨ dass suppR (f1 X a1 ) = · · · = suppR (fr X ar ) = {Lt(f )} gilt. Es folgt Lt(f ) = Lt(f1 X a1 ) = Lt(f1 ) X a1 und damit f = Lc(f ) Lt(f1 ) X a1 .  1.2. Monomialideale. Definition 1.11. Ein Ideal a ⊂ S heisst Monomialideal, wenn a von einer Teilmenge von M erzeugt wird. Definition 1.12. Seien (G, ∗) ein Monoid und deg : Nn → G ein Homomorphismus von Monoiden. Dieser induziert ur g ∈ G setze Lauf S eine G-Graduierung: F¨ −1 Sg := hX deg (g) iR . Dann gilt S = g∈G Sg und Sg · Sh ⊂ Sg∗h f¨ ur g, h ∈ G. Sei a ⊂ S ur g ∈ G setze ag := a∩Sg . Das Ideal a heisst G-graduiert, Lein Ideal. F¨ wenn a = g∈G ag . P Beispiele 1.13. A) Der Homomorphismus deg : Nn → Z, a 7→ ni=1 ai induziert die Standard-Z-Graduierung. B) Der identische Homomorphismus deg = idNn induziert die Standard-Multigraduierung. Die standard-multigraduierten Ideale sind genau die Monomialideale.

KOMBINATORISCHE KOMMUTATIVE ALGEBRA

3

1.3. Termideale. Definition 1.14. Ein Ideal a ⊂ S heisst Termideal, wenn a von einer Teilmenge von T erzeugt wird. Bemerkung 1.15. Jedes Termideal ist ein Monomialideal. Ist R ein K¨orper, so sind die Termideale genau die Monomialideale. Definition 1.16. Sei (M, ∗) ein Monoid. Eine Teilmenge A ⊂ M heisst Monoidideal, wenn M ∗ A ⊂ A. Die Menge der Monoidideale von Nn bezeichnen wir mit M(n). Bemerkung 1.17. Sei (M, ∗) ein Monoid. Beliebige Durchschnitte und Vereinigungen von Monoididealen von M sind wieder Monoidideale von M . Sind A, B ⊂ M Monoididieale, so ist auch A ∗ B ein Monoidideal. Lemma 1.18. Es besteht eine Bijektion I : M(n) → {a ⊂ S | a ist ein Termideal}, A 7→ hX A iS . Dabei gilt f¨ ur alle A, B ∈ M(n): • • • •

I(A ∩ B) = I(A) ∩ I(B), I(A ∪ B) = I(A) + I(B), I(A + B) = I(A) · I(B), A B ⇒ I(A) I(B).

Beweis. Sei a ⊂ S ein Termideal. Setze A := {a ∈ Nn | X a ∈ a}. Man sieht leicht, dass A ⊂ Nn ein Monoidideal ist mit I(A) = a. Dies zeigt, dass I surjektiv ist. Sei B ⊂ Nn ein Monoidideal. Setze A := {a ∈ Nn | X a ∈ I(B)}. Offensichtlich gilt B ⊂ A. Die umgekehrte Inklusion folgt aus Lemma 1.10. Dies zeigt, dass I auch injektiv ist. Die zus¨atzlichen Eigenschaften sind leicht zu u ufen.  ¨ berpr¨ Korollar 1.19 (Rechenregeln f¨ ur Termideale). Seien a, b, c ⊂ S Termideale. Dann gilt • (a ∩ b) + c = (a + c) ∩ (b + c), • (a + b) ∩ c = (a ∩ c) + (b ∩ c). Korollar 1.20 (Dicksons Lemma). Jedes Termideal besitzt genau ein endliches aus Termen bestehendes minimales Erzeugendensystem. Insbesondere wird jede aufsteigende Kette a1 ⊂ a2 ⊂ a3 ⊂ . . . von Termidealen station¨ar. Beweis. Folgt aus Lemma 1.18, Bemerkung 2.12 B) und Satz 2.13. Definition 1.21. Ein echtes Ideal q √ die Inklusion (q :S a) ⊂ q gilt.



S heisst prim¨ar, wenn f¨ ur alle a ∈ S \ q

4

STEFAN FUMASOLI

Lemma 1.22. Es sei ( P :=

) r, s ∈ N, i1 , . . . , ir ∈ {1, . . . , n}, hXia11 , . . . , Xiarr , u1 , . . . , us iS a1 , . . . , ar ∈ N \ {0}, . u1 , . . . , us ∈ T ∩ R[Xi1 , . . . , Xir ]

a) Jedes prim¨are Termideal von S liegt in P . b) Ist R ein Integrit¨atsbereich, so ist jedes echte Ideal in P prim¨ar.

Beweis. a) Sei q ⊂ S ein prim¨ares Termideal. Nach Dicksons Lemma existiert eine endliche, minimale, aus Termen bestehende Erzeugendenmenge M von q. Sei u ∈ M . Schreibe u = Xia11 · · · Xiarr mit 0 < i1 0. W¨ahle j ∈ {1, . . . , r}. Weil M minimal ist, ist k6=j Xiakk ∈ / q. Weil q prim¨ar ist, ist dann aber eine Potenz von Xij in q. Dann ist aber auch eine Potenz von Xij in M . b) Sei q ∈ P ein echtes Ideal. Schreibe q = hXia11 , . . . , Xiarr , u1 , . . . , us iS mit 0 < i1 < · · · < ir ≤ n, a1 , . . . , ar ≥ 1, u√ 1 , . . . , us ∈ T ∩ R[Xi1 , . . . , Xir ] \ {1}. Dann gilt q ⊂ p := hXi1 , . . . , Xir iS und p ⊂ q. Setze R0 := R[Xj | j ∈ {1, . . . , n} \ {i1 , . . . , ir }].

0 Es gilt :S a). Wir m¨ ussen √ S = R [Xi1 , . . . , Xir ]. Seien a ∈ S \ q und b ∈ (q b ∈ q zeigen. Schreibe a = e + g, b = f + h mit e, f ∈ R0 und g, h ∈ p. Es gilt ef = ab − eh − f g − gh ∈ p, woraus ef = 0 folgt. Wir zeigen nun, dass f ein Nullteiler von S ist. Ist e 6= 0, so stimmt dies wegen ef = 0. Sei also e = 0. Es gilt dann a ∈ p \ q. Schreibe a = p + q mit q ∈ q und p ∈ S, so dass suppR (p) ∩ q = ∅ ist. Es folgt pf + ph = pb = ab − qb ∈ q. Wegen suppR (pf ) ∩ q = ∅ wird folglich jeder Summand von pf weggek¨ urzt durch einen Summanden von ph. Es muss daher suppR (pf ) ⊂ suppR (ph) gelten. Nach Voraussetzung ist p 6= 0. Ist pf = 0, so ist f eine Nullteiler. Nehmen wir nun an, es gelte Pr pf 6= 0. Definiere den Homomorphismus von Monoiden deg : T → N, c ahle u ∈ suppR (pf ), so dass deg(u) minimal ist. W¨ahle v, X → j+1 cij . W¨ v 0 ∈ suppR (p), w ∈ suppR (f ) und w 0 ∈ suppR (h), so dass u = vw = v 0 w 0 ist. Wegen h ∈ p ist deg(w 0 ) ≥ 1. Es folgt deg(v 0 ) < deg(u) und wegen f ∈ R0 auch deg(v 0 x) < deg(u) f¨ ur alle x ∈ suppR (f ). Wegen der Minimalit¨atseigenschaft von deg(u) folgt daraus γR (p, v 0 ) v 0 f = 0, wo γR (p, v 0 ) wie in 1.8 definiert ist. Also ist auch in diesem Fall f ein Nullteiler von S. Wenn nun R ein Integrit¨ √ atsbereich ist, so ist auch S integer, und es folgt f = 0 und damit b = h ∈ p ⊂ q. 

Definition 1.23. Eine endliche Menge M von Idealen von S heisst irredundante Prim¨arzerlegung eines Ideals a ⊂ S, wenn gilt: • • • •

Die Elemente von M sind prim¨ √ar; √ ∀q ∈TM , ∀p ∈ M : q 6= p ⇒ q 6= p; a = q∈M q; T a 6= q∈M \{p} q ∀p ∈ M .

KOMBINATORISCHE KOMMUTATIVE ALGEBRA

5

Eine aus Termidealen bestehende irredundante Prim¨arzerlegung M eines Ideals a ⊂ S heisst maximal, wenn f¨ ur jede weitere aus Termidealen bestehende irredundante Prim¨arzerlegung M 0 von a gilt √ √ • ∀q ∈ M , ∀p ∈ M 0 : q = p ⇒ q ⊃ p. Beispiel 1.24. Es sei a := hx2 z, y 5 zt3 , xy 2 z 3 t4 , y 3 z 5 t7 i ⊂ Q[x, y, z, t]. Die Menge {hzi, hx2 , xy 2 , y 3 i, hx2 , t3 i, hx2 , y 5 , z 5 , xy 2 z 3 i, hx2 , y 5 , xy 2 t4 , t7 i}

ist eine irredundante Prim¨arzerlegung von a. Sie ist aber nicht maximal, denn auch {hzi, hx2 , xy 2 , y 3 i, hx2 , t3 i, hx2 , y 5 , z 5 , xz 3 i, hx2 , y 5 , xt4 , t7 i} ist eine irredundante Prim¨arzerlegung von a. Diese ist sogar maximal. Es gibt unendliche Familien von irredundanten Prim¨arzerlegungen von a, n¨amlich zum Beispiel
{hzi, hx2 , xy 2 , y 3 i, hx2 , t3 i, hx2 , y 5 , z 5 , xy 2 z 3 i, hx2 , y 5 , xy 2 t4 , y 2 t7 , t7+k i} k∈N . Definition 1.25. Sei a ⊂ S ein Ideal. Die Menge der zu S/a assoziierten Primideale ist definiert als Ass(S/a) := {p ∈ Spec(S) | ∃f ∈ S : p = (a :S f )}.

Erinnerung 1.26. Ist S ein G-graduierter Ring bez¨ uglich einer geordneten abelschen Gruppe (G, <) und ist a ⊂ S ein G-graduiertes Ideal, so sind die zu S/a assoziierten Primideale G-graduiert, und f¨ ur jedes assoziierte Primideal p ∈ Ass(S/a) existiert g ∈ G und f ∈ Sg mit p = (a :S f ).1

Lemma 1.27. Seien R integer, a ⊂ S ein Termideal und p ∈ Ass(S/a). Dann ist p ein Termideal und es existiert u ∈ T mit p = (a :S u).

Beweis. Verm¨oge deg : Nn → Zn , a → a wird S zu einem Zn -graduierten Ring und a ⊂ S als Monomialideal zu einem Zn -graduierten Ideal. Indem wir die abelsche Gruppe Zn mit einer mit der Gruppenstruktur vertr¨aglichen Totalordnung versehen (zum Beispiel mit der lexikographischen), k¨onnen wir 1.26 anwenden. Es ist also p ein Monomialideal und es existiert ein Monom f ∈ M mit p = (a :S f ). Sei g ∈ p ∩ M \ {0}. Weil p prim ist, gilt f 6= 0. Weil R integer ist, gilt Lt(f g) = Lt(f ) Lt(g). Weil a ein Termideal ist, gilt Lt(f g) ∈ a. Es folgt f Lt(g) = Lc(f ) Lt(f ) Lt(g) = Lc(f ) Lt(f g) ∈ a und damit Lt(g) ∈ p. Dies zeigt, dass p ein Termideal ist. Es folgt weiter g Lt(f ) = Lc(g) Lt(f ) Lt(g) = Lc(g) Lt(f g) ∈ a und damit g ∈ (a :S Lt(f )). Dies zeigt p = (a :S Lt(f )), da p ⊃ (a :S Lt(f )) klar ist.  Korollar 1.28 (Erster Eindeutigkeitssatz f¨ ur Prim¨arzerlegungen). Seien R ein Integrit¨atsbereich, a ⊂ S ein Termideal und M eine aus Termidealen bestehende √ irredundante Prim¨arzerlegung von a. Dann gilt Ass(R/a) = { q | q ∈ M }.2 1Siehe

z.B. Maria-Helena Seiler: Graduierte Ringe und Moduln, Seminarvortrag 8. Juni 2005, Proposition 2.9 und Corollar 2.10. 2Falls R Noethersch ist, gilt diese Aussage f¨ ur beliebige Ideale. Siehe z.B. M. Brodmann: Kommutative Algebra. Vorlesung SS 2005, Satz (4.27).

6

STEFAN FUMASOLI

Beweis. Folgt aus Lemma 1.18, Lemma 1.22, Bemerkung 2.65 C) und Satz 2.66.  Korollar 1.29. Ist R ein Integrit¨atsbereich, so besitzt jedes Termideal von S genau eine maximale aus Termidealen bestehende irredundante Prim¨arzerlegung. Beweis. Folgt aus Lemma 1.18, Lemma 1.22, Satz 2.34 und Korollar 1.28.



Korollar 1.30 (Maclagans Lemma). Sei M eine unendliche Menge von Termidealen. Dann existieren a, b ∈ M mit a b. Insbesondere existiert eine unendliche echt absteigende Kette a1 ! a2 ! a3 ! . . . von Termidealen ai ∈ M . Beweis. Folgt aus Lemma 1.18 und Satz 2.73



2. Monoidideale 2.1. Die kanonische Ordnung auf Nn . Definition 2.1. Wir definieren auf Nn folgendermassen eine Ordnung. Sind a, b ∈ Nn , so sei a ≥ b genau dann, wenn ai ≥ bi f¨ ur alle i. Definition 2.2. F¨ ur a, b ∈ Nn setze a ∧ b := (min{a1 , b1 }, . . . , min{an , bn }) und a ∨ b := (max{a1 , b1 }, . . . , max{an , bn }).

Bemerkung 2.3. Seien a, b ∈ Nn . A) Es gilt a ≥ b genau dann, wenn X b |X a . B) X a∧b = ggT(X a , X b ). C) X a∨b = kgV(X a , X b ). D) a ∧ b ist in Nn das gr¨osste Element unter denen, die kleiner sind sowohl als a als auch als b. E) a ∨ b ist in Nn das kleinste Element unter denen, die gr¨osser sind sowohl als a als auch als b. F) Jede absteigende Kette a1 ≥ a2 ≥ a3 ≥ . . . von Elementen ai ∈ Nn wird station¨ar. Insbesondere enth¨alt jede nicht leere Teilmenge von Nn ein minimales Element. G) (Nn , ∨) ist ein Monoid mit neutralem Element 0 = (0, . . . , 0). Notation 2.4. Ist (M, ≤) eine geordnete Menge, so bezeichne Min M die Menge der minimalen Elemente von M und Max M die Menge der maximalen Elemente von M . Lemma 2.5. Sei (M, ≤) eine geordnete Menge mit der Eigenschaft, dass jede unendliche Teilmenge M 0 ⊂ M zwei Elemente a, b ∈ M 0 mit a < b besitzt. Dann ist Min M endlich. Beweis. W¨are Min M unendlich, so g¨abe es nach Voraussetzung zwei Elemente a, b ∈ Min M mit a < b. Dann w¨are aber b in M nicht minimal. 

KOMBINATORISCHE KOMMUTATIVE ALGEBRA

7

Bemerkung 2.6 (Schubfachprinzip). Eine endliche Vereinigung endlicher Mengen ist endlich. Daraus folgt umgekehrt: Ist eine Vereinigung endlich vieler Mengen unendlich, so muss schon eine der Mengen unendlich sein. Lemma 2.7. Sei (M, ≤) eine unendliche geordnete Menge mit folgenden Eigenschaften: (i) Jede nicht leere Teilmenge von M besitzt ein minimales Element. (ii) Jede unendliche Teilmenge M 0 ⊂ M besitzt zwei Elemente a, b ∈ M 0 mit a < b. Dann existiert eine unendliche, echt aufsteigende Kette a0 < a1 < a2 < . . . von Elementen ai ∈ M . Beweis. Wir konstruieren induktiv eine Folge (Mi )i∈N von unendlichen Teilmengen Mi ⊂ M und eine Folge (ai )i∈N von Elementen ai ∈ Mi , so dass ai < a f¨ ur alle a ∈ Mi+1 ist f¨ ur alle i ∈ N. Dann gilt offensichtlich a0 < a1 < a2 < . . . . Wir setzen M0 := M und nehmen an, dass f¨ ur i ∈ N eine unendliche Menge Mi ⊂ M bereits konstruiert ist. Die Menge Min Mi ist nach Voraussetzung (i) nicht leer und nach Voraussetzung (ii) und Lemma 2.5 endlich. Da Mi unendlich ist, existieren nach dem Schubfachprinzip ein minimales Element ai ∈ Min Mi und eine unendliche Teilmenge Mi+1 ⊂ Mi , so dass ai < a f¨ ur alle a ∈ Mi+1 ist.  Lemma 2.8. Sei M ⊂ Nn eine unendliche Menge. Dann existiert eine unendliche, echt aufsteigende Kette a0 < a1 < a2 < . . . von Elementen ai ∈ M . Insbesondere existieren a, b ∈ M mit a < b.

Beweis. Nach Lemma 2.7 und Bemerkung 2.3 F) gen¨ ugt es zu zeigen, dass jede unendliche Teilmenge M 0 ⊂ M zwei Elemente a, b ∈ M 0 mit a < b besitzt. Sei also M 0 ⊂ M eine unendliche Teilmenge. Wir machen Induktion nach n ∈ N. F¨ ur n = 0 ist nichts zu zeigen. F¨ ur n = 1 0 ist M eine wohlgeordnete Menge. Sei also n > 1. Definiere N := {(a1 , . . . , an−1 ) ∈ Nn−1 | (a1 , . . . , an ) ∈ M 0 }. Ist N endlich, so existieren nach dem Schubfachprinzip ein Element (a1 , . . . , an−1 ) ∈ N und eine unendliche Teilmenge M 00 ⊂ M 0 mit (b1 , . . . , bn−1 ) = (a1 , . . . , an−1 ) f¨ ur alle 00 00 (b1 , . . . , bn ) ∈ M . Nach dem Fall n = 1 ist dann M wohlgeordnet. Nehmen wir nun an, N sei unendlich. Nach Induktionsvoraussetzung existiert eine unendliche, echt aufsteigende Kette a(0) < a(1) < a(2) < . . . von Elementen (i) (i) a(i) ∈ N . F¨ ur jedes i ∈ N w¨ahle ein ai ∈ N, so dass (a1 , . . . , an−1 , ai ) ∈ M 0 . N¨ahmen wir f¨alschlicherweise an, es g¨alte a ≮ b f¨ ur alle a, b ∈ M 0 mit a 6= b, so g¨alte a0 > a1 > a2 > . . . , was aber unm¨oglich ist.  2.2. Monoidideale von Nn sind endlich erzeugt. Bemerkung 2.9. Seien (M, ∗) ein Monoid und A ⊂ M eine Teilmenge. Dann ist M ∗ A ein Monoidideal.

8

STEFAN FUMASOLI

Definition 2.10. Seien (M, ∗) ein Monoid und A ⊂ M eine Teilmenge. Wir setzen hAi := M ∗ A und sagen, das Monoidideal hAi sei von A erzeugt. Sind a1 , . . . , ar ∈ M endlich viele Elemente, so schreiben wir ha1 , . . . , ar i := h{a1 , . . . , ar }i.

Bemerkung 2.11. Sei M ein Monoid. A) Sei A ⊂ M eine Teilmenge. Dann ist hAi der Durchschnitt aller Monoidideale von M , welche A enthalten. B) Seien A ⊂ M eine Teilmenge und B ⊂ M ein Monoidideal. Es gilt B = hAi genau dann, wenn A ⊂ B ⊂ hAi ist. S C) Sei A ⊂ M eine Teilmenge. Dann gilt hAi = a∈A hai. D) Seien A, B ⊂ M zwei Teilmengen, so dass A ⊂ B ist. Dann gilt hAi ⊂ hBi. Bemerkung 2.12. Sei A ⊂ Nn eine Teilmenge. A) Es gilt hAi = {b ∈ Nn | ∃a ∈ A mit a ≤ b}. B) Es gilt hX hAi iS = hX A iS .

Satz 2.13 (Dicksons Lemma). Ist A ⊂ Nn eine Teilmenge, dann ist hAi = hMin Ai, wobei Min A endlich ist. Insbesondere gilt: a) Jedes Monoidideal von Nn ist endlich erzeugt. b) Jede aufsteigende Kette A1 ⊂ A2 ⊂ A3 ⊂ . . . von Monoididealen Ai ⊂ Nn wird station¨ar. c) Jede nicht leere Menge von Monoididealen besitzt ein bez¨ uglich Inklusion maximales Element. Beweis. Sei A ⊂ Nn eine Teilmenge. Nach Lemma 2.8 und Lemma 2.5 ist Min A endlich. Aus Bemerkung 2.12 A) folgt, dass hAi von Min A erzeugt wird. Daraus folgt auch a). b) Betrachten wir eine aufsteigende Kette S A1 ⊂ A2 ⊂ A3 ⊂ . . . von Monoididealen von Nn . Die Vereinigung A := i∈N Ai ist ein Monoidideal und daher erzeugt von der endlichen Menge Min A. Wir finden i ∈ N, so dass Min A ⊂ Ai ist. Es folgt Aj = Ai f¨ ur alle j ≥ i. c) Sei M ⊂ M(n) eine nicht leere Menge von Monoididealen. Bes¨asse M kein maximales Element, so k¨onnte man eine echt aufsteigende Kette von Monoididealen konstruieren.  2.3. Zerlegungen. Lemma 2.14. Seien A, B ⊂ Nn zwei Teilmengen. Dann gilt hAi∩hBi = hA∨Bi.

Beweis. Mit den Bemerkungen 2.12 und 2.3 E) sieht man sofort, dass A ∨ B ⊂ hAi ∩ hBi ⊂ hA ∨ Bi gilt. 

Notation 2.15. F¨ ur i ∈ {1, . . . , n} definiere ei ∈ Nn durch ( 1, falls i = j, (ei )j = 0, sonst.

KOMBINATORISCHE KOMMUTATIVE ALGEBRA

9

Ist a ∈ Nn , so bezeichne supp(a) := i ∈ {1, . . . , n} ai 6= 0 den Tr¨ager von a. Ist A ⊂ Nn eine Teilmenge, so setze  bAc := i ∈ {1, . . . , n} ∃k ∈ N \ {0} : kei ∈ A . 

Es bezeichne (

P(n) :=

) r, s ∈ N, i1 , . . . , ir ∈ {1, . . . , n}, ha1 ei1 , . . . , ar eir , u1 , . . . , us i ∈ M(n) a1 , . . . , ar ∈ N\{0}, u1 , . . . , us ∈ Nn : supp(u1 ), . . . , supp(us ) ⊂ {i1 , . . . , ir }

die Menge der prim¨aren Monoidideale. Es bezeichne n die Potenzmenge von {1, . . . , n}.

Definition 2.16. Eine Abbildung Z : n → P(n) heisst Zerlegung, wenn f¨ ur n jedes I ∈ Z(I) = Nn oder bZ(I)c = I n gilt. → P(n) heisst Zerlegung von A ∈ M(n), wenn T Eine Zerlegung Z : I∈ n Z(I) = A ist. Sei M eine Menge. Eine Abbildung Z : M → P(n) heisst irredundant, wenn f¨ ur alle J ∈ M gilt \ Z(I) ⊂ Z(J) ⇒ Z(J) = Nn .


I∈M \{J}

Definiere Z(n) := {Z :

n

→ P(n) | Z ist eine irredundante Zerlegung}.

Bemerkung 2.17. A) Es gilt X ei = Xi f¨ ur alle i ∈ {1, . . . , n}. Es gilt bNn c = {1, . . . , n} = bhe1 , . . . , en ic, aber he1 , . . . , en i Nn . T T B) Sei M ⊂ M(n) eine endliche Menge. Dann gilt b A∈M Ac = A∈M bAc. n Sind insbesondere alle Elemente von M prim¨ar, ist M 6= ∅ und T gibt es ein I ∈ mit ur alle A ∈ M , so ist nach Lemma 2.14 auch A∈M A prim¨ar mit T bAc = I f¨ b A∈M Ac = I. n pC) Ist der Ring R reduziert und ist A ∈ P(n) \ {N }, so gilt hXi | i ∈ bAciS = hX A iS . D) Ist R ein Integrit¨atsbereich, so entsprechen die prim¨aren Termideale von S genau den echten prim¨aren Monoididealen von Nn (vgl. Lemma 1.22). Ist A ∈ M(n), so entsprechen die irredundanten Prim¨arzerlegungen von hX A iS genau den irredundanten Zerlegungen von A. Lemma 2.18. Sei Z : n → P(n) Dann existiert eine irredunT eine Zerlegung. T dante Zerlegung Y ∈ Z(n) mit I∈ n Y (I) = I∈ n Z(I).





Beweis. Wir machen Induktion nach r := #{I ∈ n | Z(I) 6= Nn }. F¨ ur r = 0 ist die Aussage trivial. Sei also r > 0. Ist Z nicht irredundant, so existiert J ∈ n T mit I∈ n \{J} Z(I) ⊂ Z(J). Definiere die Zerlegung ( Nn , falls I = J; W : n → P(n), I 7→ Z(I), sonst.


10

STEFAN FUMASOLI

Dann gilt nat¨ urlich setzung auf W an.

T

I∈

n


W (I) =

T

I∈

n


Z(I). Wende nun die Induktionsvoraus

Algorithmus 2.19. Der Beweis von Lemma 2.18 liefert unmittelbar einen – wenn auch ineffizienten – Algorithmus zur Irredundierung“ von Zerlegungen. Im ” folgenden ist eine Implementierung in CoCoA3 angegeben. Um Beispiele besser lesbar zu machen, arbeiten wir mit Idealen in einem Polynomring u ¨ ber einem K¨orper statt mit Monoididealen: Define IsSubideal(A,B); -- Input: Zwei Ideale A und B -- Output: Falls A Teilmenge von B ist -> TRUE, sonst -> FALSE Return HIntersection(A,B)=A; EndDefine; Define Irredundiere(L); -- Input: Eine Liste L von Idealen -- Output: Eine irredundante Liste W von Idealen mit demselben Durchschnitt. -Ist L eine Zerlegung, so ist auch W eine Zerlegung. For I:=1 To Len(L) Do If Not(L[I]=Ideal(1)) Then W:=WithoutNth(L,I); If IsSubideal(HIntersectionList(W),L[I]) Then Insert(W,I,Ideal(1)); Return Irredundiere(W) EndIf; EndIf; EndFor; Return L; EndDefine; -------------------------------

Satz 2.20. Jedes Monoidideal besitzt eine irredundante Zerlegung. Beweis. Sei A ∈ M(n). Nach Satz 2.13 ist A erzeugt von endlich vielen Elementen u(1) , . . . , u(r) ∈ Nn . F¨ ur k ∈ {1, . . . , n}r setze Bk :=

r [

i=1

F¨ ur I ∈

n

setze Y (I) :=

(i)

huki eki i. \

Bk .

k∈{1,...,n}r {k1 ,...,kr }=I

Sei J ∈ n . Man sieht sofort, dass Bk = Nn oder bBk c = J gilt f¨ ur alle k ∈ {1, . . . , n}r mit {k1 , . . . , kr } = J. Nach Bemerkung 2.17 B) ist insbesondere Y (J) ∈ P(n) mit Y (J) = Nn oder bY (J)c = J. Also ist Y eine Zerlegung. Nach Lemma 2.14 gilt f¨ ur jedes i ∈ {1, . . . , r} (i)

(i)

(i) hu(i) i = hu1 e1 ∨ · · · ∨ u(i) n en i = hu1 e1 i ∩ · · · ∩ hun en i. 3CoCoATeam:

CoCoA: Ein System f¨ ur Computations in Commutative Algebra“, erh¨ altlich ” unter http://cocoa.dima.unige.it.

KOMBINATORISCHE KOMMUTATIVE ALGEBRA

11

Es folgt (1)

(r)

A = hu , . . . , u i = =

\

r [

k∈{1,...,n}r i=1

r [

i=1

(i)

(i)

hu i =

huki eki i =

\

I∈

n




r \ n [

i=1 j=1

(i)

huj ej i

\

Bk =

k∈{1,...,n}r {k1 ,...,kr }=I

\

I∈

Y (I).

n




Nach Lemma 2.18 existiert somit eine irredundante Zerlegung von A.



Algorithmus 2.21. Der Beweis des vorhergehenden Satzes ist konstruktiv. Das heisst er liefert einen Algorithmus zur Bestimmung von irredundanten Zerlegungen: -- Hilfsfunktionen, die in CoCoA 4.5 neuerdings implementiert sind. ------------------------------Define Tupels(L,M); -- Input: eine Menge L und eine natuerliche Zahl M -- Output: die Produktmenge L^M If M=0 Then Return [[]] EndIf; Return [Concat([I[1]],I[2])|I In L> -- Die Menge {X_1, ..., X_n}^r, wo r die Anzahl Erzeuger ist: C:=Tupels(Indets(),Len(G)); -- Die Liste aller Ideale B_k, k in {X_1, ..., X_n}^r: B:=[Ideal([K[I]^Deg(G[I],K[I])|I In 1..Len(G)])|K In C]; -- Die Potenzmenge von {X_1, ..., X_n}: P:=Subsets(Indets()); -- Die Zerlegung Y in Form einer durch die Potenzmenge indizierten Liste: Y:=[HIntersectionList([B[K]|K In 1..Len(C) And EqSet(C[K],J)])|J In P]; -- Eine Irredundierung von Y: Z:=Irredundiere(Y); Return [[P[J],Z[J]]|J In 1..Len(P)]; EndDefine; -------------------------------

12

STEFAN FUMASOLI

Use S::=Q[x,y,z,t]; Zerlegung([x^2z, y^5zt^3, xy^2z^3t^4, y^3z^5t^7]); ------------------------------[[[ ], Ideal(1)], [[t], Ideal(1)], [[z], Ideal(z)], [[z, t], Ideal(1)], [[y], Ideal(1)], [[y, t], Ideal(1)], [[y, z], Ideal(1)], [[y, z, t], Ideal(1)], [[x], Ideal(1)], [[x, t], Ideal(t^3, x^2)], [[x, z], Ideal(1)], [[x, z, t], Ideal(1)], [[x, y], Ideal(x^2, xy^2, y^3)], [[x, y, t], Ideal(x^2, y^5, t^7, xy^2t^4)], [[x, y, z], Ideal(x^2, z^5, y^5, xy^2z^3)], [[x, y, z, t], Ideal(1)]] -------------------------------

Problem 2.22. Der vorangehende Algorithmus ist nicht effizient. Finde einen Algorithmus, der mit wesentlich weniger Operationen auskommt. 2.4. Maximale Zerlegungen. Definition 2.23. Sind Z, Z 0 : n → P(n) zwei Zerlegungen, so sagen wir Z 0 sei in Z enthalten und schreiben Z 0 ⊂ Z, wenn Z 0 (I) ⊂ Z(I) f¨ ur alle I ∈ n gilt. 0 0 0 Wir schreiben Z Z, wenn Z ⊂ Z und Z 6= Z ist. n Eine Zerlegung → P(n) heisst maximal, wenn es keine Zerlegung Z 0 : TZ : n → P(n) von I∈ n Z(I) mit Z Z 0 gibt.


Bemerkung 2.24. A) Maximale Zerlegungen sind irredundant. B) Nach Satz 2.13 b) und Satz 2.20 ist klar, dass jedes Monoidideal eine maximale Zerlegung besitzt. Das Beispiel 1.24 zeigt umgekehrt, dass nicht jedes Monoidideal eine minimale“ Zerlegung besitzt. ” Problem 2.25. A) Finde einen Algorithmus, der entscheidet, ob eine irredundante Zerlegung maximal ist. B) Finde einen Algorithmus, der f¨ ur jedes Monomialideal A eine maximale Zerlegung von A berechnet. C) Ver¨andere die Prozedur Zerlegung() im Algorithmus 2.21 so, dass bereits die Liste B irredundiert wird. Liefert die so ver¨anderte Prozedur immer eine maximale Zerlegung? Define Zerlegung(G); -- Input: ein Erzeugendensystem G eines Termideales in einem zuvor definierten Ring S -- Output: eine irredundante Primaerzerlegung des Ideals -- Die Menge {X_1, ..., X_n}^r, wo r die Anzahl Erzeuger ist: C:=Tupels(Indets(),Len(G)); -- Die Liste aller Ideale B_k, k in {X_1, ..., X_n}^r: B:=[Ideal([K[I]^Deg(G[I],K[I])|I In 1..Len(G)])|K In C]; -- Eine Irredundierung von B: B0:= Irredundiere(B); -- Die Potenzmenge von {X_1, ..., X_n}: P:=Subsets(Indets()); -- Eine Zerlegung Y in Form einer durch die Potenzmenge indizierten Liste: Y:=[HIntersectionList([B0[K]|K In 1..Len(C) And EqSet(C[K],J)])|J In P]; -- Eine Irredundierung von Y: Z:=Irredundiere(Y); Return [[P[J],Z[J]]|J In 1..Len(P)]; EndDefine; ------------------------------Use S::=Q[x,y,z,t];

KOMBINATORISCHE KOMMUTATIVE ALGEBRA

13

Zerlegung([x^2z, y^5zt^3, xy^2z^3t^4, y^3z^5t^7]); ------------------------------[[[ ], Ideal(1)], [[t], Ideal(1)], [[z], Ideal(z)], [[z, t], Ideal(1)], [[y], Ideal(1)], [[y, t], Ideal(1)], [[y, z], Ideal(1)], [[y, z, t], Ideal(1)], [[x], Ideal(1)], [[x, t], Ideal(t^3, x^2)], [[x, z], Ideal(1)], [[x, z, t], Ideal(1)], [[x, y], Ideal(x^2, xy^2, y^3)], [[x, y, t], Ideal(x^2, y^5, t^7, xt^4)], [[x, y, z], Ideal(x^2, z^5, y^5, xz^3)], [[x, y, z, t], Ideal(1)]] -------------------------------

T 0 n Lemma 2.26. Seien Z, Z : → P(n) zwei Zerlegungen mit T I∈ n Z(I)0 = T T 0 n existiert mit I∈ n \{J} Z(I) ⊂ I∈ n \{J} Z (I) I∈ n Z (I), so dass ein J ∈ 0 und Z(J) Z (J). Dann ist Z nicht maximal. ( Z 0 (I), falls I = J; Beweis. Definiere die Zerlegung W : n → P(n), I 7→ Z(I), sonst. Es gilt \ \ \ \ Z(I) ⊂ Z 0 (J) ∩ Z(I) ⊂ Z 0 (I) = Z(I).








I∈

n

I∈







I∈

n \{J}

Also ist auch W eine Zerlegung von

T

I∈

n




n

I∈




Z(I) mit Z

n




W.






Lemma 2.27. Seien A ∈ M(n) und J ∈ n .TSeien Z, Z 0 ∈ Z(n) zwei maximaT le Zerlegungen von A mit I∈ n \{J} Z(I) = I∈ n \{J} Z 0 (I). Dann gilt Z(J) = Z 0 (J).





Beweis. Setze T := {a ∈ Nn | supp(a) ⊂ J}. Nehmen wir an es gelte Z(J) 6= Z 0 (J). Nach Lemma 2.26 gilt Z 0 (J) 6⊂ Z(J), sonst w¨are n¨amlich Z 0 nicht maximal. Es folgt Min(Z 0 (J)) 6⊂ Z(J). Wegen Min(Z 0 (J)) ⊂ T ist T ∩ Z 0 (J) \ Z(J) nicht leer. W¨ahle a ∈ T ∩ Z 0 (J) \ Z(J). Wegen bZ(J)c = J ist Z(J) ∪ hai prim¨ar. Definiere die Zerlegung ( Z(J) ∪ hai, falls I = J; W : n → P(n), I 7→ Z(I), sonst. Es gilt A=

\

I∈



n

Z(I) ⊂




= hai ∩

I∈


\

\

I∈

n



W (I) = hai ∪ Z(J) ∩






Z(I) ∪

n \{J}



\

I∈

n






I∈

n

Z(I) ⊂ Z (J) ∩

setze ∆J := {I ∈

I∈

n

Z(I)

n \{J}

0

Also ist auch W eine Zerlegung von A. Wegen Z maximal. Widerspruch! Notation 2.28. F¨ ur J ∈




\


\

0



Z (I) ∪ A = A.

n \{J}

W ist dann aber Z nicht 

| I ⊂ J}.

Lemma 2.29. Seien A ∈ M(n), J ∈ n und Z : n → P(n) eine Zerlegung von A. Dann gilt \  Z(I) = b ∈ Nn ∃a ∈ A : bi = ai ∀i ∈ J . I∈∆J

14

STEFAN FUMASOLI

Insbesondere h¨angt dieser Durchschnitt nur von A und J ab, nicht aber von der Wahl von Z. Beweis. Setze

 B := b ∈ Nn ∃a ∈ A : bi = ai ∀i ∈ J . Sei ur alle i ∈ J. Es giltSa ∈ A ⊂ T b ∈ B. Dann existiert a ∈ T A, so dass bi = ai f¨ Z(I). W¨ a hle c ∈ Min Z(I) mit c ≤ a. Es gilt supp(c) ⊂ I∈∆J I = I∈∆J I∈∆J J, insbesondere also ci = 0 f¨ ur alle i ∈ {1, . . . , n} \ J. Es folgt c ≤ b und damit T b ∈ I∈∆J Z(I). T Sei umgekehrt b ∈ I∈∆J Z(I). F¨ ur jedes IP ∈ n \ ∆J w¨ahle iI ∈ I \ J und rI ∈ N, so dass rI eiI ∈ Z(I) ist. Setze a := b + I∈ n \∆J rI eiI . Dann ist a ∈ Z(I) T T f¨ ur alle I ∈ n \ ∆J . Insgesamt ist a ∈ I∈∆J Z(I) ∩ I∈ n \∆J Z(I) = A und es gilt bi = ai f¨ ur alle i ∈ J. 





Definition 2.30. Die Elemente von n heissen Simplizes. Die Dimension eines Simplexes I ∈ n ist dim(I) := (#I) − 1. Eine Teilmenge ∆ ⊂ n heisst simplizialer Komplex, falls f¨ ur alle I, J ∈ n gilt I ∈ ∆ und J ⊂ I ⇒ J ∈ ∆.

Die Dimension eines Komplexes ∆ ist definiert als

dim(∆) := sup {dim(I) ∈ Z | I ∈ ∆} ∈ N ∪ {−1, −∞}.

Bemerkung 2.31. Ist J ∈ n , so ist ∆J ein simplizialer Komplex. Vereinigungen von simplizialen Komplexen in n sind simpliziale Komplexe. Insbesondere gilt S ∆ = I∈∆ ∆I . Beispiel 2.32. Den simplizialen Komplex

∆ := {∅, {1}, {2}, {3}, {4}, {1, 2}, {1, 4}, {2, 3}, {2, 4}, {3, 4}, {1, 2, 4}} ⊂

k¨onnen wir visualisieren als ∆{1,2,4} ∪ ∆{2,3} ∪ ∆{3,4} .

4

. Er ist zweidimensional. Ferner gilt ∆ =

Satz 2.33 (Zweiter Eindeutigkeitssatz f¨ ur Prim¨arzerlegungen). Sei A ∈ M(n) n und sei ∆ ⊂ ein simplizialer Komplex.TSeien Z, Z 0 : n → P(n) zwei ZerT legungen von A. Dann gilt I∈∆ Z(I) = I∈∆ Z 0 (I). Insbesondere h¨angt dieser Durchschnitt nur von A und ∆ ab, nicht aber von der Wahl der Zerlegung von A. S Beweis. Wegen ∆ = J∈M ∆J gilt nach Lemma 2.29 \ \ \ \ \ \ Z(I) = Z(I) = Z 0 (I) = Z 0 (I). I∈∆

J∈∆ I∈∆J

J∈∆ I∈∆J

I∈∆



Satz 2.34 (Eindeutigkeitssatz f¨ ur maximale Zerlegungen). Jedes Monoidideal besitzt genau eine maximale Zerlegung.

KOMBINATORISCHE KOMMUTATIVE ALGEBRA

15

Beweis. Seien A ∈ M(n) und seien Z, Z 0 ∈ Z(n) zwei maximale Zerlegungen von A. Nehmen wir an, es gelte Z 6= Z 0 . Setze Γ := {I ∈ n | Z(I) 6=SZ 0 (I)}. Sei J ∈ Γ ein bez¨ uglich der Inklusion maximales Element. Setze ∆ := I∈Γ\{J} ∆I . Dann ist J ∈ / ∆. T T T Nach Satz 2.33 folgt I∈∆ Z(I) = I∈∆ Z 0 (I) und damit I∈ n \{J} Z(I) = T 0 0 I∈ n \{J} Z (I). Nach Lemma 2.27 impliziert dies Z(J) = Z (J). Widerspruch! 





Problem 2.35. Charakterisiere die Menge der maximalen Zerlegungen. 2.5. Quadratfreie Monomialideale. Definition 2.36. Ein Element a ∈ Nn , beziehungsweise ein Term X a ∈ T(R, n) heisst quadratfrei, wenn ai ≤ 1 ist f¨ ur alle i ∈ {1, . . . , n}. Ein Monoidideal, bzw. ein Termideal heisst quadratfrei, wenn es durch quadratfreie Elemente erzeugt wird. Lemma 2.37. √ Sei a ⊂ S ein Monomialideal. a) Auch a ist ein Monomialideal. b) Sei a ein perfektes Termideal. Dann ist a quadratfrei. √ c) Seien R reduziert und a ein Termideal. Dann ist auch a ein Termideal. d) Seien R reduziert und a ⊂ S ein quadratfreies Termideal. Dann ist a perfekt. Beweis. a) Folgt aus 1.13 und der Tatsache, dass Radikale von graduierten Idealen wieder graduiert sind.4 b) P Sei a ∈ Nn , so dass X a ∈ a ist. Setze r := max {ai ∈ N | i ∈ {1, . . . , n}} und b := i∈supp(a) ei . Dann ist a ≤ rb und damit (X b )r ∈ a, folglich ist X b ∈ a. Dies zeigt, dass a von√quadratfreien Termen erzeugt wird. √ c) Nach a) ist a ein Monomialideal. Seien x ∈ R\{0}, u ∈ T, so dass xu ∈ a. Dann existiert r ∈ N, so dass xr ur ∈ a. Ist √ R reduziert, so ist xr √ 6= 0 und folglich r u ∈ a nach Lemma 1.10. Also gilt u ∈ a. Dies zeigt, dass a von Termen erzeugt ist. √ √ d) Nach c) ist a ein Termideal. Sei a ∈ Nn , so dass X a ∈ a ist. Sei r ∈ N \ {0}, so dass (X a )r ∈ a ist. Sei b ∈ Nn quadratfrei mit X b ∈ a, so dass X b |(X a )r gilt. Es ist also b ≤ ra und damit supp(b) ⊂ supp(ra) = supp(a). Es folgt X a ∈ a.  Definition 2.38. F¨ ur einen simplizialen Komplex ∆ ⊂ Stanley-Reisner-Monoidideal P A∆ := h i∈I ei | I ∈ n \ ∆i

n

definieren wir das

und das Stanley-Reisner-Ideal

a∆ := h 4Siehe

Q

i∈I Xi

|I∈

n

\ ∆iS .

z.B. M. Brodmann: Algebraische Geometrie. Eine Einf¨ uhrung, Bemerkung (15.3).

16

STEFAN FUMASOLI

Beispiel 2.39. Das Stanley-Reisner-Ideal des simplizialen Komplexes ∆ = von Beispiel 2.32 im Polynomring R[x, y, z, t] ist a∆ = hxz, yztiS . Satz 2.40. Es besteht eine Bijektion n o ∆ ist simplizialer ∆⊂ n → {A ∈ M(n) | A ist quadratfrei }, ∆ 7→ A∆ , Komplex deren Inverse gegeben ist durch die Zuordnung n

A 7→

\ {supp(a) ∈

n

| a ∈ A ist quadratfrei}.

Beweis. Selbstverst¨andlich sind Stanley-Reisner-Monoidideale quadratfrei, also ist die Abbildung wohldefiniert. 0 n Seien zwei verschiedene simpliziale KomplexeP und I ∈ ∆ \ ∆0 . P∆, ∆ ⊂ W¨are i∈I ei ∈ A∆ , g¨abe es eine Teilmenge J ⊂ I, so dass i∈J ei ∈ Min A∆ w¨are, das heisst, soPdass J ∈ 2 \ ∆ w¨are. Dann w¨are aber ∆ kein simplizialer Komplex. Es folgt i∈I ei ∈ A∆0 \ A∆ . Dies zeigt die Injektivit¨at der Abbildung. Sei A ∈ M(n) quadratfrei. Setze n

∆ :=

\ {supp(a) ∈

n

| a ∈ A ist quadratfrei}.

Seien I ∈ ∆ und J ⊂ I. Wenn J nicht in ∆ w¨are, g¨abe es ein quadratfreies a = supp(a). Weil A ein Monoidideal ist, w¨are dann aber auch P∈ A mit J P / ∆ erg¨abe. Folglich ist ∆ i∈I ei = a + i∈I\J ei ∈ A, was den Widerspruch I ∈ ein simplizialer Komplex. Eine leichte Rechnung zeigt schliesslich A∆ = A und damit Surjektivit¨at: ⊂“: Sei J ∈ n \ ∆. Es existiert ein quadratfreies a ∈ A mit supp(a) = J. Es ” P folgt j∈J ej = a ∈ A. P ⊃“: Sei a ∈ A quadratfrei. Dann ist supp(a) ∈ / ∆. Also ist a = i∈supp(a) ei ∈ ” A∆ .  Problem 2.41. Bestimme #{A ∈ M(n) | A ist quadratfrei}.

Satz 2.42. Sei ∆ ⊂ n ein simplizialer Komplex. Es bezeichne Max ∆ die bez¨ uglich Inklusion maximalen Elemente von ∆. Definiere ( hei | i ∈ Ii, falls {1, . . . , n} \ I ∈ Max ∆, Z∆ : n → P(n), I 7→ Nn , sonst. Dann ist Z∆ die maximale Zerlegung des Stanley-Reisner-Monoidideals A∆ . T Beweis. Es ist klar, dass Z∆ eine Zerlegung ist. Wir zeigen zuerst I∈ n Z∆ (I) = P h i∈I ei | I ∈ n \T∆i. T ⊂“: Sei a ∈ I∈ n Z∆ (I) = I∈Max ∆ hei | i ∈ {1, . . . , n} \ Ii. F¨ ur jedes ” I ∈ Max ∆ w¨ahlen wir jI ∈ supp(a) \ I. Setze J := {jI | I ∈ Max ∆}. Nehmen wir f¨alschlicherweise an, es sei J ∈ ∆. Wir w¨ahlen J 0 ∈ Max ∆ mit J ⊂ J 0 . Dann ist jJ 0 ∈ J,Pwas der Wahl \ J 0 widerspricht. Somit ist J ∈ n \ ∆ P von jJ 0 ∈ supp(a) und a ∈ h i∈J ei i ⊂ h i∈I ei | I ∈ n \ ∆i.





KOMBINATORISCHE KOMMUTATIVE ALGEBRA

17

n \ ∆ und J ∈ n . Ist {1, . . . , n} \ J ∈ / Max ∆, so ist nat¨ urlich P”⊃“: Seienn I ∈ e ∈ N = Z (J). Ist {1, . . . , n} \ J ∈ Max ∆, so gilt I ∩ J = 6 ∅, denn sonst i ∆ i∈I P w¨are I ⊂ {1, . . .P , n} \ J und damit I ∈ ∆. Dies zeigt e ∈ he | j ∈ Ji = j i∈I i T Z∆ (J). Es folgt i∈I ei ∈ I∈ n Z∆ (I).


Als n¨achstes zeigen wir, dass Z∆ maximal ist. Nehmen wir im Gegenteil an, Z∆ sei nicht maximal. Weil Z∆ (I) quadratfrei ist f¨ ur alle I ∈ n , ist dann Z∆ nicht irredundant. Es existiert also J ∈ n mit {1, . . . , n} \ J ∈ Max ∆ und \ \ Z∆ (I) ⊂ Z∆ (J) = hej | j ∈ Ji. hei | i ∈ Ii = I∈ n \{J}: {1,...,n}\I∈Max ∆


I∈




n \{J}

Folglich existiert I ∈ n mit {1, . . . , n} \ I ∈ Max ∆ und I J. Dann ist aber {1, . . . , n}\J {1, . . . , n}\I ∈ ∆, also {1, . . . , n}\J ∈ / Max ∆. Widerspruch!  Beispiel 2.43. Das Stanley-Reisner-Ideal des simplizialen Komplexes ∆ = von Beispiel 2.32 im Polynomring R[x, y, z, t] ist a∆ = hxz, yztiS = hziS ∩ hx, yiS ∩ hx, tiS . Problem 2.44. Implementiere einen Algorithmus zur Bestimmung maximaler Prim¨arzerlegungen von quadratfreien Termidealen mit Hilfe von simplizialen Komplexen. 2.6. Alexanderdual und irreduzible Zerlegungen. Notation 2.45. ur a ∈ Nn definiere ea := hai ei | ai ≥ 1i ∈ M(n). Pn F¨ Setze 1 := i=1 ei = (1, . . . , 1) ∈ Nn .

Lemma 2.46. Seien a, b ∈ Nn . Dann gilt a  b genau dann, wenn a ∈ eb+1 ist.

Beweis. Es gilt a  b genau dann, wenn ein i ∈ {1, . . . , n} mit ai ≥ bi +1 existiert, genau dann, wenn ein i ∈ {1, . . . , n} mit a ≥ (bi +1)ei existiert, genau dann wenn  a ∈ h(b1 + 1)e1 , . . . , (bn + 1)en i = eb+1 ist.

Definition 2.47. Es bezeichne I(n) := {ea ∈ M(n) | a ∈ Nn } die Menge der irreduziblen Monoidideale. Eine endliche Teilmenge T Z ⊂ I(n) heisst irreduzible Zerlegung eines Monoidideals A ∈ M(n), wenn Z = A gilt. Eine endliche Teilmenge Z ⊂ I(n) heisst T irredundant, wenn (Z \ {z}) 6⊂ z ist f¨ ur alle z ∈ Z.

Bemerkung 2.48. Es gilt Nn ∈ / I(n) und I(n) ⊂ P(n).

¨ Ubungsaufgabe 2.49. Ein echtes Monoidideal von Nn ist genau dann irreduzibel (im Sinne von Definition 2.47), wenn es sich nicht als Durchschnitt von zwei echt gr¨osseren Monoididealen schreiben l¨asst. Bemerkung 2.50. Wie in Kapitel 2.3 beweist man leicht, dass jedes Monoidideal eine irredundante irreduzible Zerlegung besitzt.

18

STEFAN FUMASOLI

Satz 2.51 (Kriterium f¨ ur irredundante irreduzible T Zerlegungen). Seien Z ⊂ I(n) eine endliche Teilmenge und A ∈ I(n) \ Z mit Z ⊂ A. Dann existiert B ∈ Z mit B ⊂ A. (1)

(r)

Beweis. Wir schreiben A = ea und Z = {eb , . . . , eb } mit geeigneten a, b(i) ∈ (i) Nn . Wir nehmen an, dass eb 6⊂ A gilt f¨ ur alle i ∈ {1, . . . , r}. F¨ ur jedes i ∈ (i) (i) {1, . . . , r} existiert dann ji ∈ {1, . . . , n} mit bji 6= 0, so dass bji eji ∈ / A ist. Tr b(i) (1) (r) Setze c := bj1 ej1 ∨ · · · ∨ bjr ejr . Nach Lemma 2.14 gilt dann c ∈ i=1 e ⊂ A. Somit existiert k ∈ {1, . . . , n} mit ak > 0 und ak ek ≤ c. Es folgt ak ≤ ck . W¨ahle (l) (l) l ∈ {1, . . . , r} mit jl = k und ck = bjl . Aus ak ≤ bjl und ak ek ∈ A folgt der (l) Widerspruch bjl ejl ∈ A.  Notation 2.52. F¨ ur a, b ∈ N mit b ≤ a schreibe ( a − b + 1, falls b ≥ 1, a \ b := 0, sonst. F¨ ur a, b ∈ Nn mit b ≤ a schreibe a \ b := (a1 \ b1 , . . . , an \ bn ) und a − b := (a1 − b1 , . . . , an − bn ). Bemerkung 2.53. Sind a, b ∈ Nn mit b ≤ a, so gilt a \ b ≤ a und a \ (a \ b) = b. Definition 2.54. F¨ ur a ∈ Nn und A ∈ M(n) mit b ≤Ta f¨ ur alle b ∈ Min A [a] definiere das Alexanderdual von A bez¨ uglich a als A := b∈Min A ea\b .

Beispiel 2.55. Seien S := Q[x, y, z, t], a := hx2 z, y 5 zt3 , xy 2 z 3 t4 , y 3 z 5 t7 iS und f := x2 y 5 z 5 t7 . Dann ist in der entsprechenden Notation f¨ ur Termideale statt f¨ ur Monoidideale a[f ] = hx, z 5 iS ∩ hy, z 5 , t5 iS ∩ hx2 , y 4 , z 3 , t4 iS ∩ hy 3 , z, tiS = hxyt4 , xt5 , x2 y 3 , xy 4 , xyz 3 , z 5 , x2 yz, x2 ytiS ,

(a[f ] )[f ] = hx2 , y 5 , t4 iS ∩ hx2 , t3 iS ∩ hx, y 3 iS ∩ hx2 , y 2 iS

∩ hx2 , y 5 , z 3 iS ∩ hziS ∩ hx, y 5 , z 5 iS ∩ hx, y 5 , t7 iS

= hx2 z, y 5 zt3 , xy 2 z 3 t4 , y 3 z 5 t7 iS = a.

Lemma Seien a ∈ Nn und A ∈ M(n) mit b ≤ a f¨ ur alle b ∈ Min A. Dann T 2.56.a−b+1 gilt b∈Min A e = ea+1 ∪ A[a] . Beweis. Es gilt

ea+1 ∪ A[a] = ea+1 ∪

\

ea\b =

b∈Min A

\

b∈Min A

(ea+1 ∪ ea\b ).

Sei b ∈ Min A. Es gen¨ ugt ea−b+1 = ea+1 ∪ ea\b zu zeigen.

KOMBINATORISCHE KOMMUTATIVE ALGEBRA

19

⊂“: Sei i ∈ {1, . . . , n}. Falls bi = 0 ist, ist (ai − bi + 1)ei = (ai + 1)ei ∈ ea+1 . ” Andernfalls ist (ai − bi + 1)ei = (ai \ bi )ei ∈ ea\b . ⊃“: Wegen 1 ≤ a−b+1 ≤ a+1 ist klar, dass ea+1 ⊂ ea−b+1 ist. Sei c ∈ Min ea\b . ” Dann existiert i ∈ {1, . . . , n} mit c = (ai \bi )ei , so dass ai \bi 6= 0 ist. Insbesondere  ist dann bi 6= 0 und es folgt c = (ai − bi + 1)ei ∈ ea−b+1 . Lemma 2.57. Seien a ∈ Nn und A ∈ M(n) mit b ≤ a f¨ ur alle b ∈ Min A. Sei n b ∈ N mit b ≤ a. Es gilt b ∈ / A genau dann, wenn a − b ∈ A[a] ist.

Beweis. Es gilt b ∈ / A genau dann, wenn c  b ist f¨ ur alle c ∈ Min A, genau dann, wenn a − b  a − c ist f¨ ur alle c ∈ Min A, nach Lemma 2.46 genau T dann, wenn a − b ∈ ea−c+1 ist f¨ ur alle c ∈ Min A, genau dann, wenn a − b ∈ c∈Min A ea−c+1 ist, nach Lemma 2.56 genau dann, wenn a − b ∈ ea+1 ∪ A[a] ist. Nun ist aber a − b ≤ a, also a − b ∈ / ea+1 . Darum ist a − b ∈ ea+1 ∪ A[a] genau dann, wenn a − b ∈ A[a] ist.  Satz 2.58 (Dualit¨at). Seien a ∈ Nn und A ∈ M(n) mit b ≤ a f¨ ur alle b ∈ Min A. [a] [a] [a] Dann gilt b ≤ a f¨ ur alle b ∈ Min(A ) und (A ) = A. Beweis. Ist b ∈ Min A, so ist mit b ≤ a auch a \ b ≤ a. Insbesondere sind dann die minimalen Erzeuger von ea\b kleiner gleich a. Die erste Aussage folgt nun direkt aus Lemma 2.14. Insbesondere gilt auch b ≤ a f¨ ur alle b ∈ Min((A[a] )[a] ). Sei b ∈ Nn mit b ≤ a. Dann gilt auch a − b ≤ a. Zweimalige Anwendung des Lemmas 2.57 liefert b ∈ A ⇐⇒ b = a − (a − b) ∈ (A[a] )[a] . Da sowohl die minimalen Erzeuger von A als auch die minimalen Erzeuger von (A[a] )[a] kleiner gleich a sind, folgt somit die Aussage.  Lemma 2.59. Seien a, b, c ∈ Nn mit b ≤ a und c ≤ a. Dann gilt a \ b ≤ a \ c genau dann, wenn eb ⊂ ec ist. Beweis. ⇒“: Sei a \ b ≤ a \ c. Sei i ∈ {1, . . . , n} mit bi 6= 0. Wegen ai \ bi ≤ ai \ ci ” ist dann auch ci 6= 0. Es folgt bi ≥ ci und damit bi ei ∈ ec . ⇐“: Es gelte nun eb ⊂ ec . Sei i ∈ {1, . . . , n}. Ist bi = 0, so ist nat¨ urlich ” ai \ bi ≤ ai \ ci . Ist bi 6= 0, so ist wegen bi ei ∈ ec auch ci ≥ 1, und es gilt bi ≥ ci . Auch dann folgt ai \ bi ≤ ai \ ci .  Satz 2.60 (Minimale Erzeuger versus irreduzible Komponenten). Sei A ∈ M(n). W¨ahle a ∈ Nn mit b ≤ a f¨ ur alle b ∈ Min A. Dann ist {ea\b | b ∈ Min(A[a] )} eine irredundante irreduzible Zerlegung von A. Beweis. Setze Z := {ea\b | b ∈ Min(A[a] )}. Nach Satz 2.58 gilt A = (A[a] )[a] = T Z. Also ist Z eine irreduzible Zerlegung von A. Nehmen wir an, Z sei nicht irredundant. Dann existiert c ∈ Min(A[a] ), so T dass (Z \ {ea\c }) = A ⊂ ea\c ist. Nach Satz 2.51 existiert b ∈ Min(A[a] ) \ {c} mit ea\b ⊂ ea\c . Nach Lemma 2.59 und Bemerkung 2.53 folgt b = a \ (a \ b) ≤ a \ (a \ c) = c, was in Widerspruch steht zu c ∈ Min(A[a] ). 

20

STEFAN FUMASOLI

Satz 2.61 (Eindeutigkeitssatz f¨ ur irreduzible Zerlegungen). Jedes Monoidideal besitzt genau eine irredundante irreduzible Zerlegung. Beweis. Sei A ∈ M(n). Seien Z und Z 0 zwei irredundante irreduzible Zerlegungen von A. Schreibe Z = {eb | b ∈ B} und Z 0 = {eb | b ∈ B 0 } mit zwei geeigneten endlichen Mengen B, B 0 ⊂ Nn . W¨ahle a ∈ Nn , so dass b ≤ a ist f¨ ur alle b ∈ B ∪B 0 . Setze C := ha \ b | b ∈ Bi. Sind b, c ∈ B zwei verschiedene Elemente, so gilt eb 6⊂ ec wegen der Irredundanz von Z. Aus Lemma 2.59 folgt dann T a \ b  aa\c\ c. [a] Dies zeigt die Gleichheit Min C = {a \ b | b ∈ B}. Es folgt C = c∈Min C e = T T T a\(a\b) = b∈B eb = Z = A und mit Satz 2.58 auch C = (C [a] )[a] = A[a] . b∈B e Dies zeigt B = {a \ (a \ b) | b ∈ B} = {a \ c | c ∈ Min C} = {a \ c | c ∈ Min A[a] }. Genau gleich zeigt man B 0 = {a \ c | c ∈ Min A[a] }. Daraus folgt sofort Z = Z 0.  Bemerkung 2.62. Satz 2.61 zeigt insbesondere, dass die in Satz 2.60 angegebene irreduzible Zerlegung nicht von der Wahl von a abh¨angt. 2.7. Assoziierte. Definition 2.63. Sind A ⊂ Nn eine Teilmenge und b ∈ Nn , so schreiben wir A − b := {a ∈ Nn | a + b ∈ A}. F¨ ur A ∈ M(n) definiere Ass(A) := {I ∈ n | ∃b ∈ Nn : A − b = hei | i ∈ Ii}. Lemma 2.64. Sei A ∈ M(n) \ Nn . Dann gilt ∃I ∈

n

: A = hei | i ∈ Ii ⇐⇒ a + b ∈ / A ∀a, b ∈ Nn \ A.

Beweis. ⇒“: Sei I ∈ n mit A = hei | i ∈ Ii. Sind a, b ∈ Nn \ A, so gilt ” ai = bi = 0 f¨ ur alle i ∈ I, also auch (a + b)i = 0 f¨ ur i ∈ I. Daraus folgt a + b ∈ / A.

⇐“: Sei I := {i ∈ {1, . . . , n} | ei ∈ A}. Dann gilt nat¨ urlich hei | iP∈ Ii ⊂ A. ” Sei a ∈ Nn \ hei | i ∈ Ii. Wir zeigen a ∈ / A mit Induktion nach r := ni=1 ai . Ist r = 0, so ist a = 0 ∈ / A wegen A 6= Nn . Sei nun r ≥ 1 und j ∈ supp(a). Es ist dann a0 := a − ej ∈ Nn \ hei | i ∈ Ii. Somit gilt nach Induktionsvoraussetzung a0 ∈ / A. Wegen a ∈ / hei | i ∈ Ii ist j ∈ / I, also ej ∈ / A. Nach Voraussetzung gilt dann a = a0 + ej ∈ / A.  Bemerkung 2.65. Seien R ein Integrit¨atsbereich und A ∈ M(n). A) F¨ ur b ∈ Nn gilt hX A−b iS = (hX A iS :S X b ). B) Ein Termideal a ⊂ S ist genau dann ein Primideal, wenn I ∈ n existiert mit a = hXi | i ∈ IiS . C) Nach Lemma 1.27 gilt darum Ass(S/hX A iS ) = {hXi | i ∈ IiS | I ∈ Ass(A)}. Satz 2.66 (Erster Eindeutigkeitssatz f¨ ur Prim¨arzerlegungen). Sei A ∈ M(n) n und sei Z : → P(n) eine irredundante Zerlegung von A. Dann gilt Ass(A) = {I ∈ n | Z(I) 6= Nn }.

KOMBINATORISCHE KOMMUTATIVE ALGEBRA

21

Beweis. Setze A := {I ∈ n | Z(I) 6= Nn }. Wir machen Induktion nach r := #A. Ist r = 0, dann ist A = Nn . F¨ ur jedes b ∈ Nn gilt dann A − b = Nn . Also ist Ass(A) leer. Sei zun¨achst r = 1. Dann gilt A = {bAc}, und A ist ein echtes prim¨ares Monoidideal. Wir m¨ ussen {bAc} = Ass(A) zeigen. ⊂“: Setze T := {a ∈ Nn | supp(a) ⊂ bAc}. Die Menge T \ A ist endlich und ” nicht leer. W¨ahle b ∈ Max (T \ A). Es gilt dann ei + b ∈ A f¨ ur alle i ∈ bAc. Dies zeigt A − b ⊃ hei | i ∈ bAci. Ist andererseits a ∈ Nn mit supp(a) ∩ bAc = ∅, so gilt a + b ∈ / A. Dies zeigt A − b ⊂ hei | i ∈ bAci. Also ist bAc ∈ Ass(A). ⊃“: Seien J ∈ Ass(A) und b ∈ Nn , so dass A − b = hei | i ∈ Ji. Ist j ∈ bAc, ” so existiert k ∈ N mit kej ∈ A. Insbesondere ist dann kej + b ∈ A und damit kej ∈ A − b = hei | i ∈ Ji. Dies zeigt j ∈ J und damit bAc ⊂ J. Nehmen wir an, diese Inklusion sei echt. W¨ahle j ∈ J \ bAc. Wegen ej + b ∈ A gilt dann b ∈ A. Daraus folgt der Widerspruch A − b = Nn . T Sei nun r > 1. W¨ahle J ∈ A und setze B := I∈ n \{J} Z(I). Definiere die Zerlegung ( Nn , falls I = J, Y : n → P, I 7→ Z(I), sonst


von B. Aus Z ⊂ Y folgt sofort, dass Y irredundant ist. Nach Induktionsvoraussetzung gilt Ass(B) = A \ {J}. Setze B := {I ∈ n | ∃b ∈ B \ A : A − b = hei | i ∈ Ii}. Wir zeigen zuerst B ⊂ Ass(Z(J)). Seien I ∈ B und b ∈ B \ A, so dass A − b = hei | i ∈ Ii ist. Wegen A ⊂ Z(J) ist die Inklusion A − b ⊂ Z(J) − b klar. Ist umgekehrt a ∈ Z(J) − b, dann ist wegen b ∈ B auch a + b ∈ Z(J) ∩ B = A, also a ∈ A − b. Dies zeigt Z(J) − b = A − b = hei | i ∈ Ii und damit I ∈ Ass(Z(J)). Nach dem Fall r = 1 gilt Ass(Z(J)) = {J}. Also ist B entweder leer, oder es gilt B = Ass(Z(J)). Weil Z irredundant ist, gilt A B. Beachte, dass f¨ ur alle b ∈ Nn die Menge A−b ein Monoidideal ist. Die Menge I := {A−b ∈ M(n) | b ∈ B\A} ist somit nicht leer. Nach Satz 2.13 c) existiert ein bez¨ uglich der Inklusion maximales Element C ∈ I. W¨ahle b ∈ B \ A mit C = A − b. Seien c, d ∈ Nn \ C. Dann ist b + d ∈ B \ A. Wegen C = A − b ⊂ A − (b + d) und wegen der Maximalit¨at von C in I muss C = A − (b + d) gelten. W¨are nun c + d ∈ C, so w¨are c ∈ A − (b + d) = C, was nach Wahl von c nicht m¨oglich ist. Also finden wir mit Lemma 2.64 ein I ∈ n mit C = hei | i ∈ Ii. Es gilt dann I ∈ B. Insgesamt haben wir damit B = Ass(Z(J)) gezeigt.

Als n¨achstes wollen wir Ass(A) ⊂ Ass(B)∪Ass(Z(J)) zeigen: Seien I ∈ Ass(A) und b ∈ Nn, so dass A − b = hei | i ∈ Ii ist. Nehmen wir an, es gelte I ∈ / Ass(B). Dann gilt nat¨ urlich A − b 6= B − b. Wegen A − b ⊂ B − b existiert also ein a ∈ Nn , so dass a + b ∈ B \ A ist. Wir zeigen A − b = A − (a + b): Sei c ∈ A − (a + b). Es gilt also a + b + c ∈ A und damit a + c ∈ A − b = hei | i ∈ Ii. Nach Voraussetzung ist a + b ∈ / A, also a ∈ / A − b = hei | i ∈ Ii. Nach Lemma 2.64

22

STEFAN FUMASOLI

ist also c ∈ hei | i ∈ Ii = A − b. Weil die andere Inklusion trivial ist, ist nun A − b = A − (a + b) bewiesen. Es folgt I ∈ B = Ass(Z(J). Insgesamt haben wir bis jetzt Ass(A) ⊂ A gezeigt. F¨ ur den Nachweis der umgekehrten Inklusion gen¨ ugt es, J ∈ Ass(A) zu zeigen. Dies folgt aber sofort aus J ∈ Ass(Z(J)) = B ⊂ Ass(A).  Notation 2.67. F¨ ur eine endliche Teilmenge Z ⊂ I(n) definiere \ YZ : n → P(n), I 7→ {B ∈ Z | bBc = I}.

Lemma 2.68. Sei Z ⊂ I(n) eine irredundante endliche Teilmenge. Dann ist YZ eine irredundante Zerlegung. Beweis. Es ist klar, dass YZ eine Zerlegung ist. Nehmen wirTan, YZ sei nicht irredundant. Dann existiert J ∈ n mit YZ (J) 6= Nn , so dass I∈ n \{J} YZ (I) ⊂ T YZ (J) ist. Folglich existiert B ∈ Z mit bBc = J und {C ∈ Z | bCc 6= J} ⊂ B. Dann ist aber Z nicht irredundant. 


Satz 2.69. Sei A ∈ M(n). Sei Z ⊂ I(n) die irredundante irreduzible Zerlegung von A. Dann ist YZ die maximale Zerlegung von A. Beweis. Sei Y 0 : n → P(n) eine Zerlegung von A. F¨ ur jedes I sei S WI ⊂ I(n) 0 0 die irredundante irreduzible Zerlegung von Y (I). Dann ist Z := I∈ n WI eine irreduzible Zerlegung von A. Weil Z irredundant ist, folgt Z ⊂ Z 0 und damit {B ∈ Z | bBc = I} ⊂ {B ∈ Z 0 | bBc = I} f¨ ur alle I ∈ n . Sei J ∈ n . Nach Lemma 2.68 ist YWJ eine irredundante Zerlegung von Y 0 (J). Nach Satz 2.66 gilt {bBc ∈ n | B ∈ WJ } = {I ∈ n | YWJ (I) 6= Nn } = Ass(Y 0 (J)). Eine zweite Anwendung von Satz 2.66 auf die irredundante Zerlegung ( Y 0 (J), falls I = J, n → P(n), I 7→ 0, sonst,


liefert Ass(Y 0 (J)) ⊂ {J}. Das heisst, es gilt bBc = J f¨ ur alle B ∈ WJ . Es folgt WI = {B ∈ Z 0 | bBc = I} und damit W ⊃ {B ∈ Z | bBc = I} f¨ ur I T T n 0 0 jedes I ∈ . Dies zeigt Y (I) = WI ⊂ {B ∈ Z | bBc = I} = YZ (I) f¨ ur alle I ∈ n und damit die Maximalit¨at von YZ .  Bemerkung 2.70. A) Mit 2.69 haben wir einen weiteren Beweis f¨ ur die Eindeutigkeit der maximalen Zerlegungen. B) Satz 2.69 liefert eine positive Antwort auf die Frage in Problem 2.25 C). Mit Hilfe von Satz 2.51 kann in dem dort angegebenen Algorithmus der Schritt B0:=Irredundiere(B) erheblich beschleunigt werden. Ferner ist wegen Lemma 2.68 klar, dass man sich den letzten Schritt Z:=Irredundiere(Y) schenken kann. C) Die S¨atze 2.60 und 2.69 liefern einen andern Algorithmus zur Bestimmung von maximalen Zerlegungen.

KOMBINATORISCHE KOMMUTATIVE ALGEBRA

23

Problem 2.71. A) Verbessere den Algorithmus von 2.25 C) im Sinne von Bemerkung 2.70 B). B) Implementiere einen Algorithmus zur Bestimmung von maximalen Zerlegungen im Sinne von Bemerkung 2.70 C). C) Welcher der beiden Algorithmen ist effizienter? Problem 2.72. Inwiefern ist 2.60 und 2.69 eine Verallgemeinerung von 2.40 und 2.42 f¨ ur beliebige Monoidideale? 2.8. Maclagans Lemma.

5

Satz 2.73. Sei I ⊂ M(n) eine unendliche Teilmenge. Dann existieren A, B ∈ I mit A B. Insbesondere existiert eine unendliche echt absteigende Kette A 1 ! A2 ! A3 ! . . . von Monoididealen Ai ∈ I. Beweis. 1) Nehmen wir zuerst an, dass jede unendliche Teilmenge von I zwei Elemente A, B ∈ I mit A B enth¨alt. Nach Satz 2.13 c) besitzt jede nicht leere Teilmenge von I ein bez¨ uglich Inklusion maximales Element. Damit sind die Voraussetzungen von Lemma 2.7, angewandt auf die unendliche geordnete Menge (I, ⊃), erf¨ ullt und es existiert eine unendliche echt absteigende Kette A1 ! A2 ! A3 ! . . . von Monoididealen Ai ∈ I. 2) Da die Menge {Ass(A) | A ∈ I} endlich ist, existiert nach dem Schubfachprinzip eine Menge A ∈ {Ass(A) | A ∈ I} und eine unendliche Teilmenge J ⊂ I, so dass Ass(A) = A ist f¨ ur alle A ∈ J. Es gen¨ ugt, die Aussage des Satzes f¨ ur J zu beweisen. Wir tun dies mit Induktion nach r := #A. Es ist klar, dass r ≥ 1 ist.

3) Sei zun¨achst r = 1. Schreibe A = {J}. Nach Satz 2.66 gilt dann A ∈ P(n) f¨ ur alle A ∈ J. Definiere T := {a ∈ Nn | supp(a) ⊂ J}. Ist A ∈ J, dann ist nach Definition der prim¨aren Monoidideale wegen bAc = J die Menge T \ A endlich. Nach 1) gen¨ ugt es zu zeigen, dass jede unendliche Teilmenge von J zwei Elemente A, B mit A B besitzt. Nehmen wir an, dies sei nicht der Fall: Es gelte also A 6⊂ B f¨ ur alle A, B ∈ J0 mit A 6= B f¨ ur eine unendliche Teilmenge J0 ⊂ J. Im folgenden konstruieren wir eine absteigende Kette J0 T ⊃ J1 ⊃ J2 ⊃ T . . . von 0 unendlichen Teilmengen Ji ⊂ J mit der Eigenschaft, dass A∈Ji A A∈Ji+1 A f¨ ur alle i ∈ N gilt. Das steht dann aber im Widerspruch zu Satz 2.13 b). Setze J0 := J0 . Sei i ∈ N. Wir nehmen an, die unendliche Menge Ji sei bereits konstruiert. W¨ahle B ∈ Ji . Ist A ∈ J0 \ {B}, so ist nach Voraussetzung A 6⊂ B, also Min A 6⊂ B. Wegen Min A ⊂ T ist dann A ∩ T \ B nicht leer. Weil T \ B nur endlich viele Teilmengen besitzt, existieren nach dem Schubfachprinzip eine nicht leere Teilmenge M ⊂ T \ B und eine unendliche Teilmenge Ji+1 ⊂ Ji , so dass A ∩ T \ B = M ist f¨ ur alle A ∈ Ji+1 . Wegen M ⊂ A f¨ ur alle A ∈ Ji+1 gilt 5Vgl.

D. Maclagan: Antichains of monomial ideals are finite. Proc. amer. math. soc. 129(6), 1609–1615 (2000).

24

STEFAN FUMASOLI

T

T M ⊂ A∈Ji+1 A. Andererseits ist A∈Ji A ⊂ B ⊂ Nn \ M . Weil M nicht leer ist, T T folgt daraus A∈Ji A A∈Ji+1 A.

4) Sei jetzt r ≥ 2. F¨ ur jedes A ∈ J k¨onnen wir nach Satz 2.20 eine T irredundante J Zerlegung ZA ∈ Z(n) von A w¨ahlen. F¨ ur J ∈ A setzen wir A := I∈ n \{J} ZA (I). F¨ ur J ∈ A und L ⊂ J definieren wir ferner LJ := {AJ | A ∈ L}. Nach Satz 2.66 gilt {Ass(AJ ) | A ∈ J} = A \ {J}. Seien F¨ ur jedes A ∈ J gilt dann T J0 , J1 ∈ ATzwei verschiedene Elemente. T A = I∈ n ZA (I) = I∈ n \{J0 } ZA (I) ∩ I∈ n \{J1 } ZA (I) = AJ0 ∩ AJ1 . Es folgt J ⊂ {A ∩ B | A ∈ JJ0 , B ∈ JJ1 }. Es k¨onnen also JJ0 und JJ1 nicht beide endlich sein. W¨ahlen wir also J ∈ A, so dass JJ unendlich ist. Nach Induktionsvoraussetzung finden wir eine unendliche, bez¨ uglich der Inklusion total geordnete Teilmenge J0 ⊂ JJ . Setze K := {A ∈ J | AJ ∈ J0 }. Es gen¨ ugt, die Aussage des Satzes f¨ ur K zu beweisen. Setze KJ := {ZA (J) ∈ P(n) | A ∈ K}.











Fall 1: Die Menge KJ ist endlich. Nach dem Schubfachprinzip existieren B ∈ KJ und eine unendliche Teilmenge L ⊂ K, so dass ZA (J) = B ist f¨ ur alle A ∈ L. Ist A ∈ L, so gilt A = AJ ∩ B mit AJ ∈ J0 . Folglich ist L bez¨ uglich der Inklusion total geordnet, und wir sind in diesem Fall fertig.

Fall 2: Die Menge KJ ist unendlich. Nach Satz 2.66 gilt Ass(A) = {J} f¨ ur alle A ∈ KJ . Nach dem Fall r = 1 finden wir eine unendliche, bez¨ uglich der Inklusion total geordnete Teilmenge K0 ⊂ KJ . Setze L := {A ∈ K | ZA (J) ∈ K0 }. Da L unendlich ist, gen¨ ugt es, die Aussage des Satzes f¨ ur L zu beweisen. Nach 1) gen¨ ugt es zu zeigen, dass jede unendliche Teilmenge von L zwei Elemente A, B mit A B besitzt. Nehmen wir an, dies sei nicht der Fall: Es gelte also A 6⊂ B f¨ ur alle A, B ∈ L0 mit A 6= B f¨ ur eine unendliche Teilmenge L0 ⊂ L. Setze M0 := {ZA (J) | A ∈ L0 }. Die Menge M0 ⊂ K0 ist bez¨ uglich der Inklusion total geordnet. Es gilt (L0 )J ⊂ (L)J ⊂ KJ ⊂ J0 , also ist auch M1 := (L0 )J bez¨ uglich der Inklusion total geordnet. Wegen L0 ⊂ {A ∩ B | A ∈ M0 , B ∈ M1 } ist mindestens eine der beiden Mengen M0 , M1 unendlich. Sei j ∈ {0, 1}, so dass Mj unendlich ist. Weil Mj bez¨ uglich der Inklusion total geordnet ist, existiert nach Satz 2.13 b) eine echt absteigende Kette A0 ! A1 ! A2 ! . . . von Monoididealen Ai ∈ Mj . F¨ ur jedes i ∈ N w¨ahle Bi ∈ M1−j , so dass Ai ∩ Bi ∈ L0 ist. Wegen Ai ∩ Bi 6⊃ Ai+1 ∩ Bi+1 f¨ ur alle i ∈ N nach Voraussetzung 0 an L folgt Bi 6⊃ Bi+1 f¨ ur alle i ∈ N. Weil auch M1−j bez¨ uglich der Inklusion total geordnet ist, folgt daraus B0 B1 B2 . . . , was im Widerspruch zu Satz 2.13 b) steht. 

KOMBINATORISCHE KOMMUTATIVE ALGEBRA

25

3. Ordnungen auf Nn 3.1. Termordnungen. Definition 3.1. Seien (M, ∗) ein Monoid und ≤ eine Ordnung auf M . Diese Ordnung heisst Monoidordnung, wenn sie total ist und wenn sie mit der Monoidstruktur vertr¨aglich ist, dass heisst, wenn f¨ ur alle a, b, c ∈ M gilt a ≤ b ⇒ a ∗ c ≤ b ∗ c, und sie heisst Termordnung, wenn das neutrale Element e f¨ ur ∗ das einzige minimale Element ist, das heisst, wenn e ≤ a ist f¨ ur alle a ∈ M . Die Menge der Termordnungen von Nn bezeichnen wir mit TOn . Sind ≤1 , ≤2 zwei Ordnungen auf M , so sagen wir ≤1 verfeinert ≤2 , wenn f¨ ur alle a, b ∈ M mit a ≤2 b auch a ≤1 b gilt. Beispiel 3.2. F¨ ur die in 2.2 definierte Ordnung auf Nn ist mit der Monoidstruktur vertr¨aglich, und es gilt Min Nn = {0}. Sie ist somit genau dann eine Termordnung, wenn n ∈ {0, 1}. Wir nennen diese Ordnung kanonische Ordnung von Nn und bezeichnen sie weiterhin mit ≤. Lemma 3.3. Sei ≤τ eine Monoidordnung auf Nn . a) Genau dann ist ≤τ eine Termordnung, wenn sie die kanonische Ordnung verfeinert. b) F¨ ur alle a, b, c ∈ Nn gilt a + c ≤τ b + c ⇒ a ≤τ b. c) Seien a, b ∈ Nn und c ∈ N \ {0}. Dann gilt a ≤τ b ⇐⇒ ca ≤τ cb. d) Ist ≤τ eine Termordnung, so ist ≤τ eine Wohlordnung. Beweis. a) ⇒“: Sei ≤τ eine Termordnung, und seien a, b ∈ Nn mit a ≤ b. Sei ” c := b − a. Es gilt 0 ≤τ c. Daraus folgt a = 0 + a ≤τ c + a = b. ⇐“: Es verfeinere ≤τ die kanonische Ordnung. Ist c ∈ Nn , dann ist 0 ≤ c und ” damit 0 ≤τ c. b) Seien a, b, c ∈ Nn mit a + c ≤τ b + c. W¨are a >τ b, so w¨are a + c >τ b + c.

c) Indukton nach c: Aus a ≤τ b folgt dann (c − 1)a ≤τ (c − 1)b und damit ca = a + (c − 1)a ≤τ b + (c − 1)a ≤τ b + (c − 1)b = cb. Aus a >τ b folgt ebenso ca >τ cb. d) Sei ≤τ eine Termordnung. Sei A ⊂ Nn eine nicht leere Teilmenge. Dann ist Min≤ A endlich nach Dicksons Lemma. Setze b := min≤τ (Min≤ A). Wir zeigen nun b ≤τ a f¨ ur alle a ∈ A: Sei a ∈ A. W¨ahle c ∈ Min≤ A mit c ≤ a. Nach Teil a) folgt dann b ≤τ c ≤τ a.  Definition 3.4. Seien M ein Monoid mit einer Monoidordnung ≤σ und N ⊂ M ein Untermonoid mit einer Monoidordnung ≤τ . Wir sagen dann, ≤σ sei eine Erweiterterung von ≤τ und ≤τ sei eine Einschr¨ankung von ≤σ , falls f¨ ur alle a, b ∈ N gilt: a ≤σ b ⇐⇒ a ≤τ b.

26

STEFAN FUMASOLI

Lemma 3.5. Sei ≤τ eine Monoidordnung auf Nn . Dann gibt es auf Qn und auf Zn je genau eine Monoidordnung, die ≤τ erweitert.

Beweis. Definiere ≤σ folgendermassen: Seien a, b ∈ Qn . Setze c := b − a. W¨ahle r ∈ N \ {0} und d ∈ Nn , so dass d + rc ∈ Nn gilt. Es gelte a <σ b, falls d <τ d + rc gilt. Seien r 0 ∈ N \ {0} und d0 ∈ Nn , so dass d0 + r 0 c ∈ Nn ist. Dann gilt nach Lemma 3.3 b) und c) d <τ d + rc ⇐⇒ r 0 d <τ r 0 d + r 0 rc ⇐⇒ rd0 + r 0 d <τ rd0 + r 0 d + r 0 rc ⇐⇒ rd0 <τ rd0 + r 0 rc ⇐⇒ d0 <τ d0 + r 0 c.

Das heisst, a <σ b gilt unabh¨angig von der Wahl von r und d. Man zeigt nun leicht, dass ≤σ eine Monoidordnung auf Qn ist, die ≤τ erweitert. Durch Einschr¨ankung auf Zn erhalten wir sofort eine Erweiterung von ≤τ auf Zn . Ebenso leicht zeigt man die Eindeutigkeit der erweiternden Monoidordnungen.   ai 6= 0 Definition 3.6. F¨ ur a ∈ Rn \ {0} ν(a) := min i ∈ {1, . . . , n} definiere und µ(a) := max i ∈ {1, . . . , n} ai 6= 0 . Definiere auf Rn die lexikographischen Ordnungen ≤lex und ≤xel folgendermassen: Seien a, b ∈ Rn zwei verschiedene Elemente. Es gelte a bµ(a−b) gilt. Es gelte a bν(a−b) gilt. Die durch diese Ordnungen auf Nn induzierten Ordnungen erhalten die gleichen Bezeichnungen. Beispiel 3.7. In R[x, y, z, t] gilt x2 z >lex xy 2 z 3 t4 >lex y 5 zt3 >lex y 3 z 5 t7 , x2 z <xel y 5 zt3 <xel xy 2 z 3 t4 <xel y 3 z 5 t7 . x2 z >revlex y 5 zt3 >revlex xy 2 z 3 t4 >revlex y 3 z 5 t7 . x2 z |b| ⇒ a >τ b.

Definiere die homogene lexikographische Ordnung ≤deglex folgendermassen: Seien a, b ∈ Nn . Es gelte a <deglex b genau dann, wenn |a| < |b| oder wenn |a| = |b| und a
KOMBINATORISCHE KOMMUTATIVE ALGEBRA

27

Definition 3.9. Sei V = [Vij | i, j ∈ {1, . . . , n}] ∈ Rn×n eine invertierbare Pn Matrix. F¨ ur a ∈ Nn definieren wir wie u ¨blich V a ∈ Rn durch (V a)i = j=1 Vij aj f¨ ur i ∈ {1, . . . , n}. Wir definieren die Ordnung ≤V folgendermassen: Seien a, b ∈ Nn . Es gelte a ≤V b genau dann, wenn V a ≤lex V b gilt. Beispiel 3.10. Es gilt ≤lex =≤"

1 0 ··· 0

0 1 ··· 0

··· ··· ··· ···

0# 0 ··· 1

und ≤degrevlex =≤2

1 6 0 4 0 ··· 0

1 0 0 ··· −1

··· ··· ··· ··· ···

1 0 −1 ··· 0

3 1 −1 7 0 5 ··· 0

.

¨ Ubungsaufgabe 3.11. A) Zeige, dass die Ordnungen ≤lex , ≤deglex , ≤degrevlex Termordnungen sind und dass die Ordnung ≤revlex zwar eine Monoidordnung, aber f¨ ur n ≥ 1 keine Termordnung ist. B) Warum gibt es keine Termordnung ≤τ mit x2 z >τ y 3 z 5 t7 >τ xy 2 z 3 t4 >τ y 5 zt3 ? C) Zeige, dass f¨ ur invertierbares V ∈ Rn×n die Relation ≤V eine Modulordnung ist. D) Zeige: F¨ ur invertierbares V ∈ Rn×n ist ≤V genau dann eine Termordnung, wenn in allen Spalten von V der erste von 0 verschiedene Eintrag positiv ist. E) Finde eine Matrix V ∈ Zn×n , so dass ≤deglex =≤V gilt. Notation 3.12. Es bezeichne Mat+ n die Menge der invertierbaren reellen n × nMatrizen, deren Spalten die Eigenschaft haben, dass jeweils der erste von 0 verschiedene Eintrag positiv ist. Lemma 3.13. a) Seien V , W ∈ Mat+ 2 mit V11 W12 6= V12 W11 . Dann gilt ≤V 6=≤W . Insbesondere ist TO2 ¨ uberabz¨ahlbar. b) Die Menge der homogenen Termordnungen auf N3 ist ¨ uberabz¨ahlbar. Beweis. a) Nach Voraussetzung gilt 0 ≤ V11 , V12 , W11 , W12 . Ohne Einschr¨ankung nehmen wir V11 W12 < V12 W11 an. Dann gilt 0 < V12 , W11 . W12 W11 12 . Dann ist α VV11 − αW > 1. Fall: V11 6= 0. W¨ahle α ∈ N mit α > V12 WV1111−V 11 W12 11 W12 V12 W¨ahle β ∈ N mit α W11 < β < α V11 . Setze a := (0, α), b := (β, 0). Es gilt dann V a = (αV12 , αV22 ) >lex (βV11 , βV21 ) = V b und W a = (αW12 , αW22 ) 0, und f¨ ur alle α ∈ N \ {0} und β ∈ N gilt 12 (0, α) >V (β, 0). Ist β > W , so gilt andererseits (0, 1) <W (β, 0). W11 b) Analog zeigt man, dass ≤» 1 1 1 – f¨ ur r ∈ R≥0 homogen ist und durch r 1 r 0 eindeutig bestimmt wird.  0 1 0 Lemma 3.14. Seien ≤σ , ≤τ ∈ TOn , so dass f¨ ur alle a, b ∈ Nn mit supp(a) ∩ supp(b) = ∅ genau dann a ≤σ b gilt, wenn a ≤τ b gilt. Dann gilt ≤σ =≤τ .

28

STEFAN FUMASOLI

Beweis. Seien a, b ∈ Nn mit a ≤σ b. Wir zeigen a ≤τ b mit Induktion nach |a|. Falls supp(a) ∩ supp(b) leer ist, ist nach Voraussetzung nichts zu zeigen. Sei also i ∈ supp(a) ∩ supp(b). Die Induktionsvoraussetzung liefert dann a ≤σ b ⇒ a − ei ≤σ b − ei ⇒ a − ei ≤τ b − ei ⇒ a ≤τ b.

 Satz 3.15 (Klassifizierung von TO2 ). Es besteht eine Bijektion   ≤ , falls (r, i) = (0, 1),   [ 01 10 ] (R≥0 × {0}) ∪ (Q≥0 × {1}) → TO2 , (r, i) 7→ ≤[ 1 r ] , falls i = 0, 0 1   ≤ 1 r , sonst. [ ] 1 0

Beweis. Man sieht sofort, dass die Abbildung wohldefiniert ist. Injektivit¨at: Wegen Lemma 3.13 m¨ ussen wir nur noch zeigen, dass ≤[ 1 r ] 6=≤[ 1 r ] 0 1 1 0 ist f¨ ur alle r ∈ Q>0 . Seien α, β ∈ N \ {0} und r := αβ . Dann gilt (α, 0) <[ 1 r ] (0, β) 0 1 und (α, 0) >[ 1 r ] (0, β). 1 0

Surjektivit¨at: Sei ≤τ ∈ TO2 . Setze

r := inf { αβ ∈ Q | α, β ∈ N \ {0} : (α, 0) >τ (0, β)} ∈ R ∪ {∞}.

Fall 1: r = ∞. Dann gilt (α, 0) <τ (0, β) f¨ ur alle α, β ∈ N \ {0}. Mit Hilfe von Lemma 3.14 folgern wir ≤τ =≤xel =≤[ 0 1 ] . 1 0

Fall 2: Das Infimum r ∈ R wird nicht angenommen. Wir zeigen, dass in diesem Fall ≤τ =≤[ 1 r ] gilt: Seien α, β ∈ N \ {0}. Man rechnet leicht nach, dass 0 1 (α, 0) >[ 1 r ] (0, β) genau dann gilt, wenn r < αβ ist. Nach Lemma 3.14 gen¨ ugt es 0 1 also zu zeigen, dass (α, 0) >τ (0, β) ⇐⇒ r < αβ

gilt. ⇒“: Diese Richtung folgt sofort aus der Definition von r und der Vorausset” zung, dass r als Infimum nicht angenommen wird. ⇐“: Sei r < αβ . Weil r als Infimum nicht angenommen wird, finden wir α0 , ” 0 β 0 ∈ N \ {0} mit r < αβ 0 < αβ und (α0 , 0) >τ (0, β 0 ). Mit Lemma 3.3 c) und a) folgt (αα0 , 0) >τ (0, αβ 0 ) >τ (0, βα0 ). Nochmalige Anwendung von Lemma 3.3 c) liefert (α, 0) >τ (0, β). Fall 3: Das Infimum r wird angenommen. Insbesondere ist dann 0 < r ∈ Q. Wir zeigen, dass in diesem Fall ≤τ =≤[ 1 r ] gilt: Seien α, β ∈ N \ {0}. Man rechnet 1 0 leicht nach, dass (α, 0) <[ 1 r ] (0, β) genau dann gilt, wenn r > αβ ist. Nach Lemma 1 0 3.14 gen¨ ugt es also zu zeigen, dass (α, 0) <τ (0, β) ⇐⇒ r >

α β

KOMBINATORISCHE KOMMUTATIVE ALGEBRA

29

gilt. ⇐“: Diese Richtung folgt sofort aus der Definition von r. ” ⇒“: Es gelte r ≤ αβ . Weil r als Infimum angenommen wird, finden wir α0 , ” 0 0 β 0 ∈ N \ {0} mit r = αβ 0 und (α0 , 0) >τ (0, β 0 ). Es gilt also αβ 0 ≤ αβ . Genau gleich wie in Fall 2 rechnet man nach, dass (α, 0) >τ (0, β) ist.  Definition 3.16. Sei k ∈ {0, . . . , n}. P P n F¨ ur a ∈ Nk , b ∈ Nn−k schreiben wir aa b := ki=1 ai ei + n−k ur i=1 bi ei+k ∈ N f¨ die Konkatenation von a und b. Seien ≤1 ∈ TOk , ≤2 ∈ TOn−k . Wir definieren die Blockordnung oder Eliminan n k tionsordnung ≤a 1 ≤2 auf N folgendermassen: Seien a, b ∈ N . Seien a1 , b1 ∈ N a a a und a2 , b2 ∈ Nn−k so, dass a = a1 a2 und b = b1 b2 gilt. Es gelte a ≤1 ≤2 b genau dann, wenn a1 <1 b1 oder (a1 = b1 und a2 ≤2 b2 ). ¨ Ubungsaufgabe 3.17. A) Zeige, dass f¨ ur k ∈ {0, . . . , n} und zwei Termordnungen ≤1 ∈ TOk und ≤2 ∈ TOn−k die Blockordnung ≤a 1 ≤2 eine Termordnung ist. B) Seien j, k ∈ N mit j ≤ k ≤ n. Seien ≤1 ∈ TOj , ≤2 ∈ TOk−j , ≤3 ∈ TOn−k . a a a Zeige, dass die Gleichheit (≤a 1 ≤2 ) ≤3 =≤1 (≤2 ≤3 ) gilt. C) Zeige, dass ≤lex = ≤a . . . a ≤ gilt, wo ≤ die kanonische Ordnung von N ist. | {z } n

Problem 3.18. Klassifiziere alle Termordnungen von Nn . (Hinweise finden sich in M. Kreuzer, L. Robbiano: Computational commutative algebra 1, SpringerVerlag, Berlin, 2000, Tutorial 10). 3.2. Initialideale. Festsetzung 3.19. Im folgenden bezeichne K immer einen K¨orper und S := K[X1 , . . . , Xn ] den Polynomring u ¨ber K in n Unbestimmten. Standardm¨assig versehen wir S mit der Standard-Z-Graduierung. Verm¨oge des kanonischen Isomorphismus von Monoiden Nn ∼ = T, a 7→ X a identifizieren wir die Ordnungen von T = T(K, n) mit denjenigen von Nn . Definition 3.20. Sei ≤τ ∈ TOn . F¨ ur f ∈ S \ {0} ist der Leitterm von f bez¨ uglich ≤τ definiert als der bez¨ uglich ≤τ gr¨osste Term in f : Ltτ (f ) := max≤τ supp(f ).

F¨ ur ein Ideal a ⊂ S ist das Initialideal von a bez¨ uglich ≤τ definiert als inτ a := hLtτ f | f ∈ a \ {0}iS .

F¨ ur einen K-Untervektorraum V ⊂ S ist der Initialvektorraum von V bez¨ uglich ≤τ definiert als inτ V := hLtτ f | f ∈ V \ {0}iK .

30

STEFAN FUMASOLI

Bemerkung 3.21. Sei ≤τ ∈ TOn . A) Seien f , g ∈ S \ {0}. Dann gilt Ltτ (f g) = (Ltτ f )(Ltτ g). B) Sei V ⊂ S ein Ideal. Dann ist der Initialvektorraum von V bez¨ uglich ≤τ ein Idealvon S. Insbesondere ist dann inτ V als Initialideal identisch mit inτ V als Initialvektorraum. C) Sei a ⊂ S ein Ideal. Dann ist inτ a ein Monomialideal. L Definition 3.22. F¨ ur einen graduierten S-Modul M = i∈Z Mi mit dimK Mi < ∞ f¨ ur alle i ∈ Z definieren wir die Hilbertfunktion von M durch hM : Z → N, i 7→ dimK Mk .
Beispiel 3.23. A) Es gilt hS (i) = n−1+i f¨ ur alle i ∈ N. i

B) Wir wollen die Hilbertfunktion eines graduierten Hauptideals berechnen: Sei das Ideal a ⊂ S erzeugt von einem homogenen Polynom f ∈ S vom Grad d ∈ N. Sei i ∈ Z. Als K-Vektorraum ist dann der i-te homogene Teil von a erzeugt
von der Menge {uf | u ∈ Si−d ∩ T}. Es folgt ha (i) = hS (i − d) = n−1+i−d . i−d

Satz 3.24. Seien ∆ ⊂ n ein simplizialer Komplex und a∆ das zugeh¨orige Stanley-Reisner-Ideal. F¨ ur i ∈ Z bezeichne fi die Anzahl i-dimensionaler Simplizes von ∆. Dann gilt X i − 1  hS/a∆ (i) = fj j j∈Z f¨ ur alle i ∈ N.

∈ A∆ ist quadratfrei}. Beweis. Nach Satz 2.40 gilt ∆ = n \ {supp(a) ∈ n | a P n Sei a ∈ N . Weil A∆ quadratfrei ist, gilt a ∈ A∆ ⇐⇒ i∈supp(a) ei ∈ A∆ . Es folgt darum X a ∈ / a∆ ⇐⇒ supp(a) ∈ ∆. Sei nun i ∈ N. Nach dem vorhergehenden Beispiel gilt dann hS/a∆ (i) = #{a ∈ Nn | supp(a) ∈ ∆ ∧ |a| = i} X = #{a ∈ Nn | supp(a) = I ∧ |a| = i} I∈∆

X #I − 1 + i − #I  = hh i∈I Xi iK[Xi |i∈I] (i) = i − #I I∈∆ I∈∆   n n X X i − 1 X i−1 = #{I ∈ ∆ | dim(I) = j − 1} = i − j j−1 j=0 j=0 I∈∆: X

Q

#I=j

=

X j∈Z

fj−1



i−1 j−1



=

X j∈Z

fj



 i−1 . j 

KOMBINATORISCHE KOMMUTATIVE ALGEBRA

31

Beispiel 3.25. Wir betrachten wieder das Stanley-Reisner-Ideal a∆ = hxz, yzti im Polynomring K[x, y, z, t] des simplizialen Komplexes ∆ = von Beispiel 2.32. Die Hilbertfunktion von S/a∆ ist gegeben durch         i−1 i−1 i−1 i−1 hS/a∆ (i) = +4 +5 + . −1 0 1 2
Der Binomialkoeffizient i−1 ist genau dann 1, wenn i = 0 ist, sonst ist er 0. Es −1 2 gilt also hS/a∆ (i) = i +7i f¨ ur i ≥ 1 und hS/a∆ (0) = 1. 2 Notation 3.26. Seien g, h : Z → N zwei Abbildungen. Wir schreiben g ≤ h, falls g(i) ≤ h(i) ist f¨ ur alle i ∈ Z. Ferner schreiben wir g < h, falls g ≤ h und g 6= h gilt. Die Summe von g und h ist definiert durch g + h : Z → N, i 7→ g(i) + h(i). Bemerkung 3.27. Seien a, b ⊂ S zwei graduierte Ideale von S mit derselben Hilbertfunktion. Dann gilt: a ⊂ b ⇒ a = b. Lemma 3.28. Sei ≤τ ∈ TO. a) Sei V ⊂ S ein K-Untervektorraum. Dann gilt dimK inτ V = dimK V. b) Sei a ⊂ S ein graduiertes Ideal. Dann gilt hinτ a = ha . Beweis. a) Ist dimK V endlich, w¨ahle eine Basis (f1 , . . . , fr ) von V mit Ltτ fi 6= Ltτ fj f¨ ur alle i, j ∈ {1, . . . , r} mit i 6= j. Dann ist (Ltτ f1 , . . . , Ltτ fr ) eine Basis von inτ V . Ist V unendlichdimensional, so folgt daraus auch sofort Unendlichdimensionalit¨at von inτ V . b) F¨ ur alle i ∈ Z gilt (inτ a)i = inτ (ai ). Mit a) folgt dimK (inτ a)i = dimK inτ (ai ) = dimK ai .  Lemma 3.29. Sei a ⊂ S ein graduiertes Ideal. Dann ist {inτ a | ≤τ ∈ TO} endlich. Beweis. Setze M := {inτ a | ≤τ ∈ TO}. W¨are M unendlich, so g¨abe es nach dem Lemma von Maclagan zwei Elemente b, c ∈ M mit b c. Nach Lemma 3.28 gilt hb = ha = hc . Nun folgt der Widerspruch b = c aus Bemerkung 3.27.  Definition 3.30. Sei S 0 := S[Xn+1 ] = K[X1 , . . . , Xn+1 ]. Wir definierenP wie folgt die Homogenisierung homog : S → S 0 : Sei f ∈ S \ {0}. Schreibe f = u∈T γu u mit geeigneten γu ∈ K f¨ ur u ∈ T. Setze X deg(f )−deg(u) homog(f ) := γu uXn+1 . u∈T

Ferner setze homog(0) := 0. Ist a ⊂ S ein Ideal, so definiere ahomog := hhomog(f ) | f ∈ aiK[Xn+1 ] .

Andererseits definieren wir die Dehomogenisierung

dehomog : S 0 → S, f 7→ f (X1 , . . . , Xn , 1)

32

STEFAN FUMASOLI

und f¨ ur ein Ideal a ⊂ S 0

adehomog := {dehomog(f ) | f ∈ a}.

¨ Ubungsaufgabe 3.31. Sei S 0 := S[Xn+1 ]. A) F¨ ur f , g ∈ S gilt homog(f g) = homog(f )homog(g). B) Ist a ⊂ S ein Ideal, dann ist ahomog ein Ideal von S 0 . C) Ist a ⊂ S 0 ein Ideal, dann ist adehomog ein Ideal von S. D) Ist a ⊂ S ein Ideal, dann gilt (ahomog )dehomog = a. P di E) Seien d1 , . . . , dr ∈ N und f1 , . . . , fr ∈ S, so dass f := ri=1 Xn+1 homog(fi ) P r d homogen ist. Dann gibt es ein d ∈ N, so dass f = Xn+1 homog( i=1 fi ) ist. F) Ist a ⊂ S ein Ideal, dann gilt ahomog = hf ∈ S 0 | f ist homogen und dehomog(f ) ∈ aiS 0 .

Lemma 3.32. Seien a ⊂ S ein Ideal und ≤τ ∈ TOn . Sei ≤σ :=≤a τ ≤∈ TOn+1 . Dann gilt inτ a = (inσ (ahomog ))dehomog . Beweis. ⊂“: F¨ ur f ∈ S \ {0} gilt Ltτ (f ) = dehomog(Ltσ (homog(f ))). ” ⊃“: Sei f ∈ ahomog \ {0} homogen. Nach 3.31 E) existieren d ∈ N und ” d g ∈ a, so dass f = Xn+1 homog(g) ist. Nun rechnet man leicht nach, dass dehomog(Ltσ (f )) = Ltτ (g) ist.  Korollar 3.33. Sei a ⊂ S ein Ideal. Dann ist {inτ a | ≤τ ∈ TO} endlich. Beweis. Nach Lemma 3.32 gilt #{inτ a | ≤τ ∈ TOn } ≤ #{inτ (ahomog ) | ≤τ ∈ TOn+1 }.

Nach Lemma 3.29 ist {inτ (ahomog ) | ≤τ ∈ TOn+1 } endlich.



Beispiel 3.34. Sei f := x2 z + y 5 zt3 + xy 2 z 3 t4 + y 3 z 5 t7 ∈ K[x, y, z, t]. Setze a := hf i. Dann gilt {inτ a | ≤τ ∈ TO} = {hx2 zi, hy 5 zt3 i, hxy 2 z 3 t4 i, hy 3z 5 t7 i}. ⊂“: Sei ≤τ ∈ TO. Sei u ∈ inτ a ∩ T. Dann existiert ein g ∈ K[x, y, z, t], so dass ” u = Ltτ (gf ) = (Ltτ g)(Ltτ f ) ist. Insbesondere ist inτ a von Ltτ f erzeugt.

⊃“: Es ist nicht so einfach zu sehen, dass hxy 2 z 3 t4 i ein Initialideal von a ist. ” Wir wollen eine Termordnung ≤τ mit Ltτ f = xy 2 z 3 t4 finden. Es muss dann insbesondere xy 2 z 3 t4 >τ x2 z und xy 2 z 3 t4 >τ y 3 z 5 t7 gelten. Aus der ersten Ungleichung folgt y 2 z 2 t4 >τ x und aus der zweiten folgt x >τ yz 2 t3 , zusammen also y 2 z 2 t4 >τ x >τ yz 2 t3 . Dass hier kein Widerspruch mit der Transitivit¨at auftaucht, ist schon ein gutes Zeichen. Andererseits sehen wir auch, dass wir nicht mit einer simplen“ Ordnung rechnen k¨onnen. ” Am besten suchen wir eine Matrix V ∈ N4×4 mit yz 2 t3
KOMBINATORISCHE KOMMUTATIVE ALGEBRA

33

Gehen wir einmal davon aus, dass schon gelten soll V12 + 2V13 + 3V14 < V11 < 2V12 + 2V13 + 4V14 . W¨ahlen wir V12 = V13 = V14 = 1, dann ist V11 = 7. Setzen wir nun V := dann ist V in R4×4 invertierbar. Schliesslich rechnen wir nach, dass



7 0 0 0

1 1 0 0

1 0 1 0

1 0 0 1



,

xy 2 z 3 t4 >V y 3 z 5 t7 >V x2 z >V y 5 zt3 gilt. Problem 3.35. Finde einen Algorithmus, der alle Initialideale eines gegebenen Ideals berechnet. Definition 3.36. Seien a ⊂ S ein Ideal und ≤τ ∈ TO. Eine endliche Teilmenge G ⊂ a \ {0} heisst Gr¨obnerbasis von a bez¨ uglich ≤τ , wenn inτ a = hLtτ (f ) | f ∈ GiS gilt. Eine Gr¨obnerbasis G von a bez¨ uglich ≤τ heisst reduziert, wenn folgendes gilt: ∀g, h ∈ G, ∀u ∈ supp(h) : g 6= h ⇒ Ltτ (g) - u.

Eine endliche Teilmenge G ⊂ a heisst universelle Gr¨obnerbasis von a, wenn G eine Gr¨obnerbasis von a bez¨ uglich jeder Termordnung ist. Beispiel 3.37. A) Sei f ∈ S \ {0}. Dann ist {f } eine universelle Gr¨obnerbasis von hf iS , wie wir im Beispiel 3.34 gesehen haben. B) Sei A ⊂ Nn eine endliche Teilmenge. Dann ist X A eine universelle Gr¨obnerbasis von hX A iS . Ist ≤τ ∈ TOn , dann ist X Min A eine minimale Gr¨obnerbasis von hX A iS . Lemma 3.38 (Existenz von Gr¨obnerbasen). Seien a ⊂ S ein Ideal und ≤τ ∈ TO. Dann existiert eine reduzierte Gr¨obnerbasis von a bez¨ uglich ≤τ . Zum Beweis der Existenz von Gr¨obnerbasen verwende, dass aufsteigende Ketten von Termidealen station¨ar werden. Hat man eine Gr¨obnerbasis, gewinnt man daraus leicht eine reduzierte Gr¨obnerbasis. Lemma 3.39. Seien a ⊂ S ein Ideal und ≤σ , ≤τ ∈ TOn zwei Termordnungen mit inσ a = inτ a. Sei G ⊂ a eine reduzierte Gr¨obnerbasis von a bez¨ uglich ≤σ . Dann gilt Ltτ (g) = Ltσ (g) f¨ ur alle g ∈ G. Insbesondere ist dann ist G auch eine reduzierte Gr¨obnerbasis von a bez¨ uglich ≤τ . Beweis. Sei g ∈ G. Dann gilt Ltτ (g) ∈ inτ a = inσ a. Weil G bez¨ uglich ≤σ eine Gr¨obnerbasis von a ist, existiert f ∈ G, so dass Ltσ (f ) | Ltτ (g). Weil G reduziert ist, folgt f = g. Aus Ltσ (g) | Ltτ (g) folgt Ltσ (g) ≤σ Ltτ (g) (siehe Lemma 3.3 a)) und daraus wiederum Ltσ (g) = Ltτ (g).  Korollar 3.40 (Existenz von universellen Gr¨obnerbasen). Sei a ⊂ S ein Ideal. Dann besitzt a eine universelle Gr¨obnerbasis. Beweis. Folgt aus Korollar 3.33, Lemma 3.38 und Lemma 3.39.



34

STEFAN FUMASOLI

Lemma 3.41. Seien a ⊂ S ein Ideal und ≤τ ∈ TO. Ist G ⊂ a eine Gr¨obnerbasis von a bez¨ uglich ≤τ , dann wird a durch G erzeugt. Zum Beweis verwende, dass Termordnungen Wohlordnungen sind. Bemerkung 3.42. Mit Hilfe des Buchberger-Algorithmus, der auch in CoCoA implementiert ist, kann man Gr¨obnerbasen berechnen.6

6Siehe

1992.

z.B. D. Cox, J. Little, D. O’Schea: Ideals, Varieties, and Algorithms, Springer-Verlag,