Gröbnerbasis

Kernidee und Bedeutung

Eine Gröbnerbasis ist ein besonderes endliches Erzeugendensystem eines Ideals I im Polynomring K[X₁,…,Xₙ] über einem Körper K. Sie ist so gewählt, dass sich zuverlässig entscheiden lässt, ob ein gegebenes Polynom zu I gehört. Darüber hinaus hilft sie beim Lösen polynomialer Gleichungssysteme sowie beim Vergleichen von Idealen und algebraischen Varietäten.

Die Berechnungen hängen von einer Monomordnung ab. Diese legt fest, wie Monome geordnet werden. Dadurch besitzt jedes von null verschiedene Polynom einen Leitterm LT(f): das bezüglich der Monomordnung größte Monom zusammen mit seinem Koeffizienten. Sowohl die Reihenfolge der Monome als auch Ergebnisse einer mehrdimensionalen Polynomdivision können von der gewählten Monomordnung abhängen.

Idealzugehörigkeit und Polynomdivision

Ist I=(g₁,…,gₙ)⊆K[X₁,…,Xₖ], so gehört ein Polynom f genau dann zu I, wenn Polynome a₁,…,aₙ existieren mit

f=a₁g₁+⋯+aₙgₙ.

Um eine solche Darstellung zu suchen, wird die Polynomdivision auf mehrere Divisoren verallgemeinert. Gesucht werden Polynome a₁,…,aₙ und ein Rest r mit

f=a₁g₁+⋯+aₙgₙ+r.

Zu Beginn setzt man a₁=⋯=aₙ=r=0. Solange das aktuell zu bearbeitende Polynom nicht null ist, vergleicht man seinen Leitterm mit den Leittermen LT(gᵢ). Teilt ein LT(gᵢ) den aktuellen Leitterm, wird ein geeignetes Vielfaches von gᵢ abgezogen und der entsprechende Koeffizient aᵢ ergänzt. Ist der aktuelle Leitterm durch keinen LT(gᵢ) teilbar, wird er zum Rest r hinzugefügt und aus dem aktuellen Polynom entfernt. Während des gesamten Verfahrens gilt

f_ursprünglich=a₁g₁+⋯+aₙgₙ+r+f_aktuell.

Am Ende ist f_aktuell=0 und die gewünschte Darstellung liegt vor. Es gilt dann f∈I genau dann, wenn r∈I. Bei beliebigen Erzeugern folgt aus r≠0 jedoch nicht, dass f∉I ist.

Beispielsweise seien g₁=x, g₂=x²+1 und f=g₁+g₂=x²+x+1. Bei Division in aufsteigender Reihenfolge der Indizes erhält man

f=xg₁+(x+1)=(x+1)g₁+1.

Der Rest ist 1, obwohl f∈I gilt. Auch 1 gehört zum Ideal, denn 1=−xg₁+g₂. Ein fest vorgegebenes Erzeugendensystem reicht daher nicht immer für einen eindeutigen Zugehörigkeitstest aus.

Definition der Gröbnerbasis

Ein Erzeugendensystem G=(g₁,…,gₙ) eines Ideals I heißt bezüglich einer Monomordnung < eine Gröbnerbasis, wenn für jedes f∈I{0} mindestens ein gᵢ existiert, dessen Leitmonom das Leitmonom von f teilt. Genau diese Eigenschaft beseitigt das Problem, dass bei gewöhnlichen Erzeugern trotz f∈I ein nicht verschwindender, nicht weiter reduzierbarer Rest auftreten kann.

Eine Gröbnerbasis G heißt reduziert, wenn alle g∈G normiert sind und kein Monom eines Basispolynoms g durch die Leitterme der anderen Basispolynome dargestellt werden kann. Formal darf kein Monom von g im Ideal ⟨{LT(g′):g′∈G{g}}⟩ liegen.

Für jedes Ideal und jede fest gewählte Monomordnung gibt es genau eine reduzierte Gröbnerbasis. Nicht reduzierte Gröbnerbasen und Darstellungen eines Polynoms durch die Basispolynome müssen dagegen nicht eindeutig sein.

