PD. Dr. Martin Kreuzer WS 2001/2002 Fakultät für Mathematik Universität Regensburg

Übungen zur Vorlesung “Computeralgebra für Naturwissenschaftler”

Tutorium 4: Berechnung einiger Gröbner-Basen

In diesem Tutorium wollen wir zwei Versionen des Buchberger-Algorithmus für Polynomideale implementieren und an einigen Beispielen ausprobieren. Insbesondere werden wir einen Fall sehen, in dem die Elemente der Gröbner-Basis sehr hohen Grad haben, obwohl die Erzeuger des Ideals kleine Grade haben.

a) Schreiben Sie eine CoCoA-Funktion SPoly(…), die eine Liste [g_{1}, …, g_{s}] von Polynomen und Indizes i, j ∈ {1, …, s} mit i ≠ j als Argumente nimmt, und die das S-Polynom S_{ij} von g_{i} und g_{j} bzgl. der momentanen Termordnung berechnet.

b) Implementieren Sie Buchbergers Algorithmus in einer CoCoA-Funktion FirstGB(…), die die Gröbner-Basis eines Ideals bzgl. der momentanen Termordnung berechnet. (Hinweis: Verwenden Sie die eingebaute Funktion NR(…).)

c) Berechnen Sie mit Hilfe von FirstGB(…) die Gröbner-Basen der folgenden Ideale bzgl. der angegebenen Termordnungen.

1) I_{1} = (y^{2}, xyz + z^{3}) ⊆ ℚ[x, y, z] bzgl. DegRevLex

2) I_{2} = (x^{2}y − 1, xy^{2} − x) ⊆ ℚ[x, y] bzgl. Lex und bzgl. DegRevLex

3) I_{3} = (x − z^{4}, y − z^{5}) ⊆ ℚ[x, y, z] bzgl. Lex und bzgl. DegRevLex

d) Berechnen Sie mit Hilfe von FirstGB(…) die reduzierte Gröbner-Basis des folgenden Ideals I_{m} bzgl. DegRevLex für i = 1, …, 100. I_{m} = (x_{1}^{m+1} − x_{2}x_{3}^{m−1}x_{4}, x_{1}x_{2}^{m−1} − x_{3}^{m}, x_{1}^{m}x_{3} − x_{2}^{m}x_{4}) ⊆ ℚ[x_{1}, x_{2}, x_{3}, x_{4}] Können Sie die Gesetzmässigkeit erraten? Können Sie dies sogar beweisen?

e) Beweisen Sie, dass die reduzierte Gröbner-Basis in d) stets das Polynom f_{m} = x_{3}^{m^{2}+1} − x_{2}^{m^{2}}x_{4} enthält. Zeigen Sie auch, dass I_{3} bzgl. Lex und DegRevLex dieselbe Gröbner-Basis hat. Stimmt dies für alle m?

f) Schreiben Sie eine CoCoA-Funktion SecondGB(…), die den Buchberger-Algorithmus implementiert und die folgenden beiden Optimierungen beinhaltet:

1) Das nächste abzuarbeitende Paar wird in B stets so gewählt, dass der Grad von kgV(t_{i}, t_{j}) minimal ist. Dies ist die normale Auswahlstrategie.

2) Gilt ggT(t_{i}, t_{j}) = 1, so braucht S_{ij} gar nicht erst berechnet zu werden, weil

sich stets NR_{σ,H}(S_{ij}) = 0 ergibt. Es liegt eine triviale Syzygie vor.

g) Vergleichen Sie die Algorithmen FirstGB(…) und SecondGB(…) in den folgenden Fällen. Messen Sie dazu die Ausführungsgeschwindigkeit und zählen Sie die Anzahl der Aufrufe von NR(…). Verwenden Sie sowohl Lex als auch DegRevLex.

1) J_{1} = (x^{2} − 2y^{2} + 3x, x^{3} − 2xy) ⊆ ℚ[x, y]

2) J_{2} = (x − 2z^{4}, y − 3z^{5}) ⊆ ℚ[x, y, z]

3) J_{3} = (x^{2} − 2y^{2}, x^{3} − 3z^{3}, x^{4} − t^{4}) ⊆ Q[x, y, z, t]

4) J_{4} = (x^{3} − 4y^{3}, x^{5} − 7z^{5}, x^{7} − 11t^{7}) ⊆ ℚ[x, y, z, t]

5) J_{5} = (x^{2} + y^{3} + z^{3} − 1, x^{3} + y^{4} + z^{5} − 1) ⊆ ℚ[x, y, z]