Gröbnerbasis

Eine Gröbnerbasis (nach Bruno Buchberger, 1965) bzw. Standardbasis (nach Heisuke Hironaka, 1964) ist ein endliches Erzeugendensystem zu einem Ideal $I$ im Polynomring $K[X_{1},\ldots ,X_{n}]$ über dem (kommutativen) Körper $K$, die besonders gut dafür geeignet ist, zu entscheiden, ob ein gegebenes Polynom zum Ideal gehört oder nicht.

Das Idealzugehörigkeitsproblem

Sei $I=\langle g_{1},\ldots ,g_{n}\rangle \subseteq K[X_{1},\dots ,X_{k}]$, also das Ideal $I$ von den Polynomen $g_{1},\ldots ,g_{n}$ erzeugt, dann gehört ein Polynom $f$ genau dann zu $I$, wenn sich $f$ als Linearkombination

$f=a_{1}g_{1}+\dots +a_{n}g_{n}$

mit Polynomen $a_{1},\dots ,a_{n}\in K[X_{1},\dots ,X_{k}]$ schreiben lässt.

Man kann nun versuchen, so eine Darstellung mit Hilfe der Polynomdivision mit Rest zu finden, indem man so lange dividiert, bis der erhaltene Rest verschwindet (also die Division aufgeht):

$f=a_{1}g_{1}+r_{1}$

$f=a_{1}g_{1}+a_{2}g_{2}+r_{2}$

...

Dabei treten aber zwei Probleme auf:

1. Falls mehr als eine Variable in den Polynomen vorkommen ($k>1$), so lassen sich die Terme eines Polynoms nicht so ohne weiteres "der Größe nach" ordnen, was für die Polynomdivision notwendig ist.
2. Können wir denn überhaupt sicher sein, dass durch wiederholte Polynomdivision immer der Rest 0 erscheint?

Das erste Problem lässt sich recht einfach lösen, indem eine Monomordnung gewählt wird. Dann können die Terme jedes Polynomes so angeordnet werden, wie es die Ordnung vorgibt - vor allem können wir nun vom Leitterm ${\rm {LT}}$ eines Polynoms sprechen, also dem (bzgl. der Monomordnung) größten Monom mit seinem Koeffizienten. Der einzige Nachteil ist aber, dass diese Reihenfolge, und damit das Ergebnis der Polynomdivisionen immer von dieser Wahl abhängen.

Das zweite Problem ist schwieriger, denn es ist tatsächlich nicht lösbar, wenn die erzeugenden Polynome fest vorgegeben sind. Es kann nur gelöst werden, indem das Erzeugendensystem passend geändert wird - dieses geänderte Erzeugendensystem ist dann eine Gröbnerbasis.

Verallgemeinerte Polynomdivision

Die Aufgabe der verallgemeinerten Polynomdivision ist nun also: Für ein Polynom $f$ und mehrere Polynome $g_{1},\dots ,g_{n}$ sollen Polynome $a_{1},\dots ,a_{n},r$ gefunden werden, die die Gleichung

$f=a_{1}g_{1}+\dots +a_{n}g_{n}+r$

erfüllen.

Dazu bietet sich folgendes Vorgehen an:

1. Beginne mit $a_{1}=\dots =a_{n}=r=0$
2. Falls $f=0$ breche ab, sonst vergleiche der Reihe nach alle ${\rm {{LT}(g_{i})}}$, ob sie ${\rm {{LT}(f)}}$ teilen.
3. Falls etwa $a{\rm {{LT}(g_{i})={\rm {{LT}(f)}}}}$, so ersetze $a_{i}$ durch $a_{i}+a$ und $f$ durch $f-ag_{i}$ und gehe zu Schritt 2.
4. Falls kein ${\rm {{LT}(g_{i})}}$ teilt, so ersetze $r$ durch $r+{\rm {{LT}(f)}}$ und $f$ durch $f-{\rm {{LT}(f)}}$ und gehe zu Schritt 2.

Dann ist in jedem Schritt die Gleichung

$f_{urspr}=a_{1}g_{1}+\dots +a_{n}g_{n}+r+f_{aktuell}$

