Dieser Audiobeitrag wird von der Universität Erlangen-Nürnberg präsentiert.

Gut, dann kann es jetzt weitergehen.

Und zwar mit diesem Buchberger Algorithmus. Der hat als Eingabe eine Menge F an Polynomen.

Die erzeugen ideal in einem gewissen Polynomring, in n unbestimmten.

Und ich habe eine gewisse Termordnung gegeben.

Und Output ist eine Menge G in dem Ideal. Endlich und ist eine Gröbner Basis von I bezüglich dieser Termordnung.

Also tatsächlich, wie kann ich ein gegebenes Ideal, also eine Erzeugenmenge umwandeln in eine andere Erzeugenmenge, die schöne Eigenschaften hat, von G die Leiterme von I erzeugen.

So, im ersten Schritt legen wir also los. Wir kopieren uns einfach das

einfach das 11-mal, damit wir immer noch wissen, was die Eingabemenge ist.

Wir sammeln eine Menge von Paaren auf. Wir wollen ja gerade diese ganzen S-Polynome dann betrachten.

Wir sammeln also die ganzen Paare auf. Natürlich brauchen wir nur die, wo F und G verschieden sind, weil das S-Polynomen von F und F ist natürlich 0.

Das sind die kritischen Paare, die werden auch tatsächlich Critical Pairs genannt. Deswegen auch C hier. Und das sind die kritischen Fälle, die ich testen muss, um zu sehen, ob meine Menge G eine Gröbner Basis ist.

Das werde ich danach noch als Satz formulieren. Und jetzt durchlaufe ich eine Schleife.

Also solange C nicht leer ist.

Dann wähle ich mir so ein Paar aus F und G hier raus, brechen das entsprechende S-Polynomen.

Das Paar brauche ich jetzt erstmal nicht weiter betrachten. Das wird also rausgenommen.

Und dann nehme ich dieses S-Polynomen und dividiere das durch G.

Das heißt in anderen Worten, ich will die Normalform von S bezüglich G. Also ich mache eine Polynomendivision von S durch G. Da kommt irgendein Polynom raus.

Jetzt gibt es also zwei Fälle. Wenn R gleich 0 ist, alles super.

Dann habe ich R erfolgreich als polynomialen Linearkombination der Polynomen G dargestellt. Alles super.

Und insbesondere als auch den Leithermen konnte ich da teilen. Und falls R nicht 0 ist, dann ist der Leitherm von R einer, den ich noch nie gesehen habe.

Auch kein Teiler davon.

Der Rest ungleich 0 ist... dann füge ich dieses Element hinzu und damit kriege ich aber auch neue kritische Paare.

Wer möchte, kann also geschweifte Klammern hier noch setzen. Die Schleife geht hier auf und hier zu. Das Wire geht hier auf und hier zu.

Und sollte ich tatsächlich hier runterkommen, dann gebe ich das G zurück.

Das ist jetzt so ein Loop zu dem C, da werden welche rausgenommen. Es werden wieder kritische Situationen hinzugefügt.

Aber wir wissen ja, das kann nicht so oft passieren. Also es kann nur endlich oft passieren.

Dann wird dieser Buchberger Algorithmus terminiert.

Die Folge aller Elemente G, die nicht in F sind, die also im Laufe des Algorithmus hinzukommen. Die ist nach dem großen Dixenlemmer endlich.

Also der Satz ist eigentlich der hier von. Das da hinten ist jetzt quasi schon der Beweis.

Und dass das tatsächlich eine Gründerbasis ist, die da rauskommt, sagt der nächste Satz aus, den der Buchberger gezeigt hat.

Gründerbasis von I, genau dann, was durch dieses G erzeugt wird.

Wenn die Normalform von dem S-Proinomen von F, G bezüglich der Gründerbasis gleich Null ist,

dann ist das für alle F und G aus meiner Gründerbasis, also aus meiner Menge.

Genau dann, wenn da kein neuer Leitherm entsteht, den ich noch nicht gesehen habe, bin ich auf der sicheren Seite.

Und hier ist es ja gerade so, dass sollte ich tatsächlich hier unten ankommen, was ich ja tue, dann habe ich ja alle kritischen Paare durchprobiert

und weiß, dass sie zu Null reduzieren. Okay, alles super.

Gut, also wir haben jetzt auch einen Algorithmus, der das tut und das wollen wir natürlich nicht selber machen.

Wir wollen natürlich das andere nicht damit beschäftigen und es gibt auch richtig gute Software dafür.

Da werdet ihr wahrscheinlich große Probleme haben, die zu schlagen erstmal.

Der Champ ist momentan wohl Singular, ein Computer-Algebra-System aus Kaiserslautern.

Wenn ihr also Gründerbasen berechnen wollt, ansonsten haben wir natürlich noch Cocoa, die sich damit ganz gut auskennen.

Maple wäre jetzt nicht die erste Wahl, obwohl sie auch besser geworden sind, Mathematika.

Und dann gibt es noch einige andere, also in diesem Fall würde ich euch, wenn euer Leben dadurch das abhängt, zu Singular warten.

Die besten Überlebenschancen. Cocoa würde dann besser werden, wenn ihr homogene Ideale habt, also wenn die Polynome alle gleichen Grad haben.

Da sieht es dann vielleicht anders aus, aber ansonsten ist Singular eine gute Chance.

Und wenn ihr Polynome-Systeme löst, in einem Computer-Algebra-System, dann passiert es oft, dass so eine Gründerbasenmaschine im Hintergrund stattet.

Das kriegt ihr gar nicht mit.

Also wir haben jetzt einen Algorithmus, der ist endlich, rechne ich es richtig aus.

Rechne ich eine richtig coole Menge aus.