Gewichtete-homogene Struktur in Polynomgleichungen

Das Lösen von Gleichungen ist seit jeher ein Leitproblem der Mathematik, das in vielen Anwendungen auftaucht. Die Art der Gleichungen und die Werkzeuge, die zu ihrer Lösung verwendet werden, hängen jedoch von der Anwendung ab. Zum Beispiel bilden lineare Gleichungen die mathematische Grundlage von Suchmaschinen und künstlicher Intelligenz. Eine allgemeinere Klasse von Gleichungen ist die Klasse der Polynomgleichungen. Solche Gleichungen modellieren unter anderem Fragestellungen in Physik und Ingenieurwesen und kommen in verschiedenen Bereichen der Mathematik vor. Es wurden verschiedene Algorithmen vorgeschlagen und implementiert, um sie zu lösen. Um die Komplexität dieser Algorithmen besser zu verstehen, haben Mathematiker Eigenschaften von Systemen untersucht, die zu dem einen oder anderen Verhalten führen. Eine wichtige Errungenschaft war der Anfang der 2000er Jahre abgeschlossene Beweis, dass die Lösung eines Zufallssystems mit endlich vielen Lösungen Zeit benötigt, die polynomial zur Anzahl der Lösungen ist. Der Hauptbestandteil des Beweises ist die Beobachtung, dass zufällige Systeme Regelmäßigkeitseigenschaften erfüllen. Andererseits sind Systeme, die in Anwendungen auftreten, keine Zufallssysteme, und tatsächlich erfüllen sie häufig nicht die notwendigen Regularitätseigenschaften. Um diese Ergebnisse zu verallgemeinern, haben sich Forscher auf spezifische strukturelle Eigenschaften von Systemen von Polynomgleichung konzentriert um Regularitätseigenschaften auf Systeme mit spezifischen Strukturen zu verallgemeinern. Ein Beispiel für diese Strukturen ist die Klasse der gewichtet- homogenen Systeme. Solche Systeme kommen in verschiedenen Kontexten vor, zum Beispiel in der Physik oder der Kryptographie. Frühere Ergebnisse zeigen, wie man ein gewichtetes homogenes System "regularisieren" kann, wenn alle Gewichte positiv sind, um eine Komplexität zu erhalten, die polynomiell in der Anzahl der Lösungen ist. Dieses Projekt zielt darauf ab, diese Resultate zu verallgemeinern, und zwar dadurch, dass Gewichte auch Null oder negativ sein können, und durch die Betrachtung von Systemen, die gewichtet-homogen für mehrere Systeme von Gewichten sind. Das Ziel ist es, angepasste Regularisierungstechniken für solche Systeme zu entwerfen, dedizierte Algorithmen zu deren Lösung zu entwerfen und zu implementieren und deren Komplexität zu begrenzen. Über unmittelbare Anwendungen zur Lösung solcher Systeme hinaus schlagen wir vor, solche verallgemeinerten gewichtet-homogenen Strukturen zur Modellierung von Systemen zu verwenden, die bei der Eliminierung von Unbekannten aus einem System von Polynomgleichungen verwendet werden. Das Ziel dabei ist, bessere Komplexitätsschranken für diese Operation zu erhalten, die grundlegend für viele andere Algorithmen ist.

Ziel des Projekts war die Untersuchung von Algorithmen zur Lösung von Systemen mit unterschiedlichen Strukturen, indem den Variablen unterschiedliche Gewichte zugewiesen werden, sowie von Algorithmen zur Vereinfachung von Systemen mit polynomialen Gleichungen durch Eliminierung von Variablen. In einem ersten Schritt untersuchten wir die algebraischen Eigenschaften einer Klasse von strukturierten Systemen und schlugen verschiedene Algorithmen zu ihrer Lösung vor, die einige Hypothesen über die Struktur berücksichtigen. Anders als in den klassischen Fällen sind diese Algorithmen nicht gleichwertig. Zur Untersuchung der Komplexität schlugen wir verschiedene Charakterisierungen des Verhaltens generischer Systeme vor und untersuchten ihre Unterschiede und Grenzen. Unter einigen dieser Hypothesen konnten wir erste Komplexitätsergebnisse erzielen. Diese Ergebnisse reichten jedoch nicht aus, um einen neuen Ansatz für die Polynomeliminierung vorzuschlagen. Stattdessen konzentrierten wir unsere Bemühungen auf einige Situationen, in denen bestehende Algorithmen nicht in der Lage sind, die Eliminierung durchzuführen. Eine dieser Situationen ist die Verwendung so genannter Signatur-Gröbner-Basen beim automatischen Theorembeweisen. Bisherige Algorithmen zur Berechnung von Signatur-Gröbner-Basen hatten in diesem Fall Einschränkungen, die eine Eliminierung unmöglich machten. Dies wiederum schränkte den Anwendungsbereich dieser Algorithmen erheblich ein. Wir haben die Algorithmen verallgemeinert, um mehr Gleichungstypen zu berücksichtigen und diese Einschränkungen aufzuheben, so dass nun eine polynomielle Eliminierung möglich ist. In einer separaten Arbeit zu diesem Thema haben wir auch einen Optimierungsalgorithmus entwickelt, um kürzere Beweise für Beziehungen zu finden. Eine weitere Situation, in der eine Eliminierung unmöglich ist, ist der Fall der so genannten Tate-Reihen. Dabei handelt es sich um Objekte aus der Zahlentheorie, bei denen es aufgrund der Eigenschaften dieser Reihen unmöglich ist, die Eliminierung mit der üblichen Methode der Eliminationsreihen durchzuführen. Wir haben jedoch bewiesen, dass es in der Praxis möglich ist, eine gültige Ordnung zu finden, die zu den gleichen Ergebnissen führt wie eine Eliminationsordnung. Dies geschieht durch eine Annäherung an eine Eliminationsreihenfolge, indem Variablen, die eigentlich null Gewicht haben sollten, ein kleines Gewicht zugewiesen wird. Wir haben diese Studie dann fortgesetzt, indem wir einen Algorithmus für die Auflistung aller möglichen gewichteten Ordnungen für ein gegebenes System angegeben haben und dabei eine so genannte "tropische Vielfalt" berechnet haben. Über die geometrischen und zahlentheoretischen Anwendungen dieser Berechnungen hinaus kann diese Studie als ein erster Schritt zur Erforschung guter Gewichtungssysteme für Systeme betrachtet werden, für die es keine offensichtliche gewichtete Struktur gibt.