erfüllt, und schließlich, wenn $f_{aktuell}=0$ ist die gewünschte Darstellung gefunden.

Mit dieser Division haben wir das Problem wie gewünscht auf ein kleineres Polynom reduziert, denn es ist $f\in I$ genau dann, wenn $r\in I$. Falls $r=0$ ist das klar, und $f\in I$. Ist aber $r\neq 0$ können wir auf diesem Weg nicht entscheiden, ob $r\in I$ oder $r\not \in I$:

Beispiel: Seien $g_{1}=x$, $g_{2}=x^{2}+1$ und $f=g_{1}+g_{2}=x^{2}+x+1$. Testet man die erzeugenden Polynome der Reihe nach (also in aufsteigende Reihenfolge der Indizes) und wendet die beschriebene Division an erhält man:

$f=xg_{1}+(x+1)=(x+1)g_{1}+1$

Offenbar gilt aber $f=g_{1}+g_{2}\in I$, also auch $r=1\in I$ (nämlich $1=-xg_{1}+g_{2}$). Man kann also im Allgemeinen aus $r\neq 0$ nicht folgern, dass $g\not \in I$ und damit $f\not \in I$ gilt.

Definition

Ein Erzeugendensystem $G=(g_{1},\ldots ,g_{n})$ von $I$ ist eine Gröbnerbasis (bezüglich einer Monomordnung $<$) von $I$, falls für jedes Polynom $f\in I\setminus {0}$ ein $g_{i}$ existiert, dessen Leitmonom das Leitmonom von $f$ teilt.

