Imaginez douze amis aux centres d’intérêt variés réunis pour une soirée quiz, tentant de se répartir en deux équipes de niveau équivalent. Zhang maîtrise l’histoire et la géographie, Li connaît le cinéma et la musique pop sur le bout des doigts, tandis que Wang excelle en sport et en cuisine. Pour rendre les deux équipes parfaitement équilibrées dans chaque domaine, le processus de constitution se heurte rapidement à une impasse : dès que l’on déplace Zhang vers l’équipe A pour rééquilibrer le score en histoire, le niveau en géographie de l’équipe A s’envole aussitôt, créant un nouveau déséquilibre sur le plan géographique.
Dilemme en apparence banal, cette situation relève en mathématiques de la théorie combinatoire des écarts (combinatorial discrepancy theory), qui étudie la façon de répartir des objets possédant de multiples caractéristiques en deux groupes tout en minimisant les divergences entre eux. Qu’il s’agisse de distribuer équitablement des modèles et des couleurs de voitures entre deux concessionnaires d’occasion ou de réparer équitablement des patients entre groupe traité et groupe placebo lors d’un essai clinique, la difficulté s’accroît de manière exponentielle dès que plusieurs dimensions entrent en jeu.
Depuis des décennies, les mathématiciens cherchent à déterminer les limites théoriques de ce déséquilibre de découpage. À l’automne 2025, les informaticiens Nikhil Bansal et Haotian Jiang ont proposé un algorithme novateur réduisant drastiquement la limite supérieure du déséquilibre, inchangée depuis près de 30 ans. Leurs travaux démontrent que même face à des ensembles massifs de caractéristiques et à des populations gigantesques, un partage quasi parfait reste tout à fait réalisable.
Pourquoi la répartition équitable hante les mathématiciens depuis des décennies
Dans la vie quotidienne, partager des objets définis par un seul attribut est élémentaire. Si vous possédez 100 parts de gâteau de taille identique, les séparer en deux lots de 50 permet d’obtenir un équilibre parfait. En réalité, cependant, les objets à répartir cumulent presque toujours plusieurs attributs simultanés.
Prenons l’exemple de la répartition des voitures d’occasion : les véhicules vendus en gros présentent des couleurs de carrosserie, des modèles et des kilométrages différents. Si l’on se contente de séparer le stock par le nombre total, un concessionnaire risque de hériter de la majorité des cabriolets tandis que l’autre recevra la plupart des berlines rouges. Chaque concessionnaire souhaite que l’ensemble des indicateurs soient alignés, mais chaque attribut tire le schéma de répartition dans une direction différente.
Dans les essais cliniques, cette interdépendance est encore plus étroite. Les chercheurs doivent répartir les participants entre groupe de traitement et groupe témoin en veillant non seulement à maintenir une distribution d’âge similaire, mais aussi à équilibrer la pression artérielle, les pathologies sous-jacentes et les habitudes de vie. Un déséquilibre marqué sur une seule dimension risquerait de compromettre la validité des résultats. Ces caractéristiques entrelacées forment aux yeux des mathématiciens un terrain de tir à la corde d’une grande complexité.
Une conjecture autrefois qualifiée d’imprudente
Afin d’éclairer théoriquement les limites du partage, le mathématicien hongrois János Komlós a formulé au début des années 1980 la célèbre conjecture de Komlós. Il a suggéré que quel que soit le nombre d’objets et le nombre de dimensions qui leur sont associées, il existe toujours un schéma de découpage dans lequel l’écart numérique maximal entre les deux groupes sur chaque caractéristique (l’écart, ou discrepancy) ne dépasse jamais une même constante fixe.
János Komlós a lui-même plaisanté plus tard en confiant qu’il n’avait osé avancer cette conjecture à l’époque que par témérité de jeunesse. En l’absence d’outils mathématiques adéquats à cette période, prouver une borne constante indépendante du nombre d’objets s’avérait extrêmement difficile, au point qu’il qualifiait sa propre proposition de “conjecture irresponsable”.
La communauté scientifique s’est engagée par la suite dans une longue course de relais. En 1985, le mathématicien Joel Spencer a prouvé que l’écart pouvait être contenu dans le logarithme log N du nombre d’objets N ; en 1998, Wojciech Banaszczyk a affiné cette borne supérieure jusqu’à la racine carrée de log N. Dès lors, l’ensemble de la communauté mathématique est restée bloquée devant ce record pendant près de 30 ans, de nombreux chercheurs doutant même qu’il puisse être dépassé un jour.
Une percée algorithmique née d’une visite d’une semaine
Le tournant s’est produit en février 2025. Haotian Jiang, alors doctorant à l’Université de Washington et aujourd’hui en poste à l’Université de Chicago, s’est rendu à l’Université du Michigan à Ann Arbor pour rendre visite au chercheur Nikhil Bansal. En 2010, Bansal avait déjà conçu un algorithme décomposant les objets avant de les recombiner par perturbations aléatoires, égalant ainsi le record de Spencer.
Dès le deuxième jour de la visite de Jiang, les deux chercheurs ont identifié un nouvel axe d’attaque au cours de leurs discussions. Après un demi-an de démonstrations et de raffinements, ils ont officiellement présenté leur nouvel algorithme à l’automne 2025, abaissant la borne supérieure de l’écart maximal à la racine quatrième de log N, soit log(N)^(1/4). C’était la première fois en près de trois décennies que l’impasse théorique dans ce domaine était franchie.
Figure : Schéma conceptuel mathématique sur le tir à la corde vectoriel et le découpage équilibré. Source : Quanta Magazine / Ada Zejun Shen
Figure : Les deux chercheurs à l’origine de la percée sur la conjecture de Komlós : Haotian Jiang (à gauche) et Nikhil Bansal (à droite). Source : Quanta Magazine / Emily France, University of Michigan
Comment empêcher les attributs complexes de s’interférer
Les algorithmes de répartition antérieurs se concentraient généralement sur le cumul final du déséquilibre global. Lorsque le nombre d’attributs augmentait, l’ajustement apporté à une caractéristique provoquait souvent un effet papillon perturbant fortement l’équilibre des autres.
La nouvelle méthode de Bansal et Jiang introduit une mesure précise de la “dépendance”. Ils ont conçu un mécanisme permettant d’évaluer dans quelle mesure la perturbation aléatoire d’un attribut entraîne des variations en cascade sur les autres attributs.
En isolant les interférences aléatoires entre attributs pendant le calcul, l’algorithme permet à chaque dimension d’effectuer un micro-ajustement indépendant sans interférer avec les autres. Cette structure abaisse non seulement la borne théorique à la racine quatrième, mais fournit également un algorithme efficace (efficient algorithm) directement déployable en calcul pratique.
Répartir tous les atomes de l’Univers n’engendre qu’un écart de 3
La racine quatrième de log N peut sembler abstraite sous forme de formule mathématique, mais transposée à l’échelle du monde réel, la portée intuitive du résultat devient évidente.
Pour un nombre d’objets N = 10, la valeur de la racine quatrième du logarithme est environ égale à 1. Si l’on augmente le nombre d’objets jusqu’au nombre estimé d’atomes dans l’Univers observable — soit environ 10^81 (un 1 suivi de 81 zéros) —, l’écart maximal calculé par cette formule n’atteint que 3 environ.
Le mathématicien de l’Université Yale Daniel Spielman a souligné qu’au cours d’une vie humaine, il est pratiquement impossible de croiser une valeur de racine quatrième de logarithme supérieure à 5. Cela signifie que même si le volume de données s’accroît jusqu’à des échelles astronomiques, l’ampleur du déséquilibre reste quasi stationnaire, infiniment proche d’une constante.
Aleksandar Nikolov, chercheur à l’Université de Toronto, a avoué qu’il penchait auparavant pour l’invalidation de la conjecture de Komlós, mais que cette nouvelle avancée l’a convaincu à nouveau de sa très forte probabilité d’être vraie. Rainie Heck, chercheuse à l’Institut Rényi en Hongrie, a également indiqué que cette théorie commence à être appliquée à l’optimisation des grands modèles de langage et des systèmes d’apprentissage automatique, et qu’il est fort probable que quelqu’un finisse par prouver définitivement l’existence d’une borne constante.
Une équité quasi parfaite désormais à portée de main
Obtenir un partage d’une équité absolue et sans la moindre erreur entre des éléments aux caractéristiques complexes se heurte à des limites mathématiques fondamentales. Néanmoins, la percée de Bansal et Jiang prouve au monde qu’un équilibre quasi parfait est non seulement réalisable en théorie, mais aussi accessible de manière efficace grâce aux ordinateurs.
De la conjecture posée il y a 40 ans et jugée alors imprudente jusqu’au mur de la racine carrée qui a résisté pendant 30 ans, les mathématiciens ont repoussé pas à pas les limites théoriques du déséquilibre. Grâce à un algorithme d’une grande finesse, ils ont démontré que face à un monde d’une extrême complexité, l’esprit humain possède la capacité d’imposer l’ordre au chaos.
Lien de référence :
- Rapport de Quanta Magazine
