Universität Regensburg, Fakultät für Mathmeatik WS 2001 / 2002 Seminar ”Aktuelle Themen der Computeralgebra“

Faugéres Algorithmus F_{4}

(von Jens Schmidbauer)

1 Grundlagen

Seien K ein Körper, n ∈ ℕ_{+} und P := K[x_{1}, …, x_{n}] der Polynomring über K. Dessen Terme 𝕋^{n} seien versehen mit einer Termordnung σ.

Definition Sei L = {l_{1}, …, l_{m}} ⊆ 𝕋^{n} mit l_{1} >_{σ} … >_{σ} l_{m}. Dann erhält man einen K-Vektorraum-Isomorphismus

ψ_{L} : ⟨L⟩_{K} ⟶ K^{m}, l_{i} ⟼ e_{i} (i = 1, …, m)

Daraus ergibt sich dann für s ∈ ℕ_{+} ein weiterer K-Vektorraum-Isomorphismus

Ψ_{L,s} : ⟨L⟩_{K}^{s} ⟶ Mat_{s,m}(K), (f_{1}, …, f_{s}) ⟼ [ ψ_{L}(f_{1}) ; ⋮ ; ψ_{L}(f_{s}) ]

Beispiel 1.1 Wählt man n = 3, σ = Lex oder σ = DegLex und die Menge aller Monome vom Grad 2, also L = {x_{1}^{2}, x_{1}x_{2}, x_{1}x_{3}, x_{2}^{2}, x_{2}x_{3}, x_{3}^{2}}, so kann man mit dieser Abbildung jedes Tupel homogener Polynome vom Grad 2 als Matrix darstellen. So wird z. B. F = (2x_{1}^{2} + 3x_{1}x_{2} + x_{2}^{2}, x_{1}^{2} + 2x_{1}x_{3} + 5x_{3}^{2}, x_{1}x_{3} + 3x_{2}x_{3}) repräsentiert durch die Matrix

Ψ_{L,3}(F) = [ \begin{matrix}2 & 3 & 0 & 1 & 0 & 0 \\ 1 & 0 & 2 & 0 & 0 & 5 \\ 0 & 0 & 1 & 0 & 3 & 0 \end{matrix} ]

Definition

a) Ist A ∈ Mat_{s,m}(K) eine (s × m)-Matrix, so bezeichne Ã die eindeutige Zeilenstufenform von A, d.h. Ã ist von der Form

Ã = [ \begin{matrix}0 & … & 0 1 & ∗ & … & ∗ & 0 & ∗ & … & ∗ & 0 & 0 & ∗ & … & ∗ \\ 0 & … & 0 & 0 & 0 & … & 0 1 & ∗ & … & ∗ & 0 & 0 & ∗ & … & ∗ \\ 0 & … & 0 & 0 & 0 & … & 0 & 0 & 0 & … & 0 1 & 0 & ∗ & … & ∗ \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ⋮ & ... & ⋮ & ⋮ \\ 0 & … & 0 & 0 & 0 & … & 0 & 0 & 0 & … & 0 & 0 & 1 & ∗ & … & ∗ \end{matrix} ]

Das bedeutet, Ã ist eine (s̃ × m)-Matrix mit s̃ = Rang(A) ≤ min(m, s).

b) Wir definieren für eine beliebige Menge F ⊆ P:

LT_{σ}(F) := {LT_{σ}(f) | f ∈ F } ⊆ 𝕋^{n}
Supp(F) := ⋃_{f∈F} Supp(f) ⊆ P

c) Seien F ⊆ P eine endliche, nichtleere Menge, s := Card(F) und F ∈ P^{s} ein Tupel, das die Elemente von F als Einträge enthält. Dann bezeichnen

s̃:= Rang(Ψ_{Supp(F),s}(F))
F̃ := Ψ_{Supp(F),s̃}^{−1}(Ψ_{Supp(F),s}(F)^{∼}) ⊆ P s̃

