Ein einheitlicher Zugang zu Gleichungslogik und Klonen

In vielen Fachdisziplinen begegnen wir formalen Ausdrücken: H2O in der Chemie, www.jku.at in der Informatik, mv2 in der Physik, oder x(y + 2) in der Mathematik. Die letzten beiden Ausdrücke sind Terme; sie ergeben nach Belegung der Variablen einen Wert. Sehr oft sind die Objekte, die man einsetzt und mit denen man rechnet, einfach Zahlen. Für die Modellierung vieler in der realen Welt auftretenden Phänomene muss man aber auch mit anderen Objekten als mit Zahlen rechnen: Vektoren stellen Punkte im Raum dar, Matrizen können Bewegungen der Punkte modellieren, und Funktionen eine über einen ganzen Zeitraum beobachtete Größe beschreiben. Viele Taschenrechner rechnen heute ganz selbstverständlich nicht nur mit Zahlen, sondern auch mit Buchstaben und rechnen so in einer algebraischen Struktur, die man Körper der rationalen Funktionen nennt. Die Wissenschaftsdisziplin Algebra beschäftigt sich mit all diesen Arten, mit den unterschiedlichsten Objekten zu rechnen; das Teilgebiet der universellen Algebra wagt einen gemeinsamen Blick auf alle denkbaren Rechenmöglichkeiten. In dieser Disziplin begegnen uns Terme, wie etwa x 2 - y2, in zwei Rollen. Sie stellen zum einen eine von x und y abhängige Größe dar, zum anderen sind sie aber auch Teile von logischen Aussagen wie etwa (x+y)(x-y) = x2 - y2. Diese beiden Rollen von Termen werden in zwei zentralen Gebieten der universellen Algebra studiert, der Theorie der Funktionenalgebren oder Klone1 und der Gleichungslogik. Die Klontheorie beschäftigt sich mit der Frage, welche Funktionen man aus gegebenen aufbauen kann. So kann etwa aus Schaltgattern für die Funktionen und und nicht jedes beliebige Schaltverhalten zusammengebaut werden; die Konjunktionen oder und nicht erlauben jeden aussagenlogischen Zusammenhang darzustellen, etwa auch wenn A, dann B als (nicht A) oder B. Welche Funktionen man aus gegebenen aufbauen kann, kann man durch Angabe bestimmter Eigenschaften der zusammengebauten Funktionen beschreiben. Das zweite Gebiet, die Gleichungslogik, beschäftigt sich mit den für die Operationen gültigen Rechenregeln, wie etwa dem Distributivgesetz. Sowohl in der Gleichungslogik als auch in der Klontheorie gibt es Endlichkeitsresultate; so lassen sich zum Beispiel manchmal alle in einer Klasse algebraischer Strukturen geltenden Rechengesetze aus einigen wenigen folgern. Zwei solche Endlichkeitsresultate haben die Autoren in den letzten Jahren bewiesen; erstaunlicherweise ließen sich hier die Klontheorie und die Gleichungslogik in ganz ähnlicher Weise behandeln. Ziel dieses Projekts ist es, die dort beobachtete Parallelität zu untersuchen, und so einen neuen breiten Informationsfluss zwischen diesen beiden Gebieten einzuleiten. Unter diesem Gesichtspunkt sollen folgende Fragestellungen bearbeitet werden: Welche Eigenschaften von Algebren können dadurch beschrieben werden, dass diese Algebren ganz bestimmte, endlich viele, Muster vermeiden? Gelingt die Übersetzung zwischen der relationalen und funktionalen Darstellung eines Klones deswegen bis jetzt nicht, weil das Problem algorithmisch unlösbar ist? Wie lang sind die Ausdrücke, die man braucht, um bestimmte Funktionen darzustellen? Um diese Fragen zu beantworten, sollen einerseits theoretische Hilfsmittel, wie etwa die Kommutatortheorie, weiterentwickelt und andererseits die Parallelität beider Gebiete präziser gefasst werden. 1 Das Wort Klon ist vermutlich ein Kunstwort, das aus dem englischen clone für the closed one gewonnen wurde.

Klonoide: ein einheitlicher Zugang zu Gleichungslogik und Klonen Welche logischen Schaltungen können gebaut werden, wenn man nur UND und ODER-Gatter (aber keine NICHT-Gatter) verwenden darf? Warum kann man lineare Gleichungen schneller lösen als nichtlineare? Welche Funktionen kann man aus Addition und Quadrieren zusammenbauen? Alle diese Fragen kann man dadurch algebraisch behandeln, dass man verschiedene Funktionen in einer algebraischen Struktur zusammenfasst. Solche Strukturen sind etwa Fastringe, Klone, oder, wenn die Funktionen von einem Bereich in einen anderen abbilden, Klonoide. Diese Klonoide wurden erstmals 2014 verwendet, um algebraische Methoden zur Lösung eines Problems der Gleichungslogik verwenden zu können, aber bisher noch kaum systematisch untersucht. In vorliegenden Projekt wurden etwa alle Klonoide zwischen einfachen abelschen Gruppen bestimmt. Dazu wurde die Darstellung von Funktionen durch Polynome untersucht. Um Funktionen als Polynome darstellen zu können, wurde eine Koordinatisierung algebraischer Strukturen entwickelt; dabei gibt man jedem Element der algebraischen Struktur einen Namen, der aus einer anderen, besser bekannten, Struktur kommt, und rechnet mit diesen Namen. Diese Koordinatisierung ergibt für manche Rechenstrukturen die schnellste bekannte Möglichkeit, Gleichungen zu lösen. Die Lösungsmengen von Gleichungen hängen natürlich davon ab, wie kompliziert die in ihnen vorkommenden Funktionen sind. Ein Maß für die Komplexität ist der Grad der Funktionen, den wir in diesem Projekt genauer untersucht haben. Unsere Arbeit über den Zusammenhang von Grad und Lösungsmenge wurde im renommierten Journal of Algebra veröffentlicht. Klonoide bieten auch eine neuen Zugang zur Universellen Algebraischen Geometrie, die sich mit der Form von Lösungsmengen von Gleichungen beschäftigt. Wir konnten Klonoide verwenden, um zu zeigen, dass die Geometrie einer Algebra sehr oft schon durch die Form sehr niedrigdimensionaler Lösungsmengen bestimmt ist. Als Teilstrukturen von Klonen geben Klonoide auch einen Einblick in möglichen Erweiterungen gegebener Algebren. In vielen Fragen in diesem Gebiet geht es darum, welche Funktionen sich aus gegebenen zusammensetzen lassen. Ein beachtenswertes Resultat aus dem vorliegenden Projekt beschreibt etwa, welche Polynome man aus x durch Quadrieren und Addieren erhält - interessanterweise lässt sich eine Potenz x^i desto besser zusammenbauen, je niedriger die Ziffernsumme von i in Binärdarstellung ist.