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 Körper $K$, 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

Das Idealzugehörigkeitsproblem

Sei $I=(g_{1},\ldots ,g_{n})\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 und damit 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. Bei multivariaten Polynomen $p\in K[X_{1},\ldots ,X_{k}]$ 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 $\operatorname {LT}$ 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

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$, brich ab, sonst vergleiche der Reihe nach alle $\operatorname {LT} (g_{i})$, ob sie Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \operatorname{LT}(f)} teilen.
3. Falls etwa Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a \operatorname{LT}(g_i) = \operatorname{LT}(f)} , so ersetze Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a_i} durch Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a_i + a} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f} durch Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f - ag_i} und gehe zu Schritt 2.
4. Falls Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \operatorname{LT}(f)} von keinem Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \operatorname{LT}(g_i)} geteilt wird, so ersetze Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle r} durch Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle r + \operatorname{LT}(f)} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f} durch Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f - \operatorname{LT}(f)} und gehe zu Schritt 2.

Dann ist in jedem Schritt die Gleichung

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f_\text{urspr} = a_1 g_1 + \dots + a_n g_n + r + f_\text{aktuell}}

erfüllt, und schließlich, wenn Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f_\text{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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f \in I} genau dann, wenn Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle r \in I} . Falls Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle r = 0} , ist das klar, und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f \in I} . Ist aber Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle r \neq 0} , können wir auf diesem Weg nicht entscheiden, ob Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle r \in I} oder Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle r \not\in I} :

Beispiel: Seien Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle g_1 = x} , Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle g_2 = x^2+1} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f = g_1 + g_2 = x^2 + x + 1} . Testet man die erzeugenden Polynome der Reihe nach (also in aufsteigender Reihenfolge der Indizes) und wendet die beschriebene Division an, erhält man:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f = xg_1 + (x+1) = (x+1)g_1 + 1}

Offenbar gilt aber Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f = g_1+g_2 \in I} , also auch Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle r = 1 \in I} (nämlich Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 1 = -xg_1 + g_2} ). Man kann also im Allgemeinen aus Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle r \neq 0} nicht folgern, dass Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle r \not\in I} und damit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f \not\in I} gilt.

Definition

Ein Erzeugendensystem Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G=(g_1,\ldots,g_n)} von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle I} ist eine Gröbnerbasis (bezüglich einer Monomordnung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle <} ) von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle I} , falls für jedes Polynom Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f \in I \setminus \{0\}} ein Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle g_i} existiert, dessen Leitmonom das Leitmonom von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f} teilt.

Eine Gröbnerbasis Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G} heißt reduziert, falls alle Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle g \in G} normiert sind, und kein Monom von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle g} durch die Leitterme der anderen Gröbnerbasispolynome dargestellt werden kann, also kein Monom von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle g} in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \langle \{\operatorname{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

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f = k_1g_1 + \ldots + k_ng_n + r}

bezüglich einer Gröbnerbasis Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G = (g_1, \ldots, g_n)} des Ideals Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle I} gefunden, so gilt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f \in I} genau dann, wenn Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle r \in I} . Da aber Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G} eine Gröbnerbasis ist, gilt das wiederum genau dann, wenn Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle r = 0} , da nach Annahme kein Leitmonom eines Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle g_i} das Leitmonom von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle g_1 = x, g_2 = x^2 + 1} gegeben sind, sowie Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f = g_1 + g_2 = x^2 + x + 1} , dann hatte die Polynomdivision Rest Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 1} geliefert.

Wenden wir zunächst den Buchberger-Algorithmus auf dieses Beispiel an, so erhalten wir die (nicht reduzierte) Gröbnerbasis Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (x, x^2 + 1, -1)} von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle I} . Bezüglich dieses Divisors ist die Division hier noch nicht abgeschlossen, denn es ist mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle g_3 = -1} :

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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.

Polynomiale Gleichungssysteme

Ein polynomiales Gleichungssystem besteht aus endlich vielen Gleichungen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f_1(x)=0,\ldots, f_k(x)=0} , wobei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle f_1,\ldots, f_k \in K[x_1, \ldots,x_n]} gegebene Polynome in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} Unbestimmten über einem Körper Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle K} und deren gemeinsame Nullstellen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x\in K^n} gesucht sind. Die Lösungsmenge Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \{x \in K^n : f_1(x) = \cdots = f_k(x) = 0\}} eines solchen Gleichungssystems beschreibt eine algebraische Varietät. Diese ist offenbar gleich Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \{x \in K^n : f(x)= 0 \quad\forall f\in I\}} , wobei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle I=(f_1,\ldots,f_k)} 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (x, y, z) \in \R^3} hat das folgende Gleichungssystem?

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x^2 + y^2 + z^2 - 1 = 0}

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x^2 - y + z^2 = 0}

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x - z = 0}

Mit Hilfe des Computers erhält man für die lexikographische Monomordnung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x > y > z} die (reduzierte) Gröbnerbasis Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle g_1 = x - z, g_2 = -y + 2z^2} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x = z}

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle y = 2z^2}

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle z^4 + \frac 1 2 z^2 - \frac 1 4 = 0}

Und wir sehen, dass die Lösungsmenge aus nur zwei Punkten besteht: Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \left\{(z, 2z^2, z) : z = \pm \frac 1 2 \sqrt{\sqrt 5 - 1}\right\}} (die zwei weiteren Lösungen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \pm\frac 1 2 \sqrt{-\sqrt 5 -1}} sind in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \R} nicht enthalten).

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 (PDF; 1,8 MB). Österreich, Universität Innsbruck, Diss., 1965
• Bruno Buchberger: Ein algorithmisches Kriterium für die Lösbarkeit eines algebraischen Gleichungssystems (PDF; 475 kB). 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