F̃ := ⋃_{i=1}^{s̃}{pr_{i}(F)} ⊆ P
F̃^{+} := {f ∈ F̃ | LT_{σ}(f) ∉ LT_{σ}(F)} ⊆ P

Dabei heißen F̃ das zu F interreduzierte Tupel und F̃ die Interreduktion von F.

Beispiel 1.2 In Beispiel 1.1 war L = Supp(F), und die eindeutige Zeilenstufenform der Matrix Ψ_{L,3}(F) lautet

Ψ_{L,3}(F)^{∼} = [ \begin{matrix}1 & 0 & 0 & 0 & −6 & 5 \\ 0 & 1 & 0 & \frac{1}{3} & 4 & −\frac{10}{3} \\ 0 & 0 & 1 & 0 & 3 & 0 \end{matrix} ]

Also gilt F̃ = \{x_{1}^{2} − 6x_{2}x_{3} + 5x_{3}^{2}, x_{1}x_{2} + \frac{1}{3}x_{2}^{2} + 4x_{2}x_{3} − \frac{10}{3}x_{3}^{2}, x_{1}x_{3} + 3x_{2}x_{3}\} und damit F̃^{+} = \{x_{1}x_{2} + \frac{1}{3}x_{2}^{2} + 4x_{2}x_{3} − \frac{10}{3}x_{3}^{2}\}.

Bemerkung Seien in der Situation von Punkt c) der Definition L := Supp(F) und m := Card(L). Seien y_{1}, …, y_{m} neue Variablen, Y := {y_{1}, …, y_{m}} und die Terme von Q := K[y_{1}, …, y_{m}] bzgl. Lex geordnet. Betrachtet man H := Ψ_{Y,s}^{−1}(Ψ_{L,s}(F)) ⊆ Q^{s} sowie H̃ := Ψ_{Y,s̃}^{−1}(Ψ_{L,s}(F)^{∼}) ⊆ Qs̃ und die zugehörigen Mengen H, H̃ ⊆ Q, so ist H̃ eine reduzierte Lex-Gröbnerbasis des von H erzeugten Ideals. [vgl. Buch, Tut. 22]

Satz 1.1 Sei F ⊆ P eine endliche Menge, und sei F′ ⊆ F mit LT_{σ}(F′) = LT_{σ}(F) und Card(F′) = Card(LT_{σ}(F)). Dann bildet B := F̃^{+}∪F′ eine Basis des K-Vektor-raums ⟨F ⟩_{K}. Beweis: Seien L := Supp(F), m := Card(L), s := Card(F) und F ⊆ P^{s} ein Tupel mit den Elementen von F als Einträgen. Betrachtet man nun den Polynomring Q := K[y_{1}, …, y_{m}] mit Termordnung Lex sowie die Menge Y := {y_{1}, …, y_{m}} ⊆ Q, so ist ⟨F ⟩_{K} isomorph zu dem von den Einträgen von Ψ_{Y,s}^{−1}(Ψ_{L,s}(F)) erzeugten K-Vektorraum V ⊆ Q, und alle Aussagen über Leitterme und Basen gelten entsprechend in V. Deswegen werden ab jetzt nur noch die Identifizierungen von F, F̃, F̃^{+}, F′ und B in V betrachtet. Aufgrund der Definitionen von F̃^{+} und F′ sind die Leitterme in B alle paarweise verschieden. Somit sind die Elemente von B linear unabhängig. Da nach der Bemerkung F̃ eine reduzierte Lex-Gröbnerbasis des von F erzeugten Ideals ist, folgt dim_{K}(V) = Card(F̃) = Card(LT_{Lex}(F̃)). Für die Leitterme gilt aber LT_{Lex}(F̃) = LT_{Lex}(F̃^{+}) ∪ LT_{Lex}(F) = LT_{Lex}(F̃^{+}) ∪ LT_{Lex}(F′) = LT_{Lex}(B). Es folgt dim_{K}(V) = Card(LT_{Lex}(B)) = Card(B). □

