Gröbnerbasen in Monoid- und Gruppenringen

Karsten Hiddemann

5. November 2003

Zusammenfassung Gröbnerbasen, entwickelt von Bruno Buchberger für kommutative Polynomringe, finden immer häufiger Anwendung bei der Lösung algorithmischer Probleme. Dieser Seminarvortrag baut auf dem Vortrag “Termersetzung in Monoidringen” auf und betrachtet Gröbnerbasen in Monoid- und Gruppenringen, welche durch Wortersetzungssysteme präsentiert werden. Neben Algorithmen zur Berechnung von Gröbnerbasen soll auf ausgewählte Anwendungen, wie z.B. das Enthaltenseinsproblem für Ideale, eingegangen werden.

1 Grundlagen

Im folgenden sei der Monoid M stets endlich präsentiert durch das total geordnete, noethersche, konfluente Termersetzungssystem (Σ, T) und 𝕂[M] sei der zugehörige kommutative Polynomring über M mit Koeffizienten aus 𝕂. Seien nun p ∈ 𝕂[M], F ⊆ 𝕂[M] gegeben. Wir wollen entscheiden können, ob p ∈ ideal_{r}(F), d.h. ob p ≡_{ideal_{r}(F)} 0 ist. Alleinige Reduktionen am Leitterm (wie bei der Polynomdivision in 𝕂[x]) reichen hier nicht aus, denn durch die Termersetzungen könnte der Grad von p dabei steigen. Es wurde daher das Prinzip der starken Reduktion p →_{f}^{s} q von rechts an einem Monom α · t eingeführt, welche durchführbar ist, falls es ein w ∈ M gibt mit LT(f ∗ w) = t so, daß gilt q = p − α · LC(f ∗ w)^{−1} · f ∗ w. Diese ist tatsächlich noethersch, und für die auf Mengen erweiterte starke Reduktion von rechts gilt p ↔^{∗}_{F}^{s} q genau dann, wenn p−q ∈ ideal_{r}(F), d.h. es gilt ↔^{∗}_{F}^{s} = ≡_{ideal_{r}(F)}.

Definition 1.1. Eine Teilmenge G ⊆ 𝕂[M] heißt starke Gröbnerbasis, wenn gilt, daß ⟷^{∗}_{G}^{s} = ≡_{ideal_{r}(G)} und ⟶_{G}^{s} konfluent ist.

2 Rechts-Reduktion und Gröbnerbasen

Um nun eine Menge als Gröbnerbasis nachzuweisen genügt es, auf lokale Konfluenz zu untersuchen, da die Reduktion noethersch ist. Doch selbst dieses ist algorithmisch nicht gut zu lösen, denn wir haben zu viel Freiheit bei der Wahl der f und w und im Allgemeinen müssen dazu unendlich viele solcher Paare betrachtet werden. Man schränkt nun die Menge der Reduktionen ein, indem gefordert wird, daß die Multiplikation mit w den Leitterm von f an seiner Leitposition beläßt.

Definition 2.1. Seien p, f zwei Polynome ungleich Null aus 𝕂[M]. Wir sagen f reduziert p von rechts zu q an einem Monom α · t in einem Schritt, p ⟶_{f}^{r} q, falls ein w ∈ M existiert, so daß

(a) LT(f ∗ w) = LT(f) ∘ w = t und

(b) q = p − α · LC(f ∗ w)^{−1} · f ∗ w.

Genau wie vorher definieren wir nun:

Definition 2.2. Eine Teilmenge G ⊆ 𝕂[M] heißt Rechts-Gröbnerbasis, wenn gilt, daß ⟷^{∗}_{G}^{r} = ≡_{ideal_{r}(G)} und ⟶_{G}^{r} konfluent ist.

Lemma 2.3. p ⟷^{∗}_{F}^{r} q impliziert p − q ∈ ideal_{r}(F) bzw. äquivalent p ≡_{ideal_{r}(F)} q.

Beweis. Der Fall p = q ist klar. Sei nun p ⟷^{k}_{F}^{r} p_{k} ⟷_{F}^{r} q, Induktion über k: Es ist q = p_{k} − α · f ∗ w und damit dann auch p − q = p − p_{k} + α · f ∗ w ∈ ideal_{r}(F).

Wie im letzten Vortrag gezeigt gilt die Umkehrung im Allgemeinen aber nicht, Reduktion von rechts beschreibt nicht mehr die Idealkongruenz. Durch Saturierung der reduzierenden Menge wird dieses aber wieder sichergestellt.

