Stellen Sie sich zwölf Freunde mit unterschiedlichen Interessen vor, die sich für einen Quizabend in zwei gleich starke Teams aufteilen möchten. Zhang kennt sich hervorragend mit Geschichte und Geografie aus, Li ist sattelfest bei Popmusik und Filmen, und Wang glänzt bei Sport und Kochen. Um beide Teams in jedem Bereich ebenbürtig zu gestalten, gerät die Zusammenstellung rasch in eine Sackgasse: Sobald Zhang in Team A versetzt wird, um die Geschichtspunkte auszugleichen, schießt die Geografie-Kompetenz von Team A schlagartig nach oben, was das Gleichgewicht in der Geografie erneut zerstört.
Dilemmata dieser Art gehören in der Mathematik zur kombinatorischen Diskrepanztheorie (combinatorial discrepancy theory) – dem Forschungsfeld, das untersucht, wie Objekte mit mehreren Merkmalen so auf zwei Gruppen verteilt werden können, dass die Unterschiede zwischen den Gruppen minimal bleiben. Ob bei der ausgewogenen Aufteilung verschiedener Fahrzeugmodelle und Farben auf zwei Gebrauchtwagenhändler oder bei der Verteilung von Patienten in Behandlungs- und Placebogruppen im Rahmen klinischer Studien: Sobald mehrdimensionale Merkmale im Spiel sind, wächst die Komplexität mit der Anzahl der Merkmale drastisch an.
Seit Jahrzehnten suchen Mathematiker nach den theoretischen Grenzen dieser Gruppen-Imbalance. Im Herbst 2025 stellten die Informatiker Nikhil Bansal und Haotian Jiang einen neuartigen Algorithmus vor, der die seit fast 30 Jahren unveränderte Obergrenze der Diskrepanz erheblich reduzierte. Ihre Arbeit beweist, dass selbst bei riesigen Merkmalsmengen und enormen Populationen eine nahezu perfekte, ausgewogene Aufteilung möglich ist.
Warum die faire Aufteilung Mathematiker seit Jahrzehnten beschäftigt
Im Alltag ist das Aufteilen von Objekten mit nur einer Eigenschaft denkbar einfach. Wenn man 100 gleich große Kuchenstücke hat, führt eine Aufteilung in zwei Hälften zu je 50 Stücken zu perfekter Balance. In der Realität überschneiden sich bei den zu verteilenden Objekten jedoch fast immer mehrere Eigenschaften gleichzeitig.
Szenario Gebrauchtwagenhändler: Die im Großhandel verkauften Fahrzeuge besitzen unterschiedliche Farben, Modelltypen und Kilometerstände. Teilt man sie einfach nach der Gesamtzahl auf, erhält womöglich ein Händler die meisten Cabrios, während der andere überwiegend rote Limousinen bekommt. Beide Händler wünschen sich eine Parität über alle Kennzahlen hinweg, doch jede Eigenschaft zieht die Aufteilung in eine andere Richtung.
In medizinischen Studien sind diese Wechselwirkungen noch enger miteinander verwoben. Forscher müssen Probanden so in Behandlungs- und Kontrollgruppen aufteilen, dass nicht nur die Altersverteilung ähnlich ist, sondern auch Blutdruck, Vorerkrankungen und Lebensgewohnheiten im gleichen Verhältnis stehen. Eine schwere Imbalance in einer einzigen Dimension könnte die Aussagekraft der Studienergebnisse gefährden. Diese miteinander verflochtenen Merkmale bilden auf dem mathematischen Spielfeld ein äußerst kniffliges Tauziehen.
Eine einst als leichtsinnig abgetane mathematische Vermutung
Um die theoretischen Grenzen der Aufteilung zu klären, formulierte der ungarische Mathematiker János Komlós Anfang der 1980er Jahre die berühmte Komlós-Vermutung. Er vermutete, dass unabhängig von der Anzahl der Objekte und der Anzahl ihrer Merkmalssdimensionen immer eine Aufteilung existiert, bei der der maximale numerische Unterschied zwischen den beiden Gruppen über alle Merkmale hinweg (die Diskrepanz, discrepancy) eine feste Konstante nicht überschreitet.
Komlós selbst scherzte später, er habe diese Vermutung damals nur aus jugendlicher Unbekümmertheit gewagt. Da es damals an effektiven mathematischen Werkzeugen fehlte, war der Beweis einer von der Objektanzahl unabhängigen konstanten Schranke extrem schwierig; er bezeichnete seinen Vorschlag sogar als „unverantwortliche Vermutung“.
In den folgenden Jahrzehnten lieferte sich die Fachwelt einen langen mathematischen Staffellauf. 1985 bewies der Mathematiker Joel Spencer, dass die Diskrepanz innerhalb des Logarithmus log N der Objektanzahl N gehalten werden kann; 1998 verbesserte Wojciech Banaszczyk die Obergrenze weiter auf die Quadratwurzel von log N. Von da an stagnierte die Mathematik fast 30 Jahre lang vor diesem Rekord, und viele Wissenschaftler zweifelten daran, ob diese Grenze jemals wieder durchbrochen werden könnte.
Algorithmic Durchbruch nach einem einwöchigen Besuch
Die Wende kam im Februar 2025. Haotian Jiang, damals Doktorand an der University of Washington und heute an der University of Chicago tätig, besuchte den Informatiker Nikhil Bansal an der University of Michigan in Ann Arbor. Bansal hatte bereits 2010 einen Algorithmus entworfen, der einzelne Objekte aufteilte und durch zufällige Perturbationen neu zusammensetzte und damit Spencers log N-Rekord erreichte.
Bereits am zweiten Tag von Jiangs Besuch fanden die beiden in ihren Diskussionen einen völlig neuen Ansatzpunkt. Nach einem halben Jahr intensiver Herleitung und Verfeinerung stellten sie im Herbst 2025 ihren neuen Algorithmus offiziell vor. Sie drückten die Obergrenze der maximalen Gruppendiskrepanz auf die vierte Wurzel aus log N, also log(N)^(1/4). Dies war der erste theoretische Durchbruch in diesem Feld seit fast drei Jahrzehnten.
Abb.: Mathematische Konzeptskizze zu Vektor-Tauziehen und ausgewogener Aufteilung. Quelle: Quanta Magazine / Ada Zejun Shen
Abb.: Die beiden Forscher hinter dem Durchbruch bei der Komlós-Vermutung: Haotian Jiang (links) und Nikhil Bansal (rechts). Quelle: Quanta Magazine / Emily France, University of Michigan
Wie sich komplexe Attribute nicht mehr gegenseitig stören
Frühere Algorithmen konzentrierten sich bei der Aufteilung meist nur auf den kumulierten Endwert der globalen Imbalance. Bei einer hohen Anzahl von Attributen führte die Anpassung eines einzelnen Merkmals oft wie ein Schmetterlingseffekt zu einer heftigen Störung des Gleichgewichts anderer Merkmale.
Bansal und Jiang führten eine präzise Messung der „Abhängigkeit“ ein. Sie entwickelten einen Mechanismus, um zu bewerten, wie stark die zufällige Perturbation eines Attributs gekoppelte Abweichungen bei anderen Attributen auslöst.
Indem der Algorithmus die zufälligen Interferenzen zwischen den Attributen während der Berechnung isoliert, gelingt es ihm, jede Dimension unabhängig und ohne gegenseitige Störung feinjustieren zu lassen. Diese Konstruktion senkte nicht nur die theoretische Obergrenze auf die vierte Wurzel, sondern lieferte auch einen effizienten Algorithmus (efficient algorithm), der direkt in der Praxis eingesetzt und ausgeführt werden kann.
Selbst beim Aufteilen aller Atome im Universum beträgt die Differenz nur 3
Die vierte Wurzel aus log N mag in mathematischen Formeln etwas abstrakt klingen, doch überträgt man sie auf reale Größenordnungen, wird die anschauliche Wirkung des Ergebnisses sofort deutlich.
Bei einer Objektanzahl von N = 10 liegt der Wert der vierten Logarithmuswurzel etwa bei 1. Erhöht man die Anzahl der zu verteilenden Objekte auf die geschätzte Gesamtzahl aller Atome im beobachtbaren Universum – etwa 10^81 (eine 1 mit 81 Nullen) –, steigt die nach dieser Formel berechnete maximale Diskrepanz lediglich auf etwa 3 an.
Der Yale-Mathematiker Daniel Spielman bemerkte dazu, dass man in einem Menschenleben wohl kaum je einer vierten Wurzel aus einem Logarithmus begegnen werde, die den Wert 5 überschreite. Das bedeutet: Selbst wenn das Datenvolumen auf astronomische Dimensionen anwächst, bleibt das Ausmaß der Gruppen-Imbalance nahezu unverändert und bewegt sich unendlich nahe an einer Konstanten.
Aleksandar Nikolov, Forscher an der University of Toronto, gestand, dass er früher eher dazu neigte zu glauben, die Komlós-Vermutung sei falsch. Das neue Ergebnis habe ihn jedoch wieder davon überzeugt, dass die Vermutung höchstwahrscheinlich wahr sei. Rainie Heck, Forscherin am Rényi-Institut in Ungarn, wies zudem darauf hin, dass diese Theorie bereits bei der Optimierung großer Sprachmodelle und Systeme des maschinellen Lernens eingesetzt werde und es gut möglich sei, dass bald jemand die Existenz einer konstanten Schranke vollständig beweisen werde.
Nahezu perfekte Fairness ist greifbar nahe
Dinge mit unzähligen komplexen Merkmalen mit absoluter, fehlerfreier Fairness aufzuteilen, stößt an mathematische Grenzen. Der Durchbruch von Bansal und Jiang beweist jedoch, dass eine nahezu perfekte Balance nicht nur theoretisch machbar ist, sondern auch rechnerisch effizient umgesetzt werden kann.
Von der vor 40 Jahren scheinbar leichtsinnigen mathematischen Vermutung bis zur 30 Jahre lang unüberwindbaren Wurzel-Mauer haben Mathematiker die theoretischen Grenzen der Imbalance Schritt für Schritt verschoben. Mit einem eleganten Algorithmus haben sie gezeigt, dass der menschliche Geist selbst in einer überaus komplexen Welt die Kraft besitzt, Ordnung aus dem Chaos zu schaffen.
Referenzlinks:
- Quanta Magazine Bericht