Satz 1.2 (Reduktion für F_{4}) Die folgenden Instruktionen beschreiben die Funktion Red(L, G), die zwei endliche Mengen L, G ⊆ P \ {0} erwartet: 1 Setze F := L 2 Setze D := LT_{σ}(F) 3 Wiederhole die Schritte 4 bis 6, solange D ≠ Supp(F) gilt: 4 Wähle ein m ∈ Supp(F) \ D 5 Füge m zu D hinzu 6 Gibt es ein g ∈ G, so dass LT_{σ}(g) ein Teiler von m ist,

so füge \frac{m}{LT_{σ}(g)}g zu F hinzu 7 Berechne F̃ und gib (F, F̃, F̃^{+}) es als Ergebnis zurück Dies ist ein Algorithmus. Beweis: Wird ein neues Polynom zu F hinzugefügt, so hat dieses den Leitterm LT_{σ}(\frac{m}{LT_{σ}(g)}g) = m. Da m zu D hinzugefügt wird, sind im nächsten Wiederholungsschritt alle neuen Elemente in Supp(F) \ D echt kleiner als m. Es gilt also zu jedem Zeitpunkt max_{σ}(Supp(F) \ D) <_{σ} max_{σ}(Supp(L)). Da D in jedem Wiederholungsschritt vergrößert wird, muss nach endlich vielen Wiederhoungen D = Supp(F) gelten. Die Berechnung von F̃ aus F erfolgt nach der Gauß-Jordan-Elimination und benötigt somit auch nur endlich viele Schritte. □

Lemma 1.3 Seien G ⊆ P \ {0} endlich, I das von G sowie J das von LT_{σ}(G) erzeugte Ideal und M ⊆ 𝕋^{n} ×G endlich. Seien außerdem L := {tg | (t, g) ∈ M} ⊆ P und (F, F̃, F̃^{+}) := Red(L, G).

a) Für alle m ∈ LT_{σ}(F̃^{+}) gilt m ∉ J.

b) Es gilt F̃^{+} ⊆ I.

c) Für alle f ∈ ⟨L⟩_{K} gilt f ⟶^{G∪F̃^{+}} 0.

Beweis:

a) Angenommen es gäbe ein m ∈ LT_{σ}(F̃^{+}) mit m ∈ J. Dann gäbe es auch ein g ∈ G, dessen Leitterm m teilt. Da m ∈ LT_{σ}(F̃^{+}) ⊆ Supp(F̃^{+}) ⊆ Supp(F̃) = Supp(F) gilt, fügt der Algorithmus \frac{m}{LT_{σ}(g)}g zu F hinzu. Dessen Leitterm ist m, im Widerspruch zur Definition von F̃^{+}.

b) Da L ⊆ I gilt und jedes zu F hinzugefügte Element stets ein Vielfaches eines Erzeugers g ∈ G ist, gilt am Ende F ⊆ I. Aus Satz 1.1 folgt nun F̃^{+} ⊆ ⟨F ⟩_{K} ⊆ I.

c) Da ⟨L⟩_{K} ein Untervektorraum von ⟨F ⟩_{K} ist, läßt sich jedes f ∈ ⟨L⟩_{K} nach Satz 1.1 als Linearkombination f = λ′_{1}f′_{1} + ⋯ + λ′_{k}f′_{k} + λ̃_{1}f̃_{1} + ⋯ + λ̃_{l}f̃_{l} darstellen mit f′_{i} ∈ F, f̃_{j} ∈ F̃^{+} und λ′_{i}, λ̃′_{j} ∈ K \ {0} für i = 1, …, k und j = 1, …, l. Die f′_{i} sind immer von der Form mg mit m ∈ 𝕋^{n} und g ∈ G. Es gilt also

λ′_{1}f′_{1} + ⋯ + λ′_{k}f′_{k} ⟶^{G} 0 und λ̃_{1}f̃_{1} + ⋯ + λ̃_{l}f̃_{l} ⟶^{F̃^{+}} 0 und somit f ⟶^{G∪F̃^{+}} 0. □

