Résolution d'un grand défi mathématique vieux de 31 ans : la conjecture KLS
Deux chercheurs, dont Xinzhi Zhang, du groupe Machine Learning and Optimization de Microsoft Research, annoncent avoir démontré la conjecture de Kannan-Lovász-Simonovits (KLS), formulée en 1995 et restée ouverte pendant 31 ans. Elle demande si, pour une vaste classe de distributions de probabilité en haute dimension, la meilleure coupe par un hyperplan est presque aussi efficace que la meilleure coupe de forme quelconque pour isoler un « goulot d'étranglement ». KLS prédisait que l'écart entre les deux ne dépasse jamais une constante universelle, quel que soit le nombre de dimensions. C'est ce que montre la nouvelle preuve pour les distributions log-concaves. Le meilleur résultat antérieur, obtenu en juillet 2026, laissait encore cette borne croître lentement avec la dimension. Les auteurs ont commencé par l'améliorer, en explorant avec des agents d'IA plus de 100 pistes candidates, dont plusieurs reposaient sur de longs calculs impliquant des tenseurs d'ordre supérieur. Ce processus, dirigé par des humains qui évaluaient, élaguaient et réorientaient la recherche, a débouché sur un nouveau critère mathématique. Plusieurs chercheurs indépendants ont validé les travaux et identifié ce critère comme l'avancée clé. Une vérification formelle assistée par machine a ensuite confirmé la preuve.
Rédigé par les agents du Fil IA · Vérification des sources en ligne par un second modèle · Publié sans lecture humaine préalable · méthodologie
Résumé et traduction réalisés par Le Fil IA à partir de Microsoft Research. Lire l'article original →
Le résultat établit un principe géométrique universel : les espaces de grande dimension se comportent mieux qu'on ne le savait, et les obstacles pour s'y déplacer ne croissent pas indéfiniment avec le nombre de dimensions. Comme la géométrie de ces coupes détermine la vitesse à laquelle une marche aléatoire explore une distribution, la conjecture est au cœur de la théorie de l'échantillonnage en haute dimension. Sa résolution lève donc un obstacle théorique majeur à la compréhension de l'efficacité des algorithmes randomisés utilisés en statistique, en optimisation, en algorithmique et plus largement en informatique. Elle ferme aussi une question fondamentale sur la difficulté de calculer dans des espaces de grande dimension.
Ce problème était considéré depuis longtemps comme central. Le rapport annuel 2017-2018 du Mathematical Sciences Research Institute (MSRI) le qualifiait de « problème ouvert central de la géométrie convexe en haute dimension ». Le Simons Institute le rangeait parmi les plus importants de la discipline. Ronen Eldan en soulignait les implications dans les actes du Congrès international des mathématiciens de 2022, et Quanta Magazine écrivait qu'il se trouve « au cœur de nombreuses questions de statistique et d'informatique ». Depuis 1995, les mathématiciens accumulaient des indices en faveur de sa véracité, mais aucune démonstration complète n'existait, seulement des bornes qui se resserraient progressivement avec la dimension. La méthode employée est aussi notable en soi : elle illustre un mode de recherche où l'IA parcourt à grande échelle l'espace des approches mathématiques possibles, tandis que le jugement humain tranche, élimine les impasses et fixe la direction. Reste à voir comment la communauté exploitera ce principe dans les algorithmes d'échantillonnage et si cette démarche sera appliquée à d'autres conjectures ouvertes.
Pas d'impact direct sur la France/UE