Definition 2.4. F ⊆ 𝕂[M] heißt saturiert, wenn gilt f ∗w ⟶_{F}^{r} 0 in einem Schritt für alle f ∈ F, w ∈ M, f ∗ w ≠ 0.

Lemma 2.5. Sei F saturiert. Dann hat jedes Polynom 0 ≠ g ∈ ideal_{r}(F) eine Darstellung der Form g = ∑_{i=1}^{k} α_{i}f_{i} ∗ w_{i} mit LT(f_{i} ∗ w_{i}) = LT(f_{i}) ∘ w_{i}.

Beweis. Sei g = ∑_{j=1}^{k} α_{j}f_{j} ∗ w_{j} und i so, daß LT(f_{i} ∗ w_{i}) ≠ LT(f_{i}) ∘ w_{i}. Dann gilt f_{i} ∗ w_{i} ⟶_{F}^{r} 0, d.h. f_{i} ∗ w_{i} = β_{i} · f′_{i} ∗ w′_{i} mit LT(f′_{i} ∗ w′_{i}) = LT(f′_{i}) ∘ w′_{i}. Ersetze also f_{i} ∗w_{i} durch β_{i} ·f′_{i} ∗w′_{i}, durch Iteration erhält man die gewünschte Darstellung.

Wie kann nun festgestellt werden, ob eine Menge eine Gröbnerbasis ist? Zur Klärung dieser Frage brauchen wir zur Vorbereitung erst noch das

Lemma 2.6 (Translation Lemma). Sei F ⊆ 𝕂[M] und p, q, h ∈ 𝕂[M].

(a) Sei p − q ⟶_{F}^{r} h, dann existieren p′, q′ ∈ 𝕂[M] so, daß p ⟶^{∗}_{F}^{r} p′, q ⟶^{∗}_{F}^{r} q′ und h = p′ − q′.

(b) Sei 0 eine Normalform von p − q bzgl. ⟶_{F}^{r}. Dann existiert g ∈ 𝕂[M] so,

daß p ⟶^{∗}_{F}^{r} g und q ⟶^{∗}_{F}^{r} g.

Beweis.

(a) Sei also p − q ⟶_{F}^{r} h = p − q − α · f ∗ w mit LT(f ∗ w) = LT(f) ∘ w = t. Angenommen, t ist sowohl Term von p als auch von q, wobei α_{1}t das Monom in p sei und α_{2}t das in q. Dann sind beide reduzierbar in t und es ist α_{1} −α_{2} = α. Sei nun t nur Term in einem der beiden Polynome, O.B.d.A. in p. Dann ist q′ = q und p ⟶_{F}^{r} p−α·f∗w. Insgesamt ergibt sich dann p′−q′ = p−q−α·f∗w = h.

(b) Der Fall p − q = 0 ist klar. Sei nun p − q ⟶_{F}^{r} h ⟶^{k}_{F}^{r} 0, wir verwenden wieder Induktion über k. Nach (a) ist h = p′ − q′ und auf diese läßt sich die Induktionsvoraussetzung anwenden.

Satz 2.7. Sei F eine saturierte Menge in 𝕂[M]. Dann sind äquivalent:

(a) F ist eine Rechts-Gröbnerbasis

(b) g ⟶^{∗}_{F}^{r} 0 ∀g ∈ ideal_{r}(F).

Beweis.

“⇒” Es gilt g ∈ ideal_{r}(F) ⇔ g ⟷^{∗}_{F}^{r} 0. Da ⟶_{F}^{r} konfluent ist und 0 irreduzibel, folgt aber induktiv g ⟶^{∗}_{F}^{r} 0.

“⇐” Zunächst ist zu zeigen, daß ⟷^{∗}_{F}^{r} = ≡_{ideal_{r}(F)}. “⊆” ist klar nach 2.3. Zu “⊇”: Sei also p ≡ q ⇔ p = q + ∑_{i=1}^{k} α_{i} · f_{i} ∗ w_{i}. Da die Summe in ideal_{r}(F) liegt, kann man diese nach 2.5 durch Reduktionsschritte beschreiben, d.h. p ⟷^{∗}_{F}^{r} q. Nun ist noch zu zeigen, daß ⟶_{F}^{r} konfluent ist, da noethersch, reicht es aus, lokale Konfluenz nachzuweisen. Sei also g ⟶_{F}^{r} g_{1}, g ⟶_{F}^{r} g_{2} und g_{1} ≠ g_{2}. Dann ist g_{1} − g_{2} ∈ ideal_{r}(F) und, da nach Voraussetzung g_{1} − g_{2} ⟶^{∗}_{F}^{r} 0, liefert das Translation Lemma 2.6 die Behauptung.