2 Der Algorithmus F_{4}

Im Folgenden seien stets K ein Körper, n, s ∈ ℕ_{+} und P := K[x_{1}, …, x_{n}] der Polynomring über K. Außerdem sei eine Termordnung σ auf 𝕋^{n} gegeben. Für g_{1}, …, g_{s} ∈ P \ {0} und i, j ∈ {1, …, s} definieren wir folgende Bezeichnungen:

t_{i} := LT_{σ}(g_{i})  c_{i} := LC_{σ}(g_{i})
t_{ij} := \frac{kgV(t_{i}, t_{j})}{t_{i}}  S_{ij} := \frac{1}{c_{i}} t_{ij}g_{i} − \frac{1}{c_{j}} t_{ji}g_{j}

Theorem 2.1 (Algorithmus F_{4}) Seien G = {g_{1}, …, g_{s}} ⊆ P eine endliche Menge und I := (g_{1}, …, g_{s}) ⊆ P das von G erzeugte Ideal. Weiter sei Sel(M) eine (beliebige) Auswahlfunktion, die eine nichtleere Teilmenge der übergebenen Menge M zurückliefert. Die folgenden Instruktionen definieren die Funktion F_{4}(G):

1 Setze H := G, s′ := s und B := {(i, j) | 1 ≤ i < j ≤ s} 2 Wiederhole die Schritte 3 bis 11, solange B ≠ ∅ ist: 3 Setze C := Sel(B) 4 Ersetze B durch B \ C 5 Setze L := {t_{ij}g_{i} | (i, j) ∈ C} ∪ {t_{ji}g_{j} | (i, j) ∈ C} 6 Berechne (F, F̃, F̃^{+}) := Red(L, H) 7 Wiederhole Schritte 8 bis 11 für jedes f ∈ F̃^{+}: 8 Erhöhe s′ um 1 9 Definiere g_{s′} := f 10 Hänge g_{s′} an H an 11 Hänge die Elemente von {(i, s′) | 1 ≤ i < s′} an B an 12 Gib G zurück Der Algorithmus F_{4} berechnet eine σ-Gröbnerbasis H von I. Beweis: Wäre die Endlichkeit nicht gegeben, so müsste dies in der äußeren Wiederholungsschleife der Fall sein, und in unendlich vielen Wiederholungsschritten müsste F̃^{+} ≠ ∅ gelten. So entstünde eine Folge (F̃_{i}^{+})_{i∈ℕ} nichtleerer Mengen und eine entsprechende Folge (H_{i})_{i∈ℕ} aufsteigender Mengen H. Nun könnte man für jedes i ∈ ℕ_{+} ein f_{i} ∈ F̃_{i}^{+} wählen und mit I_{0} := (0) und I_{i} := I_{i−1} + (LT_{σ}(f_{i})) für i ∈ ℕ_{+} eine aufsteigende Idealkette konstruieren. Es gälte stets I_{i−1} ⊆ (LT_{σ}(H_{i−1})), aber f_{i} ∉ (LT_{σ}(H_{i−1})) wegen Lemma 1.3. a) und damit I_{i−1} ⊊ I_{i}. Die Idealkette wäre somit nicht stationär, im Widerspruch zur Noether-Eigenschaft des Polynomrings P. Da anfänglich H = G gilt und zu H in jedem Schritt nur Elemente von F̃^{+} hinzugefügt werden, gilt wegen Lemma 1.3. b) stets G ⊆ H ⊆ I. Jedes Paar (i, j) mit 1 ≤ i < j ≤ s′ ist genau einmal in C enthalten. Im entsprechenden Wiederholungsschritt muss also t_{ij}g_{i}, t_{ji}g_{j} ∈ L und damit S_{ij} ∈ ⟨L⟩_{K} gelten, womit nach Lemma 1.3. c) nach diesem Wiederholungsdurchlauf S_{ij} ⟶^{H} 0 gilt. Damit ist H eine Gröbnerbasis. □ [vgl. Buch, Prop. 2.5.2 und D_{3})]

