Gleichungen in der universellen Algebra

Es ist verblüffend, welch großer Teil der Mathematik sich als das Lösen von Gleichungen verstehen lässt. Viele der großen Erkenntnisse der Naturwissenschaften bestehen in der Erfassung von Beobachtungen in einfachen Gleichungen. Das Lösen von Gleichungen lässt uns vieleVorgänge, etwa den Fall eines Körpers oder die Ausbreitung einer Krankheit, ohne Experimente in der Realität vorhersagen. Das Lösen von Gleichungen kann man aber auch verwenden, um geometrische Sätze zu beweisen: hier bestimmt man, welche Gleichungen ein die Behauptung widerlegendes Beispiel erfüllen müsste, und zeigt, dass diese Gleichungen keine Lösungen besitzen. Hier sind wir nicht so sehr an den konkreten Lösungen interessiert, sondern viel mehr daran, ob es eine Lösung gibt. Auch in vielen anderen Problemen kann man logisches Überlegen durch Lösen einer Gleichung ersetzen. Man rechnet dabei oft nicht mit Zahlen, sondern mit anderen Objekten wie etwa Wahrheitswerten und dazupassenden neuen Rechenoperationen: die Operation ODER, die falsch ODER wahr = wahr liefert, ist eine solche Rechenoperation, die beschreibt, dass die Behauptung Paris liegt in der Schweiz oder in Frankreich richtig ist. Wir wollen Gleichungen mit solchen neuen Rechenoperationen lösen. Ein naheliegender Lösungsansatz dazu ist, die Lösungen zu erraten oder alle möglichen Lösungen auszuprobieren. Wenn das auch bei Schularbeiten leider selten funktioniert, so ist es doch eine durchführbare Strategie, wenn man die Lösungen aus nur wenigen möglichen Werten auswählen kann. Während man für viele Rechenoperationen auch tatsächlich nichts Besseres weiß oder sogar beweisen kann, dass es vermutlich nichts viel Effizienteres als Durchprobieren gibt, kennt man für andere Operationen sehr viel schnellere Lösungsverfahren. Wir versuchen nun, für einige bekannte Rechenoperationen festzustellen, ob sie in die Klasse Gleichungsslösen damit ist ein Albtraum oder Gleichungslösen damit ist ganz einfach gehören. Oft besteht zwischen verschiedenen Gleichungen ein logischer Zusammenhang: jede Lösung der ersten Gleichung ist automatisch eine Lösung der zweiten, aber nie der dritten. Wir versuchen, solche Zusammenhänge aufzuspüren. Die Menge aller Lösungen einer Gleichung sind geometrische Objekte. Für neue Rechenoperationen ist es interessant zu wissen, wie diese Objekte aussehen. Eine recht kreative Art, eine Gleichung zu lösen, ist, eine Lösung nicht zu finden, sondern zu erfinden, etwa in der Form: Sei x nun eine Lösung von . Die Erfindung der komplexen Zahlen kann man genau so sehen: die imaginäre Einheit i ist einfach eine Zahl mit i*i = -1. Das funktioniert aber nicht immer: die Erfindung einer Lösung kann im Widerspruch zu den gegebenen Rechenoperationen und ihren Rechengesetzen stehen, richtet in anderen Fällen aber keinen oder weniger Schaden an. Für das vorliegende Projekt haben wir 17 konkrete Probleme über Gleichungen formuliert, die wir zu lösen versuchen werden.

Das Lösen von Gleichungen ist eines der grundlegenden Probleme der Algebra. Für manche Typen von Gleichungen gibt es Lösungsformeln, für andere wiederum effiziente Algorithmen, welche Lösungen finden. Dabei hängt die Schwierigkeit, Gleichungen zu lösen, sehr davon ab, welche Rechenoperationen in den Gleichungen auftreten. Wenn man etwa in den ganzen Zahlen nur die Addition und Subtraktion verwendet, so muss man nur lineare Gleichungssysteme lösen, für die es gute Lösungsverfahren gibt (etwa die Hermite-Zerlegung). Fügt man die Multiplikation dazu, ist das Problem, Gleichungen zu lösen, bereits so schwierig, dass es kein Lösungsverfahren mehr geben kann: Ein berühmtes Resultat aus dem Jahr 1972 von Yuri Matiyasevich sagt, dass es keinen Algorithmus gibt, der bestimmt, ob eine solche Gleichung eine Lösung in den ganzen Zahlen hat. In vielen Teilen der Mathematik, etwa in der Codierungstheorie oder in der Kryptologie, rechnet man nicht mit Zahlen, sondern mit nur endlich vielen Objekten, etwa mit 0 und 1 oder mit "wahr" und "falsch". Wenn wir aber nur in einem endlichen Vorrat von Möglichkeiten Lösungen suchen, so kann man einfach alle dieser Möglichkeiten durchprobieren. Leider ist auch das oft zu aufwändig: In einer Gleichung mit n Unbekannten, für die jeweils 2 Werte möglich sind, erhalten wir 2^n Lösungsmöglichkeiten; das sind schon für n=30 eine Milliarde von Kandidaten für Lösungen. In diesem Projekt konnten wir einige Umstände beschreiben, die es uns ermöglichen, wesentlich weniger Kandidaten zu testen. Wir konnten zeigen, dass für bestimmte Typen von Gleichungen folgende Aussagen gelten: "Wenn die Gleichung eine Lösung hat, so hat sie sehr viele Lösungen" und "In der Nähe eines jeden Punktes findet man eine Lösung". Beide Aussagen sind etwa in Polynomgleichungen über endlichen Körpern erfüllt. Somit findet man Lösungen entweder durch zufällige Wahl von Kandidaten für Lösungen: wenn es viele Lösungen gibt, wird dann bald eine Lösung unter den Kandidaten sein. Oder man grast die gesamte nähere Umgebung eines Punktes ab: wenn es eine Lösung gibt, so gibt es auch eine Lösung in der Nähe dieses Punktes. Anstatt Gleichungen zu lösen, kann man sich auch versuchen, logische Zusammenhänge zwischen Gleichungen zu finden, etwa in der Form, dass jede Lösung einer Gleichung auch Lösung einer anderen Gleichung ist. Für bestimmte algebraische Strukturen konnten wir zeigen, dass das Finden von solchen Zusammenhängen ebenso schwierig ist wie das Lösen von Gleichungssystemen. Im Zuge des Projekts haben die Projektmitglieder 4 eingeladene Plenarvorträge und 27 Vorträge auf internationalen Konferenzen oder anderen Universitäten gehalten. Die Ergebnisse dieses Projekts wurden in 13 Artikeln in Fachzeitschriften (darunter Journal of Algebra, International Journal of Algebra and Computation, Finite Fields and their Applications) und 8 Beiträgen zu Konferenzen (darunter das International Symposium on Theoretical Aspects of Computer Science (STACS) und die Konferenz Mathematical Foundations of Computer Science (MFCS)) veröffentlicht.