Forschende aus Paderborn und Leuven rückten die Dedekind-Zahlen in ihren Fokus.
Universitaet Paderborn/Besim Mazhiqi

Mathematik sorgt manchmal für einen alternativen Blickwinkel auf bekannte Dinge und bringt so eine eigene Form von Humor hervor. Ein Beispiel ist der Witz von dem Mathematiker, der gefragt wird, ob er gern Wein oder Bier haben möchte, und darauf mit "Ja" antwortet.

Die überraschende (und in der Praxis vermutlich eher nervtötende) Antwort hat mit einem Bereich der Mathematik zu tun, der sich nicht mit Zahlen, sondern mit dem Wahrheitsgehalt von Aussagen beschäftigt. "Wahr" und "falsch" lassen sich in gewissem Sinn wie die Zahlen Null und Eins verwenden, während ein "und" einer Multiplikation ähnelt, ein "oder" einer Addition und ein "nicht" einem Minus. Das daraus entstehende mathematische Konstrukt wird Boolesche Algebra genannt.

Wer bei null und eins, wahr und falsch an Computer denkt, liegt goldrichtig: Wenn Computer logische Schlüsse ziehen, agieren sie nach denselben Regeln.

Boolesche Funktionen wiederum sind Formeln innerhalb dieses Systems, die als Ganzes wahr oder falsch sein können. Darauf bezieht sich der eingangs zitierte Witz: Die Aussage, dass der an der Theke stehende Mathematiker Wein oder Bier möchte, ist wahr. Ein "Ja" ist deshalb die richtige Antwort.

Boolesche Funktionen zählen

Auch der berühmte deutsche Mathematiker Richard Dedekind beschäftigte sich mit dem Thema. Dedekind ist Schülerinnen und Schülern durch den Dedekindschen Schnitt ein Begriff, der hilft, die Reellen Zahlen zu definieren. Der deutsche Mathematiker war aber auch der Erste, der erklärte, was natürliche Zahlen eigentlich genau sind. (Wer Zahlen noch nie einfach und selbstverständlich fand, kann in diesen Grundlagenuntersuchungen der Mathematik Trost finden. Vieles an Zahlen ist alles andere als selbstverständlich.) Dedekind, Jahrgang 1831 und Mitglied einer schlagenden Burschenschaft, beschäftigte sich auch mit Booleschen Funktionen und stellte sich irgendwann die Frage, wie viele es davon gibt.

Konkret interessierte er sich für Boolesche Funktionen, die ohne Verneinungen auskommen. Dedekind fand, dass ihre Anzahl in Abhängigkeit von der Zahl der Variablen (im obigen Beispiel die Zahl der alkoholischen Getränke, die zur Auswahl stehen) sehr schnell ansteigt. Während es etwa 20 Funktionen mit drei Variablen gibt, sind es bei fünf Variablen bereits 7.581 und bei sieben Variablen 2.414.682.040.998. Für das Problem, das Dedekind 1897 formulierte, gibt es immer noch keine einfache Formel. Die Zahlen werden Dedekind-Zahlen genannt, und bislang war die letzte bekannte jene mit der Nummer acht, eine Zahl mit 23 Stellen.

Eine Darstellung der Dedekind-Zahlen 0, 1, 2 und 3.
Gemeinfrei

Sie wurde 1991 gefunden, allerdings nicht von Hand, sondern mit dem damals leistungsfähigsten Supercomputer, einem Cray 2. Doch seither stockte die Suche, die Dedekind-Zahl mit der Nummer neun ließ auf sich warten.

Bis ein Team von Forschenden der Universitäten Paderborn und Leuven die Suche erneut in Angriff nahm in der Hoffnung, dass heutige Supercomputer der Aufgabe inzwischen gewachsen sein könnten.

Um die Zahl zu finden, wäre es möglich gewesen, einfach alle denkbaren Booleschen Funktionen mit neun Stellen eine nach der anderen durchzuzählen. Doch der Aufwand dafür wäre astronomisch gewesen.

Tatsächlich gibt es eine einfachere Lösung, die sich dem Problem über eine sehr große Summenformel annähert. Mit diesem Trick ist etwa die Berechnung der bereits bekannten achten Dedekind-Zahl auf einem gewöhnlichen Laptop innerhalb weniger Minuten möglich. Doch die Berechnung der neunten Zahl würde auch so viele tausend Jahre dauern.

Durch das Ausnutzen einiger Symmetrieeigenschaften der Formel gelang es dem Team, die Zahl der Rechenschritte auf etwa fünf Trillionen zu reduzieren. Das sei immer noch eine stattliche Anzahl, vergleichbar mit der Anzahl aller Sandkörner auf der Erde, sagt Studienautor Lennart Van Hirtum, der das Projekt als Masterarbeit begann. Für einen Supercomputer sei so etwas aber zu schaffen, betont er.

Spezieller Computer nötig

Es gab allerdings ein anderes Problem: Moderne Supercomputer bestehen zu einem großen Teil nicht aus konventionellen Prozessorkernen, wie sie in unseren PCs sitzen, sondern aus sogenannten GPUs, die eigentlich zur schnellen Berechnung der Grafik von Videospielen entwickelt wurden. Auch zum Schürfen von Bitcoins eignen sie sich hervorragend, was vor einigen Jahren dazu führte, dass diese Komponenten kaum zu bekommen waren.

Auch bei Supercomputern sind GPUs beliebt. Wer im Ranking der schnellsten Supercomputer einen Spitzenplatz einnehmen will, kommt um eine große Anzahl dieser Grafikprozessoren nicht herum. Doch ausgerechnet zur Berechnung der nächsten Dedekind-Zahl sind sie äußerst ungeeignet. Es gibt jedoch eine andere Prozessorarchitektur, die genau auf Probleme wie dieses ausgelegt ist, sogenannte FPGAs, kurz für "Field programmable gate array". Die Übersetzung des Ausdrucks ist wenig erhellend, entscheidend ist, dass ihre logische Struktur flexibel programmiert werden kann und sie sich perfekt zur Berechnung von Dedekind-Zahlen eignen.

Das Team machte sich auf die Suche nach einem Supercomputer, der über eine ausreichende Anzahl solcher Prozessoren verfügte, und wurde fündig. Zum Einsatz kam der Supercomputer Nocuta 2 des Paderborn Center for Parallel Computing, kurz PC2.

Etwa fünf Monate dauerte die Berechnung. Am 8. März spuckte der Rechner ein Ergebnis aus. Es lautete 286.386.577.668.298.411.128.469.151.667.598.498.812.366, eine Zahl mit 42 Stellen. Ob es sich um die neunte oder die zehnte Zahl handelt, ist dabei Interpretationssache. Die Zählung beginnt eigentlich bei null.

Im September soll das Ergebnis bei einer Tagung zu Booleschen Funktionen in Norwegen präsentiert werden. Für den jungen Lennart Van Hirtum, der am Paderborner Center for Parallel Computing an seiner Dissertation arbeitet, wird es ein großer Auftritt sein. Ein über dreißig Jahre altes mathematisches Rätsel, dessen Anfänge ins 19. Jahrhundert zurückreichen, löst man nicht alle Tage. (Reinhard Kleindl, 30.6.2023)