Bemerkung

a) Es gibt zwei Hauptunterschiede zum Buchberger-Algorithmus:

α) Statt eines Paares (i, j) ∈ B wird eine Teilmenge C ⊆ B ausgewählt und reduziert. Würde die Funktion Sel stets eine einelementige Menge liefern, so entspräche Sel der Auswahlstrategie im Buchberger-Algorithmus. β) Der normale Rest wird in F_{4} durch die Reduktionsfunktion Red ersetzt. Diese entspricht den Bedingungen, gemäß denen der normale Rest im Buchberger-Algorithmus ersetzt werden darf. [vgl. Buch, Bem. 2.5.6]

b) Die Auswahlfunktion Sel kann man beispielsweise so wählen, dass alle Paare zurückgeliefert werden. Aber man kann auch andere Strategien wählen; denkbar wäre z. B. die Auswahl aller Paare von minimalem Grad.

3 Optimierung von F_{4}

Seien K ein Körper, n ∈ ℕ_{+}, P := K[x_{1}, …, x_{n}] und σ eine Termordnung auf 𝕋^{n}.

Genau wie beim Buchberger-Algorithmus kann man auch bei F_{4} die Menge der abzuarbeitenden Paare optimieren. So kann man beispielsweise die Optimierungen nach Gebauer-Möller oder ähnliche Regeln verwenden. Unabhängig von der gewählten Optimierung soll die entsprechende Funktion im Folgenden mit Update(H, B) bezeichnet werden, wobei H ⊆ P eine endlichen Menge und B die Liste der kritischen Paare ist. Eine weitere Optimierung für F_{4} wird nachfolgend beschrieben:

Satz 3.1 Die folgenden Anweisungen beschreiben die Funktion Simplify(t, f, F, F̃) für t ∈ 𝕋^{n}, f ∈ P und F = (F_{k})_{k=1,...,d} sowie F̃ = (F̃_{k})_{k=1,...,d} mit d ∈ ℕ und F_{k} ⊆ P endlich für k = 1, …, d:

1 Setze M := {m ∈ 𝕋^{n} | m teilt t} \ {1} 2 Schreibe M = {m_{1}, …, m_{s}} mit t = m_{1} >_{σ} … >_{σ} m_{s}. 3 Wiederhole die Schritte 4 bis 8 für j = 1, …, s: 4 Setze m := m_{j} 5 Wiederhole die Schritte 6 bis 8 für k = 1, …, d: 6 Gilt mf ∈ F_{k}, so führe die Schritte 7 und 8 durch: 7 Suche p ∈ F̃_{k} mit LT_{σ}(p) = LT_{σ}(mf) 8 Ist m = t, so gib (1, p) zurück,

andernfalls gib Simplify(\frac{t}{m}, p, F, F̃) zurück

9 Gib (t, \frac{1}{LC_{σ}(f)}f) zurück

Der Algorithmus Simplify(t, f, F, F̃) berechnet (t′, f′) ∈ 𝕋^{n} × P. Es gilt: a) LT_{σ}(t′f′) = LT_{σ}(tf).

b) Ist I ⊆ P das von ⋃_{k=1}^{d} F_{k} erzeugte Ideal, so gibt es ein r ∈ I mit LT_{σ}(r) <_{σ}

LT_{σ}(tf), so dass tf = LC_{σ}(f) t′f′ + r gilt.

c) Das Paar (t′, f′) wird so gewählt, dass t′ minimal ist mit den Eigenschaften a) und b).

Beweis: Die Menge M ist endlich und effektiv berechenbar, so dass nur endlich viele Wiederholungen auftreten können. Kommen Rekursionen vor, so gilt \frac{t}{m} <_{σ} t, so dass t in jedem Rekursionsschritt verkleinert wird, womit nur endlich viele Rekursionsschritte auftreten können. Somit wird nach endlich vielen Schritten ein Paar (t′, f′) zurückgegeben.

