Die Suche nach echtem Zufall in der Mathematik

Zahlentheorie. Dem Wiener Mathematiker Clemens Müllner gelang es, einen Spezialfall der sogenannten SarnakVermutung zu beweisen, die sich mit Primzahlen beschäftigt. Das ist wichtig für Verschlüsselungsverfahren.

Die Jagd nach Beweisen in der Zahlentheorie hat der Mathematik einige ihrer spannendsten und unterhaltsamsten Anekdoten beschert. Am bekanntesten ist die Suche nach dem Beweis für die Fermat-Vermutung, eine Verallgemeinerung des Satzes von Pythagoras. Sie beschäftigte Generationen von Mathematikern, bis Andrew Wiles fast 400 Jahre später nach siebenjähriger Arbeit im Alleingang den Beweis erbrachte. Fermat selbst hatte seine Vermutung am Seitenrand eines Buches notiert und behauptet, einen Beweis zu besitzen, eine Geschichte, die im Weltbestseller „Fermats letzter Satz“erzählt wird. Andere bekannte Probleme wie die Goldbach-Vermutung sind nach wie vor offen, obwohl für den Beweis Letzterer schon ein Preisgeld von einer Million Dollar ausgeschrieben war.

Der Reiz dieser Problemstellungen liegt darin, dass sie oft verhältnismäßig einfach zu erklären, aber in vielen Fällen ausgesprochen schwierig zu beweisen sind. Eine solche Vermutung aus der Zahlentheorie ist die Sarnak-Vermutung. Der Beweis eines wichtigen Spezialfalls dieser Vermutung gelang nun dem Mathematiker Clemens Müllner vom Institut für Diskrete Mathematik und Geometrie der TU Wien. Die Sarnak-Vermutung dreht sich um die sogenannte Möbius-Funktion, benannt nach dem deutschen Mathematiker.

Drei Werte für eine Funktion

Jede natürliche Zahl lässt sich als Produkt von Zahlen darstellen, die nicht weiter teilbar sind, den Primzahlen. Die Zahl sechs ist zum Beispiel ein Produkt der Primzahlen zwei und drei. Manche Zahlen sind das Produkt einer geraden, manche das einer ungeraden Anzahl von Primzahlen. Einige Zahlen enthalten lauter unterschiedliche Primzahlen, bei anderen kommen einige Primzahlen doppelt vor. Die Möbius-Funktion kann drei Werte annehmen: eins, wenn die Anzahl der Primzahlen gerade ist, minus eins, wenn ihre Anzahl ungerade ist, und null, wenn Primzahlen doppelt vorkommen. Für die sechs ist die Möbius-Funktion also eins.

Die Sarnak-Vermutung besagt, dass die Möbius-Funktion zufällig ist. Das sagt etwas über die Primfaktorenzerlegung, also die Zerlegung von Zahlen in Primzahlen, aus und ist von praktischer Relevanz: So gut wie alle gängigen Verschlüsselungsverfahren beruhen darauf, dass Primfaktorenzerlegung für große Zahlen enorm aufwendig ist. Gäbe es einfache Lösungen, wäre Verschlüsselung nicht mehr sicher.

Müllners Forschungsinteresse gilt Folgen von Zahlen, die mit sogenannten Automaten konstruiert werden, das sind imaginäre Maschinen aus der theoretischen Informatik, ähnlich der bekannteren Turingmaschine, die ein Modell für einen Computer darstellt. „Ursprünglich haben wir Teilfolgen von automatischen Folgen studiert“, sagt Müllner. Das sind Folgen, die von Automaten generiert werden können. „Im Zuge dessen habe ich eine neue Struktur für Automaten und automatische Folgen gefunden.“Müllner konnte nun zeigen, dass die MöbiusFunktion nicht durch Folgen angenähert werden kann, die aus solchen Automaten stammen. Salopp gesagt: Maschinen können keine einfachen Lösungen für die Primfaktorenzerlegung liefern. Genau so, wie man es sich für Verschlüsselungsverfahren wünscht.

Die Arbeiten fanden im Rahmen eines Spezialforschungsbereichs für Quasi-Monte-Carlo-Methoden statt (siehe Beitrag oben). „In diesem Bereich braucht man annähernd zufällige Folgen. Über automatische Folgen lassen sich solche sehr schnell und einfach erzeugen. Die Anwendung auf die Sarnak-Vermutung war dann ganz natürlich“, sagt Müllner.

„In der mathematischen Community ist das sehr gut angenommen worden. Die Sarnak-Vermutung ist eine sehr tief gehende Vermutung mit Anwendungen auf Zahlentheorie und dynamische Systeme“, sagt der Forscher. Nach einem allgemeinen Beweis für die Sarnak-Vermutung wird nach wie vor gesucht. (rk)