Es ist noch nicht ganz klar, welche Reduktionen wir beim Test auf die lokale Konfluenz nun im einzelnen betrachten müssen. Schwierig zu entscheiden sind diejenigen, die den gleichen Term reduzieren, diese bilden für uns kritische Paare. Wir definieren wie bei Buchberger’s Ansatz:

Definition 2.8. Seien p_{1}, p_{2} ∈ 𝕂[M]. Jedes Paar w_{1}, w_{2} ∈ M mit LT(p_{1} ∗ w_{1}) = LT(p_{1}) ∘ w_{1} = LT(p_{2}) ∘ w_{2} = LT(p_{2} ∗ w_{2}) definiert ein Rechts-s-Polynom durch

spol_{r}(p_{1}, p_{2}, w_{1}, w_{2}) = LC(p_{1} ∗ w_{1})^{−1} · p_{1} ∗ w_{1} − LC(p_{2} ∗ w_{2})^{−1} · p_{2} ∗ w_{2}

Wir bezeichnen die Menge aller solcher Paare mit U_{p_{1},p_{2}} ⊆ M × M

Satz 2.9. Sei F eine saturierte Menge in 𝕂[M]. Dann sind äquivalent:

(a) g ⟶^{∗}_{F}^{r} 0 ∀g ∈ ideal_{r}(F)

(b) spol_{r}(f_{k}, f_{l}, w_{k}, w_{l}) ⟶^{∗}_{F}^{r} 0 ∀f_{k}, f_{l} ∈ F, (w_{k}, w_{l}) ∈ U_{f_{k},f_{l}}

Beweis.

“⇒” klar, da spol_{r}(f_{k}, f_{l}, w_{k}, w_{l}) ∈ ideal_{r}(F)

“⇐” Falls h ∈ ideal_{r}(F) und h ⟶_{f}^{r} h′, so ist auch h′ ∈ ideal_{r}(F). Da die Reduktion noethersch ist, reicht es zu zeigen: Jedes 0 ≠ g ∈ ideal_{r}(F) ist reduzibel. Sei also g nach 2.5 von der Form g = ∑_{i=1}^{k} α_{i}·f_{i}∗w_{i} mit LT(f_{i}∗w_{i}) = LT(f_{i})∘w_{i}. Sei bezüglich dieser Repräsentierung t = max{LT(f_{j} ∗w_{j}) | j = 1, …, m} und K die Anzahl der f_{j} ∗ w_{j}, die t als Term enthalten. Dann ist t ≥ LT(g) und falls LT(g) = t, so ist g reduzibel an t. Sei nun t > LT(g). Das heißt es gibt also zwei Polynome f_{k}, f_{l} aus obiger Repräsentierung so, daß t = LT(f_{k} ∗ w_{k}) = LT(f_{k}) ∘ w_{k} = LT(f_{l}) ∘ w_{l} = LT(f_{l} ∗ w_{l}), also bilden diese ein s-Polynom. Wir ändern nun unsere Präsentierung entsprechend diesem s-Polynom ab: O.B.d.A. spol_{r}(f_{k}, f_{l}, w_{k}, w_{l}) ≠ 0. Da spol_{r}(f_{k}, f_{l}, w_{k}, w_{l}) ⟶^{∗}_{F}^{r} 0 ist spol_{r}(f_{k}, f_{l}, w_{k}, w_{l}) = ∑_{i=1}^{n} δ_{i} · h_{i} ∗ v_{i}, δ_{i} ∈ 𝕂^{∗}, h_{i} ∈ F, v_{i} ∈ M mit LT(spol_{r}(f_{k}, f_{l}, w_{k}, w_{l})) < t, da t herausgekürzt wird. Damit erhalten wir:

α_{k} · f_{k} ∗ w_{k} + α_{l} · f_{l} ∗ w_{l}
= α_{k} · f_{k} ∗ w_{k} + α′_{l} · β_{k} · f_{k} ∗ w_{k} − α′_{l} · β_{k} · f_{k} ∗ w_{k} + α′_{l} · β_{l} · f_{l} ∗ w_{l}
= (α_{k} + α′_{l} · β_{k}) · f_{k} ∗ w_{k} − α′_{l} · \underbrace{(β_{k} · f_{k} ∗ w_{k} − β_{l} · f_{l} ∗ w_{l})}_{spol_{r}(f_{k},f_{l},w_{k},w_{l})}

= (α_{k} + α′_{l} · β_{k}) · f_{k} ∗ w_{k} − α′_{l} · (∑_{i=1}^{n} δ_{i} · h_{i} ∗ v_{i})