a) Die Gleichheit der Leitterme ist nur fraglich, falls ein rekursiver Aufruf stattfindet. In diesem Fall gilt LT_{σ}(\frac{t}{m} p) = \frac{t}{m}LT_{σ}(mf) = LT_{σ}(tf), so dass auch im nächsten (und in jedem noch folgenden) Rekursionsschritt LT_{σ}(tf) gleich bleibt.

b) Es genügt, die Behauptung für t′ = \frac{t}{m} und f′ = p zu zeigen. Da im entsprechenden Schritt mf ∈ F_{k} gelten muss, kann man eine Menge F′_{k} ⊆ F_{k} bilden mit mf ∈ F′_{k}, LT_{σ}(F′_{k}) = LT_{σ}(F_{k}) und Card(F′_{k}) = Card(LT_{σ}(F_{k})). Nach Satz 1.1 bildet B := F′_{k} ∪ F̃_{k}^{+} eine Basis von ⟨F ⟩_{K} ⊆ I. Schreiben wir B = {b_{1}, …, b_{l}} mit b_{1} = mf, so gibt es wegen f′ = p ∈ F̃_{k} eine Darstellung f′ = ∑_{i=1}^{l} λ_{i}b_{i} mit λ_{i} ∈ K für i = 1, …, l. Mit r′ := ∑_{i=2}^{l} λ_{i}b_{i} muss LT(r′) <_{σ} LT(f′) gelten, und es folgt f′ = λ_{1}mf + r′. Wegen LC_{σ}(f′) = 1 gilt λ_{1} = \frac{1}{LC_{σ}(f)}, und mit m = \frac{t}{t′} folgt tf = LC_{σ}(f) t′f′ − LC_{σ}(f) t′r′. Also liefert r := −LC_{σ}(f) t′r′ die Behauptung. c) Die Minimalität von t′ ist klar, da die Teiler m ∈ M in absteigender Reihen-

folge abgearbeitet werden und jeweils \frac{t}{m} betrachtet wird. □

Definition Seien G ⊆ P \ {0} endlich, f ∈ P und t ∈ 𝕋^{n}. Eine Darstellung

f = ∑_{i=1}^{k} a_{i}m_{i}g_{i} mit a_{i} ∈ K \ {0}, m_{i} ∈ 𝕋^{n}, g_{i} ∈ G und LT_{σ}(m_{i}g_{i}) ≤_{σ} t

für i = 1, …, k heißt t-Repräsentation von f bzgl. G.

Lemma 3.2 Seien F = (F_{k})_{k=1,...,d} und F̃ = (F̃_{k})_{k=1,...,d} mit d ∈ ℕ und endlichen Mengen F_{k} ⊆ P für k = 1, …, d mit

F_{k} ⊆ Simplify(𝕋^{n}, ⋃_{i=1}^{k−1} F̃_{i}^{+}, (F_{i})_{i=1,...,k−1}, (F̃_{i})_{i=1,...,k−1}) (∗)

Seien G ⊆ P \ {0} endlich mit F_{k}^{+} ⊆ G für k = 1, …, d, g ∈ G, t ∈ 𝕋^{n} und (t′, g′) := Simplify(t, g, F, F̃). Dann hat g′ eine LT_{σ}(g′)-Repräsentation bzgl. G. Beweis: Der Beweis erfolgt durch Induktion nach d. Für d = 0 ist g′ = \frac{1}{LC_{σ}(g)} g bereits eine LT_{σ}(g′)-Repräsentation. Ist d > 0 und gilt g′ ≠ \frac{1}{LC_{σ}(g)} g, so ist g′ ∈ F̃_{k} für ein k ∈ {1, …, d}. Nach Satz 1.1 muss es eine eindeutige Linearkombination g′ = λ′_{1}f′_{1} + ⋯ + λ′_{l}f′_{l} + λ̃_{1}f̃_{1} + ⋯ + λ̃_{m}f̃_{m} mit f′_{i} ∈ F_{k}, f̃_{j} ∈ F̃_{k}^{+} ⊆ G und λ′_{i}, λ̃′_{j} ∈ K \ {0} für i = 1, …, l und j = 1, …, m geben, die keine Terme größer LT_{σ}(g′) aufweist. Die f′_{i} besitzen aber wegen (∗) nach Induktionsannahme eine LT_{σ}(f′_{i})-Repräsentation bzgl. G, und wegen LT_{σ}(f′_{i}) ≤_{σ} LT_{σ}(g′) folgt die Behauptung. □

