Microsoft-Forscher hilft beim Beweis einer 31 Jahre alten Vermutung

Seit 1995 steht eine Frage zur hochdimensionalen Geometrie zwischen Mathematikern und einer klaren Antwort darauf, wie Zufallswanderungen eine Verteilung erkunden. Die Kannan–Lovász–Simonovits-Vermutung fragt, ob bei einer breiten Klasse von Wahrscheinlichkeitsverteilungen der beste ebene Schnitt fast so wirksam ist wie der beste Schnitt beliebiger Form. Microsoft Research meldet nun, dass zwei Forscher sie bewiesen haben, darunter Xinzhi Zhang von der Gruppe für maschinelles Lernen und Optimierung: Die Lücke zwischen beiden Schnittarten bleibt unterhalb von einer festen Schranke, unabhängig von der Zahl der Dimensionen.

Ein ebener Schnitt ist ein Schnitt durch eine Form mit einer flachen Klinge, mathematisch eine Hyperebene. Für log-konkave Verteilungen, eine breite Familie von Wahrscheinlichkeitsverteilungen, sagt die Vermutung voraus, dass der beste ebene Schnitt vom besten Schnitt beliebiger Form nur um eine universelle Konstante abweicht, egal wie viele Dimensionen es gibt. Die Geometrie dieser Schnitte bestimmt, wie schnell eine Zufallswanderung die Verteilung erkunden kann. Deshalb steht das Problem im Zentrum des hochdimensionalen Samplings, also der Verfahren, die Zufallspunkte aus komplizierten Verteilungen ziehen.

Dass das Problem zentral ist, war lange bekannt, bevor es fiel. Das Mathematical Sciences Research Institute nannte es im Jahresbericht 2017/18 „eine zentrale offene Frage der hochdimensionalen konvexen Geometrie“, und das Simons Institute beschrieb es als „eines der wichtigsten offenen Probleme der konvexen Geometrie“. Das bis dahin beste bekannte Ergebnis, im Juli 2026 erzielt, ließ die Schranke mit wachsender Dimension langsam steigen. Die Autoren schärften es zunächst: In der am 1. Oktober 2026 veröffentlichten Fassung sank die Abhängigkeit von der Dimension auf den iterierten Logarithmus, eine Funktion, die sehr langsam, aber dennoch wächst. Die Vermutung war damit noch nicht gelöst.

Die letzten Schritte entstanden in einem ungewöhnlichen Arbeitsablauf. Die Autoren arbeiteten mit KI-Agenten in einem strukturierten, von Menschen gelenkten Verfahren und untersuchten mehr als 100 mögliche Ansätze, viele davon mit langwierigen Rechnungen mit Tensoren höherer Stufe. Einer davon führte zu einem neuen Kriterium, das zur Grundlage des Beweises wurde. Der entscheidende Schritt bestand darin, die gesamte rekursive Verfeinerung zu wiederholen, statt sie nur einmal anzuwenden. Diese Idee war von früheren Arbeiten der Autoren zu schnellen Algorithmen für die lineare Optimierung inspiriert. Sie zeigten, dass die kleinen Fehler, die in jeder Stufe entstehen, so schnell schrumpfen, dass ihre Summe durch eine universelle, von der Dimension unabhängige Konstante beschränkt bleibt. Die am 4. Oktober 2026 veröffentlichte Fassung vollendete den Beweis. Die Autoren sagen, KI-Werkzeuge hätten beim Erkunden, Herleiten und Prüfen geholfen, während die Forscher die Richtung vorgaben, die Ideen auswählten und die Argumentation überprüften.

Die Behauptung hat parallele Arbeiten ausgelöst. Am selben Tag, an dem das Microsoft-Team seinen vollständigen Beweis veröffentlichte, stellte eine separate Gruppe führender Fachleute einen eigenen, parallel entwickelten vollständigen Beweis ein und nannte die erste Microsoft-Fassung „den entscheidenden Schritt im Beweis“. Ein dritter Beweis, am selben Tag veröffentlicht, stützt sich auf eine eng verwandte Idee. Der Microsoft-Beitrag berichtet außerdem, dass mehrere unabhängige Forscher die Arbeit bestätigt haben und danach eine maschinell geprüfte formale Verifikation folgte. Ob die Arbeit bereits von einer Fachzeitschrift angenommen wurde, geht aus dem Beitrag nicht hervor.

Für Forscher, die Verfahren zum Sampling und zur Optimierung entwickeln und analysieren, liegt die Veränderung in den Garantien: Eine Schranke, die nicht mehr mit der Dimension wächst, ersetzt eine, die wuchs, wenn auch langsam. Der Beitrag stellt dies als Beseitigung eines großen theoretischen Hindernisses dar, das dem Verständnis der Effizienz randomisierter Algorithmen in Wissenschaft und Informatik im Weg stand. Einen Zeitpunkt für praktische Auswirkungen nennt er nicht, und er sagt nicht, ob sich das Ergebnis in schnellere Werkzeuge übersetzen lässt.