mit β_{k} und β_{l} passend gewählt und entweder verschwindet der Term t hierbei (falls α_{k} +α′_{l} ·β_{k} = 0) oder K sinkt, da t im zweiten Teil ersetzt wurde. Dieser Prozeß läßt sich iterieren und er ist endlich, da die Reduktion die Termordnung verkleinert und man sich daher irgendwann im Fall LT(g) = t befindet.

3 Präfix-Reduktion

Obwohl man nun Gröbnerbasen durch s-Polynome charakterisieren kann, ist ein endlicher Test meist nicht möglich. Daher schwächen wir die Reduktion weiter ab.

Definition 3.1. Seien p, f zwei Polynome ungleich Null aus 𝕂[M]. Wir sagen f präfix-reduziert p von rechts zu q an einem Monom α·t in einem Schritt, p ⟶_{f}^{p} q, falls ein w ∈ M existiert, so daß

(a) LT(f)w ≡ t, d.h. LT(f) ist Präfix von t, und

(b) q = p − α · LC(f)^{−1} · f ∗ w.

Definition 3.2. F ⊆ 𝕂[M] heißt präfix-saturiert, wenn gilt f ∗ w ⟶_{F}^{p} 0 in einem Schritt für alle f ∈ F, w ∈ M, f ∗ w ≠ 0.

Definition 3.3. Eine Teilmenge G ⊆ 𝕂[M] heißt Präfix-Gröbnerbasis, wenn gilt, daß ⟷^{∗}_{G}^{p} = ≡_{ideal_{r}(G)} und ⟶_{G}^{p} konfluent ist.

Definition 3.4. Seien p_{1}, p_{2} ∈ 𝕂[M] und w ∈ M so, daß LT(p_{1}) ≡ LT(p_{2})w, dann ist das Präfix-s-Polynom definiert durch

spol_{p}(p_{1}, p_{2}) = LC(p_{1})^{−1} · p_{1} − LC(p_{2})^{−1} · p_{2} ∗ w

Auch in diesem Fall haben wir wieder:

Satz 3.5. Sei F eine präfix-saturierte Menge in 𝕂[M]. Dann sind äquivalent:

(a) g ⟶^{∗}_{F}^{p} 0 ∀g ∈ ideal_{r}(F)

(b) spol_{p}(f_{1}, f_{2}) ⟶^{∗}_{F}^{p} 0 ∀f_{k}, f_{l} ∈ F.

Der Algorithmus zur Berechnung einer Gröbnerbasis sieht nun wie folgt aus:

PROZEDUR PRÄFIX GRÖBNER BASIS

Gegeben: Endliche Polynommenge F ⊆ 𝕂[M]

Gesucht: GB(F), eine Präfix-Gröbnerbasis von F

Benutzt: SAT_{p}, eine Präfix-saturierende Prozedur für Polynome.

Initialisierung:

G := ∪_{f∈F} SAT_{p}(f) sei die präfix-saturierte Menge zu F.
Bilde die kritischen Paare B := {(q_{1}, q_{2}) | q_{1}, q_{2} ∈ G, q_{1} ≠ q_{2} }.

Programmablauf:

⋆ Solange B nicht leer ist, nehme ein Paar (q_{1}, q_{2}) aus B heraus.

Falls spol_{p}(q_{1}, q_{2}) existiert:

– Sei h die Normalform von spol_{p}(q_{1}, q_{2}) bzgl. Präfix-Reduktion mit G

– Falls h ≠ 0, dann füge SAT_{p}(h) zu G hinzu und die neuen kritischen Paare zu B, d.h. B := B ∪ {(f, h̃), (h̃, f) | f ∈ G, h̃ ∈ SAT_{p}(h)}.

– Weiter bei ⋆.

Ausgabe: GB(F) := G;

Es gibt zwei Stellen, an denen es möglich ist, daß diese Prozedur nicht terminiert: SAT_{p}(g) könnte nicht terminieren und es kann sein, daß B nie leer wird.

Literatur

[1] B. Reinert, Tutorial on Gröbner Bases in Monoid and Groups Rings, Federated Logic Conference ’99 Workshop on Gröbner Bases and Rewriting Techniques, 1999.

[2] Krister Forsman, The Hitch Hiker’s Guide to Gröbner Bases: commutative algebra for amateurs, Contemp. Math., Amer. Math. Soc. 298 (2002), 21–42.

[3] B. Reinert, Gröbnerbasen, manuscript for a lecture given in the winter term 1996/97 (1996).

[4] B. Reinert, On Gröbner Bases in Monoid and Group Rings, Phdthesis, Fachbereich Informatik, Universität Kaiserslautern, 1995.