Satz 3.3 Seien F = (F_{k})_{k=1,...,d} und F̃ = (F̃_{k})_{k=1,...,d} mit d ∈ ℕ und endlichen Mengen F_{k} ⊆ Simplify(𝕋^{n}, ⋃_{i=1}^{k−1} F̃_{i}^{+}, (F_{i})_{i=1,...,k−1}, (F̃_{i})_{i=1,...,k−1}) für k = 1, …, d. Seien G ⊆ P \ {0} endlich mit F_{k}^{+} ⊆ G für k = 1, …, d und g_{1}, g_{2} ∈ G mit g_{1} ≠ g_{2}. Seien (t′_{ij}, g′_{i}) := Simplify(t_{ij}, g_{i}, F, F̃) und f_{i} := t′_{ij}g′_{i} für i, j = 1, 2, i ≠ j. Das S-Polynom S von f_{1} und f_{2} habe eine t′-Repräsentation für t′ ∈ 𝕋^{n} mit t′ <_{σ} LT_{σ}(f_{1}) = LT_{σ}(f_{2}) = kgV (t_{1}, t_{2}). Dann besitzt S_{12} eine t-Repräsentation bzgl. G für ein t <_{σ} kgV (t_{1}, t_{2}). Beweis: Das S-Polynom von g′_{1} und g′_{2} ist ebenfalls S. Es gilt:

S_{12} = \frac{1}{c_{1}} t_{12}g_{1} − \frac{1}{c_{2}} t_{21}g_{2}

= \frac{1}{c_{1}} t_{12}g_{1} − t′_{12}g′_{1} + t′_{12}g′_{1} − t′_{21}g′_{2} + t′_{21}g′_{2} − \frac{1}{c_{2}} t_{21}g_{2}

= r_{1} + S + r_{2}

Nach Satz 3.1 b) gilt LT_{σ}(r_{1}), LT_{σ}(r_{2}) <_{σ} LT_{σ}(t_{12}g_{1}) = LT_{σ}(t_{21}g_{2}) = kgV(t_{1}, t_{2}). Mit Lemma 3.2 folgt, dass S_{12} für t := max_{σ}{LT_{σ}(r_{1}), LT_{σ}(r_{2}), t′} <_{σ} kgV(t_{1}, t_{2}) eine t-Repräsentation besitzt. □

Um Simplify einzubauen, müssen auch Red und F_{4} wie folgt verändert werden:

Lemma 3.4 Die Reduktionsfunktion Red(L, G, F, F̃) erhält zu den endlichen Mengen L, G ⊆ P \ {0} zusätzliche Parameter F = (F_{k})_{k=1,...,d} und F̃ = (F̃_{k})_{k=1,...,d} mit d ∈ ℕ und endlichen Mengen F_{k} ⊆ P für k = 1, …, d und wird wie folgt modifiziert:

1 Setze F := L 2 Setze D := LT_{σ}(F) 3 Wiederhole die Schritte 4 bis 6, solange D ≠ Supp(F) gilt: 4 Wähle ein m ∈ Supp(F) \ D 5 Füge m zu D hinzu 6 Gibt es ein g ∈ G, so dass LT_{σ}(g) ein Teiler von m ist,

so berechne (t, f) := Simplify(\frac{m}{LT_{σ}(g)}, g, F, F̃) und füge tf zu F hinzu 7 Berechne F̃ und gib (F, F̃, F̃^{+}) als Ergebnis zurück

