Microsoft contribue à prouver une conjecture de géométrie vieille de 31 ans

Depuis 1995, une question de géométrie en grande dimension se dresse entre les mathématiciens et une réponse claire sur la façon dont les marches aléatoires explorent une distribution. La conjecture de Kannan–Lovász–Simonovits demande si, pour une large classe de distributions de probabilité, la meilleure coupe plane est presque aussi efficace que la meilleure coupe de forme quelconque. Microsoft Research annonce maintenant que deux chercheurs, dont Xinzhi Zhang, de son groupe d'apprentissage automatique et d'optimisation, l'ont démontrée : l'écart entre les deux types de coupe reste inférieur à une borne fixe, quel que soit le nombre de dimensions.

Une coupe plane est une section d'une forme réalisée avec une lame plane, un hyperplan en termes mathématiques. Pour les distributions log-concaves, une large famille de distributions de probabilité, la conjecture prédit que la meilleure coupe plane ne diffère de la meilleure coupe de forme quelconque que d'une constante universelle, quel que soit le nombre de dimensions. La géométrie de ces coupes détermine la vitesse à laquelle une marche aléatoire peut explorer la distribution, ce qui place le problème au cœur de l'échantillonnage en grande dimension, c'est-à-dire de la famille de méthodes qui tirent des points aléatoires dans des distributions complexes.

Le problème était reconnu comme central bien avant d'être résolu. L'Institut de recherche en sciences mathématiques l'a qualifié de « problème ouvert central de la géométrie convexe en grande dimension » dans son rapport annuel 2017-2018, et l'Institut Simons le décrit comme « l'un des problèmes ouverts les plus importants de la géométrie convexe ». Le meilleur résultat connu, établi en juillet 2026, laissait la borne croître lentement avec le nombre de dimensions. Les auteurs l'ont d'abord affinée : dans la version publiée le 1er octobre 2026, la dépendance vis-à-vis de la dimension tombait au logarithme itéré, une fonction qui croît très lentement mais croît encore, si bien que la conjecture n'était pas encore résolue.

Les dernières étapes sont venues d'un processus inhabituel. En travaillant avec des agents d'IA dans un cadre structuré et dirigé par des humains, les auteurs ont exploré plus de 100 approches candidates, dont beaucoup impliquaient de longs calculs avec des tenseurs d'ordre supérieur. L'une d'elles a produit un nouveau critère devenu le fondement de la preuve. Le dernier pas a consisté à répéter tout le raffinement récursif plutôt que de l'appliquer une seule fois, une idée inspirée de leurs travaux antérieurs sur les algorithmes rapides de programmation linéaire. Ils ont montré que les petites erreurs introduites à chaque étape diminuent assez vite pour que leur total reste borné par une constante universelle, indépendante de la dimension. La version publiée le 4 octobre 2026 a achevé la preuve. Les auteurs affirment que les outils d'IA ont aidé à explorer, à dériver et à vérifier, tandis que les chercheurs ont choisi la direction, sélectionné les idées et vérifié l'argumentation.

L'affirmation a suscité des travaux parallèles. Le jour même où l'équipe de Microsoft a publié sa preuve complète, un groupe distinct d'experts de premier plan a publié une preuve complète élaborée en parallèle, qualifiant la première version de Microsoft de « l'étape cruciale de la preuve ». Une troisième preuve, publiée ce jour-là, repose sur une idée très proche. La publication de Microsoft indique aussi que plusieurs chercheurs indépendants ont validé le travail et qu'une vérification formelle assistée par machine a suivi. Elle ne précise pas si l'article a déjà été accepté par une revue.

Pour les chercheurs qui conçoivent et analysent des méthodes d'échantillonnage et d'optimisation, le changement porte sur les garanties : une borne qui ne croît plus avec la dimension remplace une borne qui croissait, même lentement. La publication présente cela comme la levée d'un obstacle théorique majeur pour comprendre l'efficacité des algorithmes randomisés utilisés dans les sciences et l'informatique. Elle ne fixe aucune échéance pour un effet pratique et ne dit pas si le résultat se traduira par des outils plus rapides.