Eine Gröbnerbasis (nach Bruno Buchberger, 1965) bzw. Standardbasis (nach Heisuke Hironaka, 1964) ist ein endliches Erzeugendensystem zu einem Ideal im Polynomring über dem Körper , das besonders gut dafür geeignet ist, zu entscheiden, ob ein gegebenes Polynom zum Ideal gehört oder nicht.

Buchberger entwickelte diese 1965 in seiner Dissertation bei Wolfgang Gröbner und benannte sie nach ihm.

Motivation: Idealzugehörigkeitsproblem und verallgemeinerte Polynomdivision

Bearbeiten

Das Idealzugehörigkeitsproblem

Bearbeiten

Es sei  , also das Ideal   von den Polynomen   erzeugt, dann gehört ein Polynom   genau dann zu  , wenn sich   als Linearkombination

 

mit Polynomen   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 und damit die Division aufgeht:

 
 

Dabei treten aber zwei Probleme auf:

  1. Bei multivariaten Polynomen   lassen sich die Terme nicht mehr ohne Weiteres „der Größe nach“ ordnen, was für die Polynomdivision aber 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 nach dieser Ordnung angeordnet werden; vor allem können wir nun vom Leitterm   eines Polynoms sprechen, also des bezüglich der Monomordnung größten Monoms mit seinem Koeffizienten. Als Nachteil bleibt, dass die Anordnung der Monome und auch das Ergebnis der Polynomdivisionen von der Wahl der Monomordnung 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. Eine Gröbnerbasis stellt sich als ein geeignetes Erzeugendensystem heraus.

Verallgemeinerte Polynomdivision

Bearbeiten

Die Aufgabe der verallgemeinerten Polynomdivision ist nun also: Für ein Polynom   und mehrere Polynome   sollen Polynome   gefunden werden, die die Gleichung

 

erfüllen.

Dazu bietet sich folgendes Vorgehen an:

  1. Beginne mit  .
  2. Falls  , brich ab, sonst vergleiche der Reihe nach alle  , ob sie   teilen.
  3. Falls etwa  , so ersetze   durch   und   durch   und gehe zu Schritt 2.
  4. Falls   von keinem   geteilt wird, so ersetze   durch   und   durch   und gehe zu Schritt 2.

Dann ist in jedem Schritt die Gleichung

 

erfüllt, und schließlich, wenn  , ist die gewünschte Darstellung gefunden.

Mit dieser Division haben wir das Problem wie gewünscht auf ein kleineres Polynom reduziert, denn es ist   genau dann, wenn  . Falls  , ist das klar, und  . Ist aber  , können wir auf diesem Weg nicht entscheiden, ob   oder  :

Beispiel: Seien  ,   und  . Testet man die erzeugenden Polynome der Reihe nach (also in aufsteigender Reihenfolge der Indizes) und wendet die beschriebene Division an, erhält man:

 

Offenbar gilt aber  , also auch   (nämlich  ). Man kann also im Allgemeinen aus   nicht folgern, dass   und damit   gilt.

Definition

Bearbeiten

Ein Erzeugendensystem   von   ist eine Gröbnerbasis (bezüglich einer Monomordnung  ) von  , falls für jedes Polynom   ein   existiert, dessen Leitmonom das Leitmonom von   teilt.

Eine Gröbnerbasis   heißt reduziert, falls alle   normiert sind, und kein Monom von   durch die Leitterme der anderen Gröbnerbasispolynome dargestellt werden kann, also kein Monom von   in   liegt. Man kann zeigen, dass jedes Ideal (für eine gegebene Monomordnung) eine eindeutig bestimmte reduzierte Gröbnerbasis besitzt.

Anwendungen

Bearbeiten

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

Bearbeiten

Wird mit dem oben beschriebenen Verfahren eine nicht weiter reduzierbare Darstellung

 

bezüglich einer Gröbnerbasis   des Ideals   gefunden, so gilt   genau dann, wenn  . Da aber   eine Gröbnerbasis ist, gilt das wiederum genau dann, wenn  , da nach Annahme kein Leitmonom eines   das Leitmonom von   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   gegeben sind, sowie  , dann hatte die Polynomdivision Rest   geliefert.

Wenden wir zunächst den Buchberger-Algorithmus auf dieses Beispiel an, so erhalten wir die (nicht reduzierte) Gröbnerbasis   von  . Bezüglich dieses Divisors ist die Division hier noch nicht abgeschlossen, denn es ist mit  :

 

Wir sehen hier auch, dass die Darstellung bezüglich der Gröbnerbasis nicht eindeutig ist (da  ), sondern von der Reihenfolge der erzeugenden Polynome und der gewählten Monomordnung abhängt.

Polynomiale Gleichungssysteme

Bearbeiten

Ein polynomiales Gleichungssystem besteht aus endlich vielen Gleichungen  , wobei   gegebene Polynome in   Unbestimmten über einem Körper   und deren gemeinsame Nullstellen   gesucht sind. Die Lösungsmenge   eines solchen Gleichungssystems beschreibt eine algebraische Varietät. Diese ist offenbar gleich  , wobei   das von den Polynomen erzeugte Ideal ist.

Soll ein bestimmtes polynomiales Gleichungssystem gelöst werden, genügt es also das Ideal zu betrachten, das 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   hat das folgende Gleichungssystem?

 
 
 

Mit Hilfe des Computers erhält man für die lexikographische Monomordnung   die (reduzierte) Gröbnerbasis   und  . Die gesuchten Lösungen sind also genau die Lösungen des einfacheren Gleichungssystems

 
 
 

Und wir sehen, dass die Lösungsmenge aus nur zwei Punkten besteht:   (die zwei weiteren Lösungen   sind in   nicht enthalten).

Gleichheit von Idealen und algebraischen Varietäten

Bearbeiten

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

Bearbeiten