Dies ist ein Algorithmus.

Beweis: Die Endlichkeit gegenüber der ersten Version (Satz 1.2) bleibt erhalten, da im Beweis nur LT_{σ}(\frac{m}{LT_{σ}(g)}g) durch LT_{σ}(tf) ersetzt werden muss; diese Leitterme sind aber nach Satz 3.1 a) identisch. □

Satz 3.5 Sei G = {g_{1}, …, g_{s}} ⊆ P \ {0}. Für alle i, j ∈ {1, …, s} mit i < j habe S_{ij} eine t-Repräsentation bzgl. G mit t <_{σ} kgV (t_{i}, t_{j}). Dann ist G eine σ-Gröbnerbasis.

Beweis: siehe Becker, Weispfennig, Groebner Bases, Springer, 1993, S. 219 □

Theorem 3.6 (Verbesserter Algorithmus F_{4}) Sei G ⊆ P eine endliche Menge, und sei I das von G erzeugte Ideal. Weiter sei Sel(M) eine (beliebige) Auswahlfunktion, die eine nichtleere Teilmenge der übergebenen Menge M zurückliefert. Die folgenden Instruktionen definieren die optimierte Funktion F_{4}(G):

1 Setze H := ∅, B := ∅, s := 0 und d := 0 2 Wiederhole die Schritte 3 bis 7 für jedes g ∈ G: 3 Erhöhe s um 1 4 Definiere g_{s} := g 5 Hänge g_{s} an H an 6 Hänge die Elemente von {(i, s) | 1 ≤ i < s} an B an 7 Führe Update(H, B) durch 8 Wiederhole die Schritte 9 bis 21, solange B ≠ ∅ ist: 9 Erhöhe d um 1 10 Setze C := Sel(B) 11 Ersetze B durch B \ C 12 Setze F := (F_{k})_{k=1,...,d−1} und F̃ := (F̃_{k})_{k=1,...,d−1} 13 Setze L′ := {Simplify(t_{ij}, g_{i}, F, F̃) | (i, j) ∈ C} ∪ {Simplify(t_{ji}, g_{j}, F, F̃) | (i, j) ∈ C}

14 Setze L := {tf | (t, f) ∈ L′} 15 Berechne (F_{d}, F̃_{d}, F̃_{d}^{+}) := Red(L, G, F, F̃) 16 Wiederhole die Schritte 17 bis 21 für jedes f ∈ F̃_{d}^{+}: 17 Erhöhe s um 1 18 Definiere g_{s} := g 19 Hänge g_{s} an H an 20 Hänge die Elemente von {(i, s) | 1 ≤ i < s} an B an 21 Führe Update(H, B) durch 22 Gib H zurück

Der verbesserte Algorithmus F_{4} berechnet eine σ-Gröbnerbasis H von I.

Beweis: Die Endlichkeit folgt genau wie in der ursprünglichen Version von F_{4} (Theorem 2.1). Um die Korrektheit von F_{4} nach Satz 3.5 zu beweisen, muss gezeigt werden, dass die Voraussetzungen von Satz 3.3 erfüllt sind. Für i, j ∈ {1, …, s}, i ≠ j seien (t′_{ij}, g′_{i}) := Simplify(t_{ij}, g_{i}, F, F̃) und f_{i} := t′_{ij}g′_{i}. Dann muss für i < j das S-Polynom S von f_{i} und f_{j} eine t-Repräsentation bzgl. H mit t <_{σ} kgV (t_{i}, t_{j}) besitzen. Dies ist nach Lemma 3.2 der Fall wegen S = f_{i} − f_{j} = t′_{ij}g′_{i} − t′_{ji}g′_{j} und t′_{ij} ≤_{σ} t_{ij}, t′_{ji} ≤_{σ} t_{ji} sowie t_{ij}, t_{ji} <_{σ} kgV(t_{i}, t_{j}) (o. E. I ≠ P). □