Eine Gröbnerbasis $G$ heißt reduziert, falls alle $g\in G$ normiert sind, und kein Monom von $g$ durch die Leitterme der anderen Gröbnerbasispolynome dargestellt werden kann, also kein Monom von $g$ in $\langle \{{\rm {{LT}(g'):g'\in G\setminus \{g\}\rangle }}$ liegt. Man kann zeigen, dass jedes Ideal (für eine gegebene Monomordnung) eine eindeutig bestimmte reduzierte Gröbnerbasis besitzt.

Anwendungen

Das Konzept von Gröbnerbasen gibt zunächst eine Lösung des Idealzugehörigkeitsproblems. Damit verbunden lassen sich aber auch andere Probleme lösen (oder zumindest vereinfachen).

Lösung des Idealzugehörigkeitsproblems

Wird mit dem oben beschriebenen Verfahren eine nicht weiter reduzierbare Darstellung

$f=k_{1}g_{1}+\ldots +k_{n}g_{n}+r$

bezüglich einer Gröbnerbasis $G=(g_{1},\ldots ,g_{n})$ des Ideals $I$ gefunden, so gilt $f\in I$ genau dann, wenn $r\in I$. Da aber $G$ eine Gröbnerbasis ist gilt das wiederum genau dann, wenn $r=0$, da nach Annahme kein Leitmonom eines $g_{i}$ das Leitmonom von $r$ teilt.

Mit dem Buchberger-Algorithmus können Gröbnerbasen berechnet werden. Damit ist das Problem, ob ein Polynom zu einem Ideal gehört oder nicht, von Computeralgebrasystemen lösbar.

Beispiel: Wenn wie im Beispiel oben die erzeugenden Polynome $g_{1}=x,g_{2}=x^{2}+1$ gegeben sind, sowie $f=g_{1}+g_{2}=x^{2}+x+1$, dann hatte die Polynomdivision Rest $1$ geliefert.

Wenden wir zunächst den Buchberger-Algorithmus auf dieses Beispiel an, so erhalten wir die (nicht reduzierte) Gröbnerbasis $(x,x^{2}+1,-1)$ von $I$. Bezüglich dieses Divisors kann ist die Division hier noch nicht abgeschlossen, denn es ist mit $g_{3}=-1$:

$f=xg_{1}+(x+1)=(x+1)g_{1}+1=(x+1)g_{1}+(-1)g_{3}$

Wir sehen hier auch, dass die Darstellung bezüglich der Gröbnerbasis nicht eindeutig ist (da $f=g_{1}+g_{2}=(x+1)g_{1}-g_{3}$), sondern von der Reihenfolge der erzeugenden Polynome und der gewählten Monomordnung abhängt.

Nicht-lineare Gleichungssysteme

Ein nicht-lineares Gleichungssystem besteht aus endlich vielen Polynomen $f_{1},...,f_{k}\in K[x_{1},...,x_{n}]$, deren gemeinsame Nullstellen gesucht sind. Die Lösungsmenge $\{x\in K^{n}:f_{1}(x)=...=f_{k}(x)=0\}$ eines solchen Gleichungssystems beschreibt eine algebraische Varietät, die aber durch die Polynome nicht eindeutig bestimmt ist, sondern durch das Ideal, dass diese Polynome erzeugen.

Soll ein bestimmtes nicht-lineares Gleichungssystem gelöst werden, genügt es also das Ideal zu betrachten, dass von den Polynomen erzeugt wird. Dann kann es hilfreich sein, mit Hilfe des Buchberger-Algorithmus und einer geeigneten lexikographischen Monomordnung eine reduzierte Gröbnerbasis zu finden. Dann bleibt zwar das Problem, die Nullstellen dieser Polynome zu finden (z.B. näherungsweise durch numerische Verfahren), aber die zu untersuchenden Polynome haben immerhin eine kleinere Anzahl an Variablen und kleineren Grad.

Beispiel: Welche Lösungen $(x,y,z)\in \mathbb {R} ^{3}$ hat das folgende Gleichungssystem?

$x^{2}+y^{2}+z^{2}-1=0$

$x^{2}-y+z^{2}=0$

$x-z=0$

Mit Hilfe des Computers erhält man für die lexikographische Monomordnung $x>y>z$ die (reduzierte) Gröbnerbasis $g_{1}=x-z$, $g_{2}=-y+2z^{2}$ und $g_{3}=z^{4}+{\frac {1}{2}}z^{2}-{\frac {1}{4}}$. Die gesuchten Lösungen sind also genau die Lösungen des einfacheren Gleichungssystems

$x=z$

$y=2z^{2}$

$z^{4}+{\frac {1}{2}}z^{2}-{\frac {1}{4}}=0$

Und wir sehen, dass die Lösungsmenge aus nur vier Punkten besteht: $\{(z,2z^{2},z):z=\pm {\frac {1}{2}}{\sqrt {\pm {\sqrt {5}}-1}}\}$.

Gleichheit von Idealen und algebraischen Varietäten

Da (zu einer gegebenen Monomordnung) die reduzierte Gröbnerbasis eines Ideals eindeutig bestimmt ist, kann die Gleichheit von Idealen untersucht werden, indem (zu irgendeiner Monomordnung) die reduzierten Gröbnerbasen gebildet werden. Die Ideale sind genau dann gleich, wenn diese reduzierten Gröbnerbasen gleich sind.

Auf diese Weise kann man auch rein rechnerisch die Gleichheit von algebraischen Varietäten untersuchen, da diese durch ihre erzeugenden Ideale eindeutig bestimmt sind. Sind die reduzierten Gröbnerbasen gleich, dann sind die erzeugenden Ideale und damit auch die erzeugten Varietäten gleich.

Literatur

• Heisuke Hironaka: Resolution of singularities of an algebraic variety over a field of characteristic zero, In: Annals of Mathematics 79 (1964), Nr. 1, S. 109–326
• Bruno Buchberger: Ein Algorithmus zum Auffinden der Basiselemente des Restklassenringes nach einem nulldimensionalen Polynomideal. Österreich, Universität Innsbruck, Diss., 1965
• Bruno Buchberger:Ein algorithmisches Kriterium für die Lösbarkeit eines algebraischen Gleichungssystems. Aequationes Mathematicae 4 (1970): 374-383.
• T. Becker, B. V. Weispfenning: Gröbner bases: a computational approach to commutative algebra. Graduate Texts in Mathematics: readings in mathematics. Bd. 141, New York: Springer Verlag, 1993
• David Cox; Little, John; O'Shea, Donald: Ideals, varieties, and algorithms. New York: Springer-Verlag, 1997
• Joachim von z. Gathen, Jürgen Gerhard: Modern Computer Algebra. Cambridge University Press, 1999