Entscheidung der Idealzugehörigkeit

Wird ein Polynom f bezüglich einer Gröbnerbasis G=(g₁,…,gₙ) so weit dividiert, dass eine nicht weiter reduzierbare Darstellung

f=k₁g₁+⋯+kₙgₙ+r

entsteht, dann gilt

f∈I genau dann, wenn r=0.

Zunächst ist f∈I genau dann, wenn r∈I. Wäre ein von null verschiedener Rest r im Ideal, müsste wegen der Gröbnerbasis-Eigenschaft das Leitmonom eines gᵢ das Leitmonom von r teilen. Das widerspricht der Annahme, dass r nicht weiter reduziert werden kann. Gröbnerbasen können mit dem Buchberger-Algorithmus berechnet werden; dadurch können Computeralgebrasysteme das Idealzugehörigkeitsproblem lösen.

Im Beispiel mit g₁=x und g₂=x²+1 liefert der Buchberger-Algorithmus die nicht reduzierte Gröbnerbasis (x,x²+1,−1). Der zuvor erhaltene Rest 1 lässt sich nun durch g₃=−1 beseitigen:

f=(x+1)g₁+1=(x+1)g₁+(−1)g₃.

Die Darstellung ist dennoch nicht eindeutig, denn auch f=g₁+g₂=(x+1)g₁−g₃ gilt. Sie kann von der Reihenfolge der Erzeuger und der Monomordnung abhängen.

Polynomiale Gleichungssysteme

Ein polynomiales Gleichungssystem besteht aus endlich vielen Gleichungen f₁(x)=0,…,fₖ(x)=0 mit f₁,…,fₖ∈K[x₁,…,xₙ]. Gesucht sind die gemeinsamen Nullstellen x∈Kⁿ. Ihre Menge

{x∈Kⁿ:f₁(x)=⋯=fₖ(x)=0}

heißt algebraische Varietät. Für das Ideal I=(f₁,…,fₖ) stimmt sie mit {x∈Kⁿ:f(x)=0 für alle f∈I} überein. Deshalb kann man statt des ursprünglichen Gleichungssystems das erzeugte Ideal untersuchen.

Mit dem Buchberger-Algorithmus und einer geeigneten lexikographischen Monomordnung kann eine reduzierte Gröbnerbasis berechnet werden. Die Nullstellen müssen anschließend weiterhin bestimmt werden, gegebenenfalls näherungsweise durch numerische Verfahren. Die neue Basis kann jedoch Polynome mit weniger Variablen und kleinerem Grad liefern.

Für das reelle Gleichungssystem

x²+y²+z²−1=0, x²−y+z²=0, x−z=0

ergibt die lexikographische Monomordnung x>y>z die reduzierte Gröbnerbasis

g₁=x−z, g₂=−y+2z², g₃=z⁴+(1/2)z²−1/4.

Das System ist somit gleichbedeutend mit x=z, y=2z² und z⁴+(1/2)z²−1/4=0. Seine reelle Lösungsmenge besteht aus genau zwei Punkten:

{(z,2z²,z): z=±(1/2)√(√5−1)}.

Die beiden weiteren Werte ±(1/2)√(−√5−1) sind nicht reell.

Vergleich von Idealen und Varietäten

Da die reduzierte Gröbnerbasis eines Ideals bei festgelegter Monomordnung eindeutig ist, lässt sich die Gleichheit zweier Ideale rechnerisch prüfen: Man berechnet für beide Ideale reduzierte Gröbnerbasen bezüglich derselben Monomordnung. Die Ideale sind genau dann gleich, wenn ihre reduzierten Gröbnerbasen gleich sind.

Auf diese Weise kann nach Darstellung des Artikels auch die Gleichheit der zugehörigen algebraischen Varietäten untersucht werden. Stimmen die reduzierten Gröbnerbasen überein, so stimmen die erzeugten Ideale und damit auch die erzeugten Varietäten überein.